Следовательно,
Внеся эту поправку в формулу (1), найдем следующее (по порядку) приближение корня
Геометрически метод Ньютона эквивалентен замене дуги кривой
Выберем, например,
Рисунок 1. Геометрически показан метод Ньютона
В качестве первого приближения
Формулу для уточнения корня можно получить из прямоугольного треугольника
Имеем
Так как угол a образован касательной и осью абсцисс, его тангенс численно равен величине производной, вычисленной в точке, соответствующей абсциссе точки касания, т.е.
Тогда
или для любого шага n
В качестве начальной точки
т.е. функция и ее вторая производная в точке
В качестве простейших условий окончания процедуры уточнения корня рекомендуется выполнение условия
Как следует из последнего неравенства, требуется при расчете запоминать три значения аргумента
При составлении программы решения уравнения методом Ньютона следует организовать многократный расчет приближений для корня x. Если удается получить аналитическое выражение для производной, то ее вычисление, а также вычисление можно оформить в виде функций.
2.2 Недостатки метода
Пусть
Тогда
Возьмём нуль в качестве начального приближения. Первая итерация даст в качестве приближения единицу. В свою очередь, вторая снова даст нуль. Метод зациклится, и решение не будет найдено. В общем случае построение последовательности приближений может быть очень запутанным.
Рисунок 2. Иллюстрация расхождения метода Ньютона, примененного к функции
Если производная не непрерывна в точке корня, то метод может расходиться в любой окрестности корня.
Если не существует вторая производная в точке корня, то скорость сходимости метода может быть заметно снижена.
Если производная в точке корня равна нулю, то скорость сходимости не будет квадратичной, а сам метод может преждевременно прекратить поиск, и дать неверное для заданной точности приближение.
Пусть
Тогда
3. Функциональные модели и блок-схемы решения задачи
Функциональные модели и блок-схемы решения задачи представлены на рисунке 3, 4.
Условные обозначения:
·FUNCTN, FX – функция;
·DFUNCTN, DFDX – производная функции;
·A – рабочая переменная;
·START, X0 – начальное значение;
·PRES, E –точность вычисления.
Рисунок 3 – Функциональная модель решения задачи для поиска корня уравнения методом Ньютона
Рисунок 4 – Блок-схема решения задачи для функции NEWTOM
4. Программная реализация решения задачи
Файл FUNCTION.txt (Пример 1)
;ФУНКЦИЯ COSX - X3
(DEFUNF(X)
(- (COSX) (* XXX))
)
;ПРОИЗВОДНАЯ -sinx-3x2
(DEFUN DFDX (X)
(- (* -1 (SIN X)) (* 3 X X))
)
(SETQ X0 0.5)
(SETQ E 0.0001)
Файл FUNCTION.txt (Пример 2)
;ФУНКЦИЯ x-cosx
(DEFUN F(X)
(- X (COS X))
)
;ПРОИЗВОДНАЯ 1+sinx
(DEFUN DFDX (X)
(+ 1 (SIN X))
)
(SETQ X0 -1)
(SETQ E 0.0001)
Файл FUNCTION.txt (Пример 3)
;ФУНКЦИЯ X2+2X
(DEFUN F(X)
(+ (* X X) (* 2 X))
)
;ПРОИЗВОДНАЯ 2X+2
(DEFUN DFDX (X)
(+ 2 (* 2 X))
)
(SETQ X0 -2.3)
(SETQ E 0.0001)
Файл NEWTON.txt
;ПОДГРУЖАЕМФУНКЦИЮ
(LOAD "D:\FUNCTION.TXT" )
;РЕАЛИЗАЦИЯМЕТОДАНЬЮТОНА
(DEFUN NEWTOM (START PRES FUNCTN DFUNCTN)
;ОБЪЯВЛЕНИЕ ПЕРЕМЕННЫХ
(DECLARE (SPECIAL X))
(DECLARE (SPECIAL A))
;ЗАДАЕМ НАЧАЛЬНОЕ ЗНАЧЕНИЕ
(SETQ X START)
(SETQ A (/ (FUNCALL FUNCTN X) (FUNCALL DFUNCTN X)))
(LOOP
(SETQ X (- X A))
(SETQ A (/ (FUNCALL FUNCTN X) (FUNCALL DFUNCTN X)))
;ЕСЛИ ДОСТИГЛИ ТРЕБУЕМОЙ ТОЧНОСТИ ВЫХОДИМ ИЗ ЦИКЛА
(IF (<= (ABS A) PRES) (RETURN X))
)
)
;ОТКРЫВАЕМФАЙЛ
(SETQ OUTPUT_STREAM (OPEN "D:\KOREN.TXT" :DIRECTION :OUTPUT))
;ВЫЗЫВАЕМ МЕТОД НЬЮТОНА ДЛЯ РАСЧЕТА КОРНЯ
(SETQ KOREN (NEWTOM X0 E (FUNCTION F) (FUNCTION DFDX)))
;ВЫВОДИМКОРЕНЬВФАЙЛ
(PRINT 'KOREN OUTPUT_STREAM)
(PRINT KOREN OUTPUT_STREAM)
;ЗАКРЫВАЕМФАЙЛ
(TERPRI OUTPUT_STREAM)
(CLOSE OUTPUT_STREAM)
5. Пример выполнения программы
Пример 1.
Рисунок 5 – Входные данные.
Рисунок 6 – Выходные данные.
Пример 2.
Рисунок 7 – Входные данные.
Рисунок 8 – Выходные данные.
Пример 3.
Рисунок 9 – Входные данные.
Рисунок 10 – Выходные данные.
ЗАКЛЮЧЕНИЕ
Проблема повышения качества вычислений, как несоответствие между желаемым и действительным, существует и будет существовать в дальнейшем. Ее решению будет содействовать развитие информационных технологий, которое заключается как в совершенствовании методов организации информационных процессов, так и их реализации с помощью конкретных инструментов – сред и языков программирования.
Итогом работы можно считать созданную функциональную модель нахождения корней уравнения методом Ньютона. Данная модель может быть использована для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства. Созданная функциональная модель и ее программная реализация могут служить органической частью решения более сложных задач.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ и литературы
1. Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов [Текст] / И.Н.Бронштейн, К.А.Семендяев. – М.: Наука, 2007. – 708 с.
2. Кремер, Н.Ш. Высшая математика для экономистов: учебник для студентов вузов. [Текст] / Н.Ш.Кремер, 3-е издание – М.:ЮНИТИ-ДАНА, 2006. C. 412.
3. Калиткин, Н.Н. Численные методы. [Электронный ресурс] / Н.Н. Калиткин. – М.: Питер, 2001. С. 504.
4. Метод Ньютона – Википедия [Электронный ресурс] – Режим доступа: http://ru.wikipedia.org/wiki/Метод_Ньютона
5. Семакин, И.Г. Основы программирования. [Текст] / И.Г.Семакин, А.П.Шестаков. – М.: Мир, 2006. C. 346.
6. Симанков, В.С. Основы функционального программирования [Текст] / В.С.Симанков, Т.Т.Зангиев, И.В.Зайцев. – Краснодар: КубГТУ, 2002. – 160 с.
7. Степанов, П.А. Функциональное программирование на языке Lisp. [Электронный ресурс] / П.А.Степанов, А.В. Бржезовский. – М.: ГУАП, 2003. С. 79.
8. Хювенен Э. Мир Лиспа [Текст] / Э.Хювенен, Й.Сеппянен. – М.: Мир, 1990. – 460 с.