数值计算方法第一章课件

数值计算方法数值计算方法第一章第一章数值计算引论数值计算引论1.1 数值计算方法数值计算方法 数数值值计计算算方方法法是是应应用用数数学学的的一一个个分分支支，又又称称为为数数值值分分析析或或计计算算方方法法，它它是是研研究究用用数数字字计计算算机机求求解解各各种种数数学学问问题题的的数数值值方方法法及及其其理理论论的的一一门门学学科科，是是程程序序设设计计和和对对数数值值结结果果进进行行分分析析的的依依据和基础。据和基础。21.1 数值计算方法数值计算方法n利用电子计算机解题的一般步骤：利用电子计算机解题的一般步骤：n提出实际问题提出实际问题n构造数学模型构造数学模型将实际问题归纳为明确的数学问将实际问题归纳为明确的数学问题题n选择计算方法选择计算方法对数学问题，选择运算简单、工对数学问题，选择运算简单、工作量节省、并能保证精确度要求的计算方法，确定作量节省、并能保证精确度要求的计算方法，确定计算步骤计算步骤n计算过程的程序设计计算过程的程序设计用一定的程序设计语言将用一定的程序设计语言将计算过程编成程序计算过程编成程序n将计算程序和原始数据输入，上机计算，最后计算将计算程序和原始数据输入，上机计算，最后计算机输出计算结果机输出计算结果31.1 数值计算方法数值计算方法n数值计算方法（数值算法）：把对数学问题的数值计算方法（数值算法）：把对数学问题的解法归结为有加、减、乘、除等基本运算，并解法归结为有加、减、乘、除等基本运算，并对运算顺序有完整而准确的描述的算法对运算顺序有完整而准确的描述的算法n数值算法具有的特点数值算法具有的特点 n面向计算机面向计算机 n有可靠的理论分析有可靠的理论分析 n要有好的计算复杂性要有好的计算复杂性 41.1 数值计算方法数值计算方法n总之，对于给定的数学模型所提出的可行、有总之，对于给定的数学模型所提出的可行、有效的算法应该是符合计算机的要求，在理论上效的算法应该是符合计算机的要求，在理论上收敛、稳定，在实际计算中精度高、计算复杂收敛、稳定，在实际计算中精度高、计算复杂性小、能通过实验验证的数值方法性小、能通过实验验证的数值方法 51.2 算法算法n算法的概念算法的概念n人工手算过程人工手算过程n计算机运算过程：先将所制定的解题方案告诉计算计算机运算过程：先将所制定的解题方案告诉计算机，令计算机按照人们所规定的计算顺序去自动执机，令计算机按照人们所规定的计算顺序去自动执行行n程序设计：用机器所能接受的程序设计：用机器所能接受的“语言语言”来描述解题来描述解题步骤步骤n算法：指解题方案的准确而完整的描述算法：指解题方案的准确而完整的描述 n算法的描述：日常语言，数学语言，算法语言，算算法的描述：日常语言，数学语言，算法语言，算法框图法框图61.2 算法算法n举例：求解二元一次方程组举例：求解二元一次方程组 首先判断首先判断 是否为是否为071.2 算法算法n算法框图算法框图81.2 算法算法n算法的优劣算法的优劣 n计算量的大小是衡量算法优劣的一个重要标准计算量的大小是衡量算法优劣的一个重要标准 n例如：行列式解法的克莱姆法则，解一个例如：行列式解法的克莱姆法则，解一个n阶方程组，要阶方程组，要算算n+1个个n阶行列式的值，总共需要阶行列式的值，总共需要n!(n-1)(n+1)次乘法。次乘法。如果求解一个如果求解一个20阶左右的方程组，需要工作很多年才能阶左右的方程组，需要工作很多年才能完成完成 n尽量节约存储量，也是设计算法时需要考虑的一个尽量节约存储量，也是设计算法时需要考虑的一个因素因素 n尽量利用原有的工作单元进行累算。算式采用尽量利用原有的工作单元进行累算。算式采用“动态动态”形式，如将形式，如将y=x2表示为表示为 ,即将单元即将单元x的内容的内容自乘，结果仍存放在单元自乘，结果仍存放在单元x中中 91.2 算法算法n设计算法所要考虑的另一个因素就是逻辑结构的复设计算法所要考虑的另一个因素就是逻辑结构的复杂性问题杂性问题 n算法的递推性算法的递推性n算法的递推化：将一个复杂的计算过程归结为简单算法的递推化：将一个复杂的计算过程归结为简单过程的多次重复过程的多次重复 n例如：给定例如：给定x的的n次多项式次多项式101.2 算法算法 令令 上式可以表示为递推的公式：上式可以表示为递推的公式：初值为：初值为：111.2 算法算法n多项式的秦九韶计算方法多项式的秦九韶计算方法 n将多项式按降幂的次序排列为：将多项式按降幂的次序排列为：n将多项式表示为嵌套形式：将多项式表示为嵌套形式：n设用设用 表示第表示第k层的值，那么第层的值，那么第k层的结果层的结果 显然等于第显然等于第k-1层的结果层的结果 乘上乘上x再加上系数再加上系数 121.2 算法算法n初值为：初值为：131.2 算法算法141.2 算法算法n例：用秦九韶方法求多项式例：用秦九韶方法求多项式 在在x=-0.2的值的值 151.2 算法算法多项式降多项式降幂系数幂系数秦九韶方法的秦九韶方法的计算结果计算结果0008330008330041670040000166670158670504682710906351081873161.3 误差的来源误差的来源n数可以分为两类：数可以分为两类：n精确数（准确数、真值）：精确的反映实际情况的精确数（准确数、真值）：精确的反映实际情况的数。如教室里面有数。如教室里面有42名学生名学生n近似数（某准确数的近似值）：只能近似的反映实近似数（某准确数的近似值）：只能近似的反映实际情况。如测量得到桌子的长度为际情况。如测量得到桌子的长度为950mm，这个，这个测量值是不能精确的反映桌子实际长度的近似值测量值是不能精确的反映桌子实际长度的近似值n误差：将一个数的准确值与其近似值之差称为误差：将一个数的准确值与其近似值之差称为误差误差 171.3 误差的来源误差的来源n误差产生的原因误差产生的原因 n模型误差（描述误差）模型误差（描述误差）n观测误差（测量误差）观测误差（测量误差）n截断误差（方法误差）截断误差（方法误差）n无穷过程用有限过程近似引起的误差无穷过程用有限过程近似引起的误差n例如：指数函数例如：指数函数 可展开成下列幂级数形式可展开成下列幂级数形式 但在实际计算中，只能截取有限项求出但在实际计算中，只能截取有限项求出181.3 误差的来源误差的来源根据泰勒余项定理，根据泰勒余项定理，关于关于 的截断误差是的截断误差是n例：假定例：假定|x|1，用泰勒多项式计算，用泰勒多项式计算 的值，设要求的值，设要求截断误差不超过截断误差不超过0.005，问公式该取多少项？，问公式该取多少项？n舍入误差（计算误差）舍入误差（计算误差）n无论用计算机、计算器计算还是笔算，都只能用有限位无论用计算机、计算器计算还是笔算，都只能用有限位小数来代替无穷小数或用位数较少的小数来代替位数较小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数，产生舍入误差多的有限小数，产生舍入误差 n例如：例如：3.1415926，191.4 近似数的误差表示法近似数的误差表示法n绝对误差绝对误差n设设x*是准确值是准确值x的一个近似值，则的一个近似值，则 称为近似值称为近似值x*的绝对误差，简称误差。的绝对误差，简称误差。n定义定义 如果如果 那么那么 叫做近似数叫做近似数x*的绝对误差限，用它反映近的绝对误差限，用它反映近似数的精度。似数的精度。201.4 近似数的误差表示法近似数的误差表示法n通常我们用通常我们用x=x*+*来表示近似数来表示近似数x*的精确度或的精确度或准确值所在的范围，准确值所在的范围，*应该取得尽可能小应该取得尽可能小n例例x4.3762816，取近似数，取近似数x*4.376，则，则x-x*=0.0002816，有，有|x-x*|=0.00028160.0003=0.3103 同样同样|x-x*|=0.00028160.00029=0.29103n例：用一把有毫米刻度的尺子，测量桌子的长度，例：用一把有毫米刻度的尺子，测量桌子的长度，读出来的值读出来的值x*1235mm，这是桌子实际长度，这是桌子实际长度x的的一个近似值，由尺子的精度可以知道，这个近似值一个近似值，由尺子的精度可以知道，这个近似值的误差不会超过的误差不会超过1/2mm 211.4 近似数的误差表示法近似数的误差表示法n按四舍五入原则取近似值是使用最广泛的取近似值按四舍五入原则取近似值是使用最广泛的取近似值的方法的方法 n四舍五入的误差限四舍五入的误差限n在计算机中通常采用的是二进制实数系统，表示形在计算机中通常采用的是二进制实数系统，表示形式为：式为：的数称为机器数。其中整数的数称为机器数。其中整数m称为阶码，小数称为阶码，小数 为尾数为尾数 221.4 近似数的误差表示法近似数的误差表示法n设设x为一个实数，其十进制的标准形式为：为一个实数，其十进制的标准形式为：x0.x1x210m 其中其中m是整数，是整数，x1,x2,是是0,1,9中的任一数，但中的任一数，但x10，经过四舍五入保留，经过四舍五入保留n位数字，得到近似值位数字，得到近似值231.4 近似数的误差表示法近似数的误差表示法n四舍时的误差限为：四舍时的误差限为：|x x*|=(0.x1x2xnxn+1-0.x1x2xn)10m (0.x1x2xn499-0.x1x2xn)10m =10m0.004991/210m-nn五入时的误差限五入时的误差限|x x*|=(0.x1x2xn1(xn+1)0.x1x2xn)10m =(0.001-0.00 xn+1)10m 10m-n(1-0.xn+1)由于由于xn+15,所以所以1-0.xn+11/2，因此有，因此有|x x*|1/210m-n241.4 近似数的误差表示法近似数的误差表示法n例：圆周率例：圆周率3.14159，用四舍五入取小数点，用四舍五入取小数点后后4位时，近似值为位时，近似值为3.1416，此时，此时m=1，n=5，m-n=1-5=-4，因此绝对误差，因此绝对误差*1/2104。同样取。同样取小数点后小数点后2位时，近似值为位时，近似值为3.14，其绝对误差，其绝对误差*1/2102n线性运算对误差的影响线性运算对误差的影响 n设设xk*是是xk的近似值，对任意系数的近似值，对任意系数k，取，取 作为作为 的近似值，这时有不等式的近似值，这时有不等式251.4 近似数的误差表示法近似数的误差表示法 如果每个近似值如果每个近似值xk*的误差限全为的误差限全为*，则和式，则和式 x*的误差限为（的误差限为（）*n例：用近似公式求例：用近似公式求ex在在x=-0.2的值，并估计误差的值，并估计误差 令令 0.81873 利用余项公式可估计出截断误差限利用余项公式可估计出截断误差限10.3106，系数的舍入误差都不超过，系数的舍入误差都不超过1/2105，和式的舍，和式的舍入误差限为入误差限为20.5107，误差限为，误差限为120.35106 261.4 近似数的误差表示法近似数的误差表示法n有效数字有效数字 n定义定义 设数设数x的近似值的近似值x*=0.x1x2xn10m，其中，其中xi是是0到到9之间的任一个数，但之间的任一个数，但x10,i=1,2,3,n正正整数，整数，m整数，如果整数，如果|x x*|1/210m-n 则称则称x*为为x的具有的具有n位有效数字的近似值，位有效数字的近似值，x*准确到准确到第第n位，位，x1x2xn 是是x*的有效数字。的有效数字。271.4 近似数的误差表示法近似数的误差表示法n由上述定义由上述定义n例：例：3.141592，当取，当取3.142和和3.141作为其作为其近似值时，有效数字分别为多少位？近似值时，有效数字分别为多少位？有效数位为有效数位为3位位有效数位为有效数位为5位位有效数位为有效数位为4位位281.4 近似数的误差表示法近似数的误差表示法n有效数字的确定有效数字的确定 n用四舍五入取准确值的前用四舍五入取准确值的前n位位x*作为近似值，则作为近似值，则x*必有必有n个有效数字个有效数字 例如，例如，3.1415926,取取3.14作为近似值，则有作为近似值，则有3位位有效数字，取有效数字，取3.142作为近似值，则有作为近似值，则有4位有效数字位有效数字 n有效数字位数相同的两个近似数，绝对误差不一定相同有效数字位数相同的两个近似数，绝对误差不一定相同 例如，设例如，设x1*=12345,x2*=12.345，二者均有，二者均有5位有效数位有效数字，前者的绝对误差为字，前者的绝对误差为1/2，后者的绝对误差为，后者的绝对误差为1/2103 n把任何数乘以把任何数乘以10p等于移动该数的小数点，这样并不影响等于移动该数的小数点，这样并不影响其有效数字的位数其有效数字的位数 291.4 近似数的误差表示法近似数的误差表示法n准确值被认为具有无穷多位有效数字准确值被认为具有无穷多位有效数字 例如，真值例如，真值0.5，不表示只有，不表示只有1位有效数字，具有无穷多位有效数字，具有无穷多位有效数字位有效数字 n相对误差相对误差n定义定义 x的近似值的近似值x*的相对误差的相对误差 n相对误差限可由绝对误差限求出，反之，绝对误差相对误差限可由绝对误差限求出，反之，绝对误差限也可由相对误差限求出限也可由相对误差限求出 301.4 近似数的误差表示法近似数的误差表示法n例：取例：取3.14作为作为的四舍五入的近似值，试求其相的四舍五入的近似值，试求其相对误差对误差 311.4 近似数的误差表示法近似数的误差表示法n有效数字与相对误差有效数字与相对误差n定理定理1 如果近似数如果近似数 具有具有n位有效数字，则其相对误差位有效数字，则其相对误差 证证 因因 ，有，有 又，又，有有n位有效数字，即位有效数字，即 ，因此，因此321.4 近似数的误差表示法近似数的误差表示法n例：取例：取3.14作为作为的四舍五入的近似值，试求其相的四舍五入的近似值，试求其相对误差对误差 解：四舍五入的近似值解：四舍五入的近似值3.14，各位都是有效数字，各位都是有效数字，因此因此n=3，所以，所以 331.4 近似数的误差表示法近似数的误差表示法n定理定理2 如果近似数如果近似数 的的相对误差相对误差 则该近似数至少具有则该近似数至少具有n位有效数字位有效数字 证证 因为因为341.4 近似数的误差表示法近似数的误差表示法 根据有效数字定义可知，根据有效数字定义可知，x*具有具有n位有效数字位有效数字 n例：已知近似数的相对误差为例：已知近似数的相对误差为0.25%，问可能有几，问可能有几位有效数字位有效数字 解：根据定理解：根据定理2 x1未给出，取未给出，取 按最不利的情况取，按最不利的情况取，x*至少应该有至少应该有2位有效数字位有效数字 351.4 近似数的误差表示法近似数的误差表示法n有效数字的位数表征了近似数的精度，绝对误差与有效数字的位数表征了近似数的精度，绝对误差与小数点后的位数有关，相对误差与有效数字的位数小数点后的位数有关，相对误差与有效数字的位数有关有关 361.5 数值运算误差分析数值运算误差分析 n函数运算误差函数运算误差n设一元函数设一元函数f(x)的自变量的自变量x的近似值为的近似值为x*，f(x)的近的近似值为似值为f(x*)，其误差记为，其误差记为 ，对，对f(x)在近似值在近似值x*附近泰勒展开式为附近泰勒展开式为n两边取绝对值得两边取绝对值得371.5 数值运算误差分析数值运算误差分析n设设 与与 相差不大，可以忽略相差不大，可以忽略*的高次的高次项，于是可以得出函数运算的误差和相对误差项，于是可以得出函数运算的误差和相对误差381.5 数值运算误差分析数值运算误差分析n例：正方形的边长约为例：正方形的边长约为100cm，怎样测量才能，怎样测量才能使其面积误差不超过使其面积误差不超过1cm2？n解：设正方形的边长为解：设正方形的边长为xcm，测量值为，测量值为x*cm，面积，面积为为 Y=f(x)=x2 因此因此 要使正方形面积误差不超过要使正方形面积误差不超过1cm2，测量边长时绝，测量边长时绝对误差应不超过对误差应不超过0.005cm 391.6 减少运算误差的若干原则减少运算误差的若干原则n两个相近的数相减，会严重损失有效数字两个相近的数相减，会严重损失有效数字n设设y=x-A 其中其中A和和x均为准确值。假设均为准确值。假设A运算时不发生误差，运算时不发生误差，而而x有误差，其近似值为有误差，其近似值为x*，由此可估计出当用，由此可估计出当用x*近似代替近似代替x时，时，y的相对误差的相对误差 由上可以看出，在由上可以看出，在x的绝对误差的绝对误差*(x*)不变时，如果不变时，如果x*越接近越接近A，那么，那么y的相对误差的相对误差r*(y*)会变得越大，会变得越大，而相对误差的增大必然会导致有效数字位数的减少而相对误差的增大必然会导致有效数字位数的减少 401.6 减少运算误差的若干原则减少运算误差的若干原则n例：当例：当x=10003时，计算时，计算 的的近似值近似值 解：如果使用解：如果使用6位十进制浮点运算，运算时取位十进制浮点运算，运算时取6位有位有效数字，结果为效数字，结果为 只有一位有效数字，损失了只有一位有效数字，损失了5位有效数字位有效数字 如果改用如果改用 则其结果有则其结果有6位有效数字，与精确值位有效数字，与精确值0.00499912523117984非常接近非常接近 411.6 减少运算误差的若干原则减少运算误差的若干原则n例：例：x1=1.99999，x2=1.99998，求，求lgx1-lgx2，如，如果使用果使用6位十进制浮点运算，运算时取位十进制浮点运算，运算时取6位有效数字，位有效数字，则则lgx1-lgx20.301028-0.301026=0.000002只只有一位有效数字，损失了有一位有效数字，损失了5位有效数字。位有效数字。如果改用如果改用lgx1-lgx2 2.17149106，则其结果有则其结果有6位有效数字，与精确值位有效数字，与精确值2.171488695634106非常接近非常接近 421.6 减少运算误差的若干原则减少运算误差的若干原则n当当x接近接近0时时 当当x充分大时充分大时 431.6 减少运算误差的若干原则减少运算误差的若干原则n防止大数防止大数“吃掉吃掉”小数小数 n计算机的位数有限，在进行加减法运算时，要对阶计算机的位数有限，在进行加减法运算时，要对阶和规格化和规格化 n例如在四位浮点机上作运算例如在四位浮点机上作运算 0.73151030.4506105 对阶是对阶是0.73151030.0000103，计算结果为，计算结果为0.7315103，结果是大数，结果是大数“吃掉吃掉”了小数了小数 n当参加运算的两个数的数量级相差很大时，如果不当参加运算的两个数的数量级相差很大时，如果不注意运算次序，就有可能把数量级小的数注意运算次序，就有可能把数量级小的数“吃掉吃掉”441.6 减少运算误差的若干原则减少运算误差的若干原则n例如：已知例如：已知A=105，B5，C105 如果按照（如果按照（AB）C进行运算，则结果接近于零，进行运算，则结果接近于零，结果失真；如果按照（结果失真；如果按照（AC）B进行计算，则结进行计算，则结果接近于正确的结果果接近于正确的结果5 451.6 减少运算误差的若干原则减少运算误差的若干原则n在除法运算中要避免出现除数的绝对值远远小在除法运算中要避免出现除数的绝对值远远小于被除数绝对值的情形于被除数绝对值的情形n例：在例：在4位浮点十进制数下，用消去法解线性方程位浮点十进制数下，用消去法解线性方程组组 解：仿计算机实际计算，将上述方程组写成解：仿计算机实际计算，将上述方程组写成461.6 减少运算误差的若干原则减少运算误差的若干原则（1）（0.3000104）（）（2）得到下述方程组）得到下述方程组 解得解得 x1=0,x2=0.2 如果反过来用第二个方程消去第一个方程中含如果反过来用第二个方程消去第一个方程中含x1的的项，那么就可以避免很小的数作除数的情形，即项，那么就可以避免很小的数作除数的情形，即（2）（0.3000104）（）（1），得），得 解得解得 x1=1.4,x2=0.2471.6 减少运算误差的若干原则减少运算误差的若干原则n简化计算步骤，减少运算次数简化计算步骤，减少运算次数n例如：计算例如：计算x255，如果逐个相乘，要做，如果逐个相乘，要做254次乘法，次乘法，但若改成但若改成 x255=x x2 x4 x8 x16 x32 x64 x128 只要只要14次乘法运算即可次乘法运算即可 n例：计算和式例：计算和式 的值，如果直接逐的值，如果直接逐项求和，运算次数多且误差积累，但是可以进行化项求和，运算次数多且误差积累，但是可以进行化简：简：那么整个计算只要一个求倒数和一次减法就可以那么整个计算只要一个求倒数和一次减法就可以 481.6 减少运算误差的若干原则减少运算误差的若干原则n选用数值稳定性好的计算公式选用数值稳定性好的计算公式n定义定义 一个算法如果输入数据有误差，而在计算过一个算法如果输入数据有误差，而在计算过程中舍入误差不增长，那么称此算法是数值稳定的，程中舍入误差不增长，那么称此算法是数值稳定的，否则称此算法为数值不稳定的否则称此算法为数值不稳定的 n例：求例：求 （n=0,1,2,8）的值）的值 解：由于解：由于 491.6 减少运算误差的若干原则减少运算误差的若干原则 初值初值 于是可建立递推公式于是可建立递推公式 按按 上上 式就可以逐步算得式就可以逐步算得501.6 减少运算误差的若干原则减少运算误差的若干原则511.6 减少运算误差的若干原则减少运算误差的若干原则n如果改变计算公式，如果改变计算公式，由于误差是逐步衰减的，初值由于误差是逐步衰减的，初值In可以这样确定，不可以这样确定，不妨设妨设I9 I10，于是由，于是由521.6 减少运算误差的若干原则减少运算误差的若干原则可求得可求得I9 0.017，可逐次求得，可逐次求得I8 0.019 I7 0.021I6 0.024 I5 0.028I4 0.034 I3 0.043I2 0.058 I1 0.088I0 0.182 53