Главная Учебники - Разные Лекции (разные) - часть 33
Введение 1. Постановка задачи 2. Математические и алгоритмические основы решения задачи 2.1 Описание метода 2.2 Недостатки метода 3. Функциональные модели и блок-схемы решения задачи 4. Программная реализация решения задачи 5. Пример выполнения программы Заключение Список использованных источников и литературы ВВЕДЕНИЕ Метод Ньютона (также известный как метод касательных)— это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Метод был описан Исааком Ньютоном в рукописи Deanalysiperaequationesnumeroterminoruminfinitas (лат.Об анализе уравнениями бесконечных рядов), адресованной в 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. Требуется найти корень уравнения Производная функции Возьмем за начальную точку Таким образом, корень уравнения Пример 2. Найдем корень уравнения функции методом Ньютона cosx = x3
. Эта задача может быть представлена как задача нахождения нуля функции f(x) = cosx − x3
. Имеем выражение для производной Так как Таким образом, корень уравнения функции cosx = x3
равен 0.86547403. Пример 3. Требуется найти корень уравнения Производная функции Возьмем за начальную точку Таким образом, корень уравнения 2. Математические и алгоритмические основы решения задачи 2.1 Описание метода Пусть корень x уравнения то можно уточнить это значение по методу Ньютона. Положим где Следовательно, Внеся эту поправку в формулу (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.
|