數(shù)值分析講稿黑白

第八章方程求根求解非線性方程f

(x)

0f

是非線性函數(shù)，例：代數(shù)方程10f

(x)

例:

方程f

(x)

ex

sin

x

0a

x

a

xn

n1n

n1a

x

a

0,

n

1。L

設

f

(x)

在[a,b]

上連續(xù)且

[a,b]

有且僅有一個根又f

(a)

f

(b)

0。則可用對分法：不妨設

f

(a)

0,

f

(b)

011

1122

2

b

bab2

a

ab2a

a.

1）,若f

ab

0

輸出根x

ab

,否則：若f

ab

0

，令，b

反之

,2),對[a1,b1]區(qū)間重復1）的計算，并產(chǎn)生[a2,b2],L.22x

a

i

bi3),

若

f

a

i

bi

0，則得到根

§1.

非線性方程實根的對分法(二分法)二分法的收斂性二分法產(chǎn)生一個有根區(qū)間：[a,b]

[a1,b1]

L

[an,bn][a

n,b

n

]

區(qū)間長度：22

nn

nn

1

n

1

a

1

(b

a)

L

1

(b

a

)b當n

足夠大時，取近似值2

a

n

bn

，xnb

ax

x

n

2n

1

誤差：計算簡便，容易估計誤差，但收斂較慢。x0bf

(x)a1a

x*b1§2.

迭代法改寫方程：f

(x)

0

x

(x)且

連續(xù)。建立迭代格式：xn1

(xn)，得到序列{xn

}則若{x

n}收斂必收斂到f

(x）

0

的根：nlim

x

n

1

limn

n

(

x

)

lim

x

n

n

x*，則：x*

(

x*

)

f

(

x*

)

0lim

xn若{x

}收斂，即nn

迭代過程的幾何表示y

(x)Ox*x2x1x0xyP0Q1P1P2Q

2P

*x

(x)

y

(x)x

yy

x交點即為真根例：求方程f

(x)

x3

x

1

0

在x0

1.5附近的根x*.解：（1）將方程改寫為x

3

x

1k

0

1

2xk

1.5

1.35721

1.33086xk

1

3

xk由此建立迭代公式

1(k

0,1,

2L

)L

7

8L

1.32472

1.32472迭代收斂。（2）若將方程改寫為x

x3

1k

0

1xk

1.5

2.375kk

1

x3

1.2

L12.39

L建立迭代公式

x迭代不收斂。定理.設函數(shù)

(x)在區(qū)間[a,b]上滿足條件（1）對任意x

[a,b]，都有a

(x)

b;(2)存在常數(shù)0

L

1,使得對一切x,y

[a,b],都有

(

x)

(

y

)

L x

y則方程x

(x)在[a,b]內(nèi)有唯一的根x*,且對任何初值x0

[a,b],迭代序列xn

1

(

xn

)均收斂于x*，并有(n

0,1,L

)*x

xnLn1

Lx

x10收斂充分性定理(一、1)證：

由條件（2）

知

(

x

)在[a

,

b

]上連續(xù)。令

(

x

)

x

(

x

),

則

(

x

)在[a

,

b

]上連續(xù)，

且

(a

)

a

(a

)

0,

(b

)

b

(b

)

0故存在

[a

,

b

]，

使得（）

0,即

（）,所以方程x

(x

)在[a

,b

]內(nèi)有根。**12*

*x*1

x*

21

2**1x

,由條件（2），有(

x

)

(

x

)

L

x

x

x*

x*2

1

2假設方程x

(x)在[a,

b]內(nèi)有兩個根x

導出，唯一性得證。收斂充分性定理(一、2)對任意x

0

[a

,b

],由迭代公式依此類推，

得

xn

x0

L

x

x*

n

*有x

xk

(

xk

)

(

xk

1

)

L

xkxk

1

xk

1n

x

*

(

x

)

(

x

*

)

L

x

x

*n

1n

1n

因

0

L

1,

所以

lim

xn

x

*即對任意初值x

0

[

a

,

b

],

迭代序列xn

均收斂到方程的根

x

*。類似地，對任意正整數(shù)k

,有

L

Lk

x

x1

0收斂充分性定理(一、3)xn

p

xn

xn

p

xn

p1

xn

p1

xn

p2

xn1

xnn

p1L

x1x0

Ln

p2x

x1

01)

x1

x0L

Lnx

1x0

Ln(Lp1

Lp

2

L10x*

x于是，對任意正整數(shù)n,p,有1

Lp1

L令p

,得nLnx1

x01

LnL

x

xL收斂充分性定理(一、4)kk

1x

x

Lk

x

x10收斂充分性定理(二、1)定理.設函數(shù)

(x

)在區(qū)間[a

,b]上滿足條件（1）對任意x

[a

,b

]，都有a

(x

)

b;(2)存在常數(shù)0

L

1,

使得對一切x

[a

,

b],

都有

'

(

x

)

L則方程x

(x

)在[a

,b]內(nèi)有唯一的根x*,且對任何初值x0

[a

,b],迭代序列xn

1

(

xn

)均收斂于x*，并有*(n

0,1,L

)x

xnLn1

Lx

x10收斂充分性定理(二、2)證：設x

,y為[a

,b

]上任意兩點，由微分中值定理，在x

,y

之間至少存在一點

，使得

(

x

)

(

y

)

'

(

)(

x

y

)

(

x

)

(

y

)

'(

)(

x

y

)

'

(

)(

x

y

)

L x

y即

(x

)滿足上一定理的條件（

2

），故結論成立。*誤差估計式

x

xnLn

x

x

表明，常數(shù)L越小，1

L1

0簡單迭代法收斂越快。因而構造迭代函數(shù)(x)的原則是使'(x)在有根區(qū)間[a,b]上有盡可能小的上界。對任意正整數(shù)p有

xn

p1

xn

p2

xn1

xn1）xn1

xnxn

p

xn

xn

p

xn

p1n1

n

1

x1

L

1

x（

Lp1

Lp2

L令p

,得nn1n

x

xx*

x1

L可通過檢查xn1

xn

來判斷迭代過程應否終止。L例：用簡單迭代法求方程

f

(x)

x2

x

1

0

的根。解：因

f

(1.5)

0.25

0,

f

(2)

1

0

[1.5,2]

為有根區(qū)間。（1）x

x

1

1(x)

因1.5

1.51

1(x)

'122

1

21

1

1且

(x)3.1622

2.5(2)

x

1

1

(x)

2

x

12'2x且

(x)2

1.5因1.5

1

1

(x)1

1

21

1

11.52

2.25x2

根據(jù)定理，任取x0

[1.5,2],由這兩種等價方程所構造的

簡單迭代方法都收斂，且第一種所產(chǎn)生的迭代序列收斂較快。收斂充分性定理(三、1)定理：如果函數(shù)(x)在x*的一鄰域O(x*

,

*

)內(nèi)連續(xù)可微，x*為方程x

(x)的根，且'(x)

1,則存在正數(shù)

,

*,使得對任意*

*0x

[x

,x

],迭代序列xn1

(xn

)收斂于x*.(n

0,1,2,L

)證：因'

(x)在O(x*

,

*

)內(nèi)連續(xù)，且

'

(x)

1,故存在正數(shù)L

1,

*

,

使得對x

[x*

,

x*

]，有'

(x)

L

1另一方面，由(x*

)

x*

,又有(x)

x*

(x)

(x*

)

L

x

x*

*即(x)

[x*

,

x*

]。由上面定理知，迭代序列xn1

(xn

)收斂于x

。收斂充分性定理(三、2)實際用迭代法計算時，先用對分區(qū)間法求較好的初值，然后再進行迭代。迭代法加速（埃特肯方法）（1）*設x0是根x

的某個

值，

通過兩次迭代校正x1

(

x0

)

x2

(

x1

)*

'1

010x

x*

(

x

)

(

x

)

( )(

x

x*

)*

'2

1

2

1x

x*

(

x

)

(

x

)

( )(

x

x*

)假定

'(x)改變不大，近似地取某個近似值L,201

x*

L

(

x

x*

)有由微分中值定理，有1

2(

x

x

)2則由x

x*

L

(

x

x*

)

x1x

x*x

x*10x*

x2

2

1

*x

x

x

x*2

1

0x

2

x

x此種加速需用兩次迭代值進行加工。迭代法的加速（埃特金方法）（2）如果將一次改進值作為一步，則計算公式如下：k

1(xk

1

x%k

1)2x%k

1

(xk

)xk

1

(

x%k

1)k

1xk1

x

xkk

1

2x%

x校正

再校正改進

§3.

Newton

法非線性問題的最簡單解法是線性近似.將非線性方程線性化，以線性方程的解逐步近非線性方程的解，這就是Newton法的基本思想f

(x)

0

在真根附近

x0

點展開成

Taylor

級數(shù)：200

0

002!'''()f(x)

f(fxfx

x

xx)(x-

)(

)xL)

0)'(

x0x1

x01)解出x作為近似根x

：f

f(

x0

)

(

f'(

x0n

0,

1, 2,

f'

f

(xn)

(xn),依次產(chǎn)生迭代格式，稱

Newton

法：xn1

xn)x

x

00取線性部分近似代替f(x)

0

:

f(x

)

f

'

(x0

0Newton

法的幾何解釋0

1

ξ與

x

軸

交

點

(y

0

)

為

第

二

個

近

似

根

x

1

：'f

'(

x

0

)x

1

x

0

f

(

x

1)0

0

0fx

x

xy

f

()

( )(x

)當

x0

在取定后（在真根

附近），過

x0,

f

(

x0)作

f

(x)

的切線，則切線方程：'(0，f(0))定義：

設迭代過程xk

1

(

xk

)收斂于方程x

(x)的根x*

,如果迭代誤差e

x

x*kk當

k

時成立下列漸進關系式

C

(C

0為常數(shù)）e

pek

1k則稱該迭代過程是p階收斂的。p

1為線性收斂，p

1為超線性收斂，p

2為平方收斂。迭代法收斂速度定義定理：對于迭代過程xk

1

(xk

),如果

(x)在所(

p)求根x*的鄰近連續(xù)，并且'

(x*)

"(x*)

L

(

p1)

(x*)

0;

(

p)

(x*)

0則該迭代過程在點x*鄰近是p階收斂的。證：由于'

(x*)

0

1,故x

(x

)具有局部收斂性。k1

k**(

p)

()**

p(

p)

()k1k(x

x*)

pp!k(x

x

)p!p!k將(x

)k(x

)

(x

)

kep(

p)

(x*)在根x

處展開，由條件有e

k

1

x

x

迭代過程的收斂速度依賴于迭代函數(shù)

(x

)的選取。如果當x

[a

,b

]時只可能是線性收斂。'(x

)

0,則該迭代過程k

1

kf

'

(

x

)f

(

x

)

f

''

(

x

)'2'

f

(

x

)

假定x*是f

(x

)的一個單根，即f

(x*

)

0,f

'(x*

)

0,則由上式知

'(x

*

)

0,由上述定理知，牛頓法在根x*的鄰近至少是平方收斂的。f

(

xk

)f

(

x

)

(

x

)

x

由于

(

x

)

kf

'

(

x

)對牛頓公式

x

x

其迭代函數(shù)為例：用牛頓法解方程

xex

1

0.解：f

(

x

)

xe

x

1,

f

'

(

x

)

e

x

(1

x)f

'

(

x

)xk

1牛頓公式為

xkf

(

x

)牛頓法迭代函數(shù)為

(x)

x

1

x

xk

e

xkx

e

x1

xk可先用二分法或經(jīng)驗確定迭代初值x0

0.5，

再按牛頓公式進行迭代。

x

Newton法具有收斂快，穩(wěn)定性好，精度高等優(yōu)點，是求解非線性方程的有效方法之一。但它每次迭代均需計算函數(shù)值與導數(shù)值，故計算量較大。而且當導數(shù)值提供有時，Newton法無法進行?！?.弦截法與拋物基本思想：利用一些函數(shù)值f

(xk

),

f

(xk

1

),L

來回避導數(shù)值f

'

(xk

)的計算。設xk

,

xk

1,L

,

xk

r是f(x)

0的一組近似根，利用函數(shù)值f

(xk

),

f

(xk

1

),L

,

f

(xk

r

),構造插值多項式pr

(x),并適當選取pr

(x)

0的一個根作為f

(x)

0的新的近似根xk＋1，這就確定了一個迭代過程，記迭代函數(shù)為：xk

1

(xk

,

xk

1,L

,

xk

r

).當r

1時為弦截法，當r

2時為拋物

。一、弦截法設xk

,xk

1是f

(x)

0的近似根，利用f

(xk

),f

(xk

1

)構造一次插值多項式p1

(x)，并用p1

(x)

0的根作為f

(x)

0的新的近似根xk

1.k

1

kk由

p1

(

x)

f

(

xk

)

(

x

x

)kk

1f

(

xk

)

f

(

xk

1

)f

(xk

)

f

(

xk

1

)kk

1(

xk

xk

1

).x

xf

(

xk

)

x

xkf

'

(

x

)此迭代公式可看作牛頓公式x

x

f

(

xk

)

中的導數(shù)kk k

1x

xf

'(x

)用差商f

(xk

)

f

(xk

1

)取代的結果。弦截法的幾何表示x0x*x1

x2x3

XYf(x)<0P0P2P1弦截法在求xk

1時要用到前面兩步的結果xk,

xk

1.需兩個初值x0,

x1，

而牛頓切

在計算xk1時，

只用到前一步xk的值。弦截法收斂性定理定理：假設f

(x)在根x*的鄰域

:

x

x*

內(nèi)具有二階連續(xù)導數(shù)，且對任意x

有f

'

(x)

0,又初值x0

,

x1

,

那么當鄰域充分小時，弦截法f

(xk

)k

k

1k

k

1xk

1

xk

(x

x

).f

(x

)

f

(x

)2將按階p

15

1.618收斂到根x*.弦截法收斂性定理（1）***證：

用數(shù)學歸納法證明迭代值全屬于。首先證明當xk

1

,

xk

時xk

1必屬于。設f

(

x*

)

0，p

(

x)是以x

,

x

為節(jié)點的插值多項式。1

k

1

kf

"

(

)121又由于xk

1是p1

(x)

0的根，故有2(

x

xk

)(

x由

f

(

x)

p1(

x)

1

(

x

xk

)(

x

xk

1

) p

(

x

)

2"f

(

)f

"

(

)

xk

1

)

1

ekek1.'*k

1p

(

x*

)

p

(

x*

)

p

(

x

)

p

(1

1

1

k

1

1

f

(

xk

)

f

(

xk

1

)

(

x*'k k

1

)(

x

x)

)e

.k

12

k

1

x

)

f

(x

x弦截法收斂性定理（2）f

"

(

)對上兩個式子聯(lián)立

ek

1

1

ek

ek

1.2

f

'

(

2

)由于1

,

2

[xk

1

,xk

],故當xk

1

,xk

時m

ax

f

"

(

x

)

1

,

2

.2

m

in

f

'

(

x

)因x

0

,x1

,由數(shù)學歸納法知一切xk

全屬于

x

.

M

.xek

1

ek

1

M

ek

xk

1

.選取鄰域

充分小,以保證M

1,

則當xk1與xk

屬于

時記

M

弦截法收斂性定理（3）2k

2k

3

M

4e*ek

1

ek

1'2f

"

(

)這里M

*

2

f

'

(

x*

)f

"

(

x*

)

.2

f

(

)ek

1

1ek

ek

11k

M

ekkM

M

ek

M22

3

e

e

ek

1

k

2

e

ek

1

k

1

1

(M

)k

e故當k

時有ek

0,

收斂性得證。當k充分大時，由令

e

L由遞推不等式M

*k

1d

zk

,則有差分方程zkk

1.

z

z弦截法收斂性定理（4）1

11

11其特征方程

為

2

1

0

1.618,

0.618;1

22

2

1

221由于

,當k充分大時

z1

1k

11

1

M

*

1

M

*k(d

)k

1

k方程zk

1

zk

z是一差分方程，考慮z

k的特解，kkk

1

1k

c

,kd

zM

*k

1c

k

1c

故差分方程的通解為

z

c

c

（c

,c

為任意常數(shù)）e

d

故而1

11

111e

M

*1－1k

1此說明弦截法收斂的階1

1.618.1M

*kkkd

zkk

1

M

*c

c

d

d

M

*

ekM

*k

1故有

e

1

（M

*

e

）ke

e埃特肯加速方法幾何解釋*設x0

是根x

的某個x1

(

x0

)值，

通過兩次迭代校正x2

(

x1

)

L

(

x0

x

*

)11則由

x

x

*x

x

*2有由微分中值定理，有x1

x

*

(

x0

)

(

x

*

)

'

(1

)(

x0

x

)**x2

x

*

(

x

)

(

x

*

)

'

(

)(

x

x

)1

21假定

'(x

)改變不大，近似地取某個近似值L

,x2

x

*

L

(

x

x

*

)(

x2

x1

)

2x

x

*

1

0

x

x

*x

*2

x

1x

x

*2x0

2

x1

xx

*x0

x

2

x

21x0

2

x1

x2用弦截法給出埃特金算法的幾何解釋用弦截法的幾何解釋。形如x

(x)的方程，給出埃特金算法點P3的坐標x3

滿足P

*3P2

y(x)PP0P1x*x1

x3

x2x0

x2

x1

(

xx

x3x

xx

x

x

2x

2

x

x2

x

)此即為加速埃特金公式.從圖上可知,盡管迭代值x

比x

和x

更遠偏離了x

*

,2

0

1但按上式定出的x3卻明顯地扭轉了這種發(fā)散的趨勢.x

由此解出二、拋物設已知方程f(x)

0的三個近似根xk,xk

1

,xk

2,以這三點為節(jié)點構造二次插值多項式p2

(x),并適當選取p2

(x)的一個零點xk

1作為新的近似根,這樣確定的迭代過程稱拋物

,也稱密勒法.f

(

x)P2(x)xk1

xkx*xk1xk2拋物

計算公式p2

(

x

)

f

(

xk

)

f

[

xk

,

xk

1

](

x

xk

)+

f

[

xk

,

xk

1

,

xk

2

](

x

xk

)(

x

xk

1

).k

ak

f

[

xk

,

xk

1

,

xk

2

]kk

1

k

2k

1k k

1

k

f

[

x

,

x

]+

f

[

x

,

x

,

x](

x

x

)

b

c

f

(

x

)

k

k插值多項式令*在xk

2

,

xk

1

,

xk

三個近似根中,假定xk

更接近根x

,故新的近xk

1

xk

似根應在xk

鄰近,即

x

xk

較小.于是拋物線計算公式為kkkb

22

a

p2

(

x

)

ak

(

x

xk

)

2

b

(

x

x

)

ck

k

k

b

4

a

ck

k

k

k

x

k

k

k

k

2c

b

2kkkk

k2ck

sgn(bk

)b

2

x

xb

4

a

cb

4

a

c可以證明,如果f

(x

)在其零點x*

鄰近三階連0

1

2續(xù)可微,且初值x

,

x

,

x

充分接近x*

,

則拋物是收斂的。特別地，若x*

是方程f

(x

)

0的單根，收斂解為1.84。另一方面，在收斂性的證明中雖然要求初始值充分接近根x*，但實際計算表明，拋物線法對初值要求并不苛刻，在初值不太好的情況下常常也能收斂。缺點是程序較復雜，并在計算實根的過程中，也常常需要采用復數(shù)計算，增加了工作量。因此，拋物適用于當初值不太好時求方程f

(x

)

0的復根的情況?！?.代數(shù)方程的牛頓法如果f

(x)是多項式，可針對多項式的特性，建立求解代數(shù)方程f

(x)

0的有效解法。計算函數(shù)