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

Тема  3.  Решение  систем  линейных  алгебраических  уравнений  итерационными  методами.

Описанные  выше  прямые  методы  решения  СЛАУ  не  очень  эффективны  при  решении  систем  большой  размерности  (т.е.  когдо  значение  n  достаточно  велико).  Для  решения  СЛАУ  в  таких  случаях  больше  подходят  итерационные  методы

Итерационные  методы  решения  СЛАУ  (их  второе  название  -  методы  последовательного  приближения  к  решению)  не  дают  точного  решения  СЛАУ,  а  дают  только  приближение  к  решению,  причем  каждое  следующее  приближение  получается  из  предыдущего  и  является  более  точным,  чем  предыдущее   (при  условии,  что  обеспечена  сходимость  итераций).  Начальное  (или,  так  называемое,  нулевое)  приближение  выбирается  вблизи  предполагаемого  решения  или  произвольно  (в  качестве  его  можно  взять  вектор  правой  части  системы).  Точное  решение  находится  как  предел  таких  приближений  при  стремлении  их  количества  к  бесконечности.  Как  правило,  за  конечное  число  шагов  (т.е.  итераций)  этот  предел  не  достигается.  Поэтому,  на  практике,  вводится  понятие  точности  решения,  а  именно  задается  некоторое  положительное  и  достаточно  малое  число  e  и  процесс  вычислений  (итераций)  проводят  до  тех  пор,  пока  не  будет  выполнено  соотношение    .

Здесь   -  приближение  к  решению,  полученное  после  итерации  номер  n,   а  -  точное  решение  СЛАУ  (которое  заранее  неизвестно).  Число  итераций  n=n(e),   необходимое  для  достижения  заданной  точности  для  конкретных  методов  можно  получить  из  теоретических  рассмотрений  (т. е.  для  этого  имеются  расчетные  формулы).  Качество  различных  итерационных  методов  можно  сравнить  по  необходимому  числу  итераций  для  достижения  одной  и  той  же  точности.

            Для  исследования  итерационных  методов  на  сходимость  необходимо  уметь  вычислять  нормы  матриц.   Норма  матрицы  -  это  некая  числовая  величина,  характеризующая  величину  элементов  матрицы  по  абсолютной  величине.   В  высшей  математике  имеется  несколько  различных  видов  норм  матриц,  которые,  как  правило,  являются  эквивалентными.  В  нашем  курсе  мы  будем  пользоваться  только  одной  из  них.  А  именно,  под  нормой  матрицы  мы  будем  понимать  максимальную  величину  среди  сумм  абсолютных  величин  элементов  отдельных  строк  матрицы.  Для  обозначения  нормы  матрицы  -  ее  название  заключается  в  две  пары  вертикальных  черточек.  Так,  для  матрицы  A  под  ее  нормой  будем  понимать  величину

                                          .                                                      (3.1)

Так,  к  примеру,  норма  матрицы  А  из  примера  1  находится  следующим  образом :

            .

Рекомендуемые материалы

Наиболее  широкое  применение  для  решения  СЛАУ  получили  три  итерационных  метода

- метод  простой  итерации

- метод  Якоби

- метод  Гуасса-Зейделя.

Метод  простой  итерации  предполагает  переход  от  записи  СЛАУ  в  исходном  виде  (2.1)  к  записи  ее  в  виде 

                                        (3.2)

или,  что  тоже,  в  матричном  виде, 

                                               x = С×x + D,                                                                                    (3.3)

где  :

   C  -  матрица  коэффициентов  преобразованной  системы  размерности  n´n

    x  -  вектор  неизвестных,  состоящий  из  n  компонент

   D  -   вектор  правых  частей  преобразованной  системы,  состоящий  из  n  компонент.

Система  в  виде  (3.2)  может  быть  представлена  в  сокращенном  виде

Исходя  из  этого  представления  формула  простой  итерации  будет  иметь  вид

                                                          (3.4)

где  m  -  номер  итерации,   а      -  значение  x_j  на  m-ом  шаге  итерации.  Тогда,  если  процесс  итераций  сходится,  с  увеличением  количества  итераций  будет  наблюдаться 

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

            Если  за  начальное  (нулевое)  приближение  взять  вектор  свободных  членов,  т.е.  x⁽⁰⁾  = D,  то  величина  погрешности  имеет  вид

                                                                                   (3.5)

здесь под  x^*  понимается  точное  решение  системы.   Следовательно, 

если   ,  то  по  заданной  точности  e  можно  заранее  расчитать  необходимое  количество  итераций.  А  именно,  из  соотношения 

после  небольших  преобразований  получим

                                      .                                                              (3.6)

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

            Поиск  решений  заданной  СЛАУ  методом  простой  итерации  удобно  производить  с  занесением  полученных  результатов  в  таблицу  следующего  вида :

Следует  особо  отметить,  что  в  решении  СЛАУ  этим  методом  наиболее  сложным  и  трудоемким  является  выполнение  преобразования  системы  из  вида  (2.1)  к  виду  (3.2).  Эти  преобразования  должны  быть  эквивалентными,  т.е.  не  меняющими  решения  исходной  системы,  и  обеспечивающие  величину  нормы  матрицы  C  (после  выполнения  их) меньшей  единицы.   Единого  рецепта  для  выполнения  таких  преобразований  не  существует.  Здесь  в  каждом  конкретном  случае  необходимо  проявлять  творчество.  Рассмотрим  примеры,  в  которых  будут  приведены  некоторые  способы  преобразования  системы  к  необходимому  виду.

Пример 1.  Найдем  решение  системы  линейных  алгебраических  уравнений  методом  простой  итерации  (с  точностью  e=0.001)

Эта  система  приводится  к  необходимому  виду  простейшим  способом.  Перенесем  все  слагаемые  из  левой  части  в  правую,   а  затем  к  обоим  частям  каждого  уравнения  прибавим  по  x_i  (i=1, 2, 3, 4).  Получим  преобразованную  систему  следующего  вида

                  .

            Матрица  C  и  вектор  D  в  этом  случае  будут  следующими

                  C =  ,        D =  .

Вычислим  норму  матрицы C.  Получим

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

                     ,   ,   ,   .

По  формуле  (3.6)  вычислим  необходимое  число  шагов  итерации.   Определим  сначала  норму  вектора  D.  Получим

Тогда

                             .

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

или

    Выполнив  все  арифметические  операции,  получим 

                                                   .

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

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

Пример 2.   Преобразуем  систему  уравнений

к  виду,  который  позволил  бы  использовать  при  ее  решении  метод  простой  итерации.

            Поступим  сначала  аналогично  предыдущему  примеру.  Получим

Матрица  C  такой  системы  будет

                                                    C =.

Вычислим  ее  норму.  Получим

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

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

Матрица  C  такой  системы  будет

                                                   C =.

Вычислим  ее  норму.   Получим

Так  как   норма  матрицы C  оказалась  меньшей  единицы,  преобразованная  таким  образом  система  пригодна  для  решения  методом  простой  итерации.

Пример 3.   Преобразуем  систему  уравнений

к  виду,  который  позволил  бы  использовать  при  ее  решении  метод  простой  итерации.

            Поступим  сначала  аналогично  примеру  1.  Получим

Матрица  C  такой  системы  будет

                                       C =.

Вычислим  ее  норму.   Получим

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

            Для  преобразования  исходной  матрицы  к  виду,  удобному  для  применения  метода  простой  итерации  поступим  следующим  образом.  Сначала  образуем  “промежуточную”  систему  уравнений,  в  которой 

- первое  уравнение  является  суммой  первого  и  второго  уравнений  исходной  системы

- второе  уравнение  -  суммой  удвоенного  третьего  уравнения  со  вторым  за  вычетом  первого

- третье  уравнение  -  разность  третьего  и  второго  уравнений  исходной  системы.

В  результате  получим  эквивалентную  исходной  “промежуточную”  систему  уравнений

Из  нее  несложно  получить  еще  одну  систему  “промежуточную”  систему

      ,

а  из  нее  преобразованную

         .

Матрица  C  такой  системы  будет

                                              C =.

Вычислим  ее  норму.   Получим

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

Метод  Якоби  предполагает,  что  все  диагональные  элементы  матрицы    A  исходной  системы  (2.2)  не  равны  нулю.  Тогда  исходную  систему  можно  переписать  в  виде

                                                                    (3.7)

Из  такой  записи  системы  образована  итерационная  формула  метода  Якоби

                       .                   (3.8)

Условием  сходимости  итерационного  процесса  метода  Якоби  является  так  называемое  условие  доминирования  диагонали  в  исходной  системе  (вида  (2,1)).  Аналитически  это  условие  записывается  в  виде

               .                                                       (3.9)

Следует  отметить,  что   если  в  заданной  системе  уравнений  условие  сходимости  метода  Якоби  (т.е.  условие  доминирования  диагонали)  не  выполняется,  во  многих  случаях  можно  путем  эквивалентных  преобразований  исходной  СЛАУ  привести  ее  решение  к  решению  эквивалентной  СЛАУ,  в  которой  это  условие  выполняется. 

Пример 4.   Преобразуем  систему  уравнений

к  виду,  который  позволил  бы  использовать  при  ее  решении  метод  Якоби. 

            Эту  систему  мы  уже  рассматривали  в  примере  3,  поэтому  перейдем  от  нее  к  полученной  там  “промежуточной”  системе  уравнений.  Легко  установить,  что  у  нее  условие  доминирования  диагонали  выполняется,  поэтому  преобразуем  ее  к  виду,  необходимому  для  применения  метода  Якоби.  Получим

Из  нее  получаем  формулу  для  выполнения  вычислений  по  методу  Якоби  для  заданной  СЛАУ

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

Довольно  высокая  точность  полученного  решения  достигнута  за  шесть  итераций.

Метод  Гаусса-Зейделя  является  усовершенствованием  метода  Якоби  и  также  предполагает,  что  все  диагональные  элементы  матрицы    A  исходной  системы  (2.2)  не  равны  нулю.  Тогда  исходную  систему  можно  переписать  в  виде  аналогичном  методу  Якоби,  но  несколько  отличном  от  него

                               .    

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

Идея  метода  Гаусса-Зейделя  заключается  в  том,  что  авторы  метода  усмотрели  возможность  ускорить  процесс  вычислений  по  отношению  к  методу  Якоби  за  счет  того,  что  в  процессе  очередной  итерации  найдя  новое  значение  x₁  можно  сразу  же  использовать  это  новое  значение  в  этой  же  итерации  для  вычисления  остальных  переменных.  Аналогично  этому,  дальше,  найдя  новое  значение  x₂  можно его  также  сразу  использовать  в  этой  же  итерации  и  т.д.

            Исходя  из  этого,  формула  итераций  для  метода  Гаусса-Зейделя  имеет  следующий  вид

               .         (3.10)

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

Пример 5.   Решим  методом  Гаусса-Зейделя  систему  уравнений

            Эту  систему  мы  уже  рассматривали  в  примерах  3  и  4,  поэтому  сразу  перейдем  от  нее  к  преобразованой  системе  уравнений  (см.  пример  4),  в  которой  условие  доминирования  диагонали  выполняется.  Из  нее  получаем  формулу  для  выполнения  вычислений  по  методу  Гаусса-Зейделя 

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

Довольно  высокая  точность  полученного  решения  достигнута  за  пять  итераций.