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

1、于佳平东华大学Email： 教材 数值分析及其MATLAB实验 姜健飞 吴笑千 胡良剑编 每周五每周五 8:15-9:45 第二教学楼第二教学楼129室室 每个单每个单周五周五 10:05-11:35 图文图文3号机房号机房 (图文图文信息中心信息中心) 请按机号入座！请按机号入座！ 笔试考试：笔试考试：70% 70% 闭卷闭卷 上机考试：上机考试：20% 20% 平时成绩：平时成绩：10% 10% 作业：双周上课前交到讲台上作业：双周上课前交到讲台上 上机作业要在上机时检查上机作业要在上机时检查 答疑：答疑：1 1）课前或课后）课前或课后 2 2）2 2号学院楼号学院楼449449室室 67

2、792331 67792331 3 3）1.1 数值算法的研究对象 1.2 误差分析的概念1.3 数值算法设计的一些要点 数学分析、高等代数、概率论与数理统计都是精确数学分析、高等代数、概率论与数理统计都是精确数学，例如极限、导数、积分都是唯一的。数学，例如极限、导数、积分都是唯一的。 数值分析不同，我们面对的问题是理论上有解的，数值分析不同，我们面对的问题是理论上有解的，但我们没有求解公式；另外一种情况，计算量过大，但我们没有求解公式；另外一种情况，计算量过大，我们手工难以实现的。这样的一类问题，实际上都我们手工难以实现的。这样的一类问题，实际上都是无限的，但我们只能取有限项求解，因此得到的

3、是无限的，但我们只能取有限项求解，因此得到的是近似解。是近似解。 近似解就有个近似程度，这个解就不是唯一的了，近似解就有个近似程度，这个解就不是唯一的了，精确度不同，解就不同，距离真解误差越小越好。精确度不同，解就不同，距离真解误差越小越好。实际问题数学模型数值分析理论程序设计上机计算 计算的目的不在于数据，而在于洞察事物。 理查德哈明 The purpose of computing is insight，not numbers. Richard Wesley Hamming地球外部大气流动模型 应用：大数据搜索、金融、核实验、飞行器、应用：大数据搜索、金融、核实验、飞行器、油田勘探、天气预

4、报油田勘探、天气预报 .飞机外形优化设计问题 掌握各种解决数学问题的数值方法掌握各种解决数学问题的数值方法 对近似解进行评估对近似解进行评估 在计算机上实现求解在计算机上实现求解 仿真模拟仿真模拟(1) 求解线性方程组求解线性方程组AX=b, 其中其中A为为3阶可逆方阶可逆方阵，阵，X=(x1, x2, x3)T;(2) 求代数方程求代数方程x2+x 6=0在在0,4上的根上的根x*；(3) 已知已知y=P(x)为为x0, x1上的直线，满足上的直线，满足P(x0)=y0, P(x1)=y1, x2 (x0, x1), 求求P(x2)；(4) 计算定积分计算定积分 (1ab)；(5) 解常微分

5、方程初值问题解常微分方程初值问题 1baIdxx 00( )yxy(1) Cramer法则法则 , 其中其中D=|A|, Dj为由为由b置换置换D的第的第j列所得。列所得。 (2)根据求根公式得根据求根公式得x*=2;(3) P(x2)= ;(4) 根据积分公式得到根据积分公式得到 ;(5) 根据常微分方程求解公式得根据常微分方程求解公式得,1,2,3jjDxjD1002010()yyyxxxx lnbIa212( )y xx(1) 求解线性方程组求解线性方程组AX=B, 其中其中A为为30阶可逆方阶可逆方阵，阵，X=(x1, x2, x30)T;(2) 求超越方程求超越方程xex =1在在0

6、,1上的根上的根x*；(3) 已知已知y=f(x)为为x0, x1上的函数，满足上的函数，满足f(x0)=y0, f(x1)=y1, x2 (x0, x1), 求求f(x2)；(4) 计算定积分计算定积分 (1ab)；(5) 解常微分方程初值问题解常微分方程初值问题 1lnbaIdxx( )200yxyy (1) 计算量非常大，计算量非常大，3130！29次乘法；次乘法；(2) 无法求得无法求得x*的解析形式，只能求近似值；的解析形式，只能求近似值；(3) f(x2) 试试；试试；(4) 无法找到原函数，考虑近似方法；无法找到原函数，考虑近似方法；(5) 没有解析解，数值解法求取近似解。没有解

7、析解，数值解法求取近似解。1002010()yyyxxxx 计算机的认识能力是有限的计算机的认识能力是有限的 （例如（例如C语言不语言不能识别能识别“积分积分”） 计算机的计算能力也是有限的（例如例计算机的计算能力也是有限的（例如例2(1),2(1),超级计算机超级计算机“天河二号天河二号”每秒做每秒做33.8633.86千万亿千万亿次乘法，也需要次乘法，也需要591591亿年）亿年）解决方案：解决方案： 计算机算法计算机算法对于给定的问题和设备（计算机），一个算法对于给定的问题和设备（计算机），一个算法是用该设备可理解的语言表示的，对解决这个问是用该设备可理解的语言表示的，对解决这个问题的一

8、种方法的精确刻画。题的一种方法的精确刻画。计算机算法主要包含计算机算法主要包含数值算法、非数值算法数值算法、非数值算法和和软计算方法软计算方法三类。三类。 Fortran C+Matlab 数值算法数值算法主要指与连续数学模型有关的算法，主要指与连续数学模型有关的算法，如数值线性代数、方程求解、数值逼近、数如数值线性代数、方程求解、数值逼近、数值微积分、微分方程数值解和最优化计算方值微积分、微分方程数值解和最优化计算方法等；法等；( (本课程内容本课程内容) ) 非数值算法非数值算法主要指与离散数学模型有关的算主要指与离散数学模型有关的算法，如排序、搜索、分类、图论算法等；法，如排序、搜索、分

9、类、图论算法等； 软计算方法软计算方法是近来发展的不确定性算法的总是近来发展的不确定性算法的总称，包括神经网络计算、模糊逻辑、遗传算称，包括神经网络计算、模糊逻辑、遗传算法、蚂蚁算法等。法、蚂蚁算法等。 有穷性有穷性 数值性数值性 近似性近似性 误差限和有效数字误差限和有效数字 截断误差与收敛性截断误差与收敛性 舍入误差和数值稳定性舍入误差和数值稳定性 数据误差和病态问题数据误差和病态问题 误差和相对误差误差和相对误差(定义定义1.1) 设设x*是某量的准确值，是某量的准确值，x是是x*的近似值的近似值称称 x = x*-x 为为x的的误差误差或或绝对误差绝对误差。 | x*-x | , 称称

10、 为为x的的(绝对绝对)误差限误差限或或精度精度， rx = (x*-x)/x*称为称为x的的相对误差相对误差 |(x*- x)/ x *| r, 称称 r为为x的的相对误差限相对误差限。当当 r 很小时，很小时， r /| x |。 误差的四则运算见后误差的四则运算见后 准确位数和有效数字准确位数和有效数字(定义定义1.2)设设x = 0.a1 a 2an 10m (m为整数为整数) (1.1)其中其中a 1an为为09中一个数字且中一个数字且a 1 0。如果如果 | x*-x| 0.5 10 k (1.2)即即x的误差不超过的误差不超过10-k位的位的单位单位则称近似数则称近似数x准确到第

11、准确到第k位小数位小数，并说，并说x有有m+k位位有效数字有效数字。 等价定义：如果近似值等价定义：如果近似值x的绝对误差限不超过它某一位的半个的绝对误差限不超过它某一位的半个单位，则从这一位起，直到最左边的第一位非零数字为止的单位，则从这一位起，直到最左边的第一位非零数字为止的所有数字都称为所有数字都称为有效数字有效数字。并说。并说x“准确准确”到这一位。到这一位。圆周率圆周率 =3.1415926。x1=3.14; x 2=3.141; x 3=3.142; x 4=3.1414解解(1) x1=0.314 101 , x1=0.1592610 2, | x1| 0.5 10 2,有有3位

12、有效数字；位有效数字；(2) x2=0.592610 3, |x2| 0.5 10 2,有有3位位有效数字；有效数字；(3) x3= 0.407310 3, | x3| 0.5 10 3,有有4位有效数字；位有效数字； (4) x4=0.192610 3, |x4| 0.5 10 3, 有有4位有效数字。位有效数字。 设设x*是某量的准确值，是某量的准确值，x是是x*的近似值，如果的近似值，如果在从第一个非零数字开始的第在从第一个非零数字开始的第n位进行四舍位进行四舍五入五入( (即考虑第即考虑第n+1n+1位是舍还是入？位是舍还是入？) )，x*和和x的结果完全一致，则称的结果完全一致，则称

13、x有有n位有效数字。位有效数字。 与定义与定义1.2的区别的区别 x* 未知，从而在数值分析中无法应用。按照通俗定义，未知，从而在数值分析中无法应用。按照通俗定义， 只只有三位有效数字，但实际上有三位有效数字，但实际上 的误差比的误差比 的误差小，因此的误差小，因此是是 的更好的近似值。的更好的近似值。通俗定义并不合理。通俗定义并不合理。*343.1415926, 3.142, .,3 1414xxx 截断误差截断误差：一个无限的数学极限过程用有限次运算一个无限的数学极限过程用有限次运算近似计算产生的误差。近似计算产生的误差。 例（无限）例（无限） 近似计算（近似计算（有限有限） 截断误差（余

14、项公式）截断误差（余项公式） 在在0与与x之间之间 212!nxxxexn 2( )12!nxnxxeSxxn 1( )( )(1)!nxnnxeSxRxen 算法的算法的收敛性收敛性：该算法总可以通过提高计算该算法总可以通过提高计算量使得截断误差任意小。即量使得截断误差任意小。即 余项余项0 0 舍入误差舍入误差: 由于机器字长的限制而产生的误差由于机器字长的限制而产生的误差 机器数机器数( (二进制二进制0-1,0-1,离散离散) ) 规格化浮点式规格化浮点式: : 阶码阶码m m（用二进制数表示）（用二进制数表示）, ,字长字长t ,t ,尾数尾数 ( ( 1 1=1)=1) 2 2m

15、m 0.0. 1 1 2 2 t t, , m=m=1 1 2 2s s 单精度单精度3232位位(4(4字节字节): t=23,s=7, ): t=23,s=7, 符号符号2 2位位, , 表示范表示范围围 2.9 2.9 1010 3939 3.43.4 10103838 (2 (2-128 -128 2 2128128) ) 双精度双精度6464位位(8(8字节字节) : t=52,s=10, ) : t=52,s=10, 符号符号2 2位位, ,表示表示范围范围 5.56 5.56 1010 309309 1.791.79 1010308308 (2 (2-1024 -1024 2 2

16、10241024) ) 上溢出上溢出和下溢出和下溢出0 00 误差传播问题误差传播问题: 设函数设函数y=f(x1, x2, , xn)是一是一个算法或模型，个算法或模型， 是变量是变量xi的准确值，而的准确值，而 是变量是变量xi的近似值。如果的近似值。如果 , 且且f的计算过程中没有新的误差产生，那么计的计算过程中没有新的误差产生，那么计算结果算结果 具有怎样的精度？具有怎样的精度？即即*ixix *| |iiiixxx12( ,)nyf x xx*1212| |(,)(,)| ?nnyf xxxf x xx算法的数值稳定算法的数值稳定: 计算过程中舍入误差不计算过程中舍入误差不会被严重放

17、大会被严重放大 线性情形用严格估计线性情形用严格估计 非线性情形用线性近似非线性情形用线性近似 绝对误差传播主要取决于绝对误差传播主要取决于条件数条件数 相对传播主要取决于相对传播主要取决于条件数条件数 条件数很大条件数很大 病态问题病态问题 *12121| |(,)(,)|nnniiiyf xxxf xxxa *1(),niiifyxx *1( )()()nirriiixfyxxy *|() |ifx *|()|iixfxy (a b)= a b, r(a b)= a/(a b) ra b/(a b) rb(相近数相减相近数相减不稳定不稳定) (ab) b a+a b r(ab) ra+ r

18、b (a/b) (1/b) a (a/b2) b (分母分母b 0不稳定不稳定) r(a/b) rarb计算误差限计算误差限: 例如：例如：| ()| | ?abab | ()| | ?abb aa b n=0, 1, , 20 估计估计 110,nxnIx edx 11(1)1nInen 算法一算法一: 分部积分分部积分递推公式递推公式 In=1 nIn-1, n=1,20 I0=1-1/e I1 I2 I20 误差很大误差很大(见书见书P8) ， n = n n-1, 20 =(20!) 0 ，不稳定，不稳定算法二：递推公式算法二：递推公式 In-1=(1 In)/n, n= 20 ,1I

19、20 估计式中点估计式中点 I19 I1 I0 误差很小误差很小 n-1 = n /n, 0 = 20 /(20!)，稳定，稳定*11,nnInI 例例1.6 (病态问题病态问题)（保留（保留4位有效数字）位有效数字） x1=x2=x3=1 x1=1.2203, x2= -0.3084, x3= 2.2981. 病态问题病态问题: 很小的变化数据却导致解产生了很大的很小的变化数据却导致解产生了很大的变化。变化。 区别：收敛性和数值稳定性主要源于算法，区别：收敛性和数值稳定性主要源于算法，病态性病态性主要是模型本身的原因主要是模型本身的原因 。 1231231234932194936440360

20、361310614144107202137693739401036003600 xxxxxxxxx 1231231230.75000.52502.6360.75000.42360.1.3630001.4740.52500.30000.21361 031.9xxxxxxxxx 设计算法基本原则设计算法基本原则 计算精度：收敛性、稳定性计算精度：收敛性、稳定性 计算速度：计算量、收敛速度、多个计算速度：计算量、收敛速度、多个CPU通信通信 计算空间：存储量计算空间：存储量 注意事项注意事项 病态问题病态问题 速度细节速度细节(加法、乘法，函数加法、乘法，函数) 计算多项式的值计算多项式的值 存储细

21、节存储细节(降维降维) 计算多项式的值计算多项式的值 稳定性细节稳定性细节(相近数相减相近数相减(例例)，大数吃小数，大数吃小数(例例)，分母接近分母接近0 (例例) ) 死循环死循环 设置循环的上界。设置循环的上界。 实数相等比较实数相等比较 中间结果（要少显示和输出）中间结果（要少显示和输出）速度细节速度细节使用秦九韶算法(Horners rule)0111)(axaxaxaxpnnnn 0121)()(axaxaxaxaxpnnn 计算多项式的值可大大减少计算量直接计算，乘法的运算次数: n+(n-1)+1+0=n(n+1)/2乘的运算次数：n次算法过程设计可使用递推计算公式：算法过程设

22、计可使用递推计算公式： p0=an, pk=pk-1x + an-k ( k =1,n)最后得到的最后得到的 p 即是多项式即是多项式 p(x) 的值，算法过程只需的值，算法过程只需n次乘法次乘法和和n次加法，此算法称为秦九韶算法次加法，此算法称为秦九韶算法.0121)()(axaxaxaxaxpnnn p=an, p=px + an-k ( k =1,n)存储细节存储细节求求 的小正根的小正根( (取取3 3位有效数字位有效数字). ). 21610 xx 解解1863 ,x 只有一位有效数字只有一位有效数字. . *2x2863x 则具有则具有3 3位有效数字位有效数字. . 若改用若改用由求根公式由求根公式2863x *287.940.06,x (863 )(863 )110.062715.94863863 相近数相减相近数相减 20.06274606680622 8.,x 精精确确值值大数吃小数大数吃小数 1234 +