/>СОДЕРЖАНИЕ
Введение
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 (лат.Метод флюксий и бесконечныеряды) или Geometriaanalytica (лат.Аналитическаягеометрия) в собранияхтрудов Ньютона, которая была написана в 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
(DEFUNDFDX (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 (
)
)
; ОТКРЫВАЕМ ФАЙЛ
(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)
(CLOSEOUTPUT_STREAM)
5. Пример выполненияпрограммы
Пример 1.
/>
Рисунок 5 – Входныеданные.
/>
Рисунок 6 – Выходныеданные.
Пример 2.
/>
Рисунок 7 – Входныеданные.
/>
Рисунок 8 – Выходныеданные.
Пример 3.
/>
Рисунок 9 – Входныеданные.
/>
Рисунок 10 – Выходныеданные.
ЗАКЛЮЧЕНИЕ
Проблемаповышения качества вычислений, как несоответствие между желаемым идействительным, существует и будет существовать в дальнейшем. Ее решению будетсодействовать развитие информационных технологий, которое заключается как всовершенствовании методов организации информационных процессов, так и ихреализации с помощью конкретных инструментов – сред и языков программирования.
Итогомработы можно считать созданную функциональную модель нахождения корней уравнения методомНьютона. Данная модель может бытьиспользована для решения задач оптимизации, в которых требуется определить нульпервой производной либо градиента в случае многомерного пространства. Созданная функциональная модель и еепрограммная реализация могут служить органической частью решения более сложныхзадач.
СПИСОКИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ и литературы
1. Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов[Текст] / И.Н.Бронштейн, К.А.Семендяев. – М.: Наука, 2007. – 708 с.
2. Кремер, Н.Ш.Высшая математика для экономистов: учебник для студентов вузов. [Текст] /Н.Ш.Кремер, 3-е издание – М.: ЮНИТИ-ДАНА, 2006. C. 412.
3. Калиткин,Н.Н. Численные методы. [Электронный ресурс] / Н.Н. Калиткин. – М.: Питер, 2001.С. 504.
4. Метод Ньютона – Википедия[Электронный ресурс] – Режим доступа: ru.wikipedia.org/wiki/Метод_Ньютона
5. Семакин, И.Г.Основы программирования. [Текст] / И.Г.Семакин, А.П.Шестаков. – М.: Мир, 2006. C. 346.
6. Симанков,В.С. Основы функционального программирования [Текст] / В.С.Симанков,Т.Т.Зангиев, И.В.Зайцев. – Краснодар: КубГТУ, 2002. – 160 с.
7. Степанов, П.А.Функциональное программирование на языке Lisp. [Электронный ресурс] / П.А.Степанов,А.В. Бржезовский. – М.: ГУАП, 2003. С. 79.
8. Хювенен Э. Мир Лиспа [Текст] / Э.Хювенен, Й.Сеппянен. – М.: Мир, 1990. –460 с.