Реферати

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

Тахмасп I. Шах Тахмасиб (1514-1576) - Шах Ірану, другий шах династії Сефевидов. Старший син Исмаила I, засновника династії Сефевидов. Біографія Народився Тахмасп I у 1514 році в місті Исфаган. У 1524 році у віці 10 років став правителем-шахиншахом Ірану. У 1538 році Шах Тахмасп відправив війська на придушення заколоту в Ширване, очолюваним Альгасом і останній ширваншах з династії династії Дербенди Шахрух був захоплений у полон.

Впровадження інформаційного менеджменту на підприємство. ФЕДЕРАЛЬНЕ АГЕНТСТВО ПО УТВОРЕННЮ Брянський державний технічний університет Кафедра "Економіка і менеджмент" К у р с о в а я р а б о т а по дисципліні: "Інформаційний менеджмент"

Шаховской, Іван Леонтьевич. Князь Верба́н Лео́нтьевич Шаховско́й (1777-1860), генерал від інфантерії, генерал-ад'ютант. Біографія З князів. У службу записаний сержантом у л.-гв. Измайловский полк 1 січня 1786. Випущений в армію капітаном 1 січня 1794 р., визначений у Херсонський гренадерський полк і брав участь у бойових діях з польськими конфедератами.

Валютний курс 4. Зміст 1. Валютний курс і види котирувань валют (прямі, непрямі), крос - курси......3 2. Права й обов'язки резидентів і нерезидентів при проведенні валютного контролю......7

Кінь Пржевальська. ДОПОВІДЬ ПО БІОЛОГІЇ НА ТЕМУ: КІНЬ ПРЖЕВАЛЬСЬКА ВИКОНАВ: УЧЕНЬ 7"А" КЛАСУ ГОУ СОШ № 163 р. МОСКВИ ЄФРЕМОВ МИХАЙЛО 2009 р. Кінь Пржевальська Наукова класифікація

ЗМІСТ

Введення

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, а послідовність поліномів і в результаті отримував наближене рішення х.

Уперше метод був опублікований в трактаті Алгебра Джона Валліса в 1685 році, на прохання якого він був стисло описаний самим Ньютоном. У 1690 році Джозеф Рафсон опублікував спрощений опис в роботі Analysis aequationum universalis (лати. Загальний аналіз рівнянь). Рафсон розглядав метод Ньютона як чисто алгебраїчний і обмежив його застосування поліномами, однак при цьому він описав метод на основі послідовних наближень xnвместо більше за важку для розуміння послідовність поліномів, використану Ньютоном. Нарешті, в 1740 році метод Ньютона був описаний Томасом Симпсоном як итеративний метод першого порядку рішення нелінійних рівнянь з використанням похідною в тому вигляді, в якому він викладається тут. У тій же публікації Симпсон узагальнив метод на випадок системи з двох рівнянь і відмітив, що метод Ньютона також може бути застосований для рішення задач оптимізації шляхом знаходження нуля похідною або градієнта.

У1879 годуАртурКеливработе The Newton-Fourier imaginary problem (англ. Проблема комплексних чисел Ньютона-Фурье) був першим, хто відмітив труднощі в узагальненні методу Ньютона на випадок уявного коріння поліномів міри вище другої і комплексних початкових наближень. Ця робота відкрила шлях до вивчення теорії фракталов.

Метою даної курсової роботи є Лісп - реалізація знаходження коріння рівняння методом Ньютона.

1. Постановка задачі

Дано рівняння:.

Потрібно вирішити це рівняння, точніше, знайти одне з його коріння (передбачається, що корінь існує). Передбачається, що F(X) безперервна і диференціюється на відрізку [А;][В].

Вхідним параметром алгоритму, крім функції 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(х) = cosx − x3.

Маємо вираження для похідної.

Оскільки для всіх х і x3 > 1 для х > 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 Опис методу

Нехай корінь х рівняння відділений на відрізку [a, b], причому і безперервні і зберігають певні знаки при. Якщо на деякому довільному кроці n знайдене наближене значення кореня,

то можна уточнити це значення по методу Ньютона. Покладемо,

(1)

де вважаємо малою величиною. Застосовуючи формулу Тейлора, отримаємо:.

Отже,.

Внеся цю поправку в формулу (1), знайдемо наступне (по порядку) наближення кореня.

(2)

Геометрично метод Ньютона еквівалентний заміні дуги кривої дотичної, проведеній в деякій точці кривій. Дійсно, покладемо для визначеності, що при і (малюнок 1).

Виберемо, наприклад,, для якого. Проведемо дотичну до кривої в точці B0с координатами.

Малюнок 1. Геометрично показаний метод Ньютона

Як перше наближення кореня х візьмемо абсцису точки перетину дотичною з віссю Ox. Через точку знов проведемо дотичну, абсциса точки перетину якої дасть друге наближення кореня х і т. д.

Формулу для уточнення кореня можна отримати з прямокутного трикутника, освіченого дотичною, проведеною в точці B0, віссю абсцис і перпендикуляром, відновленим з точки.

Маємо.

Оскільки кут а освічений дотичної і віссю абсцис, його тангенс чисельно рівний величині похідній, обчисленій в точці, відповідній абсцисі точки дотику, т. е..

Тоді

або для будь-якого кроку n.

Як початкова точка можна прийняти або один з кінців відрізка [a, b], або точку всередині цього інтервалу. У першому випадку рекомендується вибирати ту межу, де виконується умова,

т. е. функція і її друга похідна в точці повинні бути одного знака.

Як найпростіші умови закінчення процедури уточнення кореня рекомендується виконання умови.

Як випливає з останньої нерівності, потрібно при розрахунку запам'ятовувати три значення аргументу. У практичних інженерних розрахунках часто застосовують порівняння аргументів на поточній і попередній ітераціях:.

При складанні програми рішення рівняння методом Ньютона потрібно організувати багаторазовий розрахунок наближень для кореня х. Якщо вдається отримати аналітичне вираження для похідної, то її обчислення, а також обчислення можна оформити у вигляді функцій.

2.2 Нестачі методу

Нехай.

Тоді.

Візьмемо нуль як початкове наближення. Перша ітерація дасть як наближення одиницю. У свою чергу, друга знов дасть нуль. Метод зациклиться, і рішення не буде знайдене. У загальному випадку побудова послідовності наближень може бути дуже заплутаною.

Малюнок 2. Ілюстрація розходження методу Ньютона, застосованого до функції з початковим наближенням в точці

Якщо похідна не безперервна в точці кореня, то метод може розійтися в будь-якій околиці кореня.

Якщо не існує друга похідна в точці кореня, то швидкість збіжності методу може бути помітно знижена.

Якщо похідна в точці кореня рівна нулю, то швидкість збіжності не буде квадратичною, а сам метод може передчасно припинити пошук, і дати невірне для заданої точності наближення.

Нехай.

Тоді і отже. Таким чином збіжність методу не квадратична, а лінійна, хоч функція всюди нескінченно диференціюється.

3. Функціональні моделі і блок-схеми рішення задачі

Функціональні моделі і блок-схеми рішення задачі представлені на малюнку 3, 4.

Умовні позначення:

· FUNCTN, FX - функція;

· DFUNCTN, DFDX - похідна функції;

· А - робоча змінна;

· START, X0 - початкове значення;

· PRES, Е - точність обчислення.

Малюнок 3 - Функціональна модель рішення задачі для пошуку кореня рівняння методом Ньютона

Малюнок 4 - Блок-схема рішення задачі для функції NEWTOM

4. Програмна реалізація рішення задачі

Файл FUNCTION.txt (Приклад 1);

ФУНКЦІЯ COSX - X3

(FUNF(X)

(- (COSX) (* XXX))

);

ПОХІДНА -sinx-3x2

(FUN DFDX (X)

(- (* - 1 (SIN X)) (* 3 X X))

)

(SETQ X0 0.5)

(SETQ Е 0.0001)

Файл FUNCTION.txt (Приклад 2);

ФУНКЦІЯ x-cosx

(FUN F(X)

(- X (COS X))

);

ПОХІДНА 1+sinx

(FUN DFDX (X)

(+ 1 (SIN X))

)

(SETQ X0 -1)

(SETQ Е 0.0001)

Файл FUNCTION.txt (Приклад 3);

ФУНКЦІЯ X2+2X

(FUN F(X)

(+ (* X X) (* 2 X))

);

ПОХІДНА 2X+2

(FUN DFDX (X)

(+ 2 (* 2 X))

)

(SETQ X0 -2.3)

(SETQ Е 0.0001)

Файл NEWTON.txt;

"ПОДГРУЖАЕМФУНКЦИЮ

(LOAD D:\\FUNCTION.TXT");

РЕАЛИЗАЦИЯМЕТОДАНЬЮТОНА

(EFUN NEWTOM (START PRES FUNCTN DFUNCTN);

ОГОЛОШЕННЯ ЗМІННИХ

(DECLARE (SPECIAL X))

(DECLARE (SPECIAL А));

ЗАДАЄМО ПОЧАТКОВЕ ЗНАЧЕННЯ

(SETQ X START)

(SETQ А (/ (FUNCALL FUNCTN X) (FUNCALL DFUNCTN X)))

(SETQ X (- XA))

(SETQ А (/ (FUNCALL FUNCTN X) (FUNCALL DFUNCTN X)));

ЯКЩО ДОСЯГЛИ НЕОБХІДНОЇ ТОЧНОСТІ ВИХОДИМО З ЦИКЛУ

(IF ( <(ABS А) PRES) (RETURN X))

)

);

"ОТКРИВАЕМФАЙЛ

(SETQ OUTPUT_STREAM (OPEN D:\KOREN.TXT": DIRECTION: OUTPUT));

ВИКЛИКАЄМО МЕТОД НЬЮТОНА ДЛЯ РОЗРАХУНКУ КОРЕНЯ

(SETQ KOREN (NEWTOM X0 Е (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. Хювенен Е. Мір Ліспа [Текст] / Е. Хювенен, Й. Сеппянен. - М.: Мир, 1990. - 460 з.