Определение корня одномерного уравнения методом простой итерации

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

(14) имеет вид:

(15)

где .

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

(16)

Рис.3 Иллюстрация сходящегося процесса метода простой итерации

На рисунке 3 проиллюстрирован процесс последовательного решения уравнения (1) методом простой итерации. Пересечение кривой и прямой (точка A) соответствует решению системы уравнений (16) и корню уравнения (14).

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

(17) Алгоритм метода простой итерации выглядит следующим образом:

x1=начальное_значение

err = требуемая_точность

Начало цикла

x2=F(x1)

Если |x2-x1| < err тогда

Вывод на печать x2

Выход из программы

Иначе

x1=x2

Конец если

Конец цикла

Метод простой итерации находит корень не во всех случаях. На рисунке 4 приведен пример расходящегося процесса.

Рис. 4 Пример расходящегося процесса метода простой итерации

Рассмотрим нестрогий вывод условия сходимости метода простой итерации.

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

Рис. 5 Сходящийся ряд значений x_k

Если ряд сходится, то для него справедливо соотношение:

(18) или для шага с номером k

(19) Если правую часть неравенства (19), с учетом (15), представить в виде , тогда условие сходимости на шаге k принимает вид:

(20)

Условие сходимости метода простой итерации (20) представляет собой разностное представление производной функции , таким образом, из формулы (20) можно получить дифференциальную форму условия сходимости метода простой итерации:

(21) для значений , принадлежащих окрестности искомого корня.

Формулу (21) можно использовать для предварительной оценки сходимости метода простой итерации. Так, для примера, приведенного на рис.3, производная функции в окрестности корня меньше единицы – процесс сходится, а для примера, приведенного на рис.4 производная функции в окрестности корня больше единицы и процесс расходится.

В некоторых случаях можно улучшить сходимость метода простой итерации. Рассмотрим модифицированный метод простой итерации. Корни уравнения не изменятся, если к правой и левой части добавить , где – параметр (в более общем случае к правой и левой части уравнения (14) можно добавить произвольную обратимую функцию ). Тогда уравнение (14) примет вид:

выразив , получим новую усовершенствованную формулу для метода простой итерации:

или

, где

Условие сходимости (20) для модифицированного метода простой итерации будет иметь вид следующего неравенства с параметром :

или

(22) Изменяя параметр в выражении (22) можно значительно улучшить сходимость метода простой итерации.

В качестве примера рассмотрим процесс определения корней уравнения .

Рис. 6 Анализ функции для метода простой итерации

На рисунке 6 приведены графики функции – линия 1, – линия 2, – линия 3. Поскольку тангенс угла наклона линии 2 больше чем 1 в окрестности первого корня – этот корень неустойчив. Второй корень устойчив – тангенс угла наклона линии 2 в окрестности второго корня меньше единицы.

Описание алгоритма нахождения корня нелинейного одномерного уравнения методом простой итерации:

Задаем точность вычисления корня по оси абсцисс и по оси ординат: e_x и e_y.

Задаем максимальное количество итераций нахождения корня – maxi.

Задаем начальное значение x₀.

Начало цикла по i от 1 до maxi.

В цикле вычисляем следующее приближение корня: x₁=f(x₀)+x₀.

В цикле вычисляем изменение значений x и f(x) на данной итерации:

dx=|x₁-x₀|, df=|f(x₁)-f(x₀)|.

Проверяем условие сходимости алгоритма. Задаем ветвление: если dx<e_x и df<e_y, то корень найден, вывод на экран значения x_i, f(x_i) и номера итерации i. Выход из программы. Конец ветвления.

Копируем значение x₁ в x₀ для следующей итерации: x₀=x₁.

Конец цикла.

Вывод сообщения: ”Корень не найден за i итераций”

Конец программы.

Описание алгоритма нахождения корня уравнения методом простой итерации на естественном языке:

ex=точность_по_оси_X

ey=точность_по_оси_Y

maxi=максимальное_количество_итераций

x0=начальное_значение_х

Цикл по i от 1 до maxi

x1=f(x0)

dx=Модуль(x1-x0)

df=Модуль(f(x1)-f(x0))

Если dx<ex И df<ey Тогда

Печать " Корень найден за "+i+" итераций "

Печать " x= "+x1+" f(x)= "+f(x1)

Печать " Конец итераций "

Выход Из Программы

Конец Если

x0=x1

Конец Цикла

Печать "Решение не найдено за "+ maxi +"итераций "

Определение Функции f0

Параметры x

Возврат 3*x-EXP(x)

Конец Определения Функции

Определение Функции f

Параметры x

Возврат f0(x)+x

Конец Определения Функции

Пример реализации алгоритма нахождения корня одномерного нелинейного уравнения методом простой итерации на VFP:

CLEAR

ex=0.0001

ey=0.0001

maxi=100

x0=1

FOR i=1 TO maxi

x1=f(x0)

dx=ABS(x1-x0)

df=abs(f(x1)-f(x0))

IF dx<ex AND df<ey then

?" Корень найден за "+ALLTRIM(STR(i))+" итераций "

?" x= "+STR(x1)+" f(x)= "+STR(f(x1))

?

?" Конец итераций "

RETURN

ENDIF

x0=x1

endfor

? "Решение не найдено за", maxi, "итераций"

FUNCTION f0

PARAMETERS x

RETURN 3*x-EXP(x)

ENDFUNC

FUNCTION f

PARAMETERS x

RETURN f0(x)+x

ENDFUNC

Пример реализации алгоритма нахождения корня одномерного нелинейного уравнения методом простой итерации на VBA:

Sub Simple_Iteration()

ex = 0.0001

ey = 0.0001

maxi = 100

x0 = 1.1

For i = 1 To maxi

x1 = f(x0) + x0

df = Abs(f(x1) - f(x0))

Debug.Print "i=" & i & " x= " & x1 & " f(x)= " & f(x1)

If Abs(x1 - x0) < ex And df < ey Then

Debug.Print " Корень найден за " & i & " итераций"

Debug.Print " x= " & x1 & " f(x)= " & f(x1)

Debug.Print " Конец итераций"

Exit Sub

End If

x0 = x1

Next i

Debug.Print "Решение не найдено за", maxi, "итераций"

End Sub

Function f0(x)

f = 2*x - Exp(x)

End Function

Function f(x)

f = f0(x)+x

End Function

Результаты работы программы на VBA для функции , начального значения x₀ = 1.1:

i=1 x= 1,39583397605357 f(x)= 0,149160879773209

i=2 x= 1,54499485582678 f(x)= -5,29629438655936E-02

i=3 x= 1,49203191196118 f(x)= 2,99752635717079E-02

i=4 x= 1,52200717553289 f(x)= -0,01539014343569

i=5 x= 1,5066170320972 f(x)= 8,40821312260687E-03

i=6 x= 1,51502524521981 f(x)= -4,46024377229914E-03

i=7 x= 1,51056500144751 f(x)= 2,40587791438962E-03

i=8 x= 1,5129708793619 f(x)= -1,28652386385397E-03

i=9 x= 1,51168435549804 f(x)= 6,91223382955464E-04

i=10 x= 1,512375578881 f(x)= -3,70446886386766E-04

i=11 x= 1,51200513199461 f(x)= 1,98802854120217E-04

i=12 x= 1,51220393484873 f(x)= -1,06611507514565E-04

i=13 x= 1,51209732334122 f(x)= 5,71945781615568E-05

i=14 x= 1,51215451791938 f(x)= -3,06771414297913E-05

Корень найден за 14 итераций

x= 1,51215451791938 f(x)= -3,06771414297913E-05