Рефетека.ру / Информатика и програм-ие

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

СОДЕРЖАНИЕ


Введение

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, осью абсцисс и перпендикуляром, восстановленным из точки Нахождение корней уравнения методом Ньютона (ЛИСП-реализация).

Имеем


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


Так как угол  образован касательной и осью абсцисс, его тангенс численно равен величине производной, вычисленной в точке, соответствующей абсциссе точки касания, т.е.


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


Тогда


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


или для любого шага n


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


В качестве начальной точки Нахождение корней уравнения методом Ньютона (ЛИСП-реализация) можно принять либо один из концов отрезка [a, b], либо точку внутри этого интервала. В первом случае рекомендуется выбирать ту границу, где выполняется условие


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


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

В качестве простейших условий окончания процедуры уточнения корня рекомендуется выполнение условия

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


Как следует из последнего неравенства, требуется при расчете запоминать три значения аргумента Нахождение корней уравнения методом Ньютона (ЛИСП-реализация). В практических инженерных расчетах часто применяют сравнение аргументов на текущей и предыдущей итерациях:


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


При составлении программы решения уравнения методом Ньютона следует организовать многократный расчет приближений для корня . Если удается получить аналитическое выражение для производной, то ее вычисление, а также вычисление можно оформить в виде функций.


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 с.

Похожие работы:

  1. Нахождение корней уравнения методом простой итерации ...
  2. • Решение уравнений средствами Excel
  3. • Решение прикладных задач методом дихотомии
  4. • Применение языков программирования высокого уровня для ...
  5. • Применение языков программирования высокого уровня для ...
  6. • Экзаменационные билеты по численным методам за первый семестр ...
  7. • Разработка программного обеспечения для решения ...
  8. • Применение языков программирования высокого уровня для ...
  9. • Математическая модель метода главных компонент
  10. • Обработка результатов психологических тестов (ЛИСП ...
  11. • Языки и технологии программирования
  12. • Лисп-реализация алгоритма кодирования информации RSA
  13. • ЛИСП-реализация основных операций над базами данных
  14. • Поиск нулей функции. Итерационные методы
  15. • ЛИСП-реализация основных операций над нечеткими ...
  16. • ЛИСП-реализация основных способов вычисления ...
  17. • Лисп-реализация конечных автоматов
  18. • Лисп-реализация математических операций над ...
  19. • ЛИСП-реализация операций над матрицами
Рефетека ру refoteka@gmail.com