数值分析-计算方法.pptx

1、数 值 分 析,上海大学机自学院,第一章 绪 论1.1 课程主要内容 1、非线性方程数值解法 2、线性方程组的数值解法 3、插值方法 4、数值积分 5、常微分方程初值问题的数值解法,1.2 数值算法概论 数值算法是利用计算机求解数学问题近似解的方法，所获近似解也称为原问题的数值解或逼近解。,重点研究数值算法构造及其相关理论，包括误差分析，算法收敛性和稳定等。,实际问题,数学模型,构造数值算法,程序设计,获取近似解,数值算法，不仅仅是单纯的数学公式，而是指解题方案准确而完整的描述。,算法优劣主要取决于:1、计算开销2、误差控制,数值方法是一门与计算机应用密切结合的实用性很强的学科；思维方法是归纳

2、法，核心问题是“误差”或误差分析。数值方法这门课程讨论连续变量问题又要讨论离散变量问题，关心的是数值结果。数值分析、计算数学、计算方法或数值方法这门课程已成为近代数学的一个重要分支。,例1.1 多项式求值的秦九韶算法 P(x)=a0+a1x+a2x2+anxn,算法： 令 tk=xk uk=a0+a1x+akxk则得递推公式 tk=xtk-1 uk=uk-1+aktk 初值 t0=1 , u0=a0,(k=1,2,n),显然，由算法计算n次多项式P(x)值所需的乘法次数为2n 。,算法（秦九韶算法，我国宋代数学家） P(x)=a0+a1x+a2x2+anxn P(x)=a0+x (a1+a2x

3、+anxn-1) P(x)=a0+x (a1+x (a2+anxn-2) P(x)=a0+x (a1+x (an-1+anx) )显然，由里层往外一层一层的计算，仅需n次乘法运算，比算法节省一半的计算量。,秦九韶算法 令 (p=0) v0=an (p=1) v1=anx+an-1=v0x+an-1 (p=2) v2=(anx+an-1)x+an-2=v1x+an-2 (p=k) vk=vk-1x+an-k . (p=n) vn=vn-1x+a0,v0=an vk=vk-1x+an-k (k=1,2,n) P(x)=vn,例1.2 计算积分解：通过直接计算可产生如下递推公式 ， （1.1） 由经

4、典微积分知识可推得In具有如下性质(1) (2) 单调递减(3) (4)直接根据公式(1.1)，从n=1计算到n=30 。结果为,表1-1从n=18开始，计算值出现异常。原因是从第n-1步计算到第n步时，第n-1步的误差被放大了5倍。,算法改造：由性质(4)，取递推公式改写为 （1.2）从n=30计算到n=1。由于该算法每向后推进一步，其误差便减少5倍，可期望获得符合原积分性态的数值结果。计算结果见表1-2。,表1-2由此列可知，算法的设计十分重要，关系到计算结果是否真实可信。,1.3 误差 实际问题的求解过程中，一般会产生误差。误差的产生是正常的，不可避免的。,实际问题,数学模型,问题的解,

5、模型误差,观测误差,截断误差,舍入误差,本课程中，仅考虑数值计算过程所带来的误差，即截断误差和舍入误差。,截断误差 计算过程中，往往将解题方案加工成算术运算与逻辑运算的有限序列，这种加工过程常表现为无穷过程的截断，由此产生的误差称为截断误差。 ,用计算机计算 时，只能取有限项 截断误差为,舍入误差 计算过程中数据的位数可能很多，甚至为无穷小数，受计算机字长限制，用机器代码表示的数据必须舍入成一定的位数，由此产生的误差称为舍入误差。,定义1.1 设 是某量的精确值，是其近似值，则称差= 为的绝对误差。 一般而言， 未知，直接确定e是困难的，常用|e|表征绝对误差， 称为绝对误差限。,定义1.2

6、在定义1.1的假设条件下，称比值=/ 为近似值得相对误差。 通常用|er|r表征相对误差， r称为相对误差限。因 未知，常用=/表示相对误差。,通常近似值的精度用所谓有效数字位数来表征，即近似值 的绝对误差限是它某一位的半个单位，则称该近似值“准确”到这一位，且这一位直到前面第一个非零数字为止的所有数字均为有效数字。,如圆周率的近似值为=3.142，其绝对误差限为 | -|=0.0004070.0005=(0.5) 101-4则近似值有4位有效数字，近似值准确到小数点后第3位。,小数点后第3位半个单位,定义1.3 若 的近似值=0.12 10m，其中1 0，诸 0,1,2,9，为整数，且 |-

7、 | (0.5) 10 ，1 则称近似值有位有效数字或称准确到 10 位。,定理1.1 设近似值=0.12 10m有位有效数字，则其相对误差限为 =(1/21) 10 +1,定理1.2 设近似值=0.12 10m的相对误差限为 =(1/2(1+1) 10 +1 ，则近似值有位有效数字。,证明：定理1.1因为=0.12 10 ，故有 1 10 1 ( 1 +1) 10 1 当有位有效数字时 = 0.5 10 1 10 1 = 1 2 1 10 +1 定理1.2 ( 1 +1) 10 1 1 2 1 +1 10 +1 = 1 2 10 所以有位有效数字,例1.3 下列近似值有几位有效数字，其相对误

8、差是多少？（1） =，=2.71828（2） =0.030021，=0.0300解：（1） =2.7182818284 =0.0000018 1 2 10 16 近似值=2.71828有6位有效数字 （2） =0.0000210， 的相对误差为，求ln的绝对误差。 例1.6 设的相对误差为2%，求 的相对误差。,对多元函数 1 , 2 , ，若自变量的准确值 1 , 2 , , 近似值为 1 , 2 , 取多元函数 1 , 2 , 的Taylor展式的一阶项，得多元函数绝对误差及相对误差的估计式 = =1 1 , 2 , = =1 1 , 2 , 1 , 2 , ,四则运算的绝对误差估计式 1

9、 2 = 1 + 2 1 2 = 2 1 + 1 2 1 2 = 2 1 + 1 2 2 2 , 2 0,误差对计算结果的影响：例1.7 用中心差商公式求f(x)= 在x=2的导数：理论上，步长h愈小，计算结果愈准确。假定受计算机字长限制，只能取5位有效数字，于是 h=0.1 h=0.0001,4位有效数字,例1.8 考察如下病态方程组 准确解为： x1=x2=x3=1若将系数舍入成3位有效数字，则有其解为x1=1.09，x2=0.488，x3=1.49系数改变不大，但近似解与精确解出入太大。,1.4 避免误差扩大的几个常用原则 1、简化计算步骤，减少运算次数 2、避免两个相近数相减，导致有效

10、数字损失 a1=0.12345,a2=0.12346 a2-a1=0.00001 仅剩一位有效数字 解决方法 （1） （2） ， （3） ，,3、避免小数做除数，放大误差4、注意运算次序，防止大数“吃掉”小数 a=1234578，0bi1 ，i=1,2,100 在具有8位浮点数的计算机上，计算 a+b1+b2+ +b100 如果从左依次做加法运算，则有 a+b1=a， (a+b1)+b2=a+b2=a, a+b1+b2+ +b100=a 这里bi1被当作数值0 正确方法 先计算 =1 100 再与求和,1.5 化粗为精的松弛方法 1、松弛法 设F0与F1为准确值F*的两个近似值 取F0与F1的

11、加权平均作为新的近似值 =(1-)F0+F1 权系数01称为松弛因子 2、超松弛法 如果F0与F1有优劣之分，譬如F0为劣F1为优 =(1+)F1-F0=F1+(F1-F0),割圆术阿基米德 3.14祖冲之 3.1415926 3.1415927 祖冲之之前的刘徽从计算圆内正6边形面积S6开始一直计算到圆内正192边形面积S192，圆半径r=10，其中 S96=313 584 625 ， S192=314 64 625 换算成圆周率后分别约为3.14利用超松弛法，取= 36 105, =S192+ 36 105 (S192-S96)=314 4 25 该结果相当于圆内正3072边形的面积，换算

12、成圆周率，得 3.1416比阿基米德的圆周率精度提高了两个数量级 如果取= 1 3 ，则可得圆周率 3.14159265相当于计算到圆内正24576边形面积,1.6 向量范数与矩阵范数定义1.4 称n维实空间 上的一个非负函数 为范数，若其满足（1） 当且仅当（2） ， 及（3） ， 。 对于一维实空间R而言， 即为绝对值 。对于n维向量，将主要涉及lp(p =1,2,)范数： ，,特别，l范数为 。定理1.3 若 与 为Rn上的任意两种范数，则存在正常数C2C1使得 ， 。定义1.5 设有向量序列X(k)Rn|X(k)=( , , T ,若 ，i=1,2,n则称序列X(k)收敛域向量X =(

13、x1,x2,xn)T 。,定理1.4 在空间Rn中，序列X(k)收敛于向量X的充要条件是存在范数 ，使得定义1.6 设A为n阶方阵， 为Rn中的某范数，则称 为矩阵A的从属于向量范数的范数，记作 。,矩阵范数的性质：（1）对任意n阶方阵A有 ，且 当且仅当A=0；（2）对任意实数k及任意n阶方阵A，有 ；（3）对任意两个n阶方阵A，有 ， ；（4）对 及任意n阶方阵A，有 性质（4）称为矩阵A及向量X的相容性。,定理1.5 设有n阶方阵A=(aij)，则与l1，l2，l范数相容的矩阵范数分别为 其中 为矩阵的谱半径，其满足 为方阵B的特征值。定理1.6 A为n阶方阵，则,定理1.7 ， lim =0 的充要条件是 1。,