Решение Слау методом Гаусса

 

1.Теоретическая часть

1.1 Постановка задачи

Рассмотрим систему линейных алгебраических уравнений (СЛАУ)

,     (1)

где - матрица , - искомый вектор, - заданный вектор. Будем предполагать, что определитель матрицы отличен от нуля, т.е. решение системы (1) существует.

1.2 Описание метода Гаусса

Одним из самых распространенных методов решения систем линейных уравнений является метод Гаусса. Этот метод (который также называют методом последовательного исключения неизвестных) известен в различных  вариантах уже более 2000 лет.

1.2.1 Сущность метода исключения Гаусса

Это метод последовательного  исключения переменных, когда с помощью  элементарных преобразований система  уравнений приводится к равносильной системе ступенчатого (или треугольного) вида, из которого последовательно, начиная  с последних (по номеру) переменных, находятся все остальные переменные.

Метод заключается в том, что при прямом ходе в алгоритме  метода Гаусса на каждом шаге исключения производится выбор наибольшего  по модулю элемента в качестве ведущего. Этого достигают перестановкой  строк или столбцов матрицы коэффициентов. Наиболее распространённой в вычислительной практике является стратегия выбора главного элемента столбца - нахождение максимального по модулю элемента k-го столбца матрицы и использование  его в качестве ведущего элемента на k-м шаге исключения. В этом случае для невырожденных систем гарантируется, что ведущие элементы не равны  нулю, и уменьшается погрешность  при делении и последующем  вычитании при преобразованиях. Рекомендуется также масштабировать предварительно каждое уравнение исходной системы, разделив на его наибольший по абсолютной величине коэффициент. Это  делает рост элементов промежуточных  матриц ограниченным.

 

 

Помимо аналитического решения  СЛАУ, метод Гаусса также применяется  для:

a) нахождения матрицы,  обратной к данной (к матрице  справа приписывается единичная  такого же размера, что и  исходная: , после чего приводится  к виду единичной матрицы методом  Гаусса-Жордана; в результате  на месте изначальной единичной  матрицы справа оказывается обратная  к исходной матрица: );

b) определения ранга матрицы  (согласно следствию из теоремы  Кронекера-Капелли ранг матрицы  равен числу её главных переменных);

c) численного решения  СЛАУ в вычислительной технике  (ввиду погрешности вычислений  используется Метод Гаусса с  выделением главного элемента, суть  которого заключена в том, чтобы  на каждом шаге в качестве  главной переменной выбирать  ту, при которой среди оставшихся  после вычёркивания очередных  строк и столбцов стоит максимальный  по модулю коэффициент).

Для контроля ошибки реализации метода используются так называемые контрольные суммы. Схема контроля основывается на следующем очевидном  положении. Увеличение значения всех неизвестных  на единицу равносильно замене данной системы контрольной системой, в  которой свободные члены равны  суммам всех коэффициентов соответствующей  строки. Создадим дополнительный столбец, хранящий сумму элементов матрицы  по строкам. На каждом шаге реализации прямого хода метода Гаусса будем  выполнять преобразования и над  элементами этого столбца, и сравнивать их значение с суммой по строке преобразованной  матрицы. В случае не совпадения значений счет прерывается.

1.2.2 Точность метода

Корни, полученные методом  Гаусса точны при следующих условиях:

· Коэффициенты в задании  даны точно

· По ходу работы не выполнялись  округления.

1.2.3 Преимущества и недостатки метода Гаусса

Итак, метод Гаусса применим к любой системе линейных уравнений, он идеально подходит для решения  систем, содержащих больше трех линейных уравнений. Метод Гаусса решения  СЛАУ с числовыми коэффициентами в силу простоты и однотипности выполняемых  операций пригоден для счета на электронно-вычислительных машинах.

Достоинства метода:

a) менее трудоёмкий по  сравнению с другими методами;

b) позволяет однозначно  установить, совместна система или  нет, и если совместна, найти  её решение;

c) позволяет найти максимальное  число линейно независимых уравнений  - ранг матрицы системы.

Недостатки  метода:

Один из основных недостатков  метода Гаусса связан с тем, что при  его реализации накапливается вычислительная погрешность. Для больших систем порядка m число действий умножений и делений близко к .

Для того, чтобы уменьшить  рост вычислительной погрешности применяются  различные модификации метода Гаусса. Например, метод Гаусса с выбором  главного элемента по столбцам, в этом случае на каждом этапе прямого хода строки матрицы переставляются таким  образом, чтобы диагональный угловой  элемент был максимальным. При  исключении соответствующего неизвестного из других строк деление будет  производиться на наибольший из возможных  коэффициентов и следовательно  относительная погрешность будет  наименьшей.

Так же существенным недостатком этого метода является невозможность сформулировать условия совместности и определенности системы в зависимости от значений коэффициентов и свободных членов. С другой стороны, даже в случае определенной системы этот метод не позволяет найти общие формулы, выражающие решение системы через ее коэффициенты и свободные члены, которые необходимо иметь при теоретических исследованиях.

 

 

1.2.4 Условие применимости метода

Необходимым и достаточным  условием применимости метода является неравенство нулю всех «ведущих элементов» (на диагонали полученной матрицы  не должно быть нулевых элементов).

 

1.3 Алгоритм решения системы методом Гаусса

1.3.1 Общий случай

Процесс решения по методу Гаусса состоит из двух этапов: прямой и обратный ходы.

Процесс приведения к системе  с треугольной матрицей называется прямым ходом, а нахождения неизвестных - обратным. Если один из ведущих элементов  равен нулю, изложенный алгоритм метода Гаусса неприменим. Тем не менее, для  нормальной матрицы с ненулевым  определителем всегда возможна такая  перестановка уравнений, что на главной  диагонали не будет нулей. В приведенном  коде для простоты перестановок не делается, зато делается проверка решения, а прямой и обратный ход для  наглядности вынесены в отдельные  подпрограммы.

На первом этапе осуществляется так называемый прямой ход, когда  путём элементарных преобразований над строками систему приводят к  ступенчатой или треугольной  форме, либо устанавливают, что система  несовместна. А именно, среди элементов  первого столбца матрицы выбирают ненулевой, перемещают его на крайнее  верхнее положение перестановкой  строк и вычитают получившуюся после  перестановки первую строку из остальных  строк, домножив её на величину, равную отношению первого элемента каждой из этих строк к первому элементу первой строки, обнуляя тем самым  столбец под ним.

После того, как указанные  преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого размера. Если на какой-то из итераций среди  элементов первого столбца не нашёлся ненулевой, то переходят  к следующему столбцу и проделывают  аналогичную операцию.

На первом этапе (прямой ход) система приводится к ступенчатому (в частности, треугольному) виду.

Если в процессе приведения системы к ступенчатому виду появятся нулевые уравнения, т.е. равенства  вида 0=0, их отбрасывают. Если же появится уравнение вида  то это свидетельствует  о несовместности системы.

На этом прямой ход метода Гаусса заканчивается.

Алгоритм прямого прохода:

Выбрать максимальный элемент  строки стоящий справа от текущего диагонального элемента, запомнить  столбец, в котором он стоит;

Если максимальный элемент  равен нулю, то СЛАУ не имеет решения, т.к. в системе присутствую линейно  зависимые уравнения;

Поменять столбец найденный  в пункте 1, со столбцом, в котором  располагается текущий диагональный элемент;

Разделить все элементы строки на текущий диагональный элемент (он изменился, т.к. столбцы были переставлены);

Вычитаем текущую строку из ниже лежащих строк матрицы, умножая  ее на коэффициент при соответствующем  неизвестном.

Прямой проход завершен, результат – нижняя (находящаяся  под главной диагональю) треугольная  матрица заполнена нулями.

На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить  фундаментальную систему решений, либо, если все переменные являются базисными, то выразить в численном  виде единственное решение системы  линейных уравнений.

Эта процедура начинается с последнего уравнения, из которого выражают соответствующую базисную переменную (она в нем всего  одна) и подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх.

Каждой строчке соответствует  ровно одна базисная переменная, поэтому  на каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет  случай последней строки.

Примечание: на практике удобнее  работать не с системой, а с расширенной  ее матрицей, выполняя все элементарные преобразования над ее строками. Удобно, чтобы коэффициент a₁₁ был равен 1 (уравнения переставить местами, либо разделить обе части уравнения на a₁₁).

Запишем систему  Ax=f,  в развернутом виде                                               

Предположим, что  . Последовательно умножая первое уравнение на и складывая с i-м уравнение, исключим из всех уравнений кроме первого. Получим систему

 

Аналогичным образом из полученной системы  исключим . Последовательно, исключая все неизвестные, получим систему треугольного вида

Описанная процедура называется прямым ходом метода Гаусса. Заметим, что ее выполнение было возможно при  условии, что все  , не равны нулю.

Выполняя последовательные подстановки в последней системе, (начиная с последнего уравнения) можно получить все значения неизвестных.

    .

Эта процедура получила название обратный ход метода Гаусса.

1.3.2 Описание алгоритма на примере системы 4-х уравнений с 4-мя неизвестными.

Рассмотрим систему 4-х уравнений с 4-мя неизвестными.

 a₁₁x₁+a₁₂ x₂+a₁₃x₃+a₁₄x₄=a₁₅,

a₂₁x₁+a₂₂ x₂+a₂₃ x₃+a₂₄x₄=a₂₅,

a₃₁x₁+a₃₂ x₂+a₃₃x₃+a₃₄x₄=a₃₅, (1)

a₄₁x₁+a₄₂ x₂+a₄₃x₃+a₄₄ x₄=a₄₅,

Пусть a₁₁0 (ведущий элемент). Разделив коэффициенты 1-го уравнения системы на a₁₁, получим:

x₁+b₁₂ x₂+b₁₃x₃+b₁₄x₄=b₁₅, (2)

(j>1).

Пользуясь уравнением (2), легко  исключить из системы (1) неизвестную x₁. Для этого достаточно из 2-го уравнения системы (1) вычесть уравнение (2), умноженное на a₂₁, а из 3-го уравнения системы (1) вычесть уравнение (2), умноженное на a₃₁ и т. д. В результате получим систему из трёх уравнений:

a⁽¹⁾₂₂x₂+a⁽¹⁾₂₃x₃+a⁽¹⁾₂₄x₄=a⁽¹⁾₂₅,

a⁽¹⁾₃₂x₂+a⁽¹⁾₃₃x₃+a⁽¹⁾₃₄x₄=a⁽¹⁾₃₅,

a⁽¹⁾₄₂x₂+a⁽¹⁾₄₃x₃+a⁽¹⁾₄₄x₄=a⁽¹⁾₄₅, (1')

где коэффициенты a⁽¹⁾_ij вычисляются по формуле

a⁽¹⁾_ij = a_ij - a_i1b_1j (i, j 2).

Далее, разделив коэффициенты первого уравнения системы (1') на ведущий элемент a⁽¹⁾₂₂, получим уравнение

x₂+b⁽¹⁾₂₃x₃+b⁽¹⁾₂₄x₄=b⁽¹⁾₂₅ (2')

где (j > 2).

Исключая теперь х₂ таким же способом, каким мы исключили x¹, придем к следующей системе уравнений:

a⁽²⁾₃₃x₃+a⁽²⁾₃₄x₄=a⁽²⁾₃₅

a⁽²⁾₄₃x₃+a⁽²⁾₄₄x₄=a⁽²⁾₄₅ (1'')

a⁽²⁾_ij = a⁽¹⁾_ij - a_i2b⁽¹⁾_2j (i, j 3).

Затем разделим коэффициенты первого уравнения системы (1'') на “ведущий элемент” a⁽²⁾₃₃ и получим:

x₃+b⁽²⁾₃₄x₄=b⁽²⁾₃₅, (2'')

где

(j > 3).

Исключив аналогичным  путём x₃ из системы (1''), будем иметь:

a⁽³⁾₄₄x₄=a⁽³⁾₄₅

где a⁽³⁾_ij = a⁽²⁾_ij - a_i3b⁽²⁾_3j (i, j 4).

Отсюда

x₄ = (2''')

Остальные неизвестные последовательно находятся из уравнений (2''), (2') и (2).

x₃ = b⁽²⁾₃₅ - b⁽²⁾₃₄x₄,

x₂ = b⁽¹⁾₂₅ - b⁽¹⁾₂₃x₃ - b⁽¹⁾₂₄x₄,

x₁ = b₁₅ - b₁₂x₂ - b₁₃x₃ - b₁₄x₄.

Таким образом, процесс решения  линейной системы по методу Гаусса сводится к построению эквивалентной  системы (2), (2'), (2''), (2'''), имеющей треугольную  матрицу.

Вычисления удобно помещать в таблицу.

 

2. Практическая часть

2.1 Примеры

Пример 1)

Покажем, как методом Гаусса можно решить следующую систему:

Обнулим коэффициенты при  x во второй и третьей строчках. Для этого вычтем из них первую строчку, умноженную на   и -1 , соответственно:

Теперь обнулим коэффициент  при y в третьей строке, вычтя из неё вторую строку, умноженную на 4 :

В результате мы привели  исходную систему к треугольному виду, тем самым закончив первый этап алгоритма.

На втором этапе разрешим полученные уравнения в обратном порядке. Имеем:

z = - 1 из третьего;

y = 3 из второго, подставив полученное z

 x = 2 из первого, подставив полученные z и y.

Таким образом, исходная система  решена.

В случае если число уравнений  в совместной системе получилось меньше числа неизвестных, то тогда  ответ будет записываться в виде фундаментальной системы решений.

 

Пример 2)

Перепишем систему линейных алгебраических уравнений в матричную  форму. Получится матрица 3 × 4, слева  от разделительной линии стоят коэффициенты при переменных, а справа стоят  свободные члены.

Проведём следующие действия:

Из  второй строки  вычтем первую строку, умноженную на 3;

Из третьей строки  вычтем первую строку:

Вторую строку умножим на -1;

Из третьей строки вычтем вторую строку:

Третью строку умножим на -1;

Из второй строки вычтем третью строку, умноженную на 2;

Из первой строки вычтем третью строку, умноженную на 3:

Из первой строки вычтем вторую строку, умноженную на 2:

В левой части матрицы  по главной диагонали остались одни единицы. В правом столбце получаем решение:

 х₁ = -4

 х₂ = -13

 х₃ = 11

Пример 3) 

 Найдите общее решение  системы уравнений 

 

где неизвестными являются  x₁,..x₆.

Выпишем расширенную матрицу  системы 

Прибавим ко второй строке первую, умноженную на число -4;

к третьей строке прибавим первую, умноженную на  -3:

 

Прибавим к третьей  строке вторую, умноженную на число  -2:

Прямой ход метода Гаусса закончен. Выписываем по полученной матрице систему уравнений:

 

Переносим в правую часть  неизвестные x₁, x₃, x₄, x₆ (неизвестное x₁ реально в ней присутствовать не будет, коэффициент перед ним равен нулю). Получаем :

Пусть x₁=C₁, x₃=C₂, x₄=C₃, x₆=C₄ . Из уравнений находим:

Ответ: x₁=C₁ ,  x₂= 5-C₂+ C₃+C₄ , x₃=C₂ , x₄=C₃ , x₅= - 2- C₄ , x₆=C₄ , где C₁, C₂, C₃, C₄ -произвольные числа.        

Замечание:  В процессе решения можно также установить, какие ранги у матриц  и  где расположены их базисные миноры. В предыдущем примере  базисный минор расположен в строках с номерами 1, 2, в столбцах с номерами 2, 5.        

Пример 4)

Найдите общее решение системы уравнений

 

Запишем расширенную матрицу  системы:

 

Ко второй строке прибавим первую, умноженную на -20;

к третьей строке прибавим первую, умноженную на -4;

к четвертой строке прибавим первую, умноженную на -5:

 

Вторую строку, умноженную на  -1, прибавим к третьей:

 

В третьей строке все элементы a_3j  равны нулю, а элемент b₃ ≠ 0 . Значит, система несовместна.

Ответ: Система несовместна.        

Пример 5)

Решите систему 

 

Запишем расширенную матрицу  системы:

 

Первую строку, умноженную на числа  ,  -1,  -2, прибавим соответственно ко второй, третьей и четвертой строкам:

К третьей строке прибавим вторую, умноженную на  . Получим:

 

К четвертой строке прибавим третью, умноженную на :

Выписываем по полученной матрице  систему уравнений:

 

Находим последовательно  значения неизвестных:

 

Ответ: x₁ = , x₂ = , x₃ = , x₄ = .        

 

 Замечание: Так же, как и при решении системы уравнений по правилу Крамера, при использовании метода Гаусса приходится выполнять большой объем вычислительной работы. Из-за этого вполне возможно, что будет допущена какая-либо ошибка в вычислениях. Поэтому желательно после решения системы выполнить проверку, то есть подставить полученные значения неизвестных в уравнения системы. Для выполнения полной проверки подстановку нужно произвести во все уравнения системы. Если же по каким-то причинам это невыполнимо, то можно подставить найденные значения в одно уравнение. В отличие от правила Крамера в методе Гаусса эту подстановку нужно производить в ПОСЛЕДНЕЕ уравнение исходной системы. При наличии в этом уравнении всех неизвестных эта подстановка почти всегда покажет наличие ошибки, если таковая была допущена.