萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 計算多項式根:Laguerre 方法完整實作

求解高次多項式根在科學計算中常見。本文提供基於 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

輔助函數:多項式求值 (evalPoly)


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]

演算法特性

  • 全域收斂:Laguerre 方法幾乎對任意初始猜測收斂。
  • 複根支援:使用 cmath.sqrt 處理複數運算。
  • 去多項式:每找到一個根即降階,避免重複收斂同一根。
  • 數值穩定:雙重分母選擇策略減少除以微小數風險。

生產環境建議

  • 改用 numpy.roots 或 scipy.optimize.root:經過高度優化、支援高精度、誤差控制。
  • 多項式次數極高時需考慮數值條件數,必要時用多精度庫 (mpmath)。
  • 實係數多項式複根成共軛對出現,可優化儲存。

理解 Laguerre 方法原理,有助於在無法使用 SciPy 的嵌入式環境中實現多項式求根。

copyright © 萬盛學電腦網 all rights reserved