Файл: Маркова Вычислит методы алгебры Практикум.doc

П 3.8 Метод Зейделя решения систем линейных алгебраических уравнений

Рассмотрим метод Зейделя [20]. Этот метод является модификацией метода простых итераций и приводит к более быстрой сходимости, т.е. для получения решения с заданной точностью требуется выполнить меньшее количество итераций, а следовательно потребуется меньше затрат машинного времени.

Имеем систему линейных алгебраических уравнений

. (1)

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

.(2)

В методе Зейделя последовательность итерационных приближений строится по правилу

(3)

или в развернутом виде

(4)

Суть метода состоит в следующем: для вычисления первой компоненты вектора необходимо знать компоненты вектора . При нахождении второй компоненты вектора используются только что найденное значение и известные значения компонент вектора и т.д. Таким образом, при вычислении компоненты вектора неизвестных на (k+1)-й итерации используются , уже вычисленные на (k+1)-й итерации. Значения остальных компонент берутся из предыдущей итерации.

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

,(5)

где P=G-D, Q=B-P.

Метод Зейделя (5) можно трактовать как разновидность общего итерационного процесса:

(6)

где .

Критерием сходимости метода Зейделя служит следующее утверждение [20]:

Для того чтобы метод Зейделя сходился при любом , необходимо и достаточно, чтобы , где  все собственные значения матрицы F.

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

1. Метод Зейделя сходится, если выполняется неравенство , где  первая или вторая норма матрицы.

2. Для сходимости метода Зейделя достаточно чтобы , но хотя бы при одном i выполнялось условие .

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

, (7)

где  заданная точность.

Если для одной и той же системы метод простой итерации и метод Зейделя сходятся, то последний предпочтительнее.

Области сходимости этих двух методов различны, т.е. существуют системы, для которых метод простой итерации сходится, а метод Зейделя – нет, и наоборот.

Пример 1. Методом Зейделя решить систему линейных уравнений с точностью .

Решение:

Приведение СЛАУ к эквивалентному виду аналогично приведению в методе простых итераций

Заметим, что , следовательно, условие сходимости метода (2) выполнено.

Зададим вектор начального приближения .

Выполним расчеты по формуле (4)

На первой итерации имеем систему

.

Условие окончания итерационного процесса не выполняется, значит продолжаем процесс. На второй итерации получаем

.

Условие окончания итерационного процесса не выполняется. Продолжаем итерировать.

На третьей итерации требуемая точность достигнута .

Лабораторная работа № 11

Цель: изучить метод Зейделя решения систем линейных алгебраических уравнений.

Задание

1. В классе «Итерационные методы решения СЛАУ» («IterationMethods») реализуйте метод Зейделя («zeidelMethod»). Для реализации методов используйте объекты и методы матричных классов «SquareMatrix», «Vector».

2. Решите систему линейных алгебраических уравнений методом Зейделя () в соответствии с вариантом.

3. Решите те же задачи, используя пакет для математических вычислений.

4. Сравните результат выполнения п. 2 с решением, полученным в п. 3.

Варианты заданий

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

Имеем систему линейных алгебраических уравнений

AX = f . (1)

Канонической формой итерационного метода решения системы (1) называется его запись в виде [19]

(2)

где – вещественная невырожденная матрица порядка , задающая тот или иной итерационный метод,  итерационный параметр.

Если B_к+1=E, где Е – единичная матрица, то итерационный метод (2) называется явным, в противном случае неявным.

Если и не зависят от номера итераций, то итерационный метод (2) называется стационарным, и нестационарным  в противном случае.

Рассмотрим метод скорейшего спуска.

Пусть имеем систему (1) с симметричной положительно определенной матрицей А.

Обозначим через

(3)

невязку, которая получается при подстановке приближенного значения X^(k), полученного на k-й итерации, в уравнение (1).

Рассмотрим явный нестационарный итерационный метод [20]

.(4)

Перепишем метод (4) с учетом равенства (3), имеем

. (5)

Выберем итерационный параметр из условия минимума при заданном векторе , где , точное решение. Поскольку погрешность удовлетворяет уравнению , получим [19]