15.2.3. Метод Гаусса

Следует заметить, что как метод обратной матрицы, так и метод Крамера являются очень трудоемкими по количест­ву вычислительной работы. Оба они требуют порядка N2N! арифметических действий для нахождения решения системы линейных уравнений. При П = 5 это составит около 3000 дей­ствий, при П = 10 — около 3,6 ∙ 108 действий. При решении серьезных задач приходится иметь дело с системами уравне­ний порядка П = 100 и более. При таких масштабах даже су­перкомпьютерам потребуется огромное время для вычисления решения. Кроме того, погрешности компьютерного округления чисел приводят к значительным ошибкам в расчетах численно­го решения систем уравнений большого порядка. Между тем существуют более экономичные методы решения систем ли­нейных уравнений, основанные на предварительном преобра­зовании расширенной матрицы системы к специальному виду. В частности, одним из них является метод Гаусса, практичес­кую реализацию которого мы приводим ниже.

Рассмотрим систему уравнений общего вида (15.1). Пусть для определенности A11 ≠ 0 (если A11 = 0, то можно переста­вить на первое место ненулевое слагаемое или начать с другого уравнения). Умножим первое уравнение системы (15.1) на чис­ло A21/A11 и затем вычтем его из второго уравнения этой системы. Умножим обе части первого уравнения на число A31/A11 и затем вычтем его из третьего уравнения и так далее, т. е. процесс заключается в последовательном вычитании первого уравнения, умножаемого на числа Ai1/A11, из I-го уравнения (I = 2, 3, ... , M). Таким образом, в результате элементарных преобразований мы получим эквивалентную систему, в кото­рой начиная со второго уравнения отсутствуют слагаемые, со­держащие неизвестное X1:

Где верхний индекс в скобках означает новые коэффициенты, полученные после первого шага. Для удобства записи будем оперировать расширенной матрицей системы, отделяя в ней вертикальной чертой столбец свободных членов. Итак, после первого шага, содержащего (т — 1) элементарных преобразо­ваний системы, мы переходим от расширенной матрицы (15.4) исходной системы к расширенной матрице

Второй шаг заключается в том, что теперь второе уравне­ние системы (15.7) или вторая строка матрицы (15.8) исполь­зуется для аналогичных элементарных преобразований строк с третьей по M-ю: эта строка последовательно умножается на число И вычитается из I-й строки (I = 3, 4, ... ,M). В результате этих (M - 2) элементарных преобразований полу­чаем новую расширенную матрицу, соответствующую новой эквивалентной системе уравнений. Эта матрица имеет вид

Где верхний индекс означает новые коэффициенты. В случае если элемент = 0, то второе уравнение можно поменять местами с другим уравнением, у которого элемент ≠ 0.

Продолжим этот процесс аналогичным образом (т. е. на 3-м шаге преобразуются строки с 4-й по Т-Ю, на 4-м шаге — стро­ки с 5-й по M-ю и т. д.) до тех пор, пока не дойдем до последней M-й строки. После (R - 1)-го шага процесса последовательного исключения неизвестных мы получим следующую расширен­ную матрицу:

Последние (M - R) строк этой матрицы соответствуют урав­нениям эквивалентной системы уравнений

Эти уравнения могут появиться, если соответствующие урав­нения исходной системы (15.1) представляют собой линейные комбинации других уравнений этой системы, о чем говорилось в п. 15.1. Здесь мы не исследовали заранее систему (15.1) на совместность; поэтому если эта система несовместна, то хотя бы одно из чисел , ,..., не равно нулю. Таким образом, метод Гаусса позволяет на определенном шаге устано­вить возможную несовместность исходной системы линейных уравнений или выявить и удалить уравнения, являющиеся ли­нейными комбинациями других уравнений системы (15.1), если она совместна.

Пусть система (15.1) совместна, тогда все правые части уравнений (15.10) равны нулю, и после удаления нулевых урав­нений в эквивалентной системе и нулевых строк в расширенной матрице получаем матрицу специфического ступенчатого ви­да, ранг которой равен R. Все элементы этой матрицы, стоящие слева или ниже элементов Аij, равны нулю:

Эта расширенная матрица соответствует системе уравнений ранга R, которая имеет вид

Система уравнений (15.12) уже полностью подготовлена к на­хождению решения, процесс которого осуществляется снизу вверх, т. е. от последнего уравнения к первому. Переход от сис­темы (15.1) к эквивалентной ей системе (15.12) называется Пря­мым ходом, а нахождение неизвестных из системы (15.12) — Обратным ходом метода Гаусса. Далее последовательность действий аналогична изложенной выше.

1. Если R = N, то система (15.12) имеет вид

Поднимаясь снизу вверх, последовательно находим (обратный ход метода Гаусса):

— из последнего R-го уравнения неизвестное Xr = ;

— из (R - 1)-го уравнения неизвестное Xr-1 путем подста­новки в это уравнение уже найденного неизвестного Xr;

— из I-го уравнения неизвестное Xi при подстановке в него найденных величин Xr, xR-1, ..., Xi-1;

— и так далее до первого уравнения, из которого при под­становке в него уже найденных величин Xr, Xr-1 , ..., X2 находим Х1.

2. Ранг системы уравнений (15.12) меньше N. В этом слу­чае, как и ранее, объявляем неизвестные Xr+1, Xr+2, …, Xп, сво­бодными и формируем правые части уравнений (15.12), остав­ляя в левых частях слагаемые, содержащие базисные перемен­ные X1, X2, ..., Xr:

Решение этой системы находится обратным ходом метода; те­перь базисные неизвестные зависят от свободных неизвестных, которые могут принимать любые значения, а потому система (15.1) имеет бесчисленное множество решений.

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

Пример 2. Пример 1 п. 15.2.

Решение. Выпишем расширенную матрицу этой системы; справа в скобках укажем числа, на которые умножается соот­ветствующая строка матрицы для того, чтобы сложить ее с нижними строками. Горизонтальными стрелками показаны пе­реходы к расширенным матрицам эквивалентных систем. Пер­вую строку расширенной матрицы исходной системы умножа­ем последовательно на (-2) и (-1) и прибавляем ее соответ­ственно к 2-й и 3-й строкам этой матрицы. После первого шага, состоящего в "обнулении" первого столбца согласно формуле (15.9), получаем (номера шагов показаны перед стрелками пе­рехода)

Второй шаг прямого хода метода Гаусса состоит в операциях с преобразованной расширенной матрицей: прибавляем вторую строку, умноженную на (-3), к 3-й строке:

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

Которая эквивалентна исходной системе. Отсюда последова­тельно находим: Z = -1/2, У = 0,х = 1- 0 - (-1/2) = 3/2.

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

Решение. Составим расширенную матрицу этой системы, после чего выполним соответствующие шаги прямого хода ме­тода Гаусса. Имеем

Последняя нулевая строка в расширенной матрице, полученной после 3-го шага, появилась из-за того, что в исходной системе четвертое уравнение является суммой 1-го и 3-го уравнений. Система совместная, и после удаления нулевой строки заклю­чительный вид расширенной матрицы соответствует системе трех уравнений с четырьмя неизвестными (ранг системы мень­ше числа неизвестных). Полагая X4 свободной переменной, по­лучаем

Из этой системы обратным ходом метода Гаусса находим

Данная система уравнений имеет бесчисленное множество ре­шений, поскольку X4 может принимать любые значения.

< Предыдущая		Следующая >