뉴턴 방법

함수 $f$에 부과되는 유일한 요구 사항은 적어도 하나의 근을 가지며 탐색 구간에서 연속이고 미분 가능해야 한다는 것입니다.

#알고리즘 설명

알고리즘은 어떤 초기 근삿값 $x_0$에서 시작하여, 점 $x = x_i$에서 그래프에 접선을 긋고 그 접선이 $x$축과 만나는 교점의 좌표를 다음 근삿값 $x_{i+1}$로 삼는 방식으로 반복적으로 더 나은 해를 구해 나갑니다. 직관적으로 말하면, 함수 $f$가 “좋은” 함수이고 $x_i$가 이미 근에 충분히 가깝다면 $x_{i+1}$은 근에 더욱 가까워집니다.

$x_i$에 대한 교점을 구하려면 접선의 방정식을 0으로 놓아야 합니다:

뉴턴 방법은 계산 수학에서 매우 중요합니다. 대부분의 경우 방정식의 수치해를 구하는 데 바로 이 방법이 사용됩니다.

#제곱근 구하기

구체적인 예로, 다음 방정식의 해를 구하는 문제로 바꾸어 표현할 수 있는 제곱근 구하기 문제를 살펴봅시다:

어떤 주어진 정밀도 $\epsilon$으로 근을 계산해야 한다면, 매 반복마다 다음과 같이 해당 검사를 수행할 수 있습니다:

const double eps = 1e-9;

double sqrt(double n) {
    double x = 1;
    while (abs(x * x - n) > eps)
        x = (x + n / x) / 2;
    return x;
}

이 알고리즘은 많은 함수에 대해 올바른 답으로 잘 수렴하지만, 이것이 확실하고 증명 가능하게 일어나는 것은 특정 부류의 함수(예를 들어, 볼록 함수)에 대해서뿐입니다. 또 다른 문제는 수렴이 일어난다면 그 수렴이 얼마나 빠른가 하는 것입니다.

#수렴 속도

$x_0 = 1$에서 시작하여 $2$의 제곱근을 구하는 뉴턴 방법을 실행하고, 각 반복 후에 앞자리 숫자가 몇 개나 정확한지 살펴봅시다:

1.0000000000000000000000000000000000000000000000000000000000000
1.5000000000000000000000000000000000000000000000000000000000000
1.4166666666666666666666666666666666666666666666666666666666675
1.4142156862745098039215686274509803921568627450980392156862745
1.4142135623746899106262955788901349101165596221157440445849057
1.4142135623730950488016896235025302436149819257761974284982890
1.4142135623730950488016887242096980785696718753772340015610125
1.4142135623730950488016887242096980785696718753769480731766796

반복할 때마다 정확한 자릿수가 대략 두 배로 늘어나는 것을 확인할 수 있습니다. 이처럼 뛰어난 수렴 속도는 단순한 우연이 아닙니다.

수렴 속도를 수치적으로 추정하기 위해 $i$번째 반복에서의 작은 상대 오차 $\delta_i$를 생각하고, 다음 반복에서 오차 $\delta_{i+1}$이 얼마나 더 작아지는지 살펴봅시다.

여기서는 오차 $d_i$가 작다는 가정을 이용하여 $(1 + \delta_i)^{-1}$을 점 $0$에서 테일러 급수로 전개했습니다. 수열 $x_i$가 $x$로 수렴하므로, 충분히 큰 $n$에 대해 $d_i \ll 1$이기 때문입니다.

마지막으로 $\delta_{i+1}$을 정리하면 다음을 얻습니다.

이는 해에 이미 가까워졌을 때 매 반복마다 상대 오차가 대략 제곱된 뒤 절반으로 줄어든다는 것을 의미합니다. 로그 $(- \log_{10} \delta_i)$는 $x_i$의 올바른 유효 숫자 개수와 대략 같으므로, 오차를 제곱하는 것은 답의 유효 숫자가 두 배로 늘어나는 것에 해당하며, 이는 앞서 관찰한 바와 같습니다.

이 성질을 이차 수렴이라고 하며, 이는 제곱근을 구하는 경우에만 해당하는 것이 아닙니다. 엄밀한 증명은 연습 문제로 남겨 두고, 일반적인 경우에 다음이 성립함을 보일 수 있습니다.