뉴턴의 방법

수치 분석에서 뉴턴의 방법은 아이작 뉴턴과 조셉 래프슨의 이름을 따서 뉴턴-래프슨 방법으로도 알려져 있으며, 실제 값 함수의 근(또는 0)에 대해 연속적으로 더 나은 근사치를 생성하는 근 찾기 알고리즘입니다. 가장 기본적인 버전은 실수 함수 f와 그것의 도함수 f', 그리고 근 off에 대한 초기 추측으로 시작합니다. f 가 특정 가정을 만족하고 초기 추측이 근접하다면,

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

는 보다 근의 근사치를 더 잘 나타냅니다. 기하학적으로 (,x₁ 0)은 fat 그래프의 접선의 x절편입니다.x₀x₀ 즉, 개선된 추측은 초기 추측에서 f 의 선형 근사치의 고유한 근입니다. 이 과정은 다음과 같이 반복됩니다.

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

충분히 정확한 값에 도달할 때까지. 정확한 숫자는 각 단계에 따라 대략 두 배로 늘어납니다. 이 알고리즘은 Householder's methods의 클래스에서 처음이며, Halley's method가 그 뒤를 이습니다. 이 방법은 복잡한 함수와 방정식 체계로도 확장될 수 있습니다.

묘사

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

=에서 곡선()의 접선이 x축을 가로채면 기울기는

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

포기를 위한 해결

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

임의의 초기값 x로 과정을₀ 시작합니다. (0에 가까울수록 좋습니다. 그러나 0이 어디에 놓일지에 대한 직관이 없는 경우, "추측 및 점검" 방법은 중간값 정리에 호소함으로써 가능성을 비교적 작은 간격으로 좁힐 수 있습니다. 이 초기 추측이 미지의 0에 충분히 가깝고 () ≠ 0인 경우 이 방법은 일반적으로 수렴됩니다. 또한 다중성 1의 0에 대해 수렴은 0 근처에서 적어도 2차적입니다(수렴 속도 참조). 이는 직관적으로 정확한 자릿수의 수가 모든 단계에서 대략 두 배로 증가한다는 것을 의미합니다. 보다 자세한 내용은 아래 § 애널리시스에서 확인하실 수 있습니다.

가구주의 방법은 비슷하지만 훨씬 더 빠른 수렴을 위해 더 높은 순서를 가지고 있습니다. 그러나 각 단계에 필요한 추가 계산은 특히 도함수에 대한 계산 비용이 높은 경우 뉴턴 방법에 비해 전체 성능을 저하시킬 수 있습니다.

역사

"뉴턴의 방법"이라는 이름은 아이작 뉴턴(Isaac Newton)이 디 분석 방정식(De analysis es numero terminorum infinitas, 1669년 작성, 1711년 윌리엄 존스 발표)과 디 메토디스 플럭시오눔 에 세리에룸 인피니타룸(De metodis fluxionum et serierum infinitarum, 1671년 작성)에서 이 방법의 특별한 경우를 기술한 데서 유래했습니다. 존 콜슨(John Colson)에 의해 1736년에 플럭스의 방법(Method of Fluxion)으로 번역되어 출판되었습니다. 그러나 그의 방법은 위에서 제시한 현대의 방법과 상당히 다릅니다. 뉴턴은 이 방법을 다항식에만 적용했는데, 초기 근 추정에서 시작하여 오류 수정 순서를 추출했습니다. 그는 각각의 수정을 사용하여 다항식을 남은 오차의 관점에서 다시 쓴 다음, 고차항을 무시함으로써 새로운 수정을 해결했습니다. 그는 방법을 도함수와 명시적으로 연결하거나 일반적인 공식을 제시하지 않았습니다. 뉴턴은 이 방법을 수적 문제와 대수적 문제 모두에 적용하여 후자의 경우 테일러 급수를 만들어냈습니다.

뉴턴은 그의 방법을 비에타의 유사하고 덜 정확한 방법에서 유도했을지도 모릅니다. 비에타의 방법의 본질은 페르시아 수학자 샤라프 알딘 알투시의 연구에서 찾을 수 있으며, 그의 후계자 잠시 ī드 알카시 ī는 뉴턴의 방법을 사용하여 - = 0을 N의 근을 구했습니다(Ypma 1995). 뉴턴의 제곱근을 계산하는 방법의 특별한 경우는 예로부터 알려져 있었고 종종 바빌로니아 방법이라고 불립니다.

뉴턴의 방법은 17세기 일본 수학자 고와 세키가 단변수 방정식을 풀 때 사용했지만 미적분학과의 연관성은 없었습니다.^[1]

뉴턴의 방법은 1685년 존 월리스에 의해 역사적이고 실용적인 대수학 논문으로 처음 출판되었습니다.^[2] 1690년에 조셉 라프슨은 Analysis a equationum universalis에 간단한 설명을 발표했습니다.^[3] 또한 라프슨은 다항식에만 이 방법을 적용했지만, 원래 다항식에서 연속적인 수정을 한 번씩 추출함으로써 뉴턴의 지루한 다시 쓰기 과정을 피했습니다. 이를 통해 그는 각 문제에 대해 재사용 가능한 반복 표현식을 도출할 수 있었습니다. 마침내 1740년 토마스 심슨은 뉴턴의 방법을 미적분학을 이용한 일반적인 비선형 방정식을 푸는 반복적인 방법으로 설명했고, 기본적으로 위와 같은 설명을 했습니다. 같은 출판물에서 심슨은 또한 두 방정식의 시스템에 일반화를 제공하며 뉴턴의 방법은 기울기를 0으로 설정함으로써 최적화 문제를 해결하는 데 사용될 수 있다고 언급합니다.

1879년 뉴턴에서 아서 케일리가푸리에 허수 문제는 뉴턴의 방법을 차수가 2보다 크고 복소 초기값을 갖는 다항식의 복소근으로 일반화하는 데 어려움을 처음으로 알아차렸습니다. 이로써 유리함수의 반복 이론에 대한 연구의 길이 열렸습니다.

실용적 고려사항

뉴턴의 방법은 강력한 방법입니다. 일반적으로 수렴은 이차적입니다. 방법이 뿌리에 수렴할 때 뿌리와 근사치 사이의 차이는 각 단계에서 제곱됩니다(정확한 자릿수는 대략 두 배). 그러나 방법에 몇 가지 어려움이 있습니다.

함수의 도함수를 계산하는 데 어려움

뉴턴의 방법은 도함수를 직접 계산할 수 있어야 합니다. 도함수에 대한 분석식은 쉽게 구할 수 없거나 평가 비용이 많이 들 수 있습니다. 이러한 상황에서는 함수에서 두 개의 가까운 점을 통과하는 선의 기울기를 사용하여 도함수를 근사하는 것이 적절할 수 있습니다. 이 근사를 사용하면 수렴 속도가 뉴턴의 방법보다 느린 챈트 방법과 같은 결과를 얻을 수 있습니다.

메서드가 루트에 수렴하지 못함

구현하기 전에 뉴턴 방법의 2차 수렴 증명을 검토하는 것이 중요합니다. 구체적으로 증명에서 가정한 사항을 검토해야 합니다. 방법이 수렴되지 않는 상황의 경우, 이 증명에서 가정한 가정이 충족되지 않기 때문입니다.

오버슈트

첫 번째 도함수가 특정 루트 근처에서 잘 동작하지 않으면 메서드가 오버슈트되어 해당 루트에서 분기될 수 있습니다. 근의 근방에서 도함수가 잘 작용하지 않는 근이 하나인 함수의 예는 다음과 같습니다.

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

이 경우 루트가 오버샷되고 x의 시퀀스가 발산됩니다. = 1/2의 경우 루트는 여전히 오버샷되지만 시퀀스는 두 값 사이에서 진동합니다. 1/2 < < 1의 경우 루트는 여전히 오버샷되지만 시퀀스는 수렴되며 ≥ 1의 경우 루트는 오버샷되지 않습니다.

경우에 따라서는 연속적인 과완화를 사용하여 뉴턴의 방법을 안정화시킬 수도 있고, 같은 방법을 사용하여 수렴 속도를 높일 수도 있습니다.

정지점

함수의 정지점이 발생하면 도함수는 0이고 메소드는 0으로 나눗셈되어 종료됩니다.

초기 견적 불량

초기 추정치의 큰 오차는 알고리즘의 비수렴에 기여할 수 있습니다. 이 문제를 극복하기 위해 미적분학, 로그, 미분을 사용하거나 심지어 확률적 터널링과 같은 진화 알고리즘을 사용하여 최적화 중인 함수를 선형화할 수 있습니다. 양호한 초기 추정치는 최종 전역 최적 모수 추정치에 근접합니다. 비선형 회귀 분석에서 제곱 오차의 합(SSE)은 최종 모수 추정치 영역에서 "가까운" 포물선에 불과합니다. 여기서 발견된 초기 추정치를 사용하면 뉴턴-랩슨 방법을 빠르게 수렴할 수 있습니다. SSE의 헤센 행렬이 양수이고 SSE의 1차 도함수가 0에 가깝다는 것은 여기에만 있습니다.

비수렴 완화

뉴턴 방법의 강력한 구현에서는 반복 횟수에 제한을 두고 해를 근을 포함하는 것으로 알려진 간격으로 묶고 방법을 보다 강력한 근 찾기 방법과 결합하는 것이 일반적입니다.

다중도가 1보다 큰 근에 대한 느린 수렴

찾는 루트의 다중도가 1보다 크면 특별한 조치를 취하지 않는 한 수렴 속도는 선형(각 단계에서 상수 요인에 의해 감소된 오차)에 불과합니다. 두 개 이상의 근들이 서로 가까이 있을 때, 2차 수렴이 명확해질 때까지 반복이 많이 필요할 수 있습니다. 그러나 근의 다중도 m을 알면 다음과 같이 수정된 알고리즘이 2차 수렴률을 보존합니다.^[4]

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

이는 연속적인 과잉 완화를 사용하는 것과 같습니다. 반면, 근의 다중도 m을 알 수 없는 경우 한두 번의 반복을 수행한 후 m을 추정한 후 그 값을 사용하여 수렴 속도를 높일 수 있습니다.

근의 다중도 m이 유한하면 () = ()/()는 다중도 1과 같은 위치에 근을 갖습니다. ()x의 근을 찾기 위해 뉴턴의 방법을 적용하면 일반적으로 ()x의 2차 도함수를 포함하지만 많은 경우에 2차 수렴을 회복합니다. 특히 단순한 경우, 만약 () = 그렇다면 () = / 그리고 뉴턴의 방법은 다음과 같은 한 번의 반복에서 근을 찾습니다.

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

분석.

함수 f가 α에서 0, 즉 () = 0이고, f가 α 근방에서 미분 가능하다고 가정하자.

f가 연속적으로 미분 가능하고 그 도함수가 α에서 0이 아닌 경우, 그 이웃에 있는 모든 시작 값에 대해 수열()x_n이 α로 수렴하도록 α의 이웃이 존재합니다.^[5]

만약 f가 연속적으로 미분 가능하다면, 그 도함수는 α에서 0이 아니고, 그것이 α에서 2차 도함수를 가지면, 수렴은 2차 이상입니다. 2차 도함수가 α에서 0이 아니면 수렴은 단지 2차적입니다. 3차 도함수가 존재하고 α 근방에 경계를 이루면 다음과 같습니다.

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

어디에

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

도함수가 α에서 0이면 수렴은 일반적으로 선형입니다. 구체적으로 f가 연속적으로 미분 가능한 () = 0 및 () ≠ 0의 두 배인 경우 α의 이웃이 존재하여 해당 이웃의 모든 시작 값에 대해 반복률의 시퀀스가 1/2 비율로 선형적으로 수렴합니다. 또는 () = 0 및 () ≠가 ≠일 경우, α의 근방 U에 x가 있고, α는 곱셈 r의 0이 되며, () ∈일 경우, α의 근방이 존재하여, 그 근방에 있는 모든 시작 값에 대하여 반복되는 수열이 선형적으로 수렴됩니다.

그러나 병리적 상황에서는 선형 수렴조차 보장되지 않습니다.

실질적으로 이러한 결과는 국지적이며, 수렴의 근접성은 사전에 알 수 없습니다. 그러나 전역 수렴에 대한 몇 가지 결과도 있습니다: 예를 들어, α의 오른쪽 이웃이 주어지면 f가 에서 2배 미분 가능하고 ≠가 0, · > 0인 경우 순서의 각각이 α로 단조적으로 감소합니다.

뉴턴의 반복법에 대한 2차 수렴 증명

테일러의 정리에 따르면 연속적인 2차 도함수를 갖는 함수()x는 근에 가까운 점에 대한 전개로 나타낼 수 있습니다.x 이 근을 α라고 가정해 보겠습니다. 그렇다면 ()α의 전개는 다음과 같습니다.

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

(1)

여기서 테일러 급수 전개 잔량의 라그랑주 형태는

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

여기서 는 α와 사이에 있습니다.

α는 근이므로 (1)은 다음과 같습니다.

${\displaystyle 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)를 ()x_n로 나누고 정리하면 다음과 같습니다.

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

다음에 의해 정의된 것을 기억하기

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

(4)

라고 생각합니다.

$${\displaystyle \underbrace {\alpha-x_{n+1}}_{\varepsilon_{n+1}}={\frac {-f"(\xi_{n})}{2f'(x_{n})}{(\,\underbrace {\alpha-x_{n}}_{\varepsilon_{n}\,)}^{2}\,}$$

그것은,

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

(5)

양쪽의 절대값을 취하는 것은

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

(6)

식 (6)은 다음 조건을 만족할 경우 수렴 순서가 적어도 2차적임을 보여줍니다.

1. () ≠ 0; 모든 ∈에 대해, 여기서 I는 간격 [ - , + ];
2. ()는 모든 ∈에 대해 연속입니다.
3. M ε₀ < 1

여기서 M은

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

이런 조건이 지속된다면,

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

인력의 분지

인력 기저들의 서로소 부분집합들, 즉 임의의 점으로부터 반복되는 각 영역 내에서 하나의 특정한 근으로 이어지는 실수선의 영역들은 수가 무한하고 임의로 작을 수 있습니다. 예를 들어, 함수() = - 2 - 11 + 12 = ( - 4) ( - 1) ( + 3)의 경우 다음과 같은 초기 조건이 연속적인 인력 기저에 있습니다.

고장분석

뉴턴의 방법은 어떤 조건이 충족될 때에만 수렴이 보장됩니다. 2차 수렴 증명에서 이루어진 가정을 충족하면 방법이 수렴하게 됩니다. 다음 하위 섹션의 경우 수렴 방법이 실패하면 증명에서 가정한 가정이 충족되지 않았음을 나타냅니다.

출발점 불량

수렴에 필요한 함수의 조건을 만족하는 경우도 있지만, 초기 점으로 선택한 점은 방법이 수렴하는 구간에 있지 않습니다. 예를 들어, x가 ∞ 또는 - ∞로 이동함에 따라 근을 찾는 함수가 0에 가까워지면 이러한 일이 발생할 수 있습니다. 이러한 경우 0을 초기점으로 사용하기 위해 더 나은 추정치를 얻기 위해 이등분과 같은 다른 방법을 사용해야 합니다.

반복점이 정지 상태임

함수를 생각해 보십시오.

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

최대 = 0이고 = ±1에서 () = 0의 해를 갖습니다. (0, 1)의 접선이 x축과 평행하므로 정지점 = 0(도함수가 0인 경우)부터 반복하면 정의되지 않습니다.

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

시작점이 아닌 어떤 반복점이 정지한 경우에도 동일한 문제가 발생합니다. 도함수가 작지만 0이 아니더라도 다음 반복은 훨씬 더 나쁜 근사치가 될 것입니다.

시작점이 사이클에 진입함

일부 함수의 경우 일부 시작점이 무한 순환에 진입하여 수렴을 방지할 수 있습니다. 허락하다

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

0을 시작점으로 삼습니다. 첫 번째 반복은 1을 생성하고 두 번째 반복은 0으로 돌아가므로 순서는 루트로 수렴되지 않고 둘 사이에서 교대로 이루어집니다. 사실, 이 2-사이클은 안정적입니다. 0과 1 주변에는 모든 지점이 2-사이클로 점근적으로 반복되는 이웃이 있습니다(따라서 함수의 루트가 아닙니다). 일반적으로 수열의 거동은 매우 복잡할 수 있습니다(뉴턴 프랙탈 참조). 이 방정식의 실제 해는 -1.76929235...

파생상품이슈

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

근에 도함수가 존재하지 않습니다.

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

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

모든 반복점에 대해 다음 반복점은 다음과 같습니다.

$${\displaystyle 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인 모든 () =에 대해 무한대로 발산됩니다. = 1/2(제곱근)인 한계의 경우, 반복은 점과 - 사이에서 무한히 교대하므로 이 경우에도 수렴하지 않습니다.

불연속 도함수

도함수가 근에서 연속적이지 않으면 근의 어떤 이웃에서도 수렴이 실패할 수 있습니다. 함수를 고려합니다.

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

파생 제품은 다음과 같습니다.

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

이 도함수는 x가 오른쪽(또는 왼쪽)에서 0에 접근하는 반면, 0 < 1의 경우 () ≥ - > 0에 접근함에 따라 부호가 계속 바뀝니다.

따라서 ()/()xf′x는 근 근처에서 무한대로 존재하며, 뉴턴의 방법은 다음과 같이 하더라도 근 근처의 거의 모든 곳에서 발산할 것입니다.

• 기능은 어디에서나 구별 가능합니다(따라서 연속적입니다).
• 근의 도함수는 0이 아닙니다.
• f는 뿌리를 제외하고는 무한히 미분 가능합니다.
• 도함수는 근의 근방(unlike()/())에 경계지어집니다.

비사차 수렴

어떤 경우에는 반복 속도가 수렴하지만 약속한 만큼 빠르게 수렴하지 않습니다. 이러한 경우에는 뉴턴의 방법처럼 더 간단한 방법이 빠르게 수렴합니다.

도함수 0

근에서 1차 도함수가 0이면 수렴은 2차적이지 않습니다. 허락하다

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

그러면 () = 2 그리고 결과적으로

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

따라서 수렴은 2차적이지 않습니다. 함수가 어디에서나 무한히 미분할 수 있지만 말입니다.

루트가 "거의" 두 배에 불과할 때도 비슷한 문제가 발생합니다. 예를 들어, 다음과 같이.

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

그렇다면 = 1에서 시작하는 처음 몇 번의 반복은 다음과 같습니다.

수렴이 2차적으로 보이는 지점에 도달하기 위해서는 여섯 번의 반복이 필요합니다.

2차 도함수 없음

근에 2차 도함수가 없으면 수렴이 2차적이지 않을 수 있습니다. 허락하다

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

그리고나서

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

그리고.

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

= 0인 경우를 제외하고는 정의되지 않습니다. 주어진,

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

약 4/3 비트의 정밀도를 가지고 있습니다. 이는 2차 수렴에 필요한 개수의 2배 미만입니다. 따라서 뉴턴의 방법(이 경우)의 수렴은 이차적이지 않습니다. 함수는 어디에서나 연속적으로 미분할 수 있고, 도함수는 근에서 0이 아니며, f는 원하는 근을 제외하고는 무한히 미분할 수 있습니다.

일반화

복소함수

복잡한 함수를 다룰 때 뉴턴의 방법을 직접 적용하여 0을 찾을 수 있습니다.^[8] 각 영점에는 복소평면의 인력 유역이 있는데, 이는 메소드가 특정 영점으로 수렴하도록 하는 모든 시작 값의 집합입니다. 이러한 세트는 표시된 이미지와 같이 매핑할 수 있습니다. 많은 복잡한 함수에서 인력의 기저의 경계는 프랙탈입니다.

어떤 경우에는 복소 평면에 이러한 인력의 기저에 없는 영역이 존재하므로 반복률이 수렴되지 않습니다. 예를 들어,^[9] 실제 초기 조건을 사용하여 + 1의 근을 구하는 경우, 모든 후속 반복은 실수가 되므로 두 근 모두 비실수이므로 반복은 어느 루트에도 수렴할 수 없습니다. 이 경우 거의 모든 실제 초기 조건은 혼돈 행동으로 이어지는 반면, 일부 초기 조건은 무한대 또는 유한 길이의 반복 사이클로 반복됩니다.

커트 맥멀런은 뉴턴의 방법과 유사한 순수 반복 알고리즘이 가능한 경우 4도 이상의 다항식에 적용될 때 알고리즘이 복소 평면의 일부 열린 영역에서 발산한다는 것을 보여주었습니다. 그러나 McMullen은 3차 다항식에 대해 일반적으로 수렴하는 알고리즘을 제시했습니다.^[10] 또한 어떤 다항식에 대해서도 허버드, 슐라이허, 서덜랜드는 뉴턴의 방법이 적어도 그 중 하나에서 수렴할 수 있도록 초기점들의 집합을 선택하는 방법을 제시했습니다.^[11]

체비셰프의 삼차법

이 섹션은 비어 있습니다. 추가하여 도움을 드릴 수 있습니다. (2019년 2월)

내쉬-모저 반복

이 섹션은 비어 있습니다. 추가하여 도움을 드릴 수 있습니다. (2019년 2월)

연립방정식

이 기사는 검증을 위해 추가 인용이 필요합니다. 신뢰할 수 있는 출처에 인용을 추가하여 이 기사를 개선하는 데 도움을 주세요. 출처가 없는 재료는 문제가 발생하여 제거될 수 있습니다. 출처 찾기 : "Newton's method" – 뉴스 · 신문 · 서적 · 학자 · JSTOR (2023년 1월) (본 템플릿 메시지 제거 방법 및 시기에 대해 알아보기)

k개의 변수, k개의 함수

연속 미분 가능한 함수 $f{\displaystyle :}$ R ${\displaystyle {}^{}}$의 ( simultane) 영점을 찾는 것과 같은 k 방정식 체계를 푸는 데 뉴턴의 방법을 사용할 수도 있습니다. ${\displaystyle {}^{}}$ → ${\displaystyle R}$.$${\displaystyle f:\mathbb {${\displaystyle R^{}}$} ^{${\displaystyle {}^{}}$}\to \mathbb {R}.} 이는 단일 벡터 값 함수 F: R k → R k의 영점을 찾는 것과 같습니다${\displaystyle .}$${\displaystyle F:\mathbb {R} ^{k}\to \mathbb {R} ^{k}}$ 위의 공식에서$$ 스칼라 x는_n 벡터 x로_n 대체되며 함수 ()x_n를 도함수 ()x_n로 나누는 대신 함수 (x_n)에 x 야코비안 행렬 (x_n)의 역수를 곱해야 합니다. 결과적으로 다음과 같은 식이 됩니다.

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

실제로 야코비안 행렬의 역산을 계산하는 것보다, 선형 방정식 체계를 풀어서 시간을 절약하고 수치 안정성을 높일 수 있습니다.

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

알_{n + 1} 수 없는 x - x 에_n 대하여.

k개 변수, m개 방정식, > 포함

알고리즘이 J의 역수 대신 비제곱 야코비안 행렬 = ()의 일반화된 역수를 사용하는 경우에도 뉴턴 방법의 k차원 변형을 사용하여 k(nonlinear)보다 큰 방정식의 시스템을 해결할 수 있습니다. 비선형 시스템에 해가 없으면, 이 방법은 비선형 최소 제곱의 의미에서 해를 찾으려고 시도합니다. 자세한 내용은 가우스-뉴턴 알고리즘을 참조하십시오.

바나흐 공간에서

또 다른 일반화는 바나흐 공간에서 정의된 함수 F의 근을 찾는 뉴턴의 방법입니다. 이 경우 공식은

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

여기서 ()X_n는 에서 계산된 프레셰 도함수입니다. 방법을 적용하려면 각각의 프레셰 도함수가 경계적으로 가역적이어야 합니다. 뉴턴-칸토로비치 정리는 근의 존재와 수렴 조건을 제시합니다.^[12]

p-adic number 이상

p-adic 분석에서 한 변수에 다항식을 나타내는 표준 방법은 p-adic 근을 갖는 헨젤 보조정리로, p-adic 숫자에 대한 뉴턴 방법의 재귀를 사용합니다. 실수에 비해 p-아딕 수에서 덧셈과 곱셈의 더 안정적인 거동(특히 p-아딕의 단위 공은 고리) 때문에 헨젤 보조정리의 수렴은 실수선에 대한 고전적인 뉴턴의 방법보다 훨씬 간단한 가설에서 보장될 수 있습니다.

뉴턴-푸리에법

뉴턴-푸리에 방법은 근 근사의 절대 오차에 대한 경계를 제공하는 동시에 2차 수렴을 제공하기 위해 조지프 푸리에가 뉴턴 방법을 확장한 것입니다.

()x는 [,a ]에서 연속적으로 미분할 수 있고 f는 이 구간에서 근을 포함한다고 가정합니다. ()를 이 간격에서 ≠ 0이라고 가정합니다(예를 들어 () < 0, () > 0, () > 0인 경우, () > 0인 경우). 이것은 이 구간에 고유한 근이 있다는 것을 보장합니다. 이것을 α라고 부릅니다. 위로 오목한 것이 아니라 아래로 오목한 경우 뿌리가 같으므로 ()x를 f-()x로 교체합니다.

=를 구간의 오른쪽 끝점이라고 하고 =를 구간의 왼쪽 끝점이라고 합니다. 주어진, 정의

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

여기서 분모는 ()x_n이고 ()z_n가 아닙니다. 반복은 루트까지 엄격하게 감소하고 반복은 루트까지 엄격하게 증가합니다. 또한.

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

와 사이의 거리가 2차적으로 줄어들도록 말입니다.

준뉴턴법

Jacobian을 사용할 수 없거나 너무 비싸서 모든 반복에서 계산할 수 없을 때 준-뉴턴 방법을 사용할 수 있습니다.

q-

뉴턴의 방법은 일반적인 도함수의 q-아날로그로 일반화할 수 있습니다.^[13]

수정된 뉴턴 방법

매클리 수속

비선형 방정식은 일반적으로 여러 해를 갖습니다. 그러나 초기값이 적절하지 않을 경우 뉴턴의 방법은 원하는 해로 수렴하지 않거나 앞서 발견한 해와 같은 해로 수렴할 수 있습니다. ${\displaystyle \mathrm{f}(x)}$ = 0 ${\$displaystyle f(x) = 0} 의 N개의 해를 이미 구했을 때, 다음 방정식에 뉴턴 방법을 적용하면 다음 근을 구할 수 있습니다.

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

이 방법은 두 번째 종류의 베셀 함수의 0을 얻기 위해 적용됩니다.^[16]

히라노의 변형 뉴턴 방법

히라노의 수정된 뉴턴 방법은 뉴턴 방법의 수렴성을 보존하고 불안정함을 방지하는 수정입니다.^[17] 복잡한 다항식을 해결하기 위해 개발되었습니다.

간격 뉴턴 방법

이 섹션에는 텍스트를 확인하지 않는 인용문이 포함될 수 있습니다. 인용 오류 확인 부탁드립니다. (2019년 2월) (본 템플릿 메시지 제거 방법 및 시기에 대해 알아봅니다.)

뉴턴의 방법을 구간 연산과 결합하는 것은 어떤 맥락에서는 매우 유용합니다. 이를 통해 함수의 값이 작거나 연속적인 반복 사이에 변수의 변동이 작은 일반적인 중단 기준보다 더 신뢰할 수 있습니다. 또한 뉴턴의 방법이 이론적으로 수렴하지만 부동 소수점 정밀도가 부족하여 수치적으로 발산하는 경우도 감지할 수 있습니다(일반적으로 변수의 매우 작은 변화가 함수의 값을 극적으로 변화시킬 수 있는 큰 다항식의 경우에 해당합니다; 윌킨슨 다항식 참조).^[18][19]

X가 실제 구간인 → C(여기서 X는 실제 구간입니다. F'의 구간 확장 F'가 있다고 가정하자. 즉, F'는 구간 ⊆를 입력으로 하고 다음과 같은 구간 ()을 출력합니다.

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

또한 0 ∉()를 가정하므로 특히 f는 X에서 최대 한 근을 갖습니다. 그런 다음 뉴턴 연산자의 간격을 다음과 같이 정의합니다.

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

여기서 ∈. F'에 대한 가설은 ()가 잘 정의되어 있고 구간임을 의미합니다(구간 연산에 대한 자세한 내용은 구간 산술 참조). 이는 자연스럽게 다음과 같은 순서로 이어집니다.

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

평균값 정리는 fin의 근이 존재할 경우 fin도 포함됨을 보장합니다. 또한 F'에 대한 가설은 m이 Y의 중간점일 때의 최대 절반 크기임을 보장하므로 이 수열은 [,x* ]로 수렴하며, 여기서 x*는 X의 f의 근입니다.

()X가 엄격하게 0을 포함하는 경우, 확장된 구간 분할을 사용하면 ()에 대한 두 구간의 조합이 생성됩니다.X 따라서 여러 근이 자동으로 분리되고 경계지어집니다.

적용들

최소화 및 최대화 문제

뉴턴의 방법을 사용하면 함수의 최솟값 또는 최댓값을 구할 수 있습니다().x 도함수는 최소값 또는 최대값에서 0이므로 도함수에 뉴턴의 방법을 적용하면 국소 최소값과 극대값을 구할 수 있습니다. 반복은 다음과 같습니다.

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

수와 멱급수의 곱셈적 역

중요한 응용은 뉴턴-랩슨 나눗셈으로, 곱셈과 뺄셈만으로 a의 역수를 빠르게 구할 수 있는데, 즉 x를 1/=로 표현하는 데 사용됩니다. 우리는 () = 1/ -의 0을 찾는 것으로 다시 표현할 수 있습니다. 우리는 () = -1/가 있습니다.

뉴턴의 반복은

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

따라서 뉴턴의 반복은 두 번의 곱셈과 한 번의 뺄셈만 있으면 됩니다.

이 방법은 또한 멱급수의 곱셈 역수를 계산하는 데 매우 효율적입니다.

초월방정식 풀기

많은 초월방정식은 뉴턴의 방법을 사용하여 임의의 정밀도까지 풀 수 있습니다.

뉴턴의 방법이 초월방정식에 적용될 수 있고 방정식의 해로 수렴될 때, 이것은 해가 초기 근사에 의해 형성된 쌍과 어떤 근사의 정확성을 증가시키는 알고리즘에 의해 정확하게 표현되는 계산 가능한 수임을 의미합니다.

특수 함수의 0을 구하는 중

그 근을 구하기 위해 베셀 함수의 비율에 뉴턴의 방법을 적용합니다.^[20]

비선형 방정식 해에 대한 수치적 검증

뉴턴 방법을 여러 번 사용하고 해 후보군을 구성하여 비선형 방정식의 해에 대한 수치 검증을 확립했습니다.^[21][22]

예

제곱근

어떤 수 a의 제곱근을 구하는 문제, 즉 양수 x를 =와 같이 구하는 문제를 생각해 보자. 뉴턴의 방법은 제곱근을 계산하는 많은 방법 중 하나입니다. 우리는 이것을 () = - 의 0을 찾는 것으로 다시 표현할 수 있습니다. 우리는 () = 2가 있습니다.

예를 들어 초기 추측 = 10으로 612의 제곱근을 찾는 경우 뉴턴 방법으로 주어진 수열은 다음과 같습니다.

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

올바른 숫자에 밑줄이 그어져 있습니다. 몇 번의 반복만으로 소수점 이하의 자리까지 정확한 해를 얻을 수 있습니다.

공식을 다음과 같이 재배열하면 제곱근을 구하는 바빌로니아 방법이 나옵니다.

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

cos () =의 솔루션

cos =인 양수 x를 찾는 문제를 생각해 보자. 우리는 () = cos () - 의 0을 찾는 것으로 다시 표현할 수 있습니다. 우리는 () = -sin () - 3을 갖는다. 모든 x에 대하여 cos () 가 ≤ 1이고 > 1에 대하여 > 1이므로, 우리는 해가 0과 1 사이에 있음을 알고 있습니다.

예를 들어, 초기 추측 = 0.5일 때 뉴턴 방법에 의해 주어진 수열은 다음과 같습니다(시작 값이 0이면 정의되지 않은 결과가 나오므로 해에 가까운 시작점을 사용하는 것의 중요성을 나타냅니다).

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

위의 예에서는 올바른 숫자에 밑줄을 그었습니다. 특히 소수점 이하 12자리가 맞습니다. 소수점 이하의 올바른 숫자는 2에서 5와 10으로 증가하여 2차 수렴을 보여줍니다.

코드

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

초기 추측값은 = 1이고 함수는 () = - 2이므로 () = 2가 됩니다.

뉴턴 방법의 각 새로운 반복은 다음과 같이 표시됩니다. x1. 우리는 계산하는 동안 분모() 여부를 확인할 것입니다.yprime)가 너무 작아집니다(보다 smaller합니다). epsilon), 그렇지 않으면 많은 양의 오류가 발생할 수 있으므로 () ≈이 0인 경우에 해당됩니다.

디프 f(x):               돌아가다 x**2 - 2   # f(x) = x^2 - 2  디프 f_prime(x):  돌아가다 2*x        # f'(x) = 2배  디프 뉴톤_(     x0,               # 처음 추측한 것은     f,                # 우리가 찾으려는 근을 가진 함수     f_prime,          # 함수의 도함수     관용의,        # 반복이 이보다 적게 변경되면 중지     엡실론,          # 이보다 작은 숫자로 나누지 않음     max_반복,   # 계산할 최대 반복 횟수     ):     위해서 i 안에 범위(max_반복):         y = f(x0)         와이프라임 = f_prime(x0)          한다면 복근(와이프라임) < 엡실론:       # 분모가 너무 작으면 포기             브레이크.          x1 = x0 - y / 와이프라임            # 뉴턴의 계산을 수행합니다.          한다면 복근(x1 - x0) <= 관용의:   # 결과가 원하는 공차 이내일 때 중지합니다.             돌아가다 x1                   # x1은 허용 오차와 최대 반복 횟수 내의 솔루션입니다.          x0 = x1                         # 프로세스를 다시 시작하려면 x0 업데이트      돌아가다 없음.                         # 뉴턴의 방법은 수렴하지 않았습니다. 

참고 항목

메모들

참고문헌

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

더보기

• 켄달이. Atkinson, 수치해석학개론, (1989) John Wiley & Sons, Inc., ISBN 0-471-62489-6
• Tjalling J. Ypma, Newton-Rapson 방법의 역사적 발전, 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.
• 듀플하르트, 비선형 문제에 대한 뉴턴 방법. 아핀 불변성 및 적응 알고리즘. 계산수학의 스프링어 시리즈, 제35권. 스프링어, 베를린, 2004. ISBN 3-540-21099-7.
• C. T. Kelley, Newton's Method로 비선형 방정식 풀기, 알고리즘 기초, SIAM, 2003 ISBN 0-89871-546-6.
• J. M. Ortega, W. C. Rheinboldt, 여러 변수의 비선형 방정식 반복해법. 응용수학의 고전, 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.특히 섹션 9.4, 9.6 및 9.7을 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.참조하십시오.
• Avriel, Mordecai (1976). Nonlinear Programming: Analysis and Methods. Prentice Hall. pp. 216–221. ISBN 0-13-623603-0.

외부 링크

Wikimedia Commons에는 Newton Method와 관련된 미디어가 있습니다.

Newton의 방법과 관련된 단어 목록은 Wikibooks의 Newton의 방법 범주를 참조하십시오.

• "Newton method", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Weisstein, Eric W. "Newton's Method". MathWorld.
• 뉴턴의 방법, 시티즌디움.
• Mathews, J., The Accelerated and Modified Newton Methods, 코스 노트.
• 우, X, 방정식의 뿌리, 과정 노트.