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

Сходимость последовательности векторов 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)(обратная матрица.

Лемма 2Если норма ||B||< = q<1, то матрица (Е-B) имеет обратную, такую что Е+B+ +……+ +…..=(Е-В)^(-1), причем || (Е-В)^(-1)||< =1/1-qV= Е+B+ +……+ +….

||V||=||…||< =||E||+||B||+|| ||+||+…+||+|| ||+…<||E||+||B||+|| ||+||+…+||+|| ||<1+q+q^2+…q^n+…+1/1-q

||V||<=1/1-q

Теорема 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 была меньше единицы.

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

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

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

Теорема о погрешностях. Пусть q 1, тогда справедливы оценки (1) - апостериорная («после»). (2) – априорная («до»). Док-во: = B +f

= B +f вычитаем нижнее из верхнего - = B - B = B( - ); = * q* ; q* (**); так как q<1, то разности приближений и 0. = +…+ + (заменим каждую норму разности, используя (**)) q* + * +…+ * = q*(1+q+…+ )* = q* . Устремим m к , фиксируя «k». Тогда , 0, в результате чего получится соотношение (1). По соотношению (**) q* ; .