當一元方程f(z)=0的左端函數f(z)不是z的多項式時,稱之為超越方程。這類方程除極少數情形(如簡單的三角方程)外,隻能近似地數值求解,此種數值解法的研究至今仍是計算數學的主要課題。超越方程的數值解法也適用於代數方程。

  數值求解超越方程時首先需要確定解的分佈區域,它可以利用圖解法或者根據f(z)的解析性質來確定。當f(x)為實函數時,確定方程實根的分佈的最常用方法是應用連續函數的中值定理:如果實的連續函數f(x)在區間[α,b]的兩個端點的值異號,則f(x)在此區間內至少有一個根。

  二分法 利用中值定理計算實函數實根的簡單易行的方法,算法如下:

  設區間[α0b0]滿足條件f(α0)f(b0)<0,[α0b0]的二等分點為

計算f( x 0)的值,若f( x 0)=0,即為所求解;若f( x 0)f(α 0)<0,取α 10b 1= x 0作為新的區間端點;若f( x 0)f(α 0)>0,取α 1= x 0b 1= b 0作為新區間的端點。[α 1b 1]的二分點為 計算f( x 1)的值並重復上述步驟以確定新的區間[α 2b 2],如此繼續下去。則得到區間序列[α kb k]( k=0,1,…),它滿足f(α k)f( b k)<0,並且 b kk達到指定的精確度要求時,則取 為方程的解,它與精確解的誤差不超過

  迭代法 解超越方程的主要方法,既適用於求實根,也適用於求復根。使用這類方法時一般需要知道根的足夠好的近似值。最常用的方法有牛頓法、割線法、二次插值法、雙曲插值法、切比雪夫迭代法、艾特肯δ2加速方法和斯梯芬森方法等。

  牛頓法 也稱切線法,其計算公式為

z 0為事先選定的根的初始近似。設 z 為 f( z)的根,若f( z)在 z 的某鄰域內二次可微,且f′( z )≠0,則當 z 0z 充分接近時,牛頓法至少是二階收斂的,即當 k充分大時有估計式 成立, C為確定的常數。一般說來,牛頓法隻具有局部收斂性,即僅當初始近似與根充分接近時才收斂。但是,當f( x)為實函數,且於[α, b]上f′( x)和 f″( x)不變號時,若f( x)於[α, b]上有根,則隻要初始近似 x 0滿足條件f( x 0) f″( x 0)>0,牛頓法就收斂。一般情形,為減弱對初始近似的限制,可利用牛頓下降算法,其算式為

ω k>0為迭代參數,由條件│f( z k +1)│<│f( z k)│確定,牛頓法的 k+1次近似 z k +1是f( z)在 z k處的泰勒展開式的線性部分的根。

  割線法 又稱弦位法,其算式為

z 0z 1為初始近似。若f( z)於其根 z 的某鄰域二次連續可微,且f′( z )≠0,則 z 0z 1z 充分接近時,割線法收斂於 z ,並當 k充分大時有估計式 式中 C為常數, 割線法的 k+1次近似 z k +1是以 z kz k -1為插值節點的線性插值函數的根,如果利用更精確的近似表達式則可構造出更高階的迭代法。

  二次插值法 亦稱繆勒方法,是利用二次插值多項式構造的迭代算法。設已確定瞭zkzk-1zk-2,則zk+1就取為以zkzk-1zk-2為節點的二次插值多項式兩個根中與zk最接近者,其算式為

式中“±”號選成使分母的模為最大者,而

式中 當分母為0,則λ k=1。

  雙曲插值法 利用線性分式插值構造的迭代算法,其算式為

式中 μ k、δ k、Δ z k和f k的意義與二次插值法相同。

  若f(z)在其根z

的某鄰域內三次可微,並且 z 0z 1z 2z 充分接近,則二次插值法和雙曲插值法均收斂。此外,如果f′( z )≠0,對充分大的 k,有估計式

式中 C為確定常數,τ為方程式 t 3- t 2- t-1=0的惟一正根,τ=1.839…。

  切比雪夫迭代法 三階收斂的方法,其算式為

當f( z)在其根 z 的鄰域內三次可微且f′( z )≠0時,對充分大的 k,有 C為確定常數。

  艾特肯δ2加速方法 提高迭代法收斂速度的有效算法,設{zk}為迭代序列,δ2加速的算式為

若f( z)在其根 z 處充分光滑,且f( z )≠0,則對充分大的 k,有 並且若 z kp( p>1)階收斂,即

C 0均為常數。當f′( z )=0時也有加速作用。此算法可以循環使用。

  斯梯芬森方法 不算微商而二階收斂的方法,其算式為

它可由迭代算法 循環使用 δ 2程序導出。

  所有的迭代法用於求重根(即f′(z

)=0)時,其收斂速度將變慢,收斂階將降低。

  為求得達到所需精度的解而花費的代價是評價迭代法優劣的依據,效能指數是其重要指標,它定義為p1/μ,p為收斂階,μ為每步需要計算的函數值和微商值的總數。效能指數越大,說明方法越好。二分法及上述各種迭代法的收斂階(單根時和重根時)和效能指數如表。

各種迭代法的收斂階和效能指數

  隻有當初始近似與解充分接近時,迭代法才收斂,這是所述算法的共同特點。減弱對初始近似的限制是提高迭代法有效性的重要措施,例如,牛頓法中引進下降因子。對一些特殊函數類(如單調函數,隻有實根的解析函數等)的大范圍收斂迭代算法也有一些研究工作。

  

參考書目

 A.Ostrowski,Solutions of Equations in Euclidean and Banach Spaces,3rd ed.,Academic Press,New York,1973.

 J.F.Traub,Iterative Methods for the Solution of Equations,Prentice-Hall,Englewood Cliffs,New Jersey,1964.