Итерациональные методы решения нелинейных уравнений

ГЛАВА 4. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ. 

       Пусть дана система линейных алгебраических уравнений (СЛАУ) вида

                  (4.1)

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

             , ,  (4.2)

систему (4.1) можно записать в виде матричного уравнения

                                    .  (4.3)

      Для решения систем линейных алгебраических уравнений существуют точные методы: метод Гаусса, с помощью обратной матрицы (матричный метод), по формулам Крамера. Однако, при большом числе неизвестных применение точных методов решения затруднено. В этом случае для нахождения корней системы (4.1) целесообразнее пользоваться приближенными (численными) методами, которые и будут рассмотрены в данной главе. 

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

      Пусть дана система линейных алгебраических уравнений вида (4.1).

      Предположим, что диагональные элементы матрицы  не равны нулю, т.е. (в случае равенства одного или нескольких из них нулю, с помощью перестановки уравнений или других эквивалентных преобразований можно добиться, чтобы они были отличны от нуля). Разделив -ое уравнение системы на , получим:

                  (4.4)

где коэффициенты при .

      Введем  обозначения:

                    ,  (4.5)

      Тогда система (4.4) примет вид:

                              (4.6)

      Систему (4.6) будем решать методом последовательных приближений. Выбираем начальное приближение ; далее вычисляем следующие приближения:

          , ,…, , … (4.7)

      Если  последовательность приближений  является сходящейся, т.е. у нее существует предел , то этот предел является решением системы (4.6). Действительно,

                .

      Получили , т.е. – является решением системы (4.6), а система (4.6) получена из системы (4.1), следовательно, будет являться решением исходной системы (4.1).

      Теорема 4.1 (достаточное условие сходимости итерационного процесса).

      Если  для приведенной системы  выполнено хотя бы одно из условий:

а)

б) ,

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

      В частности процесс итерации заведомо сходится, если элементы приведенной системы (4.4) удовлетворяют неравенству , где - число неизвестных системы. 

      Следствие.

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

      Теорема 4.2 (необходимое и достаточное условие сходимости процесса итерации для системы линейных уравнений).

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

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

      Теорема сходимости итерационного процесса накладывает жесткие условия  на коэффициенты системы (4.3). Однако, если , то с помощью элементарных преобразований системы (4.3) ее можно заменить эквивалентной системой , такой, что условия теоремы сходимости будут выполнены.

      Умножим левую и правую часть соотношения (4.3) слева на матрицу  , где - матрица с малыми по модулю элементами.

      Проведем  преобразования:

                        

      Если  обозначить , , то получим .

      Если  элементы матрицы  достаточно малы по модулю, т.е. , то элементы матрицы будут удовлетворять достаточному условию сходимости итерационного процесса.

      Итерационный  процесс заканчивается, если для  двух приближений  и выполнено условие , где - заданная точность. 

§4.2. Метод Зейделя. 

      Метод Зейделя представляет собой  некоторую модификацию метода простых итераций. Основная его идея состоит в том, что при вычислении -го приближения неизвестной учитываются уже вычисленные ранее -е приближения неизвестных . Т.е. найденное -е приближение сразу же используется для получения -го приближения последующих координат (Рис.4.1).

     Предполагая, что  -е приближения корней системы (4.4) известны, -е приближения корней будут находиться по следующим итерационным формулам метода Зейделя:

                .  (4.8)

      Теорема 4.3 (достаточное условие сходимости метода Зейделя).

      Если  для приведенной системы  выполнено хотя бы одно из условий:

1) , где ;

2) , где ;

3) , где ,

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

      Запишем систему (4.8) в сокращенном виде:

               (4.9)

      Введем  обозначения: , где

        , .

      Тогда формулу (4.9) можем переписать в матричном  виде:

                         , (4.10)

где

, , .

      Теорема 4.4 (необходимые и достаточные условия сходимости метода Зейделя).

      Для сходимости процесса Зейделя, заданного  формулой (4.9), для приведенной системы линейных уравнений (4.4) при любом выборе свободного члена и начального вектора необходимо и достаточно, чтобы все корни уравнения были по модулю меньше единицы.

     Пример 4.1. Построить рабочие формулы метода простых итераций и метода Зейделя для численного решения СЛАУ вида:

                            (4.11)

     Решение.

     Заметим, что система (4.11) имеет точное решение  .

     Из  системы (4.11) видно, что модули диагональных коэффициентов в каждом уравнении отличны от нуля и больше суммы модулей всех остальных коэффициентов, не считая столбца свободных членов. Тогда, разделим каждое уравнение системы (4.11) на соответствующий диагональный коэффициент, сформируем столбец в левой части и перенесем остальные слагаемые в правую часть, получим рабочие формулы метода простых итераций вида:

                  

     Начальное приближение обычно выбирают равным столбцу свободных членов преобразованной системы .

     Рабочие формулы метода Зейделя запишутся  так:

                    

§4.3. Метод релаксации. 

      Рассмотрим  систему линейных алгебраических уравнений (4.1)

в которой  .

      Сделаем преобразования: свободные члены  перенесем в левую часть и каждое -ое уравнение поделим на . Таким образом, получим систему, удобную для релаксации:

                      (4.12)

где .

      Введем  понятие невязки для приближенного  решения  .

      Пусть дана система  , тогда точное решение можно записать в виде , где -правка корня . Подставим в систему, получим

      Введем  обозначение  . Тогда . Выражение называется невязкой для приближенного решения .

      Пусть задано начальное приближение системы (4.12):

.

      Подставим данное приближение в систему (4.12) и получим невязки  :

                     (4.13)

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

.

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

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

                        (4.14)

      Решение.

      Приведем  систему (4.14) к виду, удобному для  релаксации

                      (4.15)

      В качестве начального приближения выбираем

                         .

      Находим соответствующие невязки: , , . Выбираем максимальную невязку и полагаем , тогда

Опять выбираем максимальную невязку и  полагаем , тогда

      Далее и

       ,

       ,

       ,

       ,

       ,

      Окончательно  получим: