Метод Ньютона для решения нелинейных уравнений (стр. 2 из 3)
Процесс деления отрезка проводится до тех пор, пока длина текущего интервала неопределённости не будет меньше заданной точности, то есть
вк – ак < E. Тогда в качестве приближенного решения уравнения будет точка, соответствующая середине интервала неопределённости.
4). Метод хорд. Идея метода состоит в том, что на отрезке [a,b] строится хорда стягивающая концы дуги графика функции y=f(x), а точка c, пересечения хорды с осью абсцисс, считается приближенным значением корня
c = a - (f(a)Ч (a-b)) / (f(a) - f(b)),
c = b - (f(b)Ч (a-b)) / (f(a) - f(b)).
Следующее приближение ищется на интервале [a,c] или [c,b] в зависимости от знаков значений функции в точках a,b,c
x* О [c,b] , если f(с)Ч f(а) > 0 ;
x* О [a,c] , если f(c)Ч f(b) < 0 .
Если f'(x) не меняет знак на [a,b], то обозначая c=x1 и считая начальным приближением a или b получим итерационные формулы метода хорд с закрепленной правой или левой точкой.
x0=a, xi+1 = xi - f(xi)(b-xi) / (f(b)-f(xi), при f '(x)Ч f "(x) > 0 ;
x0=b, xi+1 = xi - f(xi)(xi-a) / (f(xi)-f(a), при f '(x)Ч f "(x) < 0 .
Сходимость метода хорд линейная.
1.2 Алгоритм метода Ньютона
Построим эффективный алгоритм вычисления корней уравнения. Пусть задано начальное приближение
. Вычислим в этой точке значение функции 
и её производной 
. Рассмотрим графическую иллюстрацию метода: 
.Далее получим следующее приближение в точке
, проводя касательную из точки ( 
) до пересечения с осью абсцисс:
(8)Продолжая этот процесс, получим известную формулу Ньютона:
(9)y
xРис. 1.
Приведем простейшую рекурсивную подпрограмму-функцию:
function X_Newt(x,eps:real):real;
var y:real;
begin
y:=x-f(x)/f1(x);
if abs(f(x)) > eps
then X_Newt:=X_Newt(y,eps)
else X_Newt:=y
end;
Метод Ньютона (касательных) характеризуется квадратичной скоростью сходимости, т.е. на каждой итерации удваивается число верных знаков. Однако этот метод не всегда приводит к нужному результату. Рассмотрим этот вопрос подробнее.
Преобразуем уравнение (1) к эквивалентному уравнению вида:
x=g(x) (10)
В случае метода касательных
. Если известно начальное приближение к корню x=x0, то следующее приближение найдем из уравнения x1=g(x0), далее x2=g(x1),... Продолжая этот процесс, получим рекуррентную формулу метода простой итерацииxk+1=g(xk) (11)
Итерационный процесс продолжается до тех пор, пока не будут выполнены условия (5-7).
Всегда ли описанный вычислительный процесс приводит к искомому решению? При каких условиях он будет сходящимся? Для ответа на эти вопросы опять обратимся к геометрической иллюстрации метода.
Корень уравнения представляется точкой пересечения функций y=x и y=g(x). Как видно из рис. 3(а), если выполняется условие
, то процесс сходится, иначе – расходится (рис3(б)).
(a) (б)
Рис. 3.
Итак, для того чтобы итерационный процесс был сходящимся и приводил к искомому результату, требуется выполнение условия:
(12)Переход от уравнения f(x)=0 к уравнению х=g(x) можно осуществлять различными способами. При этом важно, чтобы выбранная функция g(x) удовлетворяла условию (12). К примеру, если функцию f(x) умножить на произвольную константу q и добавить к обеим частям уравнения (1) переменную х, то g(x)=q*f(x)+x . Выберем константу q такой, чтобы скорость сходимости алгоритма была самой высокой. Если 1<g’(x)<0, то сходимость итерационного процесса будет двусторонней. Производная по х от этой функции: g’(x)=1+q*f’(x). Наибольшую сходимость получим при g’(x)=0, тогда q= - 1/f’(x) и формула (11) переходит в формулу Ньютона (9).
Метод Ньютона обладает высокой скоростью сходимости, однако он не всегда сходится. Условие сходимости
, где g(x) = x – f(x)/ f’(x), сводится к требованию 
.В практических расчетах важно выбирать начальное значение
как можно ближе к искомому значению, а в программе устанавливать «предохранитель от зацикливания».Недостатком метода является и то, что на каждом шаге необходимо вычислять не только функцию, но и ее производную. Это не всегда удобно. Одна из модификаций метода Ньютона - вычисление производной только на первой итерации:
(13)Другой метод модификации – замена производной конечной разностью
(14)Тогда
(15)Геометрический смысл такого изменения алгоритма Ньютона состоит в том, что от касательной мы приходим к секущей. Метод секущих уступает методу Ньютона в скорости сходимости, но не требует вычисления производной. Заметим, что начальные приближения в методе секущих могут располагаться как с разных сторон от корня, так и с одной стороны.
Запишем в общем виде алгоритм метода Ньютона.
1. Задать начальное приближение х(0) так, чтобы выполнилось условие
f(x(0))*f’’(x(0))>0. (16)
Задать малое положительное число ε , как точность вычислений. Положить к = 0.
2. Вычислить х(к+1) по формуле (9) :
.3. Если | x(k+1) - x(k) | < ε, то процесс вычисления прекратить и положить х* = x(k+1). Иначе увеличить к на 1 (к = к + 1) и перейти к пункту 2.
Решим вручную несколько нелинейных уравнений методом Ньютона, а потом сверим результаты с теми, которые получатся при реализации программного продукта.
Пример 1
Решить уравнение методом Ньютона.
sin x2 + cosx2 - 10x. = 0.
Вычисления производить с точностью ε = 0, 001.
Решение:
Вычислим первую производную функции.
F’(x)=2x cosx2 - 2x sinx2 - 10.
Теперь вычислим вторую производную от функции.
F’’(x)=2cosx2 - 4x2sinx2 - 2sinx2 - 4x2cosx2 = cosx2 (2-4x2 ) - sinx2 (2+4x2).
Построим приближённый график данной функции.
Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x(0)) * f’’(x(0)) > 0.
Пусть x(0) = 0, 565, тогда f(0. 565)*f’’(0. 565) = -4. 387 * (-0. 342) = 1. 5 > 0,
Условие выполняется, значит берём x(0) = 0, 565.
Теперь составим таблицу значений, для решения данного уравнения.
| k | x(k) | f(x(k)) | f’(x(k)) | | x(k+1) - x(k) | |
| 0 | 0. 565 | -4. 387 | -9. 982 | 0. 473 |
| 1 | 0. 092 | 0. 088 | -9. 818 | 0. 009 |
| 2 | 0. 101 | 0. 000 | -9. 800 | 0. 000 |
| 3 | 0. 101 |
Отсюда следует, что корень уравнения х = 0, 101.
Пример 2
Решить уравнение методом Ньютона.
cos x – e-x2/2 + x - 1 = 0
Вычисления производить с точностью ε = 0, 001.
Решение:
Вычислим первую производную функции.
F’(x) = 1 – sin x + x*e-x2/2.
Теперь вычислим вторую производную от функции.
F’’(x) = e-x2/2 *(1-x2) – cos x.
Построим приближённый график данной функции.
Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x(0)) * f’’(x(0)) > 0.
Пусть x(0) = 2, тогда f(2)*f’’(2) = 0. 449 * 0. 010 = 0.05 > 0,
Условие выполняется, значит берём x(0) = 2.
Теперь составим таблицу значений, для решения данного уравнения.
| k | x(k) | f(x(k)) | f’(x(k)) | | x(k+1) - x(k) | |
| 0 | 2 | 0. 449 | 0. 361 | 1. 241 |
| 1 | -0. 265 | 0. 881 | 0. 881 | 0. 301 |
| 2 | -0. 021 | 0. 732 | 0. 732 | 0. 029 |
| 3 | 0. 000 | 0. 716 | 0. 716 | 0. 000 |
| 4 | 1. 089 |
Отсюда следует, что корень уравнения х = 1. 089.
Пример 3
Решить уравнение методом Ньютона.
x2 - e-x = 0.
Вычисления производить с точностью ε = 0, 001.
Решение:
Вычислим первую производную функции.
F’(x) = 2*x + e-x.
Теперь вычислим вторую производную от функции.
F’’(x) = 2 - e-x.
Построим приближённый график данной функции.