第7章非線性方程求根剖析課件

第7章非線性方程求根第一節(jié)方程求根與二分法本章主要討論單變量的非線性方程求根問(wèn)題1非線性方程根的不同情況設(shè)非線性方程為：f(x)=0

當(dāng)f(x)為多項(xiàng)式時(shí)，非線性方程是一種特殊形式的方程，即多項(xiàng)式方程，也叫n

次代數(shù)方程

。若x*使得f(x*)=0，則稱x*為方程f(x)=0的根或函數(shù)f(x)的零點(diǎn)。

2非線性方程根的不同情況若f(x)可表示成：且g(x*)≠0當(dāng)m=1時(shí)，x*稱為f(x)的單根；當(dāng)m>1時(shí)，x*稱為方程f(x)的m重根，或函數(shù)f(x)的m重零點(diǎn)。n次的非線性方程在復(fù)數(shù)域內(nèi)有且僅有n個(gè)根。3求根的方法對(duì)于1次、2次的多項(xiàng)式方程，已經(jīng)有成熟、有效的解法；對(duì)于3次、4次的多項(xiàng)式方程，也有公式可以使用，但形式較為復(fù)雜；高于4次的多項(xiàng)式方程早在1830年就證明了不可能用公式求解。4求根的方法根據(jù)前面的討論，可以把次數(shù)高于2次的多項(xiàng)式方程同一般的非線性方程f(x)=0的求解作為相同的問(wèn)題進(jìn)行研究。對(duì)這類問(wèn)題通常采用區(qū)間法或迭代法求解。5非線性方程的有根區(qū)間若f(x)滿足條件:(1)在[a,b]內(nèi)連續(xù),(2)f(a)·f(b)<0,則f(x)=0在[a,b]內(nèi)必有根。f(x)的有根區(qū)間在微積分中有這樣的定理：若f(x)在[a,b]內(nèi)還嚴(yán)格單調(diào),則f(x)=0在[a,b]內(nèi)只有一根。6非線性方程的有根區(qū)間例：判斷方程f(x)=x4-4x3+1=0

有幾個(gè)實(shí)根，有根區(qū)間是什么？由

f(x)=4x2(x-3)=0得駐點(diǎn)

x1=0,x2=3。因此將實(shí)軸分為三個(gè)區(qū)間來(lái)討論：

(-∞,0),(0,3)，(3,+∞)

f(x)

在此三區(qū)間的符號(hào)分別為“-”、“-

”、“+”7非線性方程的有根區(qū)間所以f(x)在(-∞,0),(0,3)，(3,+∞)

區(qū)間上分別單調(diào)減、單調(diào)減、單調(diào)增。分析計(jì)算可得：

f(–∞)>0,f(0)=1>0,f(3)=-26<0,f(+∞)>0可見f(x)僅有兩個(gè)實(shí)根,分別位于(0,3),(3,+∞)8非線性方程的有根區(qū)間又因?yàn)閒(4)=1>0,所以第二有根區(qū)間可縮小為(3,4)。x(-∞,0)0(0,3)3(3,4)4(4,+∞)

f(x)f(x)

-↘0+

-↘0-+↗+++↗有根區(qū)間(0,3)(3,4)9非線性方程的有根區(qū)間逐步搜索法(增值尋根法)

增值尋根法的基本思想是:從初值開始,按規(guī)定的一個(gè)初始步長(zhǎng)h來(lái)增值。同時(shí)計(jì)算。10非線性方程的有根區(qū)間搜索過(guò)程,可從a開始,也可從b開始,這時(shí)應(yīng)取步長(zhǎng)h<0。此時(shí)

即為方程的根說(shuō)明區(qū)間

內(nèi)無(wú)根

可能遇到三種情形：說(shuō)明區(qū)間

內(nèi)有根

11求方程的有根區(qū)間.解根據(jù)有根區(qū)間定義，對(duì)方程的根進(jìn)行搜索計(jì)算，結(jié)果如下表：方程的三個(gè)有根區(qū)間為［1,2］,［3,4］,［5,6］.12二分法應(yīng)用二分法的前提：已經(jīng)確定了非線性方程的有根區(qū)間[a,b]。設(shè)方程f(x)=0在區(qū)間[a,b]內(nèi)有且只有一個(gè)實(shí)根x*。即f(x)滿足條件:(1)在[a,b]內(nèi)連續(xù)；(2)f(a)·f(b)<0,(3)

f(x)在[a,b]內(nèi)嚴(yán)格單調(diào)。13二分法二分法的基本思想是：通過(guò)等分有根區(qū)間，不斷壓縮有根區(qū)間的大小。在有限步運(yùn)算中，當(dāng)區(qū)間壓縮到一定小的程度時(shí)，用其中點(diǎn)作為原方程的近似解。取有根區(qū)間[a,b]的中點(diǎn)計(jì)算f(x0)，考察f(x0)的正負(fù)情況。14二分法(1)若

f(x0)=0,

則

x0就是方程的根x*,計(jì)算結(jié)束

;(2)若

，則

令

a1=a,b1=x0;(3)若

，則

令

a1=x0

,b1=b

;此時(shí)的有根區(qū)間為[a1,b1]，該區(qū)間大小為原區(qū)間的一半。15二分法對(duì)壓縮了的有根區(qū)間[a1,b1]，實(shí)行同樣的步驟。若每次二分時(shí)所取區(qū)間中點(diǎn)都不是根，則上述過(guò)程將無(wú)限進(jìn)行下去。如此反復(fù)進(jìn)行,可得一系列有根區(qū)間16二分法由于每一區(qū)間都是前一區(qū)間的一半，因此區(qū)間[ak,bk]的長(zhǎng)度為：即當(dāng)k→∞

時(shí),區(qū)間必將最終收縮為一點(diǎn)x*,顯然x*就是所求的根。17二分法

小結(jié)：二分法也可以看作一種迭代法，它的迭代過(guò)程確定了一個(gè)區(qū)間的序列{I(k)}，使每個(gè)區(qū)間都包含方程的某個(gè)解x*。且區(qū)間長(zhǎng)度趨于零。顯然，當(dāng)區(qū)間的長(zhǎng)度足夠小時(shí)，此區(qū)間中任何一點(diǎn)與x*的差必小于某一個(gè)值。所以可以用此區(qū)間中任何一點(diǎn)作為x*的近似，且誤差可以容易估計(jì)。18二分法當(dāng)區(qū)間[ak,bk]的中點(diǎn)作為x*的近似值時(shí)，即：二分法的特點(diǎn)：計(jì)算簡(jiǎn)單，且總是收斂的。但是收斂速度慢。二分法適合于尋求一個(gè)較好的近似解，作為其它方法求解的初值。19二分法

例：用二分法求方程

f(x)=x3-x-1=0在區(qū)間(1,1.5)的實(shí)根,要求誤差不超過(guò)0.005。解：即要求滿足取k=620二分法(1)f(a)<0,f(b)>0(2)根據(jù)精度要求,取到小數(shù)點(diǎn)后四位即可.-+-++--1.251.3751.31251.34381.32811.32031.32421.51.51.3751.3751.34381.32811.32811.01.251.251.31251.31251.31251.32030123456

bk

akk二分法計(jì)算過(guò)程見下表：x*≈1.3242

21二分法例：用二分法求在[1,2]內(nèi)的一個(gè)實(shí)根，且要求滿足精度22二分法kakbkxkf(xk)01.02.01.52.37511.01.51.25-1.7986721.251.51.3750.1621131.251.3751.3125-0.8483941.31251.3751.34375-0.3509851.343751.3751.359375-0.0964161.3593751.3751.363281250.0323623二分法kakbkxkf(xk)71.3593751.36718751.364257813-0.0321581.363281251.36718751.3647460940.00007291.363281251.3652343751.364257813-0.01605101.3642578131.3652343751.364746094-0.00799x*≈x10=1.36474609424第七章非線性方程求根第二節(jié)迭代法及其收斂性25迭代法的基本思想迭代法是一種重要的逐次逼近法,其基本思想是：將方程

f(x)=0

化為等價(jià)方程然后在有根區(qū)間內(nèi)取一點(diǎn)

x0

，按下式計(jì)算計(jì)算結(jié)果生成數(shù)列如果這個(gè)數(shù)列有極限當(dāng)(x)連續(xù)時(shí),顯然

就是方程

x=(x)的根。26這種求根方法稱為迭代法。如果迭代序列收斂,則稱迭代格式收斂,否則稱為發(fā)散。于是可以從數(shù)列

中求得滿足精度要求的近似根。稱為迭代格式,

(x)稱為迭代函數(shù),x0

稱為迭代初值,數(shù)列

稱為迭代序列。迭代法的基本思想27所以通常稱為的不動(dòng)點(diǎn)，求f(x)的零點(diǎn)等價(jià)于求的零點(diǎn)。因此，又稱為不動(dòng)點(diǎn)迭代法。迭代法的基本思想28對(duì)方程進(jìn)行如下三種變形：用迭代法求方程

x4+2x2-x-3=0在區(qū)間[1,1.2]內(nèi)的

實(shí)根。解例1迭代法的基本思想29分別按以上三種形式建立迭代格式，并取x0=1進(jìn)行迭代計(jì)算，結(jié)果如下：迭代法的基本思想30第二種格式比第一種格式收斂快得多,而第三種格式不收斂?？梢姷袷讲煌?收斂情況也不同。準(zhǔn)確根

=1.124123029。迭代法的基本思想31例2用迭代法求方程在內(nèi)的一個(gè)近似根，取初始近似值解原方程的等價(jià)方程可以有以下不同形式迭代法的基本思想32對(duì)應(yīng)的迭代公式有：取列表計(jì)算如下迭代法的基本思想331.365230021.3659167381.365229941.3638870071.3652230581.3678469761.365225591.3600941951.365264751.3751702541.364957011.34545838-469.731.367376371.402540802.99696.73221.348399731.286953770.8165-0.87511.51.51.51.50(4)(3)(2)(1)n迭代法的基本思想34n

(1)

(2)

(3)

(4)91.364878221.36523001101.36541006151.36522368201.36523024231.36522998251.36523001接上表迭代法的基本思想35例2.3

求方程在附近的根.解若將方程改寫為,構(gòu)造迭代法

由可知，顯然不收斂.

構(gòu)造迭代法

若將方程改為36計(jì)算結(jié)果如下：從結(jié)果看它是收斂的，且在6位有效數(shù)字時(shí)即為根x*的近似值.37迭代法的幾何意義一般來(lái)說(shuō)從構(gòu)造不止一種，有的收斂，有的不收斂，這取決于

的性態(tài)。方程

的根，在幾何上就是直線與曲線

交點(diǎn)的橫坐標(biāo)38迭代法的幾何意義39迭代法的幾何意義40迭代法的幾何意義41迭代法的幾何意義42迭代法的收斂條件定理

1

(1)當(dāng)x∈[a,b]時(shí)，(2)存在正數(shù)L<1，使對(duì)任意的

x∈[a,b],(2)對(duì)任意迭代初值

x0∈[a,b],迭代序列(1)方程在[a,b]上有唯一根

;在[a,b]上存在,且滿足條件：設(shè)收斂于

。

則43定義：對(duì)任意的

x0∈R,產(chǎn)生的序列都屬于這個(gè)鄰域，且收斂到x*，則稱該迭代法局部收斂。

設(shè)有不動(dòng)點(diǎn)x*,如果存在x*的某個(gè)鄰域方程迭代法的收斂條件定理：設(shè)x*為的不動(dòng)點(diǎn)，在x*的某個(gè)鄰域連續(xù)，且，則迭代格式局部收斂。44則迭代必發(fā)散。反之，若在根

的鄰域

U

內(nèi)迭代法的收斂條件且有下列誤差估計(jì)式:45例1中采用的三種迭代格式,在有根區(qū)間(1,1.2)內(nèi)有例如迭代收斂。迭代法的收斂條件46迭代收斂。迭代發(fā)散。迭代法的收斂條件47例3考察例2中四種迭代法在根附近的收斂情況，取根的近似值為解不收斂迭代法的收斂條件48不收斂迭代法的收斂條件收斂49收斂上例說(shuō)明

值越小,收斂速度就越快.迭代法的收斂條件50例4.構(gòu)造不同迭代法求的根.解

(1)

不滿足定理1條件.

.收斂.

收斂.

(2)(3)51若取,分別用上述三種迭代計(jì)算，結(jié)果見下表從表2-3看到迭代法(1)不收斂，迭代法(2)和迭代法(3)收斂，在迭代法(3)中，收斂最快.k迭代法（1）迭代法（2）迭代法（3）01232

1.5

2

1.52

1.75

1.73475

1.732361

2

1.75

1.732143

1.73205152迭代法的收斂速度則稱迭代格式是

p

階收斂的.

p=1時(shí)稱為線性收斂,

p>1時(shí)稱為超線性收斂.顯然,收斂階越大,收斂越快.p=2

時(shí)稱為二階(平方)收斂,

特別地,令若53則迭代過(guò)程在

的鄰近為

p階收斂。(1)若為線性收斂；則迭代過(guò)程在的鄰近(2)若定理

3的根,在

的鄰域

U內(nèi)有連續(xù)的

p階導(dǎo)數(shù)，則

設(shè)

為迭代法的收斂速度54將處進(jìn)行泰勒展開：迭代法的收斂速度55迭代法的加速無(wú)論是解線性方程組的Jacobi迭代法和G—S迭代法還是解非線性方程N(yùn)ewton系列迭代法都涉及到收斂速度問(wèn)題如何加快迭代法的速度呢？也涉及到初值的選取問(wèn)題如何改善迭代法的適用范圍呢？56由G-S迭代法的矩陣形式加速加速法主要思想57------(5)兩邊同時(shí)乘D58----(6)上式為逐次超松弛法(SOR迭代法)的矩陣形式令----(7)59SOR法化為G-S迭代法G-S法為SOR法的特例,SOR法為G-S法的加速例1.用G-S法和SOR法求下列方程組的解,要求精度1e-660解:(1)G-S迭代法61[x,k]=gauss_seidel(a,b,[1,1,1]',1e-6)

11

10.75000000.37500001.50000000.56250000.53125001.54166670.65104170.59635421.61458330.70182290.65820311.6727431……….0.99999330.99999231.99999260.99999430.99999351.99999370.99999520.99999441.9999946k=71x=0.9999950.9999941.999995滿足精度的解迭代次數(shù)為71次62(1)SOR迭代法

1110.63750000.01218751.31990630.20042700.37175721.31228050.65503350.53401191.69228480.70584680.77334011.7771932………..0.99999900.99999761.99999910.99999840.99999931.99999890.99999980.99999941.99999980.99999960.99999981.9999997k=24x=1.0000001.0000002.000000滿足精度的解迭代次數(shù)為24次SOR法的收斂速度比G-S法要快得多63SOR法都收斂嗎？1.SOR迭代法收斂的充要條件是對(duì)于SOR迭代法(7),有如下結(jié)論----(8)(此結(jié)論的證明較復(fù)雜),因此有另外,松弛因子的選取是很困難的,一般采用試算進(jìn)行64二、非線性方程迭代法的加速對(duì)于迭代法上式的迭代函數(shù)令迭代改變量即求導(dǎo)并令----(9)65得因此有松弛迭代法:--------(10)從后面的例子可以看出,加速效果是明顯的甚至一些不收斂的迭代法經(jīng)過(guò)松弛加速后也能收斂66不方便中值定理差商近似代替導(dǎo)數(shù)即67于是可以得到迭代格式:其中-------(11)上組公式稱為Altken公式或Altken加速68將(11)式綜合后可得一個(gè)解析式表示的迭代法:----(12)上式稱為Steffensen迭代法Altken公式與Steffensen公式是等價(jià)的加速效果也是很明顯的例2中將比較不同加速方法69例2.對(duì)迭代格式進(jìn)行加速解方程組解:x0=0.5x1=0.375x2=0.3509115x3=0.3477369x4=0.3473496x5=0.3473028x6=0.3472971x7=0.3472964(1)直接使用迭代格式迭代7次,得到滿足精度的解70(2)對(duì)迭代格式進(jìn)行松弛加速x0=0.5x1=0.3333333x2=0.3472222x3=0.3472964x4=0.3472964迭代4次,得到滿足精度的解71(3)對(duì)迭代格式進(jìn)行Altken加速(11)式x0=0.5x1=0.3451613x2=0.3472961x3=0.3472964迭代3次,得到滿足精度的解從以上3種結(jié)果可見,迭代法加速技術(shù)效果比較明顯迭代格式顯然不收斂72x0=1.5x1=1.5350706x2=1.5321124x3=1.5320889x4=1.5320889迭代4次,得到滿足精度的解對(duì)迭代格式進(jìn)行松弛加速x=1.5x=1.5333333x=1.5320906x=1.5320889x=1.5320889迭代4次,得到滿足精度的解對(duì)迭代格式進(jìn)行Altken加速可見加速技術(shù)可能將不收斂的迭代法加速為收斂73第七章非線性方程求根第三節(jié)牛頓迭代法74牛頓法的基本思想設(shè)已知方程

f(x)=0的近似根為x0，且在

x0附近f(x)

可用一階泰勒多項(xiàng)式近似，表示為：當(dāng)

f’(x0)≠0時(shí)，方程

f(x)=0可用線性方程近似代替，即：75牛頓法的基本思想解線性方程：得：取此

x作為原方程的新近似根

x1，重復(fù)以上步驟，得迭代公式：此式稱為牛頓(Newton)迭代公式。76牛頓法的基本思想例

1：用牛頓法求方程在

內(nèi)一個(gè)實(shí)根，取初始近似值解：所以迭代公式為：列表計(jì)算如下：1.365230011.365262011.37333331.5

3

2

10

n77牛頓法的幾何意義方程f(x)=0

的根就是曲線

y=f(x)

與x

軸交點(diǎn)的橫坐標(biāo)x*，當(dāng)初始值x0

選取后，過(guò)(x0,f(x0))

作切線，其切線方程為：它與x軸交點(diǎn)的橫坐標(biāo)為：78牛頓法的幾何意義設(shè)xk

是x*

的第k

次近似值，過(guò)(xk

,f(xk

))作y=f(x)的切線，其切線與x軸交點(diǎn)的橫坐標(biāo)為：若過(guò)曲線y=f(x)上的點(diǎn)P(xk,f(xk

))引切線，該切線與

x軸交點(diǎn)的橫坐標(biāo)即為由牛頓迭代公式求得的

xk+1,因此牛頓迭代法也稱牛頓切線法。79牛頓法的幾何意義80例5.用Newton迭代法求方程的根:解:由Newton迭代法x0=0.5;x1=0.3333333333x2=0.3472222222x3=0.3472963532x4=0.3472963553迭代四次精度達(dá)10-8

81牛頓法的幾何意義

用牛頓迭代法求方程

x=e–x在

x=0.5附近的根。例2:將原方程化為

x–e

–x=0，則

f(x)=x–e

–x，

f’(x)=1+e

–x,

解：牛頓迭代格式為取

x0=0.5，迭代得:x1=0.566311,x2=0.5671431,x3=0.567143382牛頓迭代法的收斂速度牛頓迭代法的迭代函數(shù)為：由于f(x*)

=0，所以當(dāng)

時(shí),不一定為

0所以f(x)在x*附近是平方收斂的。83重根情況當(dāng)x*為m重根時(shí)，

f(x)可表為:84重根情況令則85計(jì)算重根的牛頓迭代法對(duì)于有重根的情況采用如下迭代格式：用牛頓法求方程的重根時(shí)僅為線性收斂。86計(jì)算重根的牛頓迭代法例：方程的有二重根，用牛頓迭代法和重根的牛頓迭代法分別求方程的近似根。迭代初值為1.5。87計(jì)算重根的牛頓迭代法例：用牛頓迭代法求

f(x)=(x-1)[sin(x-1)+3x]-x3+1=0在0.95附近的根。取

x0=0.95用牛頓迭代法求得的

xk

見下表。k

xk01230.950.97442790.98705830.9934878k

xk4560.99673280.99835760.999190188計(jì)算重根的牛頓迭代法由重根數(shù)

m為

2,用加速法

x0=0.95x1=0.9988559x2=x3=1收斂速度大大加快于直接用牛頓迭代公式。得：89Newton迭代法需要求每個(gè)迭代點(diǎn)處的導(dǎo)數(shù)復(fù)雜！--------(12)--------(13)這種格式稱為簡(jiǎn)化Newton迭代法精度稍低三、Newton迭代法的變形90則Newton迭代法變?yōu)?-------(14)這種格式稱為弦截法收斂階約為1.618幾何意義91例6.用簡(jiǎn)化Newton法和弦截法解例(5)中方程的根，解:由簡(jiǎn)化Newton法并和Newton迭代法比較由弦截法92x0=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á)到精度10-8

簡(jiǎn)化Newton法迭代11次弦截法迭代5次Newton迭代法迭代4次93無(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ā)散94--------(15)這種方法稱為Newton下山法，95例7.解:1.先用Newton迭代法x4=9.70724x5=6.54091x6=4.46497x7=3.13384x8=2.32607x9=1.90230x10=1.75248x11=1.73240x12=1.73205x13=1.73205迭代13次才達(dá)到精度要求962.用Newton下山法,結(jié)果如下k=0x0=-0.99fx0=0.666567k=1x1=32.505829f(x)=11416.4w=0.5x1=15.757915f(x)=1288.5w=0.25x1=7.383958f(x)=126.8w=0.125x1=3.196979f(x)=7.69w=0.0625x1=1.103489f(x)=-0.655k=2x2=4.115071