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

Метод Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.

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

Обоснование

Чтобы численно решить уравнение $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\!$.

Файл:Newton iteration.png

Иллюстрация метода Ньютона (синим изображена функция $f(x)\!$, нуль которой необходимо найти, красным — касательная в точке очередного приближения $x_{n}\!$). Здесь мы можем увидеть, что последующее приближение $x_{n+1}\!$ лучше предыдущего $x_{n}\!$.

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

Основная идея метода заключается в следующем: задаётся начальное приближение вблизи предположительного корня, после чего строится касательная к исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка и берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность.

Пусть $f(x):\;[a,\;b]\to \mathbb {R} \!$ — определённая на отрезке [a, b] и дифференцируемая на нём действительнозначная функция. Тогда формула итеративного исчисления приближений может быть выведена следующим образом:

$f'(x_{n})=\operatorname {tg} \,\alpha ={\frac {\mathrm {\Delta y} }{\mathrm {\Delta x} }}={\frac {f(x_{n})-0}{x_{n}-x_{n+1}}}={\frac {0-f(x_{n})}{x_{n+1}-x_{n}}}\,\!$,

где α — угол наклона касательной в точке $x_{n}\!$.

Следовательно искомое выражение для $x_{n+1}\!$ имеет вид:

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

Итерационный процесс начинается с некого начального приближения $x_{0}$ (чем ближе к нулю, тем лучше, но если предположения о нахождении решения отсутствуют, методом проб и ошибок можно сузить область возможных значений, применив теорему о промежуточных значениях).

Алгоритм

1. Задаются начальным приближением $x_{0}$.
2. Пока не выполнено условие останова, в качестве которого можно взять $|x_{n+1}-x_{n}|<\varepsilon \!$ или $|f(x_{n+1})|<\varepsilon \!$ (то есть погрешность в нужных пределах), вычисляют новое приближение: $x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\!$.

Пример

Иллюстрация применения метода Ньютона к функции $f(x)=\cos {x}-x^{3}$ с начальным приближением в точке $x_{0}=0,5$.
Файл:Newton ex.PNG График последовательных приближений.	Файл:Newton conv.PNG График сходимости.
Согласно способу практического определения скорость сходимости может быть оценена как тангенс угла наклона графика сходимости, то есть в данном случае равна двум.

Рассмотрим задачу о нахождении положительных $x$, для которых $\cos x=x^{3}$. Эта задача может быть представлена как задача нахождения нуля функции $f(x)=\cos x-x^{3}$. Имеем выражение для производной $f^{\prime }(x)=-\sin x-3x^{2}$. Так как $\cos x\leqslant 1$ для всех $x$ и $x^{3}>1$ для $x>1$, очевидно, что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение $x_{0}=0{,}5$, тогда:
${\begin{matrix}x_{1}&=&x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}&=&1{,}112141637097\\x_{2}&=&x_{1}-{\frac {f(x_{1})}{f'(x_{1})}}&=&{\underline {0{,}9}}09672693736\\x_{3}&=&x_{2}-{\frac {f(x_{2})}{f'(x_{2})}}&=&{\underline {0{,}86}}7263818209\\x_{4}&=&x_{3}-{\frac {f(x_{3})}{f'(x_{3})}}&=&{\underline {0{,}86547}}7135298\\x_{5}&=&x_{4}-{\frac {f(x_{4})}{f'(x_{4})}}&=&{\underline {0{,}8654740331}}11\\x_{6}&=&x_{5}-{\frac {f(x_{5})}{f'(x_{5})}}&=&{\underline {0{,}865474033102}}\end{matrix}}$

Подчёркиванием отмечены верные значащие цифры. Видно, что их количество от шага к шагу растёт (приблизительно удваиваясь с каждым шагом): от 1 к 2, от 2 к 5, от 5 к 10, иллюстрируя квадратичную скорость сходимости.

Условия применения

Файл:Newton bad.PNG

Иллюстрация расхождения метода Ньютона, применённого к функции $f(x)=x^{3}-2x+2$ с начальным приближением в точке $x_{0}=0$.

Рассмотрим ряд примеров, указывающих на недостатки метода.

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

• Если начальное приближение недостаточно близко к решению, то метод может не сойтись.

Пусть

$f(x)=x^{3}-2x+2\!$

Тогда

$x_{n+1}=x_{n}-{\frac {x_{n}^{3}-2x_{n}+2}{3x_{n}^{2}-2}}$

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

Файл:Newton ex2.png

График производной функции $f(x)=x+x^{2}\sin(2/x)$ при приближении $x$ к нулю справа.

• Если производная не непрерывна в точке корня, то метод может расходиться в любой окрестности корня.

Рассмотрим функцию:

$f(x)={\begin{cases}0&,\;x=0\\x+x^{2}\sin \left({\frac {2}{x}}\right)&,\;x\neq 0\end{cases}}$

Тогда $f'(0)=1\!$ и $f'(x)=1+2x\sin(2/x)-2\cos(2/x)\!$ всюду, кроме 0.

В окрестности корня производная меняет знак при приближении x к нулю справа или слева. В то время, как: $f(x)\geq x-x^{2}>0\!$ для $0<x<1\!$.

Таким образом $f(x)/f'(x)\!$ не ограничено вблизи корня, и метод будет расходиться, хотя функция всюду дифференцируема, её производная не равна нулю в корне, $f\!$ бесконечно дифференцируема везде, кроме как в корне, а её производная ограничена в окрестности корня.

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

Рассмотрим пример:

$f(x)=x+x^{4/3}\!$

Тогда $f'(x)=1+(4/3)x^{1/3}\!$ и $f''(x)=(4/9)x^{-2/3}\!$ за исключением $x=0\!$, где она не определена.

На очередном шаге имеем $x_{n}\!$,

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}={\frac {(1/3)x_{n}^{4/3}}{(1+(4/3)x_{n}^{1/3})}}\!$

Скорость сходимости полученной последовательности составляет приблизительно 4/3. Это существенно меньше, нежели 2, необходимое для квадратичной сходимости, поэтому в данном случае можно говорить лишь о линейной сходимости, хотя функция всюду непрерывно дифференцируема, производная в корне не равна нулю, и $f\!$ бесконечно дифференцируема везде, кроме как в корне.

• Если производная в точке корня равна нулю, то скорость сходимости не будет квадратичной, а сам метод может преждевременно прекратить поиск, и дать неверное для заданной точности приближение.

Пусть

$f(x)=x^{2}\!$

Тогда $f'(x)=2x\!$ и следовательно $x-f(x)/f'(x)=x/2\!$. Таким образом сходимость метода не квадратичная, а линейная, хотя функция всюду бесконечно дифференцируема.

Ограничения

Пускай задано уравнение $f(x)=0\!$, где $f(x):\;\mathbb {X} \to \mathbb {R} \!$ и надо найти его решение.

Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Она носит имя советского математика и экономиста, лауреата Нобелевской премии по экономике 1975 года «за вклад в теорию оптимального распределения ресурсов» Леонида Витальевича Канторовича (1912—1986) и является одной из многочисленных теорем, ставших результатами его научных изысканий.

Теорема Канторовича.

Если существуют такие константы $A,B,C\!$, что:

1. ${\frac {1}{|f'(x)|}}<A\!$ на $[a,\;b]\!$, то есть $f'(x)\!$ существует и не равна нулю;
2. $\left|{\frac {f(x)}{f'(x)}}\right|<B\!$ на $[a,\;b]\!$, то есть $f(x)\!$ ограничена;
3. $\exists f''(x)\!$ на $[a,\;b]\!$, и $|f''(x)|\leq C\leq {\frac {1}{2AB}}\!$;

Причём длина рассматриваемого отрезка $|a-b|<{\frac {1}{AB}}\left(1-{\sqrt {1-2ABC}}\right)\!$. Тогда справедливы следующие утверждения:

1. на $[a,\;b]\!$ существует корень $x^{*}$ уравнения $f(x)=0:\quad \exists x^{*}\in [a,\;b]:f(x^{*})=0\!$;
2. если $x_{0}={\frac {a+b}{2}}\!$, то итерационная последовательность сходится к этому корню: $\left\{x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\right\}\to x^{*}\!$;
3. погрешность может быть оценена по формуле $|x^{*}-x_{n}|\leq {\frac {B}{2^{n-1}}}(2ABC)^{2^{n-1}}\!$.

Из последнего из утверждений теоремы в частности следует квадратичная сходимость метода:

$|x^{*}-x_{n}|\leq {\frac {B}{2^{n-1}}}(2ABC)^{2^{n-1}}={\frac {1}{2}}{\frac {B}{2^{n-2}}}\left((2ABC)^{2^{n-2}}\right)^{2}=\alpha |x^{*}-x_{n-1}|^{2}\!$

Тогда ограничения на исходную функцию $f(x)\!$ будут выглядеть так:

1. функция должна быть ограничена;
2. функция должна быть гладкой, дважды дифференцируемой;
3. её первая производная $f'(x)$ равномерно отделена от нуля;
4. её вторая производная $f''(x)\!$ должна быть равномерно ограничена.

Историческая справка

Метод был описан Исааком Ньютоном в рукописи De analysi per aequationes numero terminorum infinitas (лат. Об анализе уравнениями бесконечных рядов), адресованной в 1669 году Барроу, и в работе De metodis fluxionum et serierum infinitarum (лат. Метод флюксий и бесконечные ряды) или Geometria analytica (лат. Аналитическая геометрия) в собраниях трудов Ньютона, которая была написана в 1671 году. В своих работах Ньютон вводит такие понятия, как разложение функции в ряд, бесконечно малые и флюксии (производные в нынешнем понимании). Указанные работы были изданы значительно позднее: первая вышла в свет в 1711 году благодаря Уильяму Джонсону, вторая была издана Джоном Кользоном в 1736 году уже после смерти создателя. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения $x_{n}$, а последовательность полиномов и в результате получал приближённое решение $x$.

Впервые метод был опубликован в трактате Алгебра Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе Analysis aequationum universalis (лат. Общий анализ уравнений). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений $x_{n}$ вместо более трудной для понимания последовательности полиномов, использованной Ньютоном. Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.

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

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

Файл:Newton mod.PNG

Иллюстрация последовательных приближений метода одной касательной, применённого к функции $f(x)=e^{x}-2$ с начальным приближением в точке $x_{0}=1,8$.

Метод одной касательной

В целях уменьшения числа обращений к значениям производной функции применяют так называемый метод одной касательной.

Формула итераций этого метода имеет вид

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

Суть метода заключается в том, чтобы вычислять производную лишь один раз, в точке начального приближения $x_{0}\!$, а затем использовать это значение на каждой последующей итерации:

$\alpha (x)=\alpha _{0}=-{\dfrac {1}{f'(x_{0})}}\!$.

При таком выборе $\alpha _{0}\!$ в точке $x_{0}\!$ выполнено равенство

$\displaystyle {\varphi }'(x_{0})=1+\alpha _{0}f'(x_{0})=0,\!$

и если отрезок, на котором предполагается наличие корня $x^{*}\!$ и выбрано начальное приближение $x_{0}\!$, достаточно мал, а производная ${\varphi }'(x)\!$ непрерывна, то значение ${\varphi }'(x^{*})\!$ будет не сильно отличаться от ${\varphi }'(x_{0})=0\!\!$ и, следовательно, график $y={\varphi }(x)\!$ пройдёт почти горизонтально, пересекая прямую $y=x\!$, что в свою очередь обеспечит быструю сходимость последовательности точек приближений к корню.

Этот метод можно также рассматривать, как модернизацию метода хорд (секущих), где число ${\gamma }\!$ следует выбрать равным $\max \limits _{x}\vert {\varphi }'(x)\vert \!$.

Многомерный случай

Обобщим полученный результат на многомерный случай. Пускай необходимо найти решение системы:

$\left\{{\begin{array}{lcr}f_{1}(x_{1},x_{2},\ldots ,x_{n})&=&0\\\ldots &&\\f_{n}(x_{1},x_{2},\ldots ,x_{n})&=&0\end{array}}\right.$

Выбирая некоторое начальное значение ${\vec {x}}^{[0]}\!$, последовательные приближения ${\vec {x}}^{[j+1]}\!$ находят путём решения систем уравнений:

$f_{i}+\sum _{k=1}^{n}{\frac {\partial f_{i}}{\partial x_{k}}}({\vec {x}}_{k}^{[j+1]}-{\vec {x}}_{k}^{[j]})=0,\quad i=1,2,\ldots ,n\!$,

где ${\vec {x}}^{[j]}=\left(x_{1}^{[j]},x_{2}^{[j]},\ldots ,x_{n}^{[j]}\right),\quad j=0,1,2,\ldots \!$.

Применительно к задачам оптимизации

Пускай необходимо найти минимум функции многих переменных $f({\vec {x}}):\mathbb {R} ^{n}\to \mathbb {R} \!$. Эта задача равносильна задаче нахождения нуля градиента $\nabla f({\vec {x}})\!$. Применим изложенный выше метод Ньютона:

$\nabla f({\vec {x}}^{[j]})+H({\vec {x}}^{[j]})({\vec {x}}^{[j+1]}-{\vec {x}}^{[j]})=0,\quad j=1,2,\ldots ,n\!$,

где $H({\vec {x}})\!$ — гессиан функции $f({\vec {x}})\!$.

В более удобном итеративном виде это выражение выглядит так:

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

Следует отметить, что в случае квадратичной функции метод Ньютона находит экстремум за одну итерацию.

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

Метод Ньютона-Рафсона является улучшением метода Ньютона нахождения экстремума, описанного выше. Основное отличие заключается в том, что на очередной итерации каким-либо из методов одномерной оптимизации выбирается оптимальный шаг:

${\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\!$ шагов, либо не обновляют вовсе.

Файл:Newtroot 1 0 0 0 0 m1.png

Бассейны Ньютона для полинома пятой степени $p(x)=x^{5}-1$. Разными цветами закрашены области притяжения для разных корней. Более тёмные области соответствуют большему числу итераций.

Обобщение на комплексную плоскость

До сих пор в описании метода использовались функции, осуществляющие отображения в пределах множества действительных значений. Однако метод может быть применён и для нахождения нуля функции комплексного переменного. При этом процедура остаётся неизменной:

$z_{n+1}=z_{n}-{\frac {f(z_{n})}{f'(z_{n})}}\!$

Особый интерес представляет выбор начального приближения $z_{0}\!$. Ввиду того, что функция может иметь несколько нулей, в различных случаях метод может сходиться к различным значениям, и вполне естественно возникает желание выяснить, какие области обеспечат сходимость к тому или иному корню. Этот вопрос заинтересовал Артура Кейли ещё в 1879 году, однако разрешить его смогли лишь в 70-х годах двадцатого столетия с появлением вычислительной техники. Оказалось, что на пересечениях этих областей (их принято называть областями притяжения) образуются так называемые фракталы — бесконечные самоподобные геометрические фигуры.

Ввиду того, что Ньютон применял свой метод исключительно к полиномам, фракталы, образованные в результате такого применения, обрели название фракталов Ньютона или бассейнов Ньютона.

Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.

1. Амосов А.А., Дубинский Ю. А., Копченова Н.П. Вычислительные методы для инженеров. — М.: Мир, 1998.

1. Бахвалов Н.С., Жидков Н.П., Кобельков Г.Г. Численные методы. — 8-е изд.. — М.: Лаборатория Базовых Знаний, 2000.

1. Вавилов С. И. Исаак Ньютон. — М.: Изд. АН СССР, 1945.

1. Волков Е.А. Численные методы. — М.: Физматлит, 2003.

1. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.

1. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.

1. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — Энергоатомиздат, 1972.

1. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.

1. Морозов А.Д. Введение в теорию фракталов. — МИФИ, 2002.

См. также

• Метод простой итерации
• Метод секущих
• Метод хорд
• Метод Чебышева
• Фрактал
• Численное решение уравнений

Ссылки

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

---

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Метод Ньютона. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

---