ЗМІСТ
Введення
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 році вже після смерті творця. Однак опис методу істотно відрізнялося від його нинішнього викладу: Ньютон застосовував свій метод виключно до поліномами. Гадав не послідовні наближення x n, а послідовність поліномів і в результаті отримував наближене рішення x.
Вперше метод був опублікований в трактаті Алгебра Джона Валліса в 1685 році, на прохання якого він був коротко описаний самим Ньютоном. У 1690 році Джозеф Рафсона опублікував спрощений опис в роботі Analysis aequationum universalis (лат. Загальний аналіз рівнянь). Рафсона розглядав метод Ньютона як чисто алгебраїчний і обмежив його застосування поліномами, однак при цьому він описав метод на основі послідовних наближень x n замість більш важкою для розуміння послідовності поліномів, використаної Ньютоном. Нарешті, в 1740 році метод Ньютона був описаний Томасом Сімпсоном як ітеративний метод першого порядку вирішення нелінійних рівнянь з використанням похідної в тому вигляді, в якому він викладається тут. У тій же публікації Сімпсон узагальнив метод на випадок системи з двох рівнянь і відзначив, що метод Ньютона також може бути застосований для вирішення завдань оптимізації шляхом знаходження нуля похідної або градієнта.
У 1879 році Артур Келі в роботі The Newton-Fourier imaginary problem (англ. Проблема комплексних чисел Ньютона-Фур'є) був першим, хто відзначив труднощі в узагальненні методу Ньютона на випадок уявних коренів поліномів ступеня вище другий і комплексних початкових наближень. Ця робота відкрила шлях до вивчення теорії фракталів.
Метою даної курсової роботи є Лісп - реалізація знаходження коренів рівняння методом Ньютона.
1. Постановка завдання
Дано рівняння:
.
Потрібно вирішити це рівняння, точніше, знайти один з його коренів (передбачається, що корінь існує). Передбачається, що F (X) неперервна і диференційовна на відрізку [A; B].
Вхідним параметром алгоритму, крім функції F (X), є також початкове наближення - деякий X 0, від якого алгоритм починає йти.
Нехай вже обчислено X i, обчислимо X i +1 наступним чином. Проведемо дотичну до графіка функції F (X) в точці X = X i, і знайдемо точку перетину цієї дотичної з віссю абсцис. X i +1 покладемо рівним знайденої точці, і повторимо весь процес від початку.
Неважко отримати такий вираз:
X i +1 = X i - F (X i) / F '(X i)
Інтуїтивно ясно, що якщо функція F (X) достатньо "хороша", а X i знаходиться досить близько від кореня, то X i +1 буде перебувати ще ближче до шуканого кореня.
Приклад 1.
Потрібно знайти корінь рівняння , З точністю
.
Похідна функції дорівнює
.
Візьмемо за початкову точку , Тоді
-9.716215;
5.74015;
3.401863;
-2.277028;
1.085197;
0.766033;
0.739241.
Таким чином, корінь рівняння
дорівнює 0.739241.
Приклад 2.
Знайдемо корінь рівняння функції методом Ньютона
cosx = x 3.
Це завдання може бути представлена як задача знаходження нуля функції
f (x) = cosx - x 3.
Маємо вираз для похідної
.
Так як для всіх x і x 3> 1 для x> 1, очевидно, що рішення лежить між 0 і 1. Візьмемо в якості початкового наближення значення x 0 = 0.5, тоді:
1.112141;
0.90967;
0.867263;
0.865477;
0.865474033111;
0.865474033102.
Таким чином, корінь рівняння функції
cosx = x 3 дорівнює 0.86547403.
Приклад 3.
Потрібно знайти корінь рівняння , З точністю
.
Похідна функції
дорівнює
.
Візьмемо за початкову точку , Тоді
-2.3;
-2.034615;
-2.000579;
-2.0.
Таким чином, корінь рівняння
дорівнює -2.
2. Математичні та алгоритмічні основи рішення задачі
2.1 Опис методу
Нехай корінь x рівняння відділений на відрізку [a, b], причому
і
безупинні і зберігають певні знаки при
. Якщо на деякому довільному кроці n знайдено наближене значення кореня
,
то можна уточнити це значення за методом Ньютона. Покладемо
, (1)
де вважаємо малою величиною. Застосовуючи формулу Тейлора, отримаємо:
.
Отже,
.
Внісши цю поправку до формули (1), знайдемо наступне (по порядку) наближення кореня
. (2)
Геометрично метод Ньютона еквівалентний заміні дуги кривої дотичній, проведеної в деякій точці кривої. Справді, покладемо для визначеності, що
при
і
(Рисунок 1).
Виберемо, наприклад, , Для якого
. Проведемо дотичну до кривої
в точці B 0 з координатами
.
Малюнок 1. Геометрично показаний метод Ньютона
В якості першого наближення кореня x візьмемо абсцису точки перетину дотичної з віссю Ox. Через точку
знову проведемо дотичну, абсциса точки перетину якої дасть другий наближення
кореня x і т.д.
Формулу для уточнення кореня можна отримати з прямокутного трикутника , Утвореного дотичній, проведеної в точці B 0, віссю абсцис і перпендикуляром, відновленим з точки
.
Маємо
.
Так як кут утворений дотичній і віссю абсцис, його тангенс чисельно дорівнює величині похідної, обчисленої точці, що відповідає абсциссе точки дотику, тобто
.
Тоді
або для будь-якого кроку 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 - X 3
(DEFUN F (X)
(- (COS X) (* X X X))
)
; ПОХІДНА-sinx-3x2
(DEFUN DFDX (X)
(- (* -1 (SIN X)) (* 3 XX))
)
(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 +2 X
(DEFUN F (X)
(+ (* XX) (* 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 (- XA))
(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 с.