근 찾기 알고리즘

3. 다항식의 근 찾기

함수 가 다항식인 경우는 잘 연구되어 있으며, 다항식의 성질을 활용한 근 찾기 알고리즘이 존재한다. 단, 2차 방정식의 해조차 수치적 안정성에 주의가 필요하다^[8]。

실근의 경우, 스투름의 정리가 근의 위치를 특정하거나 분리하는 데 도움이 된다^[2]。이와 구간 연산을 뉴턴 방법과 조합한 근 찾기 알고리즘도 생각할 수 있지만, 다른 방법을 사용하는 것이 일반적이다.

다항식의 근을 찾는 방법 중 하나는 다항식의 콤파니언 행렬을 이용하는 것이다.

베어스토우 방법은 실수 계수 다항식의 2차 인수를 구하는 데 뉴턴 방법을 사용한다. 실수 계산만으로 실수 다항식의 실근과 복소수 근을 구할 수 있다.

3. 1. 콤파니언 행렬

3. 2. 라게르 방법

3. 3. 젠킨스-트라웁 방법

3. 4. 듀란-카너 방법 (아버스 방법)

3. 5. 분할 원법

3. 6. 윌킨슨 다항식

4. 중근 계산

다항식 $p(x)$가 중근을 가질 경우, 일반적인 근 찾기 알고리즘으로는 근을 계산하기 어렵다. 계수가 명시적으로 주어진 일변수 다항식에 대해서는 다음과 같은 알고리즘이 존재한다.

1. 먼저, $p(x)$가 중근을 갖는지 알아야 한다. $p(x)$가 $r$에서 중근을 갖는다면, 미분 $p\text{'}(x)$도 $r$에서 근을 가지므로, $p(x)$와 $p\text{'}(x)$의 최대공약수를 계산하고, 최고차항의 계수가 1이 되도록 상수배한 것을 $g(x)$로 한다. ($g\; =\; \backslash gcd(p,\; p\text{'})$) 스투름의 정리를 참조하라. $g(x)\; =\; 1$이라면, $p(x)$는 중근을 갖지 않으므로, 다른 근 찾기 알고리즘으로 근을 구하고 종료한다.

2. $p(x)$가 중근을 갖는다고 가정한다. $g(x)$는 $r$에서 $p\text{'}(x)$와 같은 중복도의 근을 가지며, $g(x)$의 차수는 $p(x)$보다 작다는 것에 주의한다. 재귀적으로 이 루틴을 적용하여(1단계로 돌아가 $p(x)$를 $g(x)$로 둔다), $g(x)$의 근을 계산한다.

3. $g$가 얻어졌으므로, $p(x)$를 $(x\; -\; r)$로 분해하고, $r$에 있는 모든 중근이 제거될 때까지 이것을 반복한다. 몫으로부터 다른 근 찾기 알고리즘으로 근을 구하고 종료한다.

5. 관련 서적

• Birge-Vieta method^영어[1]
• 비선형방정식의 근^한국어[2]
• 이리 마사오, 《수치 계산: 방정식의 해법》, 아사쿠라 서점, ISBN 978-4-25411362-4 (1981년 12월)
• 빅터 Y. 팬, "다항식 방정식 풀기: 역사와 최근 진전", SIAM 리뷰, Vol.39, No.2, pp.187-220 (1997년 6월)
• 존 마이클 맥네미, ''다항식의 근을 구하는 수치적 방법 - 파트 I'', 엘스비어, ISBN 978-0-444-52729-5 (2007년 6월 4일)
• 존 마이클 맥네미, 빅터 Y. 팬, ''다항식의 근을 구하는 수치적 방법 - 파트 II'', 엘스비어, ISBN 978-0-444-52730-1 (2013년 6월 19일)

참조

_[1] 서적 数値解析入門 サイエンス社 2003-06
_[2] 서적 数値解析 共立出版 2002-02
_[3] 서적 Applied and Computational Complex Analysis I Wiley 1974
_[4] 서적 UNIX & Information Science-5 C 言語による数値計算入門 サイエンス社 2005
_[5] 웹사이트 Secant Method http://mathworld.wol[...]
_[6] 서적 Algorithms for Minimization Without Derivatives Prentice-Hall 1973
_[7] 웹사이트 Brent's Method http://mathworld.wol[...]
_[8] 웹사이트 安定性 http://www.nag-j.co.[...]
_[9] 논문 Sur une m´ethode pour obtenir par approximation les racines d’une ´equation alg´ebraique qui a toutes ses racines r´eelles 1898
_[10] 논문 A Three-Stage Variables-Shift Iteration for Polynomial Zeros and Its Relation to Generalized Rayleigh Iteration 1970
_[11] 서적 Numerical Recipes in FORTRAN: The Art of Scientific Computing Cambridge University Press 1992
_[12] 서적 A First Course in Numerical Analysis McGraw-Hill 1978
_[13] 서적 Rounding Errors in Algebraic Processes Prentice Hall 1963