복소 평면에서 다항식 방정식의 영점

Source: Dev.to

번역할 텍스트를 제공해 주시면, 요청하신 대로 한국어로 번역해 드리겠습니다. (코드 블록, URL 및 마크다운 형식은 그대로 유지됩니다.)

초록

이 기사에서는 복소 평면에서 차수 (n)인 다항식 방정식의 근을 찾기 위한 Laguerre 알고리즘에 대해 논의합니다. 우리는 특정 경우를 유도하고 단순 근에 대한 수렴성을 분석합니다. 알고리즘 구현을 사용하여 예제를 검증함으로써 그 장점과 한계를 보여줍니다.

Introduction

다항식의 차수가 (n)인 경우 그 영점을 찾는 문제는 수세기 동안 수학 발전에 큰 영향을 미쳐 왔으며, 실용적·이론적 응용 모두에서 여전히 중요한 역할을 합니다.

현재는

[ p(z)=\sum_{i=0}^{n} a_i z^{i}\qquad (1) ]

와 같은 형태의 다항식에 대한 연구가 수학이나 응용수학에서 중심적인 위치를 차지하고 있지는 않습니다. 많은 경우 문제를 선형화하여 선형대수 도구와 고속 푸리에 변환(Fast Fourier Transform)을 이용해 풀며, 이 과정에서 다항식 방정식의 근이 등장하기도 합니다.

그럼에도 불구하고, 이러한 형태의 방정식은 여전히 일부 응용수학 분야에서 관심을 받고 있으며, 그 근을 찾기 위한 알고리즘도 계속해서 개발·연구되고 있습니다.

아벨이 1827년에 증명했듯이 차수가 4 이상인 다항식에 대해서는 근호(radicals)만으로 정확한 해를 구할 수 있는 일반 공식이 존재하지 않으므로, 이러한 다항식을 풀어야 하는 문제는 수치적 방법에 의존할 수밖에 없습니다.

본 기사에서는 복소평면에서의 Laguerre 방법과 여러 종류의 다항식에 대한 구현을 논의합니다.

Source: …

이론적 결과

초기 정의 및 정리

정의 1 (수렴 차수).
알고리즘이 근 (\eta)에서 수렴 차수 (\alpha)를 가진다고 한다는 것은

[ \lim_{n\to\infty}\frac{|z_{n+1}-\eta|}{|z_n-\eta|^{\alpha}}=C\qquad (2) ]

가 어떤 상수 (C\neq0)에 대해 성립할 때이다.

정의 2 (전역 vs. 국부 방법).
수치 방법이 전역이라고 하는 것은 다항식의 영에 충분히 가깝지 않은 초기값을 사용해도 수렴한다는 뜻이며, 그렇지 않으면 국부라고 한다.

정리 1.
(n>1) 차의 복소 계수를 가진 다항식 (p(z))에 대해, (p(z))는 정확히 (n)개의 복소 근을 (중복도 포함하여) 가진다.

정리 2.
(m>4) 차의 정규화된 다항식 (p(z))와

[ P={p_i : i\in{1,\dots ,\ell}} ]

를 그 근들의 집합이라고 하자. 초기점이

[ u_0\in\mathbb{C}\setminus P,\qquad p’(u_0)\neq0\ \text{또는}\ p”(u_0)\neq0, ]

일 때, 다음 수열을 정의한다

[ L_p(u_0)=\bigl(u_n\bigr)_{n\in\mathbb{N}} ]

[ u_{n+1}=u_n-\frac{m}{,q(u_n)+s(u_n)r(u_n)}\qquad (3) ]

여기서

[ \begin{aligned} q(z)&=\frac{p’(z)}{p(z)},\ t(z)&=q(z)^2-\frac{p”(z)}{p(z)},\ r(z)&=\sqrt{(m-1)\bigl(mt(z)-q(z)^2\bigr)}, \end{aligned} ]

그리고

[ s(z)= \begin{cases} ;1, & \text{if } \operatorname{Re}q(z),\operatorname{Re}r(z)+\operatorname{Im}q(z),\operatorname{Im}r(z)\ge0,\[4pt] -1, & \text{otherwise}. \end{cases} ]

분모는 절대로 0이 되지 않는다: (q(u_n)+s(u_n)r(u_n)\neq0).

만약 단순 근 (p\in P)가 존재하여

[ |u_0-p|\le\frac{1}{2m-1}\min_{p_i\in P\setminus{p}}|p-p_i|, ]

이면 수열 (L_p(u_0))는 (p)로 수렴하고

[ |u_n-p|\le\lambda^{,n},|u_0-p|,\qquad \lambda=\frac{15}{16},\qquad n\in\mathbb{N}\setminus{0}. ]

(p(z))의 모든 근이 단순일 경우, 위 부등식에서

[ \mu_p=\min_{p_i\in P\setminus{p}}|p-p_i| ]

는 아래와 같이 하한을 가질 수 있다

[ \Bigl(1+\frac{1}{d_0}\max_{1\le j\le\binom{m}{2}}|d_j|\Bigr)^{-\frac12} ]

(원문에서 계속).

구현 라이브러리

앞 절의 결과를 이용하여 다음과 같은 라이브러리를 만들었다:

반올림 오차는 deflation 및 evalpoly 루틴에서 가장 크게 나타나므로, 이러한 오류를 완화하기 위해 모든 계산을 long double 정밀도로 수행한다.

결과 및 토론

일련의 테스트가 수행되었으며, 가장 대표적인 결과는 아래 표에 표시됩니다.

• 저차 다항식에 대해 알고리즘은 놀라운 정밀도를 달성합니다 – 예를 들어, 숫자의 제곱근을 소수점 이하 13자리까지 근사할 수 있습니다.
• 중복도 (\le 10)인 근에 대해 알고리즘은 매우 잘 동작합니다. 비록 다중 근을 위해 특별히 설계된 것은 아니지만.
• 차수가 높아지면서 발산이 나타나기 시작합니다. 최대 반복 횟수를 늘려도 도움이 되지 않으며, 다중 근의 경우 방법이 선형적으로만 수렴하고 실용적이지 않을 정도로 많은 반복이 필요할 수 있습니다.
• 차수 (n>10)인 단순근 다항식의 경우 동작이 개선되지만, 표의 마지막 두 다항식은 실패를 보여줍니다: 알고리즘이 마지막 근을 계산하려다 발산했으며, 존재하는 14개의 근 중 13개만 찾았습니다.
• 차수가 크게 증가함에 따라 전체 정밀도가 급격히 악화됩니다.

테스트 결과 표

결론

첫 번째 구현에서는 알고리즘이 소규모 문제에 대해 좋은 성능을 보입니다. 그러나 추가 개발 시간을 투자하면 상당히 최적화될 수 있습니다. 현재 상태에서는 코드가 고성능 프로덕션 환경(예: Mathematica 또는 MATLAB 수준의 작업)에는 적합하지 않습니다.

전체 소스 코드는 GitHub에서 확인할 수 있습니다.

참고문헌

1. Pan, Y., & Victor, Solving a Polynomial Equation: Some History and Recent Progress, SIAM Review, 39(2), 187‑220 (1997).
2. Ahlfors, L., Complex Analysis, McGraw‑Hill, 1979.
3. Møller, H., Convergence and visualization of Laguerre’s root‑finding algorithm, 9 January 2015.
4. Acton, S. F., Numerical Methods that Work, The Mathematical Association of America, 1990.
5. Kiusalaas, J., Numerical Methods in Engineering with Python 3, Cambridge University Press, 2013.