解非線性方程組的數(shù)值方法

在科學(xué)研究的數(shù)學(xué)問(wèn)題中更多的是非線性問(wèn)題，它們又常常歸結(jié)為非線性方程或非線性方程組的求解問(wèn)題。第一節(jié)非線性方程求根的迭代法第二節(jié)非線性方程組的簡(jiǎn)單迭代法第三節(jié)非線性方程組的Newton型迭代法第四節(jié)無(wú)約束優(yōu)化算法第八章非線性方程組的數(shù)值方法2/4/20231滿足方程(1)的x值通常叫做方程的根或解，也叫函數(shù)f(x)=0的零點(diǎn)。非線性方程的一般形式f(x)=0(1)這里f(x)是單變量x的函數(shù)，它可以是代數(shù)多項(xiàng)式

f(x)=a0+a1x+……+anxn

(an≠0)也可以是超越函數(shù)，即不能表示為上述形式的函數(shù)。第一節(jié)非線性方程求根的迭代法2/4/20232

在用近似方法時(shí)，需要知道方程的根所在區(qū)間。若區(qū)間a,b含有方程f(x)=0的根，則稱a,b為f(x)=0的有根區(qū)間；若區(qū)間a,b僅含方程f(x)=0的一個(gè)根，則稱a,b為f(x)=0的一個(gè)隔根區(qū)間。求隔根區(qū)間有兩種方法：一、非線性方程求根的基本問(wèn)題包括：根的存在性、根的隔離和根的精確化

根的存在定理(零點(diǎn)定理)：

f(x)為[a,b]上的連續(xù)函數(shù)，若f(a)·f(b)<0，則[a,b]中至少有一個(gè)實(shí)根。如果f(x)在[a,b]上還是單調(diào)遞增或遞減的，則f(x)=0僅有一個(gè)實(shí)根。2/4/20233例如，求方程3x-1-cosx=0的隔根區(qū)間。將方程等價(jià)變形為3x-1=cosx

，易見y=3x-1與y=cosx的圖像只有一個(gè)交點(diǎn)位于[0.5，1]內(nèi)。畫出y=f(x)的略圖，從而看出曲線與x軸交點(diǎn)的大致位置。也可將f(x)=0等價(jià)變形為g1(x)=g2(x)的形式，y=g1(x)與y=g2(x)兩曲線交點(diǎn)的橫坐標(biāo)所在的子區(qū)間即為含根區(qū)間。(1)描圖法2/4/20234(2)逐步搜索法運(yùn)用零點(diǎn)定理可以得到如下逐步搜索法：先確定方程f(x)=0的所有實(shí)根所在的區(qū)間為[a,b],從x0=a出發(fā),以步長(zhǎng)

h=(b-a)/n

其中n是正整數(shù)，在[a,b]內(nèi)取定節(jié)點(diǎn)：

xi=x0＋ih

(i=0,1,2，……，n)

計(jì)算f(xi)的值,依據(jù)函數(shù)值異號(hào)及實(shí)根的個(gè)數(shù)確定隔根區(qū)間,通過(guò)調(diào)整步長(zhǎng)，總可找到所有隔根區(qū)間。2/4/20235例2.2

求方程x3-3.2x2+1.9x+0.8=0的隔根區(qū)間。解：設(shè)方程的根為α，ν=max{1，|-3.2|，|1.9|}μ=max{|-3.2|,|1.9|,|0.8|}=3.2故,即有根區(qū)間為(-4.2,-0.2)和(0.2,4.2)對(duì)于m次代數(shù)方程

f(x)=xm+am-1xm-1+…+a1x+a0=0其根的模的上下界有如下結(jié)論：(1)若μ=max{|am-1|,……,|a1|,|a0|}，則方程根的模小于μ+1(2)若ν=max{1，

|am-1|,……,|a1|},則方程根的模大于2/4/20236f=inline('x^3-3.2*x^2+1.9*x+0.8')

h=1;n=4/h;fori=0:nf(-4.2+i*h)endfori=0:nf(0.2+i*h)end2/4/20237h=0.8-1.377160000000e+002-81.95600000000002-43.34800000000001-18.81999999999999-5.300000000000000.284000000000001.060000000000000.50000000000000-0.316000000000001.684000000000009.5720000000000026.42000000000000h=1-1.377160000000e+002-70.81600000000002-29.51600000000001-7.816000000000000.284000000000001.060000000000000.200000000000000.140000000000006.8800000000000026.420000000000002/4/20238定義1

若有x*滿足(x*)=0，則稱x*為方程的根或函數(shù)f(x)的零點(diǎn)，特別地，如果函數(shù)f(x)可分解為f(x)=(x

x*)mg(x)且g(x*)0,則稱x*是f(x)的m重零點(diǎn)或f(x)=0的m重根。當(dāng)m=1時(shí)，稱x*是f(x)的單根或單零點(diǎn)。

2/4/20239定理1

設(shè)函數(shù)f(x)∈Cm[a,b],則點(diǎn)p∈(a,b)是f(x)

的m重零點(diǎn)，當(dāng)且僅當(dāng)

f(p)=f’(p)=f’’(p)=…=f(m-1)(p)=0,但f(m)(p)≠0證明:(充分性)將f(x)在點(diǎn)p作m-1階Taylor展開2/4/202310由假設(shè)證畢2/4/202311例給定方程：x-sinx=0,問(wèn)x*=0是幾重零點(diǎn).解：設(shè)f(x)=x-sinx,則f(0)=0;f’(x)=1-cosx,f’(0)=0;f’’(x)=sinx,f’’(0)=0;f(3)(x)=cosx,f

(3)(0)=1;由定理1,x*=0是3重零點(diǎn).2/4/202312

知α=φ(α)，即{xk}收斂于方程的根α

。二、簡(jiǎn)單迭代法

簡(jiǎn)單迭代法又稱為不動(dòng)點(diǎn)迭代法，基本思想是首先構(gòu)造不動(dòng)點(diǎn)方程x=φ(x)，即由方程f(x)=0變換為等價(jià)形式x=φ(x),式中φ(x)稱為迭代函數(shù)。然后建立迭代格式：xk+1

=φ(xk)稱為不動(dòng)點(diǎn)迭代格式。當(dāng)給定初值x0

后,由迭代格式xk+1=φ(xk)可求得數(shù)列{xk}。如果{xk}收斂于α，且φ(x)在α連續(xù)，則α就是不動(dòng)點(diǎn)方程的根。因?yàn)椋?/4/202313迭代法的幾何意義記y1=x,y2=φ(x),它們交點(diǎn)的橫坐標(biāo)α即為方程的根2/4/202314xyy=xx*y=φ(x)x0p0x1p1xyy=xx*y=φ(x)x0p0x1p1xyy=xx*y=φ(x)x0p0x1p1xyy=xx*y=φ(x)x0p0x1p12/4/202315對(duì)于迭代法需要討論的基本問(wèn)題是，迭代函數(shù)的構(gòu)造，迭代序列的收斂性和收斂速度以及誤差估計(jì)。問(wèn)題：φ(x)的形式不唯一，如：2/4/202316取初始值，計(jì)算結(jié)果如下：

0.3

0.3

-0.0047

0.3617

-1.0108

0.3732

0.3753

0.37572/4/202317用蛛網(wǎng)圖觀察不動(dòng)點(diǎn)迭代zlxp1132/4/202318若從任何可取的初值出發(fā)都能保證收斂，則稱它為大范圍收斂。如若為了保證收斂性必須選取初值充分接近于所要求的根，則稱它為局部收斂。通常局部收斂方法比大范圍收斂方法收斂得快。因此，一個(gè)合理的算法是先用一種大范圍收斂方法求得接近于根的近似值（如對(duì)分法），再以其作為新的初值使用局部收斂法（如迭代法）。這里討論迭代法的收斂性時(shí)，均指的是局部收斂性。2/4/202319考慮方程x=φ(x),φ(x)C[a,b],若(I)當(dāng)x[a,b]時(shí)，φ(x)[a,b]；(II)對(duì)x[a,b],有

|φ’(x)|L<1成立。則任取x0[a,b]，由xk+1=φ

(xk)得到的序列收斂于φ(x)

在[a,b]上的唯一不動(dòng)點(diǎn)。并且有誤差估計(jì)式：(k=1,2,…)且存在極限定理2（收斂定理）2/4/202320證明：①φ(x)

在[a,b]上存在不動(dòng)點(diǎn)？令有根②不動(dòng)點(diǎn)唯一？反證：若不然，設(shè)還有，則在和之間而2/4/202321③當(dāng)k

時(shí)，

xk收斂到x*？④2/4/202322⑤⑥注：定理?xiàng)l件非必要條件，可將[a,b]縮小，定義局部收斂性：若在x*的某領(lǐng)域B={x||xx*|}有φC1[a,b]且|φ’(x*)|<1，則由x0B開始的迭代收斂。即調(diào)整初值可得到收斂的結(jié)果。2/4/202323迭代法收斂階則稱數(shù)列為階收斂，也稱相應(yīng)的迭代法為階方法。當(dāng)且時(shí)，稱數(shù)列為線性收斂.當(dāng)時(shí)，稱數(shù)列平方收斂（或二階收斂）.當(dāng)時(shí)，稱數(shù)列為超線性收斂。定義設(shè)數(shù)列收斂于,令誤差,如果存在某個(gè)實(shí)數(shù)及正常數(shù)，使2/4/202324顯然，越大，數(shù)列收斂的越快。所以，迭代法的收斂階是對(duì)迭代法收斂速度的一種度量。2/4/202325定理3（迭代法的局部收斂定理）設(shè)α是方程x=φ(x)的根，如果(1)迭代函數(shù)φ(x)在α的鄰域可導(dǎo)；(2)在α的某個(gè)鄰域S={x:|x-α|≤δ},對(duì)于任意的xS有則對(duì)于任意的初值x0S

，迭代公式xn+1=φ(xn)

產(chǎn)生的數(shù)列{xn}，收斂于方程的根α

。2/4/202326定理3’（迭代法的局部收斂定理）設(shè)α是方程x=φ(x)的根，如果(1)迭代函數(shù)φ(x)在α的鄰域一階導(dǎo)數(shù)連續(xù)；則存在α的某個(gè)鄰域S={x:|x-α|≤δ}

及正數(shù)L<1,使對(duì)于任意的xS有取任意的初值x0S

，迭代公式xn+1=φ(xn)

產(chǎn)生的數(shù)列{xn}，收斂于方程的根α

。2/4/202327控制誤差ε的方法：(1)先計(jì)算滿足誤差要求的迭代次數(shù)n，再迭代。由可得(2)事后誤差估計(jì)法。由于因而可用|xn-xn-1|≤ε來(lái)控制迭代過(guò)程。2/4/202328例

用迭代法求x3-x2-1=0在隔根區(qū)間[1.4,1.5]內(nèi)的根，要求準(zhǔn)確到小數(shù)點(diǎn)后第4位.解：(1)由方程的等價(jià)形式構(gòu)造迭代公式由2/4/202329知φ(x)在（1.4,1.5)可導(dǎo)，且故迭代法收斂。2/4/202330functiony=diedai(fname,x0,e,N)%用途:迭代法求解非線性方程f(x)=0y=x0;x0=y+2*e;k=0;whileabs(x0-y)>e&k<Nk=k+1;x0=y;y=fname(x0);

disp(y)endifk==N

disp('warning')end

f=inline('(x^2+1)^(1/3)');y=diedai(f,1.5,10^(-4),500);2/4/202331三、牛頓迭代法任取初始值，上過(guò)點(diǎn)的切線方程為：與軸交于點(diǎn)過(guò)點(diǎn)的切線方程為與軸交于點(diǎn)如此下去得牛頓迭代公式:用切線代替曲線，用線性函數(shù)的零點(diǎn)作為

f(x)的零點(diǎn)的近似值。2/4/202332（收斂的充分條件）設(shè)f

C2[a,b]，若(1)f(a)f(b)<0；(2)在整個(gè)[a,b]上f”不變號(hào)且f’(x)0；(3)選取x0

[a,b]使得f(x0)f”(x0)>0；則Newton’sMethod產(chǎn)生的序列{xk}收斂到f(x)在[a,b]的唯一根。根唯一產(chǎn)生的序列單調(diào)有界，保證收斂。定理42/4/202333yx0bax0yx0bax0yx0bax0yx0Bax02/4/202334例

用迭代法求在隔根區(qū)間[1.4,1.5]內(nèi)的根，要求準(zhǔn)確到小數(shù)點(diǎn)后第4位。（1）牛頓迭代公式為（2）當(dāng)時(shí)有，因,故取,牛頓迭代法收斂。2/4/202335functiony=newton(fname,dfname,x0,e,N)y=x0;x0=y+2*e;k=0;whileabs(x0-y)>e&k<Nk=k+1;x0=y;y=x0-fname(x0)/dfname(x0);

disp(y)endifk==N

disp('warning')end2/4/202336

f=inline('x^3-x^2-1');

df=inline('3*x^2-2*x');y=newton(f,df,1.5,0.5*10^(-4),500)2/4/202337（局部收斂性）設(shè)f

C2[a,b]，若x*

為f(x)在[a,b]上的根，且f’(x*)0，則存在x*的鄰域使得任取初值，Newton’sMethod產(chǎn)生的序列{xk}收斂到x*，且滿足定理5證明：Newton’sMethod事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代其中，則收斂由Taylor展開：2/4/202338只要f’(x*)0，則令可得結(jié)論。注：在單根附近收斂快，是平方收斂的．由Taylor展開：2/4/202339

對(duì)于迭代過(guò)程，如果在所求根的鄰近連續(xù)，并且(*)

則該迭代過(guò)程在點(diǎn)鄰近是P階收斂的。定理6證明：由于。據(jù)上定理，立即可以斷定迭代過(guò)程具有局部收斂性。再將在根處展開，利用條件(*)，則有注意到，由上式得2/4/202340因此對(duì)迭代誤差有:。這表明迭代過(guò)程確實(shí)為P階收斂，證畢。2/4/2023412/4/2023422/4/2023432/4/2023442/4/2023451、優(yōu)點(diǎn)：牛頓迭代法具有平方收斂的速度，所以在迭代過(guò)程中只要迭代幾次就會(huì)得到很精確的解。這是牛頓迭代法比簡(jiǎn)單迭代法優(yōu)越的地方。牛頓迭代法的優(yōu)缺點(diǎn)2、缺點(diǎn)：選定的初值要接近方程的解，否則有可能得不到收斂的結(jié)果。再者，牛頓迭代法計(jì)算量比較大。因每次迭代除計(jì)算函數(shù)值外還要計(jì)算微商值。2/4/202346牛頓法主要有兩個(gè)缺點(diǎn)：局部收斂，計(jì)算量大。2/4/202347割線法的幾何意義用割線代替曲線，用線性函數(shù)的零點(diǎn)作為

f(x)的零點(diǎn)的近似值。收斂階為P=1.6182/4/202348（Horner算法）四、高次代數(shù)方程求根的嵌套算法2/4/2023492/4/202350五、迭代法和離散動(dòng)力系統(tǒng)

對(duì)于一個(gè)給定的迭代法，它產(chǎn)生的序列除了收斂于一個(gè)固定點(diǎn)外，還可能有十分復(fù)雜的行為。研究當(dāng)時(shí)漸近行為成為離散動(dòng)力系統(tǒng)這門學(xué)科分支所關(guān)注的內(nèi)容。它的理論、方法和結(jié)果不但對(duì)科學(xué)計(jì)算有重大意義，近年來(lái)它也為其他領(lǐng)域的科學(xué)家深感興趣，它所引出的混沌、分形等術(shù)語(yǔ)已廣泛出現(xiàn)在各類文獻(xiàn)中。2/4/202351考慮二次函數(shù)的迭代，即一維離散動(dòng)力系統(tǒng)其中是一個(gè)可變的參數(shù)，觀察不同的r值對(duì)迭代點(diǎn)列的影響。1.取r=[00.30.60.91.21.51.82.12.42.73.03.33.63.9],觀察迭代序列的極限。2/4/202352（1）當(dāng)r

分別等于0,0.3,0.6,0.9,1.2,1.5,1.8,2.1,2.4時(shí)，每個(gè)r所對(duì)應(yīng)的后50個(gè)迭代值均重合為一點(diǎn)，這說(shuō)明對(duì)這些值極限存在。（2）當(dāng)r

分別等于3.0,3.3時(shí)，迭代值對(duì)應(yīng)兩個(gè)點(diǎn)，這說(shuō)明極限不存在。（3）當(dāng)r

分別等于3.6,3.9時(shí)，出來(lái)更多的點(diǎn)。zlx12/4/2023532.用蛛網(wǎng)圖觀察三種不同類型的迭代r=2.7r=3.2r=3.90.2,0.5120,0.7995,0.5129,0.7995,0.5130,0.7995,0.5130,…構(gòu)成一個(gè)二循環(huán)zlx22/4/2023543.加密r的值，得到Feigenbaum圖。

我們看到，隨著r的增加，圖中從開始的一條曲線（不動(dòng)點(diǎn)）分裂為兩條曲線（2周期循環(huán)）,4條曲線（4周期循環(huán)）,8條曲線（8周期循環(huán)）,…,這種現(xiàn)象叫倍周期現(xiàn)象。zlx002/4/202355第二節(jié)非線性方程組的簡(jiǎn)單迭代法

一、引言2/4/202356非線性方程組解的復(fù)雜性2/4/202357clear,clfx1=-2:.2:2;y2=-2:.2:2;y1=f1(x1);x2=f2(y2);plot(x1,y1,'r:',x2,y2,'b')xlabel('x'),ylabel('y')(3)a=0(4)a=-1(1)a=1(2)a=1/42/4/202358幾類典型非線性問(wèn)題2/4/2023592/4/202360例：半線性橢圓型邊值問(wèn)題解:(1)剖分求解域.YN+1N:210012….NN+1X2/4/202361(2)對(duì)微分算子進(jìn)行離散.2/4/202362在每個(gè)點(diǎn)(xi