4. Численное решение систем уравнений Решение систем линейных уравнений

 

 

Способы решения систем линейных уравнений делятся на две группы:

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

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

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

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

Решение матричных уравнений

 Рассмотрим систему n линейных алгебраических уравнений относительно n неизвестных :

                                                                   (4.1)

В соответствии с правилом умножения матриц рассмотренная система линейных уравнений может быть записана в матричном виде:

                                      

Ax=b,                                                             (4.2)

где:

      ,   ,   .                                    (4.3)

 

 

Рис. 4.1. Решение матричных уравнений

Матрица A, столбцами которой являются коэффициенты  при соответствующих неизвестных, а строками – коэффициенты при неизвестных в соответствующем уравнении, называется матицей системы; матрица-столбец b, элементами которой являются правые части уравнений системы, называется матрицей правой части или просто правой частью системы. Матрица-столбец x, элементы которой – искомые неизвестные, называются решением системы.

Если матрица A - неособенная, то есть , то система (4.1), или эквивалентное ей матричное уравнение (4.2), имеет единственное решение.

В самом деле, при условии  существует обратная матрица . Умножая обе части уравнения (4.2) на матрицу , получим:

                                              ,                                                  (4.4)

Формула (4.4) дает решение уравнения (4.2) и оно единственно.

Системы линейных уравнений удобно решать с помощью функции lsolve. 

На рис. 4.1 показано решение системы трех линейных уравнений относительно трех неизвестных.

 

Метод Гаусса

Метод Гаусса, его еще называют методом Гауссовых исключений, состоит в том, что систему (4.1) приводят последовательным исключений неизвестных к эквивалентной системе с треугольной матрицей:

решение которой находится по рекуррентным формулам:        

              ,  , (i=n-1, n-2, …1)                          (4.5)

Рис. 4.2. Метод Гаусса

Метод итерации

 

Пусть дана линейная система (4.1). Введя в рассмотрения матрицы (4.3), систему (4.1), коротко можно записать в виде матричного уравнения (4.2). Предполагая, что диагональные коэффициенты , (1, 2, …), разрешим первое уравнение системы (4.1) относительно x₁, второе – относительно x₂ и т.д. Тогда получим эквивалентную систему:

                  ,                       (4.6)

где

;   при и  при i=j  (i,j=1, 2, …, n).

Введя матрицы

 и ,

систему (4.6) можно записать в матичной форме: , а (k+1) приближение вычисляется по формуле:

                                                                               (4.7)

Приведем достаточное условие сходимости метода итерации.

Теорема. Процесс итерации для приведенной линейной системы (4.6) сходится к единственному ее решению, если какая-нибудь каноническая форма матрицы  меньше единицы, т.е. для итерационного процесса (4.7) достаточное условие есть:

                                                                                                         (4.8)

Следствие 1. Процесс итерации для системы (4.6) сходится, если:

1)  (m- норма или неопределенная норма)

или

2)  (l - норма или норма L1)

или

3)  (k - норма или Евклидова норма).

 Следствие 2. Для системы (4.1) процесс итерации сходится, если выполнены неравенства:

1) (i=1, 2, …, n)

или

2) (j=1, 2, …, n)

 

где штрих у знака суммы означает, что при суммировании пропускаются значения i=j, т.е. сходимость имеет место, если модули диагональных элементов матрицы A системы (4.1) или для каждой строки превышает сумму модулей недиагональных элементов этой строки, или же для каждого столбца превышает сумму модулей недиагональных элементов этого столбца.

Метод Зейделя

 

Метод Зейделя представляет собой некоторую модификацию метода итераций. Основная его идея заключается в том, что при вычислении (k+1)-го приближения неизвестной x_i учитываются уже вычисленные ранее (k+1)-е приближения неизвестных .

Пусть получена эквивалентная система (4.6). Выберем произвольно начальные приближения корней . Далее, предполагая, что k-ые приближения  корней известны, согласно Зейделю будем строить (k+1)-е приближения корней по формулам:

                     (4.9)

(k=0, 1, 2, …)

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