Решение слау методом Зейделя

Вид материала

Решение

Подобный материал:

• Неравенств и, если «да», то найдите общее решение и частное решение двумя способами:, 11.47kb.
• Алгоритм решения системы n линейных уравнений методом Гаусса- зейделя представлен, 111.8kb.
• Программа обсуждена на заседании кафедры Математики фнти, 45.62kb.
• Решение алгебраических уравнений высоких степеней. Решение нелинейных уравнений методом, 9.13kb.
• Лабораторная работа 1 Методы решения задач линейной алгебры, 32.21kb.
• Курсовая работа «Дифференциальные уравнения» Задача №1 (3 задачи), 8.81kb.
• 1. Решение нелинейного уравнения методом Ньютона-Рафсона, 156.67kb.
• решение разреженных симметричных слау на суперкомпьютерах, 257.67kb.
• Решение слау с разреженными матрицами, 32.92kb.
• Курсовая работа 03 112 -116 «Дифференциальные уравнения» Задача №1 Получить точное, 12.24kb.

Решение СЛАУ методом Зейделя


Филипп Людвиг Зе́йдель (24.10.1821 — 13.08.1896, Мюнхен) — немецкий математик и астроном.


Метод Зейделя для решения системы,

Ax = b,

(1)

где – вещественная п×п-матрица, – п-мерные векторы (столбцы), представляет собой некоторую модификацию метода простой итерации. Основная его идея заключается в том, что при вычислении (k+1)-го приближения неизвестной учитываются уже вычисленные ранее (k+1)-ые приближения неизвестных .

Пусть система приведена к эквивалентному виду

x = Bx + c,

(2)

где – вещественная п×п-матрица, x, c – п-мерные векторы. Обозначим – k ое приближение к решению системы. Очередное ((k+1) ое) приближение к решению системы определяется по формуле

(3)

Иначе можно сказать, что очередное ((k+1) ое) приближение к решению системы определяется из системы соотношений:



Эту систему можно представить в виде , где

.

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

Сформулируем более удобные для применения достаточные условия сходимости метода Зейделя.

Теорема. Обозначим

, .

(4)

Пусть 0<1. Тогда система (2) имеет единственное решение, которое может быть найдено как предел последовательности, построенной по формулам (3), начиная с произвольного начального приближения . При этом для любого k = 0, 1,… имеют место оценки

,	(5)
.	(6)

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

Пусть – последовательность, построенная по формулам (3), начиная с некоторого . Оценим . Так как х^* – решение системы (2), то

.

(7)

Уменьшим в равенстве (3) номер k на 1 и вычтем из полученного равенства равенство (7):

.

Отсюда

.

Используя обозначения (4), из последнего неравенства получаем, что

.

Беря максимум в левой части, получим

.

(8)

где l таково, что . Заметим, что из условия 0<1 следует, что для всех l выполняется _l <1. С учетом этого из (8) получаем . Отсюда по индукции можно доказать, что . Поскольку 0<1, то , то есть .

Докажем оценки (5) и (6). Оценим . Уменьшим в равенстве (3) номер k на 1 и вычтем полученное равенство из (3):

.

Отсюда

.

Используя обозначения (4), из последнего неравенства получаем, что

.

Беря максимум в левой части, получим

,

(9)

где l таково, что . Заметим, что из условия 0<1 следует, что для всех l выполняется _l <1. С учетом этого из (9) получаем . Отсюда по индукции можно доказать, что

,

(8)

где pk – произвольное натуральное число. Рассмотрим теперь :





.

Переходя к пределу при m, получим оценку (5). Из неё по индукции получаем (6).


Теорема доказана полностью.


Замечание. Если исходная матрица A имеет преобладающую главную диагональ, то <1, где .

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

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

.

Из условия преобладания главной диагонали следует, что <1. Следовательно, , то есть , и .

Далее при любом имеем

,

то есть при любом

.

Тем более тогда при любом . Отсюда, беря максимум в правой части неравенства .