Описание используемого метода

2. Описание используемого метода

 

Для решения методом Зейделя система линейных алгебраических уравнений Ax = b должна быть приведена к виду x = Gx+f , где G - некоторая матрица, f - преобразованный вектор свободных членов. Затем выбирается начальное приближение - произвольный вектор x⁽⁰⁾ - и строится рекуррентная последовательность векторов x⁽¹⁾, x⁽²⁾,..., x^(k),... по формуле

.

Для сходимости этой последовательности при любом начальном приближении необходимо и достаточно, чтобы все собственные значения матрицы G были по абсолютной величине меньше единицы. На практике это трудно проверить, и обычно пользуются достаточными условиями сходимости - итерации сходятся, если какая-нибудь норма матрицы меньше единицы, т.е.

 или .

Чем меньше норма матрицы G, тем быстрее сходится итерационный процесс.

Преобразование системы можно осуществить, просто решая каждое i-е уравнение относительно x_i :

.

 

Метод Зейделя использует следующий алгоритм построения приближений:

Если A - матрица с доминирующей диагональю, т.е. , то метод Зейделя сходится при любом начальном приближении x⁽⁰⁾.

Метод Зейделя сходится примерно так же, как геометрическая прогрессия со знаменателем ||G|| . Если норма матрицы G близка к 1, то скорость сходимости очень медленная. Для ускорения сходимости используется метод релаксации. Суть его в том, что полученное по методу Зейделя очередное значение пересчитывается по формуле:

Здесь 0<w£2 – параметр релаксации. Если w<1 - нижняя релаксация, если w>1 – верхняя релаксация. Параметр w подбирают так, чтобы сходимость метода достигалась за минимальное число итераций.

Метод Зейделя является одношаговым итерационным методам, когда для нахождения x^(k+1) требуется помнить только одну предыдущую итерацию x^(k).

Погрешность итерации вычисляется по формуле:

n - порядок матрицы A.

Если d меньше заданной точности e, то итерационный процесс прекращают.

Элементы главной диагонали называются главными. Заметим, что если в ходе расчётов по данному алгоритму на главной диагонали окажется нулевой элемент, то произойдет сбой программы. Для того, чтобы избежать этого, следует перестановку строк таким образом, чтобы на главной диагонали находились максимальные элементы строк. Т. е., если в k-й строке максимальным является i-й элемент, необходимо поменять местами k-ю и i-ю строки, и поменять местами соответствующие элементы вектора b. Такой выбор главного элемента необходим для сходимости итерационного процесса.

Приведём блок-схему реализации данного метода: