Методът на Нютон (известен също като метод на допирателните) е итерационен числен метод (алгоритъм) за намиране на приблизителни стойности на корените на реални функции. Той използва поредица от последователни все по-точни приближения, до достигане на търсената точност на решението. Започва се със стойност, относително близка до истинското решение. Функцията се замества с нейната допирателна в тази точка и се изчислява стойността на аргумента, при която допирателната пресича нулевата линия. Тази точка се приема за нова изходна стойност и методът се повтаря итеративно.
Описание на метода Геометрична интерпретация
Основната идея на метода е следната: задава се начално приближение близо до предполагаемия корен, след което в точката на приближение се построява допирателна към графиката на изследваната функция, за която се намира пресечната точка с абцисната ос близо до предполагаемия корен. Тази точка се приема за ново приближение и в точката на приближение се построява нова допирателна към графиката на функцията, която пресича оста в следващата точка на приближение . Процесът продължава докато се постигне необходимата точност.
Извеждане За да се реши числено уравнението с помощта на проста итерация, то трябва да се преобразува в еквивалентно уравнение: , където е свиващо се изображениеСвиващото се изображение е изображение на метрично пространство върху себе си, което намалява разстоянието между произволни точки в някакъв силен смисъл..
За най-добра сходимост на метода, в точката на следващото приближение трябва да бъде изпълнено условието . Решението на това уравнение се търси във вида , тогава:
Ако се приеме, че точката на приближение е „достатъчно близо“ до корена и че дадената функция е непрекъсната , крайната формула за е:
Като се отчете това, функцията се определя като
При определени условия тази функция извършва свиващо се изображение в околността на корена.
В този случай, алгоритъмът за намиране на числено решение на уравнението се свежда до проста итеративна процедура за изчисление (метод на последователните приближения):
Съгласно теоремата на БанахТеоремата на Банах за неподвижната точка е твърдение в метричната геометрия, което гарантира съществуването и уникалността на неподвижна точка за определен клас изображения на метрични пространства. Тя съдържа и конструктивен метод за намиране на тази точка., последователността от приближения се стреми към корена на уравнението .
Алгоритъм Записват се изразите за функцията и първата ѝ производна . Задават се желаната точност на изчисление като абсолютна грешка (тъй като методът на Нютон е частен случай на метода на простата итерация) и началното приближение . Определят се стойностите на функцията и първата ѝ производна . Изчислява се ново приближение докато не се изпълни условието за спиране .
Примери Квадратен корен от число Разглежда се задачата за намиране на квадратен корен от число. Има много начини за изчисляването на корени и Нютоновият метод е един от тях.
Например, ако трябва да се намери квадратен корен от 612, това е еквивалентно на намирането на решенията на уравнението
Тогава функцията, която се използва за метода на Нютон е
с производна
При избрана начална стойност , редицата получена по метода на Нютон е
Подчертаните цифри са коректни числа. Само с няколко итерации може да се намери решение, с точност много цифри след запетаята.
Решение на неполиномни уравнения Разглежда се задачата за намиране на положителното число x, удовлетворяващо уравнението . Уравнението се записва във вида и се търсят корените му. Първата производна е . Тъй като за всяко , от уравнението следва, че и и , т.е. търсеният корен се намира между 0 и 1. Избира се, примерно начална стойност . (Забележете, че при начална стойност 0 ще се получи неопределен резултат, което показва важността от използването на начална точка, която е близо до нулата.)
Верните числа са подчертани в примера по-горе. В частност x6 е с точност до всички показани позиции след запетаята. Вижда се, че броят на правилните числа след десетичната точка нараства от 2 (за x3) до 5 и 10, показвайки квадратната сходимост.
Условия на приложение Има редица примери, посочващи недостатъците на метода.
Контрапримери Ако началното приближение не е достатъчно близко до решението, методът може да не се сближи. Ако производната не е непрекъсната в коренната точка, методът може да се отклони във всяка околност на корена. Ако втората производна не съществува в коренната точка, скоростта на сходимост на метода може да бъде значително намалена. Ако производната в коренната точка е нула, скоростта на сходимост няма да бъде квадратична и самият метод може да прекрати търсенето преждевременно и да доведе до приближение, което е неправилно за дадената точност.
Ограничения
Теорема на Канторович
Обобщения и модификации
Метод на секущата Метод на единичната тангента Метод на Нютон – Фурие Многомерен случай Приложен към оптимизационни задачи Метод на Нютон – Рафсон Методът на Нютон-Рафсон е подобрение на метода на Нютон за намиране на екстремум, описан по-горе. Основната разлика е, че при следващата итерация един от методите за едномерна оптимизация избира оптималната стъпка:
където За оптимизиране на изчисленията се прилага следното подобрение: вместо да се преизчислява хесианът на целевата функция при всяка итерация, те се ограничават до началното приближение и го актуализират само веднъж на всеки стъпки или изобщо не го актуализират.
Приложен към задачи с най-малки квадрати Метод на Гаус – Нютон
Обобщение към комплексната равнина
Реализация
Вижте също Нютонов фрактал Алгоритъм на Гаус – Нютон Двоично търсене Дихотомия
Източници и бележки
Външни препратки «Бассейны Ньютона» на сайте 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).
Категория:Алгоритми Категория:Приложна математика Категория:Числени методи