3. Достаточные условия сходимости итерационного процесса.

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

Теорема Самарского

Пусть - самосопряженная положительно определенная матрица:

, ,

- положительно определенная матрица, - положительное число:

, .

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

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

,,.

т. е. оно, в частности, предполагает, что матрица является положительно определенной. Кроме того, неравенство определяет интервал, в котором может изменяться параметр:

.

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

и подставим в рекуррентную формулу для итерационной последовательности . В результате получим:

.

Отличие итерационной формулы от заключается в том, что она является однородной.

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

,

где

, так что.

Умножая обе части равенства слева на матрицу , получим еще одно рекуррентное соотношение

.

Рассмотрим последовательность положительных функционалов:

.

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

Из самосопряженности матрицы и формулы следует

В результате формула принимает вид:

Таким образом, последовательность функционалов с учетом условия образует монотонно невозрастающую последовательность, ограниченную снизу нулем

.

Поэтому она сходится. Далее, согласно лемме 3

,

где - строго положительная константа. В результате, согласно и будем иметь

Из этого неравенства и сходимости последовательности функционалов следует, чтопри. В свою очередь, так что

Теорема доказана.

4. Метод простой итерации.

Такое название получил метод, при котором в качестве матрицы выбирается единичная матрица:, а итерационный параметрпредполагается независящим от номера итерации. Иными словами, метод простой итерации – это явный стационарный метод, когда очередная итерациявычисляется по рекуррентной формуле

Будем считать, что матрица удовлетворяет условию теоремы Самарского,, тогда формула , определяющая границу интервала сходимости по итерационному параметру, принимает вид

.

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

Разложим вектор по базису собственных векторов

,

тогда

,

и

.

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

.

Дальнейшее исследование метода простой итерации построим на конкретном анализе рекуррентной формулы . Введем матрицу оператора перехода

,

и перепишем формулу в виде

.

При этом погрешность будет удовлетворять аналогичному рекуррентному соотношению, только однородному

.

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

Лемма 1

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

.

Доказательство элементарно. Оно проводится прямой проверкой

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

.

Лемма 2

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

,

Достаточность. Условие означает, что норма матрицы, согласно , будет меньше единицы:. В результате получаем

, при.

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

.

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

,.

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

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

, при.

Найденное значение является границей интервала сходимости метода простой итерации

.

Это неравенство нам уже известно. Оно было получено ранее из теоремы Самарского как достаточное условие сходимости. Дополнительный анализ на основе леммы 2 позволяет уточнить результат. Теперь мы установили, что принадлежность итерационного параметра интервалу является необходимым и достаточным условием сходимости метода простой итерации.

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

.

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

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

,

которое дает

.

В результате получаем:

Свое наименьшее значение норма матрицы достигает при:

.

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

В заключение заметим, что формула , определяющая границу интервала сходимости , и формула для оптимального значения итерационного параметрапредставляют прежде всего теоретический интерес. Обычно при решении СЛАУ наибольшее и наименьшее характеристические числа матрицынеизвестны, так что подсчитать величиныизаранее невозможно. В результате итерационный параметрнередко приходится подбирать прямо в процессе вычислений методом проб и ошибок.

Задача 2.

Рассмотреть систему двух уравнений с двумя неизвестными

и построить для нее приближенное решение с помощью метода простой итерации.

Выпишем сразу решение системы

, ,

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

Перейдем к решению системы методом простой итерации. Матрица системы имеет вид

.

Она самосопряженная и положительно определенная, поскольку

.

Составим характеристическое уравнение для матрицы и найдем его корни:

,

,

С их помощью можно определить границу интервала сходимости и оптимальное значение итерационного параметра:

,.

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

, где

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

, , ,

, , ,

, , ,

, , .

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

.