Метод простой итерации, называемый также методом последовательного приближения, - это математический алгоритм нахождения значения неизвестной величины путем постепенного ее уточнения. Суть этого метода в том, что, как видно из названия, постепенно выражая из начального приближения последующие, получают все более уточненные результаты. Этот метод используется для поиска значения переменной в заданной функции, а также при решении систем уравнений, как линейных, так и нелинейных.
Рассмотрим, как данный метод реализуется при решении СЛАУ. Метод простой итерации имеет следующий алгоритм:
1. Проверка выполнения условия сходимости в исходной матрице. Теорема о сходимости: если исходная матрица системы имеет диагональное преобладание (т.е, в каждой строке элементы главной диагонали должны быть больше по модулю, чем сумма элементов побочных диагоналей по модулю), то метод простых итераций - сходящийся.
2. Матрица исходной системы не всегда имеет диагональное преобладание. В таких случаях систему можно преобразовать. Уравнения, удовлетворяющие условию сходимости, оставляют нетронутыми, а с неудовлетворяющими составляют линейные комбинации, т.е. умножают, вычитают, складывают уравнения между собой до получения нужного результата.
Если в полученной системе на главной диагонали находятся неудобные коэффициенты, то к обеим частям такого уравнения прибавляют слагаемые вида с i *x i, знаки которых должны совпадать со знаками диагональных элементов.
3. Преобразование полученной системы к нормальному виду:
x - =β - +α*x -
Это можно сделать множеством способов, например, так: из первого уравнения выразить х 1 через другие неизвестные, из второго- х 2 , из третьего- х 3 и т.д. При этом используем формулы:
α ij = -(a ij / a ii)
i = b i /a ii
Следует снова убедиться, что полученная система нормального вида соответствует условию сходимости:
∑ (j=1) |α ij |≤ 1, при этом i= 1,2,...n
4. Начинаем применять, собственно, сам метод последовательных приближений.
x (0) - начальное приближение, выразим через него х (1) , далее через х (1) выразим х (2) . Общая формула а матричном виде выглядит так:
x (n) = β - +α*x (n-1)
Вычисляем, пока не достигнем требуемой точности:
max |x i (k)-x i (k+1) ≤ ε
Итак, давайте разберем на практике метод простой итерации. Пример:
Решить СЛАУ:
4,5x1-1.7x2+3.5x3=2
3.1x1+2.3x2-1.1x3=1
1.8x1+2.5x2+4.7x3=4 с точностью ε=10 -3
Посмотрим, преобладают ли по модулю диагональные элементы.
Мы видим что условию сходимости удовлетворяет лишь третье уравнение. Первое и второе преобразуем, к первому уравнению прибавим второе:
7,6x1+0.6x2+2.4x3=3
Из третьего вычтем первое:
2,7x1+4.2x2+1.2x3=2
Мы преобразовали исходную систему в равноценную:
7,6x1+0.6x2+2.4x3=3
-2,7x1+4.2x2+1.2x3=2
1.8x1+2.5x2+4.7x3=4
Теперь приведем систему к нормальному виду:
x1=0.3947-0.0789x2-0.3158x3
x2=0.4762+0.6429x1-0.2857x3
x3= 0.8511-0.383x1-0.5319x2
Проверяем сходимость итерационного процесса:
0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0.383+ 0.5319= 0.9149 ≤ 1 , т.е. условие выполняется.
0,3947
Начальное приближение х (0) = 0,4762
0,8511
Подставляем данные значения в уравнение нормального вида, получаем следующие значения:
0,08835
x (1) = 0,486793
0,446639
Подставляем новые значения, получаем:
0,215243
x (2) = 0,405396
0,558336
Продолжаем вычисления до того момента, пока не приблизимся к значениям, удовлетворяющим заданному условию.
x (7) = 0,441091
Проверим правильность полученных результатов:
4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3.1*0,1880+2.3*0,441-1.1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977
Результаты, полученные при подстановке найденных значений в исходные уравнения, полностью удовлетворяют условиям уравнения.
Как мы видим, метод простой итерации дает довольно точные результаты, однако для решения этого уравнения нам пришлось потратить много времени и проделать громоздкие вычисления.
1. Пусть известен отрезок , который содержит один корень уравнения f(x) = 0. Функция f является непрерывно дифференцируемой функцией на этом отрезке (f(x)ÎC 1 ). При выполнении этих условий можно применять метод простой итерации.
2. По функции f(x) строится функция j(x), удовлетворяющая трём условиям: она должна быть непрерывно дифференцируемой (j(x)ÎC 1 ), такая, что уравнение x = j(x) равносильно уравнению f(x)=0; должна также переводить отрезок в себя .
Будем говорить, что функция j(x) переводит отрезок [ a, b] в себя, если для любого x Î [ a, b], y = j(x) также принадлежит [ a, b] (y Î [ a, b]).
На функцию j(x) накладывается третье условие:
Формула метода: x n +1 = j(x n).
3. При выполнении этих трех условий для любого начального приближения x 0 Î последовательность итераций x n +1 = j(x n) сходится к корню уравнения: x = j(x) на отрезке ().
Как правило, в качестве x 0 выбирается один из концов .
,
где e – заданная точность
Число x n +1 при выполнении условия остановки итерационного процесса является приближенным значением корня уравнения f(x) = 0 на отрезке , найденным методом простой итерации с точностью e.
Построить алгоритм для уточнения корня уравнения: x 3 + 5x – 1 = 0 на отрезке методом простой итерации с точностью e.
1. Функция f(x) = x 3 +5x-1 является непрерывно дифференцируемой на отрезке , содержащем один корень уравнения.
2. Наибольшую трудность в методе простой итерации представляет построение функции j(x), удовлетворяющей всем условиям:
Рассмотрим: 
.
Уравнение x = j 1 (x) эквивалентно уравнению f(x) = 0, но функция j 1 (x) не является непрерывно дифференцируемой на отрезке .
Рис. 2.4. График функции j 2 (x)
С другой стороны, , следовательно, . Отсюда: – непрерывно дифференцируемая функция. Отметим, что уравнение:x = j 2 (x) эквивалентно уравнению f(x) = 0. Из графика (рис. 2.4) видно, что функция j 2 (x) переводит отрезок в себя.
Условие, что функция j(x) переводит отрезок в себя, можно переформулировать следующим образом: пусть – область определения функции j(x), а – область изменения j(x).
Если отрезок принадлежит отрезку , то функция j(x) переводит отрезок в себя.
, 
.
Все условия для функции j(x) выполнены.
Формула итерационного процесса: x n +1 = j 2 (x n).
3. Начальное приближение: x 0 = 0.
4. Условие остановки итерационного процесса:
Рис. 2.5. Геометрический смысл метода простой итерации
.
При выполнении этого условия x n +1 – приближенное значение корня на отрезке , найденное методом простой итерации с точностью e . На рис. 2.5. иллюстрируется применение метода простой итерации.
Теорема о сходимости и оценка погрешности
Пусть отрезок содержит один корень уравнения x = j(x), функция j(x) является непрерывно дифференцируемой на отрезке , переводит отрезок в себя, и выполнено условие :
.
Тогда для любого начального приближения x 0 Î последовательность сходится к корню уравнения y = j(x) на отрезке и справедлива оценка погрешности :
.
Устойчивость метода простой итерации. При выполнении условий теоремы о сходимости алгоритм метода простой итерации является устойчивым.
Сложность метода простой итерации . Объем памяти ЭВМ, необходимый для реализации метода простой итерации, незначителен. На каждом шаге нужно хранить x n , x n +1 , q и e.
Оценим число арифметических действий, необходимых для реализации метода простой итерации. Запишем оценку для числа n 0 = n 0 (e) такого что, для всех n ³ n 0 выполняется неравенство: 
Из этой оценки вытекает, что чем ближе q к единице, тем медленнее сходится метод.
Замечание. Не существует общего правила построения j(x) по f(x) так, чтобы выполнялись все условия теоремы о сходимости. Часто используется следующий подход: в качестве функции j выбирается функция j(x) = x + k× f(x), где k – константа.
При программировании метода простой итерации для остановки итерационного процесса часто требуют одновременного выполнения двух условий:
и .
Все остальные итерационные методы, которые мы будем рассматривать, являются частными случаями метода простой итерации. Например, при 
метод Ньютона является частным случаем метода простой итерации.
Лекция Итерационные методы решения системы алгебраических линейных уравнений.
Условие сходимости итерационного процесса.Метод Якоби.Метод Зейделя
Метод простой итерации
Рассматривается система линейных алгебраических уравнений
Для применения итерационных методов система должна быть приведена к эквивалентному виду
Затем выбирается начальное приближение к решению системы уравненийи находится последовательность приближений к корню.
Для сходимости итерационного процесса
достаточно, чтобы было выполнено условие
(норма матрицы). Критерий окончания
итераций зависит от применяемого
итерационного метода.
Метод Якоби .
Самый простой способ приведения системы к виду, удобному для итерации, состоит в следующем:
Из первого уравнения системы выразим неизвестное x 1 , из второго уравнения системы выразимx 2 , и т. д.
В результате получим систему уравнений с матрицей B, в которой на главной диагонали стоят нулевые элементы, а остальные элементы вычисляются по формулам:
Компоненты вектора d вычисляются по формулам:
Расчетная формула метода простой итерации имеет вид:
или в покоординатной форме записи выглядит так:
Критерий окончания итераций в методе Якоби имеет вид:
Если
,
то можно применять более простой критерий
окончания итераций
Пример 1. Решение системы линейных уравнений методом Якоби.
Пусть дана система уравнений:
Требуется найти решение системы с
точностью
Приведем систему к виду удобному для итерации:
Выберем начальное приближение, например,
- вектор правой части.
Тогда первая итерация получается так:
Аналогично получаются следующие приближения к решению.
Найдем норму матрицы B.
Будем использовать норму
Так как сумма модулей элементов в каждой
строке равна 0.2, то
,
поэтому критерий окончания итераций в
этой задаче
Вычислим нормы разностей векторов:
Так как
заданная точность достигнута на четвертой
итерации.
Ответ: x 1 = 1.102, x 2 = 0.991, x 3 = 1.0 1 1
Метод Зейделя .
Метод можно рассматривать как модификацию метода Якоби. Основная идея состоит в том, что при вычислении очередного (n+1) -го приближения к неизвестномуx i приi >1 используют уже найденные(n+1)- е приближения к неизвестнымx 1 ,x 2 , ...,x i - 1 , а неn -ое приближение, как в методе Якоби.
Расчетная формула метода в покоординатной форме записи выглядит так:
Условия сходимости и критерий окончания итераций можно взять такими же, как в методе Якоби.
Пример 2. Решение систем линейных уравнений методом Зейделя.
Рассмотрим параллельно решение 3-х систем уравнений:
Приведем системы к виду удобному для итераций:
Заметим, что условие сходимости
выполнено только для первой системы.
Вычислим 3 первых приближения к решению
в каждом случае.
1-ая система:
Точным решением будут значения: x 1 = 1.4, x 2 = 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).
и параметр τ > 0 выбирают так, чтобы по
возможности сделать минимальной величину
Пусть λ min и λ max – минимальное и максимальное собственные значения матрицы A. Оптимальным является выбор параметра
В этом случае
принимает минимальное значение равное:
Пример 3. Решение систем линейных уравнений методом простой итерации. (вMathCAD)
Пусть дана система уравнений Ax = b
Для построения итерационного процесса найдем собственные числа матрицы A:
- используется встроенная функция для
нахождения собственных чисел.
Вычислим итерационный параметр и проверим условие сходимости
Условие сходимости выполнено.
Возьмем начальное приближение - вектор x0, зададим точность 0.001 и найдем начальные приближения по приведенной ниже программе:
|
| |
Точное решение
Замечание. Если в программе возвращать матрицу rez, то можно просмотреть все найденные итерации.
Рассмотрим систему линейных алгебраических уравнений
Проведем несколько равносильных преобразований. Умножим обе части системы на один и тот же скалярный множитель затем прибавим к правой и левой частям системы вектор Систему уравнений можно теперь записать в виде, удобном для итераций:
 |
(2.15) |
Теперь построим последовательность приближений к решению системы. Выберем произвольный вектор - начальное приближение к решению. Чаще всего его просто полагают нулевым вектором. Скорее всего, начальное приближение не удовлетворяет (2.15) и, следовательно, исходной системе. При подстановке его в исходное уравнение возникает невязка Вычислив невязку, с помощью (2.15) можно уточнить приближение к решению, считая, что
По первому приближению снова вычисляется невязка, процесс продолжается. В
ходе итерации получаем Эквивалентная формулировка метода, называемого методом простых итераций
, заключается в следующем. Решение (2.15) находится как предел последовательности 
приближений, члены которой связаны рекуррентным соотношением (оно эквивалентно приведенному выше, из записи исключен вектор невязки):
| (2.16) |
(или любому произвольному вектору). Если предел такой последовательности существует, то говорят о сходимости итерационного процесса к решению СЛАУ .
Существуют другие формы записи метода итераций , например
При , последняя формула соответствует однопараметрическому итерационному процессу - рассмотренному выше методу простых итераций . При , - n -шаговому явному итерационному процессу, при , - методу простой итерации без итерационного параметра. В случае, когда , итерационный метод называется неявным - для вычисления следующего приближения к решению придется решать (как правило, более простую, чем исходную) систему линейных уравнений.
Теорема (достаточное условие сходимости
метода простой итерации
).
Итерационный процесс (2.16) сходится к решению СЛАУ
со скоростью геометрической прогрессии при выполнении условия: 
Доказательство .
Пусть - точное решение системы (2).
Вычитая из (2.16)-(2.15), получим , или, обозначив погрешность 
,
получим для эволюции погрешности уравнение 
Справедлива цепочка неравенств: , где 
Отсюда следует, что при 
Из неравенства 
можно получить оценку количества итераций,необходимых для достижения точности т.е. для выполнения условия Эта оценка имеет вид
Теорема (критерий сходимости метода простой итерации (без доказательства)) . Пусть СЛАУ (2.15) имеет единственное решение. Тогда для сходимости итерационного процесса (2.16) необходимо и достаточно, чтобы все собственные значения матрицы по абсолютной величине были меньше единицы.
Сравним по количеству арифметических действий прямые и итерационные методы . Метод Гаусса без выбора главного элемента при требует
Арифметических действий; метод простой итерации
(2.16) 
, где i
- число приближений, необходимое для достижения заданной точности. Значит, при I < n/3
метод итераций становится предпочтительнее. В реальных задачах, в основном, Кроме того, итерационные методы
можно делать более эффективными, изменяя итерационные параметры. В ряде случаев итерационные методы
оказываются более устойчивыми по отношению к накоплению ошибок округления, чем прямые
.