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

Другим методом решения трансцендентных уравнений является метод простых итераций. Пусть дано уравнение f(x) = 0, где f(x) – непрерывная функция, Требуется определить действительный корень уравнения, заключенный на отрезке [a, b]. Полагая f(x) = x - φ(x), заменим уравнение f(x) = 0 равносильным ему уравнением

x = φ(x). (1)

Выберем какое-нибудь х₀ € [a, b] и подставим в правую часть уравнения (1); тогда получим х₁ = φ(х₀). Затем это значение подставим в правую часть уравнения (1) и получим х₂ = φ(x₁). Повторяя этот процесс, получим последовательность чисел x_n = φ(x_n−1). Здесь могут представиться два случая:

1. последовательность x₁, x₂, …, x_n , ….сходится, т.е. имеет предел, тогда этот предел будет корнем уравнения f(x) = 0;

2. последовательность x₁, x₂, …, x_n , …. расходится, т.е. не имеет предела.

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

Теорема. Пусть на отрезке [a, b] функция φ(x) определена и дифференцируема причем все ее значения φ(x) € [a, b], тогда ,если существует правильная дробь q такая, что

|φ′(x)| ≤ q < 1 (*)

при х€ (a, b), то

1. То итерационный процесс

x_n = φ(x_n−1) (n = 1, 2, …)

сходится, а за нулевое приближение можно взять любое число из отрезка [a, b],

2. Предельное значение

является единственным корнем уравнения

x = φ(x)

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

Пусть f(x) = x − φ(x), тогда f′(x) =1 − φ′ (x) ≥ 1 – q , отсюда, учитывая, что f(ξ) = 0, получим

|x _n – x_{n + 1}| = |φ(x _{n − 1}) - φ(x_n)| = = |f ′(c_n)| |x _n – x _{n − 1}| ≤ q |x_n – x_{n – 1}|

|x _n− x_{n + 1}| = |x _n - φ(x_n)| = |f(x_n) – f(ξ)| = f ′(c_n) |x_n – ξ | = (1 − φ(c_n)) |x _n – ξ| ≥ (1 – q) |x _n – ξ |

Отсюда

(2)

Формула (2) дает возможность оценить погрешность приближенного значения х _n по расхождению двух последовательных приближений x _{n – 1} и x _n.

Пусть ε – предельная абсолютная погрешность корня ξ. Процесс итерации следует продолжать до тех пор, пока для двух последовательных приближений x _{n – 1} и x _n не будет выполняться неравенство

|x _n − x _{n – 1}|

Выясним далее, как привести уравнение f(x) = 0 к виду (1). Пусть φ(x) = λ f(x) + x. Если x = ξ - корень уравнения f(x) = 0, то φ(ξ) = ξ, т.е. x = ξ – корень уравнения (1). Таким образом, уравнение x = x + λ f(x) равносильно уравнению f(x) = 0. Подберем λ так, чтобы выполнялось условие (*).

| φ′(x)| = | λ f′(x) + 1| < 1

-1 < λ f′ (x) + 1 < 1,

-2 < λ f′ (x) < 0

Пусть r = max |f′(x)|. Тогда

Геометрическая иллюстрация метода итераций.

Построим на плоскости хОу графики функций у = х и y = φ(x). Каждый действительный корень является абсциссой точки пересечения М прямой у = х и кривой y = φ(x). отправляясь от некоторой точки А₀(х₀, φ(x₀)) строим ломаную линию А₀В₁А₁В₂А₂В_….. («лестница»), звенья которой попеременно параллельны оси Ох и Оу, вершины А₀, А₁, А₂, … лежат на кривой y = φ(x),а вершины В₁, В₂, В₃, … лежат на прямой у = х. Общие абсциссы точек А₁ и В₁, А₂ и В₂, …, представляют собой соответственно последовательные приближения x₁, x₂, … корня ξ.

Возможен также другой вид ломаной А₀В₁А₁В₂А₂В_…. («спираль»). Очевидно, решение в виде «лестницы» получается, когда производная φ′(x) положительна. Решение в виде «спирали», получается, когда φ′(x) отрицательна. При этом процесс итерации сходится, если | φ′(x)| < 1, т.е. угловой коэффициент касательной к кривой по модулю меньше единицы. Если | φ′(x)| > 1, то процесс итерации может расходиться.

y = x y = φ(x)

y B₁ A₀

B₂

A₁

B₃

M A₂

A₃

ξ x₃ x₂ x₁ x₀ x

y y = x

A₁ B₂

B₃ A₃ A₀

B₁ y = φ(x)

x₁ x₃ ξ x₂ x₀ x

П р и м е р .

Составим далее на языке QBASIC программу нахождения корня уравнения

f(x) = 1 – 3x + cosx =0 (**)

методом итераций с точностью Е =0.0001.

Ранее показано, что единственный корень уравнения находится на интервале [0, 1]/

f′(x) = -3 – sin x < 0, |f′(x)| ≤ 4.

Представляем уравнение (**) в виде

x = φ(x) = λ f(x) + x (***)

λ = ² / _r, r = max |f′(x)| = 4

x = ² / _r (1 -3 x + cos x) +x = ½ (1 – x + cos x) ≡ φ(x)

Для определения окончания процесса итерации находим величину q из условия

| φ′ (x)|≤ q < 1

|φ′ (x)| = | 0.5 (−1− sin x)| ≤ 0.8

Блок-схема программы имеет следующий вид.

Ввод x₀, E, q

q1 = ^{(1 – q) E}/ _q величина, необходимая для определения

окончания процесса итерации.

n = 0 , x = x₀ n – счетчик числа итераций

t = 0.5 (1 –x + cosx)

n = n + 1

нет

|x – t | < q1

да

Вывод root = x , n

x = t

end

Текст программы имеет вид:

Ответ программы: x =0.6070896 или, округляя x = 0. 60709, n = 45.

Рассмотренную задачу можно решить в среде MathCAD.

f(x) = 1 – 3x + cosx =0

Представим один из способов решения трансцендентного уравнения в среде MathCAD.

Открываем рабочий лист и записываем левую часть уравнения

Затемняем один символ (переменную х ) в этой записи путем протаскивания курсора. Открываем меню «Символ», подменю «Переменные», щелчок по строке «Решить». На рабочем листе появится результат. Делаем округление.

.60710

Строим график функции, определяющей левую часть уравнения.