Приближенное решение алгебраических и трансцендентных уравнений Метод Ньютона (стр. 4 из 4)

Погрешность

Имеются две разновидности применения формулы (1). Первая разновидность: вычисления ведутся непосредственно по формуле (1) при

, начиная с двух приближений x0 и x1, взятых, по возможности, поближе к корню x * . При этом не предполагается, что x * лежит между x0 и x1 (и что значения функции f в точках x0 и x1 имеют разные знаки). При этом не гарантируется, что корень попадёт на отрезок между xi − 1 и xi на каком-либо следующем шаге (хотя это и исключено). В таком случае затруднительно дать оценку погрешности, с которой xi + 1 приближает истинное значение корня x * , и поэтому довольствуются таким эмпирическим правилом: вычисления прекращают, когда будет выполнено неравенство , где - желаемая точность нахождения корня. При этом полагают приближённое значение корня равным .

Условие сходимости

Достаточное условие сходимости, таково:

Это неравенство может быть переписано в виде откуда получаем, что сходимость гарантируется, когда, во-первых, так как (тем самым проясняется смысл выбора знака числа ), а во-вторых, когда при всех X на всём рассматриваемом отрезке, окружающем корень. Это второе неравенство заведомо выполнено, если

где

. Таким образом, угловой коэффициент K не должен быть слишком мал по абсолютной величине: при малом угловом коэффициенте уже на первом шаге точка X[1] может выскочить из рассматриваемой окрестности корня X[*] , и сходимость итераций к корню может быть нарушена.

Метод половинного деления

Снова предположим, что корень отделён на отрезке

и знаки и различны (функция меняет знак при переходе через корень ).

Положим

и и вычислим значения функции в левом конце отрезка, , и в его середине ; . Сравним знаки чисел и . Если эти знаки различны, то корень лежит в интервале ; если же одинаковы, то тогда различны знаки и , и корень лежит в интервале . (Возможен ещё случай ; тогда корень уже найден.) В обоих случаях смены знака корень оказывается отделён на отрезке либо , длина которого ровно в два раза меньше длины исходного отрезка . Обозначим этот отрезок половинной длины через (то есть положим в случае, когда и разных знаков, и в случае, когда и одного знака).

Далее повторим процесс для отрезка

: снова отыщем его середину , найдём значение функции и сравним знак этого числа со знаком ; если знаки разные, то корень отделён на , если одинаковые, то на (или же оказывается, что ; тогда корень найден). Длина отрезка, на котором отделён корень, уменьшилась ещё в два раза.

Рис 4. Последовательное деление отрезка пополам и приближение к корню

Поступая тем же образом и далее, получаем, что после

делений длина отрезка, на котором лежит корень, сокращается в раз и становится равной (если корень не был точно определён на каком-то предыдущем этапе, то есть не совпал с при некотором ).

Погрешность

Пусть

- заданная точность, с которой требуется отыскать корень. Процесс деления отрезков следует остановить, как только станет верным неравенство . Очевидно, что если при этом положить

то расстояние от корня

, лежащего где-то в интервале , до середины этого интервала будет не больше , то есть приближённое равенство будет выполнено с нужной точностью. C увеличением точности заметно возрастает объем вычислительной работы, поэтому метод удобно применять для нахождения грубого корня уравнения.

Метод легко реализуется на ЭВМ.

Пример решения уравнения методом Ньютона

Уравнение:

, .

f(0)=1

f’’(0)=1

Следовательно, при x=1 f(x)f’’(x)>0. Начальное приближение x0=0.

f’(x)=

f’(x)

0 при

n	xn	f(xn)	f'(xn)	hn
0	0	1	3	-0,333333333
1	-0,333333333	0,062142078	2,606445364	-0,023841696
2	-0,357175029	0,000392296	2,573426701	-0,000152441
3	-0,357327470	1,63265E-08	2,573213436	-6,34481E-09
4	-0,357327477	2,9976E-15	2,573213427	-1,16493E-15
5	-0,357327477	0	2,573213427	0

Вывод: в третьем приближении получен результат с 4-мя точными знаками после запятой:

.

Ответ:

Список литературы

· «Основы вычислительной математики», Б. П. Демидович, И.А. Марон, 1966г.

· Материалы электронной библиотеки http://elib.ispu.ru/