Метод простой итерации последовательных приближений. Метод итераций. Общий алгоритм последовательных приближений

По аналогии с (2.1) систему (5.1) можно представить в следующей эквивалентной форме:

где g(x) - итерационная вектор-функция векторного аргумента. Системы нелинейных уравнений часто возникают непосредственно в виде (5.2) (например, в численных схемах для дифференциальных уравнений), в этом случае никаких дополнительных усилий для преобразования уравнений (5.1) в систему (5.2) не требуется. Если продолжить аналогию с методом простой итерации для одного уравнения, то итерационный процесс, основанный на уравнении (5.2), можно организовать следующим образом:

• 1) выбирается некоторый начальный вектор х ((,) е 5 о (х 0 , а) (предполагается, что х* е 5„(х 0 , а));
• 2) последующие приближения вычисляются по формуле

то итерационный процесс завершен и

Как и раньше, нам необходимо выяснить, при каких условиях

Обсудим этот вопрос, выполнив простой анализ. Вначале мы введем ошибку /г-го приближения как е (^ = x (i) - х*. Тогда мы можем записать

Подставим эти выражения в (5.3) и разложим g(x* + e (/i)) по степеням е (к> в окрестности х* как функцию векторного аргумента (предполагая, что все частные производные функции g(x) непрерывны). Учитывая также, что х* = g(x*), мы получим

или в матричной форме

В = {b nm } = I (х*)1 - итерационная матрица.

Если норма ошибки ||е®|| достаточно мала, то вторым слагаемым в правой части выражения (5.4) можно пренебречь, и тогда оно совпадает с выражением (2.16). Следовательно, условие сходимости итерационного процесса (5.3) вблизи точного решения описывается теоремой 3.1.

Сходимость метода простой итерации. Необходимое и достаточное условие для сходимости итерационного процесса (5.3):

и достаточное условие:

Эти условия имеют скорее теоретическое, чем практическое значение, так как мы не знаем х‘. По аналогии с (1.11) получим условие, которое может быть полезным. Пусть х* е 5 о (х 0 , а) и матрица Якоби для функции g(x)

существует для всех x e S n (x 0 , a ) (заметим, что C(x*) = В). Если элементы матрицы С(х) удовлетворяют неравенству

для всех х е 5„(х 0 , а), тогда достаточное условие (5.5) также выполняется для любой матричной нормы.

Пример 5.1 (метод простой итерации) Рассмотрим следующую систему уравнений:

Одна из возможностей представить эту систему в эквивалентной форме (5.2) - выразить Х из первого уравнения и х 2 из второго уравнения:

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

Точное решение х* е 5„((2, 2), 1). Выберем начальный вектор х (0) = (2,2) и ? р = КТ 5 . Результаты вычислений представлены в табл. 5.1.

Таблица 5.1

		||Х - X (i_1 > | 2 / X (A) 2
	1.50000 1.73205
	1.69258 1.34646
	1.71914 1.40036
	1.71642 1.39483
	1.71669 1.39536
	1.71667 1.39532

Эти результаты показывают, что сходимость довольно медленная. Для того чтобы получить количественную характеристику сходимости, проведем простой анализ, считая х (1/) точным решением. Матрица Якоби С(х) для нашей итерационной функции имеет вид

тогда матрица В приближенно оценивается как

Легко проверить, что ни условие (5.5), ни условие (5.6) не удовлетворяются, но сходимость имеет место, так как 5(B) ~ 0.8.

Часто можно ускорить сходимость метода простой итерации, слегка изменив процесс вычислений. Идея такой модификации очень проста: для вычисления п -й компоненты вектора х (А+1) можно использовать не только (т = п ,..., N ), но также уже вычисленные компоненты вектора следующего приближения х к ^ (/= 1,п - 1). Таким образом, модифицированный метод простой итерации может быть представлен в виде следующей итерационной схемы:

Если приближения, генерируемые итерационным процессом (5.3), сходятся, то итерационный процесс (5.8) сходится, как правило, быстрее за счет более полного использования информации.

Пример 5.2 (модифицированный метод простой итерации) Модифицированная простая итерация для системы (5.7) представляется в виде

Как и прежде, выберем начальный вектор х (0) = (2, 2) и г р = = 10 -5 . Результаты вычислений представлены в табл. 5.2.

Таблица 5.2

	1.50000 1.11803
	1.72076 1.40036
	1.71671 1.39538
	1.71667 1.39533

I Теболыное изменение порядка вычислений привело к уменьшению количества итераций в два раза, а значит, и к уменьшению количества операций в два раза.

Метод простой итерации, называемый также методом последовательного приближения, - это математический алгоритм нахождения значения неизвестной величины путем постепенного ее уточнения. Суть этого метода в том, что, как видно из названия, постепенно выражая из начального приближения последующие, получают все более уточненные результаты. Этот метод используется для поиска значения переменной в заданной функции, а также при решении систем уравнений, как линейных, так и нелинейных.

Рассмотрим, как данный метод реализуется при решении СЛАУ. Метод простой итерации имеет следующий алгоритм:

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

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

Как мы видим, метод простой итерации дает довольно точные результаты, однако для решения этого уравнения нам пришлось потратить много времени и проделать громоздкие вычисления.

Пусть дана система n алгебраических уравнений с n неизвестными:

Алгоритм метода простой итерации:

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

Затем формируется циклический математический процесс, каждый цикл которого представляет собой одну итерацию. В результате каждой итерации получается новое значение вектора неизвестных. Для организации итерационного процесса запишем систему (1) в приведенном виде. При этом слагаемые, стоящие на главной диагонали, нормируются и остаются слева от знака равенства, а остальные переносятся в правую часть. Приведенная система уравнений имеет вид:

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

12. Основная итерационная формула, применяемая в методе простой итерации, для решения нелинейного уравнения:

13. Критерий останова итерационного процесса в методе простой итерации для решения нелинейного уравнения:

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

14. Критерий выбора вспомогательной функции F(x) для итерационного отрезка интервала :

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

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

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

15. Метод Гаусса, применяемый для решения систем линейных уравнений, предусматривает:

Метод основан на преобразовании матрицы к треугольному виду. Это достигается последовательным исключением неизвестных из уравнений системы.

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 – константа.

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

и .

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

Численное решение уравнений и их систем состоит в приближённом определении корней уравнения или системы уравнений и применяется в случаях, когда точный метод решения неизвестен или трудоёмок.

Постановка задачи [ | ]

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

f (x 1 , x 2 , … , x n) = 0 {\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=0}

{ f 1 (x 1 , x 2 , … , x n) = 0 … f n (x 1 , x 2 , … , x n) = 0 {\displaystyle \left\{{\begin{array}{lcr}f_{1}(x_{1},x_{2},\ldots ,x_{n})&=&0\\\ldots &&\\f_{n}(x_{1},x_{2},\ldots ,x_{n})&=&0\end{array}}\right.}

Численные методы решения уравнений [ | ]

Покажем, как можно решить изначальную систему уравнений , не прибегая к оптимизационным методам . В случае, если наша система представляет собой СЛАУ , целесообразно прибегнуть к таким методам, как метод Гаусса или метод Ричардсона . Однако мы всё же будем исходить из предположения, что вид функции нам неизвестен, и воспользуемся одним из итерационных методов численного решения . Среди большого разнообразия таковых выберем один из наиболее известных - метод Ньютона . Этот метод в свою очередь основывается на принципе сжимающего отображения. Поэтому сначала будет изложена суть последнего.

Сжимающее отображение [ | ]

Определим терминологию:

Говорят, что функция осуществляет сжимающее отображение на , если

Тогда справедлива следующая основная теорема:

Теорема Банаха (принцип сжимающих отображений). Если φ {\displaystyle \varphi } - сжимающее отображение на [ a , b ] {\displaystyle } , то:

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

Поясним смысл параметра α {\displaystyle \alpha } для случая одной переменной. Согласно теореме Лагранжа имеем:

φ (x) ∈ C 1 [ a , b ] . ∀ x 1 , x 2 ∈ (a , b) , x 1 < x 2 ∃ ξ ∈ (x 1 , x 2) : φ ′ (ξ) (x 2 − x 1) = φ (x 2) − φ (x 1) {\displaystyle \varphi (x)\in C^{1}.\quad \forall x_{1},x_{2}\in (a,\;b),\quad x_{1}

Отсюда следует, что α ≈ | φ ′ (ξ) | {\displaystyle \alpha \approx |\varphi "(\xi)|} . Таким образом, для сходимости метода достаточно, чтобы ∀ x ∈ [ a , b ] | φ ′ (x) | ≤ 1. {\displaystyle \forall x\in \quad |\varphi "(x)|\leq 1.}

Общий алгоритм последовательных приближений [ | ]

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

Применительно к СЛАУ [ | ]

Рассмотрим систему:

{ a 11 x 1 + … + a 1 n x n = b 1 … a n 1 x 1 + … + a n n x n = b n {\displaystyle \left\{{\begin{array}{ccc}a_{11}x_{1}+\ldots +a_{1n}x_{n}&=&b_{1}\\\ldots &&\\a_{n1}x_{1}+\ldots +a_{nn}x_{n}&=&b_{n}\end{array}}\right.}

Для неё итерационное вычисление будет выглядеть так:

(x 1 x 2 ⋮ x n) i + 1 = (a 11 + 1 a 12 … a 1 n a 21 a 22 + 1 … a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 … a n n + 1) (x 1 x 2 ⋮ x n) i − (b 1 b 2 ⋮ b n) {\displaystyle \left({\begin{array}{c}x_{1}\\x_{2}\\\vdots \\x_{n}\end{array}}\right)^{i+1}=\left({\begin{array}{cccc}a_{11}+1&a_{12}&\ldots &a_{1n}\\a_{21}&a_{22}+1&\ldots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\ldots &a_{nn}+1\end{array}}\right)\left({\begin{array}{c}x_{1}\\x_{2}\\\vdots \\x_{n}\end{array}}\right)^{i}-\left({\begin{array}{c}b_{1}\\b_{2}\\\vdots \\b_{n}\end{array}}\right)}

Метод будет сходится с линейной скоростью, если ‖ a 11 + 1 … a 1 n ⋮ ⋱ ⋮ a n 1 … a n n + 1 ‖ < 1 {\displaystyle \left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn}+1\end{array}}\right\|<1}

Двойные вертикальные черты означают некоторую норму матрицы .

Решение уравнения f(x)=0 по методу Ньютона, начальное приближение: x 1 =a.

Метод Ньютона (метод касательных) [ | ]

Одномерный случай [ | ]

Оптимизация преобразования исходного уравнения f (x) = 0 {\displaystyle f(x)=0} в сжимающее отображение x = φ (x) {\displaystyle x=\varphi (x)} позволяет получить метод с квадратичной скоростью сходимости.

Чтобы отображение было наиболее эффективно, необходимо, чтобы в точке очередной итерации x ∗ {\displaystyle x^{*}} выполнялось φ ′ (x ∗) = 0 {\displaystyle \varphi "(x^{*})=0} . Будем искать решение данного уравнения в виде φ (x) = x + α (x) f (x) {\displaystyle \varphi (x)=x+\alpha (x)f(x)} , тогда:

φ ′ (x ∗) = 1 + α ′ (x ∗) f (x ∗) + α (x ∗) f ′ (x ∗) = 0 {\displaystyle \varphi "(x^{*})=1+\alpha "(x^{*})f(x^{*})+\alpha (x^{*})f"(x^{*})=0}

Воспользуемся тем, что f (x) = 0 {\displaystyle f(x)=0} , и получим окончательную формулу для α (x) {\displaystyle \alpha (x)} :

α (x) = − 1 f ′ (x) {\displaystyle \alpha (x)=-{\frac {1}{f"(x)}}}

С учётом этого сжимающая функция примет вид:

φ (x) = x − f (x) f ′ (x) {\displaystyle \varphi (x)=x-{\frac {f(x)}{f"(x)}}}

Тогда алгоритм нахождения численного решения уравнения f (x) = 0 {\displaystyle f(x)=0} сводится к итерационной процедуре вычисления:

x i + 1 = x i − f (x i) f ′ (x i) {\displaystyle x_{i+1}=x_{i}-{\frac {f(x_{i})}{f"(x_{i})}}}