Вычислительная математика. Ч. 1. Асламова В.С - 35 стр.

                                                                                                   ⎧b1x1 + c1x2                                                 = d1
                 3                                         1                                       ⎪        a2 x1 + b2 x2 + c2 x3                               = d2
                                                                                                   ⎪
                                    Вывод                                                          ⎪⎪                a3 x2 + b3 x3 + c3 x4                      = d3 (4.19)
                           да       корней                        да                                ⎨
                δ<ε                   x[i];              δ M-1                                x[i] := xx
                                                                                На главной диагонали матрицы этой системы стоят элементы b1, b2, ,bn, над
                     да                                                      ней – элементы c1, c2, ,cn-1, под ней – элементы a1, a2, ,an. При этом обычно все
                                                           2                 коэффициенты bi не равны нулю.
           Нет сходимости                                                       Метод прогонки состоит из двух этапов – прямой прогонки (аналога прямого
           за М итераций                                                     хода метода Гаусса) и обратной прогонки (аналога обратного хода метода
                                                                             Гаусса). Прямая прогонка состоит в том, что каждое неизвестное xi выражается
                                                                             через xi+1 с помощью прогоночных коэффициентов AAi, BBi:
               Конец                                                                                   xi =AAi xi+1+BBi,                         i=1,2, , n-1.       (4.20)
                                                                                Из первого уравнения системы (4.19) найдём
            Рис. 37. Блок-схема метода Гаусса-Зейделя.                                                                       c             d
                                                                                                                   x1 = − 1 ⋅ x 2 + 1 .
   Для сходимости итерационного метода достаточно, чтобы модули
                                                                                                                             b1            b1
диагональных коэффициентов для каждого уравнения системы были не меньше         С другой стороны, по формуле (4.20) x1=AA1x2+BB1. Приравнивая
сумм модулей всех остальных коэффициентов:                                   коэффициенты в обоих выражениях для x1, получаем
                                                                                                                            c                           d
                        a   ≥
                            ii    a ∑ ,
                                           ij
                                                i=1,2, ,n.         (4.18)                                      AA 1 = − 1 ,                   BB 1 = 1 .             (4.21)
                                    i≠ j                                                                                    b1                          b1
   При этом хотя бы для одного уравнения неравенство (4.18) должно              Из второго уравнения системы (4.19) выразим x2 через x3, заменяя x1 по
выполняться строго. Эти условия являются достаточным условием для            формуле (4.20):
сходимости метода, но не являются необходимыми, т.е. для некоторых систем
                                                                                                   a 2 ⋅ ( AA1 x2 + BB1 ) + b2 x2 + c2 x3 = d 2 .
итерации сходятся и при нарушении этих условий.
   В качестве исходных данных вводятся коэффициенты и правые части                                            − c 2 x 3 + d 2 − a 2 BB 1
уравнений системы, погрешность ε , допустимое число итераций М, а также         Отсюда найдём           x2 =                             ,
начальные приближения переменных хi (i=1,2, ,n). Отметим, что начальные
                                                                                                                    a 2 AA 1 + b 2
приближения можно не вводить в ЭВМ, а полагать их равным некоторым              или                          x2 = AA2 x3 + BB2 ,
значениям (например, нулю).
                                                                                                                         d 2 − a2b1
   Блок-схема данного метода представлена на рис. 37.                                                     c
                                                                                                   AA2 = − 2 , BB2 =                 , e 2 = a 2 AA1 + b2 .
                                                                                                          e2                 e2
                                 4.4. Метод прогонки                            Аналогично можно вычислить прогоночные коэффициенты для любого
                                                                             номера i :
   Метод прогонки является модификацией метода Гаусса для частного случая
разреженных систем – системы уравнений с трёхдиагональной матрицей. Такие                                         ci ,                   di − ai bi−1
                                                                                                       AA i = −                  BBi =                ,
системы получаются при моделировании некоторых инженерных задач, а также                                          ei                         ei
при численном решении краевых задач для дифференциальных уравнений.
   Запишем систему уравнений в виде:
                                                                                                       ei = a i AA i −1 + bi ,           i=2,3, , n-1.         (4.22)


                                           69                                                                             70