세 점을 지나는 원의 방정식은 어떻게 될까?

지난 번 포스팅한 최소자승법의 이해와 다양한 활용예 (Least Square Method)에서 원의 방정식을 근사시키는 예제를 적다가 생각났던 내용이다. 세 점을 지나는 원의 방정식은 유일하게 결정될텐데, 그 방정식은 무엇일까? 하는 의문에 식을 구해보게 되었다. 세 점을 지나는 원의 방정식을 알아두면 여러모로(RANSAC으로 원의 방정식을 구할 경우 등) 쓸모가 있을 것이다.

두 점을 지나는(지름의 양 끝점으로 하는) 원의 방정식은 (x-x1)(x-x2)+(y-y1)(y-y2)=0과 같이 깔끔하게 식이 구해진다. 세 점을 지나는 원의 방정식도 이렇게 식이 구해지지 않을까? 내심 기대를 하면서 식을 구해보았지만 결과는 글 끝에 있듯이 그렇게 이쁘지는 않았다 ^^

세 점 A(x1, y1), B(x2, y2), C(x3, y3)를 지나는 원의 방정식을 구하는 문제는 삼각형 ABC의 외접원을 구하는 문제와 같다. 이 외접원의 중심은 삼각형의 어느 두 변의 수직이등분선들이 만나는 지점에 위치한다. 즉, 선분 AB의 수직 이등분선과 선분 BC의 수직이등분선, 그리고 선분 CA의 수직이등분선은 모두 한 점에서 만나게 되는데, 이 교점이 외접원의 중심이다. 이러한 사실은 자신이 그림을 그려보면 쉽게 이해할 수 있다.

어느 두 변을 가지고 시작해도 결과는 같지만 여기서는 변 AB, BC를 가지고 외접원의 중심을 구해보도록 하겠다.

먼저, 선분 AB에 대한 수직 이등분선의 방정식은 다음과 같다.

또한 선분 BC에 대한 수직 이등분선의 방정식은 다음과 같다.

선분 AB에 대한 수직이등분선의 방정식은 선분 AB의 중점을 지나면서 선분 AB에 수직인 직선이다. 이러한 직선의 방정식은 벡터방정식을 이용하면 위와 같은 식을 얻을 수 있다. 먼저, 벡터 AB는 (x2-x1, y2-y1)이고 AB의 중점을 지나는 벡터는 (x-(x1+x2)/2, y-(y1+y2)/2)이다. 두 벡터의 내적을 0으로 놓으면 위 식을 얻을 수 있다.

위 연립방정식을 행렬식으로 표현해 보면 다음과 같다.

이제 위 방정식을 만족하는 해, 즉 외접원의 중심은 다음과 같이 계산된다.

역행렬이 존재하지 않는 경우, 즉 ad - bc = (x2-x1)(y3-y2) - (y2-y1)(x3-x2) = 0 인 경우에는 세 점을 지나는 원의 방정식이 존재하지 않는 경우이다. 이러한 경우는 세 점이 일직선상에 있거나 어느 두 점이 서로 같은 경우이다.

이렇게 원의 방정식을 구했을 때 장점은 선분 AB, BC, CA가 x축이나 y축에 수평인 경우에도 원의 방정식을 구할 수 있다는 점, 그리고 원의 존재여부를 역행렬 조건을 이용하여 손쉽게 알 수 있다는 점 정도가 되겠다.

원의 중심이 구해지면 원의 반지름은 손쉽게 구할 수 있을 것으로 생각한다..

☞ 이 글은 http://blog.naver.com/daesil11/80134961814 글에 대한 엮인글(트랙백)로 작성한 글입니다.

by 다크 프로그래머

테일러 급수(Taylor series)에 대한 내용은 이미 인터넷에 좋은 글들이 많습니다. 그럼에도 이렇게 다시 글을 쓰는 이유는 스스로도 애매한 부분이 많기 때문입니다. 그래서 공부하는 셈치고 관련 내용들을 쭉 정리하게 되었습니다. 테일러 급수(Taylor series)가 무엇이고 왜 필요한지, 그리고 어떻게 활용되는지 하나씩 살펴보도록 하겠습니다.

1. 테일러 급수(Taylor series)의 이해

2. 테일러 정리(Taylor's theorem)

3. 테일러 급수의 활용 / 필요한 이유

4. 테일러 급수에 대한 생각

5. Ratio Test

1. 테일러 급수(Taylor series)의 이해

테일러 급수(Taylor series) 또는 테일러 전개(Taylor expansion)는 어떤 미지의 함수 f(x)를 아래 식과 같이 근사 다항함수로 표현하는 것을 말합니다. 

 --- (1)

테일러 급수에서 주의해야 될 사항은 좌변과 우변이 모든 x에 대해 같은 것이 아니라 x = a 근처에서만 성립한다는 점입니다. 즉, x가 a에서 멀어지면 멀어질수록 f(x) = p(x)로 놓는 것은 큰 오차를 갖게 됩니다. 한편, 근사다항식의 차수는 높으면 높을수록 f(x)를 좀더 잘 근사하게 됩니다.

테일러 급수는 결국 x = a에서 f(x)와 동일한 미분계수를 갖는 어떤 다항함수로 f(x)를 근사시키는 것입니다. 위 식에서 f(a) = p(a), f'(a) = p'(a), f''(a) = p''(a), ... 임은 쉽게 확인할 수 있을 것입니다. 테일러 급수를 이용해 이와같이 x = a에서 미분계수를 일치시키면 x = a 뿐만 아니라 그 주변의 일정 구간에서도 f(x)와 p(x)가 거의 일치되게 됩니다.

그런데 문제에 따라서는 f(x)를 1차 또는 2차까지만 테일러 전개하는 경우도 많습니다. 예를 들어, f(x)를 2차 다항함수로 근사할 경우에는

 --- (2)

와 같이 놓고 Q(x)를 0처럼 생각(무시)해 버립니다. 이 경우, f(x)를 무한차수 다항함수로 근사하는 것 보다는 근사오차가 크겠지만, x가 충분히 a에 가까운 경우에는 근사오차가 거의 없다고 볼 수 있습니다.

참고로, f(x)에 대한 테일러 급수/전개는 다음과 같은 형태로도 표현될 수 있습니다 (잘 보면 형태만 다를 뿐 결국 같은 말임)

 --- (3)

2. 테일러 정리(Taylor's theorem)

테일러 급수와 관계된 것으로 테일러 정리라는게 있습니다. 테일러 정리는 n번 미분가능한 함수 f(x)에 대해

 --- (4)

를 만족하는 실함수 h(x)가 반드시 존재한다는 것입니다. (증명은? wikipedia를 참조하시길..)

즉, 테일러 정리(Taylor's theorem)는 어떤 함수를 유한차수(n차)의 다항함수로 근사시킬 수 있는 수학적 근거를 제공합니다. 이 때, h(x)(x-a)ⁿ은 근사오차를 나타냅니다.

3. 테일러 급수의 활용 / 필요한 이유

테일러 급수가 필요한 이유는 쉽게 말하면 우리가 잘 모르거나 복잡한 함수를 다루기 쉽고 이해하기 쉬운 다항함수로 대체시키기 위함입니다. 또한 어떤 함수를 테일러 급수로 표현하면 그 함수의 특성을 분석하기가 좀더 용이해지기 때문입니다. 그럼 그 구체적 활용예들을 하나씩 살펴보도록 하겠습니다.

A. 정적분의 계산

부정적분을 계산하기 힘든 함수의 경우에 아래와 같이 테일러 급수를 활용하면 정적분의 계산값을 근사적으로 구할 수 있습니다.

 --- (5)

위 식에서 sin(x²)의 테일러 급수는 sin(t)의 t = 0에서의 테일러 전개에 t = x²을 대입하여 얻어진 식이며, 적분 구간이 [0, 1]이기 때문에 x = 0에서의(즉, a = 0) 테일러 급수를 사용해도 근사오차가 크지 않습니다.

B. 함수의 점근(asymptotic) 특성 파악

테일러 급수를 활용하면 함수(특히 삼각함수, 지수함수, 로그함수와 같은 초월함수)의 점근적 특성을 손쉽게 파악할 수 있습니다. 예를 들어, 아래와 같이 x = 0 근처에서 sinx ~ x 임을 테일러 급수를 이용하면 쉽게 알 수 있습니다.

 --- (6)

C. 문제 또는 모델의 단순화

테일러 급수의 가장 일반적인 활용예로 볼 수 있습니다. 즉, 어떤 복잡한 또는 잘 모르는 함수가 있을 때, 이 함수를 저차의(1~3차) 다항함수로 근사하여 사용함으로써 문제 또는 모델을 단순화시키는데 테일러 급수가 활용될 수 있습니다. 구체적인 예를 들기는 어렵지만 테일러 급수는 논문 등에서 어떤 이론이나 주장에 대한 논리적 근거를 단순화하여 설명할 때 유용하게 사용되는 기법 중의 하나입니다. 한 활용예로 가우스-뉴턴(Gauss-Newton) 방법을 증명하는데 테일러 급수가 활용됩니다. 이에 대한 내용은 뉴턴법/뉴턴-랩슨법의 이해와 활용(Newton's method)을 참조하기 바랍니다.

D. 기타 활용예

테일러 급수는 미분방정식을 풀 때, 또는 초월함수의 함수값을 계산할 때도 활용될 수 있습니다.

예를 들어, 미분방정식 y' = y, y(0) = 1은 y를 y = a0 + a1x + a2x² + ... 라 놓고 풀면 y(0) = 1에서 a0 = 1, y' = y에서 a1 + 2a2x + 3a3x² + ... = a0 + a1x + a2x² + ...이 됩니다. 즉, a1 = a0 = 1, a2 = a1/2 = 1/2, ... 이런 식으로 y를 구할 수 있겠죠. 참고로, 이렇게 구한 y는 e^x를 테일러 전개한 식과 같습니다.

다른 예로, sinx의 값을 컴퓨터로 계산한다고 했을 때, sinx = x - x³/3! + x⁵/5! - ... 와 같이 테일러 급수를 이용하여 함수값을 계산하면 몇 번의 계산만으로도 매우 정밀한 결과값을 얻을 수 있습니다.

4. 테일러 급수 근사의 유효 범위

어떤 함수에 대한 테일러 급수 근사는 x = a 근처에서만 유효합니다. 그렇다면 x = a에서 구한 테일러 급수가 어느 정도의 구간까지 유효할 것일까요? 고차함수로 근사할수록 구간이 넣어지겠지만 그건 함수마다, 그리고 얼마나 고차 함수로 근사를 했느냐에 따라 달라질 것입니다. 그 오차를 정량적으로 구할 수도 있겠지만 가능하면 관심 지점마다 별도로 테일러 급수를 계산하여 사용하는 것이 좋겠습니다.

5. Ratio Test (2014.9.13 추가된 내용)

댓글로 문의해 주신 분이 있어서 Ratio Test에 대한 내용을 추가합니다(참고자료: http://www.haverford.edu/physics/MathAppendices/Taylor_Series.pdf). 

Ratio Test는 원래 무한급수 a1 + a2 + ... 가 수렴하는지 여부를 |a_n+1/a_n|에 대한 극한값을 이용하여 간단하게 테스트할 수 있는 방법인데 테일러 급수에도 동일하게 적용할 수 있습니다.

테일러 급수에 대한 Ratio Test: 만일 어떤 함수 f(x)에 대해 x = a에서 구한 테일러 근사 다항식을 p(x) = p1 + p2 + p3 + ... + pn 라 하면 n→∞ 일 때, p(x) = f(x)가 되는 수렴구간은 ρ = lim_n→∞|p_n+1/p_n| < 1 인 x 구간이고, ρ>1 이면 발산, ρ = 1이면 수렴 또는 발산한다.

예를 들어, f(x) = ln(1+x)인 경우 x = 0에서의 테일러 급수는 다음과 같습니다.

ln(1+x) = x - (1/2)x^2 + (1/3)x^3 -... + (-1)^(n+1) * x^n/n + ...   --- (7)

이 때, ρ<1인 구간을 구해보면

ρ = lim_n→∞|(-1)^(n+2) * x^(n+1)/(n+1)) / (-1)^(n+1) * x^n/n)| = lim_n→∞|-(n/(n+1))x| = |x|<1 --- (8)

이므로 -1<x<1인 구간에서는 식 (7)의 테일러 전개가 ln(1+x)에 수렴함을 알 수 있습니다. 즉 ln(1+x)의 경우, x = 0에서 구한 테일러 근사 다항식은 다항식의 차수가 증가하면 x = 0 뿐만 아니라 -1<x<1 구간까지도 원래 함수ln(1+x)와 일치해짐을 알 수 있습니다.

by 다크 프로그래머

(2024.12.9) '뉴턴법'이라는 용어는 방정식 f(x) = 0의 해를 구하는 문제와 수학적 최적화(optimization) 문제에 모두 사용될 수 있습니다. 그런데, 방정식 f(x) = 0의 해를 구하는 문제는 '뉴턴법' 보다는 '뉴턴-랩슨법'이라고 부르는 것이 보다 일반적입니다. 이 글은 '뉴턴-랩슨법'에 대한 글이며, 최적화 문제에서의 '뉴턴법'은 https://darkpgmr.tistory.com/149 글을 참조하기 바랍니다.

뉴턴법/뉴턴-랩슨법 하면 대부분 방정식의 근사해를 구하는 방법 정도로 알고 있지만 뉴턴법을 확장하면 연립방정식의 해, 나아가서는 비선형(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 다크 프로그래머