Newton's method

Original article: wikipedia:Newton's method

This article is about Newton's method for finding roots. For Newton's method for finding minima, see Newton's method in optimization.

수치 해석학(numerical analysis)에서, 뉴턴의 방법(Newton's method)은, 아이작 뉴턴(Isaac Newton)과 조셉 랍선(Joseph Raphson)의 이름을 따서 지은 역시 뉴턴-랍선법(Newton-Raphson method)으로 알려져 있으며, 실수-값 함수(function)의 근들 (또는 영들)에 대한 연속적으로 더 좋은 근사를 생성하는 근-찾는 알고리듬입니다. 가장 기본적인 버전은 실수 변수 x에 대해 정의된 단일-변수 함수 f, 함수의 도함수 f′, 및 f의 근에 대한 초기 추측값 x₀로 시작합니다. 만약 함수가 충분한 가정을 만족시키고 초기 추측이 가까우면, 다음은 x₀보다 근의 더 좋은 근사입니다:

$x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}\,.$

기하학적으로, (x₁, 0)은 (x₀, f(x₀))에서 f의 그래프(graph)의 접선(tangent)과 x-축과의 교차점입니다: 즉, 개선된 추측은 초기 지점에서 선형 근사(linear approximation)의 고유한 근입니다. 그 과정은, 충분하게 정확한 값에 이를 때까지, 다음과 같이 반복됩니다:

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

이 알고리듬은 핼리의 방법(Halley's method)에 의해 성공했던 하우스홀더의 방법(Householder's method)의 클래스에서 첫 번째입니다. 그 방법은 역시 복소 함수(complex functions)와 방정식의 시스템으로 확장될 수 있습니다.

Description

그 아이디어는 초기 추측으로 시작하고, 그런-다음 접선으로 함수를 근사화하고, 마지막으로 이 접선의 x-절편을 계산하는 것입니다. 이 x-절편은 전형적으로 첫 번째 추측보다 원래 함수의 근에 대한 더 좋은 근사이고, 그 방법은 반복될 수 있습니다.

x_{n + 1} is a better approximation than x_n for the root x of the function f (blue curve)

만약 x = x_n에서 곡선 f(x)에 대한 접선이 x_n+1에서 x-축을 교차하면, 그 기울기는 다음과 같습니다:

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

x_{n + 1}에 대해 풀면 다음을 제공합니다:

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

Iteration typically improves the approximation

우리는 어떤 임의적인 초기 값 x₀으로 과정을 시작합니다. (영에 더 가까울수록, 더 좋습니다. 그러나, 영이 어디에 있는지에 대한 어떤 직관이 없으면, "추측과 확인" 방법은 사잇값 정리(intermediate value theorem)에 호소함으로써 상당히 작은 구간으로 가능성을 좁힐 수 있습니다.) 이 초기 추측이 알려지지 않은 영에 충분히 가깝고 f ′(x₀) ≠ 0라는 조건 아래에서 그 방법은 보통 수렴할 것입니다. 더구나, 중복도 1의 영에 대해, 수렴은 영의 이웃에서 적어도 이차이며 (수렴의 율을 참조하십시오), 이는 직관적으로 올바른 자릿수가 모든 각 단계에서 대략 두 배가 된다는 것을 의미합니다. 자세한 내용은 아래 해석 섹션에서 확인할 수 있습니다.

하우스홀더의 방법(Householder's methods)은 유사하지만 더 빠른 수렴을 위해 더 높은 차수를 가집니다. 어쨌든, 각 단계에 필요한 여분의 계산은 특히 f 또는 그것의 도함수가 평가하기 위해 계산적으로 비용이 많이 드면 뉴턴의 방법에 비해 전체 성능을 저하시킬 수 있습니다.

History

"뉴턴의 방법"이라는 이름은 De analysi per aequationes numero terminorum infinitas (1669년에 쓰임, 1711년에 William Jones에 의해 출판됨)과 De metodis fluxionum et serierum infinitarum (1669년에 쓰임, 1711년에 John Colson에 의해 Method of Fluxions로 번역되고 출판됨)에서 방법의 특별한 경우의 아이작 뉴턴(Isaac Newton)의 설명에서 유래되었습니다. 어쨌든, 그의 방법은 위에서 제시한 현대적 방법과는 상당히 다릅니다. 뉴턴은 이 방법을 다항식에만 적용하여, 초기 근 추정에서 시작하고 오류 수정의 순서를 추출했습니다. 그는 각 수정을 사용하여 다항식을 남아있는 오류의 항으로 다시 쓰고 더 높은 차수 항을 무시함으로써 새로운 수정을 해결했습니다. 그는 방법을 도함수와 명시적으로 연결하거나 일반 공식을 제시하지 않았습니다. 뉴턴은 이 방법을 수치적 및 대수적 문제 모두에 적용하여, 후자의 경우에서 테일러 급수(Taylor series)를 생성했습니다.

뉴턴은 비에타에 의한 것과 유사하지만 덜 정확한 방법에서 그의 방법을 도출했을 수 있습니다. 비에타 방법의 본질은 페르시아 수학자 샤라프 알-딘 알-천(Sharaf al-Din al-Tusi)의 연구에서 찾을 수 있고, 반면에 그의 후계자 잠쉬드 알-캐시(Jamshīd al-Kāshī)는 N의 근을 찾기 위해 x^P − N = 0을 풀기 위해 뉴턴 방법의 한 형식을 사용했습니다 (Ypma 1995). 제곱 근을 계산하는 뉴턴의 방법의 특별한 경우는 고대부터 알려져 왔었고 종종 바빌로니아 방법(Babylonian method)이라고 불립니다.

뉴턴의 방법은 17세기 일본 수학자 세키 코오와(Seki Kōwa)에 의해 단일-변수 방정식을 풀기 위해 사용되었지만, 미적분과의 연관성은 없었습니다.

뉴턴의 방법은 1685년 존 월리스(John Wallis)의 A Treatise of Algebra both Historical and Practical에서 처음 출판되었습니다. 1690년에, 조셉 랍선(Joseph Raphson)은 Analysis aequationum universalis에서 단순화된 설명을 출판했습니다. 랍선은 역시 이 방법을 다항식에만 적용했지만, 원래 다항식에서 각각의 연속적인 수정을 추출함으로써 뉴턴의 지루한 재작성 과정을 피했습니다. 이를 통해 그는 각 문제에 대해 재사용-가능한 반복 표현을 도출할 수 있었습니다. 마지막으로, 1740년에, 토머스 심프슨(Thomas Simpson)은 뉴턴의 방법을 미적분학을 사용하여 일반적인 비-선형 방정식을 푸는 반복 방법으로 설명했으며, 본질적으로 위의 설명을 제공합니다. 같은 출판물에서, 심프슨은 역시 두 방정식의 시스템에 대한 일반화를 제공하고 그래디언트를 영으로 설정함으로써 최적화 문제를 푸는 데 뉴턴의 방법을 사용할 수 있다고 언급합니다.

1879년에 The Newton–Fourier imaginary problem에서 아서 케일리(Arthur Cayley)는 뉴턴의 방법을 2보다 큰 차수와 복소수 초기 값을 갖는 다항식의 복소수 근으로 일반화하는 데 어려움이 있음을 처음으로 알아차렸습니다. 이것은 유리 함수의 반복의 이론(theory of iterations) 연구의 길을 열었습니다.

Practical considerations

뉴턴의 방법은 강력한 기술입니다—일반적으로 수렴(convergence)은 이차입니다: 그 방법이 근에 수렴함에 따라, 근과 근사 사이의 차이는 각 단계에서 제곱됩니다 (정확한 자릿수의 개수는 대략 두 배가 됩니다). 어쨌든, 그 방법에는 몇 가지 어려움이 있습니다.

Difficulty in calculating the derivative of a function

뉴턴의 방법은 도함수가 직접 계산될 수 있어야 함을 요구합니다. 도함수에 대한 해석적 표현은 쉽게 구할 수 없거나 평가 비용이 많이 들 수 있습니다. 이들 상황에서, 함수에서 가까운 두 점을 통과하는 직선의 기울기를 사용함으로써 도함수를 근사화하는 것이 적절할 수 있습니다. 이 근사를 사용하면 수렴이 뉴턴의 방법보다 느린 시컨트 방법(secant method)과 같은 결과를 얻을 수 있습니다.

Failure of the method to converge to the root

그것을 구현하기 전에 뉴턴의 방법의 이차 수렴의 증명(proof of quadratic convergence)을 검토하는 것이 중요합니다. 구체적으로 특별히, 증명에서 만들어진 가정을 검토해야 합니다. 그 방법이 수렴에 실패하는 상황에 대해, 그것은 이 증명에서 만들어진 가정이 충족되지 않기 때문입니다.

Overshoot

만약 일차 도함수가 특정 근의 근처에서 잘 작동하지 않으면, 그 방법이 지나치게 빨리 이동할 수 있고, 해당 근에서 발산할 수 있습니다. 도함수가 근의 근처에서 잘 동작하지 않는 하나의 근을 갖는 함수의 예제는 다음입니다:

$f(x)=|x|^{a},\quad 0<a<{\tfrac {1}{2}}$

이것에 대해 근은 지나치게 빨리 이동할 것이고 x의 수열은 발산할 것입니다. a = 1/2에 대해, 근은 여전히 지나치게 빠르게 이동할 것이지만, 수열은 두 값 사이에서 진동할 것입니다. 1/2 < a < 1에 대해, 근은 여전히 지나치게 빠르게 이동될 것이지만, 수열은 수렴할 것이고, a ≥ 1에 대해 근은 전혀 빠르게 이동하지 않을 것입니다.

일부 경우에서, 뉴턴의 방법은 연속적인 과잉-이완(successive over-relaxation)을 사용함으로써 안정화되거나, 같은 방법을 사용함으로써 수렴의 속력을 높일 수 있습니다.

Stationary point

만약 함수의 정류 점(stationary point)이 발견되면, 그 도함수는 영이고 그 방법은 영에 의한 나눗셈(division by zero)으로 인해 종료될 것입니다.

Poor initial estimate

초기 추정에서 큰 오류는 알고리듬의 비-수렴에 기여할 수 있습니다. 이 문제를 극복하기 위해, 종종 미적분, 로그, 미분, 또는 심지어 확률적 터널링(stochastic tunneling)과 같은 진화 알고리듬을 사용하여 최적화되는 함수를 선형화할 수 있습니다. 좋은 초기 추정은 최종 전역적 최적 매개변수 추정에 가깝게 놓입니다. 비-선형 회귀에서, 제곱된 오차의 합 (SSE)은 오직 최종 매개변수 추정의 영역에서 포물선에 "가깝습니다". 여기에서 찾은 초기 추정은 뉴턴-랍선 방법을 빠르게 수렴하도록 허용합니다. SSE의 헤세 행렬(Hessian matrix)이 양수이고 SSE의 일차 도함수가 영에 가까운 것은 여기에서만 가능합니다.

Mitigation of non-convergence

뉴턴 방법의 강건한 구현에서, 반복의 횟수에 제한을 두고, 해를 근을 포함하는 것으로 알려진 구간으로 경계짓고, 그 방법을 보다 강건한 근 찾는 방법과 결합하는 것이 공통적입니다.

Slow convergence for roots of multiplicity greater than 1

만약 찾고 있는 근이 일보다 큰 중복도(multiplicity)를 가지면, 특별한 조치를 취하지 않은 한 수렴 율은 선형에 불과합니다 (오차는 각 단계에서 상수 인수만큼 감소합니다). 서로 가까이 있는 두 개 이상의 근이 있을 때, 반복이 이차 수렴에 대해 명백할 수 있도록 그 중 하나에 충분히 가까워지기 전에 많은 반복이 필요할 수 있습니다. 어쨌든, 근의 중복도 m이 알려져 있으면, 다음 수정된 알고리듬은 이차 수렴 율을 유지합니다:

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

이것은 연속적인 과잉-이완(successive over-relaxation)을 사용하는 것과 동등합니다. 다른 한편으로, 근의 중복도 m이 알려져 있지 않으면, 한두 번의 반복을 수행한 후 m을 추정하고, 그런-다음 그 값을 사용하여 수렴의 율을 높일 수 있습니다.

만약 근의 중복도 m이 유한이면, g(x) = f(x)/f′(x)는 중복도 1로 같은 위치에 근을 가질 것입니다. g(x)의 근을 찾기 위해 뉴턴의 방법을 적용하면 많은 경우에서 이차 수렴을 복구하지만, 일반적으로 f(x)의 이차 도함수를 포함합니다. 특히 간단한 경우에서, 만약 f(x) = x^m이면 g(x) = x/m이고 뉴턴의 방법은 다음과 함께 단일 반복에서 근을 찾습니다:

$x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}=x_{n}-{\frac {\;{\frac {x_{n}}{m}}\;}{\frac {1}{m}}}=0\,.$

Analysis

함수 f가 α에서 영을 가지고, 즉, f(α) = 0이고, f가 α의 이웃(neighborhood)에서 미분-가능이라고 가정합니다.

만약 f가 연속적으로 미분-가능이고 그 도함수가 α에서 비-영이면, 해당 이웃에서 모든 시작하는 값 x₀에 대해, 수열(sequence) (x_n)이 α로 수렴할 것임을 만족하는 α의 이웃(neighborhood)이 존재합니다.

만약 함수가 연속적으로 미분-가능이고 그 도함수가 α에서 0이 아니고 그것이 α에서 이차 도함수(second derivative)를 가지면 수렴은 이차 또는 더 빠릅니다. 만약 이차 도함수가 α에서 0이 아니면 수렴은 단지 이차입니다. 만약 삼차 도함수가 존재하고 α의 이웃에서 경계지면:

$\Delta x_{i+1}={\frac {f''(\alpha )}{2f'(\alpha )}}\left(\Delta x_{i}\right)^{2}+O\left(\Delta x_{i}\right)^{3}\,,$

여기서

$\Delta x_{i}\triangleq x_{i}-\alpha \,.$

만약 도함수가 α에서 0이면, 수렴은 보통 오직 선형입니다. 구체적으로, 만약 f가 두 번 연속적으로 미분-가능이고, f′(α) = 0이고 f″(α) ≠ 0이면, 해당 이웃에서 모든 시작하는 값 x₀에 대해, 반복의 수열이 수렴률 1/2과 함께 선형적으로 수렴함을 만족하는 α의 이웃이 존재합니다. 대안적으로, 만약 f′(α) = 0이고 x ≠ α, α의 이웃 U에서 x에 대해 f′(x) ≠ 0, α가 중복도 r의 영이 있고, f ∈ C^r(U)이면, 해당 이웃에서 모든 시작하는 값 x₀에 대해, 반복의 수열이 선형적으로 수렴함을 만족하는 α의 이웃이 존재합니다.

어쨌든, 병리학적 상황에서는 선형 수렴조차도 보장되지 않습니다.

실제로, 이들 결과는 지역적이고, 수렴의 이웃은 미리 알려져 있지 않습니다. 그러나 전역 수렴에 대한 몇 가지 결과도 있습니다: 예를 들어, α의 오른쪽 이웃 U₊가 주어질 때, 만약 f가 U₊에서 두 번 미분-가능이고 U₊에서 f′ ≠ 0, f · f″ > 0이면, U₊에서 각 x₀에 대해 수열 x_k는 α로 단조적으로 감소하는 것입니다.

Proof of quadratic convergence for Newton's iterative method

테일러의 정리(Taylor's theorem)에 따르면, 연속적인 이차 도함수를 가지는 임의의 함수 f(x)는 f(x)의 근에 가까운 점에 의한 전개로 표현될 수 있습니다. 이 근이 α라고 가정합니다. 그런-다음 x_n에 대한 f(α)의 전개는 다음과 같습니다:

$f(\alpha )=f(x_{n})+f'(x_{n})(\alpha -x_{n})+R_{1}\,$

(1)

여기서 테일러 급수 전개 나머지의 라그랑주 형식(Lagrange form of the Taylor series expansion remainder)은 다음과 같습니다:

$R_{1}={\frac {1}{2!}}f''(\xi _{n})\left(\alpha -x_{n}\right)^{2}\,,$

여기서 ξ_n는 x_n과 α 사이에 있습니다.

α가 근이기 때문에, (1)이 됩니다:

$0=f(\alpha )=f(x_{n})+f'(x_{n})(\alpha -x_{n})+{\tfrac {1}{2}}f''(\xi _{n})\left(\alpha -x_{n}\right)^{2}\,$

(2)

방정식 (2)를 f′(x_n)로 나누고 재배열하면 다음을 제공합니다:

${\frac {f(x_{n})}{f'(x_{n})}}+\left(\alpha -x_{n}\right)={\frac {-f''(\xi _{n})}{2f'(x_{n})}}\left(\alpha -x_{n}\right)^{2}$

(3)

x_{n + 1}이 다음에 의해 정의됨을 기억하십시오:

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

(4)

다음임을 찾습니다:

$\underbrace {\alpha -x_{n+1}} _{\varepsilon _{n+1}}={\frac {-f''(\xi _{n})}{2f'(x_{n})}}{(\,\underbrace {\alpha -x_{n}} _{\varepsilon _{n}}\,)}^{2}\,.$

즉,

$\varepsilon _{n+1}={\frac {-f''(\xi _{n})}{2f'(x_{n})}}\cdot \varepsilon _{n}^{2}\,.$

(5)

양쪽 변에 절댓값을 취하면 다음을 제공합니다:

$\left|{\varepsilon _{n+1}}\right|={\frac {\left|f''(\xi _{n})\right|}{2\left|f'(x_{n})\right|}}\cdot \varepsilon _{n}^{2}\,.$

(6)

방정식 (6)은 수렴의 차수(order of convergence)가 만약 다음 조건이 만족되면 적어도 이차임을 보여줍니다:

1. f′(x) ≠ 0; for all x ∈ I, where I is the interval [α − r, α + r];
2. f″(x) is continuous, for all x ∈ I;
3. x₀ satisfies r ≥ |α − x₀|;
4. M |ε₀| < 1

여기서 M은 다음에 의해 제공됩니다:

$M={\frac {1}{2}}\left(\sup _{x\in I}\vert f''(x)\vert \right)\left(\sup _{x\in I}{\frac {1}{\vert f'(x)\vert }}\right).\,$

만약 이들 조건이 유지되면,

$\vert \varepsilon _{n+1}\vert \leq M\cdot \varepsilon _{n}^{2}\,.$

Basins of attraction

각 영역 내에서 임의의 점에서 하나의 특정 근으로 이어짐을 만족하는 실수 직선의 영역—끌어당김의 웅덩이(basins of attraction)의 서로보 부분집합은 숫자에서 무한일 수 있고 임의적으로 작을 수 있습니다. 예를 들어, 함수 f(x) = x³ − 2x² − 11x + 12 = (x − 4)(x − 1)(x + 3)에 대해, 다음 초기 조건이 연속적인 끌어당김의 웅덩이에 있습니다:

2.35287527	converges to	4;
2.35284172	converges to	−3;
2.35283735	converges to	4;
2.352836327	converges to	−3;
2.352836323	converges to	1.

Failure analysis

뉴턴의 방법은 오직 특정 조건이 충족되면 수렴이 보장됩니다. 만약 이차 수렴의 증명에서 만들어진 가정이 충족되면, 그 방법은 수렴될 것입니다. 다음 하위-섹션에 대해, 수렴에 대한 그 방법의 실패는 증명에서 만들어진 가정이 충족되지 않았음을 나타냅니다.

Bad starting points

일부 경우에서, 수렴에 필요한 함수에 대한 조건은 만족시키지만, 초기 점으로 선택된 점이 그 방법이 수렴하는 구간에 있지 않습니다. 이것은, 예를 들어, 만약 x가 ∞ 또는 −∞로 갈 때 근을 구하는 함수가 점근적으로 영에 접근하면 발생할 수 있습니다. 그러한 경우에서, 이등분(bisection)과 같은 다른 방법이 초기 점으로 사용하기 위한 영에 대한 더 나은 추정을 얻기 위해 사용되어야 합니다.

Iteration point is stationary

다음 함수를 생각해 보십시오:

$f(x)=1-x^{2}.$

그것은 x = 0에서 최댓값을 가지고 x = ±1에서f(x) = 0의 해를 가집니다. 만약 우리가 정류 점(stationary point) x₀ = 0 (여기서 도함수는 영)에서 반복을 시작하면, (0, 1)에서 접선이 x-축과 평행하기 때문에 x₁은 정의되지 않을 것입니다:

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

같은 문제는 시작하는 점 대신, 임의의 반복 지점이 정류 점이면 발생합니다. 심지어 도함수가 작지만 영이 아니더라도, 다음 반복은 훨씬 더 나쁜 근사일 것입니다:

Starting point enters a cycle

The tangent lines of x³ − 2x + 2 at 0 and 1 intersect the x-axis at 1 and 0 respectively, illustrating why Newton's method oscillates between these values for some starting points.

일부 함수에 대해, 일부 시작하는 점이 무한 순환에 진입할 수 있으며, 수렴을 방지합니다. 다음이라고 놓고

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

0을 시작하는 점으로 취합니다. 첫 번째 반복은 1을 생성하고 두 번째 반복은 0으로 돌아가므로 수열은 근으로 수렴 없이 둘 사이를 교대할 것입니다. 사실, 이 2-주기는 안정적입니다: 모든 점이 2-주기 (및 따라서 함수의 근가 아닌)로 점근적으로 반복하는 0 주면과 1 주변의 이웃이 있습니다. 일반적으로, 수열의 동작은 매우 복잡할 수 있습니다 (뉴턴 프랙탈을 참조하십시오). 이 방정식의 실수 해는 −1.76929235…입니다.

Derivative issues

만약 함수가 근의 근처에서 연속적으로 미분-가능이 아니면, 첫 번째 시도에서 해를 추측하지 않은 한 뉴턴의 방법이 항상 발산하고 실패할 가능성이 있습니다.

Derivative does not exist at root

뉴턴의 방법이 발산하는 함수의 간단한 예제는 영의 세제곱근을 찾으려고 시도하는 것입니다. 세제곱근은 도함수가 정의되지 않은 x = 0을 제외하고 연속적이고 무한하게 미분-가능입니다:

$f(x)={\sqrt[{3}]{x}}.$

임의의 반복 점 x_n에 대해, 다음 반복 점은 다음일 것입니다:

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

그 알고리듬은 해를 빠르게 지나가고 처음보다 더 멀리 떨어진 y-축의 다른 쪽에 도달합니다; 뉴턴의 방법을 적용하면 실제로 각 반복에서 해로부터의 거리가 두 배가 됩니다.

사실, 반복은 0 < α < 1/2인 모든 각 f(x) = |x|^α에 대해 무한대로 발산합니다. α = 1/2 (제곱근)의 제한적인 경우에서, 반복은 점 x₀과 −x₀ 사이에서 무한정으로 교대할 것이므로, 그것들은 이 경우에도 수렴하지 않습니다.

Discontinuous derivative

만약 도함수가 근에서 연속적이지 않으면, 수렴이 임의의 근 근처에서 발생하지 않을 수 있습니다. 다음 함수를 생각해 보십시오:

$f(x)={\begin{cases}0&{\text{if }}x=0,\\x+x^{2}\sin {\frac {2}{x}}&{\text{if }}x\neq 0.\end{cases}}$

그것의 도함수는 다음과 같습니다:

$f'(x)={\begin{cases}1&{\text{if }}x=0,\\1+2x\sin {\frac {2}{x}}-2\cos {\frac {2}{x}}&{\text{if }}x\neq 0.\end{cases}}$

근의 임의의 이웃 내에서, 이 도함수는 0 < x < 1에 대해 f(x) ≥ x − x² > 0인 동안 x가 오른쪽 (또는 왼쪽)에서 0에 접근함에 따라 부호를 계속 변경합니다.

따라서 f(x)/f′(x)는 근 근처에서 경계지지 않고, 뉴턴의 방법은 심지어 다음과 같은 경우에도 근의 임의의 이웃에서 거의 모든 곳에서 발산할 것입니다:

• 함수는 모든 곳에서 미분-가능입니다 (및 따라서 연속입니다);
• 근에서 도함수는 비-영입니다;
• f는 근을 제외하고 무한하게 미분-가능입니다; 그리고
• 도함수는 근의 이웃에서 (f(x)/f′(x)와 달리) 경계집니다.

Non-quadratic convergence

일부 경우에서, 반복이 수렴하지만 약속한 만큼 빨리 수렴하지 않습니다. 이들 경우에서, 더 간단한 방법이 뉴턴의 방법만큼 빠르게 수렴됩니다.

Zero derivative

만약 일차 도함수가 근에서 영이면, 수렴은 이차가 아닐 것입니다. 다음이라고 놓으면

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

f′(x) = 2x이고 결과적으로

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

따라서 심지어 함수가 모든 곳에서 무한하게 미분-가능이더라도 수렴은 이차가 아닙니다.

심지어 근이 오직 "거의" 두 배가 될 때 유사한 문제가 발생합니다. 예를 들어, 다음이라고 놓습니다:

$f(x)=x^{2}(x-1000)+1.$

그런-다음 x₀ = 1에서 시작하는 처음 몇 번의 반복은 다음과 같습니다:

x₀ = 1

x₁ = 0.500250376…

x₂ = 0.251062828…

x₃ = 0.127507934…

x₄ = 0.067671976…

x₅ = 0.041224176…

x₆ = 0.032741218…

x₇ = 0.031642362…

수렴이 이차적으로 나타나는 지점에 도달하기 위해 6번의 반복이 필요합니다.

No second derivative

만약 근에 이차 도함수가 없으면, 수렴이 이차가 됨에 실패할 수 있습니다. 다음이라고 놓습니다:

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

그런-다음

$f'(x)=1+{\tfrac {4}{3}}x^{\frac {1}{3}}.$

그리고 정의되지 않는 x = 0일 때를 제외하고

$f''(x)={\tfrac {4}{9}}x^{-{\frac {2}{3}}}$

x_n이 주어지면,

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

이는 x_n이 가지는 것보다 약 4/3배 많은 정밀도 비트를 가집니다. 이것은 이차 수렴에 필요한 것보다 2배 적습니다. 따라서 뉴턴의 방법 (이 경우)의 수렴은 이차가 아니며, 심지어: 그 함수는 모든 곳에서 연속적으로 미분-가능입니다; 도함수는 루트에서 영이 아닙니다; 그리고 f는 원했던 근을 제외하고 무한하게 미분-가능입니다.

Generalizations

Complex functions

Basins of attraction for x⁵ − 1 = 0; darker means more iterations to converge.

Main article: Newton fractal

복소 함수(complex functions)를 다룰 때, 뉴턴의 방법은 그것들의 영을 찾기 위해 직접 적용될 수 있습니다. 각각의 영은 복소 평면에 끌어당김의 웅덩이(basins of attraction), 그 방법이 해당 특정 영으로 수렴하도록 하는 모든 시작하는 값의 집합을 가집니다. 이들 집합은 표시된 이미지에서 처럼 매핑될 수 있습니다. 많은 복소 함수에 대해, 끌어당김의 웅덩이의 경계는 프랙탈(fractals)입니다.

일부 경우에서, 복소 평면에 임의의 이들 끌어당김의 웅덩이에 있지 않은 영역이 있으며, 반복이 수렴하지 않음을 의미합니다. 예를 들어, 만약 실수 초기 조건을 x² + 1의 근을 찾기 위해 사용하면, 모든 후속 반복은 실수일 것이고 따라서 반복은 두 근 중 하나에 수렴하지 못하는데, 왜냐하면 두 근이 모두 비-실수이기 때문입니다. 이 경우에서, 거의 모든(almost all) 실수 초기 조건은 무질서한 행동(chaotic behavior)으로 이어지고, 반면에 일부 초기 조건은 무한대로 반복되거나 임의의 유한 길이의 반복 주기로 반복됩니다.

Curt McMullen은 뉴턴의 방법과 유사한 임의의 순수하게 반복 알고리듬에 대해, 그 알고리듬이 차수 4 이상의 일부 다항식에 적용될 때 복소 평면의 일부 열린 영역에서 발산할 것임을 보여주었습니다. 어쨌든, McMullen은 차수 3의 다항식에 대해 일반적으로 수렴하는 알고리듬을 제공했습니다.

Systems of equations

k variables, k functions

우리는 역시 뉴턴의 방법을 k 방정식의 시스템을 풀기 위해 사용할 수 있으며, 이는 k 연속적으로 미분-가능 함수 $f:\mathbb {R} ^{k}\to \mathbb {R}$의 (동시) 영들을 찾는 것과 같습니다. 이것은 단일 벡터-값 함수 $F:\mathbb {R} ^{k}\to \mathbb {R} ^{k}$의 영들을 찾는 것과 동등합니다. 위에 주어진 공식에서, 스칼라 x_n은 벡터 x_n으로 대체되고 함수 f(x_n)을 그의 도함수 f′(x_n)로 나누는 대신 함수 F(x_n)을 그것의 k × k 야코비 행렬(Jacobian matrix) J_F(x_n)의 역으로 곱해야 합니다. 이것은 다음과 같은 표현의 결과입니다:

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-J_{F}(\mathbf {x} _{n})^{-1}F(\mathbf {x} _{n})$.

야코비 행렬의 역을 실제로 계산하는 대신, 선형 방정식의 시스템(system of linear equations)을 풂으로써 시간을 절약하고 수치적 안정성을 높일 수 있습니다:

$J_{F}(\mathbf {x} _{n})(\mathbf {x} _{n+1}-\mathbf {x} _{n})=-F(\mathbf {x} _{n})$

여기서 x_{n + 1} − x_n는 미지수입니다.

k variables, m equations, with m > k

뉴턴 방법의 k-차원 변형은 만약 그 알고리듬이 J의 역 대신 비-정사각 야코비(Jacobian) 행렬 J⁺ = (J^TJ)⁻¹J^T의 일반화된 역(generalized inverse)을 사용하면 k 보다 큰 (비선형) 방정식의 시스템을 풀기 위해 사용될 수 있습니다. 만약 비선형 시스템(nonlinear system)이 해를 가지지 않으면, 그 방법은 비-선형 최소 제곱(non-linear least squares) 의미에서 해를 찾으려고 시도합니다. 자세한 내용에 대해 가우스-뉴턴 알고리듬(Gauss–Newton algorithm)을 참조하십시오.

In a Banach space

또 다른 일반화는 바나흐 공간(Banach space)에서 정의된 함수형(functional) F의 근을 찾기 위한 뉴턴의 방법입니다. 이 경우에서, 형식화는 다음과 같습니다:

$X_{n+1}=X_{n}-{\bigl (}F'(X_{n}){\bigr )}^{-1}F(X_{n}),\,$

여기서 F′(X_n)은 X_n에서 계산된 프레셰 도함수(Fréchet derivative)입니다. 우리는 그 방법에 대해 적용-가능하도록 되기 위해 프레셰 도함수를 각 X_n에서 경계적으로 역-가능이 됨을 필요로 합니다. 근의 존재와 근으로 수렴에 대한 조건은 뉴턴–칸토로비치 정리(Newton–Kantorovich theorem)에 의해 주어집니다.

Over p-adic numbers

p-진수 해석학에서, p-진수 근을 가지는 하나의 변수에서 다항 방정식을 표시하기 위한 표준 방법은 p-진수 숫자에 대한 뉴턴의 방법에서 재귀를 사용하는 헨젤의 보조정리(Hensel's lemma)입니다. 실수에 비해 p-진수 숫자에서 덧셈과 곱셈의 동작이 더 안정적이기 때문에 (구체적으로, p-진수에서 단위 공은 링입니다), 헨젤의 보조정리에서 수렴은 실수 직선 위에 고전적인 뉴턴의 방법보다 훨씬 간단한 가설 아래에서 보장될 수 있습니다.

Newton–Fourier method

뉴턴–푸리에 방법은 여전히 이차 수렴을 제공하면서 근 근사의 절대 오차에 대한 경계를 제공하기 위한 뉴턴 방법의 조제프 푸리에(Joseph Fourier)의 확장입니다.

f(x)가 [a, b] 위에 두 번 연속적으로 미분-가능이고 f가 이 구간 안에 근을 포함한다고 가정합니다. 이 구간 위에 f′(x), f″(x) ≠ 0임을 가정합니다 (이것은 예를 들어 f(a) < 0, f(b) > 0, 및 f′(x) > 0, 및 이 구간 위에 f″(x) > 0이면 그 경우입니다.) 이것은 이 구간 위에 고유한 근이 있음을 보장하며, 그것을 α로 부릅니다. 만약 그것이 위로 오목하지 않고 아래로 오목하면, f(x)를 −f(x)로 대체하는데 왜냐하면 그것들은 같은 근을 가지지 때문입니다.

x₀ = b를 구간의 오른쪽 끝점으로 놓고 z₀ = a를 구간의 왼쪽 끝점으로 놓습니다. x_n이 주어지면, 다음을 정의합니다:

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

이는 이전과 마찬가지로 바로 뉴턴의 방법입니다. 그런-다음 다음을 정의합니다:

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

여기서 분모는 f′(x_n)이고 f′(z_n)이 아닙니다. 반복 x_n은 근으로 엄격하게 감소할 것이고 반면에 반복 z_n은 근으로 엄격하게 증가할 것입니다. 역시, x_n과 z_n 사이의 거리가 이차적으로 감소하도록, 다음입니다:

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

Quasi-Newton methods

야코비 행렬은 사용될 수 없거나 모든 각 반복에서 계산하기에 비용이 너무 많이 들 때, 준-뉴턴 방법(quasi-Newton method)이 사용될 수 있습니다.

q-analog

뉴턴의 방법은 보통의 도함수의 q-아날로그(q-analog)로 일반화될 수 있습니다.

Modified Newton methods

Maehly's procedure

비-선형 방정식은 일반적으로 여러 해를 가집니다. 그러나 만약 초기 값이 적절하지 않으면, 뉴턴의 방법이 원했던 해로 수렴하지 않거나 이전에 찾은 같은 해로 수렴할 수 있습니다. 우리가 $f(x)=0$의 N개의 해를 이미 찾았으면, 다음 근은 뉴턴의 방법을 다음 방정식에 적용함으로써 찾을 수 있습니다:

$F(x)={\frac {f(x)}{\prod _{i=1}^{N}(x-x_{i})}}=0.$

이 방법은 두 번째 종류의 베셀 함수(Bessel function)의 영들을 얻기 위해 적용됩니다.

Hirano's modified Newton method

Hirano의 수정된 뉴턴 방법은 뉴턴 방법의 수렴성을 유지하고 불안정성을 피하는 수정입니다. 그것은 복소 다항식을 풀기 위해 개발되었습니다.

Interval Newton's method

뉴턴의 방법을 구간 산술(interval arithmetic)과 결합하면 일부 상황에서 매우 유용합니다. 이것은 보통 것보다 더 신뢰할 수 있는 중지 기준을 제공합니다 (이는 작은 함수 값 또는 연속 반복 사이의 변수의 작은 변형입니다). 역시, 이것은 뉴턴의 방법이 이론적으로는 수렴하지만 불충분한 부동-점 정밀도로 인해 수치적으로 발산하는 경우를 감지할 수 있습니다(이것은 전형적으로 변수의 아주 작은 변화가 함수의 값을 크게 변경할 수 있는 큰 차수의 다항식에 대한 경우입니다; 윌킨슨의 다항식(Wilkinson's polynomial)을 참조하십시오).

X가 실수 구간인 f → C¹(X)를 생각해 보십시오, 그리고 f′의 구간 확장 F′를 가진다고 가정하며, F′이 구간 Y ⊆ X를 입력으로 취하고 다음을 만족하는 구간 F′(Y)를 출력을 취함을 의미합니다:

${\begin{aligned}F'([y,y])&=\{f'(y)\}\\[5pt]F'(Y)&\supseteq \{f'(y)\mid y\in Y\}.\end{aligned}}$

우리는 역시 0 ∉ F′(X)임을 가정하므로, 특히 f는 X에서 많아야 하나의 근을 가집니다. 그런-다음 구간 뉴턴 연산자를 다음과 같이 정의합니다:

$N(Y)=m-{\frac {f(m)}{F'(Y)}}=\left\{\left.m-{\frac {f(m)}{z}}~\right|~z\in F'(Y)\right\}$

여기서 m ∈ Y입니다. F′에 대한 가설은 N(Y)가 잘 정의되어 있고 구간이라는 것을 의미함을 주목하십시오 (구간 연산에 대한 자세한 내용에 대해 구간 산술(interval arithmetic)을 참조하십시오). 이것은 자연스럽게 다음과 같은 수열로 이어집니다:

${\begin{aligned}X_{0}&=X\\X_{k+1}&=N(X_{k})\cap X_{k}.\end{aligned}}$

평균값 정리(mean value theorem)는 X_k에서 f의 근이 있으면, 근이 X_{k + 1}에도 있음을 보장합니다. 더욱이, F′에 대한 가설은 m이 Y의 중간 점일 때 X_{k + 1}이 많아야 X_k의 크기의 절반임을 보장하므로, 이 수열은 [x*, x*] 쪽으로 수렴하며, 여기서 x*는 X에서 f의 근입니다.

만약 F′(X)가 엄격하게 0을 포함하면, 확장된 구간 나누기의 사용은 N(X)에 대한 두 구간의 합집합을 생성합니다; 중복 근은 따라서 자동적으로 분리되고 경계진 것입니다.

Applications

Minimization and maximization problems

Main article: Newton's method in optimization

뉴턴의 방법은 함수 f(x)의 최솟값 또는 최댓값을 찾기 위해 사용될 수 있습니다. 도함수는 최소 또는 최대에서 영이므로, 지역적 최솟값과 최댓값은 도함수에 뉴턴의 방법을 적용함으로써 찾을 수 있습니다. 반복은 다음이 됩니다:

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

Multiplicative inverses of numbers and power series

중요한 응용은 뉴턴–랍선 나눗셈(Newton–Raphson division)이며, 이는 곱셈과 뺄셈만 사용하여 숫자 a의 역수(reciprocal), 즉, 1/x = a를 만족하는 숫자 x를 빠르게 찾기 위해 사용될 수 있습니다. 우리는 그것을 f(x) = 1/x − a의 영을 찾는 것으로 바꿔 말할 수 있습니다. 우리는 f′(x) = −1/x²를 가집니다.

뉴턴의 반복은 다음입니다:

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}+{\frac {{\frac {1}{x_{n}}}-a}{\frac {1}{x_{n}^{2}}}}=x_{n}(2-ax_{n}).$

그러므로, 뉴턴의 반복은 곱셈 두 번과 뺄셈 한 번만 필요합니다.

이 방법은 거듭제곱 급수(power series)의 덧셈의 역을 계산하는 데에도 매우 효율적입니다.

Solving transcendental equations

많은 초월적인 방정식(transcendental equations)은 뉴턴의 방법을 사용하여 풀 수 있습니다. 다음 방정식이 주어졌을 때,

$g(x)=h(x),$

이때 g(x) 및/또는 h(x)는 초월적인 함수(transcendental function)이며, 다음을 씁니다:

$f(x)=g(x)-h(x).$

원래 방정식을 푸는 x의 값은 그런-다음 f(x)의 근이며, 이는 뉴턴의 방법을 통해 찾을 수 있습니다.

Obtaining zeros of special functions

뉴턴의 방법은 베셀 함수의 비율에 그 근을 얻기 위해 적용됩니다.

Numerical verification for solutions of nonlinear equations

비-선형 방정식의 해에 대한 수치적 검증은 뉴턴의 방법을 여러 번 사용하고 해 후보 집합을 형성함으로써 확립되었습니다.

Examples

Square root

숫자 a의 제곱근, 즉, x² = a임을 만족하는 양수 x를 찾는 문제를 생각해 보십시오. 뉴턴의 방법은 제곱근을 계산하는 많은 방법 중 하나입니다. 우리는 그것을 f(x) = x² − a의 영을 찾는 것으로 바꿔 말할 수 있습니다. 우리는 f′(x) = 2x를 가집니다.

예를 들어, 초기 추측 x₀ = 10을 갖는 612의 제곱근을 찾기 위해, 뉴턴의 방법으로 주어진 수열은 다음과 같습니다:

${\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&10-{\dfrac {10^{2}-612}{2\times 10}}&=&35.6\qquad \qquad \qquad \quad \;\,{}\\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&35.6-{\dfrac {35.6^{2}-612}{2\times 35.6}}&=&{\underline {2}}6.395\,505\,617\,978\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {24.7}}90\,635\,492\,455\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {24.738\,6}}88\,294\,075\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {24.738\,633\,753\,7}}67\dots \end{matrix}}$

여기서 올바른 자릿수는 밑줄이 그어져 있습니다. 우리는 몇 번의 반복만으로 많은 십진 자릿수까지 정확한 해를 얻을 수 있습니다.

공식을 다음과 같이 재배열하면 제곱근을 찾는 바빌로니아 방법을 산출합니다:

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {x_{n}^{2}-a}{2x_{n}}}={\frac {1}{2}}{\biggl (}2x_{n}-{\Bigl (}x_{n}-{\frac {a}{x_{n}}}{\Bigr )}{\biggr )}={\frac {1}{2}}{\Bigl (}x_{n}+{\frac {a}{x_{n}}}{\Bigr )}$

즉, 추측 x_n과 a/x_n의 산술 평균(arithmetic mean)입니다.

Solution of cos(x) = x³

${\textstyle \cos x=x^{3}}$와 함께 양수 ${\textstyle x}$를 찾는 문제를 생각해 보십시오. 우리는 ${\textstyle f(x)=\cos(x)-x^{3}}$의 영을 찾는 것으로 바꿔 말할 수 있습니다. 우리는 ${\textstyle f'(x)=-\sin(x)-3x^{2}}$를 가집니다. 모든 ${\textstyle x}$에 대해 ${\textstyle \cos(x)\leq 1}$이고 ${\textstyle x>1}$에 대해 ${\textstyle x^{3}>1}$이므로, 해가 0과 1 사이에 있음을 알고 있습니다.

예를 들어, 초기 추측 x₀ = 0.5와 함께, 뉴턴의 방법에 의해 주어진 수열은 다음과 같습니다 (0의 시작하는 값은 정의되지 않은 결과로 이어질 것이며, 해에 가까운 시작하는 점을 사용하는 것의 중요성을 보여줌을 주목하십시오):

${\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&0.5-{\dfrac {\cos 0.5-0.5^{3}}{-\sin 0.5-3\times 0.5^{2}}}&=&1.112\,141\,637\,097\dots \\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&\vdots &=&{\underline {0.}}909\,672\,693\,736\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {0.86}}7\,263\,818\,209\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {0.865\,47}}7\,135\,298\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {0.865\,474\,033\,1}}11\dots \\x_{6}&=&\vdots &=&\vdots &=&{\underline {0.865\,474\,033\,102}}\dots \end{matrix}}$

올바른 자릿수는 위의 예에서 밑줄이 그어져 있습니다. 특히, x₆는 12 십진 위치까지 정확합니다. 우리는 십진 점 뒤의 올바른 자릿수가 2 (x₃에 대해)에서 5와 10으로 증가하여, 이차 수렴을 설명함을 알 수 있습니다.

Code

다음은 도함수 f_prime을 가지는 함수 f의 근을 찾기 위한 Python (버전 3.x) 프로그래밍 언어의 뉴턴의 방법의 구현 예제입니다.

초기 추측은 x₀ = 1이고 함수는 f′(x) = 2x가 되도록 f(x) = x² − 2가 될 것입니다.

뉴턴의 방법의 각각의 새로운 반복은 x1으로 표시될 것입니다. 우리는 계산 중에 분모 (yprime)가 너무 작아지는지(epsilon보다 작은지) 확인할 것이며, 이는 f′(x_n) ≈ 0인 경우에 해당하는데, 왜냐하면 그렇지 않으면 많은 양의 오차가 발생할 수 있기 때문입니다.

def f(x):             
	return x**2 - 2   # f(x) = x^2 - 2

def f_prime(x):
	return 2*x        # f'(x) = 2x

def newtons_method(
    x0,               # The initial guess
    f,                # The function whose root we are trying to find
    f_prime,          # The derivative of the function
    tolerance,        # 7-digit accuracy is desired
    epsilon,          # Do not divide by a number smaller than this
    max_iterations,   # The maximum number of iterations to execute
    ):
    for i in range(max_iterations):
        y = f(x0)
        yprime = f_prime(x0)

        if abs(yprime) < epsilon:       # Stop if the denominator is too small
            break

        x1 = x0 - y / yprime            # Do Newton's computation

        if abs(x1 - x0) <= tolerance:   # Stop when the result is within the desired tolerance
            return x1                   # x1 is a solution within tolerance and maximum number of iterations

        x0 = x1                         # Update x0 to start the process again

    return None                         # Newton's method did not converge

See also

• Aitken's delta-squared process
• Bisection method
• Euler method
• Fast inverse square root
• Fisher scoring
• Gradient descent
• Integer square root
• Kantorovich theorem
• Laguerre's method
• Methods of computing square roots
• Newton's method in optimization
• Richardson extrapolation
• Root-finding algorithm
• Secant method
• Steffensen's method
• Subgradient method

References

• Gil, A.; Segura, J.; Temme, N. M. (2007). Numerical methods for special functions. Society for Industrial and Applied Mathematics. ISBN 978-0-89871-634-4.
• Süli, Endre; Mayers, David (2003). An Introduction to Numerical Analysis. Cambridge University Press. ISBN 0-521-00794-1.

Further reading

• Kendall E. Atkinson, An Introduction to Numerical Analysis, (1989) John Wiley & Sons, Inc, ISBN 0-471-62489-6
• Tjalling J. Ypma, Historical development of the Newton–Raphson method, SIAM Review 37 (4), 531–551, 1995. doi:10.1137/1037125.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. MR 2265882.
• P. Deuflhard, Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms. Springer Series in Computational Mathematics, Vol. 35. Springer, Berlin, 2004. ISBN 3-540-21099-7.
• C. T. Kelley, Solving Nonlinear Equations with Newton's Method, no 1 in Fundamentals of Algorithms, SIAM, 2003. ISBN 0-89871-546-6.
• J. M. Ortega, W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables. Classics in Applied Mathematics, SIAM, 2000. ISBN 0-89871-461-3.
• Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). "Chapter 9. Root Finding and Nonlinear Sets of Equations Importance Sampling". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.. See especially Sections 9.4, 9.6, and 9.7.
• Avriel, Mordecai (1976). Nonlinear Programming: Analysis and Methods. Prentice Hall. pp. 216–221. ISBN 0-13-623603-0.

External links

• "Newton method", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Weisstein, Eric W. "Newton's Method". MathWorld.
• Newton's method, Citizendium.
• Mathews, J., The Accelerated and Modified Newton Methods, Course notes.
• Wu, X., Roots of Equations, Course notes.