таких что f(ai).f(bi) 0, где i=1,2,…,n. При этом длина каждого последующего отрезка вдвое меньше длины предыдущего. Тогда последовательное сужение отрезка вокруг неизвестного значения корня ξнанекотором шаге nобеспечивает выполнение неравенства bn - an ,
которое и является условием выхода из цикла.Очевидно, |
что с точностью ε |
|||
любое x [an;bn ] может быть принято за |
приближенное |
значение корня. |
||
Обычно выбирают середину отрезка x |
a |
b |
. |
|
n |
n |
|
||
|
|
|
||
|
|
2 |
|
|
2.1.2. Метод итераций
Алгоритм процедуры, реализующей решение нелинейного уравнения методом итераций, представлен на рис. 2.1-2. Его использование требует дополнения двух процедур-функций: fi(x)–итерирующая функция и f(x)– левая часть исходного уравнения.
Рис.2.1-3. Алгоритм метода итераций
14
Метод итераций предполагает замену уравнения f(x)=0 равносильным уравнением x= (x) [3].Функция (x) называется итерирующей функцией. Если корень уравнения отделен на отрезке [a;b], то исходя из начального приближения x0 [a;b], получают последовательность приближений к корню:
x1 = (x0), x2 = (x1), …, xn= (xn-1).
Условие сходимости метода итераций определяется теоремой:
Если все члены последовательности xn= (xn-1) [a;b]и существует такое q (0<q<1), что для всех х [a; b] выполняется условие | ’(x)| = q<1,то эта последовательность является сходящейся, а процесс итерации сходится к корню уравнения независимо от выбора начального приближения.
2.1.3. Метод Ньютона
Алгоритм процедуры, |
реализующей |
решение нелинейного уравнения |
||||
методом |
Ньютона, |
представлен |
на |
рис. 2.1-3. Корень нелинейного |
||
уравнения |
f (x) 0 |
должен быть отделен на отрезке [a;b], причем первая и |
||||
|
||||||
вторая производные ( f |
|
|
непрерывны и знакопостоянны при х |
|||
( x) |
и f ( x) ) |
|||||
[a;b].
Использование алгоритма требует двух процедур-функций: f(x)–левая часть исходного уравнения и f1(x)– производная от f(x).
Все последующие приближения к корню получаются с использованием итерационной формулы [3]
x |
i 1 |
x |
n |
|
|
|
|
f ( x |
n |
) |
|
|
|
||
f ( x |
i |
) |
|
|
|
|
|
,
где i = 0, 1, …n-1.
|
В качестве |
|
начального приближения к корню выбирают точку |
||||||||||||
х0 [a;b], где |
f (x |
0 |
) |
|
f (x) 0 |
. |
|||||||||
|
|
|
|
|
|
|
|
|
|||||||
|
Процесс вычислений прекращается, если |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
xn 1 xn |
|
|
|
|
2m1 |
, |
|
|
|
|||||
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
M 2 |
|
|
|
|
|
||
|
где |
ε - заданная точность; |
|||||||||||||
|
m1 - |
наименьшее значение f '(x ) при x [a; b]; |
|||||||||||||
|
M2 - |
наибольшее значение f "(x ) при x [a; b]. |
|||||||||||||
|
Для оценки полгрешности также используются следующих выражений: |
||||||||||||||
|
|
|
|
x |
|
x |
|
|
f(x |
) |
, |
|
|||
|
|
|
|
|
|
|
n |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n 1 |
|
|
|
n |
|
|
m |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
xn 1 xn 
ε.
15
nut(x,E,m1,xn,n)
функция f(x)
функция f’(x)
n = 0
n = n+1
|
t = f(x)/f ’(x) |
|
|
x = x-t |
|
|
f2 = f(x) |
|
|
Вывод |
|
|
n, x, f(x) |
|
Не |
|f2| |
|
< E |
||
|
||
|
m1 |
|
|
Да |
|
|
xn = x |
Конец
Входные параметры x – начальное приближение Е – точность вычислений м1 - наименьшее значение |f’(x)| на отрезке [a,b] Выходной параметр xn – корень уравнения n – количество итераций
Рис.2.1-3. Алгоритм метода Ньютона
2.1.4. Метод хорд
Схема алгоритма процедуры, реализующей метод хорд, представленная на рис. 2.1.4.-1, требует дополнения процедуры-функции f(x), в которой вычисляется левая часть уравнения.
16
Рис.2.1-4. Алгоритм метода хорд Корень нелинейного уравнения f (x) 0 должен
отрезке [a;b], причем первая и вторая производные
непрерывны и знакопостоянны при х [a;b]. Рекурентная формула метода хорд [3]:
быть отделен на
( |
f ( x) |
и |
f ( x) |
) |
|
|
|
|
|
f(xn ) |
|
|
|
где |
|
|
|
|
|
|
|
|||
xn 1 xn |
|
|
(x xn ), |
|||||
|
|
|
||||||
|
|
|
||||||
f(x) f(xn ) |
||||||||
|
|
|
|
|
||||
x
- неподвижная точка.
Неподвижен тот конец отрезка [a;b], для которого знак функции f(x) совпадает со знаком ее второй производной. Тогда второй конец отрезка можно принять за начальное приближение к корню, то есть точку х0.
Оценка погрешности метода хорд можно определить одним из выражениями:
xn xn 1 |
|
ε m |
или |
f(xn ) |
ε. |
1 |
|
||||
|
|
M1 m1 |
|
m1 |
|
17