第一章-数值分析的基本概念(删减版)

数值分析上课(2--17周)每周三8:15-9:45第二教学楼121室每个单周三10:05-11:35图文3号机房(图文信息中心三楼319室)教师：吴笑千2号学院楼理学院四楼449室答疑时间：每周二下午3:00-5:00放假和上课通知

1.中秋节期间2010年9月22日至24日放假，共3天。9月19日(星期日)上星期四（双周）的课程，9月25日(星期六)上星期五（双周）的课程。2.国庆节期间2010年10月1日至7日放假，共7天。9月26日(星期日)上星期三（双周）的课程，10月9日(星期六)上星期四（双周）的课程。

数值分析数值分析（numericalanalysis），是数学的一个分支，以数字计算机求解数学问题的理论和方法为研究对象。-----

第一章

数值分析的基本概念

§1.1数值算法的研究对象

§1.2误差分析的概念§1.3数值算法设计的一些要点

现代复杂工程技术问题的解决步骤工程问题上机计算数学模型结果分析问题解答设计算法例1.1(易计算问题)(1)求解线性方程组AX=b,其中A为3阶可逆方阵，X=(x1,x2,x3)T;(2)求代数方程x2+x6=0在[0,4]上的根x*；(3)已知y=P(x)为[x0,x1]上的直线，满足P(x0)=y0,P(x1)=y1,x2(x0,x1),求P(x2)；(4)计算定积分(1<a<b)；(5)解常微分方程初值问题解：

(1)Cramer法则,其中D=|A|,Dj为由b置换D的第j列所得。(2)根据求根公式得x*=2;(3)P(x2)=;(4)根据积分公式得到;(5)根据常微分方程求解公式得例1.2(难计算问题)(1)求解线性方程组AX=B,其中A为30阶可逆方阵，X=(x1,x2,,x30)T;(2)求超越方程xex=1在[0,1]上的根x*；(3)已知y=f(x)为[x0,x1]上的函数，满足f(x0)=y0,f(x1)=y1,x2(x0,x1),求f(x2)；(4)计算定积分(1<a<b)；(5)解常微分方程初值问题解：例1.2同例1.1“差不多”？(1)计算量非常大；(2)无法求得x*的解析形式，只能求近似值；(3)f(x2)

试试；(4)无法找到原函数，考虑近似方法；(5)没有解析解，数值解法求取近似解。利用计算机！但是…….计算机的认识能力是有限的

计算机的计算能力也是有限的可行且高效的算法+计算机！！！2数值算法的特点：

计算机算法对于给定的问题和设备（计算机），一个算法是用该设备可理解的语言表示的，对解决这个问题的一种方法的精确刻画。计算机算法主要包含数值算法、非数值算法和软计算方法三类。

三类计算机算法

数值算法主要指与连续数学模型有关的算法，如数值线性代数、方程求解、数值逼近、数值微积分、微分方程数值解和最优化计算方法等；(本课程内容)

非数值算法主要指与离散数学模型有关的算法，如排序、搜索、分类、图论算法等；软计算方法是近来发展的不确定性算法的总称，包括神经网络计算、模糊逻辑、遗传算法、蚂蚁算法等。

数值算法的特点有穷性

数值性

近似性

数值计算软件FortranC++Matlab§1.2误差分析的概念

误差限和有效数字

截断误差与收敛性

舍入误差和数值稳定性

数据误差和病态问题

1.误差限和有效数字误差和相对误差(定义1.1)

设x*是某量的准确值，x是x*的近似值称x=x*-x

为x的误差或绝对误差。|x*-x|,称为x的(绝对)误差限或精度，rx=(x*-x)/x*称为x的相对误差|(x*-x)/x*|

r,称

r为x的相对误差限。当

r

很小时，

r

/|x|。

误差的四则运算见后准确位数和有效数字(定义1.2)设x=0.a1a2an10m(m为整数)(1.1)其中a1~an为0~9中一个数字且a10。如果

|x*-x|0.510k(1.2)即x的误差不超过10-k位的半个单位则称近似数x准确到第k位小数，并说x有m+k位有效数字。

等价定义：如果近似值x的绝对误差限不超过它某一位的半个单位，则从这一位起，直到最左边的第一位非零数字为止的所有数字都称为有效数字。并说x“准确”到这一位。例1.3(误差限和有效数字)圆周率

=3.1415926。x1=3.14;x2=3.141;x3=3.142;x4=3.1414解(1)x1=0.314101,x1=0.15926102,|x1|0.5102,有3位有效数字；(2)x2=0.5926103,|x2|0.5102,有3位有效数字；(3)x3=0.4073103,|x3|0.5103,有4位有效数字；

(4)x4=0.1926103,|x4|0.5103,有4位有效数字。

有效数字概念的通俗定义

设x*是某量的准确值，x是x*的近似值，如果在从第一个非零数字开始的第n位进行四舍五入(即考虑第n+1位是舍还是入？)，x*和x的结果完全一致，则称x有n位有效数字。

与定义1.2的区别x*

未知，从而在数值分析中无法应用。按照通俗定义，

只有三位有效数字，但实际上的误差比的误差小，因此是的更好的近似值。通俗定义并不合理。2.截断误差与收敛性

截断误差：一个无限的数学极限过程用有限次运算近似计算产生的误差。

例（无限）近似计算（有限）截断误差（余项公式）在0与x之间

算法的收敛性：该算法总可以通过提高计算量使得截断误差任意小。即余项0

3.舍入误差和数值稳定性

舍入误差:由于机器字长的限制而产生的误差机器数(二进制0-1,离散)规格化浮点式:阶码m,字长t,尾数(1=1)2m0.12t,

m=12s

单精度32位(4字节):t=23,s=7,符号2位,表示范围

2.910393.41038(2-128

2128)双精度64位(8字节):t=52,s=10,符号2位,表示范围

5.56103091.7910308(2-1024

21024)上溢出和下溢出00数值稳定性误差传播问题:设函数y=f(x1,x2,,xn)是一个算法或模型，是变量xi的准确值，而是变量xi的近似值。如果,且f的计算过程中没有新的误差产生，那么计算结果具有怎样的精度？即算法的数值稳定:计算过程中舍入误差不会被严重放大误差的传播线性情形用严格估计非线性情形用线性近似绝对误差传播主要取决于条件数

相对传播主要取决于条件数

条件数很大病态问题误差的四则运算(ab)=ab,r(ab)=[a/(ab)]ra[b/(ab)]rb(相近数相减不稳定)(ab)

ba+abr(ab)

ra+rb(a/b)(1/b)a(a/b2)b(分母b0不稳定)r(a/b)

rarb例1.5(数值稳定性)

n=0,1,…,20估计算法一:分部积分递推公式In=1nIn-1,n=1,,20

I0=1-1/eI1I2…I20

误差很大(见书P8)

，n

=nn-1,20=(20!)0

，不稳定算法二：递推公式In-1=(1In)/n,n=20,,1I20估计式中点I19…I1I0

误差很小n-1

=n/n,0=20/(20!)，稳定4.数据误差和病态问题例1.6(病态问题)（保留4位有效数字）x1=x2=x3=1x1=1.1650,x2=0.0003,x3=2.0004.

病态问题:很小的变化数据却导致解产生了很大的变化。区别：收敛性和数值稳定性主要源于算法，病态性主要是模型本身的原因。§1.3数值算法设计的一些要点设计算法基本原则计算精度：收敛性、稳定性计算速度：计算量、收敛速度、多个CPU通信计算空间：存储量注意事项病态问题速度细节(加法、乘法，函数)计算多项式的值存储细节(降维)计算多项式的值稳定性细节(相近数相减，大数吃小数，分母接近0)死循环设置循环的上界。实数相等比较中间结果（要少显示和输出）速度细节使用秦九韶算法(Horner’srule)计算多项式的值可大大减少计算量直接计算，乘法的运算次数:n+(n-1)+…+1+0=n(n+1)/2乘的运算次数：n次算法过程设计可使用递推计算公式：

p0=an,

pk=pk-1x

+an-k(k=1,…,n)最后得到的p

即是多项式p(x)的值，算法过程只需n次乘法和n次加法，此算法称为秦九韶算法.

p=an,p=px

+an-k(k=1,…,n)存储细节求的小正根(取3位有效数字).

解只有一位有效数字.则具有3位有效数字.若改用由求根公式相近数相减大数吃小数1234+(0.4+0.3)=1235取4位有效数字计算：(1234+0.4)+0.3=1234问题：(x+y)+z