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

 

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 , соответственно: