當一元方程f(z)=0的左端函數f(z)不是z的多項式時,稱之為超越方程。這類方程除極少數情形(如簡單的三角方程)外,隻能近似地數值求解,此種數值解法的研究至今仍是計算數學的主要課題。超越方程的數值解法也適用於代數方程。
數值求解超越方程時首先需要確定解的分佈區域,它可以利用圖解法或者根據f(z)的解析性質來確定。當f(x)為實函數時,確定方程實根的分佈的最常用方法是應用連續函數的中值定理:如果實的連續函數f(x)在區間[α,b]的兩個端點的值異號,則f(x)在此區間內至少有一個根。
二分法 利用中值定理計算實函數實根的簡單易行的方法,算法如下:
設區間[α0,b0]滿足條件f(α0)f(b0)<0,[α0,b0]的二等分點為
![](/img3/3066.gif)
計算f(
x
0)的值,若f(
x
0)=0,即為所求解;若f(
x
0)f(α
0)<0,取α
1=α
0,
b
1=
x
0作為新的區間端點;若f(
x
0)f(α
0)>0,取α
1=
x
0,
b
1=
b
0作為新區間的端點。[α
1,
b
1]的二分點為
![](/img3/3067.gif)
計算f(
x
1)的值並重復上述步驟以確定新的區間[α
2,
b
2],如此繼續下去。則得到區間序列[α
k,
b
k](
k=0,1,…),它滿足f(α
k)f(
b
k)<0,並且
![](/img3/3068.gif)
當
b
k-α
k達到指定的精確度要求時,則取
![](/img3/3069.gif)
為方程的解,它與精確解的誤差不超過
迭代法 解超越方程的主要方法,既適用於求實根,也適用於求復根。使用這類方法時一般需要知道根的足夠好的近似值。最常用的方法有牛頓法、割線法、二次插值法、雙曲插值法、切比雪夫迭代法、艾特肯δ2加速方法和斯梯芬森方法等。
牛頓法 也稱切線法,其計算公式為
z
0為事先選定的根的初始近似。設
z
![](/img3/3072.gif)
為 f(
z)的根,若f(
z)在
z
![](/img3/3072.gif)
的某鄰域內二次可微,且f′(
z
![](/img3/3072.gif)
)≠0,則當
z
0與
z
![](/img3/3072.gif)
充分接近時,牛頓法至少是二階收斂的,即當
k充分大時有估計式
![](/img3/3073.gif)
成立,
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
0、
z
1為初始近似。若f(
z)於其根
z
![](/img3/3072.gif)
的某鄰域二次連續可微,且f′(
z
![](/img3/3072.gif)
)≠0,則
z
0、
z
1與
z
![](/img3/3072.gif)
充分接近時,割線法收斂於
z
![](/img3/3072.gif)
,並當
k充分大時有估計式
![](/img3/3076.gif)
式中
C為常數,
![](/img3/3077.gif)
割線法的
k+1次近似
z
k
+1是以
z
k、
z
k
-1為插值節點的線性插值函數的根,如果利用更精確的近似表達式則可構造出更高階的迭代法。
二次插值法 亦稱繆勒方法,是利用二次插值多項式構造的迭代算法。設已確定瞭zk、zk-1、zk-2,則zk+1就取為以zk、zk-1、zk-2為節點的二次插值多項式兩個根中與zk最接近者,其算式為
式中“±”號選成使分母的模為最大者,而
![](/img3/3080.gif)
-
![](/img3/3083.gif)
式中
![](/img3/3088.gif)
當分母為0,則λ
k=1。
雙曲插值法 利用線性分式插值構造的迭代算法,其算式為
式中
μ
k、δ
k、Δ
z
k和f
k的意義與二次插值法相同。
若f(z)在其根z
![](/img3/3072.gif)
的某鄰域內三次可微,並且
z
0、
z
1、
z
2與
z
![](/img3/3072.gif)
充分接近,則二次插值法和雙曲插值法均收斂。此外,如果f′(
z
![](/img3/3072.gif)
)≠0,對充分大的
k,有估計式
![](/img3/3092.gif)
式中
C為確定常數,τ為方程式
t
3-
t
2-
t-1=0的惟一正根,τ=1.839…。
切比雪夫迭代法 三階收斂的方法,其算式為
當f(
z)在其根
z
![](/img3/3072.gif)
的鄰域內三次可微且f′(
z
![](/img3/3072.gif)
)≠0時,對充分大的
k,有
C為確定常數。
艾特肯δ2加速方法 提高迭代法收斂速度的有效算法,設{zk}為迭代序列,δ2加速的算式為
若f(
z)在其根
z
![](/img3/3072.gif)
處充分光滑,且f(
z
![](/img3/3072.gif)
)≠0,則對充分大的
k,有
![](/img3/3096.gif)
並且若
z
k是
p(
p>1)階收斂,即
C
0均為常數。當f′(
z
![](/img3/3072.gif)
)=0時也有加速作用。此算法可以循環使用。
斯梯芬森方法 不算微商而二階收斂的方法,其算式為
它可由迭代算法
![](/img3/3100.gif)
循環使用 δ
2程序導出。
所有的迭代法用於求重根(即f′(z
![](/img3/3072.gif)
)=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.