非線性方程求根

非線性方程求根第一頁，共五十七頁，2022年，8月28日第二章非線性方程的求根方法引言方程求根的二分法迭代法及其收斂性Newton迭代法第二頁，共五十七頁，2022年，8月28日方程是在科學研究中不可缺少的工具；方程求解是科學計算中一個重要的研究對象；幾百年前就已經(jīng)找到了代數(shù)方程中二次至五次方程的求解公式；但是，對于更高次數(shù)的代數(shù)方程目前仍無有效的精確解法；對于無規(guī)律的非代數(shù)方程的求解也無精確解法；因此，研究非線性方程的數(shù)值解法成為必然。2.1 引言第三頁，共五十七頁，2022年，8月28日非線性方程的一般形式：f(x)=0代數(shù)方程：f(x)=a0+a1x+……+anxn

（an0）超越方程：f(x)中含三角函數(shù)、指數(shù)函數(shù)、或其他超越函數(shù)。用數(shù)值方法求解非線性方程的步驟：（1）找出隔根區(qū)間；（只含一個實根的區(qū)間稱隔根區(qū)間）（2）近似根的精確化。從隔根區(qū)間內(nèi)的一個或多個點出發(fā)，逐次逼近，尋求滿足精度的根的近似值。2.1 引言第四頁，共五十七頁，2022年，8月28日2.2方程求根的二分法二分法的基本思想： 假定f(x)=0在[a,b]內(nèi)有唯一單實根x*，考察有根區(qū)間[a,b]，取中點x0=(a+b)/2，若f(x0)=0，則x*=x0，否則，（1）若f(x0)f(a)>0，則x*在x0右側(cè)，令a1=x0，b1=b;（2）若f(x0)f(a)<0，則x*在x0左側(cè)，令a1=a，b1=x0。定理1（介值定理）設函數(shù)f(x)在區(qū)間[a,b]連續(xù)，且f(a)f(b)<0，則方程f(x)=0在區(qū)間[a,b]內(nèi)至少有一個根。第五頁，共五十七頁，2022年，8月28日

以[a1,b1]為新的隔根區(qū)間，且其長度僅為[a,b]的一半，對[a1,b1]重復前過程，得新的隔根區(qū)間[a2,b2]，如此二分下去，得一系列隔根區(qū)間：

[a,b][a1,b1][a2,b2]…[ak,bk]……

其中每個區(qū)間長度都是前一區(qū)間的一半，故[ak,bk]的長度：當k趨于無窮時趨于0。即若二分過程無限繼續(xù)下去，這些區(qū)間最后必收斂于一點x*，即方程的根。第六頁，共五十七頁，2022年，8月28日

性質(zhì)：f(an)·f(bn)<0;bn–

an=(b–a)/2n2.2方程求根的二分法 每次二分后，取有根區(qū)間的中點xk=(ak+bk)/2作為根的近似值，則可得一近似根序列：x0,

x1,

x2,…該序列必以根x*為極限。始終收斂 實際計算中，若給定充分小的正數(shù)0和允許誤差限1，當|f(xn)|<0或bn-an<1時，均可取x*xn。第七頁，共五十七頁，2022年，8月28日定理2

（二分法收斂定理）設x*為方程f(x)=0在[a,b]內(nèi)的唯一根，且f(x)滿足f(a)f(b)<0，則由二分法產(chǎn)生的第n個區(qū)間[an,bn]的中點xn滿足不等式2.2方程求根的二分法證明：第八頁，共五十七頁，2022年，8月28日對于預先給定的精度只需要即：或者：這時的xk就是滿足精度要求的近似值便有:第九頁，共五十七頁，2022年，8月28日例2.1用二分法求方程在區(qū)間[1,1.5］內(nèi)的一個實根，要求誤差不超過0.005。解因為即只要二分6次，便能達到所要求的精度。所以f(x)在區(qū)間[1,1.5]上單調(diào)增加，且f(1)f(1.5)<0,故根唯一且滿足介值定理的條件，故可直接求得：第十頁，共五十七頁，2022年，8月28日計算結(jié)果kakbkxkf(xk)01.01.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-第十一頁，共五十七頁，2022年，8月28日第十二頁，共五十七頁，2022年，8月28日計算過程簡單，收斂性可保證；對函數(shù)的性質(zhì)要求低，只要連續(xù)即可。收斂速度慢；不能求復根和重根；調(diào)用一次求解一個[a,b]間的多個根無法求得。二分法求解非線性方程的優(yōu)缺點：第十三頁，共五十七頁，2022年，8月28日不動點迭代法不動點的存在性與迭代法的收斂性迭代收斂的加速方法2.3迭代法及其收斂性第十四頁，共五十七頁，2022年，8月28日迭代法的基本思想：迭代法是一種逐次逼近的方法，用某個固定公式反復校正根的近似值，使之逐步精確化，最后得到滿足精度要求的結(jié)果。例：求方程x3-x-1=0在x=1.5附近的一個根。解：將所給方程改寫成假設初值x0=1.5是其根，代入得x1≠x0，再將x1代入得x2≠x1，再將x2代入得第十五頁，共五十七頁，2022年，8月28日如此下去，這種逐步校正的過程稱為迭代過程。這里用的公式稱為迭代公式，即k=0,1,2,……迭代結(jié)果見下表：

k

xk

k

xk012341.51.357211.330861.325881.3249456781.324761.324731.324721.32472僅取六位數(shù)字，x7與x8相同，即認為x8是方程的根。x*≈x8=1.32472第十六頁，共五十七頁，2022年，8月28日2.3.1不動點迭代法將連續(xù)函數(shù)方程f(x)＝0改寫為等價形式：x=(x)其中(x)也是連續(xù)函數(shù)，稱為迭代函數(shù)。不動點：若x*滿足f(x*)=0，則x*=(x*)；反之，若x*=(x*)，則f(x*)=0，稱x*為(x)的一個不動點。不動點迭代：(k=0,1,……)若對任意x0[a,b]，由上述迭代得序列{xk}，有極限則稱迭代過程收斂，且x*=(x*)為(x)的不動點。第十七頁，共五十七頁，2022年，8月28日但迭代法并不總令人滿意，如將前述方程x3-x-1=0改寫為另一等價形式：建迭代公式：仍取初值x0=1.5，則有x1=2.375，x2=12.396，x3=1904,結(jié)果越來越大。此時稱迭代過程發(fā)散。x2

x1

x0y=x幾何意義：第十八頁，共五十七頁，2022年，8月28日收斂發(fā)散第十九頁，共五十七頁，2022年，8月28日定理3（不動點的存在性和唯一性）

設(x)C[a,b]且滿足以下兩個條件：（1）對于任意x[a,b]，有a≤(x)≤b；（2）若(x)在[a,b]一階連續(xù)，且存在常數(shù)0<L<1，使得對任意x[a,b]，成立

|’(x)|≤L

則(x)在[a,b]上存在唯一的不動點x*。2.3.2不動點的存在性與迭代法的收斂性第二十頁，共五十七頁，2022年，8月28日不動點的存在性證明：證：若或顯然(x)在[a,b]有不動點a或b；否則，設則有（因a≤(x)≤b）記則有故存在x*使得即x*即為不動點。第二十一頁，共五十七頁，2022年，8月28日不動點存在的唯一性證明：設有x1*≠x2*,使得則由拉格朗日中值定理有：其中，ξ介于x1*和x2*之間。由定理條件可得矛盾！故

x1*=x2*，不動點唯一。第二十二頁，共五十七頁，2022年，8月28日定理4（全局收斂性）設(x)C

[a,b]且滿足以下兩個條件：則對任意x0[a,b]，由xn+1=(xn)得到的迭代序列{xn}收斂到(x)的不動點x*，并有誤差估計：（2）若(x)在[a,b]一階連續(xù)，且存在常數(shù)0<L<1，使得對任意x[a,b]，成立 |’(x)|≤L（1）對于任意x[a,b]，有a≤(x)≤b；第二十三頁，共五十七頁，2022年，8月28日(0<L<1)故迭代格式收斂。所以證明：第二十四頁，共五十七頁，2022年，8月28日反復遞推，可得誤差估計式:上述式子的意義在于:只要前后兩次近似值的差值足夠小，就可以近似值xn+1達到任意的精度。第二十五頁，共五十七頁，2022年，8月28日定義設(x)有不動點x*，若存在x*的某鄰域R：|x-x*|≤，對任意x0R，迭代過程xk+1=(xk)產(chǎn)生的序列{xk

}R且收斂到x*，則稱不動點迭代法xk+1=(xk)局部收斂。 定理4給出的收斂性稱全局收斂性，實際上其條件在較大的有根區(qū)間上是很難保證的，應用時通常只在不動點x*鄰近考察其收斂性，稱局部收斂性。第二十六頁，共五十七頁，2022年，8月28日證明：根據(jù)連續(xù)函數(shù)性質(zhì)，因’(x)連續(xù)，存在x*的某鄰域R：|x-x*|≤，對任意x

R，|’(x)|≤L<1(閉區(qū)間上的連續(xù)函數(shù)能取到最大值和最小值），且

|(x)-x*|=|(x)-(x*)|=|’(ξ)||x-x*|

≤L|x-x*|≤|x-x*|≤

即對任意x

R，總有(x)

R。由全局收斂性定義知，迭代過程xk+1=(xk

)對于任意初值x0R均收斂。定理5（局部收斂性）設x*為(x)的不動點，’(x)在x*的某鄰域連續(xù)，且|’(x*)|<1，則不動點迭代法xk+1=(xk

)局部收斂。第二十七頁，共五十七頁，2022年，8月28日例用不同方法求的根。解：格式（1）格式（2）格式（3）格式（4）第二十八頁，共五十七頁，2022年，8月28日取x0=2，對上述四種方法，計算三步所得結(jié)果如下：k xk

(1)(2) (3) (4)0 x0

22 2 2x1

3 1.5 1.75 1.75x29 2 1.73475 1.732143x3

87 1.5 1.732361 1.732051第二十九頁，共五十七頁，2022年，8月28日收斂階定義：設迭代過程xk+1=(xk)收斂于方程x=(x

)的根x*，若迭代誤差ek=xk–x*

當k時成立下列漸近關(guān)系式：（c為常數(shù)，且c0）則稱迭代過程是r階收斂的。特別地，r=1時稱線性收斂；

r=2時稱平方收斂；

r>1時稱超線性收斂。且r

越大，收斂越快。第三十頁，共五十七頁，2022年，8月28日定理：設x*為x=(x

)的不動點，若(x

)滿足：（1）(x

)在x*附近有連續(xù)的p階導數(shù)(p>1)；（2）則迭代過程xn+1=(xn)在點x*鄰近是p階收斂的。得所以故迭代過程xn+1=(xn

)

p階收斂。證：由Taylor公式第三十一頁，共五十七頁，2022年，8月28日Newton迭代法及其收斂性簡化Newton迭代法（平行弦法）弦截法Newton下山法重根情形2.4Newton迭代法第三十二頁，共五十七頁，2022年，8月28日設方程f(x)=0有第k次近似根xk（f’(xk)0），將f(x)在xk展開： （在x和xk之間）2.4.1Newton迭代法及其收斂性基本思想：將非線性方程逐步歸結(jié)為某種線性方程求解?？稍O第三十三頁，共五十七頁，2022年，8月28日記該線性方程的根為第k+1次近似xk+1，則 故f(x)=0可近似表示為即為Newton法迭代格式。（k=0,1,……）第三十四頁，共五十七頁，2022年，8月28日Newton迭代法的幾何意義：（亦稱切線法）xyx*xk+1xkPky=f(x)顯然y=f(x)在點（xk,f(xk)）處的切線方程為：它與x軸交點的橫坐標即為上述第k+1次近似:第三十五頁，共五十七頁，2022年，8月28日Newton迭代法的收斂性：迭代函數(shù)：定理：假設f(x)在x*的某鄰域內(nèi)具有連續(xù)的二階導數(shù)，且設f(x*)=0，f’(x*)0，則對充分靠近x*的初始值x0，Newton迭代法產(chǎn)生的序列{xn}至少平方收斂于x*。設f(x*)=0，f’(x*)0，則’(x*)=0，故Newton迭代法在x*附近至少平方收斂。第三十六頁，共五十七頁，2022年，8月28日解：f’(x)=ex+xex，故newton迭代公式為k

xk

0 0.51 0.571022 0.567163 0.56714迭代3次即可達到4位有效數(shù)字的近似解0.56714。若用迭代公式則達到同有效數(shù)字需18次。例：用newton迭代法解方程xex-1=0。即取迭代初值x0=0.5，結(jié)果如下：第三十七頁，共五十七頁，2022年，8月28日Newton迭代法的缺陷：1.被零除錯誤2.程序死循環(huán)y=arctanx方程:f(x)=x3–3x+2=0在重根x*=1附近，f’(x)近似為零。對f(x)=arctanx存在x0，Newton迭代法陷入死循環(huán)。第三十八頁，共五十七頁，2022年，8月28日若|’(x)|=|1-cf’(x)|<1，即取0<cf’(x)<2在x*附近成立，則收斂。若取c=1/f’(x0)，則稱簡化Newton法。2.4.2簡化Newton法（平行弦法）迭代公式：（c0,k=0,1,……）迭代函數(shù)：第三十九頁，共五十七頁，2022年，8月28日在Newton迭代格式中，用差商近似導數(shù)，2.4.3弦截法（割線法）稱弦截法。得第四十頁，共五十七頁，2022年，8月28日弦截法的幾何意義：xyx*xk+1xk-1Pk-1y=f(x)xkPk弦線PkPk-1的方程：當y＝0時，第四十一頁，共五十七頁，2022年，8月28日例用簡化的Newton迭代法和弦截法計算方程x3-3x+1=0的根。解：設f(x)=x3-3x+1，則f`(x)=3x2-3由簡化的Newton法，得由弦截法，得第四十二頁，共五十七頁，2022年，8月28日x0=0.5x1=0.3333333333x2=0.3497942387x3=0.3468683325x4=0.3473702799x5=0.3472836048x6=0.3472985550x7=0.3472959759x8=0.3472964208x9=0.3472963440x10=0.3472963572x11=0.3472963553x0=0.5;x1=0.4;x2=0.3430962343x3=0.3473897274x4=0.3472965093x5=0.3472963553x6=0.3472963553簡化Newton法弦截法要達到8位有效數(shù)字，簡化Newton法迭代11次，弦截法迭代5次，Newton迭代法迭代4次。第四十三頁，共五十七頁，2022年，8月28日無論前面哪種迭代法：（Newton迭代法、簡化Newton法、弦截法）Newton迭代法x0=2x1=-3.54x2=13.95x3=-279.34x4=122017是否收斂均與初值的位置有關(guān)。如x0=1x1=-0.5708x2=0.1169x3=-0.0011x4=7.9631e-010x5=0收斂發(fā)散第四十四頁，共五十七頁，2022年，8月28日為防止Newton法發(fā)散，可增加一個條件：|f(xk+1)|<|f(xk)|，滿足該條件的算法稱下山法?？捎孟律椒ūＷC收斂，Newton法加快速度。2.4.4Newton下山法稱Newton下山法。（0<1,—下山因子）記即第四十五頁，共五十七頁，2022年，8月28日從=1開始，逐次減半計算。的順序，直到使下降條件|f(xk+1)|<|f(xk)|成立為止。的選?。杭窗吹谒氖?，共五十七頁，2022年，8月28日例：求解方程要求達到精度|xn-xn-1|≤10-5，取x0=-0.99。解：先用Newton迭代法：f`(x)=x2-1x2=21.69118 x3=15.15689x4=9.70724x5=6.54091x6=4.46497x7=3.13384x8=2.32607

x9=1.90230x10=1.75248x11=1.73240x12=1.73205x13=1.73205需迭代13次才達到精度要求第四十七頁，共五十七頁，2022年，8月28日用Newton下山法，結(jié)果如下：k=0x0=-0.99f(x0)=0.666567k=1x1=32.505829f(x)=11416.4

=0.5x1=15.757915f(x)=1288.5

=0.25x1=7.383958f(x)=126.8

=0.125x1=3.196979f(x)=7.69

=0.0625x1=1.103489f(x)=-0.655k=2x2=4.115071f(x)=19.1

=0.5x2=2.60928f(x)=3.31

=0.25x2=1.85638f(x)=0.27k=3x3=1.74352f(x)=0.023k=4x4=1.73216f(x)=0.00024k=5x5=1.73205f(x)=0.00000k=6x6=1.73205f(x)=0.000000k

下山因子

xk

f(xk)第四十八頁，共五十七頁，2022年，8月28日設f(x)=(x-x*)m

g(x),m

2，m為整數(shù)，g(x*)0,則x*為方程f(x)=0的m重根。此時有

f(x*)=f`(x*)=……=f(m-1)(x*)=0,f(m)(x*)02.4.5重根情形《方法一》只要f`(xk

)0，仍可用Newton法計算，此時為線性收斂?！斗椒ǘ啡羧t`(x*)=0，用迭代法求m重根，則具2