非線性方程求根

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

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

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

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

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

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

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

x1,

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

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

k

xk

k

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

x1

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

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

|’(x)|≤L

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

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

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

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

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

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

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

即對(duì)任意x

R，總有(x)

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

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

)局部收斂。第二十七頁(yè)，共五十七頁(yè)，2022年，8月28日例用不同方法求的根。解：格式（1）格式（2）格式（3）格式（4）第二十八頁(yè)，共五十七頁(yè)，2022年，8月28日取x0=2，對(duì)上述四種方法，計(jì)算三步所得結(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第二十九頁(yè)，共五十七頁(yè)，2022年，8月28日收斂階定義：設(shè)迭代過(guò)程xk+1=(xk)收斂于方程x=(x

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

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

r=2時(shí)稱平方收斂；

r>1時(shí)稱超線性收斂。且r

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

)的不動(dòng)點(diǎn)，若(x

)滿足：（1）(x

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

)

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

xk

0 0.51 0.571022 0.567163 0.56714迭代3次即可達(dá)到4位有效數(shù)字的近似解0.56714。若用迭代公式則達(dá)到同有效數(shù)字需18次。例：用newton迭代法解方程xex-1=0。即取迭代初值x0=0.5，結(jié)果如下：第三十七頁(yè)，共五十七頁(yè)，2022年，8月28日Newton迭代法的缺陷：1.被零除錯(cuò)誤2.程序死循環(huán)y=arctanx方程:f(x)=x3–3x+2=0在重根x*=1附近，f’(x)近似為零。對(duì)f(x)=arctanx存在x0，Newton迭代法陷入死循環(huán)。第三十八頁(yè)，共五十七頁(yè)，2022年，8月28日若|’(x)|=|1-cf’(x)|<1，即取0<cf’(x)<2在x*附近成立，則收斂。若取c=1/f’(x0)，則稱簡(jiǎn)化Newton法。2.4.2簡(jiǎn)化Newton法（平行弦法）迭代公式：（c0,k=0,1,……）迭代函數(shù)：第三十九頁(yè)，共五十七頁(yè)，2022年，8月28日在Newton迭代格式中，用差商近似導(dǎo)數(shù)，2.4.3弦截法（割線法）稱弦截法。得第四十頁(yè)，共五十七頁(yè)，2022年，8月28日弦截法的幾何意義：xyx*xk+1xk-1Pk-1y=f(x)xkPk弦線PkPk-1的方程：當(dāng)y＝0時(shí)，第四十一頁(yè)，共五十七頁(yè)，2022年，8月28日例用簡(jiǎn)化的Newton迭代法和弦截法計(jì)算方程x3-3x+1=0的根。解：設(shè)f(x)=x3-3x+1，則f`(x)=3x2-3由簡(jiǎn)化的Newton法，得由弦截法，得第四十二頁(yè)，共五十七頁(yè)，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簡(jiǎn)化Newton法弦截法要達(dá)到8位有效數(shù)字，簡(jiǎn)化Newton法迭代11次，弦截法迭代5次，Newton迭代法迭代4次。第四十三頁(yè)，共五十七頁(yè)，2022年，8月28日無(wú)論前面哪種迭代法：（Newton迭代法、簡(jiǎn)化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ā)散第四十四頁(yè)，共五十七頁(yè)，2022年，8月28日為防止Newton法發(fā)散，可增加一個(gè)條件：|f(xk+1)|<|f(xk)|，滿足該條件的算法稱下山法。可用下山法保證收斂，Newton法加快速度。2.4.4Newton下山法稱Newton下山法。（0<1,—下山因子）記即第四十五頁(yè)，共五十七頁(yè)，2022年，8月28日從=1開(kāi)始，逐次減半計(jì)算。的順序，直到使下降條件|f(xk+1)|<|f(xk)|成立為止。的選?。杭窗吹谒氖?yè)，共五十七頁(yè)，2022年，8月28日例：求解方程要求達(dá)到精度|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次才達(dá)到精度要求第四十七頁(yè)，共五十七頁(yè)，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)第四十八頁(yè)，共五十七頁(yè)，2022年，8月28日設(shè)f(x)=(x-x*)m

g(x),m

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

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

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