Рефераты
 

Нахождение корней уравнения методом Ньютона (ЛИСП-реализация)

Нахождение корней уравнения методом Ньютона (ЛИСП-реализация)

СОДЕРЖАНИЕ

Введение

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.716215;
  • 5.74015;
  • 3.401863;
  • -2.277028;
  • 1.085197;
  • 0.766033;
  • 0.739241.
  • Таким образом, корень уравнения
  • равен 0.739241.
  • Пример 2.
  • Найдем корень уравнения функции методом Ньютона
  • cosx = x3.
  • Эта задача может быть представлена как задача нахождения нуля функции
  • f(x) = cosx ? x3.
  • Имеем выражение для производной
  • .
  • Так как для всех x и x3 > 1 для x > 1, очевидно, что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение x0= 0.5, тогда:
  • 1.112141;
  • 0.90967;
  • 0.867263;
  • 0.865477;
  • 0.865474033111;
  • 0.865474033102.
  • Таким образом, корень уравнения функции
  • cosx = x3 равен 0.86547403.
  • Пример 3.
  • Требуется найти корень уравнения , с точностью .
  • Производная функции
  • равна .
  • Возьмем за начальную точку , тогда
  • -2.3;
  • -2.034615;
  • -2.000579;
  • -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 с.


© 2010 BANKS OF РЕФЕРАТ