Решение систем линейных уравненийметодом Гаусса

Метод Гаусса является точным методом. Он позволяет получить решение системы за конечное число арифметических действий. В основе метода лежит идея последовательного исключения неизвестных. Метод состоит из двух этапов. На первом этапе (прямой ход) система при помощи последовательного исключения неизвестных приводится к треугольному виду. На втором этапе (обратный ход) из системы треугольного вида последовательно, в обратном порядке, начиная c n-го уравнения, находятся неизвестные системы.

В качестве примера возьмем систему 4 порядка.

(9.1)

Прямой ход. На первом шаге прямого хода (к=1) находим x₁ из первого уравнения системы (9.1).

- ведущий элемент первой строки.

Если , то

(9.2)

Обозначим:

(9.3)

Подставляя (9.3) в (9.2), получим

(9.4)

где

Подставляем (9.4) во 2, 3 и 4 уравнение системы (9.1), получим:

Обозначив коэффициенты при неизвестных полученной системы через , а свободные члены через перепишем полученную систему:

(9.5)

где

Таким образом, в результате выполнения первого шага прямого хода исходная система (9.1) n-го порядка преобразована к совокупности уравнения (9.4) и системы линейных уравнений (9.5), порядок которой равен n-1.

На втором шаге прямого хода (к=2) из первого уравнения системы (9.5) находим x₂.

-ведущий элемент первой строки системы (9.5).

Если , то из первого уравнения системы (9.5) имеем:

(9.6)

где

Подставив выражение (9.6) во второе и третье уравнения системы (9.5), получим новую систему линейных уравнений, порядок которой равен n-2.

(9.7)

где

Таким образом, в результате выполнения второго шага прямого хода исходная система (9.1) преобразована к совокупности уравнений (9.4), (9.6) и системы линейных уравнений (9.7),порядок которой равен n-2.

На третьем шаге прямого хода (к=3) из системы (9.7) находим x₃.

- ведущий элемент системы (9.7).

Если , то из первого уравнения системы (9.7) имеем:

(9.8)

где

Подставив выражение (9.8) для x₃ во второе уравнение системы (9.7) получим:

(9.9)

где

На последнем шаге прямого хода, если , то из уравнения (9.9) имеем:

(9.10)

где

(9.11)

В результате выполнения всех шагов прямого хода исходная система (9.1) приводится к системе треугольного вида, полученной объединением уравнений (9.4), (9.6), (9.8), (9.10):

(9.12)

При построении алгоритма прямого хода вычисление организуем в цикле по шагам, т.е. .

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

(9.13)

В процессе выполнения всех шагов прямого хода все преобразования коэффициентов и свободных членов проводим по полученным ранее рекуррентным формулам:

(9.14)

где

– номер шага прямого хода,

- номер уравнения систем (9.5), (9.7)

В процессе обратного хода из системы (9.12) неизвестные находятся в обратном порядке. Значение корня х₄ находят из последнего уравнения системы (9.12). Далее х₄ используется для отыскания корня х₃ из 3-го уравнения, далее х₃ и х₄ используются отыскания х₂ из 2-го уравнения системы (9.12), и, наконец, х₂, х₃ и х₄ используются для отыскания х₁ из 1-го уравнения системы (9.12).

Все вычисления обратного хода проводим в цикле по i, где

по рекуррентным формулам:

x_i= b_i.

Рассмотренный выше простейший вариант метода Гаусса, называемый схемой единственного деления, обладает следующим недостатком: если ведущий элемент a_kk какой-либо строки окажется равным нулю, то этот метод формально непригоден, хотя система может иметь единственное решение. Из этих соображений в схеме алгоритма добавлен поиск ненулевого ведущего элемента.

На рисунке 9.1 представлена укрупнённая схема алгоритма (блок-схема) метода Гаусса. На рисунках 9.2 - 9.6 представлены алгоритмы отдельных блоков метода.

Рис. 9.1. Укрупнённая схема алгоритма (блок-схема) метода Гаусса

Блок 2. С помощью двух вложенных циклов с управляющими переменными i=1,n и j=1,k организуем ввод коэффициентов a_i,j и свободных членов b_i исходной системы. Для того, чтобы в дальнейшем можно было выполнить в блоке 9 проверку результата, в алгоритме предусмотрено сохранение значений a_i,j и b_i исходной системы с помощью переприсвоений: c_ij=a_ij и d_i=b_i

Рис. 9.2.

Блок 3. Организуем цикл по k, внутри которого производится вычисление по всем шагам прямого хода. Последний п-й шаг прямого хода выводим из цикла.

Блок 4. На каждом шаге прямого хода выполняем поиск ненулевого ведущего элемента.

Рис. 9.3.

Поиск ненулевого ведущего элемента ведётся в следующем порядке:

а) На каждом k-ом шаге прямого хода ведущий элемент каждой строки сравнивается с нулём;

б) Если в k-ой строке имеется нулевой ведущий элемент, то в k-ом столбце в цикле осуществляется поиск ненулевого элемента.

в) Если в какой-то строке kn такой ненулевой элемент найден, то строки kn и k поэлементно, в цикле по k1=(k+1),n,меняем местами. Для перестановки элементов используется рабочая переменная R.

г) Если ненулевой ведущий элемент не найден, то коду ошибки kо присваиваем значение 1 и расчёт прекращается.

Блок 5 - шаг прямого хода. На каждом шаге прямого хода проводим исключение неизвестных путём преобразования коэффициентов и свободных членов системы по полученным ранее рекуррентным формулам.

Рис. 9.4.

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

x_n=b_n/a_n,n

Блок 7 - обратный ход. В процессе обратного хода метода Гаусса из системы треугольного вида последовательно в обратном порядке в цикле по i=(n-1),1,-1 находим неизвестные системы по рекуррентной формуле

b_i= b_i - x_j.a_i,j, i=(n-1),1, j=(n+1),n.

При этом в цикле по j=(i+1),n использован приём последовательного вычитания x_j.a_i,j из b_i,после чего вводится переприсвоение b_i =х_i.

Рис. 9.5.

Блок 9 - проверка результата. В этом блоке подставляя значения полученных неизвестных в исходную систему и используя сохранённые значения коэффициентов системы c_i,j и свободных членов d_i, проводим проверку решения задачи по формуле

Если корни системы найдены, то F_i – это число, близкое к нулю.

Блок 9 в алгоритме метода Гаусса рекомендуется использовать только в процессе отладки метода.

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

Рис. 9.6.