第1章数值计算绪论及误差.ppt

数数 值值 分分 析析Numerical Analysis主讲教师：主讲教师：邹昌文邹昌文 E-mail:绪论及误差绪论及误差 在数学发展中，理论和计算是紧密联系的。现代计算机在数学发展中，理论和计算是紧密联系的。现代计算机的出现为大规模的数值计算创造了条件，集中而系统的研究的出现为大规模的数值计算创造了条件，集中而系统的研究适用于计算机的数值方法变得十分迫切和必要。数值计算方适用于计算机的数值方法变得十分迫切和必要。数值计算方法正是在大量的数值计算实践和理论分析工作的基础上发展法正是在大量的数值计算实践和理论分析工作的基础上发展起来的，它不仅仅是一些数值方法的简单积累，而且揭示了起来的，它不仅仅是一些数值方法的简单积累，而且揭示了包含在多种多样的数值方法之间的相同的结构和统一的原理。包含在多种多样的数值方法之间的相同的结构和统一的原理。数值算法是进行科学计算必不可缺少的起码常识；更为重要数值算法是进行科学计算必不可缺少的起码常识；更为重要的是通过对它们的讨论，能够使人们掌握设计数值算法的基的是通过对它们的讨论，能够使人们掌握设计数值算法的基本方法和一般原理，为在计算机上解决科学计算问题打下基本方法和一般原理，为在计算机上解决科学计算问题打下基础。础。1.1.认识所建立算法和对每个算法进行理论分析是基认识所建立算法和对每个算法进行理论分析是基 本任务，主动适应本任务，主动适应“公式多公式多”的特点；的特点；2.2.注重各章建立算法的问题的提法，搞清问题的基注重各章建立算法的问题的提法，搞清问题的基 本提法，逐步深入；本提法，逐步深入；3.3.理解每个算法建立的数学背景，数学原理和基本理解每个算法建立的数学背景，数学原理和基本 线索，对最基本的算法要非常熟悉；线索，对最基本的算法要非常熟悉；4.4.认真进行数值计算的训练，学习各章算法完全是认真进行数值计算的训练，学习各章算法完全是 为用于实际计算，必须真会算。为用于实际计算，必须真会算。记好课堂笔记记好课堂笔记 保证课堂纪律保证课堂纪律 按时完成作业按时完成作业 按时上课，不迟到早退按时上课，不迟到早退几几 点点 要要 求求如何把数学模型归结为数值问题如何把数学模型归结为数值问题如何制定快速的算法如何制定快速的算法如何估计一个给定算法的精度如何估计一个给定算法的精度分析误差在计算过程中的积累和传播分析误差在计算过程中的积累和传播如何构造精度更高的算法如何构造精度更高的算法如何使算法较少的占用存储量如何使算法较少的占用存储量如何分析算法的优缺点如何分析算法的优缺点数值分析讲述的基本内容数值分析讲述的基本内容数值分析研究对象与特点数值分析研究对象与特点对象对象实际问题实际问题数学化数学化数字化数字化程序化程序化特点特点面向计算机面向计算机可靠性分析可靠性分析好的计算复杂性好的计算复杂性有数值实验有数值实验数值分析的研究方法数值分析的研究方法-构造法构造法数值分析课程主要讨论如何构造求数学模型近数值分析课程主要讨论如何构造求数学模型近似解的算法，讨论算法的数学原理、误差和复似解的算法，讨论算法的数学原理、误差和复杂性，配合程序设计进行计算试验并分析试验杂性，配合程序设计进行计算试验并分析试验结果。结果。与纯数学的理论方法不同，用数值计算方法所与纯数学的理论方法不同，用数值计算方法所求出的结果一般不是解的精确值或者准确的解求出的结果一般不是解的精确值或者准确的解析表达式，而是所求真解的某些近似值或近似析表达式，而是所求真解的某些近似值或近似曲线。曲线。数值分析 例如方程例如方程 x x2 2=2sinx=2sinx，在区间，在区间(1,2)(1,2)内有唯一根内有唯一根,但找不出求根的解析式但找不出求根的解析式,只能用数值计算方法求其只能用数值计算方法求其近似解。有些数学问题虽有理论上的准确的公式解近似解。有些数学问题虽有理论上的准确的公式解,但不一定实用但不一定实用,例如行列式解法的例如行列式解法的CramerCramer法则原法则原则上可用来求解线性方程组则上可用来求解线性方程组,用这种方法解一个用这种方法解一个n n元元方程组方程组,要算要算n+1n+1个个n n阶行列式的值阶行列式的值,总共需要总共需要n!(n-n!(n-1)(n+1)1)(n+1)次乘法次乘法,当当n=20n=20时时,其乘除法运算次数约需其乘除法运算次数约需10102121次方次方,即使用每秒千亿次的计算机也得需要上百即使用每秒千亿次的计算机也得需要上百年年,而用高斯（而用高斯（GuassGuass）消去法约需）消去法约需26602660次乘除法运次乘除法运算算,并且愈大并且愈大,相差就愈大。可见研究和选择好的算相差就愈大。可见研究和选择好的算法是非常重要的。法是非常重要的。算法算法(数值算法数值算法):):是指有步骤地完成解数值问题是指有步骤地完成解数值问题的过程。的过程。数值算法的特点数值算法的特点 目的性，条件和结论、输入和输出数据均目的性，条件和结论、输入和输出数据均要有明确的规定与要求。要有明确的规定与要求。确定性，精确地给出每一步的操作确定性，精确地给出每一步的操作(不一不一定都是运算定都是运算)定义定义,不容许有歧义。不容许有歧义。可执行性，算法中的每个操作都是可执行可执行性，算法中的每个操作都是可执行的的 有穷性，在有限步内能够结束解题过程有穷性，在有限步内能够结束解题过程总之：必须是构造性的数值方法总之：必须是构造性的数值方法构造算法的途径构造算法的途径迭代法迭代法离散法离散法离散问题解析化法离散问题解析化法外推法外推法误差误差/Error/Error/误差来源与分类误差来源与分类/Source&Classification/Source&Classification/从实际问题中抽象出数学模型从实际问题中抽象出数学模型 模型误差模型误差 /Modeling Error/Modeling Error/通过测量得到模型中参数的值通过测量得到模型中参数的值 观测误差观测误差 /Measurement Error/Measurement Error/求近似解求近似解 方法误差方法误差 (截断误差截断误差 /Truncation Error/Truncation Error/)机器字长有限机器字长有限 舍入误差舍入误差 /Roundoff Error/Roundoff Error/用数学方法解决一个具体的实际问题，首先要建立用数学方法解决一个具体的实际问题，首先要建立数学模型，这就要对实际问题进行抽象、简化，因数学模型，这就要对实际问题进行抽象、简化，因而数学模型本身总含有误差，这种误差叫做模型误而数学模型本身总含有误差，这种误差叫做模型误差，例自由落体差，例自由落体数学模型是指那些利用数学语言模拟现实而建立起数学模型是指那些利用数学语言模拟现实而建立起来的有关量的描述，数学模型的准确解与实际问题来的有关量的描述，数学模型的准确解与实际问题的真解不同的真解不同实际问题的真解数学模型的真解为减化模型忽略次要为减化模型忽略次要因素因素定理在特定条件下建立与实定理在特定条件下建立与实际条件有别际条件有别模型误差模型误差忽略了空气阻力忽略了空气阻力在数学模型中通常包含各种各样的参变量，如在数学模型中通常包含各种各样的参变量，如温度、长度、电压等，这些参数往往是通过观温度、长度、电压等，这些参数往往是通过观测得到的，因此也带来了误差，这种误差叫观测得到的，因此也带来了误差，这种误差叫观测误差，例重力加速度测误差，例重力加速度数学模型中的参数和原始数据，是由观测和试数学模型中的参数和原始数据，是由观测和试验得到的验得到的由于测量工具的精度、观测方法或客观条件的由于测量工具的精度、观测方法或客观条件的限制限制,使数据含有测量误差使数据含有测量误差,这类误差叫做观测这类误差叫做观测误差或数据误差误差或数据误差数值方法中需要了解观测误差数值方法中需要了解观测误差,以便选择合理以便选择合理的数值方法与之适应的数值方法与之适应观测观测误差误差精确公式用近似公式代替时精确公式用近似公式代替时,所产生的误差叫所产生的误差叫截断误差截断误差例如例如,函数函数f(x)f(x)用泰勒用泰勒(Taylor)(Taylor)多多项式项式（介于介于0 0与与x x之间）之间）近似代替，则数值方法的截断误差是近似代替，则数值方法的截断误差是截断误差的大小直接影响计算结果的精度和计算工作截断误差的大小直接影响计算结果的精度和计算工作量，量，是数值计算中必须考虑的一类误差是数值计算中必须考虑的一类误差截断误差截断误差 在数值计算中只能对有限位字长的数值进行在数值计算中只能对有限位字长的数值进行运算运算需要对参数、中间结果、最终结果作有限位需要对参数、中间结果、最终结果作有限位字长的处理工作，这种处理工作称作舍入处字长的处理工作，这种处理工作称作舍入处理理用有限位数字代替精确数，这种误差叫做用有限位数字代替精确数，这种误差叫做舍舍入误差入误差，是数值计算中必须考虑的一类误差，是数值计算中必须考虑的一类误差舍入误差舍入误差例如用例如用3.141593.14159近似代替近似代替 上述种种误差都会影响计算结果的上述种种误差都会影响计算结果的准确性，因此需要了解与研究误差，在数准确性，因此需要了解与研究误差，在数值计算中将着重研究截断误差、舍入误差，值计算中将着重研究截断误差、舍入误差，并对它们的传播与积累作出分析并对它们的传播与积累作出分析小结小结误差与有效数字误差与有效数字定义：设定义：设x x为准确值，为准确值，x x*为为x x的一个近似值，的一个近似值，称称e e*=x=x*-x-x为近似值的绝对误差为近似值的绝对误差绝对误差限绝对误差限即即比较精度比较精度相对误差相对误差相对误差限相对误差限注：从注：从注：从注：从 的定义可见，的定义可见，的定义可见，的定义可见，实际上被偷换成了实际上被偷换成了实际上被偷换成了实际上被偷换成了 ，而后才考察，而后才考察，而后才考察，而后才考察其上限。那么这样的偷换是否合法？其上限。那么这样的偷换是否合法？其上限。那么这样的偷换是否合法？其上限。那么这样的偷换是否合法？严格的说法是，严格的说法是，严格的说法是，严格的说法是，与与与与 是否反映了同一数量级的误差？是否反映了同一数量级的误差？是否反映了同一数量级的误差？是否反映了同一数量级的误差？关于此问题的详细讨论可见教材第关于此问题的详细讨论可见教材第关于此问题的详细讨论可见教材第关于此问题的详细讨论可见教材第5 5 5 5页。页。页。页。有效数字的定义有效数字的定义设设x x*为准确值为准确值x x的一个近似值，且的一个近似值，且x x*的左边第一的左边第一个非零数字到末位数字共有个非零数字到末位数字共有n n位，即位，即x x*可表示为可表示为其中其中m m为整数，为整数，a a1 1取取1-91-9中某整数，中某整数，a a2 2,a,a3 3,a an n取取0-90-9中某整数中某整数.若若x x*的绝对误差限不超过其末的绝对误差限不超过其末位数的半个单位即位数的半个单位即则称则称x x*的这的这n n位数字都是有效数字，并称位数字都是有效数字，并称x x*具具有有n n位有效数字位有效数字例例求求pipi的三位、五位、八位有效数字的三位、五位、八位有效数字三位三位3.143.14五位五位3.14163.1416八位八位3.14159273.1415927 用用四舍五入取准确值的前四舍五入取准确值的前n n位位x x*作为近似值作为近似值,则则 x x*必有必有n n位有效数字。如位有效数字。如3.1423.142作为作为 的近似值的近似值 有有4 4位有效数字，而位有效数字，而3.1413.141为为3 3位有效数字位有效数字 有效数字相同的两个近似数，绝对误差不一定有效数字相同的两个近似数，绝对误差不一定 相同。例如，设相同。例如，设x x1 1*=12345,=12345,设设x x2 2*=12.345,=12.345,两者两者 均有均有5 5位有效数字但绝对误差不一样位有效数字但绝对误差不一样 x-xx-x1 1*=x-12345x-12345 0.5=1/2 0.5=1/2 10 100 0 x-xx-x2 2*=x-12.345x-12.345 0.0005=1/20.0005=1/2 1010-3-3 把任何数乘以把任何数乘以1010p p(p=0,(p=0,1,1,)不影响有效位数不影响有效位数 准确值具有无穷多位有效数字准确值具有无穷多位有效数字,如三角形面积如三角形面积 S=1/2ah=0.5ah S=1/2ah=0.5ah 因为因为0.50.5是真值是真值,没有误差没有误差 *=0,=0,因此因此n n,准确值具有无穷位有效数字准确值具有无穷位有效数字关于有效数字说明关于有效数字说明有效数字与误差的关系有效数字与误差的关系绝对误差限与有效数字的关系绝对误差限与有效数字的关系有效数字与相对误差限的关系有效数字与相对误差限的关系定理定理1 1：有：有n n位有效数字的近似值位有效数字的近似值x x*，则其，则其相对误差满足不等式相对误差满足不等式反之若反之若则则x x*至少有至少有n n位有效数字位有效数字例例1 1 已知近似数已知近似数x x*的相对误差限为的相对误差限为0.3%0.3%，问，问x x*有几有几位有效数字？位有效数字？得得）当）当a a1 1=1=1时时,3,3 1010-3-3=1/4=1/4 1010-(n-1)-(n-1)1212 1010-3-3=10=10-(n-1)-(n-1)上式两边取以上式两边取以1010为底的对数得为底的对数得 lg2lg22 2+lg3+(-3)=-n+1 lg2=0.3010 lg3=0.4771+lg3+(-3)=-n+1 lg2=0.3010 lg3=0.4771 2 2 0.3010+0.4771-4=-n 0.3010+0.4771-4=-n n=2.9209 n=2.9209）当）当a a1 1=9=9时时,3,3 1010-3-3=1/20=1/20 1010-(n-1)-(n-1)6 6 1010-3-3=10=10-n-n 上式两边取以上式两边取以1010为底的对数得为底的对数得 lg2+lg3+(-3)=-n n=2.2219lg2+lg3+(-3)=-n n=2.2219 x x*至少有至少有3 3位有效数字位有效数字 解：由解：由例例2 2 为使为使 的近似数的相对误差小于的近似数的相对误差小于0.1%0.1%，问查开方表时，要取几位有效数字？问查开方表时，要取几位有效数字？-(n-1)lg2+2lg3+(-3)-(n-1)lg2+2lg3+(-3)-n1.2552-4 -n1.2552-4 -n-2.7448 -n2.7448 n2.7448 取取 n=3n=3即查平方表时即查平方表时 8.378.37取三位有效数字取三位有效数字 解：解：8 9 a8 9 a1 1=8=8 注意注意:已知有效数字已知有效数字,求相对误差用公式求相对误差用公式 已知相对误差已知相对误差,求具有几位有效数字公式求具有几位有效数字公式