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

数值分析

NumericalAnalysis于佳平东华大学Email：jpyu@教材《数值分析及其MATLAB实验》

姜健飞

吴笑千

胡良剑编

上课(2--17周)每周五8:15-9:45第二教学楼129室每个单周五10:05-11:35图文3号机房(图文信息中心)请按机号入座！成绩的评定方法笔试考试：70%闭卷上机考试：20%平时成绩：10%作业和答疑作业：双周上课前交到讲台上

上机作业要在上机时检查答疑：1）课前或课后2）2号学院楼449室677923313）jpyu@第一章

数值分析的基本概念

§1.1数值算法的研究对象

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

§1.1数值算法的研究对象研究对象数学分析、高等代数、概率论与数理统计都是精确数学，例如极限、导数、积分都是唯一的。数值分析不同，我们面对的问题是理论上有解的，但我们没有求解公式；另外一种情况，计算量过大，我们手工难以实现的。这样的一类问题，实际上都是无限的，但我们只能取有限项求解，因此得到的是近似解。近似解就有个近似程度，这个解就不是唯一的了，精确度不同，解就不同，距离真解误差越小越好。研究过程

（理论上有解，而无求解公式或计算量过大难以用手工实现的数学问题）实际问题数学模型数值分析理论程序设计上机计算重点内容研究并求解数学问题的数值（近似）解的方法计算的目的不在于数据，而在于洞察事物。

－－理查德·哈明Thepurposeofcomputingisinsight，notnumbers.

－－Richard

Wesley

Hamming

理论分析

科学实验

科学计算地球外部大气流动模型应用：大数据搜索、金融、核实验、飞行器、油田勘探、天气预报......飞机外形优化设计问题数值分析课程的期望掌握各种解决数学问题的数值方法对近似解进行评估在计算机上实现求解仿真模拟1.例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)计算量非常大，31＊30！＊29次乘法；(2)无法求得x*的解析形式，只能求近似值；(3)f(x2)

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

（例如C语言不能识别“积分”）计算机的计算能力也是有限的（例如例2(1),超级计算机“天河二号”每秒做33.86千万亿次乘法，也需要591亿年）解决方案：可行且高效的算法+计算机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.2203,x2=-0.3084,x3=2.2981.

病态问题:很小的变化数据却导致解产生了很大的变化。区别：收敛性和数值稳定性主要源于算法，病态性主要是模型本身的原因

。§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位有效数字.