• 1 Описание метода
  • 1.1 Вывод
  • 1.2 Геометрическая интерпретация
  • 1.3 Алгоритм
  • 1.4 Пример
• 2 Условия применения
  • 2.1 Контрпримеры
  • 2.2 Ограничения
• 3 Историческая справка
• 4 Обобщения и модификации
  • 4.1 Метод секущих
  • 4.2 Метод одной касательной
  • 4.3 Метод Ньютона-Фурье
  • 4.4 Многомерный случай
  • 4.5 Применительно к задачам оптимизации
  • 4.6 Метод Ньютона — Рафсона
  • 4.7 Применительно к задачам о наименьших квадратах
  • 4.8 Метод Гаусса — Ньютона
  • 4.9 Обобщение на комплексную плоскость
• 5 Реализация
  • 5.1 Scala
  • 5.2 Python
  • 5.3 PHP
  • 5.4 Octave
  • 5.5 Delphi
  • 5.6 C++
  • 5.7 C
  • 5.8 Haskell
  • 5.9 Fortran
  • 5.10 PascalABC.Net
• 6 Литература
• 7 См. также
• 8 Примечания
• 9 Ссылки

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

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

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

${\displaystyle \scriptstyle {f(x)\colon \mathbb {X} \to \mathbb {R} ,\;f(x)\in \mathrm {C} ^{2}(\mathbb {X} );\quad \forall x\in \mathbb {X} \;f'(x)\neq 0.}}$

${\displaystyle \scriptstyle {\varphi '(x)={\frac {f(x)f''(x)}{\left(f'(x)\right)^{2}}}.}}$

${\displaystyle \scriptstyle {\forall \varepsilon \colon 0<\varepsilon <1,\;\exists \delta >0\;\forall x\in \mathbb {X} \;|x-{\tilde {x}}|<\delta \colon |\varphi '(x)-0|<\varepsilon .}}$

${\displaystyle \scriptstyle {\forall x_{1},\;x_{2}\in \mathrm {U} _{\delta }({\tilde {x}})\;\exists \xi \in \mathrm {U} _{\delta }({\tilde {x}})\colon |\varphi (x_{1})-\varphi (x_{2})|=|\varphi '(\xi )||x_{1}-x_{2}|<\varepsilon |x_{1}-x_{2}|.}}$

${\displaystyle \scriptstyle {\forall x\in U_{\delta }({\tilde {x}})\colon \;|\varphi (x)-{\tilde {x}}|<\varepsilon |x-{\tilde {x}}|.}}$

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

${\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 x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.}$

1. Задается начальное приближение ${\displaystyle x_{0}}$.
2. Пока не выполнено условие остановки, в качестве которого следует взять ${\displaystyle \left\vert {\frac {x_{n+1}-x_{n}}{1-{\frac {x_{n+1}-x_{n}}{x_{n}-x_{n-1}}}}}\right\vert <\varepsilon }$, где ${\displaystyle \varepsilon }$ выполняет роль абсолютной погрешности (так как метод Ньютона является частным случаем метода простой итерации^[1]), вычисляют новое приближение: ${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 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;

}

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

type
  Tfunc = function( x : Double) : Double;

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

#include <iostream>
#include <cmath>

constexpr double eps = 0.000001;
double fx(double x) { return x * x - 17; } // вычисляемая функция
double dfx(double x) { return 2 * x; }     // производная функции

using function = double (*)(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 () {
  std::cout << solve(fx, dfx, 4) << "\n"; // вывод на экран
  return 0;
}

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)

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

!   Main program
    REAL*8:: Xbeg, F, D1F, error  ! Имена переменных в главной программе и подпрограмме могут отличаться    
    INTEGER  Niter, Ncalc         ! Xbeg - начальное значение, F - функция, D1F - её производная, error - остаточная ошибка
        ***                       ! Niter - заданное число итераций, Ncalc - число выполненных итераций до достижения погрешности
    CALL NEWTON(Xbeg, Niter, F, D1F, Ncalc, error)
        ***
C======================================================
    SUBROUTINE NEWTON(X0, Nmax, Func, D1Func, Nevl, rer) ! Простейший вариант устойчиво работающей программы для нахождения корня  без второй производной                                                               

	REAL*8:: X0, X1, XB, q, Func, D1Func, rer, eps       ! Итог вычисления будет записан в переменную Х0
	INTEGER  Nmax, Nevl
	
	IF(Nmax*(1000-Nmax).LE.0) Nmax=1000                 ! Защита от дурака
	                Nevl=1; XB=X0
	DO I=1, Nmax
	IF(Func(X0).EQ.0.)            EXIT
    IF(D1Func(X0).EQ.0.)          THEN
    Print *, 'Error from NEWTON: D1Func=', D1Func(X0), '  X=', X0, '  I=', I
                                  EXIT
    END IF                   
		
	X1=X0-Func(X0)/D1Func(X0) 
	
	q=abs(D1Func(X0));  q=abs(1.-q)/q
	eps=MAX(rer, epsilon(X0))                           ! epsilon(X0) - машинная точность; выбирается, если rer=0.
	IF(abs(X0-X1).LE.q*eps)       EXIT
	
	X0=X1
	END DO
    
    IF(abs(Func(X0)).GE.abs(Func(XB))) PAUSE 'Error from NEWTON: Change the X0!'

	If(I.ne.Nmax+1) Nevl=I
	If(I.eq.Nmax+1) Nevl=Nmax
	
	END SUBROUTINE