Реферат на тему:
-
Вступ
- 1 Опис методу
- 1.1 Обгрунтування
- 1.2 Геометрична інтерпретація
- 1.3 Алгоритм
- 1.4 Приклад
- 2 Умови застосування
- 2.1 Контрприклади
- 2.2 Обмеження
- 3 Історична довідка
- 4 Узагальнення і модифікації
- 4.1 Метод однієї дотичній
- 4.2 Багатомірний випадок
- 4.3 Що стосується завданням оптимізації
- 4.4 Метод Ньютона - Рафсона
- 4.5 Що стосується завданням про найменших квадратах
- 4.6 Метод Гаусса - Ньютона
- 4.7 Узагальнення на комплексну площину
Примітки
Метод Ньютона. алгоритм Ньютона (також відомий як метод дотичних) - це ітераційний чисельний метод знаходження кореня (нуля) заданої функції. Метод був вперше запропонований англійським фізиком, математиком і астрономом Ісааком Ньютоном (1643-1727), під ім'ям якого і знайшов свою популярність. Пошук рішення здійснюється шляхом побудови послідовних наближень і заснований на принципах простої ітерації. Метод має квадратичної сходимостью. Поліпшенням методу є метод хорд і дотичних. Також метод Ньютона може бути використаний для вирішення завдань оптимізації, в яких потрібно визначити нуль першої похідної або градієнта в разі багатовимірного простору.
1. Опис методу
1.1. обгрунтування
Щоб чисельно вирішити рівняння методом простої ітерації, його необхідно привести до наступної форми:, де - стискає відображення.
Для кращої збіжності методу в точці чергового наближення має виконуватися умова. Рішення даного рівняння шукають у вигляді, тоді:
У припущенні, що точка наближення «досить близька» до кореня, і що задана функція неперервна, остаточна формула для така:
З урахуванням цього функція визначається виразом:
Ця функція в околиці кореня здійснює стискуюче відображення [1]. і алгоритм знаходження чисельного рішення рівняння зводиться до ітераційної процедури обчислення:
По теоремі Банаха послідовність наближень прагне до кореня рівняння.
Ілюстрація методу Ньютона (синім зображена функція, нуль якої необхідно знайти, червоним - дотична в точці чергового наближення). Тут ми можемо побачити, що подальше наближення кращий за попередній.
1.2. геометрична інтерпретація
Основна ідея методу полягає в наступному: задається початкове наближення поблизу можливого кореня, після чого будується дотична до досліджуваної функції в точці наближення, для якої знаходиться перетин з віссю абсцис. Ця точка і береться в якості наступного наближення. І так далі, поки не буде досягнута необхідна точність.
Нехай - певна на відрізку і диференційована на ньому вещественнозначная функція. Тоді формула ітеративного обчислення наближень може бути виведена в такий спосіб:
де α - кут нахилу дотичної в точці.
Отже шуканий вираз для має вигляд:
Ітераційний процес починається з якогось початкового наближення x0 (чим ближче до нуля, тим краще, але якщо припущення про знаходження рішення відсутні, методом проб і помилок можна звузити область можливих значень, застосувавши теорему про проміжні значення).
1.3. алгоритм
- Здається початкове наближення x0.
- Ще не виконана умова зупинки, в якості якого можна взяти або (тобто похибка в потрібних межах), обчислюють нове наближення:.
1.4. приклад
Ілюстрація застосування методу Ньютона до функції f (x) = cosx - x 3 з початковим наближенням в точці x0 = 0,5.
Згідно способу практичного визначення швидкість збіжності може бути оцінена як тангенс кута нахилу графіка збіжності, тобто в даному випадку дорівнює двом.
Розглянемо задачу про знаходження позитивних x. для яких cosx = x 3. Ця задача може бути представлена як задача знаходження нуля функції f (x) = cosx - x 3. Маємо вираз для похідної f '(x) = - sinx - 3x 2. Так як для всіх x і x 3> 1 для x> 1. очевидно, що рішення лежить між 0 і 1. Візьмемо в якості початкового наближення значення x0 = 0,5. тоді:
Підкресленням відзначені вірні значущі цифри. Видно, що їх кількість від кроку до кроку зростає (приблизно подвоюючи з кожним кроком): від 1 до 2, від 2 до 5, від 5 до 10, ілюструючи квадратичную швидкість збіжності.
2. Умови застосування
Ілюстрація розбіжності методу Ньютона, застосованого до функції з початковим наближенням в точці.
Розглянемо ряд прикладів, що вказують на недоліки методу.
2.1. контрприклади
- Якщо початкове наближення недостатньо близько до вирішення, то метод може не зійтися.
Візьмемо нуль в якості початкового наближення. Перша ітерація дасть в якості наближення одиницю. У свою чергу, друга знову дасть нуль. Метод зациклиться і рішення не буде знайдено. У загальному випадку побудова послідовності наближень може бути дуже заплутаним.
Графік похідної функції при наближенні до нуля справа.
- Якщо похідна немає неперервна в точці кореня, то метод може розходитися в будь-який околиці кореня.
Тоді і всюди, крім 0.
В околиці кореня похідна змінює знак при наближенні x до нуля справа або зліва. У той час, як для.
Таким чином не обмежена поблизу кореня, і метод буде розходитися, хоча функція всюди дифференцируема, її похідна не дорівнює нулю в корені, нескінченно диференційована всюди, крім як в корені, а її похідна обмежена в околиці кореня.
- Якщо не існує друга похідна в точці кореня, то швидкість збіжності методу може бути помітно знижена.
Тоді і за винятком, де вона не визначена.
На черговому кроці маємо:
Швидкість збіжності отриманої послідовності становить приблизно 4/3. Це істотно менше, ніж 2, необхідне для квадратичної збіжності, тому в даному випадку можна говорити лише про лінійної збіжності, хоча функція всюди неперервно диференційовна, похідна в корені не дорівнює нулю, і нескінченно диференційована всюди, крім як в корені.
- Якщо похідна в точці кореня дорівнює нулю, то швидкість збіжності НЕ буде квадратичної, а сам метод може передчасно припинити пошук, і дати невірне для заданої точності наближення.
Тоді і отже. Таким чином збіжність методу не квадратична, а лінійна, хоча функція всюди нескінченно диференційована.
2.2. обмеження
Нехай задано рівняння, де і треба знайти його рішення.
Нижче наведена формулювання основної теореми, яка дозволяє дати чіткі умови застосовності. Вона носить ім'я радянського математика і економіста, лауреата Нобелівської премії з економіки 1975 року «за внесок в теорію оптимального розподілу ресурсів» Леоніда Віталійовича Канторовича (1912-1986) і є однією з численних теорем, які стали результатами його наукових пошуків.
Якщо існують такі константи, що:
- на, тобто існує і не дорівнює нулю;
- на, тобто обмежена;
- на, і;
Причому довжина розглянутого відрізка. Тоді справедливі наступні твердження:
- на існує корінь рівняння;
- якщо, то итерационная послідовність сходиться до цього кореня:;
- похибка може бути оцінена за формулою.
З останнього з тверджень теореми зокрема слід квадратична збіжність методу:
Тоді обмеження на вихідну функцію будуть виглядати так:
- функція повинна бути обмежена;
- функція повинна бути гладкою, двічі диференціюється;
- її перша похідна рівномірно відокремлена від нуля;
- її друга похідна повинна бути рівномірно обмежена.
3. Історична довідка
У 1879 році Артур Келі в роботі «Проблема комплексних чисел Ньютона - Фур'є» (англ. «The Newton-Fourier imaginary problem») був першим, хто відзначив труднощі в узагальненні методу Ньютона на випадок уявних коренів поліномів ступеня вище другий і комплексних початкових наближень. Ця робота відкрила шлях до вивчення теорії фракталів.
4. Узагальнення і модифікації
Ілюстрація послідовних наближень методу однієї дотичній, застосованого до функції з початковим наближенням в точці.
4.1. Метод однієї дотичній
З метою зменшення кількості звернень до значень похідної функції застосовують так званий метод однієї дотичній.
Формула ітерацій цього методу має вигляд:
Суть методу полягає в тому, щоб обчислювати похідну лише один раз, в точці початкового наближення, а потім використовувати це значення на кожній наступній ітерації:
При такому виборі в точці виконано рівність:
і якщо відрізок, на якому передбачається наявність кореня і вибрано початкове наближення, досить малий, а похідна неперервна, то значення буде не сильно відрізнятися від і, отже, графік пройде майже горизонтально, перетинаючи пряму, що в свою чергу забезпечить швидку збіжність послідовності точок наближень до кореня.
Цей метод можна також розглядати, як модернізацію методу хорд (січних), де число слід вибрати рівним
4.2. багатовимірний випадок
Узагальнимо отриманий результат на багатовимірний випадок.
Нехай необхідно знайти рішення системи:
Вибираючи деяке початкове значення, послідовні наближення знаходять шляхом вирішення систем рівнянь:
4.3. Що стосується завданням оптимізації
Нехай необхідно знайти мінімум функції багатьох змінних. Це завдання рівносильна задачі знаходження нуля градієнта. Застосуємо викладений вище метод Ньютона:
де - гессіан функції.
У більш зручному итеративном вигляді цей вислів виглядає так:
Слід зазначити, що в разі квадратичної функції метод Ньютона знаходить екстремум за одну ітерацію.
Знаходження матриці Гессе пов'язано з великими обчислювальними витратами, і часто не представляється можливим. У таких випадках альтернативою можуть служити квазіньютоновскіе методи, в яких наближення матриці Гессе будується в процесі накопичення інформації про кривизну функції.
4.4. Метод Ньютона - Рафсона
Метод Ньютона - Рафсона є поліпшенням методу Ньютона знаходження екстремуму, описаного вище. Основна відмінність полягає в тому, що на черговій ітерації будь-яким з методів одновимірної оптимізації вибирається оптимальний крок:
де Для оптимізації обчислень застосовують наступне поліпшення: замість того, щоб на кожній ітерації заново обчислювати гессіан цільової функції, обмежуються початковим наближенням і оновлюють його лише раз в кроків, або не оновлюють зовсім.
4.5. Що стосується завданням про найменших квадратах
На практиці часто зустрічаються задачі, в яких потрібно зробити налаштування вільних параметрів об'єкта або підігнати математичну модель під реальні дані. У цих випадках з'являються завдання про найменших квадратах:
Ці завдання відрізняються особливим видом градієнта і матриці Гессе:
де - матриця Якобі вектор-функції, - матриця Гессе для її компоненти.
Тоді чергове напрямок визначається з системи:
4.6. Метод Гаусса - Ньютона
Метод Гаусса - Ньютона будується на припущенні про те, що доданок домінує над. Ця вимога не дотримується, якщо мінімальні невязки великі, тобто якщо норма порівнянна з максимальним власним значенням матриці. В іншому випадку можна записати:
Таким чином, коли норма близька до нуля, а матриця має повний столбцевой ранг, напрямок мало відрізняється від ньютонівського (з урахуванням), і метод може досягати квадратичної швидкості збіжності, хоча другі похідні і не враховуються. Поліпшенням методу є алгоритм Левенберга - Марквардта, заснований на евристичних міркуваннях.
4.7. Узагальнення на комплексну площину
Басейни Ньютона для полінома п'ятого ступеня. Різними кольорами зафарбовані області тяжіння для різних коренів. Більш темні області відповідають більшій кількості ітерацій.
До сих пір в описі методу використовувалися функції, які здійснюють відображення в межах безлічі дійсних значень. Однак метод може бути застосований і для знаходження нуля функції комплексної змінної. При цьому процедура залишається незмінною:
Особливий інтерес представляє вибір початкового наближення. З огляду на те, що функція може мати кілька нулів, в різних випадках метод може сходитися до різних значень, і цілком природно виникає бажання з'ясувати, які області забезпечать відповідність до тієї чи іншої корені. Це питання зацікавило Артура Кейлі ще в 1879 році, проте дозволити його змогли лише в 70-х роках двадцятого століття з появою обчислювальної техніки. Виявилося, що на перетинах цих областей (їх прийнято називати областями тяжіння) утворюються так звані фрактали - нескінченні самоподібні геометричні фігури.
З огляду на те, що Ньютон застосовував свій метод виключно до поліномами, фрактали, утворені в результаті такого застосування, здобули назву фракталів Ньютона або басейнів Ньютона.
література
Примітки
- Доказ: Нехай дана функція речового змінного двічі безперервно диференціюється в своїй області визначення, похідна якої ніде не звертається в нуль: І необхідно довести, що функція здійснює стискуюче відображення поблизу кореня рівняння. В силу безперервної диференційованої функції і нерівності нулю її першої похідної безперервна. Похідна дорівнює: В умовах, накладених на, вона також неперервна. Нехай - шуканий корінь рівняння:, отже в його околиці: Тоді згідно з теоремою Лагранжа: В силу того, що в цій же дельта околиці виконується: Таким чином отримана функція в околиці кореня здійснює стискуюче відображення.