Метод Ньютона (метод касательных).
Пусть корень уравнения f(x) = 0 отделен на отрезке [a, b], причем f′ (x) и f″(x) непрерывны и сохраняют постоянные знаки на всем отрезке [a, b].
Геометрический смысл метода Ньютона состоит в том, что малый отрезок дуги кривой y = f(x) заменяется касательной к этой кривой (отсюда и название метод касательных).
Пусть f(a) < 0, f(b) > 0, f′(x) > 0, f″(x) > 0 (рис. 1) или f(a) > 0, f(b) < 0, f′(x) < 0, f″(x) < 0 (рис. 2). Проведем касательную к кривой y = f(x) в точке В0 (b, f(b). Уравнение касательной имеет вид
y – f(b) = f′(b) (x – b)
y
y
B0
A
В1 f(b)
f(a)
ξ
b=x0 x3 x2 x1
x
0
a x2
x1
x a
ξ b = x0
B
f(a) B2 f(b)
A В1 B0
Рис. 1 Рис.2
Найдем абсциссу точки пересечения касательной с осью Ox.. Полагая у = 0, x = x1, получим
Далее корень уравнения находится на отрезке [a, x1]. Применяя снова метод Ньютона, проведем касательную к кривой в точке В1(x, f(x1)). Аналогично предыдущему, находим абсциссу точки пересечения касательной с осью Ох
Продолжая этот процесс, получим
(*)
Получаем последовательность приближенных значений x1, x2, … xn … корня уравнения f(x) = 0. Эта последовательность монотонно убывающая. Докажем, что она ограничена снизу.
Для функции f(x) запишем формулу Тейлора в окрестности точки x = xn..
Если k = 1, то формула принимает вид
Полагая x = ξ и учитывая, что f(ξ) = 0 и f″(x) > 0. имеем
Т.е. последовательность x1,
x2, …, xn,
… имеет предел.
Переходя
к пределу в равенстве (*), получим
Таким образом, при n → ∞ последовательность чисел {xn} стремится к пределу, равному корню уравнения f(x) = 0.
Предположим,
далее, что f″(x)
> 0 на интервале (a, b).
Остальные предположения оставим без
изменения.
y B
f(b)
x1
N a b x
f(a)
A Рис. 3
Если снова провести касательную в точке В, то она пересечет ось абсцисс в точке, не принадлежащей отрезку [a, b]. Поэтому при таком выборе начальной точки х0 следующая точка х1 выйдет за пределы отрезка [a, b], и метод Ньютона окажется непрактичным. Таким образом, при выборе начальной точки следует руководствоваться правилом.
За исходную точку х0 следует выбирать тот конец промежутка [a, b], в котором знак функции совпадает со знаком второй производной, т.е. f(x0) ∙ f″(x0) > 0.
Для оценки погрешности приближенного значения корня х n запишем формулу Лагранжа.
Пусть |f′(x)| ≥ m1 на промежутке [a, b] ( m1 – наименьшее значение модуля производной на рассматриваемом интервале). Тогда
Блок-схема программы нахождения корня уравнения f(x) = 0 методом Ньютона имеет вид
Пусть x - начальное приближение корня,
Е – точность вычисления, mt – наименьшее значение f′(x) на отрезке [a, b],
n
– счетчик количества итераций
Ввод
x, E, mt
n
= 0
n
= n +1
t = f(x)/f′(x)
x = x - t
нет f2 = f(x)
Вывод
n, x, f(x)
Да
Вывод
n, x,f(x)
П р и м е р. Найти корень уравнения 1 – 3x + cosx = 0 методом Ньютона с точностью
Е = 10-4.
Ранее было выяснено, что корень уравнения находится на интервале [-1, 1].
f(x) = 1 – 3x + cosx. f′(x) = −3 – sin x. Наименьшее значение производной mt равно -4 ,
f″(x) = -cos x < 0 на интервале[ -1, 1], f (1) = - 2 + cos 1 < 0. За начальную точку х берем х = 1.
Программа на языке QBASIC имеет вид:
x = 1
E = .0001
mt = 4
n = 0
n1: n = n + 1
t = (1 - 3 * x + cos(x)) / (-3 - sin(x))
x = x - t
f2 = 1 - 3 * x + cos(x)
write x, n, f2
if abs(f2) / mt < E then write x, "root", f2, e: stop
goto n1
end
Результат, данный программой, имеет вид х = .6071206 - root.