한빛출판네트워크

작성: 한동훈(traxacun at unitel.co.kr)

작성일: 2003. 3. 12 - 26

지난 시간에는 분할 정복(Divide & Conquer)에 대해서 살펴보았으며 이번 시간에는 분할 정복의 연장선상에 있는 근찾기(Root Finding)와 미적분법에 대해서 살펴보고, 이러한 알고리즘을 보다 유연성있게 적용하기 위해 delegate를 어떻게 사용하는지 살펴볼 것이다.

근찾기 알고리즘(Root Finding)

방정식의 근을 찾는 알고리즘은 다양하지만 여기서는 이분법(Bisection)과 뉴튼-랩슨(Newton-Rahpson)법에 대해서만 소개할 것이다. 이외에도 방정식의 근을 찾는 알고리즘으로는 Falsi 법이나 Secant 법 등이 소개되고 있으나 실제로 가장 널리 쓰이는 뉴튼-랩슨 법을 자세히 살펴볼 것이다.

이분법(Bisection)

이분법은 중간값 정리에서 시작한다.

중간값 정리를 그림으로 나타내면 다음과 같다.

그림1. 중간값 정리

위와 같은 함수에서 x1과 x2의 값을 곱하면 음수이므로(즉, 두 함수의 부호가 서로 다르므로) 두 구간 사이에 근이 있다는 것을 알 수 있다. 다시 구간을 mid와 x2로 정의하고 값을 비교하면 결과를 구할 수 있으며, 두 구간의 차이가 0.00001 보다 작으면 근을 찾은 것으로 간주하면 된다. 다음과 같은 루프안에서 코드를 수행하면 된다.

이분법에서는 중간값과 x1, x2 중에 어느 구간에 근이 존재하는지 결정해야 한다. 그러나 이분법은 근의 개수가 짝수, 중근, 발산의 경우에는 올바른 근을 찾아내지 못한다. 이분법은 이미 함수의 형태를 알고, 근이 존재하는 구간을 구한 경우에 쓸 수 있는 방법이지만, 근에 수렴하는 속도 즉, 근을 찾아내는 시간이 오래걸리는 방법이므로 다른 알고리즘을 사용한다.

이분법 또한 잘 알려진 분할 정복 기법의 예라는 것을 기억하기 바란다.

뉴튼-랩슨(Newton-Rahpson) 법

이 방법은 뉴튼법으로 소개되기도 하며, 미적분학의 미분의 소개부분에서 소개되는 방법이기도 하다. 이 방법은 근을 찾기 위해 미분을 이용하기 때문에 매우 빠른 수렴 속도를 갖는다. 실제로 뉴튼-랩슨법은 대부분의 경우에 이분법, Falsi, Secant 보다 빠른 계산 속도를 가지며, 여러분이 사용하는 공학용 계산기에도 쓰인다.

그림2. 뉴튼-랩슨법

그림에서 알 수 있는 것처럼 초기값 x0를 정해주면 그 위치에서의 기울기(미분값)를 구해서 새로운 점 x1을 구하며, 점 x1에서도 같은 방법으로 점 x2를 구하는 것을 알 수 있다. 그림에서 볼 수 있는 것처럼 근으로 수렴하는 속도가 매우 빠르다는 것을 알 수 있다. 뉴튼-랩슨 법의 정의는 다음과 같다.

그림3. 뉴튼-랩슨법의 정의

수식만으로는 이해가 잘 가지 않을테니 를 구하는 것을 예로 들어보자. 이 값을 어떻게 구하는지 궁금하지 않은가? 의 값을 구한다는 것은 다음 방정식을 푸는 것과 같다.

뉴튼-랩슨법은 함수의 미분을 필요로 한다. 위 함수를 f(x)라 하면 전체를 다음과 같이 정의할 수 있다.

초기값을 이라 할 때 그림3의 뉴튼-랩슨법의 정의대로 계산한 결과를 표로 나타내면 다음과 같다.

표1. 뉴튼-랩슨법을 이용한 를 계산하는 과정

위 계산이 맞는지 확인하기 위해 뉴튼-랩슨법으로 방정식을 구하는 C# 코드를 작성하면 다음과 같다.

그림4. newton.cs의 소스

이 오차를 나타내기 때문에 이 값이 0.00001 보다 작으면 충분히 근에 근접했다고 판단하여 루프를 끝낸다. 허용한계(Tolerance)를 보다 작게하면 보다 정확한 값을 구할 수 있다. 여기서는 0.0000001을 허용한계로 정의했다. C#에서 1E-07과 같은 지수 표기법을 사용하였다.

while 루프에서 직접 값을 계산하여 허용한계보다 값이 큰가를 결정하고 있는데 최적화를 위해서 계산 결과를 루프안에서 임시 변수에 저장하여 이 변수를 조건문에 사용할 수도 있다. 다음은 소스 코드를 컴파일하고 실행한 결과다.

공학용 계산기에서 구한 값과 최종 결과값이 같다는 것을 알 수 있으며 공학용 계산기보다 더 정확한 값을 구할 수 있다는 것을 알 수 있다. 보다 정확한 값을 구하기 위해 허용한계값을 늘릴 수 있으나 머신 입실론(Machine Epsilon)에 의해 허용한계값을 보다 작게 했을 때 오차가 오히려 커지는 경우도 발생할 수 있다. 머신 입실론에 대해서는 C, C++, C#으로 알아본 머신 입실론을 참고하기 바라며, C#에서는 System.Double.Epsilon 속성을 통해 이 값을 출력할 수 있다.

방정식 풀이 심화

근을 찾기 위해 프로그래밍을 이용하는 경우는 비선형 방정식의 근에 근접한 값을 얻기 위한 것이다. 비선형 방정식의 근을 구하는 알고리즘으로는 선형 반복법, 이분법, 뉴튼-랩슨법, Bailey법, Aitken의 델타 제곱법등이 있다. 또한, 여기에서 소개한 것처럼 실근을 구하는 경우가 아닌 중근과 복소근을 구하기 위해서 뉴튼-랩슨법을 사용할 수 있다. 비선형 방정식과 다항 방정식의 실근과 허근을 구하는데 모두 쓸 수 있는 알고리즘이 뉴튼-랩슨법이며 성능 또한 가장 좋다. 이외에 다항 방정식을 풀기위한 알고리즘으로는 조립 제법을 이용한 Lin법이 있다. 관심있는 독자는 수치해석(Numerical Method)과 관련된 도서를 참고하기 바란다.

미분법

어떤 함수의 미분을 계산하는 알고리즘 역시 다양하다. 미분법은 고등학교때 배운 미분법의 정의를 프로그래밍에 적용하면 계산된다. 실제로는 이러한 단순한 미분법 보다는 복잡한 상미방을 풀기 위해 프로그래밍을 사용한다. 여기서는 상미방에 대해서는 소개하지 않는다.(기회가 된다면 Runge-Kutta법 중에 2차 상미방 풀이를 소개하겠지만 독자가 공업수학이나 다른 경로를 통해서 상미방의 풀이에 대해서 알고 있어야하므로 건너뛴다.) 상미방 풀이법에 관심이 있는 독자는 Euler법, Taylor 급수전개, Heun법, Runge-Kutta를 찾아보기 바라며 실제로는 Runge-Kutta법을 가장 많이 사용한다. Runge-Kutta는 가장 강력한 방법이며, 초기치, 경계치 문제등의 해법에 적용된다.

미분법은 Taylor 전개, 차분연산자, 보간다항식을 이용한 방법이 잘 알려져 있으며, 여기서는 테일러(Taylor) 급수의 전개를 이용한다.

그림5. 미분의 정의

많은 독자가 알고 있는 것처럼 미분의 정의는 위와 같다. 위 정의를 프로그램으로 옮길 때 문제가 되는 것은 컴퓨터에는 극한의 개념이 없다는 것이다. 테일러 급수 전개는 어떤 값 h의 근방에 근접한 다항식을 만들어 내는 방법이다.

그림6. 테일러 전개

그림6에서 두번째 항까지 이용하여 를 에 대해서 정리하면 다음과 같다.(테일러 전개는 두번째 항까지 이용해도 충분히 근사한 값이 나오며 보다 정확한 계산이 필요한 경우에 세번째 항까지 이용한다. 세번째 이상의 항을 이용하여 근사식을 구하는 방법은 잘 이용되지 않는다. 이 방법은 계산을 복잡하게 만들고, 연산 과정이 많아지는 만큼 오차가 쌓이기 때문에 보다 정밀한 정확도를 구하기가 어려워지기 때문이다.)

위 식에 O(h)는 오차한계를 나타낸다. 위와 같은 식을 다음 그림에서 알 수 있는 것처럼 전향차분(Forward Difference)이라 한다.

그림7. 전향차분(Forward Difference)

그림8. 후향차분(Backward Difference)

그림9. 중앙차분(Center Difference)

여기서는 보다 정확한 미분값을 얻을 수 있는 중앙 차분을 이용한다. 미분의 정의에 있는 lim을 컴퓨터가 풀 수 있는 수식으로 표현하기 위해 테일러 전개를 사용하였다. 각 수식의 전개는 다음과 같다.

식 (3)을 이용하면 x에서의 미분값을 계산할 수 있다. 다음 소스 코드는 를 에서 일 때 미분값을 구한다. h는 구간을 나타내며 이 구간값이 작을 수록 보다 정확한 미분값을 정할 수 있다. 대부분의 경우에 이면 충분히 적용할 수 있는 미분값을 구할 수 있다.

그림10. Differ.cs

실행결과는 다음과 같다.

결과와 직접 손으로 계산한 결과를 비교하면 맞게 계산 된다는 것을 알 수 있다. 그렇다면 등은 어떻게 하면 계산할 수 있을까? 이들 역시 테일러 전개를 사용하여 계산할 수 있다.

적분법

적분법 역시 미분과 마찬가지로 수학시간에 배웠던 적분의 정의를 그대로 적용하여 계산할 수 있다.

그림11. 적분법

적분의 기본 개념은 면적을 구하기 위해 구간을 잘게 나누고, 나눈 구간의 넓이를 구하여 더하는 것이다. 컴퓨터에는 극한의 개념이 없기 때문에 구간을 얼마나 작게 나누느냐에 따라서 계산 결과의 정확도가 결정된다. 위 그림에서처럼 a와 a+h 구간의 면적을 개산할 때 오차를 줄이기 위해 두 구간의 높이에 대한 평균 즉,

을 높이로 사용한다.

위와 같은 간단한 적분은 사각형을 이용하여 면적을 계산하는 것이며 이를 나타낸 그림과 소스는 다음과 같다.

그림12. 사각형을 이용한 적분

그림13. 사각형을 이용한 적분 소스

실행결과를 보면 정확한 22가 나오지는 않지만 그와 근접한 21.9999999...로 결과가 나오는 것을 알 수 있다. 간격 h를 더 작게하면 실행시간도 오래걸리면서 정확도가 오히려 떨어지는 것을 관찰할 수 있다. 이러한 결과는 루프를 반복한만큼 머신 임계값(machine epsilon)이 오차로 쌓이기 때문이다. 사각형 대신 사다리꼴을 이용하는 방법도 있다. 사다리꼴을 이용하면 사각형을 이용한 방법보다 면적에 근접한 값을 얻을 수 있다고 생각되지만 실제로는 사각형을 이용한 방법이 더 정확한 근을 구해준다. 사각형법은 구간에 따라 실제값보다 더해지거나 빼지는 값이 있어서 어느 정도 보완이 되지만, 사다리꼴은 대부분의 구간에서 실제 면적보다 더 적은 면적을 구하게 되기 때문에 오차가 더 커진다. 이 두 방법 보다 더 정확한 적분을 구하는 방법은 심슨법(Simpson Method)을 이용하는 것이다.

심슨법(Simpson"s Rule)

심슨법은 3개의 점을 지나는 2차 방정식을 구하고, 4개의 점을 지나는 3차 방정식을 구하기 위해 사용하는 라그랑지 보간법(Lagrange interpolation)을 이용한다. 라그랑지 보간법을 이용해서 두 구간의 좌표와 중점(즉, 세 점)을 지나는 2차 방정식을 구하고, 이 방정식을 이용해서 두 구간 사이의 넓이를 구한다. 다시말해, 심슨법은 두 구간 사이의 곡선을 따라서 적분하는 방법이다.

심슨법은 1/3 Rule과 3/8 Rule로 나뉘는데 1/3 Rule은 구간의 시작점과 끝점, 중점의 y 좌표를 이용하여 2차원 곡선을 지나는 곡선의 적분값을 구하는 방법이다. 3/8 Rule은 위와 비슷한 방법으로 구간을 3개로 나누고 4개의 점을 지나는 3차 곡선을 구한뒤에 그 곡선의 적분값을 구하는 방법이다. 자세한 증명은 생략하며 1/3 Rule과 3/8 Rule을 유도한 결과는 다음과 같다.

다