Мегаобучалка Главная | О нас | Обратная связь  


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




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

Условие сходимости итерационного процесса. Метод Якоби. Метод Зейделя

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

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

Ax = b

Для применения итерационных методов система должна быть приведена к эквивалентному виду

x=Bx+d.

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

Для сходимости итерационного процесса достаточно, чтобы было выполнено условие (норма матрицы). Критерий окончания итераций зависит от применяемого итерационного метода.

 

Метод Якоби.

Самый простой способ приведения системы к виду, удобному для итерации, состоит в следующем:

Из первого уравнения системы выразим неизвестное x1, из второго уравнения системы выразим x2, и т. д.

В результате получим систему уравнений с матрицей B, в которой на главной диагонали стоят нулевые элементы, а остальные элементы вычисляются по формулам:

Компоненты вектора d вычисляются по формулам:

Расчетная формула метода простой итерации имеет вид:

 

или в покоординатной форме записи выглядит так:

Критерий окончания итераций в методе Якоби имеет вид:

Если , то можно применять более простой критерий окончания итераций

Пример 1.Решение системы линейных уравнений методом Якоби.

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

Требуется найти решение системы с точностью

 

Приведем систему к виду удобному для итерации:

Выберем начальное приближение, например,

- вектор правой части.

Тогда первая итерация получается так:

Аналогично получаются следующие приближения к решению.

 

Найдем норму матрицы B.

Будем использовать норму

 

Так как сумма модулей элементов в каждой строке равна 0.2, то , поэтому критерий окончания итераций в этой задаче

 

Вычислим нормы разностей векторов:

 

Так как заданная точность достигнута на четвертой итерации.

Ответ: x1 = 1.102, x2 = 0.991, x3 = 1.011

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

Метод можно рассматривать как модификацию метода Якоби. Основная идея состоит в том, что при вычислении очередного (n+1)-го приближения к неизвестному xi при
i >1 используют уже найденные (n+1)-е приближения к неизвестным x1, x2, ..., xi - 1, а не n-ое приближение, как в методе Якоби.

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

Условия сходимости и критерий окончания итераций можно взять такими же, как в методе Якоби.

Пример 2. Решение систем линейных уравнений методом Зейделя.

Рассмотрим параллельно решение 3-х систем уравнений:

 

Приведем системы к виду удобному для итераций:

 

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

 

1-ая система:

Точным решением будут значения: x1 = 1.4, x2 = 0.2. Итерационный процесс сходится.

 

2-ая система:

Видно, что итерационный процесс расходится.

Точное решение x 1 = 1, x 2 = 0.2.

 

3-я система:

Видно, что итерационный процесс зациклился.

Точное решение x 1 = 1, x 2 = 2.

 

Пусть матрица системы уравнений A – симметричная и положительно определенная. Тогда при любом выборе начального приближения метод Зейделя сходится. Дополнительных условий на малость нормы некоторой матрицы здесь не накладывается.

 

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

Если A – симметричная и положительно определенная матрица, то систему уравнений часто приводят к эквивалентному виду:

x = x -τ (Ax - b), τ – итерационный параметр.

Расчетная формула метода простой итерации в этом случае имеет вид:

x (n+1) = x n - τ (Ax (n) - b).

Здесь

B = E - τ A

и параметр τ > 0 выбирают так, чтобы по возможности сделать минимальной величину

Пусть λmin и λmax – минимальное и максимальное собственные значения матрицы A. Оптимальным является выбор параметра

В этом случае принимает минимальное значение равное:

Пример 3. Решение систем линейных уравнений методом простой итерации. (в MathCAD)

Пусть дана система уравнений Ax = b

 

1. Для построения итерационного процесса найдем собственные числа матрицы A:

- используется встроенная функция для нахождения собственных чисел.

2. Вычислим итерационный параметр и проверим условие сходимости

 

- условие сходимости выполнено.

3. Возьмем начальное приближение - вектор x0, зададим точность 0.001 и найдем начальные приближения по приведенной ниже программе:

 

 

Точное решение

Замечание. Если в программе возвращать матрицу rez, то можно просмотреть все найденные итерации.




Читайте также:



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (917)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.003 сек.)