Решение систем линейных алгебраических уравнений

РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Метод Гаусса

        Методы решения систем линейных алгебраических уравнений разделяются на две группы:

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

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

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

Будем предполагать, что матрица системы [pic 1] невырождена, т.е. определитель системы не равен нулю. В этом случае система имеет единственное решение, которое в курсе линейной алгебры обычно выражают по формулам Крамера в виде отношений определителей. Для численного решения системы эти формулы малопригодны, так как они требуют вычисления [pic 2] определителей, что требует большого числа действий (порядка [pic 3] арифметических операций). Даже при выборе наилучшего метода вычисление одного определителя требует примерно такого же времени, что и решение системы уравнений современными численными методами. Кроме того, следует иметь в виду, что вычисление по формуле Крамера часто ведут к большим погрешностям округления.

Выбор того или иного численного метода зависит от многих обстоятельств - от имеющихся программ, от вида матрицы систем, от типа расчета, от объема оперативной памяти и др.

Наиболее распространенным точным методом является метод Гаусса. Запишем систему уравнений в общем виде:

[pic 4].                                (5.1.46)

Расширенная матрица данной системы имеет вид:

[pic 5].                                                (5.1.47)

        Метод Гаусса состоит из прямого хода и обратного хода. Прямой ход содержит [pic 6] шагов. Рассмотрим первый шаг. Он состоит в исключении [pic 7] из всех уравнений, начиная со второго уравнения. Если [pic 8], то в первом столбце матрицы (5.1.47), начиная с коэффициента [pic 9], ищем коэффициент не равный нулю. Коэффициенты строки, в которой оказался первый не равный нулю коэффициент, переставляем местами с соответствующими коэффициентами первой строки. Если [pic 10], то эти действия не нужны.

        Далее делим коэффициенты первой строки на [pic 11]. Тогда в первой строке матрицы получим следующие коэффициенты:

[pic 12]    [pic 13]    [pic 14]    [pic 15]    [pic 16]    [pic 17].                                        (5.1.48)

        После этого из коэффициентов каждой строки матрицы (5.1.47), начиная со второй строки, вычитаем соответствующие коэффициенты первой строки (5.1.48), умноженные на первый коэффициент строки. Например, из второй строки вычитаем (5.1.48), умноженные на [pic 18].

        В результате этих действий матрица (5.1.47) будет иметь следующий вид:

[pic 19].                                        (5.1.49)

На втором шаге исключаем [pic 20] из всех уравнений, начиная с третьего. Действия данного шага аналогичны действиям первого шага. На этом шаге преобразуется матрица (5.1.49), кроме ее первой строки и первого столбца. В результате второго шага расширенная матрица системы будет иметь вид:

[pic 21].

После [pic 22] шагов матрица системы приведем к треугольному виду:

[pic 23].                                        (5.1.50)