Метод прогонки решения систем с трехдиагональной матрицей –разложение трехдиагональной матрицы :

где (проверить)

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

Формулы метода прогонки для системы :

сначала вычисляем (рекуррентно):

и решаем систему с матрицей (прямой ход):

и, наконец, решаем систему (обратный ход):

.

Теорема.	Если , то (т.е. –разложение существует и метод прогонки применим).
Док–во.	(от противного) Пусть , тогда и . Разделим равенство на и оценим : – противоречие условию.

Лекция 5. Итерационные методы решения линейных уравнений

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

с вещественными коэффициентами.

Пример и основные определения

Пример:

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

.

Одношаговый (двухслойный) итерационный метод решения :

– -тое приближение (к решению системы),

– ошибка -той итерации	– процесс для ошибки, – матрица шага для ошибки;
– невязка -той итерации	– процесс для невязки, – матрица шага для невязки;

Метод называется сходящимся, если .

(Так как в все нормы эквивалентны, то определение сходимости от нормы не зависит.)

Стационарный одношаговый итерационный метод решения :

Впредь мы будем предполагать, что и .

Условия сходимости стационарного итерационного метода

Достаточные условия:

Теорема.	Если , то , т.е. .
Док–во.

Теорема.	Если , то , т.е. .
Док–во.	.

Необходимое и достаточное условие:

Теорема.	.
Док–во.	Необходимость. Пусть , т.е. метод сходится. Так как , то, выбрав , получим, что .
	Достаточность. Если докажем, что (нулевой матрице), то , т.е. метод сходится. Итак, пусть – жорданова форма матрицы , т.е. , , , . Практически очевидно, что . Пусть – порядка блока и , тогда (бином Ньютона) , т.к. . Т.к. , , что и тр.док.