数值分析方程求根二分法

数值分析方程求根二分法第1页，共17页，2023年，2月20日，星期六数值计算中的基本原则(1)避免绝对值小的数做除数;(2)避免两相近数相减;(3)防止大数“吃”小数现象

a=109，b=9，在8位浮点数系统中做加法a+b=1.0000000×109+0.000000009×109由于只保留8位有效数，处于第九、十位的数09被舍去,实际操作是:

将

a的数据作为加法计算的最终结果.2/16第2页，共17页，2023年，2月20日，星期六(4)尽量减少计算工作量(乘、除法次数)例计算

P(x)=1+2x+3x2+4x3+5x4的值秦九韶算法

P(x)=1+x(2+x(3+x(4+5x)))应用:2进制数转换为10进制数算法(11101110)2=27+26+25+0+23+22+2+0=((((((1·2+1)2+1)2+0)2+1)2+1)2+1)2+0=2383/16第3页，共17页，2023年，2月20日，星期六例1

计算

(

n=0,1,···,20

)4/16(分部积分法)第4页，共17页，2023年，2月20日，星期六初值：I0=1–e

–1≈0.63212055882856

n=20时，S20=-30.19239488558378递推公式:In=1–nIn-1

(I0=1-e-1)S0=1-exp(-1);S(1)=1-S0;forn=2:20S(n)=1-n*S(n-1)end实际计算:Sn=1-nSn-1,S0=0.63212055882856

|e(S0)|=|S0–I0|<0.5·10-14error5/16第5页，共17页，2023年，2月20日，星期六由In=1-

nIn-1Sn-In=-

n(Sn-1-

In-1)则e(Sn)=–ne(Sn-1)=······=(n!)(–1)ne(S0)新算法:In-1=(1-In)/nS(30)=1/31forn=30:-1:2S(n-1)=(1-S(n))/n;endS0=1-S(1),S(1:21)初值误差在算法执行过程中不断增大,这种算法称为数值不稳定算法。6/16Sn-1-In-1=–(Sn

-

In)/n和Sn=1-nSn-1得Sn-1=(1-Sn)/n第6页，共17页，2023年，2月20日，星期六

在算法执行过程中,舍入误差对计算结果影响不大的一类算法被称为数值稳定算法;否则称为不稳定算法.初始误差在算法执行过程中不断减小,这种算法称为数值稳定算法。|e(S20)|=|S20-I20|=|(1-S21/21)-(1-I21/21)|=|S21-I21|/21=·······=|S30-I30|/(21·22·23·····30)7/16第7页，共17页，2023年，2月20日，星期六

r

d

例2.水中浮球问题

有一半径r

=10cm的球体,密度

=0.638.球体浸入水中后,浸入水中的深度d

是多少？

根据阿基米德定律,物体排开水的质量就是水对物体的浮力。整理得:d3–3rd2+4r3

=0注意：上式已知物体密度

=0.638,r=10,水的密度为1.第8页，共17页，2023年，2月20日，星期六由

=0.638,r=10.代入,得d3–30d2+2552=0令

f(x)=x3–30x2+2552,函数图形如下所示求解方程

f(x)=0,即是求函数

f(x)的零点.f(x)的零点所在区间为:[0,20]9/16roots([l-3002552])ans=26.3146

11.8615-8.1761第9页，共17页，2023年，2月20日，星期六第一步:对根进行隔离,找出隔根区间,或在隔根区间内确定一个解的近似值x0;设f(x)=0的根为

x*,通过迭代计算,产生序列:

x0

x1

x2

···

xn·········用数值方法求非线性方程的根,分两步进行:第二步:逐步逼近,利用近似解x0(或隔根区间)

通过迭代算法得到更精确的近似解.只须10/16非线性方程算法第10页，共17页，2023年，2月20日，星期六已知方程

f(x)=0有一隔根区间[a,b],且f(x)满足f(a)·f(b)<0,则先将[a,b]等分为两个小区间,判断根属于哪个小区间,舍去无根区间保留有根区间[a1,b1];把区间[a1,b1]一分为二,进一步判断根属于哪个更小的区间[a2,b2],如此不断二分以缩小区间长度.11/16[a1,b1][a2,b2][a3,b3]二分法迭代思路第11页，共17页，2023年，2月20日，星期六[a,b]x0=0.5(a+b)[a1,b1]=[a,x0][a1,b1]=[x0,b]x1=0.5(a1+b1)f(a1)f(b1)<0已知f(x)=0在[a,b]内有一根,且f(a)f(b)<0(1)计算:yaf(a),x00.5(a+b),y0f(x0)

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

x0

否则

a1x0,b1b,yay012/16二分法算法第12页，共17页，2023年，2月20日，星期六二分法迭代将得到一系列隔根区间

定理2

设x*是

f(x)=0在[a,b]内的唯一根,且

f(a)·f(b)<0,则二分计算过程中,各区间的中点数列性质:1.f(an)·f(bn)<0;2.bn–

an=(b–a)/2n满足:|xn–x*|≤(b–a)/2n+113/16二分法第13页，共17页，2023年，2月20日，星期六例3

用二分法求方程

在区间

[0,1]内的根,要求误差不超过2-5.x=-1:.5:2;y=exp(-x)-sin(pi*x/2);plot(x,y)grid有一个点介于0和1之间.显然f(0)·f(1)<0,14/16解:

令

,

绘图如下第14页，共17页，2023年，2月20日，星期六

00.50000.25000.50000.37500.50000.43750.50000.43750.468815/16f=inline('exp(-x)-sin(pi*x./2)');a=0;b=1;er=b-a;ya=f(a);k=0;er0=1/2^5;whileer>er0x0=.5*(a+b);y0=f(x0);

ifya*y0<0b=x0;

elsea=x0;ya=y0;

enddisp([a,b]);er=b-a;k=k+1end第15页，共17页，2023年，2月20日，星期六水中浮球问题:x3–30x2+2552=0

x

1020101510.000012.500011.250012.500011.250011.875011.562511.875011.718811.875011.796911.875011.835911.875011.855511.875011.855511.865211.860411.865216/1611.8628f=inline('x.^3-30*x.^2+2552');a=0;b=20;er=b-a;ya=f(a);k=0;er0=.005;whileer>er0x0=.5*(a+b);y0=f(x0);

ifya*y0<0b=x0;

elsea=x0;ya=y0;

enddisp([a,b]);er=b-a;k=k+1;end第16页