학창시절 수학 공부하면서 지겹도록 방정식을 풀어 보았을 겁니다. 그런데 아십니까? 우리가 손으로 풀던 문제들은, 딱 손으로 풀 수 있는 정도의 계산량만 요구하는 "연습용" 문제일 뿐이라는 걸요.
실제 현실에서 부닥치는 여러가지 문제들을 방정식으로 모델링하고 이를 풀려고 하면 절대로 손으로 (혹은 대수적으로) 풀 수 없는 경우가 태반입니다.
객관식 문제라면 보기 몇개를 거꾸로 대입시켜 해결할 수 있을 것입니다만... 현실은 주관식이어서 대입해야 할 수는 거의 무한대에 가깝습니다. 이럴 때 필요한 것이 초당 몇백만 번을 계산할 수 있는 컴퓨터의 계산 능력입니다.
이번 장에서 살펴 볼 방정식의 근 찾기 문제는 수치해석(Numerical Analysis)의 가장 전형적인 형태입니다. 기본적으로 빠른 계산 능력을 믿고 방정식에 대입시켜보는 전략이지만, 무한대의 후보를 모두 할 수는 없기에, 어떻게 범위를 좁혀서 효율적으로 근을 찾아내는 지가 관건입니다.
이 문제를 해결하기 위해 제시된 여러가지 해법 중에서 대표적인 것들을 알아 봅니다.
강의 자료
강의 동영상
25.0 방정식 근 찾기 - 시작 : 이번 장에서는 대수적으로 풀기 힘든 방정식을 컴퓨터의 뛰어난 연산 능력을 활용하여 해결하는 방법을 알아 봅니다. 빠짐없이 빠르게 근을 찾기 위한 여러가지 알고리즘들을 비교 분석해 볼 예정입니다.
25.1 방정식 근 찾기 - 개요 : 이 장에서는 f(x) = 0 형태의 방정식에서 x를 찾는 문제를 해결해 볼 겁니다. 여러가지 방법들이 있지만 각자의 특성과 장단점이 틀리기 때문에 잘 이해해야 문제에 따라 적합한 방법을 적용할 수 있습니다.
25.2 이분법 (Bisection Method) : 이분법은 <중간값 정리>라는 명제를 기반으로 하는 방정식 풀이법입니다. 이 명제에 의하면 f(x1)f(x2) < 0인 x1과 x2를 잡아야 하고, 이 구간 내에서 f(x)가 연속이어야 하는 조건을 만족해야 합니다. 이것만 만족한다면 매우 효율적으로 근을 찾아낼 수 있습니다.
25.3 Regular Falsi 법 : Regular Falsi법은 이분법과 동일한 조건을 필요로 합니다. 하지만 다른 점은 대부분의 경우 근에 대한 수렴이 이분법 보다 빠르다는 겁니다. 이는 단순히 2등분 하기 보다는, 양 구간 끝의 값을 보고 더 적극적으로 근에 다가가는 방법을 쓰기 때문입니다. 하지만 몇가지 함정이 있기 때문에 끝까지 봐야 합니다.
25.4 시컨트 법 (Secant Method) : 시컨트법은 이분법과 달리 f(x1)과 f(x2)의 부호가 달라야 한다는 전제조건에서 자유롭습니다. 임의의 두 점을 선택한 뒤, 이 두점을 지나는 직선을 그어 근에 다가가는 방법입니다.
25.5 뉴턴법 (Newton's Method) : 뉴턴의 업적은 많지만, 그 중에서 미적분학의 체계를 세웠다는 것이 매우 중요합니다. 뉴턴법은 함수 f와 이의 미분함수 f'가 있다면 어떤 한 점에서 시작하여 근을 찾을 수 있다는 원리입니다. 미분은 대수적 풀이가 용이하기 때문에 그리 까다로운 조건은 아닙니다.
25.6 근 찾기 함수 사용법 : 여러 알고리즘을 함수로 구현했으므로 이를 활용하여 실제로 근을 찾는 법을 시연해 봅니다. 문제에 따라 다르겠지만, 제가 테스트한 3차 방정식의 경우 뉴턴법이 계산 횟수가 가장 적었습니다.
25.9 방정식 근 찾기 - 결론 : 근을 찾는 알고리즘은 특성이 다르므로, 풀려는 방정식의 종류에 따라 적절한 방법을 택해야 합니다. 그리고 컴퓨터가 수를 다루는 원리상, 언제나 오차가 있을 수 있다는 점을 염두에 두어야 합니다.
관련글 |
- C++로 배우는 알고리즘
- 24장 : 행렬 (Matrix)
- 26장 : 수치 미적분
댓글 없음:
댓글 쓰기