计算方法课件 课件 刘火星 第6-9章 非线性方程解法-常微分方程的初值问题

计算方法Numerical

Analysis非线性方程解法SolutionsofNonlinear

Equations2476.1

根的隔离对分法迭代法牛顿法牛顿法的改进目录问题的提出本章研究的对象是

非线性方程f(x)

0(6.1)xyy=f

(x)s若常数

s

使得

f

(x)=0

，则称

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

(x)是n次多项式，则称(6.1)式为n次多项式方程或代数方程若f

(x)是超越函数，则称(6.1)式为超越方程问题的提出方程

f(x)

=0

的解通常称为方程的根或函数f(x)

的零点，如果函数f

(x)

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

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

则称s是f

(x)的m重零点或(6.1)式的m重根。当m=1时，称s是(6.1)式的单根或f(x)的单零点。问题的提出xyy=f

(x)xyy=f

(x)问题的提出方程

f

(x)=

0求根问题包括以下三个问题：根的存在性——方程有没有根？有几个根？根在哪儿？根的精确化6.1

根的隔离xy=f(x)a根的存在定理：设f

(x)在区间[a，b]上连续，f

(a)

f

(b)<0，则至少存在一个实数s，使得f

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

根的隔离确定出若干个区间，在每个区间内有且仅有一个根——根的隔离隔离根的方法作图法：画出

y=f

(x)的大致图形，根据曲线大致判断与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理论上已证明：对于次数

n

≤4的多项式方程，它的根可以用公式表示，而次数大于5的多项式方程，它的根一般不能用解析表达式表示因此对于f

(x)=0的函数方程，一般来说不存在根的解析表达式，而实际应用中，也不一定必需得到根的解析表达式，只要得到满足精度要求的根的近似值就可以了常用的求根方法分为区间法和迭代法两大类，最简单的是对分法。6.1

根的隔离2576.2

对分法思想：用二等分区间的方法，逐步缩小有根区间，得到满足精度要求的实根

x*

的近似值

xk①

取[a，b]区间的中点x0=（a+b）/2②

若

f

(x0)=

0，则x0是

f

(x)=0的实根③

若

f

(x0)≠

0，则由

f

(x0)的符号确定新的有根区间f

(a)

f

(x0)<0

成立，则根必在区间(a，x0)内，取a1=a，b1=

x0f

(a)

f

(x0)>0,根必在区间(x0

，b)内，取a1=

x0

，b1=

b④

这样，得到新区间[a1，b1]，其长度为[a，b]的一半，如此继续下去，进行k次等分后，得到一组不断缩小的区间

[a，b]

，

[a1，b1]

，......[ak，bk]xy=f(x)f(a)确定有解区间将区间分成两半x0=(a+b)/2求f

(x0)判断有解区间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]的中点为 xk=(ak+

bk)/2④

产生根的序列：x0，x1，x2，…，xn

02kk kk

k

b

a

lim

b

a

limklim

x

x*k

对分法是收敛的

k,

x*

[a

,

b

]k k误差将有限次对分的结果xk作为根的近似值，其误差为多少？22k

1k

bk

ak

b

ax*

x什么时候停止？给定精度εx*

x

k[例]求方程f

(x)=x3

－

x

－1在区间(1,1.5)内的根,要求精确到小数点后的第二位。[解]① a=1,b=1.5且

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

ε=10-2/2=0.005由误差估计式|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什么时候结束运算？

xn

xn

1（1）f

xn

（2）

xnxn

xn

1（3）用对分法解(6.1)，使误差不超过ε的终止准则（1）

先验估计2k

1k

b

a

x*

xk

ln(b

a)

ln

1ln

2（2）

后验估计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)

要求不高(只要连续即可).无法求复根及偶重根收敛慢把对分法与逐步扫描法结合起来,就可以求非线性方程在任一区间上的全部实根。首先,

将方程式f(x)=0化为函数式y=f(x).假设方程求解区间为

[a,b]

,扫描区间为h。由a点出发向

b点扫描，每跨一步，判断在该区间内是否有根。如有根则进行对分法求根计算，否则继续向前找根，直到走出区间[a,b]为止x*x7

=1.6758[例]求方程f

(x)=2x3

－5x－1在区间(1,2)内的根,要求误差限为

ε≤10-2[解] f

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

f(1)<0,

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

=(1+2)/2=1.5因为 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的一个初始近似值x0

，然后反复使用某一公式校正这个初始值，使之逐步精确化，直到满足精度要求为止x1

x0x2

x1...xn

xn

1构造迭代公式：xn+1

=

g(xn)产生解的序列：x0，x1，x2，…，xn等价变换 f(x)=0 x=g(x)等价方程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

迭代法迭代法要解决的问题：如何构造迭代函数？如何判断迭代格式是否收敛？如何估计误差？迭代法的几何意义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发散迭代法的几何意义O x3 x1 s x0

x2y

g(x)y

x发散g

(

x

)在s附近较陡峭y

g(x)y

xO x1 x3 s x2 x0收敛g

(

x

)在s附近较平缓迭代法的收敛性定理

定理：假定函数 满足下列条件：

则（1）方程

x=g(x)在区间[a,b]迭上有唯一根

s（2）对于任意初值

x∈[a,b]

，迭代过程

xk+1=g(xk)均收敛于s（3）且有如下的误差估计式：

g(x)（1）对任意

x

a,

b

有a

g(x)

bLkx

k

s

1

L x1

x

0x

(a,b)（2）存在正数

L<1，使对任意

x

有

|

g

(x)|

L

1277代是收敛？0

内，迭如果x

在区间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

内，迭所以x

在区间I

[0,

]2Nxn0否 0.500010.702120.610830.655340.6343……

…11敛 0.6411（1）

先验估计（2）

后验估计x

s

kln

Lx1

x0k

ln

(1

L)

xk

1

xk用迭代法解(6.1)，使误差不超过ε的终止准则kkx

xx

s

k

1L1

L279迭代法的收敛性定理定义：对于方程

x=g(x)

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

s

的某个临域Δ:|x-

s|≤δ,使迭代格式

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

Δ均收敛,则称该迭代格式在s 附近具有局部收敛性.定理：设s为方程

x=g(x)的根，

g’(x)在

s

附近连续,且|

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

x=e-x

在0.5附近的一个根，要求ε=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,如果存在正实数

p

和C，使得pk

Ck

elimek

1则称迭代格式是p阶收敛的。当p=

1时称为线性收敛（

0<

C<1），

1<

p

<2时称为超线性收敛

，p

=2时称为平方收敛定理：若迭代格式

xk+1=g(xk)

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

s,且1.

g(x)在s附近具有连续的二阶导数2.|

g’(s)|<1当g’(s)≠0时，迭代格式为线性收敛当g’(s)=0，g”(s)≠0时，迭代格式为平方收敛282迭代法的收敛速度设迭代格式

xk+1=g(xk)

是1阶收敛的

C 0

C

1eklimek

1k

设迭代格式

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的正实根，并考察收敛速度[解]

有两种方案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)

在求根范围内改变不大，取g’(x)≈a当|

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.将以上误差补偿给yk

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

axk

1

yk

(

y

x )

a

改进 xk

1

yk

1

a

(

yk

xk

)

迭代 yk

g(xk

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

x=e-x

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

(x)=

-

e-x

在x=0.5

附近有g’

(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进120.567067130.567186140.567119150.567157160.567135170.567148180.567141190.567145200.567142210.567144220.567143230.567143287迭代法的加速方法c.

上述方法要用导数g’(x)的近似值，可以进一步改进k kzk

2

yk

xk(

y

x )2

迭代 zk

g(yk

)

改进 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如果简单迭代法已经具有p（p≥2）阶收敛速度，则构造Steffensen迭代法对提高收敛速度作用不大Steffensen迭代法可以把简单迭代法不收敛的情况改为2阶收敛定理：设

s

=g(s)

，

g”(s)在包含

s

的某个区间内连续,且g’(

s

)≠1，则存在δ，当x0∈[s-δ,

s+δ]但x0

≠

s时，由Steffensen

迭代法产生的序列至少以2阶收敛速度收敛于s。[例]

用Steffensen迭代法解方程x3-x-1=0.结果见右表，发散的代公式加速后取x0=1.5 进行有较好的收敛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)迭代函数构造得好坏影响收敛速度，甚至收敛用近似方程代替原方程6.4

牛顿法Newton-RaphsonMethod思想：将非线性方程线性化（用Taylor展开）(1)

取x0

s,

将f

(x)在x0点作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)

一直重复可得迭代序列(k

0,1,2,

)f'(x

)f(x

)kkxk

1

xk

这种迭代方法称为牛顿迭代法。f

'(x)牛顿法事实上是一种迭代法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定理：设s为方程的根，在包含

s

的某个区间内g”(x)连续,且g’(x)≠1，则存在δ，当x0∈[s-δ,

s+δ]但x0

≠

s时，由牛顿法产生的序列{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]内的根nn3x2

4x

10x3

2x2

10x

20xn

1

xn

n n n f(1)

7,f(2)

16,f(1)f(2)

0f

(x)

在区间[1,2]上连续f

(x)

0 在区间[1,2]上有解[解]0111.41176521.37345531.36922541.36884551.36881161.36880871.368808结论：牛顿法的收敛性依赖于x0

的选取。sx0 x0

x0f(x)正常情况，

x0足够接近s，收敛。构成一个平行四边形，不可能逼近s。切线太平，超出了x迭代范围。牛顿法的收敛定理（收敛的充分条件）设

f

(x)在[a,

b]上满足条件：(x)在

[a,

b]上连续，不变号；[a,

b]

使得

f (x0)f(x0)

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

0；f (x)、

f选取初始值x00；则由牛顿法产生的序列{

xk

}

单调地收敛到f(x)在

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

'(x)

1

sin

xf

"(x)

cos

xf

(x)

x

cos

x[例]求

x

c

o

s

x

0

在区间[-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，计算f(x0)、f

′(x0)Step2. 迭代

x1=x0

-f(x0)/f

′(x0)，计算f(x1)、f

′(x1)Step3. if

(|f(x1)|<δ

或|x1-

x0|

<ε) 输出x1,stopStep4.

以x1、f(x1)、f

′(x1)替代

x0

、

f(x0)、f

′(x0)

，goto Step2牛顿法的特点优点：

收敛快!

缺点：

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

s

才能保证收敛6.5

牛顿法的改进（1）简化牛顿法xyx1

x0sx

2112f'(x

)0f(x

)x

x

001f'(x

)f(x)

0 x

x6.5

牛顿法的改进（1）简化牛顿法——用常数代替导数(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

牛顿法的改进（2）割线法6.5

牛顿法的改进（2）割线法——用差商代替导数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

牛顿法的改进单点割线法——在割线法中用固定点（x0,f(x0)）（xk-1,f(xk-1)）k 0f(x

)kk

xk

x0

f

x

f

x

x

x

k

16.5

牛顿法的改进（3）牛顿下山法xo

的选取很重要,如

x0偏离s

较远，则可能发散.(k

0,1,2,

)f

(x

)f

(x

)kkk

1

kx

x

)

f

(x

)k

1

k

的选取使得

f

(x

=

1代入探注： =

1时就是Newton’s

Method

公式。效果不好时，将 减半计算,逐步试[例]

用牛顿下山法解方程x3-x-1=0.kxkxk0.60.611.14062517.921.36681411.946831.326287.9855241.324725.35690951.3247183.62499661.3247182.505589当71.8201298。1.46104491.339323101.324913111.324718121.3247186.5

牛顿法的改进（4）求m重根的牛顿法若s是(6.1)式的m重零点或的m重根，函数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当方程有重根时,收敛会减慢[

例]

用牛顿法解方程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附近有单根重根时收敛会减慢，m越大越慢（4）求m重根的牛顿法如何加速重根的收敛？Ans1:

如果m已知(k

0,1,2,

)f

(x

)f

(x

)x

x

mkk

1

kkAns2:

如果m未知，考虑将求f

(x)的重根转化为求另一函数的单根f

(x)u(x)

f

(x)u(x)在s为单根，应用牛顿公式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法及两种改进的Newton法各计算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

为线性收敛，这时p

=1，0<C<1Steffensen

加速有p

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

，称为平方收敛Newton’s

Method

只要f

‘(

s)≠0

，就有p

≥

2。重根是线性收敛的。割线法有p

>1.618，称为超线性收敛。单点割线法为线性收敛。比较各种迭代法的收敛阶小结二分法简单迭代法基本思路、收敛性：大范围收敛与局部收敛、精度控制、算法实现收敛速度定义、如何判断收敛阶Steffensen迭代法构造迭代、收敛性与收敛速度小结Newton迭代法构造原理、迭代公式收敛性与收敛阶简化牛顿法割线法（构造原理、迭代公式、单点割线法）求m重根的改进Newton法插值与逼近Interpolationand

Approximation3217.1

插值基本概念Lagrange插值Newton插值等距节点插值Hermite插值样条插值7.7

最小二乘法目录7.1

插值基本概念Lagrange插值Newton插值等距节点插值Hermite插值样条插值目录问题的提出实际工作中，很难找到f

(x)的具体表达式，只能观测到一些离散数据或者f

(x)过于复杂而不易运算思路：用简单函数为离散数组建立模型或为复杂函数建立逼近xix0x1x2x3x4yiy0y1y2y3y4用简单函数为离散数组建立模型或为复杂函数建立逼近需要解决三个问题① 选定简单函数的类型。通常是选取一组线性无关的简单函数

,0

,1

...,

n

，利用它们形成线性空间

span{

0

,

1,

2,

,

n}利用形如P(

x)

a0

0

a1

1

an

n（7.1）的函数产生模型和进行逼近。问题归结为求a0,a1,...,an

，称

0,

1,...,

n

为基函数。② 建立关于模型或逼近的目标，目标决定(7.1)式中

必须满足的条件。条件分插值型和逼近型两类③ 建立算法并作出理论分析给定未知函数f

(x)的一个数表yi=f

(xi)

(i=0,1,…,n)，求某个简单的函数

(x)，来逼近函数f

(x)，并且使

(xi)=yi

，这种方法称为插值法7.1

插值基本概x念ix0x1x2x3x4yiy0y1y2y3y4具体有很多种插值法，其中以拉格朗日(Lagrange)插值和牛顿(Newton)插值为代表的多项式插值最有特点，常用的插值还有Hermit插值，分段插值和样条插值插值的任务就是由已知的观测点，为物理量(未知量)建立一个简单的、连续的解析模型，以便能根据该模型推测该物理量在非观测点处的特性定义：设精确函数

y

=

f(x)

在区间[a,b]有定义，且已知在a≤x0<x1

<

x2

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

y1

,

y2

,

...,

yn，若存在一个简单的函数

(x)，来逼近函数f

(x)，并且使

(xi)=yi

，(i=0,1,2,...,n)成立。则称

(x)

为f(x)

的插值函数，称x0,

x1

,

x2

,...,xn为插值节点，区间[a,b]为插值区间，

（*）

式为插值条件。基本概念最常用的插值函数是多项式基本概念最简单的插值函数是代数多项式Pn(x)=a0+a1x+…+anxn插值问题变为:

求n次多项式Pn(x)，使满足插值条件Pn(xi)=yi

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

,a1,…,

an即可,为此由插值条件知Pn(x)的系数满足下列n+1个代数方程构成的

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)的函数表,求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次数不超过3的插值多项式。解：依题意，设

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)就可构造出来了。但遗憾的是方程组7.2是病态方程组，当阶数n越高时，病态越重。为此我们从另一途径来寻求获得Pn(x)的方法----构造法定理：设满足条件Pn(xi)=

yi

，(i=0,1,2,...,n)的代数多项式Pn(x)=a0+a1x+…+anxn 是存在且唯一的3307.2

Lagrange插值7.2.1线性插值首先考虑

n=1的简单情形。问题：已知函数y=f

(x)的函数表，求次数不超过1的多项式P1(x)=a0+a1x满足插值条件 P1(x0)=y0,

P1(x1)=y1从几何上看，就是两点(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)可看成两个一次式的线性组合，如果令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)称为线性插值的插值基函数，它们有下述性质：

(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)的函数表求其近似插值表达式解：已知(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

,给出了两点(2.71,0.4330),

(2.72,0.4364)，求lg2.718构造简单的插值多项式作为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

抛物插值当插值区间较大或曲线[x0,x1]凸凹变化大时，线性插值的误差很大。为了减小这种误差，用简单的曲线去近似代替复杂曲线y=f

(x)。考虑

n=2的情形问题：已知函数y=f

(x)的函数表，x0、x1、x2为互异节点，求一个次数不超过2的多项式P2(x)=a0+a1x+a2x2使它满足插值条件P2(x0)=y0,

P2(x1)=y1,

P2(x2)=y2几何意义：P2(x)为过三点(x0,y0),(x1,y1),(x2,y2)的抛物线，该问题即为抛物插值xix0x1x2yiy0y1y27.2.2

抛物插值如何求P2(x)

，能否用基函数的方法，构造几个基函数l0(x),l1(x)

,l2(x)，使P2(x)

为三个基函数的线性组合？P2

(x)

l0

(x)

y0

l1

(x)

y1

l2

(x)

y2基函数l0(x),l1(x)

,l2(x)

有下述性质：(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

抛物插值[例]

已知

函数表求lg2.718解：构造抛物插值多项式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