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

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

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

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

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

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

Извеждане

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

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

${\phi }^{\prime }(x^{\ast })=1+{\alpha }^{\prime }(x^{\ast })f(x^{\ast })+\alpha (x^{\ast })f^{\prime }(x^{\ast })=0.$

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

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

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

$\phi (x)=x-\frac{f(x)}{f^{\prime }(x)}.$

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

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

$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}.$

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

Алгоритъм

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

Примери

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

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

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

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

с производна $f^{\prime }(x)=2x.$

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

$\begin{array}{ccccccc}{x}_1& =& x_0-\frac{f(x_0)}{f^{\prime }(x_0)}& =& 10-\frac{10^2-612}{2\cdot 10}& =& 35,6\\ x_2& =& x_1-\frac{f(x_1)}{f^{\prime }(x_1)}& =& 35,6-\frac{35,6^2-612}{2\cdot 35,6}& =& \underset{\_}{2}6,3955056\\ x_3& =& ⋮& =& ⋮& =& \underset{\_}{24,7}906355\\ x_4& =& ⋮& =& ⋮& =& \underset{\_}{24,7386}883\\ x_5& =& ⋮& =& ⋮& =& \underset{\_}{24,7386338}\end{array}$

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

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

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

$\begin{array}{ccccccc}{x}_1& =& x_0-\frac{f(x_0)}{f^{\prime }(x_0)}& =& 0,5-\frac{\cos (0,5)-(0,5{)}^3}{-\sin (0,5)-3(0,5{)}^2}& =& 1,112141637097\\ x_2& =& x_1-\frac{f(x_1)}{f^{\prime }(x_1)}& =& ⋮& =& \underset{\_}{0,}909672693736\\ x_3& =& ⋮& =& ⋮& =& \underset{\_}{0,86}7263818209\\ x_4& =& ⋮& =& ⋮& =& \underset{\_}{0,86547}7135298\\ x_5& =& ⋮& =& ⋮& =& \underset{\_}{0,8654740331}11\\ x_6& =& ⋮& =& ⋮& =& \underset{\_}{0,865474033102}\end{array}$

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

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

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

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

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

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

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

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

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

където ${\lambda }_j=\arg \underset{\lambda }{min}f({\overrightarrow{x}}^{[j]}-\lambda H^{-1}({\overrightarrow{x}}^{[j]})\mathrm{\nabla }f({\overrightarrow{x}}^{[j]})).$ За оптимизиране на изчисленията се прилага следното подобрение: вместо да се преизчислява хесианът на целевата функция при всяка итерация, те се ограничават до началното приближение $H(f({\overrightarrow{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).