Итерационные методы

Метод Зейделя

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

Пусть дана система

(1)

Предполагая, что диагональные члены – коэффициенты системы не равны нулю (i=1,…,n), разрешим первое уравнение системы относительно , второе – относительнои т.д. Тогда получим эквивалентную систему:

(2)

где

Система (2) решается методом последовательных приближений. За нулевое приближение можно принимать любое значение. Часто используют в этом качестве столбец свободных членов.

Следующее приближение вычисляют, подставляя значения в правую часть уравнений системы (2). В матричной форме первое приближение выразится так:

,

второе приближение вычисляется через первое:

и так далее

.

Если последовательность приближений имеет предел

,

то этот предел является решением системы (2), а, следовательно, и системы (1).

Распишем формулы приближений в развернутом виде:

(3)

Метод последовательных приближений, определяемый формулой (3), называется методом итераций. Итерационный процесс хорошо сходится, т.е. число приближений, необходимых для получения корней системы (1) с заданной точностью, невелико, если элементы матрицы малы по абсолютной величине. Т.е. для успешного применения процесса итерации модули диагональных элементов системы (1) должны быть велики по сравнению с модулями недиагональных коэффициентов этой системы. Величины свободных членов системы (1) на результат решения не влияют.

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

Рассмотрим систему линейных алгебраических уравнений с тремя неизвестными:

(1)

Выделим в правую часть из каждого уравнения диагональное неизвестное

(2)

За нулевое (начальное) приближение к решению выберем некоторые значения неизвестных и обозначим их . Подставим начальное приближение в систему (2)

(3)

В системе (3) для вычисления неизвестных ииспользовались только что вычисленные значения неизвестных на текущей итерации.

В общем случае на k-той итерации система выглядит так:

(4)

То есть, текущее значение неизвестных сразу же используется для последующих вычислений. Этот метод называется итерационным методом Гаусса - Зейделя.

Пример.

Пусть , тогда

и т.д.

Точное решение, к которому стремиться итерационный процесс () будет получено на 5-6-й итерации.

В случае системы n уравнений k- е приближение к решению будет иметь вид:

или

Итерационный процесс продолжается до тех пор, пока все не станут близки. Критерием близости может быть условие

Рассмотрим вопросы сходимости метода. Пусть дана система двух уравнений

,

тогда

(3)

(4)

Обозначим

Из (1) и (3) получим

Из последних уравнений следует:

Аналогично

Продолжая, можно получить:

Отсюда вытекает, что итерационный процесс метода Гаусса – Зейделя

сходится, если приближение на k- итерации будет существенно отличаться от первого приближения. Это возможно только при выполнении условия:

,

означающего, что диагональные члены превалируют над остальными.

Сравнение методов

Преимуществом метод исключения является то, что он конечен и теоретически с его помощью можно решить любую невырожденную систему линейных алгебраических уравнений. Итерационный метод Гаусса-Зейделя сходится только для специальных систем уравнений. Однако, если итерационный метод сходится, то он предпочтительнее:

1. Время вычислений на одну итерацию, в то время как для метода исключения время пропорционально, если решение получено менее, чем заn итераций, то для итерационного метода общие затраты будут меньше.

2. Ошибки округления для итерационного метода меньше.

3. большие системы уравнений невозможно точно решить с помощью прямых методов.