Пример ручного счета в обычной формулировке.

Лекция-3

ОСНОВЫ ЧИСЛЕННЫХ МЕТОДОВ

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

Алгебраических уравнений

Понятие об итерационных методах решения СЛАУ.

В отличие от прямых методов, итерационные методы обычно не дают точного ответа за конечное число шагов, однако на каждом шаге уменьшают ошибку на какую-то долю. Итерации прекращают, когда ошибка становится меньше допуска, заданного вычислителем (пользователем). Величина финальной ошибки зависит от количества итераций, а также от свойств метода и СЛАУ. Другими словам, итерационные методы дают решение СЛАУ в виде предела последовательности некоторых векторов, построение которых осуществляется посредством единообразного процесса, называемого итерационным процессом.

Рассмотрим два простейших итерационных метода решения СЛАУ – метод простой итерации и метод Зейделя.

Пусть требуется решить СЛАУ

(2.3.1)

Итерационные методы решения системы уравнений (2.3.1) состоят в построении последовательности векторов

(2.3.2)

по некоторому алгоритму, такому, что из следует . При этом

(2.3.3)

где – точное решение системы, а – называется начальным приближением решения.

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

, (2.3.4)

где e – малое положительное число (заданная точность). С точностью до e решение принимается равным .

Метод Зейделя и метод простой итерации.

Пусть задана система уравнений:

. (2.3.5)

Выразим через остальные члены i-го уравнения:

. (2.3.6)

Полученная запись СЛАУ приводит к двум итерационным процессам.

Метод простой итерации.

, . (2.3.7)

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

, (2.3.8)

При этом задается ( ), – номер итерации.

Процесс ведется до выполнения условия .

Норму вектора можно, в частности, вычислять по формулам:

– норма по модулю;
– «евклидова» норма;
– максимум модуля для элементов вектора.

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

При решении итерационными методами встает вопрос сходимости получаемых приближений к решению задачи.

Достаточный условие сходимости обоих методов состоит в выполнении условия диагонального преобладания:

, , (2.3.9)

где, по крайней мере, одно неравенство является строгим ( ).

Матричная формулировка метода простой итерации и метода Зейделя.

Представим матрицу в виде

, (2.3.10)

где

– нижняя треугольная матрица:

; (2.3.11)

– верхняя треугольная матрица:

; (2.3.12)

– диагональная матрица:

; (2.3.13)

– сумма верхней и нижней треугольных матриц:

. (2.3.14)

Тогда простая итерация имеет вид

(2.3.15)

Тогда (2.3.16)

Аналогично можно представить метод Зейделя в виде

(2.3.17)

Умножим правую и левую часть равенства на матрицу и перенесем в левую часть равенства, т.е.

или ,

где – нижняя треугольная матрица с главной диагональю:

; (2.3.18)

из этого следует

, (2.3.19)

Тогда (2.3.20)

Пример ручного счета в обычной формулировке.

Дана система уравнений

Выполним проверку выполнения достаточного условия сходимости.

Проверяем условие диагонального преобладания.

первое уравнение: 4>1+1=2 – выполняется;

второе уравнение: 2<1+5=6 – не выполняется;

третье уравнение: |–1|<1+6=7 – не выполняется.

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

Проверяем условие диагонального преобладания для преобразованной системы:

первое уравнение: 4>1+1=2 – выполняется;

второе уравнение: 6>1+|–1|=2 – выполняется;

третье уравнение: 5>1+2=3 – выполняется.

Для определения точности приближения воспользуемся нормой вектора

– максимум модуля для элементов вектора.

Решение СЛАУ методом простой итерации.

Схема пересчета в данном случае имеет вид:

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

Первый шаг итерации ( ):

Второй шаг итерации ( ):

Третий шаг итерации ( ):

После трех итерационных шагов получаем приближенное решение СЛАУ: .

Решение СЛАУ методом Зейделя.