Вики-текст старой страницы до правки (old_wikitext) | '{{другие значения|Метод (значения)}}
'''Метод Ньютона''', '''алгоритм Ньютона''' (также известный как '''метод касательных''') — это итерационный [[Численные методы|численный метод]] нахождения корня ([[нуль функции|нуля]]) заданной [[Функция (математика)|функции]]. Метод был впервые предложен английским [[физик]]ом, [[математик]]ом и [[астроном]]ом [[Ньютон, Исаак|Исааком Ньютоном]] ([[1643]]—[[1727]]). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах [[метод простой итерации|простой итерации]]. Метод обладает квадратичной [[скорость сходимости|сходимостью]]. Модификацией метода является [[метод хорд и касательных]]. Также метод Ньютона может быть использован для решения [[задача оптимизации|задач оптимизации]], в которых требуется определить ноль первой [[Производная функции|производной]] либо [[градиент (математика)|градиента]] в случае многомерного пространства.
{{TOChidden}}
== Описание метода ==
=== Обоснование ===
Чтобы численно решить уравнение <math>f(x)=0</math> [[метод простой итерации|методом простой итерации]], его необходимо привести к эквивалентному уравнению: <math>x=\varphi(x)</math>, где <math>\varphi</math> — [[сжимающее отображение]].
Для наилучшей [[скорость сходимости|сходимости]] метода в точке очередного приближения <math>x^*</math> должно выполняться условие <math>\varphi'(x^*)=0</math>. Решение данного уравнения ищут в виде <math>\varphi(x)=x+\alpha(x)f(x)</math>, тогда:
: <math>\varphi'(x^*)=1+\alpha'(x^*)f(x^*)+\alpha(x^*) f'(x^*)=0.</math>
В предположении, что точка приближения «достаточно близка» к корню <math>\tilde{x}</math> и что заданная функция [[непрерывное отображение|непрерывна]] <math>(f(x^*)\approx f(\tilde{x})=0)</math>, окончательная формула для <math>\alpha(x)</math> такова:
: <math>\alpha(x)=-\frac{1}{f'(x)}.</math>
С учётом этого [[Функция (программирование)|функция]] <math>\varphi(x)</math> определяется:
: <math>\varphi(x)=x-\frac{f(x)}{f'(x)}.</math>
При некоторых условиях эта функция в окрестности корня осуществляет сжимающее отображение.
{{Доказательство|Пусть дана [[Функция (программирование)|функция]] [[вещественное число|вещественного переменного]] дважды [[непрерывная дифференцируемость|непрерывно дифференцируемая]] в своей [[Область определения функции|области определения]], [[Производная функции|производная]] которой нигде не обращается в нуль:
: <math>\scriptstyle{f(x)\colon\mathbb{X}\to\R,\;f(x)\in\mathrm{C}^2(\mathbb{X});\quad\forall x\in\mathbb{X}\;f'(x)\neq 0.}</math>
И необходимо доказать, что функция <math>\scriptstyle{\varphi(x)=x-\frac{f(x)}{f'(x)}}</math> осуществляет сжимающее отображение вблизи корня уравнения <math>\scriptstyle{f(x)=0}</math>.
В силу [[непрерывная дифференцируемость|непрерывной дифференцируемости]] функции <math>\scriptstyle{f(x)}</math> и неравенства нулю её первой [[Производная функции|производной]] <math>\scriptstyle{\varphi(x)}</math> [[непрерывная функция|непрерывна]].
Производная <math>\scriptstyle{\varphi'(x)}</math> равна:
: <math>\scriptstyle{\varphi'(x)=\frac{f(x)f''(x)}{\left(f'(x)\right)^2}.}</math>
В условиях, наложенных на <math>\scriptstyle{f(x)}</math>, она также непрерывна. Пусть <math>\scriptstyle{\tilde{x}}</math> — искомый корень уравнения: <math>\scriptstyle{f(\tilde{x})=0}</math>, следовательно в его окрестности <math>\scriptstyle{\varphi'(x)\approx 0}</math>:
: <math>\scriptstyle{\forall\varepsilon\colon 0<\varepsilon<1,\;\exist\delta>0\;\forall x\in\mathbb{X}\;|x-\tilde{x}|<\delta\colon|\varphi'(x)-0|<\varepsilon.}</math>
Тогда согласно [[формула конечных приращений|теореме Лагранжа]]:
: <math>\scriptstyle{\forall x_1,\;x_2\in\mathrm{U}_\delta(\tilde{x})\;\exist\xi\in\mathrm{U}_\delta(\tilde{x})\colon|\varphi(x_1)-\varphi(x_2)|=|\varphi'(\xi)| |x_1-x_2|<\varepsilon|x_1-x_2|.}</math>
В силу того, что <math>\scriptstyle{\varphi(\tilde{x})=\tilde{x}}</math> в этой же дельта окрестности выполняется:
: <math>\scriptstyle{\forall x\in U_{\delta}(\tilde{x})\colon\;|\varphi(x)-\tilde{x}|<\varepsilon|x-\tilde{x}|.}</math>
Таким образом полученная функция <math>\scriptstyle{\varphi(x)}</math> в окрестности корня <math>\scriptstyle{U_\delta(\tilde{x})}</math> осуществляет [[сжимающее отображение]].</small>}}
В этом случае алгоритм нахождения численного решения уравнения <math>f(x)=0</math> сводится к [[Метод простой итерации|итерационной процедуре вычисления]]:
: <math>x_{n+1}=x_{n}-\frac{f(x_n)}{f'(x_n)}.</math>
По [[теорема Банаха|теореме Банаха]] последовательность приближений стремится к корню уравнения <math>f(x)=0</math>.
[[Файл:Newton iteration.svg|thumb|left|300px|Иллюстрация метода Ньютона (синим изображена функция <math>\scriptstyle{f(x)}</math>, ноль которой необходимо найти, красным — касательная в точке очередного приближения <math>\scriptstyle{x_n}</math>). Здесь мы можем увидеть, что последующее приближение <math>\scriptstyle{x_{n+1}}</math> лучше предыдущего <math>\scriptstyle{x_n}</math>.]]
=== Геометрическая интерпретация ===
Основная идея метода заключается в следующем: задаётся начальное приближение вблизи предположительного корня, после чего строится касательная к графику исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность.
'''Пусть''' 1) вещественнозначная функция <math>f(x)\colon(a,\,b)\to\R</math> непрерывно [[Дифференцируемая функция|дифференцируема]] на интервале <math>(a,\,b)</math> ; <br>
2) существует искомая точка <math>x^{*}\in (a,\,b)</math> : <math>f(x^{*})= 0</math> ; <br>
3) существуют <math>C > 0</math> и <math>\delta > 0</math> такие, что <br>
<math>\vert f'(x) \vert \geqslant C</math>
для <math>x\in(a,\,x^{*}-\delta ] \cup [ x^{*}+\delta,\,b)</math> <br>
и <math>f'(x)\ne 0</math>
для <math>x\in(x^{*}-\delta,\, x^{*})\cup(x^{*},\, x^{*}+\delta )</math> ; <br>
4) точка <math>x_n \in (a,\,b)</math> такова, что <math>f(x_n)\ne 0</math> . <br>
'''Тогда''' формула итеративного приближения <math>x_n</math> к <math>x^{*}</math>
может быть выведена из геометрического смысла касательной следующим образом:
: <math>f'(x_n)=\mathrm{tg}\,\alpha_{n} = \frac{\Delta y}{\Delta x} = \frac{f(x_n)-0}{x_n-x_{n+1}} = \frac{0-f(x_n)}{x_{n+1}-x_n},</math>
где <math>\alpha_{n}</math> — угол наклона касательной прямой
<math>y(x)=f(x_n) + (x - x_n) \cdot \mathrm{tg}\,\alpha_{n}</math>
к графику <math>f</math>
в точке <math>(x_n;f(x_n))</math> .
Следовательно (в уравнении касательной прямой полагаем <math>y(x_{n+1})=0</math>) искомое выражение для <math>x_{n+1}</math> имеет вид :
: <math>x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.</math>
Если <math>x_{n+1} \in (a,\,b)</math>, то это значение можно использовать в качестве следующего приближения к
<math>x^{*}</math> .
Если <math>x_{n+1} \notin (a,\,b)</math>, то имеет место «перелёт» (корень <math>x^{*}</math> лежит рядом с границей <math>(a,\,b)</math>). В этом случае надо (воспользовавшись идеей [[Метод бисекции|метода половинного деления]]) заменять
<math>x_{n+1}</math> на
<math>\frac{x_{n}+x_{n+1}}{2}</math>
до тех пор, пока точка «не вернётся» в область поиска
<math>(a,\,b)</math> .
'''Замечания.''' 1) Наличие непрерывной производной даёт возможность строить непрерывно меняющуюся касательную на всей области поиска решения <math>(a,\,b)\;</math> . <br>
2) Случаи граничного (в точке <math>a</math> или в точке <math>b</math>) расположения искомого решения <math>x^{*}</math> рассматриваются аналогичным образом. <br>
3) С геометрической точки зрения равенство
<math>f'(x_n)= 0</math>
означает, что касательная прямая к графику
<math>f</math>
в точке
<math>(x_n;f(x_n))</math> -
параллельна оси
<math>OX</math>
и при
<math>f(x_n)\ne 0</math>
не пересекается с ней в конечной части. <br>
4) Чем больше константа <math>C > 0</math> и чем меньше константа <math>\delta > 0</math> из пункта 3 условий,
тем для <math>x_{n}\in(a,\,x^{*}-\delta ] \cup [ x^{*}+\delta,\,b)</math>
пересечение касательной к графику <math>f</math> и оси <math>OX</math> ближе к точке <math>(x^{*};\;0)</math> ,
то есть тем ближе значение <math>x_{n+1}</math> к искомой <math>x^{*}\in (a,\,b)</math> .
Итерационный процесс '''начинается''' с некоторого начального приближения
<math>x_0 \in (a,\,b)</math> ,
причём между
<math>x_0 \in (a,\,b)</math>
и искомой точкой
<math>x^{*}\in (a,\,b)</math>
не должно быть других нулей функции
<math>f</math> ,
то есть «чем ближе <math>x_0</math>
к искомому корню <math>x^{*}</math> ,
тем лучше». Если предположения о нахождении <math>x^{*}</math> отсутствуют, методом проб и ошибок можно сузить область возможных значений, применив [[теорема о промежуточных значениях|теорему о промежуточных значениях]].
Для предварительно заданных <math>\varepsilon_{x} >0</math> , <math>\varepsilon_{f} >0</math>
итерационный процесс '''завершается''' если
<math>\left \vert \frac{f(x_n)}{f'(x_n)} \right \vert \approx \vert x_{n+1}-x_n \vert <\varepsilon_{x}</math> и
<math> \vert f(x_{n+1})\vert <\varepsilon_{f}</math> . <br>
В частности, для матрицы дисплея <math>\varepsilon_{x}</math> и <math>\varepsilon_{f}</math> могут быть рассчитаны,
исходя из масштаба отображения графика <math>f</math> ,
то есть если <math>x_n</math> и <math>x_{n+1}</math> попадают в один вертикальный, а <math>f(x_n)</math> и <math>f(x_{n+1})</math> в один горизонтальный ряд.
=== Алгоритм ===
# Задается начальное приближение <math>x_0</math>.
# Пока не выполнено условие остановки, в качестве которого можно взять <math>|x_{n+1}-x_n|<\varepsilon</math> или <math>|f(x_{n+1})|<\varepsilon</math> (то есть погрешность в нужных пределах), вычисляют новое приближение: <math>x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}</math>.
=== Пример ===
{| class="toccolours" style="float: right; font-size: 85%; background:white; color:black; width:50em; maxwidth=60%"
!colspan=2| Иллюстрация применения метода Ньютона к функции <math>f(x)=\cos x-x^3</math> с начальным приближением в точке <math>x_0=0{,}5</math>.
|-
|[[Файл:Newton ex.PNG|thumb|300px|center|График последовательных приближений.]]
|[[Файл:Newton conv.PNG|thumb|300px|center|График сходимости.]]
|-
|colspan=2| Согласно [[скорость сходимости|способу практического определения]] скорость сходимости может быть оценена как тангенс угла наклона графика сходимости, то есть в данном случае равна двум.
|}
Рассмотрим задачу о нахождении положительных <math>x</math>, для которых <math>\cos x=x^3</math>. Эта задача может быть представлена как задача нахождения нуля функции <math>f(x)=\cos x-x^3</math>. Имеем выражение для [[Производная функции|производной]] <math>f'(x)=-\sin x-3x^2</math>. Так как <math>\cos x\leqslant 1</math> для всех <math>x</math> и <math>x^3>1</math> для <math>x>1</math>, [[Теорема Больцано — Коши|очевидно]], что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение <math>x_0 = 0{,}5</math>, тогда:
: <math>\begin{matrix}
x_1 & = & x_0-\dfrac{f(x_0)}{f'(x_0)} & = & 1{,}112\;141\;637\;097, \\
x_2 & = & x_1-\dfrac{f(x_1)}{f'(x_1)} & = & \underline{0{,}}909\;672\;693\;736, \\
x_3 & = & x_2-\dfrac{f(x_2)}{f'(x_2)} & = & \underline{0{,}86}7\;263\;818\;209, \\
x_4 & = & x_3-\dfrac{f(x_3)}{f'(x_3)} & = & \underline{0{,}865\;47}7\;135\;298, \\
x_5 & = & x_4-\dfrac{f(x_4)}{f'(x_4)} & = & \underline{0{,}865\;474\;033\;1}11, \\
x_6 & = & x_5-\dfrac{f(x_5)}{f'(x_5)} & = & \underline{0{,}865\;474\;033\;102}.
\end{matrix}</math>
Подчёркиванием отмечены верные [[значащие цифры]]. Видно, что их количество от шага к шагу растёт (приблизительно удваиваясь с каждым шагом): от 1 к 2, от 2 к 5, от 5 к 10, иллюстрируя квадратичную [[скорость сходимости]].
<!-- === Псевдокод ===
Приведём псевдокод для указанного примера.
<source lang="С"> '''function''' newtonIterationFunction(x) {
'''return''' x - (cos(x) - x^3) / (-sin(x) - 3*x^2)
}
'''var''' x := 0.5
'''for''' i '''from''' 0 '''to''' 99 {
print "Итерация: " + i
print "Приближение: " + x
xold := x
x := newtonIterationFunction(x)
'''if''' x = xold {
print "Решение найдено!"
'''break'''
}
}
</source>-->
== Условия применения ==
[[Файл:Newton bad.PNG|thumb|300px|left|Иллюстрация расхождения метода Ньютона, применённого к функции <math>\scriptstyle{f(x)=x^3-2x+2}</math> с начальным приближением в точке <math>\scriptstyle{x_0=0}</math>.]]
Рассмотрим ряд примеров, указывающих на недостатки метода.
=== Контрпримеры ===
*; Если начальное приближение недостаточно близко к решению, то метод может не сойтись.
Пусть
: <math>f(x)=x^3-2x+2.</math>
Тогда
: <math>x_{n+1}=x_{n}-\frac{x_n^3-2x_n+2}{3x_n^2-2}.</math>
Возьмём ноль в качестве начального приближения. Первая итерация даст в качестве приближения единицу. В свою очередь, вторая снова даст ноль. Метод зациклится и решение не будет найдено. В общем случае построение последовательности приближений может быть [[каскад бифуркаций|очень запутанным]].
[[Файл:Newton ex2.png|thumb|350px|График производной функции <math>\scriptstyle{f(x)=x+x^2\sin(2/x)}</math> при приближении <math>\scriptstyle{x}</math> к нулю справа.]]
*; Если [[Производная функции|производная]] не [[непрерывное отображение|непрерывна]] в точке корня, то метод может расходиться в любой [[окрестность|окрестности]] корня.
Рассмотрим функцию:
: <math>f(x)=\begin{cases}
0, & x=0, \\
x+x^2\sin\left(\dfrac{2}{x}\right), & x\neq 0.
\end{cases}</math>
Тогда <math>f'(0)=1</math> и <math>f'(x)=1+2x\sin(2/x)-2\cos(2/x)</math> всюду, кроме 0.
В окрестности корня производная меняет знак при приближении <math>x</math> к нулю справа или слева. В то время, как <math>f(x)\geqslant x-x^2>0</math> для <math>0<x<1</math>.
Таким образом <math>f(x)/f'(x)</math> не ограничено вблизи корня, и метод будет расходиться, хотя функция всюду дифференцируема, её производная не равна нулю в корне, <math>f</math> [[аналитическая функция|бесконечно дифференцируема]] везде, кроме как в корне, а её производная ограничена в окрестности корня.
*; Если не существует вторая [[Производная функции|производная]] в точке корня, то [[скорость сходимости]] метода может быть заметно снижена.
Рассмотрим пример:
: <math>f(x)=x+x^{4/3}.</math>
Тогда <math>f'(x)=1+(4/3)x^{1/3}</math> и <math>f''(x)=(4/9)x^{-2/3}</math> за исключением <math>x=0</math>, где она не определена.
На очередном шаге имеем <math>x_n</math>:
: <math>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})}.</math>
[[Скорость сходимости]] полученной последовательности составляет приблизительно 4/3. Это существенно меньше, нежели 2, необходимое для квадратичной сходимости, поэтому в данном случае можно говорить лишь о линейной сходимости, хотя функция всюду [[непрерывная дифференцируемость|непрерывно дифференцируема]], производная в корне не равна нулю, и <math>f</math> бесконечно дифференцируема везде, кроме как в корне.
*; Если производная в точке корня равна нулю, то [[скорость сходимости]] не будет квадратичной, а сам метод может преждевременно прекратить поиск, и дать неверное для заданной точности приближение.
Пусть
: <math>f(x)=x^2.</math>
Тогда <math>f'(x)=2x</math> и следовательно <math>x-f(x)/f'(x)=x/2</math>. Таким образом сходимость метода не квадратичная, а линейная, хотя функция всюду бесконечно дифференцируема.
=== Ограничения ===
Пусть задано уравнение <math>f(x)=0</math>, где <math>f(x)\colon\mathbb{X}\to\R</math> и надо найти его решение.
Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Она носит имя советского [[математик]]а и [[экономист]]а [[Канторович, Леонид Витальевич|Леонида Витальевича Канторовича]] ([[1912]]—[[1986]]).
'''Теорема Канторовича.'''
''Если существуют такие константы <math>A,\;B,\;C</math>, что:''
# ''<math>\frac{1}{|f'(x)|}<A</math> на <math>[a,\;b]</math>, то есть <math>f'(x)</math> сут и не равна нулю;''
# ''<math>\left|\frac{f(x)}{f'(x)}\right|<B</math> на <math>[a,\;b]</math>, то есть <math>f(x)</math> ограничена;''
# ''<math>\exist f''(x)</math> на <math>[a,\;b]</math>, и <math>|f''(x)|\leqslant C\leqslant\frac{1}{2AB}</math>;''
''Причём длина рассматриваемого отрезка <math>|a-b|<\frac{1}{AB}\left(1-\sqrt{1-2ABC}\right)</math>. Тогда справедливы следующие утверждения:''
# ''на <math>[a,\;b]</math> существует корень <math>x^*</math> уравнения <math>f(x)=0\colon\exist x^*\in[a,\;b]\colon f(x^*)=0</math>;''
# ''если <math>x_0=\frac{a+b}{2}</math>, то итерационная [[последовательность]] сходится к этому корню: <math>\left\{ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\right\}\to x^*</math>;''
# ''погрешность может быть оценена по формуле <math>|x^*-x_n|\leqslant\frac{B}{2^{n-1}}(2ABC)^{2^{n-1}}</math>.''
Из последнего из утверждений теоремы в частности следует квадратичная [[скорость сходимости|сходимость]] метода:
: <math>|x^*-x_n|\leqslant\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.</math>
Тогда ограничения на исходную функцию <math>f(x)</math> будут выглядеть так:
# функция должна быть ограничена;
# функция должна быть [[гладкая функция|гладкой]], дважды [[дифференцируемая функция|дифференцируемой]];
# её первая [[Производная функции|производная]] <math>f'(x)</math> равномерно отделена от нуля;
# её вторая производная <math>f''(x)</math> должна быть равномерно ограничена.
== Историческая справка ==
Метод был описан [[Ньютон, Исаак|Исааком Ньютоном]] в рукописи «Об анализе уравнениями бесконечных рядов» ({{lang-la|«De analysi per aequationes numero terminorum infinitas»}}), адресованной в [[1669 год]]у [[Барроу, Исаак|Барроу]], и в работе «Метод флюксий и бесконечные ряды» ({{lang-la|«De metodis fluxionum et serierum infinitarum»}}) или «Аналитическая геометрия» ({{lang-la|«Geometria analytica»}}) в собраниях трудов Ньютона, которая была написана в [[1671 год]]у. В своих работах Ньютон вводит такие понятия, как разложение [[Функция (программирование)|функции]] в [[Ряд (математика)|ряд]], [[бесконечно малая величина|бесконечно малые]] и флюксии ([[Производная функции|производные]] в нынешнем понимании). Указанные работы были изданы значительно позднее: первая вышла в свет в [[1711 год]]у благодаря Уильяму Джонсону, вторая была издана [[Кользон, Джон|Джоном Кользоном]] в [[1736 год]]у уже после смерти создателя. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к [[полином]]ам. Он вычислял не последовательные приближения <math>x_n</math>, а последовательность полиномов и в результате получал приближённое решение <math>x</math>.
Впервые метод был опубликован в трактате «Алгебра» [[Валлис, Джон|Джона Валлиса]] в [[1685 год]]у, по просьбе которого он был кратко описан самим Ньютоном. В [[1690 год]]у [[Рафсон, Джозеф|Джозеф Рафсон]] опубликовал упрощённое описание в работе «Общий анализ уравнений» ({{lang-la|«Analysis aequationum universalis»}}). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений <math>x_n</math> вместо более трудной для понимания последовательности полиномов, использованной Ньютоном. Наконец, в [[1740 год]]у метод Ньютона был описан [[Симпсон, Томас|Томасом Симпсоном]] как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения [[задача оптимизации|задач оптимизации]] путём нахождения нуля [[Производная функции|производной]] или [[градиент (математика)|градиента]].
В [[1879 год]]у [[Кэли, Артур|Артур Кэли]] в работе «Проблема комплексных чисел Ньютона — Фурье» ({{lang-en|«The Newton-Fourier imaginary problem»}}) был первым, кто отметил трудности в обобщении метода Ньютона на случай [[комплексное число|мнимых корней]] полиномов степени выше второй и комплексных начальных приближений. Эта работа открыла путь к изучению [[фрактал|теории фракталов]].
== Обобщения и модификации ==
[[Файл:Newton mod.PNG|thumb|300px|Иллюстрация последовательных приближений метода одной касательной, применённого к функции <math>\scriptstyle{f(x)=e^x-2}</math> с начальным приближением в точке <math>\scriptstyle{x_0=1{,}8}</math>.]]
=== Метод секущих ===
Родственный [[метод секущих]] является «приближённым» методом Ньютона и позволяет '''не вычислять''' производную. Значение производной в итерационной формуле заменяется её оценкой по двум предыдущим точкам итераций:
<math>f'(x_n) \approx \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}</math> .
Таким образом, основная формула имеет вид
: <math>x_{n+1} = x_n - f(x_n) \cdot \frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})} .</math>
Этот метод схож с методом Ньютона, но имеет немного меньшую скорость сходимости. Порядок сходимости метода равен [[Золотое сечение|золотому сечению]] — 1,618…
'''Замечания.''' 1) Для начала итерационного процесса требуются два различных значения
<math>x_0</math> и
<math>x_1</math> . <br>
2) В отличие от «настоящего метода Ньютона» (метода касательных), требующего хранить только <math>x_{n}</math>
(и в ходе вычислений — временно <math>f(x_{n})</math> и <math>f'(x_{n})</math>),
для метода секущих требуется сохранение
<math>x_{n-1}</math> ,
<math>x_{n}</math> ,
<math>f(x_{n-1})</math> ,
<math>f(x_{n})</math> . <br>
3) Применяется, если вычисление <math>f'(x)</math> затруднено
(например, требует большого количества машинных ресурсов: времени и/или памяти).
=== Метод одной касательной ===
В целях уменьшения числа обращений к значениям [[Производная функции|производной]] функции применяют так называемый метод одной касательной.
Формула итераций этого метода имеет вид:
: <math>x_{n+1}=x_n-\frac{1}{f'(x_0)}f(x_n).</math>
Суть метода заключается в том, чтобы вычислять производную лишь один раз, в точке начального приближения <math>x_0</math>, а затем использовать это значение на каждой последующей итерации:
: <math>\alpha(x)=\alpha_0=-\dfrac{1}{f'(x_0)}.</math>
При таком выборе <math>\alpha_0</math> в точке <math>x_0</math> выполнено равенство:
: <math>\varphi'(x_0)=1+\alpha_0f'(x_0)=0,</math>
и если отрезок, на котором предполагается наличие корня <math>x^*</math> и выбрано начальное приближение <math>x_0</math>, достаточно мал, а производная <math>\varphi'(x)</math> непрерывна, то значение <math>\varphi'(x^*)</math> будет не сильно отличаться от <math>\varphi'(x_0)=0</math> и, следовательно, график <math> y=\varphi(x)</math> пройдёт почти горизонтально, пересекая прямую <math>y=x</math>, что в свою очередь обеспечит быструю [[скорость сходимости|сходимость]] [[последовательность|последовательности]] точек приближений к корню.
Этот метод является частным случаем [[метод простой итерации|метода простой итерации]]. Он имеет линейный порядок сходимости.
===Метод Ньютона-Фурье===
Метод Ньютона-Фурье - это расширение метода Ньютона, выведенное [[Жозеф Фурье|Жозефом Фурье]] для получения оценок на абсолютную ошибку аппроксимации корня, в то же время обеспечивая квадратичную сходимость с обеих сторон.
Предположим, что {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}} дважды непрерывно дифференцируема на отрезке {{math|[''a'', ''b'']}} и что {{mvar|f}} имеет корень на этом интервале. Дополнительно положим, что {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x''), ''<span style{{=}}"letter-spacing:0.15em">f</span>″''(''x'') ≠ 0}} на этом отрезке (например, это верно, если {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''a'') < 0}}, {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''b'') > 0}}, и {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>″''(''x'') > 0}} на этом отрезке). Это гарантирует наличие единственного корня на этом отрезке, обозначим его {{mvar|α}}. Эти рассуждения относятся к вогнутой вверх функции. Если она вогнута вниз, то заменим {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}} на {{math|−''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}}, поскольку они имеют одни и те же корни.
Пусть {{math|''x''<sub>0</sub> {{=}} ''b''}} будет правым концом отрезка, на котором мы ищем корень, а {{math|''z''<sub>0</sub> {{=}} ''a''}} - левым концом того же отрезка. Если {{math|''x<sub>n</sub>''}} найдено, определим
:<math>x_{n + 1} = x_n - \frac{f(x_n)}{f'(x_n)},</math>
которое выражает обычный метод Ньютона, как описано выше. Затем определим
:<math>z_{n + 1} = z_n - \frac{f(z_n)}{f'(x_n)},</math>
где знаменатель равен {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x<sub>n</sub>'')}}, а не {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''z<sub>n</sub>'')}}. Итерации {{mvar|x<sub>n</sub>}} будут строго убывающими к корню, а итерации {{mvar|z<sub>n</sub>}} - строго возрастающими к корню. Также выполняется следующее соотношение:
:<math>\lim_{n\to \infty} \frac{x_{n + 1} - z_{n + 1}}{(x_n - z_n)^2} = \frac{f''(\alpha)}{2f'(\alpha)}</math>,
таким образом, расстояние между {{mvar|x<sub>n</sub>}} и {{mvar|z<sub>n</sub>}} уменьшается квадратичным образом.
=== Многомерный случай ===
Обобщим полученный результат на многомерный случай.
Пусть необходимо найти решение системы:
: <math>\left\{\begin{array}{lcr}
f_1(x_1,\;x_2,\;\ldots,\;x_n) & = & 0, \\
\ldots & & \\
f_m(x_1,\;x_2,\;\ldots,\;x_n) & = & 0.
\end{array}\right.</math>
Выбирая некоторое начальное значение <math>\vec{x}^{[0]}</math>, последовательные приближения <math>\vec{x}^{[j+1]}</math> находят путём решения [[система уравнений|систем уравнений]]:
:<math>f_i+\sum_{k=1}^n\frac{\partial f_i}{\partial x_k}(x^{[j+1]}_k-x_k^{[j]})=0,\qquad i=1,\;2,\;\ldots,\;m,</math>
где <math>\vec{x}^{[j]}=(x_1^{[j]},\;x_2^{[j]},\;\ldots,\;x_n^{[j]}),\quad j=0,\;1,\;2,\;\ldots</math>.
=== Применительно к задачам оптимизации ===
Пусть необходимо найти [[Экстремум|минимум]] [[функция многих переменных|функции многих переменных]] <math>f(\vec{x})\colon\R^n\to\R</math>. Эта задача равносильна задаче нахождения нуля [[градиент]]а <math>\nabla f(\vec{x})</math>. Применим изложенный выше метод Ньютона:
: <math>\nabla f(\vec{x}^{[j]})+H(\vec{x}^{[j]})(\vec{x}^{[j+1]}-\vec{x}^{[j]})=0,\quad j=1,\;2,\;\ldots,\;n,</math>
где <math>H(\vec{x})</math> — [[гессиан функции]] <math>f(\vec{x})</math>.
В более удобном итеративном виде это выражение выглядит так:
: <math>\vec{x}^{[j+1]}=\vec{x}^{[j]}-H^{-1}(\vec{x}^{[j]})\nabla f(\vec{x}^{[j]}).</math>
В случае квадратичной функции метод Ньютона находит [[экстремум]] за одну итерацию.
Нахождение матрицы Гессе связано с большими вычислительными затратами, и зачастую не представляется возможным. В таких случаях альтернативой могут служить [[квазиньютоновские методы]], в которых приближение матрицы Гессе строится в процессе накопления информации о кривизне функции.
=== Метод Ньютона — Рафсона ===
Метод Ньютона — Рафсона является улучшением метода Ньютона нахождения экстремума, описанного выше. Основное отличие заключается в том, что на очередной итерации каким-либо из [[оптимизация (математика)|методов одномерной оптимизации]] выбирается оптимальный шаг:
: <math>\vec{x}^{[j+1]}=\vec{x}^{[j]}-\lambda_j H^{-1}(\vec{x}^{[j]})\nabla f(\vec{x}^{[j]}),</math>
где <math>\lambda_j=\arg\min_\lambda f(\vec{x}^{[j]}-\lambda H^{-1}(\vec{x}^{[j]})\nabla f(\vec{x}^{[j]})).</math>
Для оптимизации вычислений применяют следующее улучшение: вместо того, чтобы на каждой итерации заново вычислять [[гессиан]] [[целевая функция|целевой функции]], ограничиваются начальным приближением <math>H(f(\vec{x}^{[0]}))</math> и обновляют его лишь раз в <math>m</math> шагов, либо не обновляют вовсе.
=== Применительно к задачам о наименьших квадратах ===
На практике часто встречаются задачи, в которых требуется произвести настройку свободных параметров объекта или подогнать математическую модель под реальные данные. В этих случаях появляются задачи о [[метод наименьших квадратов|наименьших квадратах]]:
: <math>F(\vec{x})=\|\vec{f}(\vec{x})\|=\sum_{i=1}^m f_i^2(\vec{x})=\sum_{i=1}^m (\varphi_i(\vec{x})-\mathcal{F}_i)^2\to\min.</math>
Эти задачи отличаются особым видом [[градиент (математика)|градиента]] и [[матрица Гессе|матрицы Гессе]]:
: <math>\nabla F(\vec{x})=2J^T(\vec{x})\vec{f}(\vec{x}),</math>
: <math>H(\vec{x})=2J^T(\vec{x})J(\vec{x})+2Q(\vec{x}),\qquad Q(\vec{x})=\sum_{i=1}^m f_i(\vec{x})H_i(\vec{x}),</math>
где <math>J(\vec{x})</math> — [[матрица Якоби]] вектор-функции <math>\vec{f}(\vec{x})</math>, <math>H_i(\vec{x})</math> — матрица Гессе для её компоненты <math>f_i(\vec{x})</math>.
Тогда очередной шаг <math>\vec{p}</math> определяется из системы:
: <math>\left[J^T(\vec{x})J(\vec{x})+\sum_{i=1}^m f_i(\vec{x})H_i(\vec{x})\right]\vec{p}=-J^T(\vec{x})\vec{f}(\vec{x}).</math>
=== Метод Гаусса — Ньютона ===
{{main|Алгоритм Гаусса — Ньютона}}
Метод Гаусса — Ньютона строится на предположении о том, что слагаемое <math>J^T(\vec{x})J(\vec{x})</math> доминирует над <math>Q(\vec{x})</math>. Это требование не соблюдается, если минимальные невязки велики, то есть если норма <math>\|\vec{f}(\vec{x})\|</math> сравнима с максимальным собственным значением матрицы <math>J^T(\vec{x})J(\vec{x})</math>. В противном случае можно записать:
: <math>J^T(\vec{x})J(\vec{x})\vec{p}=-J^T(\vec{x})\vec{f}(\vec{x}).</math>
Таким образом, когда норма <math>\|Q(\vec{x})\|</math> близка к нулю, а матрица <math>J(\vec{x})</math> имеет полный столбцевой [[ранг матрицы|ранг]], шаг <math>\vec{p}</math> мало отличается от ньютоновского (с учётом <math>Q(\vec{x})</math>), и метод может достигать квадратичной скорости сходимости, хотя вторые производные и не учитываются. Улучшением метода является [[алгоритм Левенберга — Марквардта]], основанный на [[Эвристика|эвристических]] соображениях.
=== Обобщение на комплексную плоскость ===
[[Файл:Newtroot 1 0 0 0 0 m1.png|thumb|left|300px|[[Бассейны Ньютона]] для полинома пятой степени <math>\scriptstyle{p(x)=x^5-1}</math>. Разными цветами закрашены области притяжения для разных корней. Более тёмные области соответствуют большему числу итераций.]]
До сих пор в описании метода использовались функции, осуществляющие отображения в пределах [[множество|множества]] [[вещественное число|вещественных значений]]. Однако метод может быть применён и для нахождения нуля [[функция комплексной переменной|функции комплексной переменной]]. При этом процедура остаётся неизменной:
: <math>z_{n+1}=z_n-\frac{f(z_n)}{f'(z_n)}.</math>
Особый интерес представляет выбор начального приближения <math>z_0</math>. Ввиду того, что функция может иметь несколько нулей, в различных случаях метод может сходиться к различным значениям, и вполне естественно возникает желание выяснить, какие области обеспечат сходимость к тому или иному корню. Этот вопрос заинтересовал [[Кэли, Артур|Артура Кэли]] ещё в [[1879 год]]у, однако разрешить его смогли лишь в [[1970-е|70]]-х годах [[двадцатый век|двадцатого столетия]] с появлением вычислительной техники. Оказалось, что на пересечениях этих областей (их принято называть ''областями притяжения'') образуются так называемые ''[[фрактал]]ы'' — бесконечные самоподобные геометрические фигуры.
Ввиду того, что Ньютон применял свой метод исключительно к [[полином]]ам, фракталы, образованные в результате такого применения, обрели название ''фракталов Ньютона'' или ''[[бассейны Ньютона|бассейнов Ньютона]]''.
{{-}}
== Реализация ==
=== Scala ===
<source lang="scala">
object NewtonMethod {
val accuracy = 1e-6
@tailrec
def method(x0: Double, f: Double => Double, dfdx: Double => Double, e: Double): Double = {
val x1 = x0 - f(x0) / dfdx(x0)
if (abs(x1 - x0) < e) x1
else method(x1, f, dfdx, e)
}
def g(C: Double) = (x: Double) => x*x - C
def dgdx(x: Double) = 2*x
def sqrt(x: Double) = x match {
case 0 => 0
case x if (x < 0) => Double.NaN
case x if (x > 0) => method(x/2, g(x), dgdx, accuracy)
}
}
</source>
=== Python ===
<source lang="python">
from math import sin, cos
from typing import Callable
import unittest
def newton(f: Callable[[float], float], f_prime: Callable[[float], float], x0: float,
eps: float=1e-7, kmax: int=1e3) -> float:
"""
solves f(x) = 0 by Newton's method with precision eps
:param f: f
:param f_prime: f'
:param x0: starting point
:param eps: precision wanted
:return: root of f(x) = 0
"""
x, x_prev, i = x0, x0 + 2 * eps, 0
while abs(x - x_prev) >= eps and i < kmax:
x, x_prev, i = x - f(x) / f_prime(x), x, i + 1
return x
class TestNewton(unittest.TestCase):
def test_0(self):
def f(x: float) -> float:
return x**2 - 20 * sin(x)
def f_prime(x: float) -> float:
return 2 * x - 20 * cos(x)
x0, x_star = 2, 2.7529466338187049383
self.assertAlmostEqual(newton(f, f_prime, x0), x_star)
if __name__ == '__main__':
unittest.main()
</source>
=== PHP ===
<source lang="php">
<?php
// PHP 5.4
function newtons_method(
$a = -1, $b = 1,
$f = function($x) {
return pow($x, 4) - 1;
},
$derivative_f = function($x) {
return 4 * pow($x, 3);
}, $eps = 1E-3) {
$xa = $a;
$xb = $b;
$iteration = 0;
while (abs($xb) > $eps) {
$p1 = $f($xa);
$q1 = $derivative_f($xa);
$xa -= $p1 / $q1;
$xb = $p1;
++$iteration;
}
return $xa;
}
</source>
=== Octave ===
<source lang="octave">
function res = nt()
eps = 1e-7;
x0_1 = [-0.5,0.5];
max_iter = 500;
xopt = new(@resh, eps, max_iter);
xopt
endfunction
function a = new(f, eps, max_iter)
x=-1;
p0=1;
i=0;
while (abs(p0)>=eps)
[p1,q1]=f(x);
x=x-p1/q1;
p0=p1;
i=i+1;
end
i
a=x;
endfunction
function[p,q]= resh(x) % p= -5*x.^5+4*x.^4-12*x.^3+11*x.^2-2*x+1;
p=-25*x.^4+16*x.^3-36*x.^2+22*x-2;
q=-100*x.^3+48*x.^2-72*x+22;
endfunction
</source>
=== Delphi ===
<source lang="pascal">
// вычисляемая функция
function fx(x: Double): Double;
begin
Result := x * x - 17;
end;
// производная функция от f(x)
function dfx(x: Double): Double;
begin
Result := 2 * x;
end;
function solve(fx, dfx: TFunc<Double, Double>; x0: Double): Double;
const
eps = 0.000001;
var
x1: Double;
begin
x1 := x0 - fx(x0) / dfx(x0); // первое приближение
while (Abs(x1-x0) > eps) do begin // пока не достигнута точность 0.000001
x0 := x1;
x1 := x1 - fx(x1) / dfx(x1); // последующие приближения
end;
Result := x1;
end;
// Вызов
solve(fx, dfx,4));
</source>
=== C++ ===
<source lang="cpp">
#include <stdio.h>
#include <math.h>
#define eps 0.000001
double fx(double x) { return x * x - 17;} // вычисляемая функция
double dfx(double x) { return 2 * x;} // производная функции
typedef double(*function)(double x); // задание типа function
double solve(function fx, function dfx, double x0) {
double x1 = x0 - fx(x0) / dfx(x0); // первое приближение
while (fabs(x1 - x0) > eps) { // пока не достигнута точность 0.000001
x0 = x1;
x1 = x0 - fx(x0) / dfx(x0); // последующие приближения
}
return x1;
}
int main () {
printf("%f\n", solve(fx, dfx, 4)); // вывод на экран
return 0;
}
</source>
=== C ===
<source lang="cpp">
typedef double (*function)(double x);
double TangentsMethod(function f, function df, double xn, double eps) {
double x1 = xn - f(xn)/df(xn);
double x0 = xn;
while(abs(x0-x1) > eps) {
x0 = x1;
x1 = x1 - f(x1)/df(x1);
}
return x1;
}
//Выбор начального приближения
xn = MyFunction(A)*My2Derivative(A) > 0 ? B : A;
double MyFunction(double x) { return (pow(x, 5) - x - 0.2); } //Ваша функция
double MyDerivative(double x) { return (5*pow(x, 4) - 1); } //Первая производная
double My2Derivative(double x) { return (20*pow(x, 3)); } //Вторая производная
//Пример вызова функции
double x = TangentsMethod(MyFunction, MyDerivative, xn, 0.1)
</source>
=== [[Haskell]] ===
<syntaxhighlight lang="haskell">
import Data.List ( iterate' )
main :: IO ()
main = print $ solve (\ x -> x * x - 17) ( * 2) 4
-- Функция solve универсальна для всех вещественных типов значения которых можно сравнивать.
solve = esolve 0.000001
esolve epsilon func deriv x0 = fst . head $ dropWhile pred pairs
where
pred (xn, xn1) = (abs $ xn - xn1) > epsilon -- Функция pred определяет достигнута ли необходимая точность.
next xn = xn - func xn / deriv xn -- Функция next вычисляет новое приближение.
iters = iterate' next x0 -- Бесконечный список итераций.
pairs = zip iters (tail iters) -- Бесконечный список пар итераций вида: [(x0, x1), (x1, x2) ..].
</syntaxhighlight>
== Литература ==
* {{публикация|книга
|автор = Акулич И. Л.
|заглавие = Математическое программирование в примерах и задачах
|вид = Учеб. пособие для студентов эконом. спец. вузов
|место = М.
|издательство = Высшая школа
|год = 1986
|страниц = 319
|иллюстрации = ил.
|ббк = 22.1 А44
|удк = 517.8
}}
* {{публикация|книга
|автор = Амосов А. А., Дубинский Ю. А., Копченова Н. П.
|заглавие = Вычислительные методы для инженеров
|вид = Учеб. пособие
|место = М.
|издательство = Высшая школа
|год = 1994
|страниц = 544
|иллюстрации = ил.
|isbn = 5-06-000625-5
|ббк = 32.97 А62
|удк = 683.1
}}
* {{публикация|книга|автор = Бахвалов Н. С., [[Жидков, Николай Петрович|Жидков Н. П.]], Кобельков Г. Г.|заглавие = Численные методы|оригинал = |ссылка = |издание = 8-е изд.|место = М.|издательство = Лаборатория Базовых Знаний|год = 2000|страницы =|isbn = }}
* {{публикация|книга|заглавие = Исаак Ньютон|автор = Вавилов С. И. | место = М.| издательство = Изд. АН СССР| год = 1945|ссылка = http://vivovoco.astronet.ru/VV/BOOKS/NEWTON/CHAPTER_13.HTM}}
* {{публикация|книга|автор = Волков Е. А.|заглавие = Численные методы|оригинал = |ссылка = |издание =|место = М.|издательство = Физматлит|год = 2003|страницы =|isbn = }}
* {{публикация|книга|автор = Гилл Ф., Мюррей У., Райт М.|заглавие = Практическая оптимизация. Пер. с англ|оригинал = |ссылка = |издание =|место = М.|издательство = Мир|год = 1985|страницы =|isbn = }}
* {{публикация|книга|автор = Корн Г., Корн Т.|заглавие = Справочник по математике для научных работников и инженеров|оригинал = |ссылка = |издание = |место = М.|издательство = Наука|год = 1970|страницы = 575—576|isbn = }}
* {{публикация|книга|автор = Коршунов Ю. М., Коршунов Ю. М.|заглавие = Математические основы кибернетики|оригинал = |ссылка = |издание =|место М.|издательство = Энергоатомиздат|год = 1972|страницы =|isbn = }}
* {{публикация|книга|автор = Максимов Ю. А.,Филлиповская Е. А.|заглавие = Алгоритмы решения задач нелинейного программирования|оригинал = |ссылка = |издание =|место = М.|издательство = МИФИ|год = 1982|страницы =|isbn = }}
* {{публикация|книга|автор = Морозов А. Д.|заглавие = Введение в теорию фракталов|оригинал = |ссылка = |издание = |место = |издательство = МИФИ|год = 2002|страницы =|isbn = }}
== См. также ==
* [[Метод простой итерации]]
* [[Двоичный поиск]]
* [[Метод дихотомии]]
* [[Метод секущих]]
* [[Метод Мюллера]]
* [[Метод хорд]]
* [[Метод бисекции]]
* [[Фрактал]]
* [[Численное решение уравнений]]
* [[Целочисленный квадратный корень]]
* [[Быстрый обратный квадратный корень]]
== Ссылки ==
{{Родственные проекты
|Викиучебник = Category:Newton's method
|Викисклад = Newton Method
}}
* [http://fractalworld.xaoc.ru/article/frnew.html «Бассейны Ньютона» на сайте fractalworld.xaoc.ru]
* [https://web.archive.org/web/20080506085010/http://www.scottish-wetlands.org/073/73081.htm «Исаак Ньютон» на сайте www.scottish-wetlands.org]
* [http://math.nsc.ru/LBRT/g2/english/ssk/talk_lvk95.html «Математические работы Канторовича» на сайте Института математики СО РАН]
* {{springer|title=Newton method|id=p/n066560}}
* {{MathWorld|title=Newton's Method|urlname=NewtonsMethod}}
* [http://en.citizendium.org/wiki/Newton%27s_method Newton’s method, Citizendium.]
* [https://web.archive.org/web/20190524083302/http://mathfaculty.fullerton.edu/mathews/n2003/NewtonAccelerateMod.html Mathews, J., The Accelerated and Modified Newton Methods, Course notes.]
* [http://www.ece.mcmaster.ca/~xwu/part2.pdf Wu, X., Roots of Equations, Course notes.]
{{Методы оптимизации}}
[[Категория:Численные методы решения уравнений]]
[[Категория:Алгоритмы оптимизации]]
[[Категория:Исаак Ньютон]]' |
Вики-текст новой страницы после правки (new_wikitext) | '{{другие значения|Метод (значения)}}
'''Метод Ньютона''', '''алгоритм Ньютона''' (также известный как '''метод касательных''') — это итерационный [[Численные методы|численный метод]] нахождения корня ([[нуль функции|нуля]]) заданной [[Функция (математика)|функции]]. Метод был впервые предложен английским [[физик]]ом, [[математик]]ом и [[астроном]]ом [[Ньютон, Исаак|Исааком Ньютоном]] ([[1643]]—[[1727]]). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах [[метод простой итерации|простой итерации]]. Метод обладает квадратичной [[скорость сходимости|сходимостью]]. Модификацией метода является [[метод хорд и касательных]]. Также метод Ньютона может быть использован для решения [[задача оптимизации|задач оптимизации]], в которых требуется определить ноль первой [[Производная функции|производной]] либо [[градиент (математика)|градиента]] в случае многомерного пространства.
{{TOChidden}}
== Описание метода ==
=== Обоснование ===
Чтобы численно решить уравнение <math>f(x)=0</math> [[метод простой итерации|методом простой итерации]], его необходимо привести к эквивалентному уравнению: <math>x=\varphi(x)</math>, где <math>\varphi</math> — [[сжимающее отображение]].
Для наилучшей [[скорость сходимости|сходимости]] метода в точке очередного приближения <math>x^*</math> должно выполняться условие <math>\varphi'(x^*)=0</math>. Решение данного уравнения ищут в виде <math>\varphi(x)=x+\alpha(x)f(x)</math>, тогда:
: <math>\varphi'(x^*)=1+\alpha'(x^*)f(x^*)+\alpha(x^*) f'(x^*)=0.</math>
В предположении, что точка приближения «достаточно близка» к корню <math>\tilde{x}</math> и что заданная функция [[непрерывное отображение|непрерывна]] <math>(f(x^*)\approx f(\tilde{x})=0)</math>, окончательная формула для <math>\alpha(x)</math> такова:
: <math>\alpha(x)=-\frac{1}{f'(x)}.</math>
С учётом этого [[Функция (программирование)|функция]] <math>\varphi(x)</math> определяется:
: <math>\varphi(x)=x-\frac{f(x)}{f'(x)}.</math>
При некоторых условиях эта функция в окрестности корня осуществляет сжимающее отображение.
{{Доказательство|Пусть дана [[Функция (программирование)|функция]] [[вещественное число|вещественного переменного]] дважды [[непрерывная дифференцируемость|непрерывно дифференцируемая]] в своей [[Область определения функции|области определения]], [[Производная функции|производная]] которой нигде не обращается в нуль:
: <math>\scriptstyle{f(x)\colon\mathbb{X}\to\R,\;f(x)\in\mathrm{C}^2(\mathbb{X});\quad\forall x\in\mathbb{X}\;f'(x)\neq 0.}</math>
И необходимо доказать, что функция <math>\scriptstyle{\varphi(x)=x-\frac{f(x)}{f'(x)}}</math> осуществляет сжимающее отображение вблизи корня уравнения <math>\scriptstyle{f(x)=0}</math>.
В силу [[непрерывная дифференцируемость|непрерывной дифференцируемости]] функции <math>\scriptstyle{f(x)}</math> и неравенства нулю её первой [[Производная функции|производной]] <math>\scriptstyle{\varphi(x)}</math> [[непрерывная функция|непрерывна]].
Производная <math>\scriptstyle{\varphi'(x)}</math> равна:
: <math>\scriptstyle{\varphi'(x)=\frac{f(x)f''(x)}{\left(f'(x)\right)^2}.}</math>
В условиях, наложенных на <math>\scriptstyle{f(x)}</math>, она также непрерывна. Пусть <math>\scriptstyle{\tilde{x}}</math> — искомый корень уравнения: <math>\scriptstyle{f(\tilde{x})=0}</math>, следовательно в его окрестности <math>\scriptstyle{\varphi'(x)\approx 0}</math>:
: <math>\scriptstyle{\forall\varepsilon\colon 0<\varepsilon<1,\;\exist\delta>0\;\forall x\in\mathbb{X}\;|x-\tilde{x}|<\delta\colon|\varphi'(x)-0|<\varepsilon.}</math>
Тогда согласно [[формула конечных приращений|теореме Лагранжа]]:
: <math>\scriptstyle{\forall x_1,\;x_2\in\mathrm{U}_\delta(\tilde{x})\;\exist\xi\in\mathrm{U}_\delta(\tilde{x})\colon|\varphi(x_1)-\varphi(x_2)|=|\varphi'(\xi)| |x_1-x_2|<\varepsilon|x_1-x_2|.}</math>
В силу того, что <math>\scriptstyle{\varphi(\tilde{x})=\tilde{x}}</math> в этой же дельта окрестности выполняется:
: <math>\scriptstyle{\forall x\in U_{\delta}(\tilde{x})\colon\;|\varphi(x)-\tilde{x}|<\varepsilon|x-\tilde{x}|.}</math>
Таким образом полученная функция <math>\scriptstyle{\varphi(x)}</math> в окрестности корня <math>\scriptstyle{U_\delta(\tilde{x})}</math> осуществляет [[сжимающее отображение]].</small>}}
В этом случае алгоритм нахождения численного решения уравнения <math>f(x)=0</math> сводится к [[Метод простой итерации|итерационной процедуре вычисления]]:
: <math>x_{n+1}=x_{n}-\frac{f(x_n)}{f'(x_n)}.</math>
По [[теорема Банаха|теореме Банаха]] последовательность приближений стремится к корню уравнения <math>f(x)=0</math>.
[[Файл:Newton iteration.svg|thumb|left|300px|Иллюстрация метода Ньютона (синим изображена функция <math>\scriptstyle{f(x)}</math>, ноль которой необходимо найти, красным — касательная в точке очередного приближения <math>\scriptstyle{x_n}</math>). Здесь мы можем увидеть, что последующее приближение <math>\scriptstyle{x_{n+1}}</math> лучше предыдущего <math>\scriptstyle{x_n}</math>.]]
=== Геометрическая интерпретация ===
Основная идея метода заключается в следующем: задаётся начальное приближение вблизи предположительного корня, после чего строится касательная к графику исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность.
'''Пусть''' 1) вещественнозначная функция <math>f(x)\colon(a,\,b)\to\R</math> непрерывно [[Дифференцируемая функция|дифференцируема]] на интервале <math>(a,\,b)</math> ; <br>
2) существует искомая точка <math>x^{*}\in (a,\,b)</math> : <math>f(x^{*})= 0</math> ; <br>
3) существуют <math>C > 0</math> и <math>\delta > 0</math> такие, что <br>
<math>\vert f'(x) \vert \geqslant C</math>
для <math>x\in(a,\,x^{*}-\delta ] \cup [ x^{*}+\delta,\,b)</math> <br>
и <math>f'(x)\ne 0</math>
для <math>x\in(x^{*}-\delta,\, x^{*})\cup(x^{*},\, x^{*}+\delta )</math> ; <br>
4) точка <math>x_n \in (a,\,b)</math> такова, что <math>f(x_n)\ne 0</math> . <br>
'''Тогда''' формула итеративного приближения <math>x_n</math> к <math>x^{*}</math>
может быть выведена из геометрического смысла касательной следующим образом:
: <math>f'(x_n)=\mathrm{tg}\,\alpha_{n} = \frac{\Delta y}{\Delta x} = \frac{f(x_n)-0}{x_n-x_{n+1}} = \frac{0-f(x_n)}{x_{n+1}-x_n},</math>
где <math>\alpha_{n}</math> — угол наклона касательной прямой
<math>y(x)=f(x_n) + (x - x_n) \cdot \mathrm{tg}\,\alpha_{n}</math>
к графику <math>f</math>
в точке <math>(x_n;f(x_n))</math> .
Следовательно (в уравнении касательной прямой полагаем <math>y(x_{n+1})=0</math>) искомое выражение для <math>x_{n+1}</math> имеет вид :
: <math>x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.</math>
Если <math>x_{n+1} \in (a,\,b)</math>, то это значение можно использовать в качестве следующего приближения к
<math>x^{*}</math> .
Если <math>x_{n+1} \notin (a,\,b)</math>, то имеет место «перелёт» (корень <math>x^{*}</math> лежит рядом с границей <math>(a,\,b)</math>). В этом случае надо (воспользовавшись идеей [[Метод бисекции|метода половинного деления]]) заменять
<math>x_{n+1}</math> на
<math>\frac{x_{n}+x_{n+1}}{2}</math>
до тех пор, пока точка «не вернётся» в область поиска
<math>(a,\,b)</math> .
'''Замечания.''' 1) Наличие непрерывной производной даёт возможность строить непрерывно меняющуюся касательную на всей области поиска решения <math>(a,\,b)\;</math> . <br>
2) Случаи граничного (в точке <math>a</math> или в точке <math>b</math>) расположения искомого решения <math>x^{*}</math> рассматриваются аналогичным образом. <br>
3) С геометрической точки зрения равенство
<math>f'(x_n)= 0</math>
означает, что касательная прямая к графику
<math>f</math>
в точке
<math>(x_n;f(x_n))</math> -
параллельна оси
<math>OX</math>
и при
<math>f(x_n)\ne 0</math>
не пересекается с ней в конечной части. <br>
4) Чем больше константа <math>C > 0</math> и чем меньше константа <math>\delta > 0</math> из пункта 3 условий,
тем для <math>x_{n}\in(a,\,x^{*}-\delta ] \cup [ x^{*}+\delta,\,b)</math>
пересечение касательной к графику <math>f</math> и оси <math>OX</math> ближе к точке <math>(x^{*};\;0)</math> ,
то есть тем ближе значение <math>x_{n+1}</math> к искомой <math>x^{*}\in (a,\,b)</math> .
Итерационный процесс '''начинается''' с некоторого начального приближения
<math>x_0 \in (a,\,b)</math> ,
причём между
<math>x_0 \in (a,\,b)</math>
и искомой точкой
<math>x^{*}\in (a,\,b)</math>
не должно быть других нулей функции
<math>f</math> ,
то есть «чем ближе <math>x_0</math>
к искомому корню <math>x^{*}</math> ,
тем лучше». Если предположения о нахождении <math>x^{*}</math> отсутствуют, методом проб и ошибок можно сузить область возможных значений, применив [[теорема о промежуточных значениях|теорему о промежуточных значениях]].
Для предварительно заданных <math>\varepsilon_{x} >0</math> , <math>\varepsilon_{f} >0</math>
итерационный процесс '''завершается''' если
<math>\left \vert \frac{f(x_n)}{f'(x_n)} \right \vert \approx \vert x_{n+1}-x_n \vert <\varepsilon_{x}</math> и
<math> \vert f(x_{n+1})\vert <\varepsilon_{f}</math> . <br>
В частности, для матрицы дисплея <math>\varepsilon_{x}</math> и <math>\varepsilon_{f}</math> могут быть рассчитаны,
исходя из масштаба отображения графика <math>f</math> ,
то есть если <math>x_n</math> и <math>x_{n+1}</math> попадают в один вертикальный, а <math>f(x_n)</math> и <math>f(x_{n+1})</math> в один горизонтальный ряд.
=== Алгоритм ===
# Задается начальное приближение <math>x_0</math>.
# Пока не выполнено условие остановки, в качестве которого можно взять <math>|x_{n+1}-x_n|<\varepsilon</math> или <math>|f(x_{n+1})|<\varepsilon</math> (то есть погрешность в нужных пределах), вычисляют новое приближение: <math>x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}</math>.
=== Пример ===
{| class="toccolours" style="float: right; font-size: 85%; background:white; color:black; width:50em; maxwidth=60%"
!colspan=2| Иллюстрация применения метода Ньютона к функции <math>f(x)=\cos x-x^3</math> с начальным приближением в точке <math>x_0=0{,}5</math>.
|-
|[[Файл:Newton ex.PNG|thumb|300px|center|График последовательных приближений.]]
|[[Файл:Newton conv.PNG|thumb|300px|center|График сходимости.]]
|-
|colspan=2| Согласно [[скорость сходимости|способу практического определения]] скорость сходимости может быть оценена как тангенс угла наклона графика сходимости, то есть в данном случае равна двум.
|}
Рассмотрим задачу о нахождении положительных <math>x</math>, для которых <math>\cos x=x^3</math>. Эта задача может быть представлена как задача нахождения нуля функции <math>f(x)=\cos x-x^3</math>. Имеем выражение для [[Производная функции|производной]] <math>f'(x)=-\sin x-3x^2</math>. Так как <math>\cos x\leqslant 1</math> для всех <math>x</math> и <math>x^3>1</math> для <math>x>1</math>, [[Теорема Больцано — Коши|очевидно]], что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение <math>x_0 = 0{,}5</math>, тогда:
: <math>\begin{matrix}
x_1 & = & x_0-\dfrac{f(x_0)}{f'(x_0)} & = & 1{,}112\;141\;637\;097, \\
x_2 & = & x_1-\dfrac{f(x_1)}{f'(x_1)} & = & \underline{0{,}}909\;672\;693\;736, \\
x_3 & = & x_2-\dfrac{f(x_2)}{f'(x_2)} & = & \underline{0{,}86}7\;263\;818\;209, \\
x_4 & = & x_3-\dfrac{f(x_3)}{f'(x_3)} & = & \underline{0{,}865\;47}7\;135\;298, \\
x_5 & = & x_4-\dfrac{f(x_4)}{f'(x_4)} & = & \underline{0{,}865\;474\;033\;1}11, \\
x_6 & = & x_5-\dfrac{f(x_5)}{f'(x_5)} & = & \underline{0{,}865\;474\;033\;102}.
\end{matrix}</math>
Подчёркиванием отмечены верные [[значащие цифры]]. Видно, что их количество от шага к шагу растёт (приблизительно удваиваясь с каждым шагом): от 1 к 2, от 2 к 5, от 5 к 10, иллюстрируя квадратичную [[скорость сходимости]].
<!-- === Псевдокод ===
Приведём псевдокод для указанного примера.
<source lang="С"> '''function''' newtonIterationFunction(x) {
'''return''' x - (cos(x) - x^3) / (-sin(x) - 3*x^2)
}
'''var''' x := 0.5
'''for''' i '''from''' 0 '''to''' 99 {
print "Итерация: " + i
print "Приближение: " + x
xold := x
x := newtonIterationFunction(x)
'''if''' x = xold {
print "Решение найдено!"
'''break'''
}
}
</source>-->
== Условия применения ==
[[Файл:Newton bad.PNG|thumb|300px|left|Иллюстрация расхождения метода Ньютона, применённого к функции <math>\scriptstyle{f(x)=x^3-2x+2}</math> с начальным приближением в точке <math>\scriptstyle{x_0=0}</math>.]]
Рассмотрим ряд примеров, указывающих на недостатки метода.
=== Контрпримеры ===
*; Если начальное приближение недостаточно близко к решению, то метод может не сойтись.
Пусть
: <math>f(x)=x^3-2x+2.</math>
Тогда
: <math>x_{n+1}=x_{n}-\frac{x_n^3-2x_n+2}{3x_n^2-2}.</math>
Возьмём ноль в качестве начального приближения. Первая итерация даст в качестве приближения единицу. В свою очередь, вторая снова даст ноль. Метод зациклится и решение не будет найдено. В общем случае построение последовательности приближений может быть [[каскад бифуркаций|очень запутанным]].
[[Файл:Newton ex2.png|thumb|350px|График производной функции <math>\scriptstyle{f(x)=x+x^2\sin(2/x)}</math> при приближении <math>\scriptstyle{x}</math> к нулю справа.]]
*; Если [[Производная функции|производная]] не [[непрерывное отображение|непрерывна]] в точке корня, то метод может расходиться в любой [[окрестность|окрестности]] корня.
Рассмотрим функцию:
: <math>f(x)=\begin{cases}
0, & x=0, \\
x+x^2\sin\left(\dfrac{2}{x}\right), & x\neq 0.
\end{cases}</math>
Тогда <math>f'(0)=1</math> и <math>f'(x)=1+2x\sin(2/x)-2\cos(2/x)</math> всюду, кроме 0.
В окрестности корня производная меняет знак при приближении <math>x</math> к нулю справа или слева. В то время, как <math>f(x)\geqslant x-x^2>0</math> для <math>0<x<1</math>.
Таким образом <math>f(x)/f'(x)</math> не ограничено вблизи корня, и метод будет расходиться, хотя функция всюду дифференцируема, её производная не равна нулю в корне, <math>f</math> [[аналитическая функция|бесконечно дифференцируема]] везде, кроме как в корне, а её производная ограничена в окрестности корня.
*; Если не существует вторая [[Производная функции|производная]] в точке корня, то [[скорость сходимости]] метода может быть заметно снижена.
Рассмотрим пример:
: <math>f(x)=x+x^{4/3}.</math>
Тогда <math>f'(x)=1+(4/3)x^{1/3}</math> и <math>f''(x)=(4/9)x^{-2/3}</math> за исключением <math>x=0</math>, где она не определена.
На очередном шаге имеем <math>x_n</math>:
: <math>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})}.</math>
[[Скорость сходимости]] полученной последовательности составляет приблизительно 4/3. Это существенно меньше, нежели 2, необходимое для квадратичной сходимости, поэтому в данном случае можно говорить лишь о линейной сходимости, хотя функция всюду [[непрерывная дифференцируемость|непрерывно дифференцируема]], производная в корне не равна нулю, и <math>f</math> бесконечно дифференцируема везде, кроме как в корне.
*; Если производная в точке корня равна нулю, то [[скорость сходимости]] не будет квадратичной, а сам метод может преждевременно прекратить поиск, и дать неверное для заданной точности приближение.
Пусть
: <math>f(x)=x^2.</math>
Тогда <math>f'(x)=2x</math> и следовательно <math>x-f(x)/f'(x)=x/2</math>. Таким образом сходимость метода не квадратичная, а линейная, хотя функция всюду бесконечно дифференцируема.
=== Ограничения ===
Пусть задано уравнение <math>f(x)=0</math>, где <math>f(x)\colon\mathbb{X}\to\R</math> и надо найти его решение.
Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Она носит имя советского [[математик]]а и [[экономист]]а [[Канторович, Леонид Витальевич|Леонида Витальевича Канторовича]] ([[1912]]—[[1986]]).
'''Теорема Канторовича.'''
''Если существуют такие константы <math>A,\;B,\;C</math>, что:''
# ''<math>\frac{1}{|f'(x)|}<A</math> на <math>[a,\;b]</math>, то есть <math>f'(x)</math> сут и не равна нулю;''
# ''<math>\left|\frac{f(x)}{f'(x)}\right|<B</math> на <math>[a,\;b]</math>, то есть <math>f(x)</math> ограничена;''
# ''<math>\exist f''(x)</math> на <math>[a,\;b]</math>, и <math>|f''(x)|\leqslant C\leqslant\frac{1}{2AB}</math>;''
''Причём длина рассматриваемого отрезка <math>|a-b|<\frac{1}{AB}\left(1-\sqrt{1-2ABC}\right)</math>. Тогда справедливы следующие утверждения:''
# ''на <math>[a,\;b]</math> существует корень <math>x^*</math> уравнения <math>f(x)=0\colon\exist x^*\in[a,\;b]\colon f(x^*)=0</math>;''
# ''если <math>x_0=\frac{a+b}{2}</math>, то итерационная [[последовательность]] сходится к этому корню: <math>\left\{ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\right\}\to x^*</math>;''
# ''погрешность может быть оценена по формуле <math>|x^*-x_n|\leqslant\frac{B}{2^{n-1}}(2ABC)^{2^{n-1}}</math>.''
Из последнего из утверждений теоремы в частности следует квадратичная [[скорость сходимости|сходимость]] метода:
: <math>|x^*-x_n|\leqslant\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.</math>
Тогда ограничения на исходную функцию <math>f(x)</math> будут выглядеть так:
# функция должна быть ограничена;
# функция должна быть [[гладкая функция|гладкой]], дважды [[дифференцируемая функция|дифференцируемой]];
# её первая [[Производная функции|производная]] <math>f'(x)</math> равномерно отделена от нуля;
# её вторая производная <math>f''(x)</math> должна быть равномерно ограничена.
== Историческая справка ==
Метод был описан [[Ньютон, Исаак|Исааком Ньютоном]] в рукописи «Об анализе уравнениями бесконечных рядов» ({{lang-la|«De analysi per aequationes numero terminorum infinitas»}}), адресованной в [[1669 год]]у [[Барроу, Исаак|Барроу]], и в работе «Метод флюксий и бесконечные ряды» ({{lang-la|«De metodis fluxionum et serierum infinitarum»}}) или «Аналитическая геометрия» ({{lang-la|«Geometria analytica»}}) в собраниях трудов Ньютона, которая была написана в [[1671 год]]у. В своих работах Ньютон вводит такие понятия, как разложение [[Функция (программирование)|функции]] в [[Ряд (математика)|ряд]], [[бесконечно малая величина|бесконечно малые]] и флюксии ([[Производная функции|производные]] в нынешнем понимании). Указанные работы были изданы значительно позднее: первая вышла в свет в [[1711 год]]у благодаря Уильяму Джонсону, вторая была издана [[Кользон, Джон|Джоном Кользоном]] в [[1736 год]]у уже после смерти создателя. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к [[полином]]ам. Он вычислял не последовательные приближения <math>x_n</math>, а последовательность полиномов и в результате получал приближённое решение <math>x</math>.
Впервые метод был опубликован в трактате «Алгебра» [[Валлис, Джон|Джона Валлиса]] в [[1685 год]]у, по просьбе которого он был кратко описан самим Ньютоном. В [[1690 год]]у [[Рафсон, Джозеф|Джозеф Рафсон]] опубликовал упрощённое описание в работе «Общий анализ уравнений» ({{lang-la|«Analysis aequationum universalis»}}). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений <math>x_n</math> вместо более трудной для понимания последовательности полиномов, использованной Ньютоном. Наконец, в [[1740 год]]у метод Ньютона был описан [[Симпсон, Томас|Томасом Симпсоном]] как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения [[задача оптимизации|задач оптимизации]] путём нахождения нуля [[Производная функции|производной]] или [[градиент (математика)|градиента]].
В [[1879 год]]у [[Кэли, Артур|Артур Кэли]] в работе «Проблема комплексных чисел Ньютона — Фурье» ({{lang-en|«The Newton-Fourier imaginary problem»}}) был первым, кто отметил трудности в обобщении метода Ньютона на случай [[комплексное число|мнимых корней]] полиномов степени выше второй и комплексных начальных приближений. Эта работа открыла путь к изучению [[фрактал|теории фракталов]].
== Обобщения и модификации ==
[[Файл:Newton mod.PNG|thumb|300px|Иллюстрация последовательных приближений метода одной касательной, применённого к функции <math>\scriptstyle{f(x)=e^x-2}</math> с начальным приближением в точке <math>\scriptstyle{x_0=1{,}8}</math>.]]
=== Метод секущих ===
Родственный [[метод секущих]] является «приближённым» методом Ньютона и позволяет '''не вычислять''' производную. Значение производной в итерационной формуле заменяется её оценкой по двум предыдущим точкам итераций:
<math>f'(x_n) \approx \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}</math> .
Таким образом, основная формула имеет вид
: <math>x_{n+1} = x_n - f(x_n) \cdot \frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})} .</math>
Этот метод схож с методом Ньютона, но имеет немного меньшую скорость сходимости. Порядок сходимости метода равен [[Золотое сечение|золотому сечению]] — 1,618…
'''Замечания.''' 1) Для начала итерационного процесса требуются два различных значения
<math>x_0</math> и
<math>x_1</math> . <br>
2) В отличие от «настоящего метода Ньютона» (метода касательных), требующего хранить только <math>x_{n}</math>
(и в ходе вычислений — временно <math>f(x_{n})</math> и <math>f'(x_{n})</math>),
для метода секущих требуется сохранение
<math>x_{n-1}</math> ,
<math>x_{n}</math> ,
<math>f(x_{n-1})</math> ,
<math>f(x_{n})</math> . <br>
3) Применяется, если вычисление <math>f'(x)</math> затруднено
(например, требует большого количества машинных ресурсов: времени и/или памяти).
=== Метод одной касательной ===
В целях уменьшения числа обращений к значениям [[Производная функции|производной]] функции применяют так называемый метод одной касательной.
Формула итераций этого метода имеет вид:
: <math>x_{n+1}=x_n-\frac{1}{f'(x_0)}f(x_n).</math>
Суть метода заключается в том, чтобы вычислять производную лишь один раз, в точке начального приближения <math>x_0</math>, а затем использовать это значение на каждой последующей итерации:
: <math>\alpha(x)=\alpha_0=-\dfrac{1}{f'(x_0)}.</math>
При таком выборе <math>\alpha_0</math> в точке <math>x_0</math> выполнено равенство:
: <math>\varphi'(x_0)=1+\alpha_0f'(x_0)=0,</math>
и если отрезок, на котором предполагается наличие корня <math>x^*</math> и выбрано начальное приближение <math>x_0</math>, достаточно мал, а производная <math>\varphi'(x)</math> непрерывна, то значение <math>\varphi'(x^*)</math> будет не сильно отличаться от <math>\varphi'(x_0)=0</math> и, следовательно, график <math> y=\varphi(x)</math> пройдёт почти горизонтально, пересекая прямую <math>y=x</math>, что в свою очередь обеспечит быструю [[скорость сходимости|сходимость]] [[последовательность|последовательности]] точек приближений к корню.
Этот метод является частным случаем [[метод простой итерации|метода простой итерации]]. Он имеет линейный порядок сходимости.
===Метод Ньютона-Фурье===
Метод Ньютона-Фурье - это расширение метода Ньютона, выведенное [[Жозеф Фурье|Жозефом Фурье]] для получения оценок на абсолютную ошибку аппроксимации корня, в то же время обеспечивая квадратичную сходимость с обеих сторон.
Предположим, что {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}} дважды непрерывно дифференцируема на отрезке {{math|[''a'', ''b'']}} и что {{mvar|f}} имеет корень на этом интервале. Дополнительно положим, что {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x''), ''<span style{{=}}"letter-spacing:0.15em">f</span>″''(''x'') ≠ 0}} на этом отрезке (например, это верно, если {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''a'') < 0}}, {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''b'') > 0}}, и {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>″''(''x'') > 0}} на этом отрезке). Это гарантирует наличие единственного корня на этом отрезке, обозначим его {{mvar|α}}. Эти рассуждения относятся к вогнутой вверх функции. Если она вогнута вниз, то заменим {{math|''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}} на {{math|−''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'')}}, поскольку они имеют одни и те же корни.
Пусть {{math|''x''<sub>0</sub> {{=}} ''b''}} будет правым концом отрезка, на котором мы ищем корень, а {{math|''z''<sub>0</sub> {{=}} ''a''}} - левым концом того же отрезка. Если {{math|''x<sub>n</sub>''}} найдено, определим
:<math>x_{n + 1} = x_n - \frac{f(x_n)}{f'(x_n)},</math>
которое выражает обычный метод Ньютона, как описано выше. Затем определим
:<math>z_{n + 1} = z_n - \frac{f(z_n)}{f'(x_n)},</math>
где знаменатель равен {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x<sub>n</sub>'')}}, а не {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''z<sub>n</sub>'')}}. Итерации {{mvar|x<sub>n</sub>}} будут строго убывающими к корню, а итерации {{mvar|z<sub>n</sub>}} - строго возрастающими к корню. Также выполняется следующее соотношение:
:<math>\lim_{n\to \infty} \frac{x_{n + 1} - z_{n + 1}}{(x_n - z_n)^2} = \frac{f''(\alpha)}{2f'(\alpha)}</math>,
таким образом, расстояние между {{mvar|x<sub>n</sub>}} и {{mvar|z<sub>n</sub>}} уменьшается квадратичным образом.
=== Многомерный случай ===
Обобщим полученный результат на многомерный случай.
Пусть необходимо найти решение системы:
: <math>\left\{\begin{array}{lcr}
f_1(x_1,\;x_2,\;\ldots,\;x_n) & = & 0, \\
\ldots & & \\
f_m(x_1,\;x_2,\;\ldots,\;x_n) & = & 0.
\end{array}\right.</math>
Выбирая некоторое начальное значение <math>\vec{x}^{[0]}</math>, последовательные приближения <math>\vec{x}^{[j+1]}</math> находят путём решения [[система уравнений|систем уравнений]]:
:<math>f_i+\sum_{k=1}^n\frac{\partial f_i}{\partial x_k}(x^{[j+1]}_k-x_k^{[j]})=0,\qquad i=1,\;2,\;\ldots,\;m,</math>
где <math>\vec{x}^{[j]}=(x_1^{[j]},\;x_2^{[j]},\;\ldots,\;x_n^{[j]}),\quad j=0,\;1,\;2,\;\ldots</math>.
=== Применительно к задачам оптимизации ===
Пусть необходимо найти [[Экстремум|минимум]] [[функция многих переменных|функции многих переменных]] <math>f(\vec{x})\colon\R^n\to\R</math>. Эта задача равносильна задаче нахождения нуля [[градиент]]а <math>\nabla f(\vec{x})</math>. Применим изложенный выше метод Ньютона:
: <math>\nabla f(\vec{x}^{[j]})+H(\vec{x}^{[j]})(\vec{x}^{[j+1]}-\vec{x}^{[j]})=0,\quad j=1,\;2,\;\ldots,\;n,</math>
где <math>H(\vec{x})</math> — [[гессиан функции]] <math>f(\vec{x})</math>.
В более удобном итеративном виде это выражение выглядит так:
: <math>\vec{x}^{[j+1]}=\vec{x}^{[j]}-H^{-1}(\vec{x}^{[j]})\nabla f(\vec{x}^{[j]}).</math>
В случае квадратичной функции метод Ньютона находит [[экстремум]] за одну итерацию.
Нахождение матрицы Гессе связано с большими вычислительными затратами, и зачастую не представляется возможным. В таких случаях альтернативой могут служить [[квазиньютоновские методы]], в которых приближение матрицы Гессе строится в процессе накопления информации о кривизне функции.
=== Метод Ньютона — Рафсона ===
Метод Ньютона — Рафсона является улучшением метода Ньютона нахождения экстремума, описанного выше. Основное отличие заключается в том, что на очередной итерации каким-либо из [[оптимизация (математика)|методов одномерной оптимизации]] выбирается оптимальный шаг:
: <math>\vec{x}^{[j+1]}=\vec{x}^{[j]}-\lambda_j H^{-1}(\vec{x}^{[j]})\nabla f(\vec{x}^{[j]}),</math>
где <math>\lambda_j=\arg\min_\lambda f(\vec{x}^{[j]}-\lambda H^{-1}(\vec{x}^{[j]})\nabla f(\vec{x}^{[j]})).</math>
Для оптимизации вычислений применяют следующее улучшение: вместо того, чтобы на каждой итерации заново вычислять [[гессиан]] [[целевая функция|целевой функции]], ограничиваются начальным приближением <math>H(f(\vec{x}^{[0]}))</math> и обновляют его лишь раз в <math>m</math> шагов, либо не обновляют вовсе.
=== Применительно к задачам о наименьших квадратах ===
На практике часто встречаются задачи, в которых требуется произвести настройку свободных параметров объекта или подогнать математическую модель под реальные данные. В этих случаях появляются задачи о [[метод наименьших квадратов|наименьших квадратах]]:
: <math>F(\vec{x})=\|\vec{f}(\vec{x})\|=\sum_{i=1}^m f_i^2(\vec{x})=\sum_{i=1}^m (\varphi_i(\vec{x})-\mathcal{F}_i)^2\to\min.</math>
Эти задачи отличаются особым видом [[градиент (математика)|градиента]] и [[матрица Гессе|матрицы Гессе]]:
: <math>\nabla F(\vec{x})=2J^T(\vec{x})\vec{f}(\vec{x}),</math>
: <math>H(\vec{x})=2J^T(\vec{x})J(\vec{x})+2Q(\vec{x}),\qquad Q(\vec{x})=\sum_{i=1}^m f_i(\vec{x})H_i(\vec{x}),</math>
где <math>J(\vec{x})</math> — [[матрица Якоби]] вектор-функции <math>\vec{f}(\vec{x})</math>, <math>H_i(\vec{x})</math> — матрица Гессе для её компоненты <math>f_i(\vec{x})</math>.
Тогда очередной шаг <math>\vec{p}</math> определяется из системы:
: <math>\left[J^T(\vec{x})J(\vec{x})+\sum_{i=1}^m f_i(\vec{x})H_i(\vec{x})\right]\vec{p}=-J^T(\vec{x})\vec{f}(\vec{x}).</math>
=== Метод Гаусса — Ньютона ===
{{main|Алгоритм Гаусса — Ньютона}}
Метод Гаусса — Ньютона строится на предположении о том, что слагаемое <math>J^T(\vec{x})J(\vec{x})</math> доминирует над <math>Q(\vec{x})</math>. Это требование не соблюдается, если минимальные невязки велики, то есть если норма <math>\|\vec{f}(\vec{x})\|</math> сравнима с максимальным собственным значением матрицы <math>J^T(\vec{x})J(\vec{x})</math>. В противном случае можно записать:
: <math>J^T(\vec{x})J(\vec{x})\vec{p}=-J^T(\vec{x})\vec{f}(\vec{x}).</math>
Таким образом, когда норма <math>\|Q(\vec{x})\|</math> близка к нулю, а матрица <math>J(\vec{x})</math> имеет полный столбцевой [[ранг матрицы|ранг]], шаг <math>\vec{p}</math> мало отличается от ньютоновского (с учётом <math>Q(\vec{x})</math>), и метод может достигать квадратичной скорости сходимости, хотя вторые производные и не учитываются. Улучшением метода является [[алгоритм Левенберга — Марквардта]], основанный на [[Эвристика|эвристических]] соображениях.
=== Обобщение на комплексную плоскость ===
[[Файл:Newtroot 1 0 0 0 0 m1.png|thumb|left|300px|[[Бассейны Ньютона]] для полинома пятой степени <math>\scriptstyle{p(x)=x^5-1}</math>. Разными цветами закрашены области притяжения для разных корней. Более тёмные области соответствуют большему числу итераций.]]
До сих пор в описании метода использовались функции, осуществляющие отображения в пределах [[множество|множества]] [[вещественное число|вещественных значений]]. Однако метод может быть применён и для нахождения нуля [[функция комплексной переменной|функции комплексной переменной]]. При этом процедура остаётся неизменной:
: <math>z_{n+1}=z_n-\frac{f(z_n)}{f'(z_n)}.</math>
Особый интерес представляет выбор начального приближения <math>z_0</math>. Ввиду того, что функция может иметь несколько нулей, в различных случаях метод может сходиться к различным значениям, и вполне естественно возникает желание выяснить, какие области обеспечат сходимость к тому или иному корню. Этот вопрос заинтересовал [[Кэли, Артур|Артура Кэли]] ещё в [[1879 год]]у, однако разрешить его смогли лишь в [[1970-е|70]]-х годах [[двадцатый век|двадцатого столетия]] с появлением вычислительной техники. Оказалось, что на пересечениях этих областей (их принято называть ''областями притяжения'') образуются так называемые ''[[фрактал]]ы'' — бесконечные самоподобные геометрические фигуры.
Ввиду того, что Ньютон применял свой метод исключительно к [[полином]]ам, фракталы, образованные в результате такого применения, обрели название ''фракталов Ньютона'' или ''[[бассейны Ньютона|бассейнов Ньютона]]''.
{{-}}
== Реализация ==
=== Scala ===
<source lang="scala">
object NewtonMethod {
val accuracy = 1e-6
@tailrec
def method(x0: Double, f: Double => Double, dfdx: Double => Double, e: Double): Double = {
val x1 = x0 - f(x0) / dfdx(x0)
if (abs(x1 - x0) < e) x1
else method(x1, f, dfdx, e)
}
def g(C: Double) = (x: Double) => x*x - C
def dgdx(x: Double) = 2*x
def sqrt(x: Double) = x match {
case 0 => 0
case x if (x < 0) => Double.NaN
case x if (x > 0) => method(x/2, g(x), dgdx, accuracy)
}
}
</source>
=== Python ===
<source lang="python">
from math import sin, cos
from typing import Callable
import unittest
def newton(f: Callable[[float], float], f_prime: Callable[[float], float], x0: float,
eps: float=1e-7, kmax: int=1e3) -> float:
"""
solves f(x) = 0 by Newton's method with precision eps
:param f: f
:param f_prime: f'
:param x0: starting point
:param eps: precision wanted
:return: root of f(x) = 0
"""
x, x_prev, i = x0, x0 + 2 * eps, 0
while abs(x - x_prev) >= eps and i < kmax:
x, x_prev, i = x - f(x) / f_prime(x), x, i + 1
return x
class TestNewton(unittest.TestCase):
def test_0(self):
def f(x: float) -> float:
return x**2 - 20 * sin(x)
def f_prime(x: float) -> float:
return 2 * x - 20 * cos(x)
x0, x_star = 2, 2.7529466338187049383
self.assertAlmostEqual(newton(f, f_prime, x0), x_star)
if __name__ == '__main__':
unittest.main()
</source>
=== PHP ===
<source lang="php">
<?php
// PHP 5.4
function newtons_method(
$a = -1, $b = 1,
$f = function($x) {
return pow($x, 4) - 1;
},
$derivative_f = function($x) {
return 4 * pow($x, 3);
}, $eps = 1E-3) {
$xa = $a;
$xb = $b;
$iteration = 0;
while (abs($xb) > $eps) {
$p1 = $f($xa);
$q1 = $derivative_f($xa);
$xa -= $p1 / $q1;
$xb = $p1;
++$iteration;
}
return $xa;
}
</source>
=== Octave ===
<source lang="octave">
function res = nt()
eps = 1e-7;
x0_1 = [-0.5,0.5];
max_iter = 500;
xopt = new(@resh, eps, max_iter);
xopt
endfunction
function a = new(f, eps, max_iter)
x=-1;
p0=1;
i=0;
while (abs(p0)>=eps)
[p1,q1]=f(x);
x=x-p1/q1;
p0=p1;
i=i+1;
end
i
a=x;
endfunction
function[p,q]= resh(x) % p= -5*x.^5+4*x.^4-12*x.^3+11*x.^2-2*x+1;
p=-25*x.^4+16*x.^3-36*x.^2+22*x-2;
q=-100*x.^3+48*x.^2-72*x+22;
endfunction
</source>
=== Delphi ===
<source lang="pascal">
// вычисляемая функция
function fx(x: Double): Double;
begin
Result := x * x - 17;
end;
// производная функция от f(x)
function dfx(x: Double): Double;
begin
Result := 2 * x;
end;
function solve(fx, dfx: TFunc<Double, Double>; x0: Double): Double;
const
eps = 0.000001;
var
x1: Double;
begin
x1 := x0 - fx(x0) / dfx(x0); // первое приближение
while (Abs(x1-x0) > eps) do begin // пока не достигнута точность 0.000001
x0 := x1;
x1 := x1 - fx(x1) / dfx(x1); // последующие приближения
end;
Result := x1;
end;
// Вызов
solve(fx, dfx,4));
</source>
=== C++ ===
<source lang="cpp">
#include <stdio.h>
#include <math.h>
#define eps 0.000001
double fx(double x) { return x * x - 17;} // вычисляемая функция
double dfx(double x) { return 2 * x;} // производная функции
typedef double(*function)(double x); // задание типа function
double solve(function fx, function dfx, double x0) {
double x1 = x0 - fx(x0) / dfx(x0); // первое приближение
while (fabs(x1 - x0) > eps) { // пока не достигнута точность 0.000001
x0 = x1;
x1 = x0 - fx(x0) / dfx(x0); // последующие приближения
}
return x1;
}
int main () {
printf("%f\n", solve(fx, dfx, 4)); // вывод на экран
return 0;
}
</source>
=== C ===
<source lang="cpp">
typedef double (*function)(double x);
bozi txerq
double TangentsMethod(function f, function df, double xn, double eps) {
double x1 = xn - f(xn)/df(xn);
double x0 = xn;
while(abs(x0-x1) > eps) {
x0 = x1;
x1 = x1 - f(x1)/df(x1);
}
return x1;
}
//Выбор начального приближения
xn = MyFunction(A)*My2Derivative(A) > 0 ? B : A;
double MyFunction(double x) { return (pow(x, 5) - x - 0.2); } //Ваша функция
double MyDerivative(double x) { return (5*pow(x, 4) - 1); } //Первая производная
double My2Derivative(double x) { return (20*pow(x, 3)); } //Вторая производная
//Пример вызова функции
double x = TangentsMethod(MyFunction, MyDerivative, xn, 0.1)
</source>
=== [[Haskell]] ===
<syntaxhighlight lang="haskell">
import Data.List ( iterate' )
main :: IO ()
main = print $ solve (\ x -> x * x - 17) ( * 2) 4
-- Функция solve универсальна для всех вещественных типов значения которых можно сравнивать.
solve = esolve 0.000001
esolve epsilon func deriv x0 = fst . head $ dropWhile pred pairs
where
pred (xn, xn1) = (abs $ xn - xn1) > epsilon -- Функция pred определяет достигнута ли необходимая точность.
next xn = xn - func xn / deriv xn -- Функция next вычисляет новое приближение.
iters = iterate' next x0 -- Бесконечный список итераций.
pairs = zip iters (tail iters) -- Бесконечный список пар итераций вида: [(x0, x1), (x1, x2) ..].
</syntaxhighlight>
== Литература ==
* {{публикация|книга
|автор = Акулич И. Л.
|заглавие = Математическое программирование в примерах и задачах
|вид = Учеб. пособие для студентов эконом. спец. вузов
|место = М.
|издательство = Высшая школа
|год = 1986
|страниц = 319
|иллюстрации = ил.
|ббк = 22.1 А44
|удк = 517.8
}}
* {{публикация|книга
|автор = Амосов А. А., Дубинский Ю. А., Копченова Н. П.
|заглавие = Вычислительные методы для инженеров
|вид = Учеб. пособие
|место = М.
|издательство = Высшая школа
|год = 1994
|страниц = 544
|иллюстрации = ил.
|isbn = 5-06-000625-5
|ббк = 32.97 А62
|удк = 683.1
}}
* {{публикация|книга|автор = Бахвалов Н. С., [[Жидков, Николай Петрович|Жидков Н. П.]], Кобельков Г. Г.|заглавие = Численные методы|оригинал = |ссылка = |издание = 8-е изд.|место = М.|издательство = Лаборатория Базовых Знаний|год = 2000|страницы =|isbn = }}
* {{публикация|книга|заглавие = Исаак Ньютон|автор = Вавилов С. И. | место = М.| издательство = Изд. АН СССР| год = 1945|ссылка = http://vivovoco.astronet.ru/VV/BOOKS/NEWTON/CHAPTER_13.HTM}}
* {{публикация|книга|автор = Волков Е. А.|заглавие = Численные методы|оригинал = |ссылка = |издание =|место = М.|издательство = Физматлит|год = 2003|страницы =|isbn = }}
* {{публикация|книга|автор = Гилл Ф., Мюррей У., Райт М.|заглавие = Практическая оптимизация. Пер. с англ|оригинал = |ссылка = |издание =|место = М.|издательство = Мир|год = 1985|страницы =|isbn = }}
* {{публикация|книга|автор = Корн Г., Корн Т.|заглавие = Справочник по математике для научных работников и инженеров|оригинал = |ссылка = |издание = |место = М.|издательство = Наука|год = 1970|страницы = 575—576|isbn = }}
* {{публикация|книга|автор = Коршунов Ю. М., Коршунов Ю. М.|заглавие = Математические основы кибернетики|оригинал = |ссылка = |издание =|место М.|издательство = Энергоатомиздат|год = 1972|страницы =|isbn = }}
* {{публикация|книга|автор = Максимов Ю. А.,Филлиповская Е. А.|заглавие = Алгоритмы решения задач нелинейного программирования|оригинал = |ссылка = |издание =|место = М.|издательство = МИФИ|год = 1982|страницы =|isbn = }}
* {{публикация|книга|автор = Морозов А. Д.|заглавие = Введение в теорию фракталов|оригинал = |ссылка = |издание = |место = |издательство = МИФИ|год = 2002|страницы =|isbn = }}
== См. также ==
* [[Метод простой итерации]]
* [[Двоичный поиск]]
* [[Метод дихотомии]]
* [[Метод секущих]]
* [[Метод Мюллера]]
* [[Метод хорд]]
* [[Метод бисекции]]
* [[Фрактал]]
* [[Численное решение уравнений]]
* [[Целочисленный квадратный корень]]
* [[Быстрый обратный квадратный корень]]
== Ссылки ==
{{Родственные проекты
|Викиучебник = Category:Newton's method
|Викисклад = Newton Method
}}
* [http://fractalworld.xaoc.ru/article/frnew.html «Бассейны Ньютона» на сайте fractalworld.xaoc.ru]
* [https://web.archive.org/web/20080506085010/http://www.scottish-wetlands.org/073/73081.htm «Исаак Ньютон» на сайте www.scottish-wetlands.org]
* [http://math.nsc.ru/LBRT/g2/english/ssk/talk_lvk95.html «Математические работы Канторовича» на сайте Института математики СО РАН]
* {{springer|title=Newton method|id=p/n066560}}
* {{MathWorld|title=Newton's Method|urlname=NewtonsMethod}}
* [http://en.citizendium.org/wiki/Newton%27s_method Newton’s method, Citizendium.]
* [https://web.archive.org/web/20190524083302/http://mathfaculty.fullerton.edu/mathews/n2003/NewtonAccelerateMod.html Mathews, J., The Accelerated and Modified Newton Methods, Course notes.]
* [http://www.ece.mcmaster.ca/~xwu/part2.pdf Wu, X., Roots of Equations, Course notes.]
{{Методы оптимизации}}
[[Категория:Численные методы решения уравнений]]
[[Категория:Алгоритмы оптимизации]]
[[Категория:Исаак Ньютон]]' |