求解高次多項式根在科學計算中常見。本文提供基於 Laguerre 方法的完整 Python 實作,可求解實根與複根,包含多項式求值、去多項式 (deflation) 等輔助函數。
from evalPoly import evalPoly # 假設已有多項式求值函數
from numpy import zeros, complex
from cmath import sqrt
from random import random
def polyRoots(a, tol=1.0e-12):
"""回傳多項式 a[0] + a[1]x + ... + a[n]x^n = 0 的所有根"""
def laguerre(a, tol):
x = random() # 隨機初始猜測
n = len(a) - 1
for _ in range(30): # 最大迭代次數
p, dp, ddp = evalPoly(a, x)
if abs(p) < tol:
return x
g = dp / p
h = g*g - ddp/p
f = sqrt((n - 1) * (n*h - g*g))
# 選擇分母較大者增強穩定性
dx = n / (g + f) if abs(g + f) > abs(g - f) else n / (g - f)
x -= dx
if abs(dx) < tol:
return x
raise RuntimeError("Too many iterations")
def deflPoly(a, root):
"""多項式去根:將 (x - root) 因式除出"""
n = len(a) - 1
b = [(0.0+0.0j)] * n
b[n-1] = a[n]
for i in range(n-2, -1, -1):
b[i] = a[i+1] + root * b[i+1]
return b
n = len(a) - 1
roots = zeros(n, dtype=complex)
for i in range(n):
x = laguerre(a, tol)
if abs(x.imag) < tol:
x = x.real
roots[i] = x
a = deflPoly(a, x) # 降階
return roots
def evalPoly(a, x):
"""Horner 方法求值,回傳 (p, p', p'')"""
n = len(a) - 1
p = a[n]
dp = 0.0 + 0.0j
ddp = 0.0 + 0.0j
for i in range(n-1, -1, -1):
ddp = ddp * x + 2 * dp
dp = dp * x + p
p = p * x + a[i]
return p, dp, ddp
# x^3 - 6x^2 + 11x - 6 = (x-1)(x-2)(x-3)
coeffs = [-6, 11, -6, 1] # a[0] + a[1]x + a[2]x^2 + a[3]x^3
roots = polyRoots(coeffs)
print(roots) # [1.+0.j, 2.+0.j, 3.+0.j]
cmath.sqrt 處理複數運算。numpy.roots 或 scipy.optimize.root:經過高度優化、支援高精度、誤差控制。理解 Laguerre 方法原理,有助於在無法使用 SciPy 的嵌入式環境中實現多項式求根。