[科普中國]-求根法

在數(shù)學(xué)和電腦運(yùn)算中，對(duì)于一個(gè)已知的從實(shí)數(shù)集合映射到實(shí)數(shù)集合，或者從復(fù)數(shù)集合映射到復(fù)數(shù)集合的連續(xù)函數(shù)f(x)，搜索變量x使得f(x)=0（此時(shí)，變量x稱為f(x)=0的根、f(x)的零點(diǎn)）的算法，稱為求根算法。在許多情況下，函數(shù)的零點(diǎn)無法被準(zhǔn)確計(jì)算出，也無法被解析解表示；是故，求根算法在實(shí)數(shù)集合下只提供一個(gè)以浮點(diǎn)數(shù)表示的近似解，或者一個(gè)足夠小的解的存在區(qū)間，在復(fù)數(shù)集合下只提供一個(gè)復(fù)根的圓盤（輸出一個(gè)區(qū)間或一個(gè)圓盤等價(jià)于輸出一個(gè)根的近似值及其誤差上限）。

解方程f(x)=g(x)與求f(x)-g(x)的根是等價(jià)的。因此求根算法可以求解任何以連續(xù)函數(shù)定義的方程。然而，許多情況下，求根算法只能找到方程的某些根，而不能保證所有根都能找到；特別指出，算法未找到根，并不代表方程確實(shí)無根。

簡(jiǎn)介大多數(shù)的數(shù)值求根算法都使用迭代法，生成一個(gè)以方程的根為極限的收斂數(shù)列。它們需要一個(gè)或多個(gè)根作為迭代的初期值，嗣后每次迭代都生成一個(gè)逐步逼近根的值。由于迭代法必須在有限步內(nèi)終止于某個(gè)點(diǎn)，這些方法都只能提供一個(gè)根的近似值，而不能提供一個(gè)精確解。 許多方法是通過代入上一個(gè)迭代值來計(jì)算一個(gè)輔助方程，從而得出下一個(gè)迭代值的。此處所指的輔助方程是指為了使源方程的根是一個(gè)定點(diǎn)并使迭代值能更快地收斂到這些定點(diǎn)而設(shè)計(jì)的一個(gè)方程，因此迭代值的極限是這個(gè)輔助方程的一個(gè)定點(diǎn)。

求根算法的性能是數(shù)值分析的研究范疇。一種算法的效率可能大幅度取決于已知點(diǎn)的性質(zhì)。例如，一部分算法都使用輸入函數(shù)的導(dǎo)數(shù)（此要求函數(shù)不但連續(xù)，而且可導(dǎo)），而其他算法則能用于任何一個(gè)連續(xù)函數(shù)。在一般情況下，數(shù)值算法不能保證找到一個(gè)函數(shù)的所有根，因此算法未能找到根并不能證明方程無根。然而，對(duì)于多項(xiàng)式，存在特定的使用代數(shù)學(xué)性質(zhì)以定位根的所在區(qū)間（或復(fù)根所在的圓盤）的算法，這個(gè)區(qū)間（或圓盤）足夠小以能保證數(shù)值算法（例如牛頓法）能收斂到唯一被定位的根。1

包圍法包圍法是指通過迭代確定根的所在區(qū)間，并逐漸縮小其區(qū)間長(zhǎng)度的算法。當(dāng)區(qū)間變得足夠小時(shí)，則認(rèn)為根已經(jīng)被找到。一般地，包圍法以介值定理為基礎(chǔ)，且能夠求出根的絕對(duì)誤差上限；而當(dāng)函數(shù)是一個(gè)多項(xiàng)式時(shí)，還有其它基于施圖姆定理或笛卡兒符號(hào)法則的方法，能夠在一個(gè)區(qū)間內(nèi)求出精確的根。

二分法最簡(jiǎn)單的求根算法為二分法︰令 為一個(gè)連續(xù)函數(shù)，且已知存在區(qū)間 滿足 和 符號(hào)互異。令 （區(qū)間的中點(diǎn)），則 和 或 和 中，必恰有一者符號(hào)互異，并將已知根所在區(qū)間的長(zhǎng)度縮短為一半。對(duì)被縮短的區(qū)間重復(fù)上述步驟，直到找到根。

縱二分法具有強(qiáng)健性，但其只能求得區(qū)間內(nèi)的一個(gè)且只有一位精度的解。此外在合適的條件下，亦存在其他能更快求得精確解的方法。

盈不足術(shù)法盈不足術(shù)法與二分法相似。異處在于，盈不足術(shù)以方式計(jì)算出迭代點(diǎn)，

盈不足術(shù)法也類似于割線法。異處在于，盈不足術(shù)法不保留前兩次迭代點(diǎn)，而是在根的兩側(cè)各保留一點(diǎn)。 盈不足術(shù)法能以較二分法更快的速度求根，且不會(huì)如割線法一樣發(fā)散（不收斂）；但在一些簡(jiǎn)單實(shí)現(xiàn)的情形中可能因?yàn)樯崛胝`差而無法收斂。

Ridders法是盈不足術(shù)法的一個(gè)變形。其使用區(qū)間中點(diǎn)的函數(shù)值，構(gòu)造出一個(gè)具有相同零點(diǎn)的函數(shù)，再用盈不足術(shù)法求解之。這個(gè)方法維持了一定的強(qiáng)健性外，亦使算法更快收斂。1

插值法許多求根算法通過插值來實(shí)現(xiàn)。即，使用上一步計(jì)算出的根的多個(gè)近似值，借助一個(gè)以插值法求出的低次多項(xiàng)式，以逼近一個(gè)函數(shù)。然后計(jì)算多項(xiàng)式的根，并用其作新的函數(shù)的根的近似值，重復(fù)此流程。

兩個(gè)函數(shù)值可利用插值法求得一個(gè)一次多項(xiàng)式，即以一條直線逼近一個(gè)函數(shù)圖像。此乃割線法及盈不足術(shù)法的基礎(chǔ)。進(jìn)而，三個(gè)函數(shù)值可求得一個(gè)二次函數(shù)，即以一條拋物線逼近一個(gè)函數(shù)圖像，此即Muller法。1

迭代法雖然所有求根算法都通過迭代，但一個(gè)迭代的求根算法，通常使用一種特定的迭代類型，包括定義一個(gè)輔助函數(shù)，應(yīng)用上一步計(jì)算出的根的近似值，求得新的近似值。輔助函數(shù)到逹一個(gè)定點(diǎn)（到逹所需的精度），即新迭代的近似值充分接近上一個(gè)迭代值時(shí)，迭代停止。

牛頓法（及類似的以導(dǎo)數(shù)為基礎(chǔ)的方法）牛頓法假定函數(shù) 的導(dǎo)數(shù)是連續(xù)的。如果起始點(diǎn)距離根太遠(yuǎn)，牛頓法可能不收斂。然而，其若收斂，速度將較二分法快，且通常為二次收斂。牛頓法也是一種重要的算法，因?yàn)樗苋菀椎赝茝V到高維問題。類似牛頓法且有更高次的收斂性的算法為Householder法。具有三次收斂性的Householder法是Halley法。

割線法將牛頓法中的導(dǎo)數(shù)替換為一個(gè)差分式，即得到割線法。 這種方法的優(yōu)點(diǎn)在于不需要計(jì)算導(dǎo)數(shù)，但其代價(jià)是收斂速度較慢（收斂次數(shù)約為1.6）。把割線法推廣到高維的算法是Broyden法。

逆插值法對(duì)函數(shù) 進(jìn)行逆插值，能夠避免插值法中出現(xiàn)復(fù)數(shù)。這種方法稱為逆二次插值法。其收斂速度漸近快于割線法；但當(dāng)?shù)x根較遠(yuǎn)時(shí)，逆二次插值法往往表現(xiàn)不佳。1

本詞條內(nèi)容貢獻(xiàn)者為:

王海俠 - 副教授 - 南京理工大學(xué)