뉴턴 방법
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
뉴턴 방법은 주어진 함수의 근을 찾는 수치 해석적 방법으로, 초기 추측에서 시작하여 접선을 이용해 근을 반복적으로 근사한다. 연속 미분 가능한 함수 f(x)의 영점 x̂를 찾기 위해 점화식 xₙ₊₁ = xₙ - f(xₙ)/f'(xₙ)을 사용하며, 초기값이 영점에 충분히 가깝고 f'(x̂) ≠ 0일 경우 빠르게 수렴한다. 2차 수렴 속도를 가지지만, 초기값, 도함수 계산, 발산 가능성 등의 한계를 가지며, 초기값 선정, 도함수 계산의 어려움, 발산 가능성 등의 한계가 있다. 이러한 문제점을 개선하기 위해 간이 뉴턴 방법, 할선법, 준 뉴턴 방법, 히라노 변형 뉴턴법, 구간 뉴턴법 등 다양한 변형 방법이 개발되었다.
더 읽어볼만한 페이지
- 근 찾기 알고리즘 - 유리근 정리
유리근 정리는 유일 인수 분해 정역 위에서 정의된 다항식환의 다항식이 분수체 원소를 근으로 가질 때, 분자는 상수항을 나누고 분모는 최고차항을 나눈다는 정리로, 일계수 다항식이면 그 근은 환의 원소가 된다. - 근 찾기 알고리즘 - 고속 역 제곱근
고속 역 제곱근 알고리즘은 부동 소수점 숫자의 역 제곱근을 빠르게 계산하는 방법으로, 과거 3D 그래픽 처리에서 부동 소수점 연산의 성능 한계를 극복하는 데 기여했으며 퀘이크 3 아레나 소스 코드 공개로 널리 알려졌으나, 하드웨어 발전으로 필요성은 감소했다. - 최적화 알고리즘 - 기댓값 최대화 알고리즘
- 최적화 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다. - 수치해석학 - 수학적 최적화
수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다. - 수치해석학 - 선형대수학
선형대수학은 벡터, 벡터 공간, 행렬 등의 개념으로 선형 방정식과 선형 변환을 연구하는 수학 분야로, 선형성을 활용해 행렬로 표현 및 계산하며, 연립일차방정식 해법, 고유값/고유벡터를 통한 행렬 분석, 벡터 공간의 기저와 차원 등을 다루고 물리학, 공학, 컴퓨터 과학 등 다양한 분야에 응용된다.
뉴턴 방법 | |
---|---|
개요 | |
![]() | |
유형 | 근 찾기 알고리즘 |
고안자 | 아이작 뉴턴 조지프 랩슨 |
개발 연도 | 1685년경 (아이작 뉴턴), 1690년 (조지프 랩슨) |
목적 | |
목적 | 함수의 근사적인 근을 찾음 |
방법 | |
방법 | 초기 추정값에서 시작 접선을 사용하여 더 나은 추정값을 반복적으로 찾음 |
수식 | |
반복 공식 | x_(n+1) = x_n - f(x_n) / f'(x_n) |
장점 및 단점 | |
장점 | 수렴 속도가 빠름 (이차 수렴) 구현이 비교적 간단함 |
단점 | 초기 추정값에 따라 수렴하지 않을 수 있음 도함수를 계산해야 함 근 근처에서 진동하거나 발산할 수 있음 다중근의 경우 수렴 속도가 느려질 수 있음 |
활용 분야 | |
활용 분야 | 방정식의 근 찾기 최적화 문제 컴퓨터 그래픽스 수치 해석 |
관련 알고리즘 | |
관련 알고리즘 | 할선법 브렌트 방법 최급강하법 |
2. 정의
연속 미분 가능한 함수 가 영점 를 갖는다고 가정한다. 또한, 라고 가정한다. 그렇다면, 다음을 만족시키는 열린집합 가 존재한다.
- 임의의 에 대하여, 수열 ()은 로 수렴한다.
이를 통해 영점 를 근사하는 방법을 '''뉴턴 방법'''이라고 한다. 뉴턴 방법은 초기 추측값에서 시작하여, 접선으로 함수를 근사한 다음, 이 접선의 x 절편을 계산한다. 이 x 절편은 일반적으로 첫 번째 추측보다 원래 함수의 근에 더 나은 근사치가 되며, 반복법을 적용할 수 있다.
어떤 임의의 초기값 에서 시작한다. 이 초기 추측이 알려지지 않은 0에 충분히 가깝고, 인 경우, 이 방법은 일반적으로 수렴한다.
생각하는 문제를 이 되는 를 구하는 것으로 한정하면, 근처에 적당한 값 을 취하고, 다음의 점화식에 의해 에 수렴하는 수열을 얻을 수 있는 경우가 많다.
:
예를 들어, 를 계산으로 구하는 경우에,
:
라고 놓고, 의 해를 구한다.
:
이므로, 점화식은
:
로 쓸 수 있다. 예를 들어 라고 하면, 이 수열은 에 수렴한다.
3. 이론
아이작 뉴턴은 1669년경 자신의 저서에서 뉴턴 방법을 처음 제시했지만, 그가 제시한 방법은 현대적인 방법과는 차이가 있었다.[1] 뉴턴은 초기 근사값을 바탕으로 오차를 수정하는 과정을 반복하여 다항식에만 이 방법을 적용했다. 각 수정값을 통해 남은 오차를 기준으로 다항식을 다시 작성하고, 고차항을 무시하여 새로운 수정값을 구했다. 뉴턴은 이 방법을 미분과 명시적으로 연결하거나 일반적인 공식을 제시하지는 않았다. 그는 수치적 문제와 대수적 문제 모두에 이 방법을 적용했으며, 후자의 경우 테일러 급수를 생성했다.
뉴턴은 프랑수아 비에트의 방법에서 아이디어를 얻었을 수 있지만, 두 방법은 동일하지 않다.[2] 비에트의 방법은 샤라프 알딘 알투시와 자마시드 알 카시의 연구에서 찾을 수 있다. 그들은 $x^P - N = 0$을 풀어 $N$의 근을 구하는 뉴턴 방법의 한 형태를 사용했다. 헨리 브리그스의 ''삼각법 브리타니카''에서도 유사한 방법을 찾을 수 있었다.[3]
1680년대에 일본 수학자 세키 고와는 뉴턴 방법을 사용하여 단일 변수 방정식을 풀었지만, 미적분과의 연결은 없었다.[4]
1685년 존 왈리스의 ''대수학 논문 (역사적 및 실용적)'에서 뉴턴 방법이 처음 출판되었고,[5] 1690년 조지프 랩슨은 ''보편 방정식 분석''에서 단순화된 설명을 출판했다.[6] 랩슨은 각 반복 과정을 원래 다항식에서 추출하여 뉴턴의 복잡한 재작성 과정을 피했다. 1740년 토마스 심프슨은 뉴턴 방법을 미적분을 사용하여 일반적인 비선형 방정식을 푸는 반복적인 방법으로 설명했다.
아서 케일리는 1879년 ''뉴턴-푸리에 허수 문제''에서 뉴턴 방법을 차수가 2보다 큰 다항식의 복소수 근과 복소수 초기 값으로 일반화하는 데 어려움이 있음을 처음으로 지적했다.
3. 1. 局所収束定理 (국소 수렴 정리)
테일러 정리에 따르면, 연속적인 2차 도함수를 갖는 임의의 함수는 그 근에 가까운 점을 중심으로 전개하여 나타낼 수 있다. 이 근을 α라고 가정하자. 그러면 xn에 대한 f(α)의 전개는 다음과 같다.여기서 라그랑주 나머지는 다음과 같다.
여기서 ξn는 xn과 α 사이에 있다.
α가 근이므로, 위의 식은 다음과 같이 된다.
위 식을 f'(xn)로 나누고 재정렬하면 다음과 같다.
xn+1이 다음과 같이 정의된다는 것을 기억하면
다음과 같음을 알 수 있다.
즉,
양변의 절댓값을 취하면
위 식은 다음 조건이 충족되면 수렴 차수가 최소한 2차임을 보여준다.
1. f'(x) ≠ 0; 모든 x ∈ I에 대해, 여기서 I는 구간 [α − |ε0|, α + |ε0|]이다.
2. f''(x)는 모든 x ∈ I에 대해 연속이다.
3. M |ε0| < 1
여기서 M은 다음과 같이 주어진다.
이 조건들이 충족되면
초깃값 x0을 f(x) = 0의 해에 충분히 가까운 곳으로 선택하면(해의 존재를 가정), 뉴턴 방법으로 생성된 수열은 2차 수렴 속도로 해에 수렴한다. 즉, 오차가 매 단계마다 제곱으로 감소한다.[36]
f(x)의 x=x0에서의 테일러 전개를 하면
:f(x) = f(x0)+f'(x0)(x-x0)+O((x-x0)2)
이 때, (우변)=0의 해는 (좌변)=0의 근의 x0에서의 다항식 차수 1차의 근사가 된다. 우변의 해는
:x=x0-f(x0)/f'(x0)
다음으로, 이 근사값이 x0보다 근에 가까워진다.
위 식을 다음과 같은 이산 역학계로 생각한다.
:xn+1 = g(xn), 단, g(x) = x - f(x)/f'(x)
이 역학계에서 f(x*)=0이 되는 x*는 고정점이다.
따라서 |g'(x*)|<1, 즉 x*가 침점(어트랙터, 안정 고정점)이며, 주어진 초기 조건 x0이 이 어트랙터의 인력 영역에 속해 있다면 xn의 ω-극한(n → ∞)은 f(x*)=0이 되는 x*에 수렴한다.
하지만, x*가 침점이라는 보장은 항상 담보되지 않는다. 예를 들어 x축의 점근선이나 함수 f(x)의 극값근방에서는 고정점이 불안정해질 수 있다.[36]
예를 들어, f(x*)를 적절한 근방의 점 xn에서 전개하면 f'(x*)≠0이면, 2차 잉여항 R2=f''(ξn)/2(xn-x*)2로서
따라서 2차로 수렴한다.
3. 2. 半局所収束定理 (반국소 수렴 정리)
전 절에서는 해의 존재를 가정한 후 초기값 를 해와 충분히 가까운 곳에 선택할 것을 요구했다. 이에 대해, 해의 존재를 가정하지 않고 초기값 가 어떤 조건을 만족할 때 해의 존재와 반복의 수렴을 보이는 정리를 반국소 수렴 정리(semi-local convergence theorem영어)라고 한다. 1차원에서의 반국소 수렴 정리는 코시에 의해 1829년에 제시되었고, 차원 유클리드 공간에서의 경우는 파인[37]에 의해 1916년에 제시되었다. 그 후, 바나흐 공간에서의 반국소 수렴 정리가 칸토로비치에 의해 1948년에 제시되었으며, 현대에는 뉴턴-칸토로비치 정리라고 불린다[38]. 이 정리에는 몇 가지 변형이 알려져 있으며, 관련 내용은 문헌에 정리되어 있다.[39]3. 3. 수렴 속도
일반적으로 뉴턴 방법은 2차 수렴한다. 즉, 해 근처에서 오차는 매 단계마다 제곱으로 감소한다. 이는 직관적으로 매 단계에서 정확한 자릿수가 대략 두 배가 된다는 것을 의미한다.[7]그러나 찾고자 하는 근이 중근(다중근)인 경우, 수렴 속도는 1차로 떨어진다. 즉, 각 단계마다 오차가 상수 인자에 의해 감소한다. 만약 도함수가 근에서 0이 아니면, 2차 수렴이 보장된다. 하지만 도함수가 근에서 0이면, 수렴은 일반적으로 선형이다.[8]
만약 근의 중복도 `m`을 알고 있다면, 다음 수정된 알고리즘은 2차 수렴 속도를 유지한다.[7]
:
이는 연속 과잉 완화를 사용하는 것과 동일하다. 반면에, 근의 중복도 `m`을 알지 못하는 경우, 1~2번의 반복을 수행한 후 `m`을 추정하여 수렴 속도를 높일 수 있다.
함수 `f`가 `α`에서 영점(zero)을 가지고, `f`가 `α`의 근방에서 미분 가능하다고 가정하자.
- 만약 `f`가 연속적으로 미분 가능하고 그 도함수가 `α`에서 0이 아니고, `α`에서 이계 도함수를 가진다면, 수렴은 2차 또는 그 이상이다. 만약 2계 도함수가 `α`에서 0이 아니라면, 수렴은 2차이다. 3계 도함수가 존재하고 `α`의 근방에서 유계라면, 다음이 성립한다.
:
:여기서
:
- 만약 도함수가 `α`에서 0이라면, 수렴은 일반적으로 선형이다. 구체적으로, `f`가 두 번 미분 가능하고, `f'(α) = 0`이고, `f''(α) ≠ 0`이면, `α`의 근방이 존재하여, 그 근방의 모든 시작값 `x_0`에 대해, 반복 수열은 속도 1/2로 선형적으로 수렴한다.[9]
그러나 병리적인 상황에서는 선형 수렴조차 보장되지 않는다.
4. 성질
뉴턴 방법은 몇 가지 성질을 갖는다.
만약 가 2번 연속 미분 가능 함수라면, 점렬의 항과 영점 사이의 오차에 대하여 부등식을 만족하는 상수 가 존재한다. 또한, 의 부호에 따라 점렬 은 증가하거나 감소하는 수열이 된다.
가 어떤 구간에서 오목 함수이며 엄격히 증가하고, 구간 내에 영점이 존재한다면, 뉴턴 반복은 단조 함수이고 수렴하며, 영점에 수렴한다.[10] 조제프 푸리에는 오른쪽 끝점에서 시작하는 뉴턴 방법의 변형을 도입했는데, 이 수열은 단조 감소하고 수렴한다.[10] 영점을 갖는 오목 증가 함수의 경우, 초기화는 거의 관련이 없으며, 반복의 어느 단계에서든 정확도는 왼쪽과 오른쪽에서 반복 위치의 차이로부터 결정될 수 있다. 가 두 번 연속 미분 가능하다면, 위치의 차이가 2차적으로 0으로 수렴함을 보일 수 있다.[10]
이러한 내용은 여러 변수를 가진 연립 방정식으로 확장될 수 있으며, 단일 변수의 경우 뉴턴 방법의 단조 수렴은 의 고차 도함수에 대한 조건으로 일반화될 수 있다.[11][12]
4. 1. 오차
만약 가 2번 연속 미분 가능 함수라면, 점렬의 항과 영점 사이의 오차에 대하여 다음 부등식을 만족하는 상수 가 존재한다.:
4. 2. 점렬의 단조성
만약 가 2번 연속 미분 가능 함수라면, 다음이 성립한다.- 임의의 에 대하여 라면, 은 증가 수열이다.
- 임의의 에 대하여 라면, 은 감소 수열이다.
가 어떤 구간에서 오목 함수이며 엄격히 증가한다고 가정하자. 만약 이 함수가 왼쪽 끝점에서 음수이고 오른쪽 끝점에서 양수라면, 중간값 정리에 의해 구간 내 어딘가에 의 영점 가 존재한다. 기하학적 원리에 따르면, 왼쪽 끝점에서 시작하는 뉴턴 반복 는 단조 함수이고 수렴하며, 반드시 에 수렴한다.[10]
조제프 푸리에는 오른쪽 끝점에서 시작하는 뉴턴 방법의 변형을 도입했다.
:
이 수열은 단조 감소하고 수렴한다. 이 정의에서 극한을 취함으로써, 의 극한 역시 영점 임이 확인된다.[10]
따라서, 영점을 갖는 오목 증가 함수의 경우, 초기화는 거의 관련이 없다. 영점의 왼쪽에 있는 어느 지점에서 시작하는 뉴턴 반복과 영점의 오른쪽에 있는 어느 지점에서 시작하는 푸리에의 수정된 뉴턴 반복은 모두 수렴한다. 반복의 어느 단계에서든 정확도는 왼쪽에서 반복 위치와 오른쪽에서 반복 위치의 차이로부터 직접 결정될 수 있다. 만약 가 두 번 연속 미분 가능하다면, 테일러 정리를 사용하여 다음을 증명할 수 있다.
:
이것은 위치의 차이가 2차적으로 0으로 수렴함을 보여준다.[10]
상기 내용은 여러 변수를 가진 연립 방정식으로 확장될 수 있는데, 이 경우 단조성과 오목성의 관련 개념을 공식화하는 것이 더 미묘하다.[11] 단일 변수의 단일 방정식의 경우, 위에서 언급된 뉴턴 방법의 단조 수렴은 의 임의의 고차 도함수에 대한 양성 또는 음성 조건으로 오목성을 대체하도록 일반화될 수 있다. 그러나 이 일반화에서, 뉴턴 반복은 접선 대신 테일러 다항식을 기반으로 하도록 수정된다. 오목성의 경우, 이러한 수정은 표준 뉴턴 방법과 일치한다.[12]
5. 고차원에서의 확장
뉴턴 방법은 여러 개의 변수와 방정식을 가진 연립 비선형 방정식의 해를 찾는 데에도 사용될 수 있다. 이 경우, 스칼라 미분 대신 야코비 행렬의 역행렬을 사용한다. 점화식은 다음과 같다.[17]
:
여기서 $\mathbf{x}_n$은 벡터, $F$는 벡터 값을 갖는 함수, $J_F$는 $F$의 야코비 행렬이다.
이는 연립 일차 방정식
:
에서 미지수 $\mathbf{x}_{n+1} - \mathbf{x}_n$를 풀어서 얻을 수도 있다.
뉴턴 방법의 $k$차원 변형은 $k$개 이상의 (비선형) 방정식 시스템을 푸는 데에도 사용될 수 있다. 이때는 야코비 행렬 $J$의 일반화 역행렬을 사용한다. 만약 비선형 시스템에 해가 없다면, 이 방법은 비선형 최소 제곱법의 의미에서 해를 찾으려고 시도한다. (자세한 내용은 가우스-뉴턴 알고리즘 참조)
예를 들어, 다음과 같은 방정식 집합을 생각해 보자.[17]
:
이 방정식은 알려진 값 벡터 $\begin{bmatrix} 2 \\ 3 \end{bmatrix}$이 주어질 때 점 벡터 $\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$에 대해 풀어야 한다.
이때, 함수 벡터 $F(X_k)$와 야코비 행렬 $J(X_k)$는 다음과 같이 정의된다.
:
각 반복에 대해 풀어야 할 방정식은 다음과 같이 다시 작성할 수 있다.
:
그리고
:
와 같이 계산한다.
초기값 $X_0$를 $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$로 설정하고, 허용 오차 $E$를 $10^{-3}$로 설정하면, 4번의 반복 후에 $X_4 = \begin{bmatrix} 0.567297 \\ -0.309442 \end{bmatrix}$로 수렴한다.
다음 표는 해를 구하는 과정에서의 반복 과정을 나타낸다.[17]
단계 | 변수 | 값 |
---|---|---|
0 | $x$ | |
$f(x)$ | ||
colspan="3" ; style="background:white;"| | ||
1 | $J$ | |
$c$ | ||
$x$ | ||
$f(x)$ | ||
colspan="3" ; style="background:white;"| | ||
2 | $J$ | |
$c$ | ||
$x$ | ||
$f(x)$ | ||
colspan="3" ; style="background:white;"| | ||
3 | $J$ | |
$c$ | ||
$x$ | ||
$f(x)$ | ||
colspan="3" ; style="background:white;"| | ||
4 | $J$ | |
$c$ | ||
$x$ | ||
$f(x)$ |
6. 응용
뉴턴 방법은 함수의 최댓값 또는 최솟값을 찾는 데에도 응용될 수 있다. 어떤 함수의 미분값은 그 함수의 최댓값 또는 최솟값에서 0이 되므로, 뉴턴 방법을 미분값에 적용하여 지역 최솟값과 최댓값을 찾을 수 있다.[35] 이때 사용되는 점화식은 다음과 같다.
예를 들어 함수 는 0에서 근을 갖는다.[1] 가 근에서 연속적으로 미분 가능하므로, 뉴턴 방법이 근처에서 초기화되면 수렴한다. 그러나 도함수 가 근에서 0이므로 2차 수렴은 보장되지 않는다. 이 경우 뉴턴 반복은 이다. 따라서 뉴턴 방법은 어디에서 초기화되든 0으로 수렴하지만, 1차 수렴 속도로만 수렴한다.
함수 도 0에서 근을 가지며, 연속적으로 미분 가능하다. 그러나 두 번째 도함수 는 존재하지 않으므로 2차 수렴을 보장할 수 없다. 실제로 뉴턴 반복은 {3+4x^{1/3}}}}이므로, 수렴 속도는 초선형이지만 2차 미만이다.
다음 표는 와 에 적용된 뉴턴 방법의 수렴 속도를 비교하여 보여준다.
scope="col" | | scope="col" | | scope="col" | | scope="col" | |
---|---|---|---|
1 | 2 | 1 | 2 |
1.4286 × 10−1 | 2.1754 × 10−1 | 3.3333 × 10−1 | 4.4444 × 10−1 |
1.4669 × 10−2 | 1.8260 × 10−2 | 6.6666 × 10−2 | 7.1111 × 10−2 |
9.0241 × 10−4 | 9.8961 × 10−4 | 3.9216 × 10−3 | 3.9369 × 10−3 |
2.5750 × 10−5 | 2.6511 × 10−5 | 1.5259 × 10−5 | 1.5259 × 10−5 |
2.4386 × 10−7 | 2.4539 × 10−7 | 2.3283 × 10−10 | 2.3283 × 10−10 |
5.0366 × 10−10 | 5.0406 × 10−10 | 5.4210 × 10−20 | 5.4210 × 10−20 |
1.3344 × 10−13 | 1.3344 × 10−13 | 2.9387 × 10−39 | 2.9387 × 10−39 |
오른쪽의 2차 수렴은 반복에서 참 근(0, 1, 2, 3, 5, 10, 20, 39, ...)까지의 거리에서 크기의 순서가 행별로 약 2배 증가하는 반면, 왼쪽의 초선형 수렴은 크기의 순서가 행별로 약 4/3배 증가한다(0, 1, 2, 4, 5, 7, 10, 13, ...).
뉴턴 방법은 뉴턴-랩슨 나눗셈에서처럼, 곱셈과 뺄셈만 사용하여 어떤 수 의 역수를 빠르게 찾는 데에도 활용될 수 있다. 즉, 를 만족하는 수 를 찾는 것이다. 이는 의 영점을 찾는 문제로 변환할 수 있으며, 이다.
이때 뉴턴 반복 공식은 다음과 같다.
따라서 뉴턴 반복은 곱셈 두 번과 뺄셈 한 번만으로 역수를 계산할 수 있다. 이 방법은 멱급수의 곱셈 역원을 계산하는 데에도 매우 효율적이다.
또한, 뉴턴 방법은 초월 방정식을 임의의 정밀도로 푸는 데 사용될 수 있다. 예를 들어, 정규 분포와 같이 닫힌 형식으로 풀 수 없는 적분 함수를 포함하는 누적 확률 밀도 함수에서 알려진 확률에 해당하는 값을 찾는 문제에 적용할 수 있다. 뉴턴 방법으로 수치적 해를 구하기 위해 필요한 도함수는 일반적으로 알려져 있어, 수치적 해를 구할 수 있다.
6. 1. 루트값 구하기
Newton's method영어은 제곱근, 세제곱근 등 루트값을 구하는 데 효과적으로 사용될 수 있다. 예를 들어, √a를 구하기 위해 이라는 방정식을 뉴턴 방법으로 풀면, 다음 점화식을 얻는다.[47]:
이 방법은 바빌로이안 방법과 동일하며, 빠르게 수렴한다. 즉, 루트를 구하는 뉴튼법은 결국 현재 추측한 루트값의 과 의 산술_평균을 반복적으로 적용한 것이다.
예를 들어 612의 루트값을 계산하는 경우, 초기값을 로 하고 뉴턴법을 적용하면 다음과 같다.
:
여기서 참값과 같은 부분의 숫자는 밑줄이 그어져있다. 많지 않은 몇번의 반복을 통해 매우 정확한 루트값이 계산되는 것을 볼 수 있다.
다음은 612의 제곱근을 찾기 위해 1, 10, -20의 초기값으로 뉴턴 방법을 적용한 결과이다.
1 | −611 | 10 | −512 | −20 | −212 |
306.5 | 9.3330 × 104 | 35.6 | 655.36 | −25.3 | 28.09 |
154.2483686786 | 2.3180 × 104 | 26.3955056180 | 84.722 | −24.744861601 | 0.30818 |
79.1079978644 | 5.6461 × 103 | 24.7906354925 | 2.5756 | −24.7386345374 | 3.8777 × 10−5 |
43.4221286822 | 1.2735 × 103 | 24.7386882941 | 2.6985 × 10−3 | −24.7386337537 | 6.1424 × 10−13 |
28.7581624288 | 215.03 | 24.7386337538 | 2.9746 × 10−9 | | | |
25.0195385369 | 13.977 | ||||
24.7402106712 | 7.8024 × 10−2 | ||||
24.7386338040 | 2.4865 × 10−6 | ||||
24.7386337537 | 2.5256 × 10−15 |
몇 번의 반복만으로도 소수점 이하 자릿수까지 정확한 해를 얻을 수 있다. 뉴턴 반복은 매우 부정확한 추측값으로 초기화된 경우에도 빠르게 수렴하는것을 볼수 있다.
6. 2. 초월 방정식의 해
많은 초월 방정식은 뉴턴 방법을 사용하여 임의의 정밀도까지 풀 수 있다. 예를 들어, 알려진 확률에 맞게 정규 분포와 같은 누적 확률 밀도 함수를 찾는 것은 일반적으로 닫힌 형식으로 풀 수 있는 알려진 방법이 없는 적분 함수를 포함한다. 그러나 뉴턴 방법으로 수치적으로 풀기 위해 필요한 도함수를 계산하는 것은 일반적으로 알려져 있으며, 수치적 해를 가능하게 한다. 예를 들어, 역 정규 누적 분포에 대한 수치적 해를 참조하라.6. 3. 최적화 문제
뉴턴 방법은 함수 f(x)|f(x)영어의 최댓값 또는 최솟값을 찾는 데 사용될 수 있다. 미분값은 최댓값 또는 최솟값에서 0이 되므로, 뉴턴 방법을 미분값에 적용하여 지역 최솟값과 최댓값을 찾을 수 있다.[35] 이때 점화식은 다음과 같다.:
6. 4. 역수 계산
뉴턴 방법은 곱셈과 뺄셈 연산만을 이용하여 어떤 수의 역수를 빠르게 계산하는 데 사용될 수 있다. 즉, 를 만족하는 수 를 찾는 것이다. 이는 의 영점을 찾는 것으로 바꿔 말할 수 있다. .뉴턴의 반복 공식은 다음과 같다.
:
따라서 뉴턴의 반복은 곱셈 2번과 뺄셈 1번만 필요하다.
이 방법은 멱급수의 곱셈 역원을 계산하는 데에도 매우 효율적이다.
7. 한계 및 주의사항
뉴턴 방법은 강력한 수치해석 방법이지만, 몇 가지 한계와 주의사항이 존재한다.
1. 초기값 선정의 중요성뉴턴 방법의 수렴 여부와 속도는 초기값에 크게 의존한다. 초기값이 실제 해에서 너무 멀리 떨어져 있거나, 함수의 도함수가 0에 가까운 지점을 지나게 되면 수렴하지 않거나 매우 느리게 수렴할 수 있다. 예를 들어, 함수 의 경우 초기값이 0.5이면 수렴 속도가 매우 느리다.[14] 반면, 함수 의 경우 초기값이 0이 아니면 발산한다. 따라서 초기값은 실제 해에 충분히 가깝고, 도함수가 0에 가까워지는 지점을 피하도록 신중하게 선택해야 한다.
2. 도함수 계산의 어려움뉴턴 방법은 도함수를 직접 계산해야 한다. 하지만 도함수의 해석적 표현을 얻기 어렵거나 계산 비용이 큰 경우가 있다. 이 경우 도함수를 근사하여 할선법과 유사한 방법을 사용할 수 있지만, 수렴 속도는 느려진다.[40] 또한, 야코비 행렬을 명시적으로 알아야 하는 경우가 있는데, 함수에 따라 이를 구하기 어려운 경우도 있다. 이럴 때는 준 뉴턴 방법을 사용한다.[40]
3. 발산 가능성뉴턴 방법은 특정 조건에서 수렴하지 않고 발산할 수 있다.[8] 초기값이 함수의 변곡점 근처에 있거나, 함수가 진동하는 형태이거나, 함수의 정의역이 불완전한 경우 등이 이에 해당한다.[9][16]
- 변곡점 근처: 초기값이 변곡점에 너무 가까우면 다음 반복값이 매우 멀어져 발산할 수 있다.
- 진동하는 함수: 반복값이 두 값 사이를 오가며 수렴하지 않을 수 있다. 예를 들어, 어떤 함수에 뉴턴 방법을 적용하면 0과 1 사이에서 진동하는 경우가 발생할 수 있다.[16]
- 함수의 정의역: 반복값이 정의역 밖으로 벗어나 계산이 불가능해질 수 있다.[16] 예를 들어, 자연 로그 함수에서 초기값이 e보다 크면 다음 반복값이 음수가 되어 계산이 불가능하다.
이러한 이유로 실제 구현에서는 반복 횟수 제한, 근을 포함하는 구간 설정, 다른 수치해석 방법과의 병행 등 추가적인 조치가 필요하다.
7. 1. 초기값 선정의 중요성
뉴턴 방법의 수렴 여부와 속도는 초기값에 크게 의존한다. 초기값이 실제 해에서 너무 멀리 떨어져 있거나, 함수의 도함수가 0에 가까운 지점을 지나게 되면 수렴하지 않거나 매우 느리게 수렴할 수 있다.뉴턴 방법은 초기 추측값에서 시작하여 함수의 접선을 이용해 근사값을 구하고, 이 과정을 반복하여 실제 해에 수렴해 나가는 방식이다. 그러나 초기값이 적절하지 않으면, 이 방법은 실패할 수 있다.
예를 들어, 함수 는 1에서 근을 갖는다. 이고 가 매끄러우므로, 1로 수렴하는 모든 뉴턴 반복은 2차로 수렴한다. 그러나 0.5에서 초기화하면 뉴턴 방법의 처음 몇 번의 반복은 약 26214, 24904, 23658, 22476으로 느리게 감소하며, 200번째 반복만이 1.0371이다. 다음 반복은 1.0103, 1.00093, 1.0000082, 1.00000000065로, 2차 수렴을 보여준다.[14]
함수 의 근을 찾는 경우, 뉴턴 반복은 다음과 같다.
:
만약 초기값을 0이 아닌 다른 값으로 설정하면, 반복 수열은 수렴하지 않고 발산한다. 예를 들어, 초기값을 0.001로 하면, 처음 몇 번의 반복 값은 -0.002, 0.004, -0.008, 0.016 등으로 진동하며, 20번째 반복 값은 1048.58, -2097.15 등으로 발산한다.
따라서, 뉴턴 방법을 사용할 때는 초기값을 신중하게 선택해야 한다. 초기값은 실제 해에 충분히 가까워야 하며, 함수의 도함수가 0에 가까워지는 지점을 피해야 한다.
7. 2. 도함수 계산의 어려움
뉴턴 방법은 수렴이 2차적이라는 장점을 가지지만, 몇 가지 어려움이 있다.우선, 뉴턴 방법은 도함수를 직접 계산해야 한다. 하지만 도함수에 대한 해석적 표현을 얻기 어렵거나, 계산 비용이 큰 경우가 있을 수 있다. 이러한 경우에는 함수 위의 두 점을 지나는 선의 기울기를 사용하여 도함수를 근사할 수 있다. 이 근사를 사용하면 할선법과 유사한 결과를 얻을 수 있지만, 수렴 속도는 뉴턴 방법보다 느리다.[40]
또한, 뉴턴 방법을 사용하려면 야코비 행렬을 명시적으로 알아야 한다. 그러나 함수 ''f''에 따라 야코비 행렬을 구체적으로 알 수 없는 경우가 있다. 이 경우에는 야코비 행렬을 필요로 하지 않는 준 뉴턴 방법을 사용한다.[40]
7. 3. 발산 가능성
뉴턴 방법은 일반적으로 2차 수렴을 보이는 강력한 방법이지만, 특정 경우에는 수렴하지 않고 발산할 수 있다.[8] 이러한 경우는 뉴턴 방법의 2차 수렴 증명에서 가정한 조건들이 충족되지 않을 때 발생한다.[9]예를 들어, 초기값이 함수의 변곡점 근처에 있거나, 진동하는 형태의 함수인 경우 발산할 수 있다.
- 변곡점 근처: 초기값이 변곡점에 너무 가까우면, 접선이 x축과 평행하거나 거의 평행하게 되어 다음 반복값이 매우 멀어질 수 있다.
- 진동하는 함수: 함수가 특정 구간에서 진동하는 형태를 가지면, 뉴턴 방법의 반복값이 두 값 사이를 오가며 수렴하지 않을 수 있다. 예를 들어, 어떤 함수에 뉴턴 방법을 적용하면 0과 1 사이에서 진동하는 경우가 발생할 수 있다.[16]
- 함수의 정의역: 함수가 불완전한 정의역을 가지는 경우, 뉴턴 방법의 반복값이 정의역 밖으로 벗어나 더 이상 반복을 진행할 수 없는 경우가 발생할 수 있다.[16] 예를 들어, 자연 로그 함수는 양수 x에 대해서만 정의되는데, 초기값이 e보다 크면 다음 반복값이 음수가 되어 계산이 불가능하다.
이러한 발산 가능성 때문에 뉴턴 방법의 실제 구현에서는 반복 횟수에 제한을 두거나, 근을 포함하는 구간을 설정하거나, 다른 수치해석 방법과 함께 사용하는 것이 일반적이다.
8. 개선된 방법
뉴턴 방법의 아이디어를 개선하여, 다음 식을 사용하는 방법을 얻을 수 있다.[41]
:
이 방법은 경우에 따라 기존 방법보다 빠르다.[41]
8. 1. 간이 뉴턴 방법 (Simplified Newton Method)
뉴턴 방법에서 도함수 계산을 간략화한 것이 '''간이 뉴턴 방법'''이다.:
간이 뉴턴 방법에 대한 반국소 수렴 정리는 '''우라베 미노루의 정리'''로 알려져 있다. 우라베 미노루의 정리는 원래 수학적 귀납법을 사용하여 증명되었지만, 그 후 바나흐 고정점 정리를 사용한 다른 증명이 주어졌다.[43] 간이 뉴턴 방법에 대한 반(半) 국소 수렴 정리를 더 쉽게 평가하기 위해 개발된 간이 뉴턴 방법의 변종이 '''크라프치크(Krawczyk) 방법'''이다.[44][45]
8. 2. 히라노 변형 뉴턴법 (Hirano's Modified Newton Method)
히라노의 수정된 뉴턴 방법은 뉴턴 방법의 수렴성을 유지하면서 불안정성을 피하도록 수정된 방법이다.[32] 이는 복소 다항식을 풀기 위해 개발되었으며, 뉴턴 방법의 국소적인 2차 수렴성을 유지하면서 불안정한 거동을 억제하도록 고안되었다.[42]8. 3. 구간 뉴턴법 (Interval Newton's Method)
구간 산술을 이용하여 뉴턴 방법을 확장한 것으로, 일반적인 중단 기준(함수의 작은 값 또는 연속적인 반복 사이의 변수의 작은 변화)보다 더 신뢰할 수 있는 중단 기준을 제공한다.[33][34] 또한, 뉴턴 방법이 이론적으로는 수렴하지만, 부동 소수점 산술의 불충분한 정밀도로 인해 수치적으로 발산하는 경우를 감지할 수 있다. (이는 일반적으로 차수가 큰 다항식의 경우로, 변수의 아주 작은 변화가 함수의 값을 극적으로 변경할 수 있다. 윌킨슨 다항식 참조).[33][34]X영어가 실수 구간이고, f'영어의 구간 확장 F'영어가 있다고 가정하면, F'영어는 구간 Y ⊆ X영어를 입력으로 받아 구간 F'(Y)영어를 출력하며 다음을 만족한다.
:
또한 0 ∉ F'(X)영어라고 가정한다. 특히 f영어는 X영어에서 최대 하나의 근을 갖는다.
그런 다음 구간 뉴턴 연산자를 다음과 같이 정의한다.
:
여기서 m ∈ Y영어. F'영어에 대한 가설은 N(Y)영어가 잘 정의되고 구간임을 의미한다(구간 연산에 대한 자세한 내용은 구간 산술 참조). 이는 자연스럽게 다음 수열로 이어진다.
:
평균값 정리는 f영어의 근이 Xk영어에 있다면, 그것이 또한 Xk+1영어에도 있음을 보장한다. 또한 F′영어에 대한 가설은 m영어이 Y영어의 중간점일 때 Xk+1영어가 Xk영어의 크기의 절반 이하임을 보장하므로, 이 수열은 [x*, x*]영어로 수렴하며, 여기서 x*영어는 f영어의 X영어에서의 근이다.
만약 F'(X)영어가 0을 엄격하게 포함한다면, 확장된 구간 나눗셈을 사용하면 N(X)영어에 대해 두 구간의 합집합이 생성된다. 따라서 다중 근은 자동으로 분리되고 경계가 설정된다.
9. 프로그램 예제 (Python)
python
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, f, f_prime, tolerance, epsilon, max_iterations):
"""뉴턴 방법
Args:
x0: 초기 추측값
f: 근을 찾으려는 함수
f_prime: 함수의 도함수
tolerance: 반복 간 변화가 이 값보다 작으면 중단
epsilon: 이 값보다 작은 수로 나누지 않음
max_iterations: 최대 반복 횟수
"""
for _ in range(max_iterations):
y = f(x0)
yprime = f_prime(x0)
if abs(yprime) < epsilon: # 분모가 너무 작으면 중단
break
x1 = x0 - y / yprime # 뉴턴 계산 수행
if abs(x1 - x0) <= tolerance: # 결과가 허용 오차 이내면 중단
return x1 # x1은 허용 오차 및 최대 반복 횟수 내의 해
x0 = x1 # 다음 반복을 위해 x0 업데이트
return None # 뉴턴 방법이 수렴하지 않음
```
다음은 도함수 `f_prime`을 갖는 함수 `f`의 근을 찾기 위한 파이썬 (버전 3.x) 프로그래밍 언어로 구현한 뉴턴 방법의 예시이다.
초기 추측값은 이고 함수는 이므로 이다.
뉴턴 방법의 각 새로운 반복은 `x1`으로 표시된다. 계산 중에 분모(`yprime`)가 너무 작아지는지(`epsilon`보다 작은지) 확인하는데, 이는 인 경우에 해당하며, 그렇지 않으면 많은 양의 오류가 발생할 수 있기 때문이다.
참조
[1]
서적
Isaac Newton on Mathematical Certainty and Method
MIT Press
2009
[2]
간행물
Historical Note on the Newton-Raphson Method of Approximation
https://www.jstor.or[...]
1911
[3]
간행물
Historical Development of the Newton-Raphson Method
https://www.jstor.or[...]
1995
[4]
웹사이트
Takakazu Seki - Biography
https://mathshistory[...]
2024-11-27
[5]
서적
A Treatise of Algebra, both Historical and Practical
http://www.e-rara.ch[...]
Richard Davis
1685
[6]
서적
Analysis Æequationum Universalis
https://archive.org/[...]
Thomas Bradyll
1697
[7]
웹사이트
Accelerated and Modified Newton Methods
http://mathfaculty.f[...]
2016-03-04
[8]
간행물
A Theoretical Introduction to Numerical Analysis
https://books.google[...]
CRC Press
[9]
간행물
[10]
서적
Solution of equations in Euclidean and Banach spaces
Academic Press
[11]
문서
Ortega and Rheinboldt, Section 13.3
[12]
서적
Iterative methods for the solution of equations
Prentice-Hall, Inc.
[13]
문서
J. E. Dennis, Jr. and Robert B. Schnabel. Numerical methods for unconstrained optimization and nonlinear equations. SIAM
[14]
문서
Anthony Ralston and Philip Rabinowitz. A first course in numerical analysis, second edition
[15]
문서
Yuri Nesterov. Lectures on convex optimization, second edition. Springer Optimization and its Applications, Volume 137.
[16]
문서
Kenneth L. Judd. Numerical methods in economics. MIT Press
[17]
서적
Numerical Analysis
https://archive.org/[...]
Prindle, Weber & Schmidt
1981-07
[18]
서적
Practical Numerical Analysis
https://archive.org/[...]
John Wiley & Sons
1995
[19]
서적
Computational Mathematics
https://archive.org/[...]
MIR Publishers
1981
[20]
서적
Numerical Methods in Engineering with Python 3
https://www.cambridg[...]
Cambridge University Press
2013-03
[21]
서적
Applied and Computational Complex Analysis
Wiley
1974
[22]
간행물
A chaotic search for {{mvar|i}}
1991-01
[23]
간행물
Families of rational maps and iterative root-finding algorithms
https://dash.harvard[...]
1987
[24]
간행물
How to find all roots of complex polynomials by Newton's method
http://dx.doi.org/10[...]
2001-10
[25]
서적
Numerical Analysis: Historical Developments in the 20th Century
North-Holland
[26]
간행물
The inverse function theorem of Nash and Moser
[27]
서적
Partial differential relations
Springer-Verlag
[28]
간행물
Mean value theorems in $q$-calculus
https://www.emis.de/[...]
2002
[29]
간행물
[30]
서적
Introduction to numerical analysis
https://archive.org/[...]
1980
[31]
서적
Computation of Special Functions
Wiley
1996
[32]
간행물
Global Convergence of a Modified Newton Iteration for Algebraic Equations
1982
[33]
문서
Moore, R. E. (1979). ''Methods and applications of interval analysis'' (Vol. 2). Siam.
[34]
문서
Hansen, E. (1978). Interval forms of Newtons method. ''Computing'', 20(2), 153–163.
[35]
서적
Convex optimization
Cambridge University Press
[36]
웹사이트
Newton's Method(Wolfram Math World)
http://mathworld.wol[...]
2010-06-08
[37]
간행물
On Newton’s Method of Approximation
1916-09-15
[38]
서적
数値解析入門(増訂版)
サイエンス社
[39]
서적
Iterative Solution of Nonlinear Equations in Several Variables
Academic Press
1970
[40]
서적
Cで学ぶ数値計算アルゴリズム
共立出版
[41]
간행물
ニュートン近似の改良
日本評論社
1980-05
[42]
간행물
平野の変形Newton法の大域的収束性
http://id.nii.ac.jp/[...]
情報処理学会
1980-11
[43]
서적
非線形解析入門
コロナ社
[44]
서적
精度保証付き数値計算
コロナ社
[45]
서적
精度保証付き数値計算の基礎
コロナ社
2018
[46]
웹사이트
Interval Newton Method
http://www2.math.uni[...]
[47]
간행물
Mean value theorems in g-calculus
http://scindeks-clan[...]
Mathematical Society of Serbia, Belgrade
2002-01
[48]
간행물
On q-Newton–Kantorovich method for solving systems of equations
https://www.research[...]
Elsevier
2005-09-15
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com