Журнал фильтра правок

''''Метод Ньютона''', '''алгоритм Ньютона''' (также известный как '''метод касательных''') — это итерационный [[Численные методы|численный метод]] нахождения корня (нуля) заданной [[Функция (программирование)|функции]]. Метод был впервые предложен английским [[физик]]ом, [[математик]]ом и [[астроном]]ом [[Ньютон, Исаак|Исааком Ньютоном]] ([[1643]]—[[1727]]), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах [[метод простой итерации|простой итерации]]. Метод обладает квадратичной [[скорость сходимости|сходимостью]]. Улучшением метода является [[метод хорд и касательных]]. Также метод Ньютона может быть использован для решения [[задача оптимизации|задач оптимизации]], в которых требуется определить нуль первой [[Производная функции|производной]] либо [[градиент]] в случае многомерного пространства. {{TOCright}} == Описание метода == === Обоснование === Чтобы численно решить уравнение <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> Эта функция в окрестности корня осуществляет сжимающее отображение<ref>'''''Доказательство:''''' <small>Пусть дана [[Функция (программирование)|функция]] [[вещественное число|действительного переменного]] дважды [[непрерывная дифференцируемость|непрерывно дифференцируемая]] в своей [[область определения|области определения]], [[Производная функции|производная]] которой нигде не обращается в нуль: : <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></ref>, и алгоритм нахождения численного решения уравнения <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>.]] === Геометрическая интерпретация === Основная идея метода заключается в следующем: задаётся начальное приближение вблизи предположительного корня, после чего строится касательная к исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка и берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность. Пусть <math>f(x)\colon[a,\;b]\to\R\!</math> — определённая на отрезке <math>[a,\;b]</math> и [[Дифференцируемая функция|дифференцируемая]] на нём действительнозначная функция. Тогда формула итеративного исчисления приближений может быть выведена следующим образом: : <math>f'(x_n)=\mathrm{tg}\,\alpha=\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</math> — угол наклона касательной в точке <math>x_n\!</math>. Следовательно искомое выражение для <math>x_{n+1}\!</math> имеет вид: : <math>x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.\,\!</math> Итерационный процесс начинается с некоего начального приближения <math>x_0</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{,}9}09\;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} x, & 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> и надо найти его решение. Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Она носит имя советского [[математик]]а и [[экономист]]а, лауреата [[Нобелевская премия|Нобелевской премии]] по экономике [[1975 год]]а «за вклад в теорию оптимального распределения ресурсов» [[Канторович, Леонид Витальевич|Леонида Витальевича Канторовича]] ([[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>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>\gamma\!</math> следует выбрать равным <math>\max\limits_x|\varphi'(x)|.\!</math> === Многомерный случай === Обобщим полученный результат на многомерный случай. Пускай необходимо найти решение системы: : <math>\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.</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}(\vec{x}^{[j+1]}_k-\vec{x}_k^{[j]})=0,\qquad i=1,\;2,\;\ldots,\;n,\!</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})=J^T(\vec{x}) f(\vec{x}),</math> : <math>H(\vec{x})=J^T(\vec{x})J(\vec{x})+Q(\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})f(\vec{x}).</math> === Метод Гаусса — Ньютона === Метод Гаусса — Ньютона строится на предположении о том, что слагаемое <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})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]]-х годах [[двадцатый век|двадцатого столетия]] с появлением вычислительной техники. Оказалось, что на пересечениях этих областей (их принято называть ''областями притяжения'') образуются так называемые ''[[фрактал]]ы'' — бесконечные самоподобные геометрические фигуры. Ввиду того, что Ньютон применял свой метод исключительно к [[полином]]ам, фракталы, образованные в результате такого применения, обрели название ''фракталов Ньютона'' или ''[[бассейны Ньютона|бассейнов Ньютона]]''. <br clear="all" /> == Литература == # {{книга|автор = Акулич И. Л.|заглавие = Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов|оригинал = |ссылка = |издание = |место = М.|издательство = Высш. шк.|год = 1986|страницы =|isbn = }} # {{книга|автор = Амосов А. А., Дубинский Ю. А., Копченова Н. П.|заглавие = Вычислительные методы для инженеров|оригинал = |ссылка |издание = |место = М.|издательство = Мир|год = 1998|страницы =|isbn = }} # {{книга|автор = Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г.|заглавие = Численные методы|оригинал = |ссылка = |издание = 8-е изд.|место = М.|издательство = Лаборатория Базовых Знаний|год = 2000|страницы =|isbn = }} # {{книга|заглавие = Исаак Ньютон|автор = Вавилов С. И. | место = М.| издательство = Изд. АН СССР| год = 1945|ссылка = http://vivovoco.rsl.ru/VV/BOOKS/NEWTON/CHAPTER_13.HTM}} # {{книга|автор = Волков Е. А.|заглавие = Численные методы|оригинал = |ссылка = |издание =|место = М.|издательство = Физматлит|год = 2003|страницы =|isbn = }} # {{книга|автор = Гилл Ф., Мюррей У., Райт М.|заглавие = Практическая оптимизация. Пер. с англ|оригинал = |ссылка = |издание =|место = М.|издательство = Мир|год = 1985|страницы =|isbn = }} # {{книга|автор = Корн Г., Корн Т.|заглавие = Справочник по математике для научных работников и инженеров|оригинал = |ссылка = |издание = |место = М.|издательство = Наука|год = 1970|страницы = 575-576|isbn = }} # {{книга|автор = Коршунов Ю. М., Коршунов Ю. М.|заглавие = Математические основы кибернетики|оригинал = |ссылка = |издание =|место М.|издательство = Энергоатомиздат|год = 1972|страницы =|isbn = }} # {{книга|автор = Максимов Ю. А.,Филлиповская Е. А.|заглавие = Алгоритмы решения задач нелинейного программирования|оригинал = |ссылка = |издание =|место = М.|издательство = МИФИ|год = 1982|страницы =|isbn = }} # {{книга|автор = Морозов А. Д.|заглавие = Введение в теорию фракталов|оригинал = |ссылка = |издание = |место = |издательство = МИФИ|год = 2002|страницы =|isbn = }} == Примечания == {{примечания}} == См. также == * [[Метод простой итерации]] * [[Двоичный поиск]] * [[Метод дихотомии]] * [[Метод секущих]] * [[Метод Мюллера]] * [[Метод хорд]] * [[Метод Чебышёва]] * [[Фрактал]] * [[Численное решение уравнений]] == Ссылки == * [http://fractalworld.xaoc.ru/article/frnew.html «Бассейны Ньютона» на сайте fractalworld.xaoc.ru] * [http://www.scottish-wetlands.org/073/73081.htm «Исаак Ньютон» на сайте www.scottish-wetlands.org] * [http://math.nsc.ru/LBRT/g2/english/ssk/talk_lvk95.html «Математические работы Канторовича» на сайте Института математики СО РАН] {{Хорошая статья|Математика}} {{Link GA|de}} [[Категория:Численные методы]] [[Категория:Алгоритмы оптимизации]] [[af:Newton-Raphson metode]] [[ar:طريقة نيوتن]] [[bg:Метод на Нютон]] [[ca:Mètode de Newton]] [[cs:Metoda tečen]] [[da:Newtons metode]] [[de:Newton-Verfahren]] [[el:Μέθοδος Νιούτον]] [[en:Newton's method]] [[es:Método de Newton]] [[fi:Newtonin menetelmä]] [[fr:Méthode de Newton]] [[he:שיטת ניוטון-רפסון]] [[hu:Newton-módszer]] [[id:Metode Newton]] [[it:Metodo delle tangenti]] [[ja:ニュートン法]] [[ko:뉴턴의 방법]] [[nl:Newton-Raphson]] [[pl:Metoda Newtona]] [[pt:Método de Newton]] [[simple:Newton's method]] [[sl:Newtonova metoda]] [[sv:Newtons metod]] [[zh:牛顿法]]'