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

К решению систем линейных уравнений сводятся многочисленные практические задачи. Можно с полным основанием утверждать, что решение линейных систем является одной из самых распространённых и важных задач вычислительной математики.

Запишем систему из n уравнений с n неизвестными:

(1)

Здесь и () – числовые коэффициенты, – неизвестные.

Методы решения систем линейных уравнений делятся на две группы – прямые и итерационные. Прямые методы используют конечные соотношения (формулы) для вычисления неизвестных. Они дают решение после выполнения заранее известного числа операций. Итерационные методы – это методы последовательных приближений. В них необходимо задать некоторое приближённое решение – начальное приближение. После этого с помощью некоторого алгоритма проводится один цикл вычислений, называемых итерацией. В результате итерации находят новое приближение. Итерации проводятся до получения решения с требуемой точностью. Одним из самых распространенных итерационных методов является метод Гаусса-Зейделя.

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

Достаточным условием сходимости метода Гаусса-Зейделя является

при i =1, 2,…, n.

Следующая последовательность шагов представляет метод Гаусса-Зейделя.

Шаг 1. Проверить выполнение условия ¹ 0, ¹ 0, …, ¹ 0. Если оно не выполняется, переставить уравнения так, чтобы оно выполнялось.

Шаг 2. Выразить j-ю переменную из j-го уравнения для каждого j=1,…,n. Получим

…………………………………………

(2)

………………………………………… .

Шаг 3. Выбрать произвольным образом начальное приближение .

Шаг 4. Подставить в правую часть системы (2), тогда в левой её части получится первое приближение ,

,

…………………………………………

…………………………………………

.

Шаг 5. Вычислить d=max| |, 1£j£n.

Шаг 6. Если меньше заданной точности, то - приближенное решение, в противном случае подставить в правую часть системы (2), тогда в левой части получим второе приближение . Снова вычислить d=max| | и поступать таким образом до тех пор, пока станет меньше заданной точности.

Переход от k-ого приближения к (k+1)-му осуществляется по формулам

,

………………………………….. (3)

,

а выход из цикла происходит при выполнения условия

,

где - заданная точность приближения.

Пример. Решить с точностью 0,001 систему

.

Решение. Диагональные элементы отличны от нуля, поэтому можно применить метод Гаусса-Зейделя. Приведем систему к виду (3):

.

Выберем начальное (нулевое) приближение и найдем :

.

Найдем второе приближение :

.

Найдем третье приближение :

.

Найдем четвертое приближение :

.

Первые три знака после запятой в и одинаковы, поэтому приближенным решением с заданной точностью является вектор

.