2.2迭代法2.2.1迭代原理2.2.2迭代的收斂性2.2.3迭代的收斂速度2.2.4迭代的加速預備定理2.2.1迭代原理計算結果見下表

方程f(x)=0化為等價形式的方程x=φ(x)，構造迭代公式xk+1=φ(xk

),k=0,1,2,……取初始近似根x0

,進行迭代計算x1=φ(x0),x2=φ(x1),……..則有x1,

x2,,…….,xk

,

…….,得到迭代序列{xk

}.如果這個序列有極限，則迭代公式是收斂的。這時

則，x*

為不動點，等價地有f(x*)=0,x*

即為方程的根。連續函數φ(x)稱為迭代函數。實際計算到|xk–xk-1|<ε（ε是預定的精度），取x*≈xk

。

迭代公式收斂指迭代序列{xk

}收斂，迭代公式發散指迭代序列{xk

}不收斂，即發散。迭代公式不一定總是收斂。例如求方程

f(x)=x3-x-1=0的一個根。對應的迭代公式為取初值迭代序列{xk

}發散.x1=φ(x0)x2=φ(x1)迭代法收斂與發散的圖示迭代法的收斂與發散收斂的情形發散的情形2.2.2迭代的收斂性迭代法的收斂條件及誤差估計式定理（充分性條件）

設函數

φ(x)

在[a,b]上連續，且(1)對x∈[a,b],有φ

(x)∈[a,b](2)存在0<L<1，使對任意x∈[a,b]有

|φ

′(x)|≤L<1則方程x=φ(x)在[a,b]上的根x*存在且唯一；對初值

x0∈[a,b]

,迭代過程xk+1=

φ

(xk)均收斂于方程的根x*。定理中的(1)對x∈[a,b],有φ(x)∈[a,b]，稱為適定性（映內性）。證明先證根的存在性。作連續函數ψ(x)=x-φ(x),由條件（1）x∈[a,b],φ

(x)∈[a,b]，即a≤φ(x)、x≤b,于是

ψ(a)=a-φ

(a)≤0

ψ(b)=b-φ(b)≥0

由于ψ(x)是連續函數，故必存在

x*∈[a,b]

使ψ(x*)=0.即ψ(x*)=x*-φ(x*)=0.于是

x*=φ

(x*)即x*為方程

x=φ

(x)的根。其次，證根的唯一性。

設y*也是方程的根，則x*=φ(x*),y*=φ(y*),x*-y*=φ(x*)–φ(y*)=φ′(ξ)(x*-y*)x*-y*–φ′(ξ)(x*-y*)=0，（x*-y*）[1-

φ′(ξ)]=0由條件（2）|φ′(x)|≤L<1，故有x*-y*=0，即x*=y*所以方程在[a,b]的根唯一。

再證迭代的收斂性。由xk=φ(xk-1),x*=φ(x*),有|xk-x*|=|φ′(ξ)(xk-1-x*)|≤L|xk-1-x*|≤L2|xk-2-x*|≤L3|xk-3-x*|≤……≤Lk|x0-x*|→0（k→∞）

所以，對[a,b]上任取的x0,迭代公式xk+1=φ(xk

)都收斂于x*。L越小收斂得越快。定理是充分性條件xk-x*=φ(xk-1)–φ(x*)=φ′(ξ)(xk-1-x*)推論：在定理的條件下，有誤差估計式驗后誤差估計式驗前誤差估計式證明：|xk-x*|≤L|xk-1-x*|=L|xk-1-xk+xk-x*|≤L（|xk-x*|+|xk-1-xk|）（1-L)|xk-x*|≤L|xk-1-xk|迭代法的終點判斷：只要相鄰兩次迭代值的偏差充分小，就能保證迭代值足夠準確，因而用|xk-xk-1|控制迭代過程的結束。定理設在區間[a,b]上方程x=φ(x)有根x*,且對一切x∈[a,b]都有|

φ′(x)|≥1，則對于該區間上任意x0(≠x*),迭代公式xk+1=φ(xk

)一定發散。證明不可能收斂于0。計算結果見下表取方程的根2.0946。由于，故取

迭代法的局部收斂性由于在實際應用中根

x*

事先不知道，故條件|φ′(x*)|<1無法驗證。但已知根的初值x0在根

x*鄰域，又根據φ′(x)的連續性，則可采用

|φ′(x0)|<1來代替|φ′(x*)|<1，判斷迭代的收斂性。

例求方程

x=e

–x在x=0.5附近的一個根，按5位小數計算，結果的精度要求為ε=10–3.解迭代公式xk+1=e

–xk，取φ

(x)=e–x,迭代公式xk+1=e

–xk收斂。迭代結果:

0123450.50.606530.545240.579700.560070.57117

0.10653－0.061290.03446－0.019630.011106789100.564860.568440.566410.567560.56691－0.006310.00358－0.002030.00115－0.00065kxkxk–xk-1xk–xk-1k

xk|x10-x9|=0.00065<ε，故x*≈x10≈0.567x0=