Метод на Нютон

Методът на Нютон (известен също като метод на допирателните) е итерационен числен метод (алгоритъм) за намиране на приблизителни стойности на корените на реални функции. Той използва поредица от последователни все по-точни приближения, до достигане на търсената точност на решението. Започва се със стойност, относително близка до истинското решение. Функцията се замества с нейната допирателна в тази точка и се изчислява стойността на аргумента, при която допирателната пресича нулевата линия. Тази точка се приема за нова изходна стойност и методът се повтаря итеративно.

Описание на метода

Геометрична интерпретация

Илюстрация на метода на Нютон. В синьо е изобразена функцията $\scriptstyle {f(x)}$, на която трябва да се намери нулата (коренът на $\scriptstyle {f(x)}=0$), с червено – допирателната в точката на поредното приближение $\scriptstyle {x_{n}}$. Тук се вижда, че следващото приближение $\scriptstyle {x_{n+1}}$ е по-добро от предишното $\scriptstyle {x_{n}}$.

Основната идея на метода е следната: задава се начално приближение $x_{n}$ близо до предполагаемия корен, след което в точката на приближение $f(x_{n})$ се построява допирателна към графиката на изследваната функция, за която се намира пресечната точка с абцисната ос $x$ близо до предполагаемия корен. Тази точка се приема за ново приближение и в точката на приближение $f(x_{n+1})$ се построява нова допирателна към графиката на функцията, която пресича оста $x$ в следващата точка на приближение $x_{n+2}$. Процесът продължава докато се постигне необходимата точност.

Извеждане

За да се реши числено уравнението $f(x)=0$ с помощта на проста итерация, то трябва да се преобразува в еквивалентно уравнение: $x=\varphi (x)$, където $\varphi$ е свиващо се изображение.

За най-добра сходимост на метода, в точката на следващото приближение $x^{*}$ трябва да бъде изпълнено условието $\varphi '(x^{*})=0$. Решението на това уравнение се търси във вида $\varphi (x)=x+\alpha (x)f(x)$, тогава:

$\varphi '(x^{*})=1+\alpha '(x^{*})f(x^{*})+\alpha (x^{*})f'(x^{*})=0.$

Ако се приеме, че точката на приближение е „достатъчно близо“ до корена ${\tilde {x}}$ и че дадената функция е непрекъсната $(f(x^{*})\approx f({\tilde {x}})=0)$, крайната формула за $\alpha (x)$ е:

$\alpha (x)=-{\frac {1}{f'(x)}}.$

Като се отчете това, функцията $\varphi (x)$ се определя като

$\varphi (x)=x-{\frac {f(x)}{f'(x)}}.$

При определени условия тази функция извършва свиващо се изображение в околността на корена.

В този случай, алгоритъмът за намиране на числено решение на уравнението $f(x)=0$ се свежда до проста итеративна процедура за изчисление (метод на последователните приближения):

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.$

Съгласно теоремата на Банах, последователността от приближения се стреми към корена на уравнението $f(x)=0$.

Алгоритъм

1. Записват се изразите за функцията $f(x)$ и първата ѝ производна $f'(x)$.
2. Задават се желаната точност на изчисление $\varepsilon$ като абсолютна грешка (тъй като методът на Нютон е частен случай на метода на простата итерация) и началното приближение $x_{0}\ \ ,\ \ (n=0)$.
3. Определят се стойностите на функцията $f(x_{0})$ и първата ѝ производна $f'(x_{0})$.
4. Изчислява се ново приближение $x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$ докато не се изпълни условието за спиране $\left\vert {\frac {x_{n+1}-x_{n}}{1-{\frac {x_{n+1}-x_{n}}{x_{n}-x_{n-1}}}}}\right\vert <\varepsilon$.

Примери

Квадратен корен от число

Разглежда се задачата за намиране на квадратен корен от число. Има много начини за изчисляването на корени и Нютоновият метод е един от тях.

Например, ако трябва да се намери квадратен корен от 612, това е еквивалентно на намирането на решенията на уравнението $\,x^{2}=612.$

Тогава функцията, която се използва за метода на Нютон е $\,f(x)=x^{2}-612$

с производна $\,f'(x)=2x.\,$

При избрана начална стойност $x_{0}=10$, редицата получена по метода на Нютон е

${\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&10-{\dfrac {10^{2}-612}{2\cdot 10}}&=&35,6\quad \quad \quad {}\\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&35,6-{\dfrac {35,6^{2}-612}{2\cdot 35,6}}&=&{\underline {2}}6,3955056\\x_{3}&=&\vdots &=&\vdots &=&{\underline {24,7}}906355\\x_{4}&=&\vdots &=&\vdots &=&{\underline {24,7386}}883\\x_{5}&=&\vdots &=&\vdots &=&{\underline {24,7386338}}\end{matrix}}$

Подчертаните цифри са коректни числа. Само с няколко итерации може да се намери решение, с точност много цифри след запетаята.

Решение на неполиномни уравнения

Разглежда се задачата за намиране на положителното число x, удовлетворяващо уравнението $\cos(x)=x^{3}$. Уравнението се записва във вида $f(x)=\cos(x)-x^{3}=0$ и се търсят корените му. Първата производна е $f'(x)=-\sin(x)-3x^{2}$. Тъй като $\cos(x)\leqslant 1$ за всяко $x$, от уравнението $\cos(x)=x^{3}$ следва, че и $x^{3}<1$ и $x<1$, т.е. търсеният корен се намира между 0 и 1. Избира се, примерно начална стойност $x_{0}=0,5$. (Забележете, че при начална стойност 0 ще се получи неопределен резултат, което показва важността от използването на начална точка, която е близо до нулата.)

${\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&0,5-{\dfrac {\cos(0,5)-(0,5)^{3}}{-\sin(0,5)-3(0,5)^{2}}}&=&1,112141637097\\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&\vdots &=&{\underline {0,}}909672693736\\x_{3}&=&\vdots &=&\vdots &=&{\underline {0,86}}7263818209\\x_{4}&=&\vdots &=&\vdots &=&{\underline {0,86547}}7135298\\x_{5}&=&\vdots &=&\vdots &=&{\underline {0,8654740331}}11\\x_{6}&=&\vdots &=&\vdots &=&{\underline {0,865474033102}}\end{matrix}}$

Верните числа са подчертани в примера по-горе. В частност x₆ е с точност до всички показани позиции след запетаята. Вижда се, че броят на правилните числа след десетичната точка нараства от 2 (за x₃) до 5 и 10, показвайки квадратната сходимост.

Условия на приложение

Има редица примери, посочващи недостатъците на метода.

Контрапримери

• Ако началното приближение не е достатъчно близко до решението, методът може да не се сближи.
• Ако производната не е непрекъсната в коренната точка, методът може да се отклони във всяка околност на корена.
• Ако втората производна не съществува в коренната точка, скоростта на сходимост на метода може да бъде значително намалена.
• Ако производната в коренната точка е нула, скоростта на сходимост няма да бъде квадратична и самият метод може да прекрати търсенето преждевременно и да доведе до приближение, което е неправилно за дадената точност.

Ограничения

^{Този раздел е празен или е мъниче. Можете да помогнете на Уикипедия, като го разширите.}

Обобщения и модификации

^{Този раздел е празен или е мъниче. Можете да помогнете на Уикипедия, като го разширите.}

Метод на Нютон – Рафсон

Методът на Нютон-Рафсон е подобрение на метода на Нютон за намиране на екстремум, описан по-горе. Основната разлика е, че при следващата итерация един от методите за едномерна оптимизация избира оптималната стъпка:

${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda _{j}H^{-1}({\vec {x}}^{[j]})\nabla f({\vec {x}}^{[j]}),$

където $\lambda _{j}=\arg \min _{\lambda }f({\vec {x}}^{[j]}-\lambda H^{-1}({\vec {x}}^{[j]})\nabla f({\vec {x}}^{[j]})).$ За оптимизиране на изчисленията се прилага следното подобрение: вместо да се преизчислява хесианът на целевата функция при всяка итерация, те се ограничават до началното приближение $H(f({\vec {x}}^{[0]}))$ и го актуализират само веднъж на всеки $m$ стъпки или изобщо не го актуализират.

Реализация

^{Този раздел е празен или е мъниче. Можете да помогнете на Уикипедия, като го разширите.}

Вижте също

• Нютонов фрактал
• Алгоритъм на Гаус – Нютон
• Двоично търсене
• Дихотомия

Външни препратки

• «Бассейны Ньютона» на сайте fractalworld.xaoc.ru
• «Исаак Ньютон» на сайте www.scottish-wetlands.org
• «Математические работы Канторовича» на сайте Института математики СО РАН

• Newton’s method, Citizendium.
• Mathews, J., The Accelerated and Modified Newton Methods, Course notes.
• Wu, X., Roots of Equations, Course notes.
• Werner Vogt: 3.2 Das Newton-Verfahren in Zur Numerik nichtlinearer Gleichungssysteme (Teil 1), Oktober 2001.

Литература

На руски език

• Акулич И. Л. Математическое программирование в примерах и задачах : Учеб. пособие для студентов эконом. спец. вузов. — М. : Высшая школа, 1986. — 319 с. : ил. — ББК 22.1 А44. — УДК 517.8(G).
• Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров : Учеб. пособие. — М. : Высшая школа, 1994. — 544 с. : ил. — ББК 32.97 А62. — УДК 683.1(G). — ISBN 5-06-000625-5.
• Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М. : Лаборатория Базовых Знаний, 2000.
• Вавилов С. И. Исаак Ньютон. — М. : Изд. АН СССР, 1945.
• Волков Е. А. Численные методы. — М. : Физматлит, 2003.
• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М. : Мир, 1985.
• Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М. : Наука, 1970. — С. 575—576.
• Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — Энергоатомиздат, 1972.
• Максимов Ю. А.,Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М. : МИФИ, 1982.
• Морозов А. Д. Введение в теорию фракталов. — МИФИ, 2002.

На немски език

• P. Deuflhard, A. Hohmann: Numerische Mathematik I. Eine algorithmisch orientierte Einführung. 3. überarbeitete und erweiterte Auflage. De Gruyter, Berlin, New York 2002, ISBN 3-11-017182-1.
• P. Deuflhard: Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms. Springer, Berlin 2004, ISBN 3-540-21099-7 (Reihe: Springer Series in Computational Mathematics, Vol. 35).
• J. M. Ortega, W. C. Rheinboldt: Iterative Solution of Nonlinear Equations in Several Variables. Society for Industrial & Applied Mathematics, 2000, ISBN 0-89871-461-3 (Reihe Classics in Applied Mathematics).
• M. Hermann: Numerische Mathematik, Band 1: Algebraische Probleme. 4., überarbeitete und erweiterte Auflage. Walter de Gruyter Verlag, Berlin und Boston 2020, ISBN 978-3-11-065665-7.

На английски език

• Hazewinkel, Michiel, ed. (2001), Newton method, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4.

Референции

• Xavier Gourdon: Newton’s method and high order iterations, fehlerfreie Darstellung in der Postscript-Datei.
• J. H. Hubbard, D. Schleicher, S. Sutherland: How to Find All Roots of Complex Polynomials by Newton’s Method Preprint (2000), Inventiones Mathematicae vol. 146 (2001).