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

 

 

Как уже было сказано, в итерационных методах определяется не само решение задачи Ax=b, а некоторая последовательность векторов x^(k) (k - номер итерации), такая, что она стремится к ветору решения при k®¥. Чтобы построить такую последовательность, надо прежде всего исходную систему Ax=b преобразовать к виду

x=Bx+f. (12)

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

т.е. преобразованные матрица B и вектор f имеют вид

, f= .

Задаваясь начальным приближением – вектором x⁽⁰⁾=(x₁⁽⁰⁾_, x₁⁽⁰⁾_,…., x₁⁽⁰⁾_,), получаем

(13)

Такая формула вычисления приближений определяет метод простой итерации – МПИ. Основной вопрос – будет ли последовательность векторов x^(k) сходится к решению системы линейных уравнений.

 

Сходимость последовательности векторов и матричной прогрессии.

 

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

 

Сходимость последовательности векторов x⁽⁰⁾_, x⁽¹⁾_,…., x^(k)_,…, определяют двумя способами: по компонентам и по норме.

Определение 1. Вектор x^*=(x₁^*_, x₂^*_,…., x_n^*_,) называется пределом этой последовательности векторов, если существует каждый из n числовых пределов

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

Определение 2. Последовательность векторов сходится к вектору x^* по норме, если .

Сходимость по норме более общая, так как не зависит от того, будет ли векторное пространство конечной или бесконечной размерности. Если размерность имеет конечное значение n, то сходимость по норме и сходимость по компонентам равносильны (т.е. из одной следует другая). Сходимость по норме во многих случаях более удобна, чем сходимость по компонентам.

Все эти рассуждения распространяются и на последовательность матриц B⁽⁰⁾, B⁽¹⁾, …, B^(k), …, однако здесь нас будет интересовать последовательность степеней матриц E, B, B², …, B^k, …, называемая матричной геометрической прогрессией.

Лемма 1(лемма Неймана). Условие, что все собственные числа матрицы B по модулю меньше единицы, является необходимым и достаточным для того, чтобы

1) B^k®¥ при k®¥;

2) матрица E-B имела обратную и E + B + B² + … +B^k + …= (E-B)^-1.

Лемма 2. Если норма ççBçç£q<1 то матрица E–B имеет обратную

(E–B)^-1 = E + B + B² + … +B^k + …, причем .

Доказательство: Обозначим матрицу, которая представляет сумму ряда степеней матрицы B за V:

.

Пронормируем это выражение и воспользуемся свойствами нормы:

Так как

(E-B)V=(E + B + B² + … + B^k + …) - (B + B² + … + B^k+1 + …) = E,

то V=(E-B)^-1, и следовательно

.

Лемма 2 доказана.

Теорема 1 (о сходимости МПИ). Необходимым и достаточным условием сходимости МПИ при любом начальном векторе x⁽⁰⁾ к решению x* СЛАУ x=Bx+f является требование, чтобы все собственные значения матрицы B по модулю были меньше единицы.

Докажем только достаточность.

Пусть собственные значения матрицы B по модулю были меньше единицы

max½l_i(B)½<1, i=1,2,…, n. По лемме 1 имеем B^k®¥ при k®¥, а также

E + B + B² + … + B^k + …= (E+B)^-1.

Применяя последовательно формулу МПИ для вычисления приближений:

x⁽¹⁾=Bx⁽⁰⁾+f,

x⁽²⁾=Bx⁽¹⁾+f=B(Bx⁽⁰⁾+f)+f=B²x⁽⁰⁾+(E+B)f,

..........

x^(k+1)=B^k+1x⁽⁰⁾ + (E + B + B² + … + B^k)f.

0 ()

Правая часть последнего выражения при любом x⁽⁰⁾ и равна (E-B)^-1f, т.е. в пределе .

Представим исходную систему x=Bx+f в виде (E-B)x=f и подставим x*:

(E-B)(E-B)^-1f=f.

Получается, что x* действительно является решением системы уравнений.

Достаточность доказана.

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

Для сходимости МПИ достаточно, чтобы какая-либо норма матрицы B была меньше единицы.

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

. (14)

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