Нахождение корней уравнения методом Ньютона (ЛИСП-реализация)
Метод Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Возьмём нуль в качестве начального приближения. Первая итерация даст в качестве приближения единицу. В свою очередь… Читать ещё >
Нахождение корней уравнения методом Ньютона (ЛИСП-реализация) (реферат, курсовая, диплом, контрольная)
СОДЕРЖАНИЕ Введение
1. Постановка задачи
- 2. Математические и алгоритмические основы решения задачи
- 2.1 Описание метода
- 2.2 Недостатки метода
- 3. Функциональные модели и блок-схемы решения задачи
- 4. Программная реализация решения задачи
- 5. Пример выполнения программы
- Заключение
Список использованных источников
и литературы
- ВВЕДЕНИЕ
- Метод Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность.
- Метод был описан Исааком Ньютоном в рукописи De analysi per aequationes numero terminorum infinitas (лат.Об анализе уравнениями бесконечных рядов), адресованной в 1669 году Барроу, и в работе De metodis fluxionum et serierum infinitarum (лат.Метод флюксий и бесконечные ряды) или Geometria analytica (лат.Аналитическая геометрия) в собраниях трудов Ньютона, которая была написана в 1671 году. В своих работах Ньютон вводит такие понятия, как разложение функции в ряд, бесконечно малые и флюксии (производные в нынешнем понимании). Указанные работы были изданы значительно позднее: первая вышла в свет в 1711 году благодаря Уильяму Джонсону, вторая была издана Джоном Кользоном в 1736 году уже после смерти создателя. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения xn, а последовательность полиномов и в результате получал приближённое решение x.
- Впервые метод был опубликован в трактате Алгебра Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе Analysis aequationum universalis (лат.Общий анализ уравнений). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений xn вместо более трудной для понимания последовательности полиномов, использованной Ньютоном. Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.
- В 1879 году Артур Кэли в работе The Newton-Fourier imaginary problem (англ. Проблема комплексных чисел Ньютона-Фурье) был первым, кто отметил трудности в обобщении метода Ньютона на случай мнимых корней полиномов степени выше второй и комплексных начальных приближений. Эта работа открыла путь к изучению теории фракталов.
- Целью данной курсовой работы является Лисп — реализация нахождения корней уравнения методом Ньютона.
- 1. Постановка задачи
- Дано уравнение:
- .
- Требуется решить это уравнение, точнее, найти один из его корней (предполагается, что корень существует). Предполагается, что F (X) непрерывна и дифференцируема на отрезке [A;B].
- Входным параметром алгоритма, кроме функции F (X), является также начальное приближение — некоторое X0, от которого алгоритм начинает идти.
- Пусть уже вычислено Xi, вычислим Xi+1 следующим образом. Проведём касательную к графику функции F (X) в точке X = Xi, и найдём точку пересечения этой касательной с осью абсцисс. Xi+1 положим равным найденной точке, и повторим весь процесс с начала.
- Нетрудно получить следующее выражение:
- Xi+1 = Xi — F (Xi) / F'(Xi)
- Интуитивно ясно, что если функция F (X) достаточно «хорошая», а Xi находится достаточно близко от корня, то Xi+1 будет находиться ещё ближе к искомому корню.
- Пример 1.
- Требуется найти корень уравнения, с точностью .
- Производная функции равна
- .
- Возьмем за начальную точку, тогда
- -9.716 215;
- 5.74 015;
- 3.401 863;
- -2.277 028;
- 1.85 197;
- 0.766 033;
- 0.739 241.
- Таким образом, корень уравнения
- равен 0.739 241.
- Пример 2.
- Найдем корень уравнения функции методом Ньютона
- cosx = x3.
- Эта задача может быть представлена как задача нахождения нуля функции
- f (x) = cosx? x3.
- Имеем выражение для производной
- .
- Так как для всех x и x3 > 1 для x > 1, очевидно, что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение x0= 0.5, тогда:
- 1.112 141;
- 0.90 967;
- 0.867 263;
- 0.865 477;
- 0.865 474 033 111;
- 0.865 474 033 102.
- Таким образом, корень уравнения функции
- cosx = x3 равен 0.86 547 403.
- Пример 3.
- Требуется найти корень уравнения, с точностью .
- Производная функции
- равна .
- Возьмем за начальную точку, тогда
- -2.3;
- -2.34 615;
- -2.579;
- -2.0.
- Таким образом, корень уравнения
- равен -2.
- 2. Математические и алгоритмические основы решения задачи
- 2.1 Описание метода
- Пусть корень x уравнения отделен на отрезке [a, b], причем и непрерывны и сохраняют определенные знаки при. Если на некотором произвольном шаге n найдено приближенное значение корня
- ,
- то можно уточнить это значение по методу Ньютона. Положим
- , (1)
- где считаем малой величиной. Применяя формулу Тейлора, получим:
- .
- Следовательно,
- .
- Внеся эту поправку в формулу (1), найдем следующее (по порядку) приближение корня
- . (2)
- Геометрически метод Ньютона эквивалентен замене дуги кривой касательной, проведенной в некоторой точке кривой. В самом деле, положим для определенности, что при и (рисунок 1).
- Выберем, например,, для которого. Проведем касательную к кривой в точке B0 с координатами .
- Рисунок 1. Геометрически показан метод Ньютона
- В качестве первого приближения корня x возьмем абсциссу точки пересечения касательной с осью Ox. Через точку снова проведем касательную, абсцисса точки пересечения которой даст второе приближение корня x и т. д.
- Формулу для уточнения корня можно получить из прямоугольного треугольника, образованного касательной, проведенной в точке B0, осью абсцисс и перпендикуляром, восстановленным из точки .
- Имеем
- .
- Так как угол a образован касательной и осью абсцисс, его тангенс численно равен величине производной, вычисленной в точке, соответствующей абсциссе точки касания, т. е.
- .
- Тогда
- или для любого шага n
- .
- В качестве начальной точки можно принять либо один из концов отрезка [a, b], либо точку внутри этого интервала. В первом случае рекомендуется выбирать ту границу, где выполняется условие
- ,
- т.е. функция и ее вторая производная в точке должны быть одного знака.
- В качестве простейших условий окончания процедуры уточнения корня рекомендуется выполнение условия
- .
- Как следует из последнего неравенства, требуется при расчете запоминать три значения аргумента. В практических инженерных расчетах часто применяют сравнение аргументов на текущей и предыдущей итерациях:
- .
- При составлении программы решения уравнения методом Ньютона следует организовать многократный расчет приближений для корня 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
- (DEFUN F (X)
- (- (COS X) (* X X X))
- )
- ;ПРОИЗВОДНАЯ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 — Выходные данные.
ЗАКЛЮЧЕНИЕ
Проблема повышения качества вычислений, как несоответствие между желаемым и действительным, существует и будет существовать в дальнейшем. Ее решению будет содействовать развитие информационных технологий, которое заключается как в совершенствовании методов организации информационных процессов, так и их реализации с помощью конкретных инструментов — сред и языков программирования.
Итогом работы можно считать созданную функциональную модель нахождения корней уравнения методом Ньютона. Данная модель может быть использована для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства. Созданная функциональная модель и ее программная реализация могут служить органической частью решения более сложных задач.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ и литературы
Бронштейн, И. Н. Справочник по математике для инженеров и учащихся втузов [Текст] / И. Н. Бронштейн, К. А. Семендяев. — М.: Наука, 2007. — 708 с.
Кремер, Н. Ш. Высшая математика для экономистов: учебник для студентов вузов. [Текст] / Н. Ш. Кремер, 3-е издание — М.:ЮНИТИ-ДАНА, 2006. C. 412.
Калиткин, Н. Н. Численные методы. [Электронный ресурс] / Н. Н. Калиткин. — М.: Питер, 2001. С. 504.
Метод Ньютона — Википедия [Электронный ресурс] - Режим доступа: http://ru.wikipedia.org/wiki/Метод_Ньютона
Семакин, И. Г. Основы программирования. [Текст] / И. Г. Семакин, А. П. Шестаков. — М.: Мир, 2006. C. 346.
Симанков, В. С. Основы функционального программирования [Текст] / В. С. Симанков, Т. Т. Зангиев, И. В. Зайцев. — Краснодар: КубГТУ, 2002. — 160 с.
Степанов, П. А. Функциональное программирование на языке Lisp. [Электронный ресурс] / П. А. Степанов, А. В. Бржезовский. — М.: ГУАП, 2003. С. 79.
Хювенен Э. Мир Лиспа [Текст] / Э. Хювенен, Й.Сеппянен. — М.: Мир, 1990. — 460 с.