Итерационные методы решения линейных алгебраических систем

Метод простой итерации или метод Якоби

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

,

где , , .

Предположим, что диагональные элементы матриц A исходной системы не равны 0 (a_ii ≠ 0, i = 1, 2, …, n). Разрешим первое уравнение системы относительно x₁, второе относительно x₂ и т.д. Получим следующую эквивалентную систему, записанную в скалярном виде:

(1),

Теперь, задав нулевое приближение , по рекуррентным соотношениям (1) можем выполнять итерационный процесс, а именно:

(2)

Аналогично находятся следующие приближения , где в (2) вместо необходимо подставить .

Или в общем случае:

. (3)

или

Условие окончания итерационного процесса .

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

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

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

Пример.

Решить систему линейных уравнений с точностью :

							x1
=				=		=	x2
		–2					x3

Решение прямыми методами, например, обратной матрицей, даёт решение:

.

Найдем решение методом простой итерации. Проверяем условие диагонального преобладания: , , .

Приводим систему уравнений к виду (1):

.

Начальное приближение . Дальнейшие вычисления оформим в виде таблицы:

Здесь

,

И т.д., пока не получим, в последнем столбце величину меньшую 0.01, что произойдет на 13 – ой итерации.

Следовательно, приближенное решение имеет вид:

Метод Гаусса – Зейделя

Расчетные формулы имеют вид:

т.е. для подсчета i –й компоненты (k +1)–го приближения к искомому вектору используется уже вычисленное на этом, т.е. (k +1)–м шаге, новые значения первых i –1 компонент.

Подробные формулы имеют вид:

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

Начальное приближение:

Найдем решение предыдущей системы уравнений методом Гаусса – Зейделя.

Расчетные формулы:

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