数值分析第二章

数值分析课件

《数值分析》Ch2 方程求根问题引例 二分法算法及其应用 不动点迭代法

Newton迭代法

数值分析课件

例2.水中浮球问题有一半径r =10 cm的球体,密 度 =0.638.球体浸入水中后, 浸入水中的深度d 是多少？rd

根据阿基米德定律,物体排开水的质量就是水 对物体的浮力。

4 M r3 3整理得:

V [r (r x) ]dxd 2 2 0

d 3 – 3 r d 2 + 4 r 3 = 0

数值分析课件

由 =0.638, r = 10.代入,得d 3 – 30 d 2 + 2552 = 0令 f (x) = x 3 – 30 x 2 + 2552 ,函数图形如下所示求解方程 f(x)=0,即 是求函数 f(x)的零 点. f(x) 的零点所 在区间为:[0, 20]roots([1 -30 0 2552]) ans = 26.3146 11.8615 -8.17613000 2000 1000 0 -1000 -2000

0

5

10

15

20

数值分析课件

用数值方法求非线性方程的根,分两步进行:第一步:对根进行隔离,找出隔根区间,或在隔根 区间内确定一个解的近似值x0; 第二步:逐步逼近,利用近似解x0 (或隔根区间) 通过迭代算法得到更精确的近似解. 设f(x) = 0的根为 x*,通过迭代计算,产生序列: x0 x1 x2 · xn··· · · ··· ···

只须

lim x n xn

*

数值分析课件

二分法迭代已知方程 f(x)=0有一隔根 区间[a, b],且f(x)满足 f(a)· f(b)<0,则先将[a , b]等 分为两个小区间,判断根属 于哪个小区间,舍去无根区 间保留有根区间[a1, b1];

把区间[a1, b1] 一分为二,进一步判断根属于哪个更 小的区间[a2, b2],如此不断二分以缩小区间长度 .

数值分析课件

已知f(x)=0在[a,b]内有一根,且f(a)f(b)<0(1)计算: ya f(a) , x0 0.5(a+b), y0 f(x0)

判断,若y0=0,则x0是根,否则转下一步; (2)判断,若y0·a<0,则a1 a, b1 x0 y否则 a1 x0, b1 b, ya y0

[a, b]

x0=0.5(a+b)

[a1,b1]=[a,x0]

x1=0.5(a1+b1)

[a1,b1]=[x0,b]f(a1) f(b1) < 0

数值分析课件

二分法迭代将得到一系列隔根区间

[a, b] [a1 , b1 ] [a2 , b2 ] [an , bn ] 性质:1. f(an)· n)<0; 2. bn – an = (b – a)/ 2n f(b定理2.2 设x*是 f(x)=0在[a, b]内的唯一根,且 f(a)· f(b)<0,则二分计算过程中, 各区间的中点数列 1 xn (an bn )( n 0,1,2, ) 2 满足: | xn – x*|≤ (b – a)/ 2n+1 思考: | xn+1 – xn | = ?

数值分析课件

例 3 用二分法求方程 e 解: 令 f ( x) e x

x

sin( x / 2) 0

在区间 [0, 1]内的根,要求误差不超过2-5.

sin( x / 2) , 绘图如下 4 3

x=-1:.5:2; y=exp(-x)-sin(pi*x/2); plot(x,y) grid有一个点介于0和1之间. 显然f(0)· f(1)< 0,

2

1

0

-1 -1

-0.5

0

0.5

1

1.5

2

数值分析课件

f=inline('exp(-x)-sin(pi*x./2)'); a=0;b=1;er=b-a;ya=f(a);k=0;er0=1/2^5; while er>er0 x0=.5*(a+b); 0 0.5000 y0=f(x0); 0.2500 0.5000 if ya*y0<0 b=x0; 0.3750 0.5000 else 0.4375 0.5000 a=x0; 0.4375 0.4688 ya=y0; end disp([a,b]);er=b-a;k=k+1 end

数值分析课件

水中浮球问题: x 3 – 30 x 2 + 2552 = 0f=inline('x.^3-30*x.^2+2552'); a=0;b=20;er=b-a;ya=f(a); k=0;er0=.005; while er>er0 x0=.5*(a+b); y0=f(x0); if ya*y0<0 b=x0; else a=x0; ya=y0; end di

sp([a,b]);er=b-a;k=k+1; end

10 10 10.0000 11.2500 11.2500 11.5625 11.7188 11.7969 11.8359 11.8555 11.8555 11.8604

20 15 12.5000 12.5000 11.8750 11.8750 11.8750 11.8750 11.8750 11.8750 11.8652 11.8652

x

11.8628

数值分析课件

将一个计算过程反复进行称为迭代,迭代法 是一类常见常用的计算技术 1 1 1 一种圆周率计算方案: 1 初值: x0=1

4

3

5

7

( 1)n 迭代格式: xn xn 1 2n 1

( n=1,2,3,·· ·· ··)

构造有效的迭代格式 选取合适的迭代初值 对迭代格式进行收敛性分析

数值分析课件

当M=45o时,求解开普列方程: E= M + e sinEe = 0.1~0.2, 迭代公式: Ej+1 = M + e sinEj (取E0 = M, 误差界:10-8)

e0.1 0.12 0.14 0.16 0.18 0.2

迭代次数7 8 8 9 9 9

E0.86126488447271 0.87771162159335 0.89459166643904 0.91190566740348 0.92965233106520 0.94782822306545

数值分析课件

例2.2 方程 x3 + 4x2 – 10 = 0 在 [1, 2] 上有一个根, 将方程变换成另一形式

(1) x 10 x / 23

xn 1 ( xn ) x0 1.5

( x ) 10 x / 23

( n = 0, 1, 2, ··) ·· ··

(2)

x 10/( x 4) ( x) 10/( x 4)

xn 1 ( xn ) x0 1.5

( n = 0, 1, 2, ··) ·· ··

数值分析课件

fi=inline('0.5*sqrt(10-x^3)'); x0=1.5;er=1;k=0; while er>0.00001 x=fi(x0); er=abs(x-x0); x0=x;k=k+1; endfi=inline('sqrt(10/(4+x))'); x0=1.5;er=1;k=0; while er>0.00001 x=fi(x0); er=abs(x-x0); x0=x;k=k+1; end

roots([1,4,0,-10]) ans = -2.6826 + 0.3583i -2.6826 - 0.3583i 1.3652

k=16 x0=1.3652 k=6 x0=1.3652

数值分析课件

f(x) = 0 x ( x )迭代格式:

xn 1 ( xn )

( n = 0, 1, 2, ·· ·· ··)

若存在 x*,使得 x* ( x*) ,则称x*为不动点y=x y (x)

(x)

迭代函数

x2

x1

x0

x ( x) y x y ( x)

数值分析课件

引理2.1 如果 ( x) C [a, b] ,满足条件:1

(1) a ( x) b ;

(2) | ( x) | L 1

则 (x) 在 [a, b] 有唯一的不动点 x*证 若 (a) a 或 (b) b ,显然 (x) 有不动点

设 (a) a , (b) b 则有 (a) a , (b) b记 ( x) ( x) x 则有 (a) (b) 0

所以,存在x*,使得 ( x*) 0即

( x*) x * , x*即为不动点.