Проблема сходимости итерационных методов

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

x=Ax+b (*)

Теорема сходимости:

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

x_k=b+Ax_k-1 (k=1, 2, ...)

достаточное условие сходимости при произвольном начальном приближении x₀ есть:

||A||<1.

Доказательство:

Последовательность приближений

x₁=b+Ax₀

x₂=b+Ax₁

...............

x_k=b+Ax_k-1

после подстановки последовательно сверху вниз приводит к:

x_k=(E+A+A²+A³+...+A^k-1)b+(A^kx₀)

Так как ||A^k|| cтремится к 0 при k стремящемся к бесконечности и ||A||<1, то lim A^k=0 и lim (E+A+A²+A³+...+A^k-1)=
=(E-A)^-1 – по теореме сходимости матричного степенного ряда.

Отсюда получаем x=lim x^k=(E-A)^-1b или (E-A)x=b и x=Ax+b, т.е. предельный вектор х есть решение системы.

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

Примечание: норма матрицы – это вещественное число, вычисленное по ее элементам и характеризующее свойства матрицы. В качестве нормы матрицы могут использоваться:

Максимальная из сумм модулей элементов строк

||A||=max i=1, 2, …, n

Максимальная из сумм модулей элементов столбцов

||A||=max j=1, 2, …, n

Евклидова норма – квадратный корень из суммы квадратов всех элементов

||A||= .