計(jì)算方法課件 課件 劉火星 第6-9章 非線性方程解法-常微分方程的初值問題

計(jì)算方法Numerical

Analysis非線性方程解法SolutionsofNonlinear

Equations2476.1

根的隔離對分法迭代法牛頓法牛頓法的改進(jìn)目錄問題的提出本章研究的對象是

非線性方程f(x)

0(6.1)xyy=f

(x)s若常數(shù)

s

使得

f

(x)=0

，則稱

s是方程(6.1)式的根若f

(x)是n次多項(xiàng)式，則稱(6.1)式為n次多項(xiàng)式方程或代數(shù)方程若f

(x)是超越函數(shù)，則稱(6.1)式為超越方程問題的提出方程

f(x)

=0

的解通常稱為方程的根或函數(shù)f(x)

的零點(diǎn)，如果函數(shù)f

(x)

可分解為f(x)=(x-s)m

φ(x)且φ(x) ≠0，

則稱s是f

(x)的m重零點(diǎn)或(6.1)式的m重根。當(dāng)m=1時(shí)，稱s是(6.1)式的單根或f(x)的單零點(diǎn)。問題的提出xyy=f

(x)xyy=f

(x)問題的提出方程

f

(x)=

0求根問題包括以下三個(gè)問題：根的存在性——方程有沒有根？有幾個(gè)根？根在哪兒？根的精確化6.1

根的隔離xy=f(x)a根的存在定理：設(shè)f

(x)在區(qū)間[a，b]上連續(xù)，f

(a)

f

(b)<0，則至少存在一個(gè)實(shí)數(shù)s，使得f

(s)=0。f(a)bf(b)s2536.1

根的隔離確定出若干個(gè)區(qū)間，在每個(gè)區(qū)間內(nèi)有且僅有一個(gè)根——根的隔離隔離根的方法作圖法：畫出

y=f

(x)的大致圖形，根據(jù)曲線大致判斷與x軸的相交位置逐步掃描法：從邊界開始，選取一定步長，逐步掃描2546.1

根的隔離[例]

求根3x-1-cosx=0x∈

[0.6,0.7]2556.1

根的隔離[例]

求根x3

+x2 -3x-

3=0x∈

[-2.0,-1.5][-1.5,-0.5][1.5,2.0]256理論上已證明：對于次數(shù)

n

≤4的多項(xiàng)式方程，它的根可以用公式表示，而次數(shù)大于5的多項(xiàng)式方程，它的根一般不能用解析表達(dá)式表示因此對于f

(x)=0的函數(shù)方程，一般來說不存在根的解析表達(dá)式，而實(shí)際應(yīng)用中，也不一定必需得到根的解析表達(dá)式，只要得到滿足精度要求的根的近似值就可以了常用的求根方法分為區(qū)間法和迭代法兩大類，最簡單的是對分法。6.1

根的隔離2576.2

對分法思想：用二等分區(qū)間的方法，逐步縮小有根區(qū)間，得到滿足精度要求的實(shí)根

x*

的近似值

xk①

取[a，b]區(qū)間的中點(diǎn)x0=（a+b）/2②

若

f

(x0)=

0，則x0是

f

(x)=0的實(shí)根③

若

f

(x0)≠

0，則由

f

(x0)的符號(hào)確定新的有根區(qū)間f

(a)

f

(x0)<0

成立，則根必在區(qū)間(a，x0)內(nèi)，取a1=a，b1=

x0f

(a)

f

(x0)>0,根必在區(qū)間(x0

，b)內(nèi)，取a1=

x0

，b1=

b④

這樣，得到新區(qū)間[a1，b1]，其長度為[a，b]的一半，如此繼續(xù)下去，進(jìn)行k次等分后，得到一組不斷縮小的區(qū)間

[a，b]

，

[a1，b1]

，......[ak，bk]xy=f(x)f(a)確定有解區(qū)間將區(qū)間分成兩半x0=(a+b)/2求f

(x0)判斷有解區(qū)間a x0f(x1)f(b)f(x0)x1

bS≈

(xn+xn-1)/26.2

對分法nanbnxnf(xn)0121.5＋111.51.25－21.251.51.375＋31.251.3751.3125－41.31251.3751.34375＋[例]求根

x3

－

x

－1=

0f(x)

x3

x

1f

(1)

1

0,

f

(2)

5

06.2

對分法260收斂性①[a,b]→[a1,b1]→[a2,b2]→…

→[ak,bk]② bk–ak=(bk-1–ak-1)/2=(b-

a)/2k③

記[ak,bk]的中點(diǎn)為 xk=(ak+

bk)/2④

產(chǎn)生根的序列：x0，x1，x2，…，xn

02kk kk

k

b

a

lim

b

a

limklim

x

x*k

對分法是收斂的

k,

x*

[a

,

b

]k k誤差將有限次對分的結(jié)果xk作為根的近似值，其誤差為多少？22k

1k

bk

ak

b

ax*

x什么時(shí)候停止？給定精度εx*

x

k[例]求方程f

(x)=x3

－

x

－1在區(qū)間(1,1.5)內(nèi)的根,要求精確到小數(shù)點(diǎn)后的第二位。[解]① a=1,b=1.5且

f(a)<0,f(b)>0精度要求為

ε=10-2/2=0.005由誤差估計(jì)式|x*-xk|≤(b-a)/2k+1得0.5/2k+1<0.005 從而 2k+1>100 取k=6 即可②kakbkxk(bk-ak)/20121.50.5111.51.250.2521.251.51.3750.12531.251.3751.31250.062541.31251.3751.343750.0312551.31251.343751.3281250.01562561.31251.3281251.3203130.00781371.320131.3281251.3241280.003997什么時(shí)候結(jié)束運(yùn)算？

xn

xn

1（1）f

xn

（2）

xnxn

xn

1（3）用對分法解(6.1)，使誤差不超過ε的終止準(zhǔn)則（1）

先驗(yàn)估計(jì)2k

1k

b

a

x*

xk

ln(b

a)

ln

1ln

2（2）

后驗(yàn)估計(jì)bk

1

ak

1

AlgorithmStep1.

輸入a,

b,

ε,δStep2.

x=(a+b)/2Step3.

if

(|f(x)|<δ

或b-x<ε)

輸出x

stopelse

if

(f(a)f(x)<0) b=xelse a=xStep4.goto

Step26.2

對分法簡單，收斂性有保證對f

(x)

要求不高(只要連續(xù)即可).無法求復(fù)根及偶重根收斂慢把對分法與逐步掃描法結(jié)合起來,就可以求非線性方程在任一區(qū)間上的全部實(shí)根。首先,

將方程式f(x)=0化為函數(shù)式y(tǒng)=f(x).假設(shè)方程求解區(qū)間為

[a,b]

,掃描區(qū)間為h。由a點(diǎn)出發(fā)向

b點(diǎn)掃描，每跨一步，判斷在該區(qū)間內(nèi)是否有根。如有根則進(jìn)行對分法求根計(jì)算，否則繼續(xù)向前找根，直到走出區(qū)間[a,b]為止x*x7

=1.6758[例]求方程f

(x)=2x3

－5x－1在區(qū)間(1,2)內(nèi)的根,要求誤差限為

ε≤10-2[解] f

(x)=2x3－5x－1有

f(1)<0,

f(2)>0 記I0=[1,2] ,x0

=(1+2)/2=1.5因?yàn)?f(x0)

f(1)>0 得I1=[1.5,2],x1=(1.5+2)/2=1.75f(x1)

f(1.5)<0

得I2=[1.5,1.75],x2

=(1.5+1.75)/2=1.625…….I6=[1.681875,1.6875],I7=[1.671875,

1.679688]b7

-

a7=0.7813 10-2<

10-26.3

迭代法思想：首先給出方程f(x)=0的一個(gè)初始近似值x0

，然后反復(fù)使用某一公式校正這個(gè)初始值，使之逐步精確化，直到滿足精度要求為止x1

x0x2

x1...xn

xn

1構(gòu)造迭代公式：xn+1

=

g(xn)產(chǎn)生解的序列：x0，x1，x2，…，xn等價(jià)變換 f(x)=0 x=g(x)等價(jià)方程n

如果limxn

s，可求得方程的根。[例]

求方程x3

3x2

3

0的根x

x

x3

3x2

3x3(1

x2

)x

x3

1/

2x

1

3x

3

x3n0.50.50.50.51-1.6252.121320.9789450.925822-0.99414

0.8290240.8741693-2.011720.9000420.8799774-1.012130.8700380.8793185-1.975740.8834420.8793936-0.977490.8775910.8793847-2.045010.8801720.8793858-1.051180.8790390.8793859-1.897780.87953710-0.928060.87931811-2.143510.87941512-1.208260.87937213-1.592520.87939114-1.022980.87938315-1.954040.87938616-0.960280.879385[例]

求方程x3

x

1

0在1.5附近的根x

x3

1x

3 x

1n1.51.512.3751.357209212.396481.33086131904.0031.32588446.9E+091.32493953.29E+291.3247663.56E+881.32472674.5E+2651.3247198

1.3247189

1.32471810

1.3247182716.3

迭代法迭代法要解決的問題：如何構(gòu)造迭代函數(shù)？如何判斷迭代格式是否收斂？如何估計(jì)誤差？迭代法的幾何意義y

xf(x)=0x=g(x)xn+1=g(xn)y=g(xn)xn+1=yx0o s x2

x1迭代法的幾何意義y

x收斂O x1 x3 s x2 x0y

g(x)y

x迭代法的幾何意義O x2 x1 x0 sy

g(x)y

xO x3 x1 s x0

x2y

g(x)y

x發(fā)散迭代法的幾何意義O x3 x1 s x0

x2y

g(x)y

x發(fā)散g

(

x

)在s附近較陡峭y

g(x)y

xO x1 x3 s x2 x0收斂g

(

x

)在s附近較平緩迭代法的收斂性定理

定理：假定函數(shù) 滿足下列條件：

則（1）方程

x=g(x)在區(qū)間[a,b]迭上有唯一根

s（2）對于任意初值

x∈[a,b]

，迭代過程

xk+1=g(xk)均收斂于s（3）且有如下的誤差估計(jì)式：

g(x)（1）對任意

x

a,

b

有a

g(x)

bLkx

k

s

1

L x1

x

0x

(a,b)（2）存在正數(shù)

L<1，使對任意

x

有

|

g

(x)|

L

1277代是收斂？0

內(nèi)，迭如果x

在區(qū)間I

[0,

]2g'(x)

0.8sin(x)

0.8

1g(x)

0.8

cos

x0

g(x)

0.8

cos

x

0.8例題問題：

xn

1

0.8

cos

xn代收。0

內(nèi)，迭所以x

在區(qū)間I

[0,

]2Nxn0否 0.500010.702120.610830.655340.6343……

…11斂 0.6411（1）

先驗(yàn)估計(jì)（2）

后驗(yàn)估計(jì)x

s

kln

Lx1

x0k

ln

(1

L)

xk

1

xk用迭代法解(6.1)，使誤差不超過ε的終止準(zhǔn)則kkx

xx

s

k

1L1

L279迭代法的收斂性定理定義：對于方程

x=g(x)

，s為方程的根，如果存在

s

的某個(gè)臨域Δ:|x-

s|≤δ,使迭代格式

xk+1=g(xk)對于任意初值x∈

Δ均收斂,則稱該迭代格式在s 附近具有局部收斂性.定理：設(shè)s為方程

x=g(x)的根，

g’(x)在

s

附近連續(xù),且|

g’(s)|<1則迭代格式xk+1=g(xk)在s附近具有局部收斂性.280[例]：求方程

x=e-x

在0.5附近的一個(gè)根，要求ε=10-500.510.60653120.54523930.57970340.56006550.57117260.56486370.56843880.56640990.56756100.566907110.567277120.567067130.567186140.567119150.567157160.567135170.567148180.567141190.567145200.567142210.567144220.567143230.567143240.567143250.567143260.567143281迭代法的收斂速度定義：對于方程

f(x)=0,迭代格式

xk+1=g(xk)

收斂于方程的根s,如果對于迭代誤差

ek=xk-s,如果存在正實(shí)數(shù)

p

和C，使得pk

Ck

elimek

1則稱迭代格式是p階收斂的。當(dāng)p=

1時(shí)稱為線性收斂（

0<

C<1），

1<

p

<2時(shí)稱為超線性收斂

，p

=2時(shí)稱為平方收斂定理：若迭代格式

xk+1=g(xk)

收斂于方程x=g(x)的根

s,且1.

g(x)在s附近具有連續(xù)的二階導(dǎo)數(shù)2.|

g’(s)|<1當(dāng)g’(s)≠0時(shí)，迭代格式為線性收斂當(dāng)g’(s)=0，g”(s)≠0時(shí)，迭代格式為平方收斂282迭代法的收斂速度設(shè)迭代格式

xk+1=g(xk)

是1階收斂的

C 0

C

1eklimek

1k

設(shè)迭代格式

xk+1=φ(xk)2階收斂02eklimek

1k

C C

0且Ce

10k

1ek

1

C

ek

C e

00422e2

12

1k

1

0k

12k

1k

1

C

eek

1

C

ek

C

C e

C e0 0

1,

C

C

0.75,為使

10

8若

e

e1階收斂

0.75

k

1

10

8

k

632階收斂

0.75

2k

1

1

10

8

k

62階收斂更快！283迭代法的收斂速度[例]

用迭代法求方程x3

x

1

0的正實(shí)根，并考察收斂速度[解]

有兩種方案x

3 x

12x3

1x

n1.51.511.3572091.34782621.3308611.32520031.3258841.32471841.3249391.32471851.32476061.32472671.32471981.32471891.3247183x2

11g

(x)

(3x2

1)23(x

1)2

/

36x(x3

x

1)g(x)

284迭代法的加速方法(1)若g’(x)

在求根范圍內(nèi)改變不大，取g’(x)≈a當(dāng)|

g’(x)≈|a|≤L<1a.

xk為

s

的近似值，迭代一次得

yk=g(xk)s

yk

g(s)

g(xk

)

g

(

)(s

xk

)

a(s

xk

)(1

a)s

yk

axk(1

a)s

yk

ayk

ayk

axk(1

a)(s

yk

)

a(

yk

xk

)ka(yk

xk)1

as

y

285迭代法的加速方法b.將以上誤差補(bǔ)償給yk

，得更精確的近似根從而得迭代加速公式k ka1

axk

1

yk

(

y

x )

a

改進(jìn) xk

1

yk

1

a

(

yk

xk

)

迭代 yk

g(xk

)[例]：用加速收斂的方法求方程

x=e-x

在0.5附近的一個(gè)根，要求ε=10-5解：g(x)=e-x且g’

(x)=

-

e-x

在x=0.5

附近有g(shù)’

(x)

≈-0.6從而得迭加速公式

1.60.6kk

1k

1k

1(

y

x )

y

xk

1y

e

xk

改

迭0.567462

代0.567132kxkyk+1

xk00.50.510.6065310.606531

0.56658220.54523930.5797030.56715

0.56714340.5600650.567143

0.56714350.57117260.56486370.568438代80.56640990.56756100.566907110.567277進(jìn)120.567067130.567186140.567119150.567157160.567135170.567148180.567141190.567145200.567142210.567144220.567143230.567143287迭代法的加速方法c.

上述方法要用導(dǎo)數(shù)g’(x)的近似值，可以進(jìn)一步改進(jìn)k kzk

2

yk

xk(

y

x )2

迭代 zk

g(yk

)

改進(jìn) x

x

k k

k

1 k

迭代 y

g(x )yk

g(xk

)zk

g(yk

)s

yks

zk

g(s)

g(xk)

g

(

)(s

xk)

g(s)

g(

yk

)

g

(

)(s

yk

)假定x*附近g

(x)變化不大s

zk s

yk從而得

新的迭代加速公式s

yk

s

xkkks

x

zk

2yk

x(zk

yk

)2Steffensen加速算法288xyy=

xy=

g(x)x0

P(x0,

x1)x1

s x2x?P(x1,

x2)x0

2x1

x2x?

x0

1 0 x0

, x1

g(x0

), x2

g(x1),(

x

x )

2加速法的幾何解釋迭代法的加速方法只要g(x)滿足定理中的條件，無論迭代格式

xk+1=g(xk)是否收斂，Steffensen法都能以不低于二階的速度收斂到

s如果簡單迭代法已經(jīng)具有p（p≥2）階收斂速度，則構(gòu)造Steffensen迭代法對提高收斂速度作用不大Steffensen迭代法可以把簡單迭代法不收斂的情況改為2階收斂定理：設(shè)

s

=g(s)

，

g”(s)在包含

s

的某個(gè)區(qū)間內(nèi)連續(xù),且g’(

s

)≠1，則存在δ，當(dāng)x0∈[s-δ,

s+δ]但x0

≠

s時(shí)，由Steffensen

迭代法產(chǎn)生的序列至少以2階收斂速度收斂于s。[例]

用Steffensen迭代法解方程x3-x-1=0.結(jié)果見右表，發(fā)散的代公式加速后取x0=1.5 進(jìn)行有較好的收斂yk

xk2(

y

x )2k kz

y3

1k kxk

1

xk

[解]對

xk+1=xk

-1

利用Steffensen迭代公式3y

x3

1k k

kxkxkykzkzk迭代性。1.51.52.37512.3964812.3751.416293迭1.840922被

5.238873212.396481.355651.4913982.31727131904.0031.3289491.3470631.44435146.9E+091.3248041.3251741.32711753.29E+291.3247181.3247181.32471963.56E+881.3247181.3247181.324718x

P(x0,

x1)x1

s x0x2x?yP(x1,

x2)y=

g(x)y=

xSteffensen迭代法的幾何解釋6.4

牛頓法Newton-RaphsonMethodf(x)=0 → x=g(x)迭代函數(shù)構(gòu)造得好壞影響收斂速度，甚至收斂用近似方程代替原方程6.4

牛頓法Newton-RaphsonMethod思想：將非線性方程線性化（用Taylor展開）(1)

取x0

s,

將f

(x)在x0點(diǎn)作Taylor

展開2!00 0 0f

(x)

f

(x

)

f

'(x

)

(x

x

)

f

(x0

)

(x

x

)2

(2)

取線性部分作為f

(x)的近似0

f

(x)

f(x)

f'(x)(x

x)0 0 0(3)

若f

(x0

)

0100記為xf

(x

)x

x

f(x0

)6.4

牛頓法4311, x

,

x

f(x

)f

(x

)x2

x1

(4)

類似的有(5)

一直重復(fù)可得迭代序列(k

0,1,2,

)f'(x

)f(x

)kkxk

1

xk

這種迭代方法稱為牛頓迭代法。f

'(x)牛頓法事實(shí)上是一種迭代法f

(x)2

f

(x)f

(x)f

(x)2g(x)

1

g(x)

x

f

(x)

f

(s)2g

(s)

f

(s)f

(s)

0

1收斂22!kk k k0

f

(s)

f(x)

f'(x)(s

x

)

k (s

x

)f

(

)2kkkkf

'(x

) 2!f'(x)k k(s

x

)

s

x

f(x)

f (

)

k 2!f'(x)kf

(

)

s

x

k

1

(s

x

)2k2!f

'(s)e2kf

(s)

lim

ek

1k

又f

’’(s)

≠

0,平方收斂296定理：設(shè)s為方程的根，在包含

s

的某個(gè)區(qū)間內(nèi)g”(x)連續(xù),且g’(x)≠1，則存在δ，當(dāng)x0∈[s-δ,

s+δ]但x0

≠

s時(shí)，由牛頓法產(chǎn)生的序列{xk}收斂。若g”(s)

≠

0

且x0

≠

s

,則序列{xk}平方收斂297牛頓法的幾何意義xs0f (

x )f (x

0)x1

x

0

x2 x1

x0211f (x1

)x

x

f

(

x )牛頓法也稱為切線法過(x,

f

(x )

) 的切線方程為0 0y

f

(x0

)

f

'(x0

)

(x

x0

)yf(x)[例]求方程

f(x)

=x3

＋

2x2＋10x－20=0

在[1,2]內(nèi)的根nn3x2

4x

10x3

2x2

10x

20xn

1

xn

n n n f(1)

7,f(2)

16,f(1)f(2)

0f

(x)

在區(qū)間[1,2]上連續(xù)f

(x)

0 在區(qū)間[1,2]上有解[解]0111.41176521.37345531.36922541.36884551.36881161.36880871.368808結(jié)論：牛頓法的收斂性依賴于x0

的選取。sx0 x0

x0f(x)正常情況，

x0足夠接近s，收斂。構(gòu)成一個(gè)平行四邊形，不可能逼近s。切線太平，超出了x迭代范圍。牛頓法的收斂定理（收斂的充分條件）設(shè)

f

(x)在[a,

b]上滿足條件：(x)在

[a,

b]上連續(xù)，不變號(hào)；[a,

b]

使得

f (x0)f(x0)

>1. f(a)f(b)<

0；f (x)、

f選取初始值x00；則由牛頓法產(chǎn)生的序列{

xk

}

單調(diào)地收斂到f(x)在

[a,b]的唯一根s。f

'(x)

1

sin

xf

"(x)

cos

xf

(x)

x

cos

x[例]求

x

c

o

s

x

0

在區(qū)間[-1,1]上的根，并判斷收斂性。nnn1

sin

xx

cos

xxn

1

xn

[解]0.8210.7398530.73453620.7390850.7390930.7390850.7390854

0.739085c[例]

用牛頓法求的迭代格式，并求135.607的平

xk

xk

1

c

2xk 2

x2

cxk

1

xk

k

方根[解]f

(

x

)

x2

c12135111.6502916768.00224815211.6450430534.9982014311.6450418619.43644312411.6450418613.20669425

11.73737224611.64540502711.64504187811.64504186911.64504186[例]

用牛頓法解方程x3-x-1=0.[解]

迭代公式kk3x2

12x3

13x2

1x3

x

1xk

1

xk

k k

k kxkxkykzkxk1.51.52.37512.396481.512.3751.4162931.8409225.2388731.347826212.396481.355651.4913982.3172711.32520031904.0031.3289491.3470631.4443511.32471846.9E+091.3248041.3251741.3271171.32471853.29E+291.3247181.3247181.32471963.56E+881.3247181.3247181.324718kxkxk1.50.611.34782617.921.32520011.946831.3247187.9855241.3247185.35690953.62499662.50558971.82012981.46104491.339323101.324913111.324718121.324718牛頓法算法AlgorithmStep1. 選定初始近似值x0，計(jì)算f(x0)、f

′(x0)Step2. 迭代

x1=x0

-f(x0)/f

′(x0)，計(jì)算f(x1)、f

′(x1)Step3. if

(|f(x1)|<δ

或|x1-

x0|

<ε) 輸出x1,stopStep4.

以x1、f(x1)、f

′(x1)替代

x0

、

f(x0)、f

′(x0)

，goto Step2牛頓法的特點(diǎn)優(yōu)點(diǎn)：

收斂快!

缺點(diǎn)：

每一步計(jì)算f(xk)和f’(xk)，工作量大初始值x0要接近根

s

才能保證收斂6.5

牛頓法的改進(jìn)（1）簡化牛頓法xyx1

x0sx

2112f'(x

)0f(x

)x

x

001f'(x

)f(x)

0 x

x6.5

牛頓法的改進(jìn)（1）簡化牛頓法——用常數(shù)代替導(dǎo)數(shù)(k

0,1,2,

)cf

(x

)kxk

1

xk

g(x)

x

f

(x)ccg

(x)

1

f

(x)

1c0

f

(x)

2[例]

用簡化牛頓法求

x-sinx-0.5=0根。1.51.511.4972166521.497304321.4973028571.497300389的31.4973003161.49730038941.49730039151.49730038961.4973003891011f

x

x

x

x1

x0f

x

y

f(x)

xyx1 x0x2011 01f

x

f

x

f

(x

)

x

x

x

x

2 1x3122 1223f

x

f

x

f

(x

)

x

x

x

x

f(x)6.5

牛頓法的改進(jìn)（2）割線法6.5

牛頓法的改進(jìn)（2）割線法——用差商代替導(dǎo)數(shù)k k

1

f

x

f

x

x

x

f(x

)kkk

1[例]

用割線法求

x-sinx-0.5=0

的根。

xk

xk

1

割線法是2步格式，收斂速度比Newton迭代法慢6.5

牛頓法的改進(jìn)單點(diǎn)割線法——在割線法中用固定點(diǎn)（x0,f(x0)）（xk-1,f(xk-1)）k 0f(x

)kk

xk

x0

f

x

f

x

x

x

k

16.5

牛頓法的改進(jìn)（3）牛頓下山法xo

的選取很重要,如

x0偏離s

較遠(yuǎn)，則可能發(fā)散.(k

0,1,2,

)f

(x

)f

(x

)kkk

1

kx

x

)

f

(x

)k

1

k

的選取使得

f

(x

=

1代入探注： =

1時(shí)就是Newton’s

Method

公式。效果不好時(shí)，將 減半計(jì)算,逐步試[例]

用牛頓下山法解方程x3-x-1=0.kxkxk0.60.611.14062517.921.36681411.946831.326287.9855241.324725.35690951.3247183.62499661.3247182.505589當(dāng)71.8201298。1.46104491.339323101.324913111.324718121.3247186.5

牛頓法的改進(jìn)（4）求m重根的牛頓法若s是(6.1)式的m重零點(diǎn)或的m重根，函數(shù)f

(x)

可分解為

f(x)

=(x-s)

m

φ(x)

,

且φ(s) ≠0，必有f(s)=f′(s)=f′′(s)=...=f

(m-1)(s)=0而f

(m)(s)≠0當(dāng)方程有重根時(shí),收斂會(huì)減慢[

例]

用牛頓法解方程x4-8.6x3-35.51x2+464.4x-998.46=0在[2,10]的根[解]7417.4856124.14540827.3604074.22138237.3485714.26033447.3484694.28007457.3484694.29001364.29500174.29749984.29874994.299374104.299687114.299844124.299922134.299961144.29998154.29999164.299995174.299998184.299999194.299999在4.0附近有重根，在7.0附近有單根重根時(shí)收斂會(huì)減慢，m越大越慢（4）求m重根的牛頓法如何加速重根的收斂？Ans1:

如果m已知(k

0,1,2,

)f

(x

)f

(x

)x

x

mkk

1

kkAns2:

如果m未知，考慮將求f

(x)的重根轉(zhuǎn)化為求另一函數(shù)的單根f

(x)u(x)

f

(x)u(x)在s為單根，應(yīng)用牛頓公式kkkku(x

)f (x

)u(xk

)u(x

)f

(x

)

1

x

ku

(xk

)xk

1

xk

[

例]

用牛頓法解方程x4-8.6x3-35.51x2+464.4x-998.46=0的重根[解]在4.0附近有2重根4414.145408163

4.290816327

24.221381617

4.299989843

34.260333503

4.300000000

44.280073698

4.299969384

54.290013091

4.300000000

64.295000543

4.299953217

74.297498762

4.300000000

84.298749003

4.300000000

94.299374407

104.299687180

114.299843584

124.299921790

134.299960895

144.299980447

154.299990224

164.299995112

174.299997556

184.299998780

194.299999392

234.299999991

244.299999991

(k

0,1,2,

)f

(x

)f

(x

)kx

x

2

k kk

1[例]

方程x4-4x2+4=0的根是二重根，試用Newton法及兩種改進(jìn)的Newton法各計(jì)算4步[解]kk4xx2

2

k x

xk

1kk2xx2

2

k x

xk

1kx2

2x(x2

2)x

x

k k kk

11231.51.51.511.4583333331.4166666671.41176470621.4366071431.4142156861.41421143831.4254976191.4142135621.41421356241.4198779221.4142135621.414213562301.414213562一般Fixed-PointIteration

為線性收斂，這時(shí)p

=1，0<C<1Steffensen

加速有p

=2，條件是g’(s)≠1

，稱為平方收斂Newton’s

Method

只要f

‘(

s)≠0

，就有p

≥

2。重根是線性收斂的。割線法有p

>1.618，稱為超線性收斂。單點(diǎn)割線法為線性收斂。比較各種迭代法的收斂階小結(jié)二分法簡單迭代法基本思路、收斂性：大范圍收斂與局部收斂、精度控制、算法實(shí)現(xiàn)收斂速度定義、如何判斷收斂階Steffensen迭代法構(gòu)造迭代、收斂性與收斂速度小結(jié)Newton迭代法構(gòu)造原理、迭代公式收斂性與收斂階簡化牛頓法割線法（構(gòu)造原理、迭代公式、單點(diǎn)割線法）求m重根的改進(jìn)Newton法插值與逼近Interpolationand

Approximation3217.1

插值基本概念Lagrange插值Newton插值等距節(jié)點(diǎn)插值Hermite插值樣條插值7.7

最小二乘法目錄7.1

插值基本概念Lagrange插值Newton插值等距節(jié)點(diǎn)插值Hermite插值樣條插值目錄問題的提出實(shí)際工作中，很難找到f

(x)的具體表達(dá)式，只能觀測到一些離散數(shù)據(jù)或者f

(x)過于復(fù)雜而不易運(yùn)算思路：用簡單函數(shù)為離散數(shù)組建立模型或?yàn)閺?fù)雜函數(shù)建立逼近xix0x1x2x3x4yiy0y1y2y3y4用簡單函數(shù)為離散數(shù)組建立模型或?yàn)閺?fù)雜函數(shù)建立逼近需要解決三個(gè)問題① 選定簡單函數(shù)的類型。通常是選取一組線性無關(guān)的簡單函數(shù)

,0

,1

...,

n

，利用它們形成線性空間

span{

0

,

1,

2,

,

n}利用形如P(

x)

a0

0

a1

1

an

n（7.1）的函數(shù)產(chǎn)生模型和進(jìn)行逼近。問題歸結(jié)為求a0,a1,...,an

，稱

0,

1,...,

n

為基函數(shù)。② 建立關(guān)于模型或逼近的目標(biāo)，目標(biāo)決定(7.1)式中

必須滿足的條件。條件分插值型和逼近型兩類③ 建立算法并作出理論分析給定未知函數(shù)f

(x)的一個(gè)數(shù)表yi=f

(xi)

(i=0,1,…,n)，求某個(gè)簡單的函數(shù)

(x)，來逼近函數(shù)f

(x)，并且使

(xi)=yi

，這種方法稱為插值法7.1

插值基本概x念ix0x1x2x3x4yiy0y1y2y3y4具體有很多種插值法，其中以拉格朗日(Lagrange)插值和牛頓(Newton)插值為代表的多項(xiàng)式插值最有特點(diǎn)，常用的插值還有Hermit插值，分段插值和樣條插值插值的任務(wù)就是由已知的觀測點(diǎn)，為物理量(未知量)建立一個(gè)簡單的、連續(xù)的解析模型，以便能根據(jù)該模型推測該物理量在非觀測點(diǎn)處的特性定義：設(shè)精確函數(shù)

y

=

f(x)

在區(qū)間[a,b]有定義，且已知在a≤x0<x1

<

x2

<...<xn≤b上的值為y0,

y1

,

y2

,

...,

yn，若存在一個(gè)簡單的函數(shù)

(x)，來逼近函數(shù)f

(x)，并且使

(xi)=yi

，(i=0,1,2,...,n)成立。則稱

(x)

為f(x)

的插值函數(shù)，稱x0,

x1

,

x2

,...,xn為插值節(jié)點(diǎn)，區(qū)間[a,b]為插值區(qū)間，

（*）

式為插值條件。基本概念最常用的插值函數(shù)是多項(xiàng)式基本概念最簡單的插值函數(shù)是代數(shù)多項(xiàng)式Pn(x)=a0+a1x+…+anxn插值問題變?yōu)?

求n次多項(xiàng)式Pn(x)，使?jié)M足插值條件Pn(xi)=yi

，(i=0,1,2,...,n)只要求出Pn(x)的系數(shù)a0

,a1,…,

an即可,為此由插值條件知Pn(x)的系數(shù)滿足下列n+1個(gè)代數(shù)方程構(gòu)成的

nnn nna

a

x

a x

a x

ya

a

x

a x

a x

y21 n 2 n

0n 1 120 1 1 2 10

a

a

x

a x2

a xn

y0 1 0 2 0 n 0

（7.2）[例]

給定f

(x)的函數(shù)表,求f

(x)

的

1

3

-7

11

a

7

18

a2

-4

1

1 -1 1 -1

a

1 12 45 25125

a

35

x-1125y-77435次數(shù)不超過3的插值多項(xiàng)式。解：依題意，設(shè)

P3(x)=a0+a1x+a2x2+a3x3

則解方程組得

a0=10,a1=5,a2=－10,a3=2故P3(x)=10＋5x－10x2＋

2x3329基本概念從方程組7.2解出ai(i=0,1,2,…n)，Pn(x)就可構(gòu)造出來了。但遺憾的是方程組7.2是病態(tài)方程組，當(dāng)階數(shù)n越高時(shí)，病態(tài)越重。為此我們從另一途徑來尋求獲得Pn(x)的方法----構(gòu)造法定理：設(shè)滿足條件Pn(xi)=

yi

，(i=0,1,2,...,n)的代數(shù)多項(xiàng)式Pn(x)=a0+a1x+…+anxn 是存在且唯一的3307.2

Lagrange插值7.2.1線性插值首先考慮

n=1的簡單情形。問題：已知函數(shù)y=f

(x)的函數(shù)表，求次數(shù)不超過1的多項(xiàng)式P1(x)=a0+a1x滿足插值條件 P1(x0)=y0,

P1(x1)=y1從幾何上看，就是兩點(diǎn)(x0,y0),(x1,y1)作一條直線y=P1(x)

,所以稱之為線性插值，直線方程為：001(x

x

)(

y1

y0

)P1

(x)

y0

(x

x

)7.2.1線性插值另一種對稱形式：101y(x1

x0

)(x

x0)y

(x0

x1

)(x

x1)P(x)

則P1(x)可看成兩個(gè)一次式的線性組合，如果令10(x0

x1

)(x

x

)l (x)

01(x1

x0

)(x

x

)l(x)

則P1(x)可可表示為l0(x),l1(x)的線性組合P1

(x)

l0

(x)

y0

l1

(x)

y1l0(x),l1(x)稱為線性插值的插值基函數(shù)，它們有下述性質(zhì)：

(i,j

0,1)i

j

0

i

ji j ijl

(x )

17.2.1線性插值10(x0

x1

)(x

x

)l (x)

01(x1

x0

)(x

x

)l(x)

xi13yi127.2.1線性插值[例]

已知

y

=

f

(x)的函數(shù)表求其近似插值表達(dá)式解：已知(x0,y0)=(1,1) (x1,y1)=(3,2)，

利用線性插值1 0 0 1 11

3

3

1

2P(x)

l

(x)

y

l

(x)

y

x

3

1

x

1

2

1

(x

1)

f(x)

1(x

1)2[例]

已知lg2.71=0.4330，lg2.72=0.4364。求y=lg2.718解：對y=lgx

,給出了兩點(diǎn)(2.71,0.4330),

(2.72,0.4364)，求lg2.718構(gòu)造簡單的插值多項(xiàng)式作為lgx的近似

0.4346

0.4330

2.71

2.72 2.72

2.71x

2.71x

2.72P(x)

0.16x

0.0006lg2.718

P1(2.718)

0.434287.2.2

拋物插值當(dāng)插值區(qū)間較大或曲線[x0,x1]凸凹變化大時(shí)，線性插值的誤差很大。為了減小這種誤差，用簡單的曲線去近似代替復(fù)雜曲線y=f

(x)?？紤]

n=2的情形問題：已知函數(shù)y=f

(x)的函數(shù)表，x0、x1、x2為互異節(jié)點(diǎn)，求一個(gè)次數(shù)不超過2的多項(xiàng)式P2(x)=a0+a1x+a2x2使它滿足插值條件P2(x0)=y0,

P2(x1)=y1,

P2(x2)=y2幾何意義：P2(x)為過三點(diǎn)(x0,y0),(x1,y1),(x2,y2)的拋物線，該問題即為拋物插值xix0x1x2yiy0y1y27.2.2

拋物插值如何求P2(x)

，能否用基函數(shù)的方法，構(gòu)造幾個(gè)基函數(shù)l0(x),l1(x)

,l2(x)，使P2(x)

為三個(gè)基函數(shù)的線性組合？P2

(x)

l0

(x)

y0

l1

(x)

y1

l2

(x)

y2基函數(shù)l0(x),l1(x)

,l2(x)

有下述性質(zhì)：(i,j

0,1,2)

1 i

j

0

i

jli

(x

j

)

ij

l0(x2)

0l1(x2)

0l2

(x2

)

1l0

(x1

)

0l1

(x1

)

1l2

(x1

)

0l0

(x0

)

1l1(x0)

0l2(x0)

0（7.3）7.2.2

拋物插值滿足（7.3）式的li(x)具有什么形式？首先，考慮l0(x)：l0(x0)=1 l0(x1)=0l0(x2)=0l0

(x)

C(x

x1

)(x

x2

)1(x0

x1)(x0

x2

)C

0(x0

x1)(x0

x2

)(x

x1

)(x

x2

)l(x)

同理有21(x2

x0)(x2

x1

)l (x)

(x1

x0)(x1

x2

)(x

x0

)(x

x1

)(x

x0

)(x

x2

)l(x)

7.2.2

拋物插值0(x0

x1)(x0

x2

)(x

x1

)(x

x2

)l(x)

1(x1

x0)(x1

x2

)(x

x0

)(x

x2

)l(x)

2(x2

x0)(x2

x1

)(x

x0

)(x

x1

)l(x)

10 2201 0 1 2021 yx

)

21 (xx)(xy

x

)(x

x

)(x

(x

x0

)(x

x2

)y

(x0

x1)(x0

x2

) (x

x)(x

x

)(x

x1

)(x

x2

)P(x)

xi2.712.72 2.3yi0.43300.4346 0.3627.2.2

拋物插值[例]

已知

函數(shù)表求lg2.718解：構(gòu)造拋物插值多項(xiàng)式2lg

2.718

P(2.718)

0.4342492P

(x)

0.029350

x2

0.319335

x

0.216876xlg(x)P2(x)|lg(x)-P2(x)

|2.70.4313637640.4313638084.34102E-082.7010.4315245840.431524623.58699E-082.7020.4316853450.4316853747

2.9158E-082.7030.4318460460.4318460692.32304E-082.7040.4320066870.4320067054

1.80432E-082.7050.4321672690.4321672831.35523E-082.7060.4323277920.4323278029.71378E-092.7070.4324882560.4324882626.48389E-092.7080.432648660.4326486643.81876E-092.7090.4328090050.4328090071.67464E-092.710.432969291

0.43296929102.7110.4331295180.4331295161.22539E-092.7120.433289685

0.4332896832.06858E-092.7130.4334497940.4334497912.56534E-092.7140.4336098430.4336098412.75918E-092.7150.4337698340.4337698312.69358E-092.7160.4339297660.4339297632.41196E-092.7170.4340896380.4340896361.95771E-092.7180.4342494520.4342494511.37414E-092.7190.4344092080.4344092077.04546E-102.720.4345689040.43456890402.7210.4347285420.4347285427.19837E-102.7220.4348881210.4348881221.3883E-092.7230.4350476410.4350476431.97014E-092.7240.4352071030.4352071062.42231E-092.7250.4353665070.4353665092.70183E-092.7260.4355258510.4355258542.76572E-092.7270.4356851380.4356851412.57111E-092.7280.4358443660.4358443682.07513E-092.7290.4360035360.4360035371.23497E-092.730.4361626470.43616