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

Назначение сервиса. Онлайн-калькулятор предназначен для отыскания корней уравнения методом итераций.

Решение оформляется в формате Word.

Правила ввода функции

Примеры

≡ x^2/(1+x)
cos²(2x+π) ≡ (cos(2*x+pi))^2

≡ x+(x-1)^(2/3)

Скачать пример оформления

Одним из наиболее эффективных способов численного решения уравнений является метод итерации. Сущность этого метода заключается в следующем. Пусть дано уравнение f(x)=0.
Заменим его равносильным уравнением

x=φ(x). (1)

Выберем начальное приближение корня x₀ и подставим его в правую часть уравнения (1). Тогда получим некоторое число

x₁=φ(x₀). (2)

Подставляя теперь в правую часть (2) вместо x₀ число x₁ получим число x₂=φ(x₁). Повторяя этот процесс, будем иметь последовательность чисел

x_n=φ(x_n-1) (n=1,2..). (3)

Если эта последовательность сходящаяся, то есть существует предел

, то переходя к пределу в равенстве (3) и предполагая функцию φ(x) непрерывной найдем

или ξ=φ(ξ).
Таким образом, предел ξ является корнем уравнения (1) и может быть вычислен по формуле (3) с любой степенью точности.

Рис. 1а Рис. 1б

Рис. 2. |φ′(x)|>1 - расходящийся процесс

На рис.1а, 1б в окрестности корня |φ′(x)|<1 и процесс итерации сходится. Однако, если рассмотреть случай |φ′(x)|>1, то процесс итерации может быть расходящимся (см. рис.2).

Достаточные условия сходимости метода итерации

Теорема 7. Пусть функция φ(x) определена и дифференцируема на отрезке [a,b], причем все ее значения φ(x)∈[a,b] и пусть |φ′(x)|≤q<1 при x∈[a,b]. Тогда процесс итерации x_n = φ(x_n_-1) сходится независимо от начального значения x₀∈[a,b] и предельное значение

является единственным корнем уравнения x= φ(x) на отрезке [a,b].
Доказательство: Рассмотрим два последовательных приближения x_n = φ(x_n_-1) и x_n₊₁= φ(x_n) и возьмем их разность x_n+1-x_n=φ(x_n)-φ(x_n-1). По теореме Лагранжа правая часть может быть представлена как

φ′(x_n)(x_n-x_n-1)

где x_n∈[a,b]
Тогда получим

Полагая n=1,2,...

|x₂-x₁|≤q|x₁-x₀|
|x₃-x₂|≤q|x₂-x₁|≤q²|x₁-x₀|
|x_n+1-x_n≤qⁿ|x₁-x₀| (4)

Из (4) в силу условия q<1 видно, что последовательность {x_n} сходится к некоторому числу ξ, то есть

, и следовательно,

(в силу непрерывности функции φ(x))
или ξ= φ(ξ) ч.т.д.
Для погрешности корня ξ можно получить следующую формулу.
Имеем x_n=φ(x_n-1).
Далее ξ-x_n=ξ-φ(x_n-1) = φ(ξ)-φ(x_n-1) →
Теперь φ(x_n-1)=φ(x_n)-φ′(c)(x_n-x_n-1) →
φ(ξ)-φ(x_n)+φ′(c)(x_n-x_n-1)
В результате получим

ξ-x_n = φ′(c₁)(ξ-x_n-1)+φ′(c)(x_n-x_n-1)
или
|ξ-x_n|≤q|ξ-x_n|+q|x_n-x_n-1|

Отсюда

, (5)

откуда видно, что при q близком к 1 разность |ξ -x_n| может быть очень большой несмотря на то что |x_n-x_n_-1|<ε, где ε-заданная величина. Для того, чтобы вычислить ξ с точностью ε необходимо обеспечить

. (6)

Тогда подставляя (6) в (5), получим |ξ -x_n|<ε.
Если q очень мало, то вместо (6) можно использовать

|x_n-x_n_-1|<ε

Сходимость метода итерации линейная с коэффициентом сходимости α=q. Действительно, имеем
ξ-x_n=φ(ξ)-φ_n-1 = φ′(c)·(ξ-x_n-1), отсюда |ξ-x_n|≤q·|ξ-x_n-1|.

Замечание. Пусть в некоторой окрестности корня ξ∈(a,b) уравнения x= φ(x) производная φ’(x) сохраняет постоянный знак и выполнено неравенство |φ’(x)|≤q<1. Тогда, если φ’(x) положительна, то последовательные приближения x_n = φ(x_n_-1) сходятся к корню монотонно.
Если же φ’(x) отрицательна, то последовательные приближения колеблются около корня.
Рассмотрим способ представления уравнения f(x)=0 в форме x= φ(x).
Функцию φ(x) необходимо задать такую, чтобы |φ’(x)| была малой величиной в окрестности корня.
Пусть известно m₁ и M₁ - наименьшее и наибольшее значения производной f’(x)
0<m₁≤f’(x) ≤M₁ (7)
Заменим уравнение f(x)=0 эквивалентным ему уравнением
x = x - λf(x).
Положим φ(x) = x- λf(x). Подберем параметр λ таким образом, чтобы в окрестности корня ξ выполнялось неравенство

0≤|φ′(x)|=|1-λ·f′(x)|≤q≤1

Отсюда на основании (7) получаем

0≤|1-λM₁|≤|1-λm₁|≤q

Тогда выбирая λ = 1/M₁, получим
q = 1-m₁/M₁ < 1.
Если λ =1/f’(x), то итерационная формула x_n = φ(x_n_-1) переходит в формулу Ньютона

x_n = x_n_-1 – f(x_n)/f’(x).

Метод итераций в Excel

В ячейку B2 заносим начало интервала a, в ячейку B3 заносим конец интервала b. Строку 4 отводим под заголовок таблицы. Сам процесс итераций организуем в ячейках A5:D5.

Процесс нахождения нулей функции методом итераций состоит из следующих этапов:

Получить шаблон с омощью этого сервиса.
Уточнить интервалы в ячейках B2, B3.
Копировать строки итераций до требуемой точности (столбец D).

Примечание: столбец A - номер итерации, столбец B - корень уравнения X, столбец C - значение функции F(X), столбец D - точность eps.

Пример. Найти корень уравнения e^-x-x=0, x=∈[0,1], ε=0.001 (8)
Решение.
Представим уравнение (8) в форме x=x-λ(e^-x-x)
Найдем максимальное значение производной от функции f(x)= e^-^x-x.
max f′(x)=max(-(e^-x+1)) ≈ -1.37. Значение . Таким образом, решаем следующее уравнение
x=x+0,73(e^-^x-x)
Значения последовательных приближений даны в таблице.