Как найти корень уравнения методом ньютона - Сайт, где вы сможете решить свои вопросы

У этого термина существуют и другие значения, см. Метод (значения).

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

Описание метода[править | править код]

Обоснование[править | править код]

Чтобы численно решить уравнение f(x)=0 методом простой итерации, его необходимо привести к эквивалентному уравнению: , где varphi — сжимающее отображение.

Для наилучшей сходимости метода в точке очередного приближения $x^{*}$ должно выполняться условие ${displaystyle varphi '(x^{*})=0}$ . Решение данного уравнения ищут в виде , тогда:

${displaystyle varphi '(x^{*})=1+alpha '(x^{*})f(x^{*})+alpha (x^{*})f'(x^{*})=0.}$

В предположении, что точка приближения «достаточно близка» к корню и что заданная функция непрерывна ${displaystyle (f(x^{*})approx f({tilde {x}})=0)}$ , окончательная формула для такова:

${displaystyle alpha (x)=-{frac {1}{f'(x)}}.}$

С учётом этого функция определяется:

${displaystyle varphi (x)=x-{frac {f(x)}{f'(x)}}.}$

При некоторых условиях эта функция в окрестности корня осуществляет сжимающее отображение.

В этом случае алгоритм нахождения численного решения уравнения f(x)=0 сводится к итерационной процедуре вычисления:

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

По теореме Банаха последовательность приближений стремится к корню уравнения f(x)=0 .

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

Геометрическая интерпретация[править | править код]

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

Пусть 1) вещественнозначная функция непрерывно дифференцируема на интервале ;
2) существует искомая точка ${displaystyle x^{*}in (a,,b)}$ : ${displaystyle f(x^{*})=0}$ ;
3) существуют C > 0 и такие, что

для ${displaystyle xin (a,,x^{*}-delta ]cup [x^{*}+delta ,,b)}$
и
для ${displaystyle xin (x^{*}-delta ,,x^{*})cup (x^{*},,x^{*}+delta )}$ ;
4) точка ${displaystyle x_{n}in (a,,b)}$ такова, что ${displaystyle f(x_{n})neq 0}$ .
Тогда формула итеративного приближения $x_{n}$ к $x^{{*}}$
может быть выведена из геометрического смысла касательной следующим образом:

${displaystyle 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}}},}$

где ${displaystyle alpha _{n}}$ — угол наклона касательной прямой
${displaystyle y(x)=f(x_{n})+(x-x_{n})cdot mathrm {tg} ,alpha _{n}}$
к графику
в точке ${displaystyle (x_{n};f(x_{n}))}$ .

Следовательно (в уравнении касательной прямой полагаем ${displaystyle y(x_{n+1})=0}$ ) искомое выражение для $x_{{n+1}}$ имеет вид :

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

Если ${displaystyle x_{n+1}in (a,,b)}$ , то это значение можно использовать в качестве следующего приближения к
$x^{{*}}$ .

Если ${displaystyle x_{n+1}notin (a,,b)}$ , то имеет место «перелёт» (корень $x^{{*}}$ лежит рядом с границей ). В этом случае надо (воспользовавшись идеей метода половинного деления) заменять
$x_{{n+1}}$ на
${displaystyle {frac {x_{n}+x_{n+1}}{2}}}$
до тех пор, пока точка «не вернётся» в область поиска
.

Замечания. 1) Наличие непрерывной производной даёт возможность строить непрерывно меняющуюся касательную на всей области поиска решения .
2) Случаи граничного (в точке или в точке ) расположения искомого решения $x^{{*}}$ рассматриваются аналогичным образом.
3) С геометрической точки зрения равенство
${displaystyle f'(x_{n})=0}$
означает, что касательная прямая к графику

в точке
${displaystyle (x_{n};f(x_{n}))}$ –
параллельна оси

и при
${displaystyle f(x_{n})neq 0}$
не пересекается с ней в конечной части.
4) Чем больше константа C > 0 и чем меньше константа из пункта 3 условий,
тем для ${displaystyle x_{n}in (a,,x^{*}-delta ]cup [x^{*}+delta ,,b)}$
пересечение касательной к графику и оси ближе к точке ${displaystyle (x^{*};;0)}$ ,
то есть тем ближе значение $x_{{n+1}}$ к искомой ${displaystyle x^{*}in (a,,b)}$ .

Итерационный процесс начинается с некоторого начального приближения
${displaystyle x_{0}in (a,,b)}$ ,
причём между
${displaystyle x_{0}in (a,,b)}$
и искомой точкой
${displaystyle x^{*}in (a,,b)}$
не должно быть других нулей функции
,
то есть «чем ближе $x_{0}$
к искомому корню $x^{{*}}$ ,
тем лучше». Если предположения о нахождении $x^{{*}}$ отсутствуют, методом проб и ошибок можно сузить область возможных значений, применив теорему о промежуточных значениях.

Для предварительно заданных ${displaystyle varepsilon _{x}>0}$ , ${displaystyle varepsilon _{f}>0}$
итерационный процесс завершается если
${displaystyle leftvert {frac {f(x_{n})}{f'(x_{n})}}rightvert approx vert x_{n+1}-x_{n}vert <varepsilon _{x}}$ и
${displaystyle vert f(x_{n+1})vert <varepsilon _{f}}$ .
В частности, для матрицы дисплея ${displaystyle varepsilon _{x}}$ и ${displaystyle varepsilon _{f}}$ могут быть рассчитаны,
исходя из масштаба отображения графика ,
то есть если $x_{n}$ и $x_{{n+1}}$ попадают в один вертикальный, а ${displaystyle f(x_{n})}$ и ${displaystyle f(x_{n+1})}$ в один горизонтальный ряд.

Алгоритм[править | править код]

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

Пример[править | править код]

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

Рассмотрим задачу о нахождении положительных , для которых $cos x=x^{3}$ . Эта задача может быть представлена как задача нахождения нуля функции $f(x)=cos x-x^{3}$ . Имеем выражение для производной $f'(x)=-sin x-3x^{2}$ . Так как для всех и $x^{3}>1$ для x>1 , очевидно, что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение $x_{0}=0{,}5$ , тогда:

${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}}$

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

Условия применения[править | править код]

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

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

Контрпримеры[править | править код]

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

Пусть

${displaystyle f(x)=x^{3}-2x+2.}$

Тогда

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

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

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

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

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

${displaystyle f(x)={begin{cases}0,&x=0,\x+x^{2}sin left({dfrac {2}{x}}right),&xneq 0.end{cases}}}$

Тогда и всюду, кроме 0.

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

Таким образом не ограничено вблизи корня, и метод будет расходиться, хотя функция всюду дифференцируема, её производная не равна нулю в корне, бесконечно дифференцируема везде, кроме как в корне, а её производная ограничена в окрестности корня.

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

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

${displaystyle f(x)=x+x^{4/3}.}$

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

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

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

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

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

Пусть

${displaystyle f(x)=x^{2}.}$

Тогда и следовательно . Таким образом сходимость метода не квадратичная, а линейная, хотя функция всюду бесконечно дифференцируема.

Ограничения[править | править код]

Пусть задано уравнение f(x)=0 , где и надо найти его решение.

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

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

Если существуют такие константы , что:

${displaystyle {frac {1}{|f'(x)|}}<A}$ на , то есть сут и не равна нулю;
${displaystyle left|{frac {f(x)}{f'(x)}}right|<B}$ на , то есть ограничена;
на , и ${displaystyle |f''(x)|leqslant Cleqslant {frac {1}{2AB}}}$ ;

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

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

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

${displaystyle |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}.}$

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

функция должна быть ограничена;
функция должна быть гладкой, дважды дифференцируемой;
её первая производная равномерно отделена от нуля;
её вторая производная должна быть равномерно ограничена.

Историческая справка[править | править код]

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

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

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

Обобщения и модификации[править | править код]

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

Метод секущих[править | править код]

Родственный метод секущих является «приближённым» методом Ньютона и позволяет не вычислять производную. Значение производной в итерационной формуле заменяется её оценкой по двум предыдущим точкам итераций:

${displaystyle f'(x_{n})approx {frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}}$ .

Таким образом, основная формула имеет вид

${displaystyle x_{n+1}=x_{n}-f(x_{n})cdot {frac {x_{n}-x_{n-1}}{f(x_{n})-f(x_{n-1})}}.}$

Этот метод схож с методом Ньютона, но имеет немного меньшую скорость сходимости. Порядок сходимости метода равен золотому сечению — 1,618…

Замечания. 1) Для начала итерационного процесса требуются два различных значения
$x_{0}$ и
$x_{1}$ .
2) В отличие от «настоящего метода Ньютона» (метода касательных), требующего хранить только ${displaystyle x_{n}}$
(и в ходе вычислений — временно ${displaystyle f(x_{n})}$ и ${displaystyle f'(x_{n})}$ ),
для метода секущих требуется сохранение
${displaystyle x_{n-1}}$ ,
${displaystyle x_{n}}$ ,
${displaystyle f(x_{n-1})}$ ,
${displaystyle f(x_{n})}$ .
3) Применяется, если вычисление f'(x) затруднено
(например, требует большого количества машинных ресурсов: времени и/или памяти).

Метод одной касательной[править | править код]

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

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

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

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

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

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

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

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

Этот метод является частным случаем метода простой итерации. Он имеет линейный порядок сходимости.

Метод Ньютона-Фурье[править | править код]

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

Предположим, что f(x) дважды непрерывно дифференцируема на отрезке [a, b] и что f имеет корень на этом интервале. Дополнительно положим, что f′(x), f″(x) ≠ 0 на этом отрезке (например, это верно, если f(a) < 0, f(b) > 0, и f″(x) > 0 на этом отрезке). Это гарантирует наличие единственного корня на этом отрезке, обозначим его α. Эти рассуждения относятся к вогнутой вверх функции. Если она вогнута вниз, то заменим f(x) на −f(x), поскольку они имеют одни и те же корни.

Пусть x₀ = b будет правым концом отрезка, на котором мы ищем корень, а z₀ = a – левым концом того же отрезка. Если x_n найдено, определим

${displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}},}$

которое выражает обычный метод Ньютона, как описано выше. Затем определим

${displaystyle z_{n+1}=z_{n}-{frac {f(z_{n})}{f'(x_{n})}},}$

где знаменатель равен f′(x_n), а не f′(z_n). Итерации x_n будут строго убывающими к корню, а итерации z_n – строго возрастающими к корню. Также выполняется следующее соотношение:

${displaystyle lim _{nto infty }{frac {x_{n+1}-z_{n+1}}{(x_{n}-z_{n})^{2}}}={frac {f''(alpha )}{2f'(alpha )}}}$

таким образом, расстояние между x_n и z_n уменьшается квадратичным образом.

Многомерный случай[править | править код]

Обобщим полученный результат на многомерный случай.

Пусть необходимо найти решение системы:

${displaystyle 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.}$

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

${displaystyle f_{i}+sum _{k=1}^{n}{frac {partial f_{i}}{partial x_{k}}}(x_{k}^{[j+1]}-x_{k}^{[j]})=0,qquad i=1,;2,;ldots ,;m,}$

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

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

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

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

где — гессиан функции .

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

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

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

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

Метод Ньютона — Рафсона[править | править код]

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

${displaystyle {vec {x}}^{[j+1]}={vec {x}}^{[j]}-lambda _{j}H^{-1}({vec {x}}^{[j]})nabla f({vec {x}}^{[j]}),}$

где ${displaystyle lambda _{j}=arg min _{lambda }f({vec {x}}^{[j]}-lambda H^{-1}({vec {x}}^{[j]})nabla f({vec {x}}^{[j]})).}$
Для оптимизации вычислений применяют следующее улучшение: вместо того, чтобы на каждой итерации заново вычислять гессиан целевой функции, ограничиваются начальным приближением ${displaystyle H(f({vec {x}}^{[0]}))}$ и обновляют его лишь раз в шагов, либо не обновляют вовсе.

Применительно к задачам о наименьших квадратах[править | править код]

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

$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 .$

Эти задачи отличаются особым видом градиента и матрицы Гессе:

$nabla F({vec {x}})=2J^{T}({vec {x}}){vec {f}}({vec {x}}),$

$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}}),$

где — матрица Якоби вектор-функции , $H_{i}({vec {x}})$ — матрица Гессе для её компоненты $f_{i}({vec {x}})$ .

Тогда очередной шаг определяется из системы:

$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}}).$

Метод Гаусса — Ньютона[править | править код]

Метод Гаусса — Ньютона строится на предположении о том, что слагаемое $J^{T}({vec {x}})J({vec {x}})$ доминирует над . Это требование не соблюдается, если минимальные невязки велики, то есть если норма сравнима с максимальным собственным значением матрицы $J^{T}({vec {x}})J({vec {x}})$ . В противном случае можно записать:

$J^{T}({vec {x}})J({vec {x}}){vec {p}}=-J^{T}({vec {x}}){vec {f}}({vec {x}}).$

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

Обобщение на комплексную плоскость[править | править код]

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

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

${displaystyle z_{n+1}=z_{n}-{frac {f(z_{n})}{f'(z_{n})}}.}$

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

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

Реализация[править | править код]

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) 
  }
}

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()

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;

}

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

Delphi[править | править код]

// вычисляемая функция
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));

C++[править | править код]

#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("%fn", solve(fx, dfx, 4)); // вывод на экран
  return 0;
}

C[править | править код]

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)

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) ..].

Литература[править | править код]

Акулич И. Л. Математическое программирование в примерах и задачах : Учеб. пособие для студентов эконом. спец. вузов. — М. : Высшая школа, 1986. — 319 с. : ил. — ББК 22.1 А44. — УДК 517.8^(G).
Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров : Учеб. пособие. — М. : Высшая школа, 1994. — 544 с. : ил. — ББК 32.97 А62. — УДК 683.1^(G). — ISBN 5-06-000625-5.
Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М. : Лаборатория Базовых Знаний, 2000.
Вавилов С. И. Исаак Ньютон. — М. : Изд. АН СССР, 1945.
Волков Е. А. Численные методы. — М. : Физматлит, 2003.
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М. : Мир, 1985.
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М. : Наука, 1970. — С. 575—576.
Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — Энергоатомиздат, 1972.
Максимов Ю. А.,Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М. : МИФИ, 1982.
Морозов А. Д. Введение в теорию фракталов. — МИФИ, 2002.

См. также[править | править код]

Метод простой итерации
Двоичный поиск
Метод дихотомии
Метод секущих
Метод Мюллера
Метод хорд
Метод бисекции
Фрактал
Численное решение уравнений
Целочисленный квадратный корень
Быстрый обратный квадратный корень

Ссылки[править | править код]

«Бассейны Ньютона» на сайте fractalworld.xaoc.ru
«Исаак Ньютон» на сайте www.scottish-wetlands.org
«Математические работы Канторовича» на сайте Института математики СО РАН
Hazewinkel, Michiel, ed. (2001), Newton method, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
Weisstein, Eric W. Newton’s Method (англ.) на сайте Wolfram MathWorld.
Newton’s method, Citizendium.
Mathews, J., The Accelerated and Modified Newton Methods, Course notes.
Wu, X., Roots of Equations, Course notes.

Источник

Решение уравнения методом Ньютона

Метод
Ньютона, алгоритм Ньютона (также известный
как метод касательных) — это итерационный
численный метод нахождения корня (нуля)
заданной функции.

Достоинства
метода Ньютона:
Метод Ньютона – самый быстрый способ
нахождения корней уравнений: обычно
заданная точность достигается за 2-3
итерации. Очень быстрая сходимость по
сравнению с методом половинного деления
и методом простой итерации к заданной
точности.

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

Значение
корня новой итерации вычисляется по
формуле

Алгоритм

Задается
начальное приближение x₀.
Пока
не выполнено условие остановки, в
качестве которого можно взять

или

(то есть погрешность в нужных пределах),
вычисляют новое приближение:

[1].

Производные
функции

;
;
если

>0

если

Точное значение корня

Первое
уравнение – кубическое уравнение

Решение
кубического уравнения по формуле Кардано

Кубическое
уравнение в каноническом виде:

Обозначим
дискриминант кубического уравнения

По
формулам Кардано 3 корня уравнения
определяются следующим образом:

где

При
этом количество корней уравнения
определяются следующим образом:

Если

, уравнение имеет три действительных
корня.

Если

,
уравнение имеет один действительный и
два комплексно сопряженных корня.

Если

, уравнение имеет два действительных
корня. Если p = q = 0, уравнение имеет один
действительный корень [2].

Разрабатываемая
функция будет вычислять только первый
корень. При наличии других действительных
корнях будет сообщать об этом.

Наше
уравнение имеет вид:

Следовательно

Вычисление
корня по формуле Кардано:

float
al, be,//альфа, бетта

p,
q,//коэффициенты канонического уравнения

de;//дискриминант
(дельта)

p
= b / a;

q
= c / a;

de
= pow(p / 3, 3) + pow(q / 2, 2);

al
= pow(-q / 2 + pow(de, 0.5), (float)1/3);

be
= pow(-q / 2 – pow(de, 0.5), (float)1/3);

if(de
<= 0)

cout<<“nYravnenie
imeet neskol’ko deistvitelnuh kornei.”;

return
al + be;

Второе
уравнение – тригонометрическое уравнение

Найдем
точное решение уравнения

Уравнение
имеет множество корней. Нас интересует
ближайший корень к точке x0,
следовательно, необходимо найти ближайшее
целое значение k.

Тогда
точное решение будет в соответствии с
найденным k:

int
k;

k
= (x0 – asin(-c / a) + b) / (2 * M_PI);

return
asin(-c / a) + 2 * M_PI * k – b;

Третье
уравнение – логарифмическое уравнение

Два
возможных точных решения:

Нам
необходимо выбрать ближайший к x0.
То есть сравниваем расстояния х1х0 и
х2х0 и выбираем ближайший:

if
(fabs(exp(-c / a) – b – x0) < fabs(-exp(-c / a) – b – x0))

return
exp(-c / a) – b;

else

return
-exp(-c / a) – b

Абсолютная и относительная погрешность вычисления

Абсолютная
погрешность вычисления находится как
модуль разности между точным и приближенным
решением [3].

А
относительной погрешностью приближённого
числа называется отношение абсолютной
погрешности приближённого числа к
самому этому числу в процентном
соотношении.

Так
в нашем случае

fabs(pribl
– toch)
– абсолютная погрешность;

fabs(pribl
– toch)
/ toch
* 100 – относительная погрешность.

Где
pribl
– приближенное решение интеграла
(методом левых прямоугольников), toch
– точное решение интеграла.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

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

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

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

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

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

Рис.1. График изменение функции

Проведенная в любой точке касательная линия к графику функции определяется производной данной функции в рассматриваемой точке, которая в свою очередь определяется тангенсом угла α (). Точка пересечения касательной с осью абсцисс определяется исходя из следующего соотношения в прямоугольном треугольнике: тангенс угла в прямоугольном треугольнике определяется отношением противолежащего катета к прилежащему катету треугольнику. Таким образом, на каждом шаге строится касательная к графику функции в точке очередного приближения .Точка пересечения касательной с осью Ox будет являться следующей точкой приближения . В соответствии с рассматриваемым методом расчет приближенного значения корня на i-итерации производится по формуле:

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

Условием окончания итерационного процесса является выполнение следующего условия:

где ˗ допустимая погрешность определения корня.

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

Математическое обоснование

Пусть дана вещественная функция , которая определена и непрерывна на рассматриваемом участке. Необходимо найти вещественный корень рассматриваемой функции.

Вывод уравнения основано на методе простых итераций, в соответствии с которым уравнение приводят к эквивалентному уравнению при любой функции . Введем понятие сжимающего отображения, которое определяется соотношением .

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

Производная сжимающего отображения определяется в следующем виде:

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

С учетом этого сжимающая функция прием следующий вид:

Таким образом, алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:

Алгоритм нахождения корня нелинейного уравнения по методу Ньютона для уравнения с одной переменной

1. Задать начальную точку приближенного значения корня функции , а также погрешность расчета (малое положительное число ) и начальный шаг итерации ().

2. Выполнить расчет приближенного значения корня функции в соответствии с формулой:

3. Проверяем приближенное значение корня на предмет заданной точности, в случае:

– если разность двух последовательных приближений станет меньше заданной точности , то итерационный процесс заканчивается.

– если разность двух последовательных приближений не достигает необходимой точности , то необходимо продолжить итерационный процесс и перейти к п.2 рассматриваемого алгоритма.

Пример решения уравнений по методу Ньютона для уравнения с одной переменной

В качестве примера, рассмотрим решение нелинейного уравнения методом Ньютона для уравнения с одной переменной. Корень необходимо найти с точностью в качестве первого приближения .

Вариант решения нелинейного уравнения в программном комплексе MathCAD представлен на рисунке 3.

Результаты расчетов, а именно динамика изменения приближенного значения корня, а также погрешности расчета от шага итерации представлены в графической форме (см. рис.2).

Рис.2. Результаты расчета по методу Ньютона для уравнения с одной переменной

Для обеспечения заданной точности при поиске приближенного значения корня уравнения в диапазоне необходимо выполнить 4 итерации. На последнем шаге итерации приближенное значение корня нелинейного уравнения будет определяться значением: .

Рис.3. Листинг программы в MathCad

Модификации метода Ньютона для уравнения с одной переменной

Существует несколько модификаций метода Ньютона, которые направлены на упрощение вычислительного процесса.

Упрощенный метод Ньютона

В соответствии с методом Ньютона требуется вычислять производную функции f(x) на каждом шаге итерации, что ведет к увеличению вычислительных затрат. Для уменьшения затрат, связанных с вычислением производной на каждом шаге расчета, можно произвести замену производной f’(x_n) в точке x_n в формуле на производную f’(x₀) в точке x₀. В соответствии с данным методом расчета приближенное значение корня определяется по следующей формуле:

Таким образом, на каждом шаге расчета строятся прямые, которые параллельны касательной к кривой y=f(x) в точке B₀ (см. рис.4). Преимуществом данного метода является то, что производная функции вычисляется один раз.

Рис.4. Модифицированный метод Ньютона

Разностный метод Ньютона

В соответствии с методом Ньютона требуется вычислять производную функции f(x) на каждом шаге итерации, что не всегда удобно, а иногда практически невозможно. Данный способ позволяет производную функции заменить разностным отношением (приближенным значением):

В результате приближенное значение корня функции f(x) будет определяться выражением разностного метода Ньютона:

Двух шаговый метод Ньютона

В результате приближенное значение корня функции f(x) будет определяться следующим выражением:

Рис.5. Двух шаговый метод Ньютона

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

Источник

Приветствую Вас, уважаемые Читатели! В реальной жизни не всегда требуется строгая математическая точность, ведь иногда достаточно решить, например, уравнение с заранее заданной погрешностью. Если для алгебраических уравнений до пятой степени мы всегда можем вывести общую формулу (спасибо Виету, Кардано и Феррари), то уравнения выше пятой включительно уже в общем виде не обязаны выражаться через привычные пять математических операций (четыре арифметических и извлечение корня).

Так себе формула, учитывая необходимость приведения произвольного кубического уравнения к указанному виду. Источник: http://900igr.net/up/datas/132129/012.jpg

А уж когда речь идёт об уравнениях, включающих трансцендентные выражения (тригонометрические функции, логарифмы), точное решение порой становится невозможным. К счастью в арсенале вычислительной математики есть большое количество приближенных методов решения уравнений, об одном из которых я Вам сегодня расскажу. Итак, поехали!

Источник: https://avatars.mds.yandex.net/get-zen_doc/3323992/pub_602179e7eccec86b33121c35_60217af8b73c460f6ca15589/scale_1200

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

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

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

Мы нашли координаты следующей точки. Что будет, если повторить этот алгоритм еще раз, еще раз…?

Ордината нашей точки будет неограниченно (это показал Ньютон) с каждой новой итерацией приближаться (как будто по спирали) к точке , которая и является корнем нашего уравнения! В этом и состоит метод Ньютона, давайте попробуем на реальном уравнении!

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

Справа мы считаем модуль погрешности. Напоминаю, что мы три знака после запятой соответствуют погрешности менее 0,001. Продолжаем аналогичные вычисления до достижения нужного результата:

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

Метод Ньютона, в отличии от метода половинных отрезков обладает квадратичной сходимостью: с каждым следующим шагом число верных значащих разрядов будет увеличиваться примерно в соотношении 1:2:4:8 и т.д., но для этого нужно сразу задаваться требуемым количеством знаков после запятой для округления и более точным начальным значением. Спасибо за внимание!

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

Источник

Численные методы решения нелинейных уравнений

Корни нелинейных уравнений

Пусть дано нелинейное уравнение

f(x)=0,qquad mathsf{(3.1)}

где f(x) — функция, определенная и непрерывная на некотором промежутке. В некоторых случаях на функцию f(x) могут быть наложены дополнительные ограничения, например, непрерывность первой и второй производных, что специально оговаривается. Функция f(x) может быть задана в виде алгебраического многочлена или трансцендентной функции (тогда ей соответствует алгебраическое или трансцендентное уравнение).

Требуется найти корни нелинейного уравнения (3.1), т.е. числа $x_{ast1},x_{ast2},ldots$ которые путем подстановки их в (3.1) превращают уравнение в верное числовое равенство. Числа $x_{ast1},x_{ast2},ldots$ называются также нулями функции f(x) .

На практике часто бывает выгодно уравнение (3.1) заменить равносильным ему уравнением (уравнения равносильны, если имеют одинаковые корни):

f_1(x)-f_2(x)=0,

(3.2)

где функции f_1(x),,f_2(x) — более простые, чем функция f(x) . Тогда при задании уравнения в виде (3.1) нулями функции f(x) являются точки пересечения f(x) с осью (рис. 3.1,д), а при задании в виде (3.2) — абсциссы точек пересечения функций f_1(x) и f_2(x) (рис. 3.1,б).

Точки пересечения функции с осью абсцисс

Замечания

1. Если $f(x)=a_nx^n+a_{n-1}x^{n-1}+ldots+a_0=P_n(x)$ — алгебраический многочлен, то уравнение (3.1) называется также алгебраическим n-й степени:

$P_n(x)equiv a_nx^n+a_{n-1}x^{n-1}+ldots+a_0=0,$

(3.3)

где a_n,ldots,a_0 — действительные числа, коэффициенты уравнения.

График сеточной функции

2. На практике встречаются задачи нахождения корней уравнения f(x_i)=0 , левая часть которого задана сеточной функцией y_i=f(x_i),~i=1,2,ldots,N (рис. 3.2).

Число $x_{ast}$ есть корень уравнения (3.1) кратности , если при $x=x_{ast}$ вместе с функцией f(x) обращаются в нуль ее производные до (k-1)-го порядка включительно, т.е. $f(x_{ast})= f'(x_{ast})= ldots= f^{(k-1)}(x_{ast})=0$ , а $f^{(k)}(x_{ast})ne0$ . Корень кратности к = 1 называется простым. На рис 3.1,с простыми корнями являются $x_{ast1},x_{ast2},x_{ast3}$ , a корни $x_{ast4},x_{ast5}$ — кратные.

В соответствии с классическим результатом Галуа алгебраическое уравнение (3.1) при ngeqslant5 не имеет решения в замкнутом (формульном) виде. Сеточные уравнения вообще не имеют формульных решений. Поэтому корни алгебраических (n>2) , трансцендентных и сеточных уравнений, как правило, определяются приближенно с заданной точностью.

Решение осуществляется в два этапа:

Первый этап. Находятся отрезки [a_i,b_i] , внутри каждого из которых содержится один простой или кратный корень $(x_{ast i}in[a_i,b_i])$ (см. рис. 3.1). Этот этап называется процедурой отделения корней. По сути на нем осуществляется грубое нахождение корней $x_{ast i}$ .

Второй этап. Грубое значение каждого корня $x_{ast i}$ уточняется до заданной точности одним из численных методов, в которых реализуются последовательные приближения. Порядок (скорость) сходимости метода определяется так же, как в методе простых итераций.

Отделение корней уравнения

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

Теорема 3.1 (о числе корней алгебраического уравнения (3.3)). Алгебраическое уравнение (3.3) n-й степени имеет ровно корней, действительных или комплексных, при условии, что каждый корень считается столько раз, какова его кратность.

Теорема 3.2 (о свойстве парной сопряженности комплексных корней уравнения (3.3)). Если $x_{ast i}=alpha+beta i$ — корень алгебраического уравнения (3.3) кратности , то число $overline{x_{ast i}}=alpha-beta i$ также является корнем той же кратности.

Следствие. Алгебраическое уравнение нечетной степени имеет по крайней мере один действительный корень.

Теорема 3.3 (об оценке модулей корней уравнения (3.3)). Пусть

$A=max bigl{|a_{n-1}|,ldots,|a_0|bigr},qquad B=max bigl{|a_n|,|a_{n-1}|,ldots, |a_1|bigr},$

где $a_k,~k=overline{0,n}$ — коэффициенты уравнения $a_nx^n+a_{n-1}x^{n-1}+ ldots+ a_{1}x+a_0=0$ . Тогда модули всех корней $x_{ast i}~(i=1,2,ldots,n)$ уравнения удовлетворяют неравенству

$frac{1}{1+dfrac{B}{|a_0|}}<|x_{ast i}| leqslant 1+frac{A}{|a_n|},quad i=1,2,ldots,n,$

(3.4)

т.е. корни уравнения расположены в кольце.

Следствие. Числа $r=frac{1}{1+dfrac{B}{|a_0|}}$ и $R=1+ frac{A}{|a_n|}$ являются соответственно нижней и верхней границами положительных корней алгебраического уравнения: $r<x_{ast i}^{+}<R$ . Аналогично числа и служат нижней и верхней границами отрицательных корней уравнения: $-R<x_{ast i}^{-}<-r$ .

Приведем полезные теоремы, используемые для более точного установления границ действительных корней алгебраических уравнений.

Теорема 3.4 (теорема Лагранжа о верхней границе положительных корней уравнения (3.3)). Пусть a_n>0 и a_i — первый отрицательный коэффициент в последовательности $a_n,a_{n-1},a_{n-2},ldots,a_1,a_0;~C$ — наибольшая из абсолютных величин отрицательных коэффициентов. Тогда за верхнюю границу положительных корней уравнения (3.3) может быть принято число

$R=1+sqrt[LARGE{n-i}]{frac{C}{a_n}},.$

(3.5)

Теорема 3.5 (о нижних и верхних границах положительных и отрицательных корней алгебраического уравнения). Пусть — верхняя граница положительных корней уравнения P_n(x)=0 ,

R_1 — верхняя граница положительных корней уравнения $P^1(x)= x^nP_n! left(frac{1}{x}right)=0$ ,
R_2 — верхняя граница положительных корней уравнения P^2(x)= P_n(-x)=0 ,
R_3 — верхняя граница положительных корней уравнения $P^3(x)= x^nP_n! left(-frac{1}{x}right)=0$ .

Тогда положительные корни $x_{ast i}^{+}$ и отрицательные корни $x_{ast i}^{-}$ уравнения (3.3) удовлетворяют неравенствам

$frac{1}{R_1}leqslant x_{ast i}^{+}leqslant R,qquad-R_2 leqslant x_{ast i}^{-}leqslant-frac{1}{R_3},.$

(3.6)

Теорема 3.6 (теорема Декарта о количестве действительных корней алгебраических уравнений). Число S_1 положительных корней (с учетом их кратностей) алгебраического уравнения P_n(x)=0 равно числу перемен знаков в последовательности коэффициентов $a_n,a_{n-1},ldots,a_0$ (коэффициенты, равные нулю, не учитываются) многочлена P_n(x) или меньше этого числа на четное число. Число S_2 отрицательных корней (с учетом их кратностей) алгебраического уравнения P_n(x)=0 равно числу перемен знаков в последовательности $a_n,a_{n-1},ldots,a_0$ многочлена P_n(-x) или меньше этого числа на четное число.

Теорема 3.7 (теорема Гюа о необходимом условии действительности всех корней алгебраического уравнения). Если алгебраическое уравнение (3.3) имеет все действительные корни, то квадрат каждого некрайнего коэффициента больше произведения двух его соседних коэффициентов.

Следствие. Если при каком-нибудь выполнено неравенство $a_k^2 leqslant a_{k-1}a_{k+1}$ , то уравнение (3.3) имеет по крайней мере одну пару комплексных корней.

Для отделения корней применяется следующая теорема.

Теорема 3.8. Если функция f(x) , определяющая уравнение f(x)=0 , на концах отрезка [a_i,b_i] принимает значения разных знаков, т.е. f(a_i)cdot f(b_i)<0 , то на этом отрезке содержится по крайней мере один корень уравнения. Если же f(x) непрерывна и дифференцируема и ее первая производная сохраняет знак внутри отрезка [a_i,b_i] $Bigl(mathop{operatorname{sign}}limits_{xin[a_i,b_i]} f'(x)=text{const}Bigr)$ , то на находится только один корень уравнения.

Способы отделения корней

В вычислительной практике обычно используются следующие способы отделения корней:

1) средствами машинной графики: функция f(x) представляется на дисплее и приближенно определяются отрезки, которым принадлежат точки $x_{ast i}$ ;

2) средствами математического анализа с помощью исследования функций и построения графиков (см. рис. 3.1,д);

3) формированием простых функций f_1(x) и f_2(x) таких, что получается равносильное уравнение в виде (3.2), и дальнейшим построением графиков этих функций (см. рис. 3.1,б).

▼ Примеры 3.1-3.3

Пример 3.1. Определить число положительных и отрицательных корней, а также их границы для уравнения

P_5(x)= x^5+2x^4-5x^3+8x^2-7x-3=0.

Решение

В данной задаче n=5,~ a_5=1,~ a_4=2,~ a_3=-5,~ a_2=8,~ a_1=-7,~ a_0=-3 . Согласно теореме 3.1 уравнение имеет пять корней. Поскольку n=5 , то по следствию из теоремы 3.2 уравнение имеет по крайней мере один действительный корень.

Оценим модули корней по теореме 3.3. Так как

A=max bigl{|2|,|-5|,|8|,|-7|,|-3|bigr}=8,qquad B=max bigl{|1|,|2|,|-5|, |8|,|-7|bigr}=8,

то $frac{1}{1+frac{8}{|-3|}}<|x_{ast i}|<1+frac{8}{|1|}$ или $frac{3}{11}<|x_{ast i}|<9$ , т.е. все корни лежат внутри данного кольца. По следствию из теоремы 3.3 это означает, что положительные корни удовлетворяют неравенству $frac{3}{11}<x_{ast i}^{+}<9$ , а отрицательные — неравенству $-9<x_{ast i}^{-}<-frac{3}{11}$ .

Применим теоремы 3.4 и 3.5 для уточнения приведенных результатов. Найдем верхнюю границу положительных корней. Так как a_3=-5 — первый отрицательный коэффициент в последовательности 1,2,-5,8,-7,-3 , то i=3 , а C=max bigl{|-5|,|-7|,|-3|bigr}=7 — наибольшая из абсолютных величин отрицательных коэффициентов. Следовательно, $R=1+sqrt[LARGE{(5-3)}]{frac{7}{1}}= 1+sqrt{7}cong3,!646$ .

Найдем нижнюю границу положительных корней. Составим уравнение:

$begin{aligned}P^{1}(x)&= x^nP_n! left(frac{1}{x}right)= x^5P_5!left(frac{1}{x} right)= x^5! left(frac{1}{x^5}+ frac{2}{x^4}-frac{5}{x^3}+frac{8}{x^2}-frac{7}{x}-3right)=\ &=-3x^5-7x^4+8x^3-5x^2+2x+1=0.end{aligned}$

или 3x^5+7x^4-8x^3+5x^2-2x-1=0 (старший коэффициент должен быть положительным). Для этого уравнения i=3,~ C=max bigl{|-8|,|-2|,|-1|bigr}=8 , поэтому $R_1=1+sqrt[LARGE{(5-3)}]{frac{8}{3}}=1+sqrt{frac{8}{3}}cong2,!632$ . Отсюда $frac{1}{R_1}=0,!38 leqslant x_{ast i}^{+}leqslant R=3,!646$ .

Уточним границы отрицательных корней. Составим уравнение:

P^2(x)=P_5(-x)= или x^5-2x^4-5x^3-8x^2-7x+3=0 .

Для этого уравнения i=4,~ C=maxbigl{|-2|,|-5|,|-8|,|-7|bigr}=8 , поэтому $R_2=1+ sqrt[LARGE{5-4}]{frac{8}{1}}=9$ . Составим уравнение

$begin{aligned}P^3(x)&= x^nP_n! left(-frac{1}{x}right)= x^5P_5! left(-frac{1}{x}right)= x^5! left(-frac{1}{x^5}+frac{2}{x^4}+frac{5}{x^3}+frac{8}{x^2}+frac{7}{x}-3right)=\ &=-3x^5+7x^4+8x^3+2x-1=0.end{aligned}$

или 3x^5-7x^4-8x^3-5x^2-2x+1=0 . Для этого уравнения i=4,~ C=max bigl{|-7|,|-8|,|-5|,|-2|bigr}=8 , поэтому $R_3=1+sqrt[LARGE{5-4}]{frac{8}{3}}=1+ frac{8}{3}cong3,!666$ . Отсюда находим: $-R_2=-9 leqslant x_{ast i}^{-}leqslant-frac{1}{R_3}=-0,!272$ . Заметим, что данный результат совпадает с полученным ранее.

Исследуем структуру корней уравнения. Так как квадрат каждого некрайнего коэффициента больше произведения двух его соседних коэффициентов, то по теореме 3.7 необходимое условие действительности всех корней уравнения выполняется.

На основе теоремы 3.6 определим число положительных и отрицательных корней. Выписываем коэффициенты многочлена P_n(x)=P_5(x)colon, 1,,2,-5,,8,-7,-3 . Так как число перемен знака S_1=3 , то число положительных корней равно трем или меньше на четное число, т.е. равно 1. Далее выписываем коэффициенты многочлена P_5(-x)colon, -1,,2,,5,,8,,7,-3 . Так как число перемен знаков S_2=2 , то число отрицательных корней равно двум или меньше на четное число, т.е. их вообще нет.

Пример 3.2. Отделить корни кубического уравнения x^3-x+1=0 .

Решение

Точка пересечения кубической параболы и прямой

Согласно теореме 3.1 уравнение имеет три корня, среди которых по крайней мере один действительный (следствие из теоремы 3.2, поскольку это уравнение нечетной степени).

Оценим модули корней уравнения по теореме 3.3. Так как

A=max bigl{|0|,|-1|,|1|bigr}=1,quad B=max bigl{|1|,|0|,|-1|bigr}=1 , то $frac{1}{1+dfrac{1}{|1|}}<|x_{ast i}|<1+frac{1}{|1|}$ или $frac{1}{2}<|x_{ast i}|<2$ .

Отсюда $frac{1}{2}<x_{ast i}^{+}<2$ и $-2<x_{ast i}^{+}<-frac{1}{2}$ .

Определим число положительных и отрицательных корней. Выписываем коэффициенты многочлена P_3(x)colon, 1,,0,-1,,1 . Так как число перемен знака S_1=2 (нулевой коэффициент не учитывается), то число положительных корней равно двум или меньше на четное число, т.е. они отсутствуют. Далее выписываем коэффициенты многочлена P_3(-x)=-x^3+x+1colon, -1,,0,,1,,1 . Так как число перемен знака S_2=1 (нулевой коэффициент не учитывается), то число отрицательных корней равно единице.

Отделим корни третьим способом. Для этого преобразуем уравнение к равносильному виду (3.2): x^3=x-1 и найдем точки пересечения фафиков y=x^3 и y=x-1 (рис. 3.3).

Очевидно, корень уравнения $x_{ast}in[-2;-1]$ .

Пример 3.3. Отделить корни уравнения третьего порядка x^3-x^2-9x+9=0 .

Решение

Процедура уточнения положения корня функции

Метод половинного деления

Пусть дано уравнение f(x)=0 и отделен простой корень $x_{ast}$ , т.е. найден такой отрезок [a_0,b_0] , что $x_{ast}in[a_0,b_0]$ и на концах отрезка функция имеет значения, противоположные по знаку (f(a_0)cdot f(b_0)<0) . Отрезок называется начальным интервалом неопределенности, потому что известно, что корень ему принадлежит, но его местоположение с требуемой точностью не определено.

Процедура уточнения положения корня заключается в построении последовательности вложенных друг в друга отрезков, каждый из которых содержит корень уравнения. Для этого находится середина текущего интервала неопределенности $c_k=frac{a_k+b_k}{2},~ k=0,1,2,ldots$ , и в качестве следующего интервала неопределенности из двух возможных выбирается тот, на концах которого функция f(x) имеет разные знаки (рис. 3.5).

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

Алгоритм метода половинного деления

1. Найти начальный интервал неопределенности L_0=[a_0,b_0] одним из методов отделения корней, задать малое положительное число varepsilon . Положить k=0 .

2. Найти середину текущего интервала неопределенности: $c_k=frac{a_k+b_k}{2}$ .

3. Если f(a_k)cdot f(c_k)<0 , то положить $a_{k+1}=a_k,~ b_{k+1}= c_k$ , а если f(c_k)cdot f(b_k)<0 , то принять $a_{k+1}=c_k,~ b_{k+1}= b_k$ . В результате находится текущий интервал неопределенности $L_{k+1}= [a_{k+1},b_{k+1}]$ .

4. Если $b_{k+1}-a_{k+1}leqslant varepsilon$ , то процесс завершить: $x_{ast}in L_{k+1}= [a_{k+1},b_{k+1}]$ . Приближенное значение корня можно найти по формуле $x_{ast}cong frac{a_{k+1}+b_{k+1}}{2}$ .

Если $b_{k+1}-a_{k+1}>varepsilon$ , положить k=k+1 и перейти к п.2.

Замечания

1. Метод имеет линейную, но безусловную сходимость, и его погрешность за каждую итерацию уменьшается в два раза:

$|b_1-a_1|=frac{|b_0-a_0|}{2};quad |b_2-a_2|= frac{|b_1-a_1|}{2}= frac{|b_0-a_0|}{2^2},quad ldots,quad |b_k-a_k|= |b_0-a_0|cdot2^{-k}.$

Из последнего соотношения можно оценить число итераций для достижения заданной точности varepsiloncolon

$|b_0-a_0|cdot2^{-k} leqslant varepsilon;qquad k geqslant log_{2}frac{|b_0-a_0|}{varepsilon},.$

Отсюда видно, что, например, для достижения точности $varepsilonapprox10^{-3}$ при (b_0-a_0)cong1 необходимо выполнить примерно десять итераций.

2. К достоинствам метода следует отнести то, что он позволяет найти простой корень уравнения $x_{ast}in[a_0,b_0]$ любых непрерывных функций f(x) при любых значениях a_0,,b_0 таких, что f(a_0)cdot f(b_0)<0 . Недостатки метода — он не обобщается на системы нелинейных уравнений и не может использоваться для нахождения корней четной кратности.

▼ Примеры 3.4-3.6

Пример 3.4. Найти корень уравнения x^3-x+1=0 методом половинного деления с точностью varepsilon_1=0,!01 и varepsilon_2=0,!0005 .

Решение

Пример 3.5. Найти корень уравнения x^3-x^2-9x+9=0 методом половинного деления с точностью varepsilon=0,!001 .

Решение

В примере 3.3 были отделены корни уравнения. Уточним корень, лежащий на отрезке [2,!5;4] . Результаты расчетов поместим в табл. 3.2.

$begin{aligned} mathit{Table~3.2}~&\ begin{array}{|c|c|c|c|c|c|c|c|} hline begin{matrix}{}\[-2pt]{}end{matrix} k& f(a_k)& a_k& b_k& f(b_k)& c_k=dfrac{a_k+b_k}{2}& f(c_k)& b_k-a_k\hline 0& -4,!125& 2,!5& 4& 21& 3,!25& 3,!5156& 1,!5\hline 1& -4,!125& 2,!5& 3,!25& 3,!5156& 2,!875& -1,!3769& 0,!75\hline 2& -1,!3769& 2,!875& 3,!25& 3,!5156& 3,!0625& 0,!78149& 0,!375\hline 3& -1,!3769& 2,!875& 3,!0625& 0,!7815& 2,!96875& -0,!3672& 0,!1875\hline 4& -0,!3672& 2,!9687& 3,!0625& 0,!7815& 3,!01562& 0,!18945& 0,!09375\hline 5& -0,!3672& 2,!9687& 3,!0156& 0,!1894& 2,!99218& -0,!0933& 0,!04687\hline 6& -0,!0933& 2,!9921& 3,!0156& 0,!1894& 3,!0039& 0,!0469& 0,!02344\hline 7& -0,!0933& 2,!9921& 3,!0039& 0,!0469& 2,!99804& -0,!02349& 0,!01172\hline 8& -0,!02349& 2,!99804& 3,!0039& 0,!0469& 3,!00097& 0,!011647& 0,!00586\hline end{array}& end{aligned}$

В результате найден интервал [2,!99804;3,!0039] и приближенное значение корня $x_{ast}cong3,!00097$ .

Пример 3.6. Отделить корни трансцендентного уравнения $x^2-e^{-x}=0$ и найти один из корней с точностью varepsilon=0,!01 .

Решение

1. Можно отделить корни уравнения, преобразовав его к равносильному виду $x^2=e^{-x}$ и определив абсциссу точек пересечения графиков функций y=f_1(x)=x^2 и $y=f_2(x)=e^{-x}colon, x_{ast}in[0,!5;1]$ . При этом f(0,!5)cdot f(1)<0 .

2. Уточним корень. Результаты расчетов приведем в табл. 3.3.

$begin{aligned} mathit{Table~3.3}~&\ begin{array}{|c|c|c|c|c|c|c|c|} hline begin{matrix}{}\[-2pt]{}end{matrix} k& f(a_k)& a_k& b_k& f(b_k)& c_k=dfrac{a_k+b_k}{2}& f(c_k)& b_k-a_k\hline 0& -0,!3565& 0,!5& 1& 0,!6321& 0,!75& 0,!09013& 0,!5\hline 1& -0,!3565& 0,!5& 0,!75& 0,!09013& 0,!625& -0,!1446& 0,!251\hline 2& -0,!1446& 0,!625& 0,!75& 0,!09013& 0,!6875& -0,!0301& 0,!125\hline 3& -0,!0301& 0,!6875& 0,!75& 0,!09013& 0,!7187& 0,!0292& 0,!0625\hline 4& -0,!0301& 0,!6875& 0,!7187& 0,!0292& 0,!7031& -0,!00069& 0,!0312\hline 5& -0,!00069& 0,!7031& 0,!7187& 0,!0292& 0,!7109& 0,!0142& 0,!0156\hline 6& -0,!00069& 0,!7031& 0,!7109& 0,!0142& 0,!707& 0,!0067& 0,!0078\hline end{array}& end{aligned}$

Вычисления показывают, что b_6-a_6=0,!7109-0,!7031=0,!0078< varepsilon= 0,!01 .

Поэтому $x_{ast}cong frac{0,!7109+0,!7031}{2}= c_6=0,!707$ .

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

Метод хорд

Этот метод при тех же предположениях обеспечивает более быстрое нахождение корня, чем метод половинного деления. Для этого отрезок [a,b] делится не пополам, а в отношении |f(a)|,colon|f(b)| .

Геометрически метод хорд эквивалентен замене кривой y=f(x) хордой, проходящей через точки (a,f(a)) и (b,f(b)) (рис. 3.6).

Уравнение хорды имеет вид $frac{x-a}{b-a}= frac{y-f(a)}{f(b)-f(a)}$ . Полагая $x=x^{(1)}$ и y=0 , получаем

$x^{(1)}= a-frac{f(a)}{f(b)-f(a)}cdot(b-a).$

Предположим, что вторая производная f''(x) сохраняет постоянный знак, и рассмотрим два случая: f(a)>0,~ f''(a)>0 (рис. 3.7,д) и f(a)<0,~ f''(x)>0 (рис. 3.7,б). Случай f''(x)<0 сводится к рассматриваемому, если уравнение записать в форме: -f(x)=0 . Первому случаю (см. рис. 3.7,д) соответствует формула (3.7), а второму случаю (3.8) (см. рис. 3.7,б):

$begin{aligned}&x^{(0)}=b,\ &x^{(k+1)}=x^{(k)}-frac{f(x^{(k)})}{f(x^{(k)})-f(a)} bigl(x^{(k)}-abigr),quad k=0,1,2,ldotsend{aligned}$

(3.7)

$begin{aligned}&x^{(0)}=a,\ &x^{(k+1)}=x^{(k)}-frac{f(x^{(k)})}{f(b)-f(x^{(k)})}bigl(b-x^{(k)}bigr),quad k=0,1,2,ldots end{aligned}$

(3.8)

В первом случае остается неподвижным конец , а во втором случае конец .

Метод хорд

Замечание. Для выявления неподвижного конца используется условие f''(x)cdot f(t)>0 , где t=a или t=b . Если неподвижен конец , применяется формула (3.7), а если конец , — формула (3.8).

Пример 3.7. Найти корень уравнения x^3-x+1=0 методом хорд с точностью varepsilon=0,!001 .

Решение

Рассмотрим задачу нахождения корня на отрезке [-2;-1] (см. пример 3.2). Так как f(a)=f(-2)=-5, f(b)=f(-1)=-1 , a f''(x)=3x^2-1>0 на отрезке [-2;-1] , то f''(x)cdot f(b)>0 и, следовательно, имеем второй случай (см. рис. 3.7,б).

Положим $x^{(0)}=a=-2,~k=0$ . Тогда по формуле (3.8) получаем

$x^{(1)}= x^{(0)}-frac{f(x^{(0)})}{f(b)-f(x^{(0)})}bigl(b-x^{(0)}bigr)=-2-frac{-5}{1-(-5)}cdot(-1-(-2))=-1,!1666.$

Так как $Delta_1=|x^{(1)}-x^{(0)}|=0,!8334>varepsilon$ , то положим k=1 и продолжим процесс:

$x^{(2)}= x^{(1)}-frac{f(x^{(1)})}{f(b)-f(x^{(1)})}bigl(b-x^{(1)}bigr)=-1,!1666-frac{-0,!5786}{1-0,!5786}cdot bigl(-1-(-1,!1666)bigr)=-1,!3953.$

Так как $Delta_2=|x^{(2)}-x^{(1)}|=0,!2287>varepsilon$ , то положим k=2 и продолжим процесс:

$x^{(3)}= x^{(2)}-frac{f(x^{(2)})}{f(b)-f(x^{(2)})}bigl(b-x^{(2)}bigr)=-1,!3953-frac{-0,!3214}{1+0,!3214}cdot bigl(-1-(-1,!3953)bigr)=-1,!2991.$

Поскольку $Delta_3=|x^{(3)}-x^{(2)}|=0,!0962>varepsilon$ , положим k=3colon

$x^{(4)}= x^{(3)}-frac{f(x^{(3)})}{f(b)-f(x^{(3)})}bigl(b-x^{(3)}bigr)=-1,!2991-frac{-0,!1064}{1+0,!1064}cdot bigl(-1-(-1,!2991)bigr)=-1,!3347.$

Так как $Delta_4=|x^{(4)}-x^{(3)}|=0,!0356>varepsilon$ , положим k=4colon

$x^{(5)}= x^{(4)}-frac{f(x^{(4)})}{f(b)-f(x^{(4)})}bigl(b-x^{(4)}bigr)=-1,!3347-frac{-0,!043}{1+0,!043}cdot bigl(-1-(-1,!3347)bigr)=-1,!3209.$

Поскольку $Delta_5=|x^{(5)}-x^{(4)}|=0,!0138>varepsilon$ , положим k=5colon

$x^{(6)}= x^{(5)}-frac{f(x^{(5)})}{f(b)-f(x^{(5)})}bigl(b-x^{(5)}bigr)=-1,!3209-frac{-0,!0162}{1+0,!0162}cdot bigl(-1-(-1,!3209)bigr)=-1,!3261.$

Так как $Delta_6=|x^{(6)}-x^{(5)}|=0,!0052>varepsilon$ , положим k=6colon

$x^{(7)}= x^{(6)}-frac{f(x^{(6)})}{f(b)-f(x^{(6)})}bigl(b-x^{(6)}bigr)=-1,!3261-frac{-0,!0059}{1+0,!0059}cdot bigl(-1-(-1,!3261)bigr)=-1,!3241.$

Поскольку $Delta_7=|x^{(7)}-x^{(6)}|=0,!0020>varepsilon$ , положим k=7colon

$x^{(8)}= x^{(7)}-frac{f(x^{(7)})}{f(b)-f(x^{(7)})}bigl(b-x^{(7)}bigr)=-1,!3241-frac{-0,!00217}{1+0,!00217}cdot bigl(-1-(-1,!3241)bigr)=-1,!3248.$

Так как $Delta_8=|x^{(8)}-x^{(7)}|=0,!0007<varepsilon=0,!001$ , то корень уравнения $x_{ast}cong-1,!3248$ . Из анализа поведения Delta_k следует, что сходимость метода хорд линейная, однако более быстрая, чем сходимость метода половинного деления.

Абсцисса точки пересечения прямой и кривой

Метод простых итераций

Пусть известно, что корень $x_{ast}$ уравнения f(x)=0 лежит на отрезке G={aleqslant xleqslant b} .

Методика решения задачи

1. Уравнение f(x)=0 равносильным преобразованием привести к виду x=varphi(x) . Это преобразование может быть осуществлено различными путями, но для сходимости нужно обеспечить выполнение условия |varphi'(x)|leqslantchi<1 ( chi — некоторая константа). При этом задача сводится к нахождению абсциссы точки пересечения прямой y=x и кривой y=varphi(x) (рис. 3.8).

2. Задать начальное приближение $x^{(0)}in[a,b]$ и малое положительное число varepsilon . Положить k=0 .

3. Вычислить следующее приближение:

$x^{(k+1)}= varphi(x^{(k)}).$

(3.9)

4. Если $|x^{(k+1)}-x^{(k)}|leqslantvarepsilon$ , итерации завершаются и $x_{ast}cong x^{(k+1)}$ . Если $|x^{(k+1)}-x^{(k)}|>varepsilon$ , положить k=k+1 и перейти к п.3.

Замечание. В качестве условия завершения итераций при известном значении chi может быть использовано неравенство

$bigl|x^{(k+1)}-x^{(k)}bigr|leqslant frac{1-chi}{chi}cdot varepsilon.$

Проблемы сходимости и единственности численного решения, являющиеся главными при использовании этого метода, решаются и исследуются с помощью понятия о сжимающем отображении и теоремы о достаточном условии сходимости метода.

Отображение (функция) varphi(x) называется сжимающим в области с коэффициентом chi~(0leqslantchi<1) , если для любых двух x',,x'' из выполнено неравенство

bigl|varphi(x'')-varphi(x')bigr|leqslantchicdotbigl|x''-x'bigr|.

(3.10)

Теорема 3.9 (о сходимости метода простых итераций и единственности получаемого численного решения)

Пусть выполнены условия:

1. Нелинейное уравнение x=varphi(x) имеет решение $x_{ast}in G$ .

2. Отображение varphi(x) является сжимающим в области с некоторым коэффициентом chi~(0leqslantchi<1) .

Тогда:

а) решение $x_{ast}$ является единственным решением в области ;

б) последовательность $x^{(0)},x^{(1)},ldots,x^{(k+1)},ldots$ , определяемая по отображению на основе итерационного процесса, сходится к решению $x_{ast}$ со скоростью геометрической прогрессии, т.е. при выборе $x^{(0)}$ из условия $|x_{ast}-x^{(0)}|<R$ , где R>0 — некоторое малое число, справедливо неравенство

$bigl|x_{ast}-x^{(k)}bigr| leqslant chi^kcdot bigl|x_{ast}-x^{(0)}bigr|,quad k=0,1,2,ldots$

Теорема 3.9 утверждает, что при выполнении условий 1,2 существует окрестность $G(x_{ast},R)$ такая, что если взять $x^{(0)}$ в этой окрестности и вычислять $x^{(1)},x^{(2)},ldots$ по формуле (3.9), то в результате с любой наперед заданной точностью можно вычислить $x^{(k+1)}approx x_{ast}$ , соответствующее искомому (единственному) корню. Но так как эта окрестность неизвестна, то можно взять произвольное $x^{(0)}in G$ . Если при этом вычисляется последовательность $x^{(0)},x^{(1)},x^{(2)},ldots,x{(k)},ldots$ , сходящаяся к некоторому значению widehat{x} , то в силу теоремы $widehat{x}=x_{ast}$ . Если сходимость отсутствует, то надо взять другое $x^{(0)}in G$ и повторить расчет.

Теорема 3.10 (о достаточном условии сходимости метода простых итераций). Пусть выполнены условия:

1. Функция varphi(x) имеет производные для всех xin G .

2. Существует число chi,(0 leqslantchi<1,~chi=text{const}) , такое, что |varphi'(x)|leqslantchi для всех xin G .

Тогда отображение varphi(x) является сжимающим в с коэффициентом сжатия х и последовательность $x^{(0)},x^{(1)},ldots,x^{(k+1)},ldots$ , определяемая на основе итерационного процесса, сходится к решению $x_{ast}$ , то есть $x^{(k)}to x_{ast}$ при ktoinfty .

▼ Доказательство

В силу условия 1 справедлива теорема Лагранжа о конечных приращениях:

varphi(x'')-varphi(x')leqslant (x''-x')varphi'(delta) для forall x',x''in G ,

где delta — точка, лежащая между и x'' . Но тогда с учетом условия 2 и замены varphi'(delta) ее мажорантой chi получим

bigl|varphi(x'')-varphi(x')bigr|leqslant chicdot bigl|x''-x'bigr|,

т.е. отображение varphi(x) — сжимающее, и, таким образом, последовательность $x^{(0)},x^{(1)},ldots,x^{(k+1)},ldots$ сходится к некоторому widehat{x} . Но тогда в силу непрерывности в имеет место равенство $widehat{x}=x_{ast}$ .

Геометрическая интерпретация процесса сходимости и расходимости в зависимости от выполнения или невыполнения достаточного условия сходимости представлена на рис. 3.9.

Сходимость итерационных последовательностей

Из рис. 3.9 видно, что при 0<varphi'(x)<1 и при -1<varphi'(x)<0 (см.рис. 3.9,д,б) итерационные последовательности $x^{(0)},x^{(1)},x^{(2)},ldots$ сходятся к $x_{ast}$ . Причем в первом случае реализуется односторонняя (монотонная) сходимость, а во втором — двусторонняя (немонотонная). При |varphi'(x)|>1 (см.рис. 3.9,в,г) процесс расходится несмотря на то, что точка $x^{(0)}$ очень близка к $x_{ast}$ . Процессы на рис. 3.9,а,б соответствуют сжимающему отображению.

Преобразование уравнения f(x)=0 к равносильному виду x=varphi(x) может быть выполнено неоднозначно. Рассмотрим универсальные практические приемы равносильного преобразования f(x)=0 , дающие сжимающие отображения.

1. Можно заменить уравнение f(x)=0 на равносильное x=x+cf(x) , где c=text{const}ne0 . Тогда, принимая правую часть этого уравнения за varphi(x) и раскрывая |varphi'(x)|= |1+cf'(x)|<1 , получаем условие

-2<ccdot f'(x)<0.

(3.11)

Таким образом, можно найти константу на отрезке G=[a,b] так, чтобы удовлетворялись неравенства (3.11). При этом надо стремиться получить такую постоянную , которая бы больше отличалась от нуля, и тогда будет реализовы-ваться более быстрая сходимость.

Можно показать, что абсолютная погрешность метода оценивается по формуле (эта оценка выражается через два последовательных приближения)

$bigl|x^{(k+1)}-x_{ast}bigr|leqslant frac{chi}{1-chi}cdot bigl|x^{(k+1)}-x^{(k)}bigr|$

(3.12)

или по формуле (эта оценка выражается через два приближения $x^{(0)}$ и $x^{(1)}$ )

$bigl|x^{(k+1)}-x_{ast}bigr|leqslant frac{chi^{k+1}}{1-chi}cdot bigl|x^{(1)}-x^{(0)}bigr|.$

(3.13)

Из оценки следует условие выхода из итерационного процесса. Если значение chi неизвестно, то выход осуществляется по условию

$bigl|x^{(k+1)}-x^{(k)}bigr|leqslant varepsilon.$

2. Уравнение f(x)=0 заменяется равносильным (где знак в правой части выбирается из условия |varphi'(x)|<1 ):

$x=xmp frac{f(x)}{max|f'(x)|}equiv varphi(x)$ при xin G ,

3. Можно выразить из уравнения f(x)=0 так, чтобы для полученного уравнения x=varphi(x) выполнялось условие сходимости |varphi'(x)|<1 в окрестности искомого корня.

Замечание к доказательству. Выполнение условия $Delta_{k+1}= bigl|x^{(k+1)}-x^{(k)}bigr|leqslant varepsilon$ не гарантирует близости к точному решению (на рис. 3.10 достигается область, где условие окончания выполняется, но корень $x_{ast}$ расположен достаточно далеко от этой области).

Итерационный процесс и корень

▼ Примеры 3.8-3.10

Пример 3.8. Методом простых итераций с точностью varepsilon=0,!001 уточнить корень трансцендентного уравнения $x^2-e^{-x}=0$ , причем искомый корень $x_{ast}in[0,!5;1,!0]equiv G$ .

Решение

Пример 3.9. Найти решение уравнения x^3-x+1=0 методом простых итераций с точностью varepsilon_1=0,!01 и varepsilon_2=0,!001 .

Решение

Пример 3.10. Найти корни уравнения x^3-x^2-9x+9=0 методом простых итераций с точностью varepsilon=0,!001 .

Решение

1. Преобразуем уравнение к виду $x=varphi(x)colon, x=sqrt[LARGE{3}]{x^2+9x-9}$ .

В примере 3.3 была выполнена операция отделения корней и получены отрезки [-4;-2],,[0,5;2],,[2;4] .

Можно показать, что на отрезках [2;4],,[-4;-2] функция $varphi(x)= sqrt[LARGE{3}]{x^2+9x-9}$ удовлетворяет условию |varphi'(x)|<1 .

На отрезке [0,!5;2] используем другой вид уравнения: $x=frac{x^3}{9}-frac{x^2}{9}+1$ . Также легко проверить, что функция $varphi(x)=frac{x^3}{9}-frac{x^2}{9}+1$ удовлетворяет достаточному условию сходимости на отрезке [0,!5;2] .

2. В качестве начальных приближений выберем:
– точку $x^{(0)}=-2$ на отрезке [-4;-2] ;
– точку $x^{(0)}=0,!5$ на отрезке [0,!5;-2] ;
– точку $x^{(0)}=2$ на отрезке [2;4] ;.
В поставленной задаче varepsilon=0,!001 .

3,4. Выполним расчеты по формуле

$x^{(k+1)}= sqrt[LARGE{3}]{(x^{(k)})^2+9x^{(k)}-9},quad k=0,1,2,ldots$

с начальными значениями $x^{(0)}=-2$ и $x^{(0)}=2$ и по формуле

$x^{(k+1)}=frac{(x^{(k)})^3}{9}-frac{(x^{(k)})^2}{9}+1,quad k=0,1,2,ldots$

с начальным значением $x^{(0)}=0,!5$ .

Результаты расчетов занесены в табл. 3.6–3.8.

$begin{aligned}& begin{aligned} mathit{Table~3.6}~&\ begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}hline k&! scriptstyle{0}!&! scriptstyle{1}!&! scriptstyle{2}!&! scriptstyle{3}!&! scriptstyle{4}!&! scriptstyle{5}!&! scriptstyle{6}!&! scriptstyle{7}!&! scriptstyle{8}!&! scriptstyle{9}!&! scriptstyle{10}!&! scriptstyle{11}!&! scriptstyle{12}!\hline x^{(k)}&! scriptstyle{2,0000}!&! scriptstyle{2,3513}!&! scriptstyle{2,6056}!&! scriptstyle{2,7694}!&! scriptstyle{2,8682}!&! scriptstyle{2,9255}!&! scriptstyle{2,9582}!&! scriptstyle{2,9767}!&! scriptstyle{2,9870}!&! scriptstyle{2,9927}!&! scriptstyle{2,9959}!&! scriptstyle{2,9977}!&! scriptstyle{2,9987}!\hline bigl|x^{(k)}-x^{(k-1)}bigr|&! -!&! scriptstyle{0,3513}!&! scriptstyle{0,2543}!&! scriptstyle{0,1638}!&! scriptstyle{0,0988}!&! scriptstyle{0,0573}!&! scriptstyle{0,0327}!&! scriptstyle{0,0185}!&! scriptstyle{0,0102}!&! scriptstyle{0,0057}!&! scriptstyle{0,0032}!&! scriptstyle{0,0018}!&! scriptstyle{0,0010}!\hline end{array}& end{aligned}<br />\[6pt] & begin{aligned} mathit{Table~3.7}~&\ begin{array}{|c|c|c|}hline k& x^{(k)}& bigl|x^{(k)}-x^{(k-1)}bigr|\hline 0&-2,!0000&-\hline 1&-2,!8438& 0,!8438\hline 2&-2,!9816& 0,!1378\hline 3&-2,!9979& 0,!0163\hline 4&-2,!9997& 0,!0018\hline 5&-2,!99997& 0,!00027\hline end{array}&end{aligned} qquadqquadqquad begin{aligned} mathit{Table~3.8}~&\ begin{array}{|c|c|c|} hline k& x^{(k)}& bigl|x^{(k)}-x^{(k-1)}bigr|\hline 0& 0,!50000&-\hline 1& 0,!98611& 0,!4861\hline 2& 0,!99849& 0,!01238\hline 3& 0,!99983& 0,!00134\hline 4& 0,!99998& 0,!00015\hline end{array}& end{aligned}end{aligned}$

В результате получены приближенные значения корней:

$x_{1ast}cong-2,!99997,qquad x_{2ast}cong0,!99998,qquad x_{3ast}cong2,!9987.$

Обратим внимание на сильное различие в числе итераций, потребовавшихся для нахождения корней $x_{ast}=3$ (табл. 3.6) и $x_{ast}=-3$ (табл. 3.7), с помощью одной и той же формулы. Заметим, что в окрестности корня $x_{ast}=3$ значения модуля производной функции $varphi(x)=sqrt[LARGE{3}]{x^2+9x-9}$ равны:

С другой стороны, в окрестности корня $x_{ast}=-3$ имеем:

Анализ результатов показывает, что чем меньше значения модуля производной |varphi'(x)| , тем быстрее сходимость.

Метод Ньютона для решения нелинейных уравнений

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

Геометрическая интерпретация метода Ньютона

1) существование второй производной функции f(x) на множестве G={aleqslant xleqslant b} ;
2) удовлетворение первой производной условию f(x)ne0 для всех xin G ;
3) знакопостоянство f'(x),,f''(x) для всех xin G .

Поэтому его желательно использовать совместно с другими методами, например методом половинного деления, чтобы достигнуть диапазона widetilde{a}leqslant x leqslant widetilde{b} , где указанные условия начинают выполняться.

Геометрическая интерпретация метода Ньютона состоит в следующем. Задается начальное приближение $x^{(0)}$ . Далее проводится касательная к кривой y=f(x) в точке $x^{(0)}$ (рис. 3.11), т.е. кривая заменяется прямой линией. В качестве следующего приближения выбирается точка пересечения этой касательной с осью абсцисс. Процесс построения касательных и нахождения точек пересечения с осью абсцисс повторяется до тех пор, пока приращение не станет меньше заданной величины varepsilon .

Получим расчетную формулу метода Ньютона. Вместо участка кривой (точка соответствует $x_{ast}$ ) возьмем участок — касательную, проведенную в точке $(x^{(0)},f(x^{(0)}))$ ). Для этого отрезка справедливо конечное соотношение:

$frac{f(x^{(0)})-0}{x^{(0)}-x^{(1)}}= f'(x^{(0)})equiv operatorname{tg}alpha,$

где alpha — угол наклона касательной в точке $(x^{(0)},f(x^{(0)}))$ к оси абсцисс. Разрешая это соотношение относительно $x^{(1)}$ , получаем $x^{(1)}= x^{(0)}-frac{f(x^{(0)})}{f'(x^{(0)})}$ . Повторяя процесс, находим общую формулу:

$x^{(k+1)}= x^{(0)}-frac{f(x^{(k)})}{f'(x^{(k)})},quad k=0,1,2,ldots$

(3.14)

Подчеркнем, что если отбросить итерационный индекс, то (3.14) записывается в виде нелинейного уравнения

$x=x-frac{f(x)}{f'(x)}equiv varphi(x),$

(3.15)

которое, однако, на [a,b] не равносильно исходному, а является таковым только в одной точке при $x=x_{ast}$ . Поэтому данный метод не служит разновидностью метода простых итераций.

Применим теперь для вывода формулы (3.14) метод линеаризации. Положим, что итерационный процесс имеет вид

$x^{(k+1)}=x^{(k)}+delta^{(k)},quad k=0,1,2,ldots$

(3.16)

где $delta^{(0)}$ — поправка к k-му приближению, которую необходимо найти. Предполагая, что f(x) имеет непрерывную вторую производную, разложим $f(x^{(k)}+delta^{(k)})$ по формуле Тейлора относительно точки $x^{(k)}colon$

$f(x^{(k)}+delta^{(k)})= f(x^{(k)})+ delta^{(k)}f'(x^{(k)})+ frac{1}{2}(delta^{(k)})^2 f''(xi),$

где $xiin bigl(x^{(k)},x^{(k+1)}bigr)$ . Учитывая, что $fbigl(x^{(k)}+ delta^{(k)}bigr)=0$ (это соответствует нахождению точки пересечения с осью абсцисс), и оставляя только линейную (относительно $delta^{(k)}$ ) часть разложения (отсюда и название — метод линеаризации), записываем линейное относительно $delta^{(k)}$ уравнение

$f(x^{(k)})+ delta^{(k)} f'(x^{(k)})=0.$

Отсюда выражается поправка $delta^{(k)}=-frac{f(x^{(k)})}{f'(x^{(k)})}$ . Подставляя $delta^{(k)}$ в (3.16), получаем (3.14).

Теорема 3.11 (о достаточных условиях сходимости метода Ньютона). Пусть выполняются следующие условия:

1. Функция f(x) определена и дважды дифференцируема на [a,b] .

2. Отрезку [a,b] принадлежит только один простой корень $x_{ast}$ , так что f(a)cdot f(b)<0 .

3. Производные f'(x),,f''(x) на [a,b] сохраняют знак, и f'(x)ne0 .

4. Начальное приближение $x^{(0)}$ удовлетворяет неравенству $f(x^{(0)})cdot f''(x^{(0)})>0$ (знаки функций f(x) и f''(x) в точке $x^{(0)}$ совпадают).

Тогда с помощью метода Ньютона (3.14) можно вычислить корень уравнения f(x)=0 с любой точностью.

Замечания

1. Метод Ньютона характеризуется вторым порядком сходимости вблизи корня и первым порядком — вдали от него. Данную оценку проверяем для двух случаев, когда $x^{(k)}$ находится далеко от корня $x_{ast}$ (это возможно на первых итерациях) и когда $x^{(k)}$ располагается вблизи $x_{ast}$ .

Первый случай. Пусть отрезок $omega=[x^{(k)},x_{ast}]$ не мал. Тогда на основе теоремы Лагранжа получим (где $m_1=minlimits_{omega}|f'(x)|$ )

$bigl|f(x^{(k)})bigr|= bigl|f(x_{ast})-f(x^{(k)})bigr|= bigl|f'(xi)bigr|cdot bigl|x_{ast}-x^{(k)}bigr| geqslant m_1 bigl|x_{ast}-x^{(k)}bigr|.$

(3.17)

Преобразуем с использованием (3.17) итерационную формулу (3.14) (где $M_1= maxlimits_{xin[a,b]}|f'(x)|$ ):

$x^{(k+1)}=x^{(k)}-frac{f(x^{(k)})}{f'(x^{(k)})};qquad bigl|x^{(k+1)}-x^{(k)}bigr|= frac{|f(x^{(k)})|}{f'(x^{(k)})} geqslant frac{m_1}{M_1} bigl|x_{ast}-x^{(k)}bigr|.$

В силу монотонности последовательности $x^{(0)},x^{(1)},ldots$ имеем

$begin{gathered}x_{ast}-x^{(k+1)}= x_{ast}-x^{(k)}-bigl(x^{(k+1)}-x^{(k)}bigr),\ bigl|x_{ast}-x^{(k+1)}bigr|= bigl|x_{ast}-x^{(k)}bigr|-bigl|x^{(k+1)}-x^{(k)}bigr| geqslant bigl|x_{ast}-x^{(k)}bigr|- frac{m_1}{M_1} bigl|x_{ast}-x^{(k)}bigr|= left(1-frac{m_1}{M_1}right)! bigl|x_{ast}-x^{(k)}bigr|. end{gathered}$

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

$bigl|x_{ast}-x^{(k+1)}bigr| leqslant ccdot bigl|x_{ast}-x^{(k)}bigr|$ , где $0 leqslant c=1-frac{m_1}{M_1}<1$ .

Второй случай. Пусть теперь отрезок $omega=[x^{(k)},x]$ мал, т.е. итерации выполняются вблизи корня. Тогда, полагая, что указанные выше предположения 1–4 теоремы 3.10 выполнены, разложим функцию f(x) в окрестности корня $x_{ast}$ относительно точки $x^{(k)}$ , учитывая члены до второго порядка. Получим

$Bigl.{f(x)}Bigr|_{x=x^{(k)}}= f(x^{(k)})+ bigl(x_{ast}-x^{(k)}bigr) f'(x^{(k)})+ bigl(x_{ast}-x^{(k)}bigr)^2 frac{1}{2}f''(xi)=0,$

где $xiin bigl(x^{(k)}-delta,,x^{(k)}+deltabigr)$ ( delta>0 — малая величина). Из данного соотношения выражаем $x_{ast}colon$

$x_{ast}=x^{(k)}-frac{f(x^{(k)})}{f'(x^{(k)})}-frac{(x_{ast}-x^{(k)})^2}{2f'(x^{(k)})},f''(xi).$

Но первые два слагаемых в правой части в соответствии с (3.14) равны $x^{(k+1)}$ . Тогда будем иметь

$x_{ast}-x^{(k)}=-frac{(x_{ast}-x^{(k)})^2}{2f'(x^{(k)})},f''(xi).$

Из последнего соотношения следует оценка погрешности (k+1)-го приближения через погрешность k-го приближения:

$bigl|x_{ast}-x^{(k+1)}bigr|leqslant frac{M_2}{2m_1} bigl|x_{ast}-x^{(k)}bigr|^2,$

(3.18)

где принято $M_2=maxlimits_{omega}|f''(x)|,~ m_1=minlimits_{omega}|f'(x)|$ . Оценка (3.18) свидетельствует о квадратичной сходимости метода касательных вблизи корня. С вычислительной точки зрения это означает, что на каждом приближении количество верных цифр результата удваивается.

2. Для нахождения комплексных корней уравнения f(z)=0 можно также использовать (3.14) в форме (где z=x+iy — комплексная переменная)

$z^{(k+1)}=z^{(k)}-frac{f(z^{(k)})}{f'(z^{(k)})},quad k=0,1,2,ldots$

Метод Ньютона может применяться не только для нахождения простых корней, но для определения кратных корней, т.е. когда на отрезке [a,b] содержащем корень, не выполняется условие f(a)cdot f(b)<0 (условие 2 теоремы 3.11). Наряду с теоремой 3.11 удобно также пользоваться следующей теоремой.

Достаточные условия сходимости метода Ньютона

Теорема 3.12 (достаточные условия сходимости метода Ньютона). Пусть:

а) дана функция f(x)colon Dto mathbb{R} , где — открытый интервал, и $f'(x)in operatorname{Lip}_{gamma}(D)$ ;

б) для некоторого rho>0 выполняется условие |f'(x)|leqslantrho при всех из .

Если уравнение f(x)=0 имеет решение $x_{ast}in D$ , то существует некоторое eta>0 , такое, что если $|x^{(0)}-x_{ast}|<eta$ , то последовательность $bigl{x^{(0)},x^{(1)},x^{(2)},ldotsbigr}$ , задаваемая формулой (3.14), существует и сходится к $x_{ast}$ . Более того, справедлива оценка

$bigl|x^{(k+1)}-x_{ast}bigr| leqslant frac{gamma}{2rho} bigl|x^{(k)}-x_{ast}bigr|^2,quad k=0,1,2,ldots$

Здесь обозначение $f'(x)in operatorname{Lip}_{gamma}(D)$ означает, что функция f'(x) непрерывна по Липшицу с константой gamma на множестве , то есть |f'(x)-f'(y)| leqslant gamma cdot|x-y| для любых x,,y из .

Замечания

1. Требование теоремы 3.12, чтобы производная f'(x) имела ненулевую нижнюю границу в , определяет, что значение $f'(x_{ast})$ должно быть ненулевым для квадратичной сходимости метода Ньютона. Если же $f'(x_{ast})=0$ , то $x_{ast}$ является кратным корнем, а метод Ньютона сходится лишь линейно.

2. Выполнение условий теоремы 3.12 гарантирует сходимость метода Ньютона только из “хорошего” начального приближения $x^{(0)}$ .

3. Метод Ньютона является локально сходящимся, так как он сходится с определенной скоростью к истинному решению при условии, что стартует в достаточной близости от этого решения.

Методика решения задачи

1. Задать начальное приближение $x^{(0)}$ так, чтобы выполнялось неравенство $f(x^{(0)})cdot f''(x^{(0)})>0$ , а также малое положительное число varepsilon . Положить k=0 .

2. Вычислить $x^{(k+1)}$ по формуле $x^{(k+1)}= x^{(k)}-frac{f(x^{(k)})}{f'(x^{(k)})}$ .

3. Если $|x^{(k+1)}-x^{(k)}|leqslant varepsilon$ , процесс завершить и положить $x_{ast}cong x^{(k+1)}$ .

Если $|x^{(k+1)}-x^{(k)}|>varepsilon$ , положить k=k+1 и перейти к п.2.

▼ Примеры 3.11-3.14

Пример 3.11. Методом Ньютона с точностью varepsilon=0,!001 уточнить корень трансцендентного уравнения $x^2-e^{-x}=0$ , причем искомый корень $x_{ast}in[0,!5;1,!0]equiv G$ .

Решение

Можно проверить, что на множестве удовлетворяются условия 1, 2, 3 теоремы 3.11, обеспечивающие сходимость метода касательных.

1. Зададим начальное приближение из условия 4. Так как для $f(x)=x^2-e^{-x}$ справедливо $f''(x)=2-e^{-x}>0$ на множестве G,~ f(a)=f(0,!5)<0, f(b)=f(1)>0 , то f(1)cdot f''(1)>0 , поэтому $x^{(0)}=1$ .

2,3. Результаты расчетов по формуле (3.14) $x^{(k+1)}= x^{(k)}-frac{(x^{(k)})^2-e^{-x^{(k)}}}{2x^{(k)}+e^{-x^{(k)}}},~k=0,1,2,ldots$ помещены в табл. 3.9.

$begin{aligned} mathit{Table~3.9}~&\ begin{array}{|c|c|c|c|c|} hline k& 0& 1& 2& 3\hline begin{matrix}{}\[-8pt]{}end{matrix} x^{(k)}& 1,!000& 0,!73304& 0,!70381& 0,!703467\hline begin{matrix}{}\[-8pt]{}end{matrix} bigl|x^{(k)}-x^{(k-1)}bigr|&-& 0,!27& 0,!029& 0,!00034\hline begin{matrix}{}\[-8pt]{}end{matrix} f(x^{(k)})& 0,!63212& 0,!05690& 0,!00065& 8,!25cdot10^{-7}\hline end{array}& end{aligned}$

Из табл. 3.9 можно сделать следующие выводы:

1. Для достижения заданной точности, проверяемой по модулю разности $bigl|x^{(k)}-x^{(k-1)}bigr|$ , потребовалось выполнить три приближения. Если же выход организовать по условию $bigl|f(x^{(k)})bigr|leqslant varepsilon$ , то достаточно двух приближений.

2. Вблизи корня $x_{ast}$ количество верных цифр в результатах $x^{(k)}$ удваивается, так что все цифры в $x^{(3)}$ являются верными, тогда как в $x^{(2)}$ верными являются первые три цифры после запятой.

3. Скорость сходимости метода Ньютона выше скорости сходимости метода простых итераций (та же точность была достигнута за пять итераций).

Пример 3.12. Методом Ньютона найти корень уравнения x^3-x+1=0 .

Решение

Пример 3.13. Найти корни уравнения x^3-x^2-9x+9=0 методом Ньютона с точностью varepsilon=0,!001 .

Решение

Процедура отделения корней была выполнена в примере 3.3. В качестве отрезков [a_i;b_i] , которым принадлежат корни уравнения, выберем [-4;-2], [2,!5;4], [0,!5;2] .

Так как f(-4)=-3,!5;~ f(-2)=15 , то есть f(-4)f(-2)<0 , производные f''(x)=6x-2<0, f'(x)=3x^2-2x-9>0 сохраняют знак при xin[-4;-2] , то условия сходимости выполняются.

Так как f(2,!5)=-4,!125;~ f(4)=21 , то есть f(2,!5)f(4)<0 , и производные f'(x)>0,~ f''(x)>0 сохраняют знак при xin[2,!5;4] , то условия сходимости на этом отрезке тоже выполняются.

Так как f(0,!5)=4,!375;~ f(2)=-5 , то есть f(0,!5)f(2)<0 , и производные f'(x)<0,~ f''(x)>0 сохраняют знак при xin[0,!5;2] , то условия сходимости выполняются.

1. Зададим начальные приближения: на отрезке [0,!5;2] выберем $x^{(0)}= 0,!5$ , так как f(0,!5)cdot f''(0,!5)>0 ; на отрезке [-4;-2] выберем $x^{(0)}=-4$ , так как f(4)cdot f''(4)>0 ; аналогично на отрезке [2,!5;4] выберем $x^{(0)}=4$ . В поставленной задаче varepsilon= 0,!001 .

2,3. Результаты расчетов по формуле (3.14) $x^{(k+1)}= x^{(k)}-frac{(x^{(k)})^3-(x^{(k)})^2-9x^{(k)}+9}{3(x^{(k)})^2-2x^{(k)}-9},~ k=0,1,2,ldots$ приведены в табл. 3.11–3.13.

$begin{aligned}& begin{aligned} mathit{Table~3.11}~&\ begin{array}{|c|c|c|c|c|c|} hline k& 0& 1& 2& 3& 4 \hline begin{matrix}{}\[-8pt]{}end{matrix} x^{(k)}&-4,!00000&-3,!255319&-3,!023383&-3,!000225&-3,!000000 \hline begin{matrix}{}\[-8pt]{}end{matrix} bigl|x^{(k)}-x^{(k-1)}bigr|&-& 0,!744681& 0,!231936& 0,!023158& 0,!000225 \hline end{array}& end{aligned}\[2pt] & begin{aligned} mathit{Table~3.12}~&\ begin{array}{|c|c|c|c|c|} hline k& 0& 1& 2& 3 \hline begin{matrix}{}\[-8pt]{}end{matrix} x^{(k)}&0,!5000& 0,!972973& 0,!9998246& 1,!0000000 \hline begin{matrix}{}\[-8pt]{}end{matrix} bigl|x^{(k)}-x^{(k-1)}bigr|&-& 0,!472973& 0,!0268516& 0,!0001754 \hline end{array}& end{aligned}\[2pt] & begin{aligned} mathit{Table~3.13}~&\ begin{array}{|c|c|c|c|c|c|c|} hline k& 0& 1& 2& 3& 4& 5 \hline begin{matrix}{}\[-8pt]{}end{matrix} x^{(k)}& 4,!0000& 3,!322581& 3,!051484& 3,!001674& 3,!000002& 3,!0000 \hline begin{matrix}{}\[-8pt]{}end{matrix} bigl|x^{(k)}-x^{(k-1)}bigr|&-& 0,!6774194& 0,!2710969& 0,!049809& 0,!001671& 2cdot10^{-6} \hline end{array}& end{aligned} end{aligned}$

В результате получены приближенные значения корней:

$x_{ast1}cong-3,!0000;qquad x_{ast2}cong1,!0000;qquad x_{ast3}cong 3,!0000.$

Пример 3.14. Найти корень уравнения x^2-2x+1=0 методом Ньютона с точностью varepsilon=0,!01 .

Решение

Очевидно, уравнение имеет один кратный корень $x_{ast}=1$ . Согласно замечанию к теореме 3.12 применение метода Ньютона для решения поставленной задачи сопровождается линейной сходимостью (табл. 3.14).

$begin{aligned} mathit{Table~3.14}~&\ begin{array}{|c|c|c|c|c|c|c|c|c|} hline k& 0& 1& 2& 3& 4& 5& 6& 7\hline begin{matrix}{}\[-8pt]{}end{matrix} x^{(k)}& 2& 1,!5& 1,!25& 1,!125& 1,!0625& 1,!03125& 1,!015625& 1,!007813 \hline begin{matrix}{}\[-8pt]{}end{matrix} bigl|x^{(k)}-x^{(k-1)}bigr|&-& 0,!5& 0,!25& 0,!125& 0,!0625& 0,!03125& 0,!015625& 0,!0078125 \hline end{array}& end{aligned}$

Полученное приближенное решение $x_{ast}cong1,!007813$ .

Нарушение знакопостоянства производных функции

Метод касательных

Метод касательных, являясь весьма эффективным средством численного анализа, к сожалению, имеет достаточно жесткие ограничения. Действительно, он не может применяться для сеточных уравнений (см. рис. 3.2); при нарушении знакопостоянства производных (рис. 3.12); при существовании неограниченных вторых производных и др. Так, если даже условие знакопостоянства нарушено вдали от корня, где выбрано $x^{(0)}$ , а вблизи корня выполняется, то все равно метод касательных неприменим (см. рис. 3.12), если не произвести сужения начального отрезка.

Кроме того, если функция f(x) очень сложная, то будет сложной и ее производная, и поэтому на каждой итерации приходится рассчитывать две функции, что снижает эффективность метода касательных.

Процесс последовательных приближений по методу Ньютона

В силу этого в ряде случаев могут оказаться более предпочтительными модификации метода касательных. Рассмотрим три из них.

Упрощенный метод Ньютона. Методика его применения совпадает с изложенной ранее, но вместо формулы (3.14) используется

$x^{(k+1)}=x^{(k)}-frac{f(x^{(k)})}{f'(x^{(0)})},quad k=0,1,2,ldotsqquad mathsf{(3.19)}$

Отличие от метода Ньютона заключается в том, что производная функции f(x) подсчитывается только в точке начального приближения, а на последующих итерациях не уточняется. Процесс последовательных приближений отражен на рис. 3.13. Первая итерация совпадает с первой итерацией метода Ньютона. На последующих итерациях соответствующие отрезки параллельны касательной, проведенной в начальной точке.

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

Пример 3.15. Найти корень уравнения x^3-x+1=0 упрощенным методом Ньютона.

Решение

Корень уравнения отделен в примере 3.2: $x_{ast}in[-2;-1]$ .

1. Выберем начальное приближение $x^{(0)}=-2$ и зададим varepsilon_1=0,!01 и varepsilon_2=0,!001 .

2,3. Выполним расчеты по формуле (3.19):

$x^{(k+1)}= x^{(k)}-frac{(x^{(k)})^3-x^{(k)}+1}{3(x^{(0)})^2-1}= x^{(k)}-frac{(x^{(k)})^3-x^{(k)}+1}{11},quad k=0,1,2,ldots$

Результаты расчетов приведены в табл. 3.15.

$begin{aligned} mathit{Table~3.15}~&\ begin{array}{|c|c|c||c|c|c|} hline begin{matrix} {}\[-6pt]{}end{matrix} k& x^{(k)}& bigl|x^{(k)}-x^{(k-1)}bigr|& k& x^{(k)}& bigl|x^{(k)}-x^{(k-1)}bigr|\hline 0&-2,!00001&-& 6&-1,!3388& 0,!0092\hline 1&-1,!5455& 0,!4545& 7&-1,!3333& 0,!0005\hline 2&-1,!4413& 0,!1042& 8&-1,!3299& 0,!00034\hline 3&-1,!3911& 0,!0502& 9&-1,!3279& 0,!002\hline 4&-1,!3637& 0,!0274& 10&-1,!3267& 0,!0012\hline 5&-1,!348& 0,!0157& 11&-1,!3259& 0,!0008\hline end{array}& end{aligned}$

При varepsilon=0,!01 получено решение $x_{ast}cong-1,!3388$ , а при varepsilon=0,!001 — решение $x_{ast}cong-1,!3259$ . Очевидно, по сравнению с методом Ньютона сходимость замедляется (см. пример 3.12).

Метод Ньютона-Бройдена

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

$x^{(k+1)}= x^{(k)}-c_kcdot frac{f(x^{(k)})}{f'(x^{(k)})},quad k=0,1,2,ldots$

(3.20)

где c_k — число, которое выбирается на каждой итерации так, чтобы уменьшить значение $bigl|f(x^{(k+1)})bigr|$ по сравнению с $bigl|f(x^{(k)})bigr|$ . При c_k=1 метод Ньютона-Бройдена совпадает с методом Ньютона.

Как правило, при плохой сходимости или ее отсутствии полагают 0<c_k<1 (рис. 3.14,д), а при хорошей сходимости для c_k=1 полагают c_k>1 (это ускоряет сходимость (рис. 3.14,б)).

Сходимость при методе Ньютона-Бройдена

На рис. 3.14 прямоугольниками отмечены точки $x^{(1)}$ , полученные при $c_0=1,~ delta^{(k)}= frac{f(x^{(k)})}{f'(x^{(k)})},~k=0,1,2,ldots$ , — поправка, соответствующая методу Ньютона, а точки $x^{(1)}=x^{(0)}-c_0delta^{(0)}$ получены по методу Ньютона-Бройдена.

Тангенс угла наклона секущей

Метод секущих

В этом методе производная функции f(x) подсчитывается с помощью конечно-разностных соотношений:

– в точке $x^{(0)}$ используется формула $f'(x^{(0)})approx frac{f(x^{(0)})-f(x^{(0)}-delta)}{delta}$ , где delta — малая положительная величина;

– в точках $x^{(k)},~k=1,2,ldots$ , используется формула $f'(x^{(k)})approx frac{f(x^{(k)})-f(x^{(k-1)})}{x^{(k)}-x^{(k-1)}}$ .

Вычисленное значение $f'(x^{(k)})$ определяет тангенс угла наклона секущей (рис. 3.15).

Методика применения метода секущих совпадает с описанной ранее, но вместо (3.14) используется формула

$x^{(k+1)}= x^{(k)}-frac{f(x^{(k)})}{f(x^{(k)})-f(x^{(k-1)})}cdot bigl(x^{(k)}-x^{(k-1)}bigr),quad k=1,2,ldots$

(3.21)

Аппроксимация сеточной функции

Замечания

1. Метод секущих является более экономичным по сравнению с методом Ньютона по количеству функций, подлежащих расчету: на каждой итерации в методе секущих необходимо рассчитать только значение $f(x^{(k)})$ , так как величина $f(x^{(k-1)})$ уже подсчитана на предыдущей итерации.

2. Метод секущих может применяться и для решения сеточных уравнений. Для сеточной функции производные в методе секущих определяются так же, но для определения $f(x^{(k)})$ в промежуточных точках осуществляется аппроксимация (как правило, интерполяция) функции f(x_i) (рис. 3.16). На этом рисунке штриховой линией показана аппроксимационная кривая.

3. Для всех описанных модификаций скорость сходимости по сравнению с методом касательных снижается: p<2 . Однако для некоторых из них (метод секущих) значение p>1 и может достигать p=1,!5 .

Пример 3.16. Методом секущих найти корень уравнения x^3-x+1=0 с точностью varepsilon=0,!001 .

Решение

1. Зададим начальное приближение $x^{(0)}=-2$ (см. пример 3.12).

2. Для вычисления $f'(x^{(0)})$ зададим delta=0,!1 . Тогда

$f'(x^{(0)})cong frac{f(-2)-f(-2,!1)}{0,!1}= frac{-5-(-6,!161)}{0,!1}= 11,!61.$

Отсюда $x^{(1)}= x^{(0)}-frac{f(x^{(0)})}{f'(x^{(0)})}=-2-frac{-5}{11,!61}=-1,!36934$ .

Дальнейшие расчеты выполняются по формуле (3.21):

$begin{aligned}x^{(2)}&=x^{(1)}-frac{f(x^{(1)})}{f(x^{(1)})-f(x^{(0)})}cdot bigl(x^{(1)}-x^{(0)}bigr)=-1,!56934-frac{-1,!29567}{3,!704325}cdot0,!43066=-1,!41871;\[2pt] x^{(3)}&=x^{(2)}-frac{f(x^{(2)})}{f(x^{(2)})-f(x^{(1)})}cdot bigl(x^{(2)}-x^{(1)}bigr)=-1,!41871-frac{-1,!43678}{0,!858893}cdot0,!15063=-1,!34211;\[2pt] x^{(4)}&=x^{(3)}-frac{f(x^{(3)})}{f(x^{(3)})-f(x^{(2)})}cdot bigl(x^{(3)}-x^{(2)}bigr)=-1,!34211-frac{-1,!07538}{0,!361404}cdot0,!0766=-1,!32613;\[2pt] x^{(5)}&=x^{(4)}-frac{f(x^{(4)})}{f(x^{(4)})-f(x^{(3)})}cdot bigl(x^{(4)}-x^{(3)}bigr)=-1,!32613-frac{-1,!00603}{0,!069348}cdot0,!01598=-1,!32474;\[2pt] x^{(6)}&=x^{(5)}-frac{f(x^{(5)})}{f(x^{(5)})-f(x^{(4)})}cdot bigl(x^{(5)}-x^{(4)}bigr)=-1,!32474-frac{-1,!000139}{0,!005936}cdot0,!00139=-1,!32472cong x_{ast}.\[2pt] end{aligned}$

Результаты расчетов приведены в табл. 3.16.

$begin{aligned} mathit{Table~3.16}~&\ begin{array}{|c|c|c|c|c|c|c|c|} hline k& 0& 1& 2& 3& 4& 5& 6\hline begin{matrix}{}\[-8pt]{}end{matrix} x^{(k)}&-2,!00000&-1,!56934&-1,!41871&-1,!34211&-1,!32613&-1,!32474&-1,!32472\hline begin{matrix}{}\[-8pt]{}end{matrix} bigl|x^{(k)}-x^{(k-1)}bigr|&-& 0,!43066& 0,!15063& 0,!07660& 0,!01598& 0,!00139& 0,!00002 \hline end{array}& end{aligned}$

Очевидно, метод сходится чуть хуже метода Ньютона (см. пример 3.12), однако скорость сходимости выше линейной.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Кнопка "Поделиться"

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

Источник

Описание метода[править | править код]

Обоснование[править | править код]

Геометрическая интерпретация[править | править код]

Алгоритм[править | править код]

Пример[править | править код]

Условия применения[править | править код]

Контрпримеры[править | править код]

Ограничения[править | править код]

Историческая справка[править | править код]

Обобщения и модификации[править | править код]

Метод секущих[править | править код]

Метод одной касательной[править | править код]

Метод Ньютона-Фурье[править | править код]

Многомерный случай[править | править код]

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

Метод Ньютона — Рафсона[править | править код]

Применительно к задачам о наименьших квадратах[править | править код]

Метод Гаусса — Ньютона[править | править код]

Обобщение на комплексную плоскость[править | править код]

Реализация[править | править код]

Scala[править | править код]

Python[править | править код]

PHP[править | править код]

Octave[править | править код]

Delphi[править | править код]

C++[править | править код]

C[править | править код]

Haskell[править | править код]

Литература[править | править код]

См. также[править | править код]

Ссылки[править | править код]

Решение уравнения методом Ньютона

Точное значение корня

Абсолютная и относительная погрешность вычисления

Численные методы решения нелинейных уравнений

Корни нелинейных уравнений

Отделение корней уравнения

Способы отделения корней

Метод половинного деления

Алгоритм метода половинного деления

Метод хорд

Метод простых итераций

Метод Ньютона для решения нелинейных уравнений

Достаточные условия сходимости метода Ньютона

Метод касательных

Метод Ньютона-Бройдена

Метод секущих

Вам также может понравиться

Как найти среднее формула информатика

Майнкрафт как легко найти сокровищницу

Как найти все свои задолженности

Добавить комментарий Отменить ответ