뉴턴법/뉴턴-랩슨법의 이해와 활용(Newton's method)

뉴턴법/뉴턴-랩슨법 하면 대부분 방정식의 근사해를 구하는 방법 정도로 알고 있지만 뉴턴법을 확장하면 연립방정식의 해, 나아가서는 비선형(non-linear) 모델의 파라미터를 구하는 문제까지 확장될 수 있습니다.

뉴턴법/뉴턴랩슨법 뿐만 아니라 가우스-뉴턴법, 비선형 최소자승법은 모두 연관된 내용이기 때문에 이들을 한꺼번에 알아두면 좋을 것 같습니다. 그러면 구체적인 예와 함께 이들을 하나씩 살펴보도록 하겠습니다.

1. 뉴턴법(Newton's Method)의 이해

2. 뉴턴법(Newton's Method)의 특징 및 제약사항

3. 뉴턴법의 활용

4. 가우스-뉴턴 방법을 이용한 연립방정식의 근사해 구하기

5. 가우스-뉴턴 방법을 이용한 비선형 최소자승법

6. 비선형 최소자승법 예제: 원 근사

1. 뉴턴법(Newton's Method)의 이해

뉴턴법(Newton's method)은 뉴턴-랩슨법(Newton-Raphson method)이라고도 불리는데, 방정식 f(x) = 0의 해를 근사적으로 찾을 때 유용하게 사용되는 방법이다.

예를 들어, 아래와 같이 x에 대한 7차 방정식이 있는데 이건 머 인수분해도 안되고 도저히 정상적인 방법으로는 해를 구하기 힘들다. 이럴 때 사용해 볼 수 있는 방법이 뉴턴법이다.

뉴턴법은 기본적으로는 f'(a)가 x = a에서의 접선의 기울기라는 미분의 기하학적 해석을 이용한다. f(x) = 0인 x를 찾고 싶은데 그러한 해를 전혀 모른다고 하자.

그럴 땐, 일단은 아무값이나 x = a를 넣고 f(a)의 값을 살펴본다. 만일 f(a)>0이고 f'(a)>0라면 f(x) = 0이 되는 x는 a보다 작은 값일 것이다 (머리 속으로 그래프를 그려보시길..). 따라서 다음에는 a보다 작은 값을 넣고 함수값을 살펴본다. 그런데, 해가 a보다 작은 곳에 있다는 것은 알겠는데 얼마나 값을 줄여야 하는 걸까? 만일 x=a에서의 |함수값|이 작고 접선의 기울기가 가파르다면 바로 근처에 해가 있을 것이고, 반대로 |함수값|이 크고 접선 기울기가 완만하다면 멀리 떨어진 곳에 해가 존재할 것이다.

뉴턴법(Newton's method)/뉴턴-랩슨법(Newton-Raphson method)은 현재 x값에서 접선을 그리고 접선이 x축과 만나는 지점으로 x를 이동시켜 가면서 점진적으로 해를 찾는 방법이다.

아래 그림을 예로 들면, 만일 처음에 x = x1에서 시작했다면 그 다음 x값은 x2가 될 것이고, x2에서 다시 접선을 그려보면 점차 실제 해에 가까워지는 것을 확인할 수 있다. 이와 같은 과정을 계속 반복하다보면 해를 찾을 수 있다는 게 뉴턴법(Newton's method)이다.

뉴턴법(Newton's method)/뉴턴-랩슨법(Newton-Raphson method)을 수식화하면 아무 값이나 초기값 x1에서 시작해서 다음 수식에 따라 수렴할 때까지 계속 x를 이동시켜 나간다 이다.

종료 조건은 x 값의 변화가 거의 없을 때까지이다. 즉, |x^t+1 - x^t|이 매우 작은 값이면 뉴턴법을 종료하고 x = x^t+1이 해, 즉 f(x^t+1) = 0 라고 생각하는 것이다.

2. 뉴턴법(Newton's Method)의 특징 및 제약사항

뉴턴법은 물론 만능이 아니다. 해가 없으면 당연히 못 찾는 것이고, 해가 있더라도 뉴턴법으로 해를 못 찾을 수도 있다. f(x)가 연속이고 미분가능해야 한다는 조건도 필요하다. 만일 f(x) = 0인 해가 여러 개 있다면 뉴턴법은 그중 하나의 해를 찾아줄 뿐이다. 또한 해가 여러 개인 경우에는 초기값 x1을 어떻게 주느냐에 따라서 뉴턴법으로 찾아지는 해가 달라질 수 있다.

특히나 뉴턴법을 사용할 때 가장 어려운 점 중의 하나가 초기값을 어떻게 선택하느냐이다. 똑같은 문제라 하더라도 초기값을 잘 주면 금방 해를 찾을 수 있지만 잘못 주면 시간이 오래 걸리거나 아에 해를 찾지 못할 수도 있다. 생각할 수 있는 한 방법은 먼저 일정한 간격으로 x값을 변화시키면서 함수값의 변화를 본 후 함수값의 부호가 바뀌는 구간마다 보간법(interpolation)으로 초기값을 잡는 것이다.

3. 뉴턴법의 활용

뉴턴법/뉴턴-랩슨법은 위와 같이 (i) 방정식 f(x) = 0의 해를 구할 때, (ii) 서로 다른 두 함수 g(x)와 h(x)의 값이 같게 되는 x를 구할 때 (f(x) = g(x) - h(x)로 놓고 f(x) = 0인 x를 구한다), (iii) f(x)의 최소값 또는 최대값을 구할 때 활용될 수 있다. 일반적으로 함수는 극점에서 최대값 또는 최소값을 가지므로 f'(x) = 0인 x를 뉴턴법으로 구한 후 f(x)에 대입하면 f(x)의 최대값/최소값을 구할 수 있다. f'(x) = 0인 x는 xn+1 = xn - f'(x)/f''(x)로 구한다.

위에 나열한 것들은 뉴턴법의 일반적인 활용법들이고 이런 거 외에도 그냥 알아두면 어딘가는 써 먹을 데가 있을 것이라 생각합니다. 예를 들어, 카메라에서 왜곡보정된 영상좌표를 구할 때에도 뉴턴법이 활용될 수 있습니다.

4. 가우스-뉴턴(Gauss-Newton) 방법을 이용한 연립방정식의 근사해 구하기

(가우스-뉴턴 방법에 대한 내용은 조금 어려울 수 있으니 글 끝 부분에 있는 원 근사 예제와 함께 보면 좋을 것 같습니다)

연립방정식의 근사해를 구할 때는 가우스-뉴턴(Gauss-Newton) 방법을 사용하는데, 가우스-뉴턴 방법은 뉴턴법을 연립방정식으로 확장한 것으로 볼 수 있다. 다음과 같이 변수의 개수가 n, 식의 개수가 m개인 (m>=n) 다변수 연립방정식이 있다고 하자 (기본적으로 연립방정식은 변수가 여러 개 일때 사용하는 것임).

위 연립방정식을 행렬 표현으로 바꾸기 위해 X = (x1, .., xn), F(X) = (f1(X), ..., fm(X))라 놓으면 위 식은 F(X) = 0와 같은 행렬식 형태가 된다. 즉, 위에서 설명한 뉴턴법을 똑같이 적용할 수 있는 형태가 된 것이다. 이 때, F는 F: Rⁿ -> R^m인 다변수 다차원 함수로 볼 수 있으며 이에 대한 미분은 Jacobian 행렬로 표현된다 (아래와 같은 행렬을 Jacobian 행렬이라 부른다)

이제 F를 함수, X를 변수로 보고 원래 뉴턴법 식을 그대로 쓰면 다음과 같은 형태가 될 것이다.

그러나, 행렬(J)로 직접 나눌 수는 없기 때문에 물론 위 식은 잘못된 수식이다. 대신, F/J는 JP = F인 P를 구함으로써 계산할 수 있다. 즉, 연립방정식에 대한 뉴턴법 수식은 다음과 같다.

계산 방법을 좀더 부연 설명하면, 현재의 X 추정값에 대해 J와 F값을 계산한 후에 JP = F인 P를 구한다. 구한 P를 이용해서 X = X - P로 X를 업데이트한다. 업데이트된 X로 J, F를 다시 계산하고 P도 구한다. 이와 같은 과정을 X가 수렴할 때까지 반복한다 이다. 참고로, JP = F인 P는 최소자승법을 이용하면 P = (J^TJ)^-1J^TF와 같이 계산된다.

정리하면, 가우스-뉴턴(Gauss-Newtorn) 방법은 어떤 초기값(해에 대한 초기 추정치) X⁰를 시작점으로 다음과 같이 X를 갱신함으로써 근사해를 찾는 방법이다.

수학적 유도) 참고로 F(X) = 0인 X를 구하는 문제는 테일러 급수 를 이용하면 다음과 같이 유도할 수 있습니다. 테일러 급수에 대한 내용은 테일러 급수의 이해와 활용 (Taylor series)을 참조하기 바립니다.  매 가우스-뉴턴 단계에서 F(X)를 테일러 급수를 이용하여 근사시키면 F(X) ~ F(X^k) + J(X^k)(X-X^k)가 됩니다 (2차 이상의 항은 무시했을 때). 따라서, 현재 단계에서 F(X) = 0으로 만드는 X는  F(X ^k ) + J(X ^k )(X-X ^k ) = 0인 X이며, 이것을 X에 대해 풀면 X = X^k - J^-1F (J의 역행렬이 존재하는 경우), X = X^k -  (J ^T J) ^-1 J ^T F (J의 역행렬이 존재하지 않는 경우 pseudo inverse를 이용)가 됩니다.

5. 가우스-뉴턴 방법을 이용한 비선형 최소자승법

최소자승법의 이해와 다양한 활용예 (Least Square Method)에서 설명한 내용은 선형 최소자승법 (linear least square method)에 대한 내용이었습니다. 비선형 least square 문제에 대해서는 여기서 설명드린 가우스-뉴턴 방법을 적용하면 파라미터를 추정할 수 있습니다. 다만, 선형 least square 문제는 해가 유일하게 결정되지만 비선형 least square 문제는 해가 근사적으로 구해지며, 초기값에 따라 해를 구하지 못할 수도 있습니다.

관측값을 (xi, yi), 모델 파라미터를 β = ( β1,  β2, ...,  βm) , 모델을 y = f(x, β)라 할때, 알다시피 최소자승법은 residual인 ri = yi - f(xi, β)들의 제곱합을 최소로 하는 모델 파라미터 β를 찾는 방법입니다.

이는, 원래는 다음과 같은 연립 방정식을 푸는 문제이기 때문에 앞서 설명한 '가우스-뉴턴법을 이용한 연립방정식의 근사해 구하기'를 이용해서 β를 구할 수 있습니다 (구체적 예는 아래의 원 근사 예제 참조).

6. 비선형 최소자승법 예제: 원 근사

2차원 평면 상의 점  (x1, y1), ..., (xm, ym)을 근사하는 원 방정식을 구하는 문제를 가우스-뉴턴 방법으로 한번 구해보겠습니다. 이 경우, residual은 다음과 정의됩니다.

그러면, 가우스-뉴턴 방법을 적용하기 위한 행렬들은 다음과 같이 계산됩니다.

, ,

이제 X를 적당한 값으로 초기화한 후에, 가우스-뉴턴 방법을 반복적으로 적용하면 원하는 원의 방정식을 구할 수 있게 됩니다.

by 다크 프로그래머