рефератырефератырефератырефератырефератырефератырефератырефераты

рефераты, скачать реферат, современные рефераты, реферат на тему, рефераты бесплатно, банк рефератов, реферат культура, виды рефератов, бесплатные рефераты, экономический реферат

"САМЫЙ БОЛЬШОЙ БАНК РЕФЕРАТОВ"

Портал Рефератов

рефераты
рефераты
рефераты

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

СОДЕРЖАНИЕ

Введение

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