数值计算方法的意义内容与方法.ppt

数 值 计 算 方 法陈研陈研 Tel:62732959 新学科综合楼新学科综合楼 4-201 中国农业大学资源和环境学院中国农业大学资源和环境学院 2005年年9月月1 1 数值计算方法的意义、内容与方法数值计算方法的意义、内容与方法软件的核心就是算法。软件的核心就是算法。软件的核心就是算法。软件的核心就是算法。20 20 世纪最伟大的科学技术发明世纪最伟大的科学技术发明世纪最伟大的科学技术发明世纪最伟大的科学技术发明-计算机计算机计算机计算机 计算机是对人脑的模拟，它强化了人的思维智能；计算机是对人脑的模拟，它强化了人的思维智能；计算机是对人脑的模拟，它强化了人的思维智能；计算机是对人脑的模拟，它强化了人的思维智能；计算机的发展和应用，已不仅仅是一种科学技术计算机的发展和应用，已不仅仅是一种科学技术计算机的发展和应用，已不仅仅是一种科学技术计算机的发展和应用，已不仅仅是一种科学技术现象，而且成了一种政治、军事、经济和社会现象；现象，而且成了一种政治、军事、经济和社会现象；现象，而且成了一种政治、军事、经济和社会现象；现象，而且成了一种政治、军事、经济和社会现象；没有软件的支持，超级计算机只是一堆废铁而已；没有软件的支持，超级计算机只是一堆废铁而已；没有软件的支持，超级计算机只是一堆废铁而已；没有软件的支持，超级计算机只是一堆废铁而已；算法犹如乐谱，算法犹如乐谱，算法犹如乐谱，算法犹如乐谱，软件犹如软件犹如软件犹如软件犹如CDCD盘片，盘片，盘片，盘片，而硬件如同而硬件如同而硬件如同而硬件如同CDCD唱机。唱机。唱机。唱机。算法的研究和应用正是本课程的主题算法的研究和应用正是本课程的主题算法的研究和应用正是本课程的主题算法的研究和应用正是本课程的主题 ！现代科学研究的三大支柱理论研究科学实验科学计算21212121世纪信息社会的两个主要特征：世纪信息社会的两个主要特征：世纪信息社会的两个主要特征：世纪信息社会的两个主要特征：“计算机无处不在计算机无处不在计算机无处不在计算机无处不在”“数学无处不在数学无处不在数学无处不在数学无处不在”21212121世纪信息社会对科技人才的要求：世纪信息社会对科技人才的要求：世纪信息社会对科技人才的要求：世纪信息社会对科技人才的要求：-会会会会“用数学用数学用数学用数学”解决实际问题解决实际问题解决实际问题解决实际问题-会用计算机进行科学计算会用计算机进行科学计算会用计算机进行科学计算会用计算机进行科学计算科学计算解题过程一、一、计算数学的产生和早期发展计算数学的产生和早期发展计算数学是数学的一个古老的分支，虽然数学不仅仅计算数学是数学的一个古老的分支，虽然数学不仅仅是计算，但推动数学产生和发展的最直接原因还是是计算，但推动数学产生和发展的最直接原因还是计算问题计算问题计算问题计算问题。二、二十世纪计算数学的发展二十世纪计算数学的发展数值代数数值代数 最优化计算最优化计算 数值逼近数值逼近 计算几何计算几何 概率统计计算概率统计计算 蒙特卡罗方法蒙特卡罗方法 微分方程的数值解法微分方程的数值解法 微分方程的反演问题微分方程的反演问题 数值计算的主要内容数值计算的主要内容数值代数：方程求根、线性方程组求解、数值代数：方程求根、线性方程组求解、特征值和特征向量的计算、特征值和特征向量的计算、非线性方程组的求解；非线性方程组的求解；数值逼近：插值、数值微分和积分、数值逼近：插值、数值微分和积分、最小二乘法；最小二乘法；微分方程数值解：微分方程数值解：常微分方程数值解；常微分方程数值解；偏微分方程数值解：偏微分方程数值解：差分法差分法 有限元法有限元法 有限体积法有限体积法&教材教材 数值计算方法数值计算方法 徐涛徐涛 编著编著（吉林科学技术出版（吉林科学技术出版社）社）&参考书目参考书目 应用应用数值方法数值方法 使用使用MATLAB和和C语言语言 Robert J.Schilling&Sandra L.Harris （机械工业出版社）机械工业出版社）Numerical Recipes in C+The Art of Scientific Computing Second Edition William H.Press 等著等著 （电子工业出版社）（电子工业出版社）现代数值分析现代数值分析 李庆扬、易大义、王能超李庆扬、易大义、王能超 编著编著 （高等教育出版社）（高等教育出版社）2 算算 法法一、算法的概念一、算法的概念 描述算法可以有不同的方式。例如，可以用日常语言描述算法可以有不同的方式。例如，可以用日常语言和数学语言加以叙述，也可以借助形式语言（算法语言）和数学语言加以叙述，也可以借助形式语言（算法语言）给出精确的说明，也可以用框图直观地显示算法的全貌。给出精确的说明，也可以用框图直观地显示算法的全貌。定义：由基本运算及运算顺序的规定所构成的完整的定义：由基本运算及运算顺序的规定所构成的完整的 解题步骤，称为解题步骤，称为算法算法算法算法。例例1：一群小兔一群鸡，两群合到一群里，要数腿共：一群小兔一群鸡，两群合到一群里，要数腿共48，要数脑袋整要数脑袋整17，多少小兔多少鸡？，多少小兔多少鸡？算术方法算术方法：若没有小兔，则鸡应是若没有小兔，则鸡应是17只只总腿数总腿数：21734一只小兔增加一只小兔增加 2条腿，条腿，应该有应该有只小兔只小兔1010只小鸡只小鸡代数方法代数方法：设有设有x只小鸡，只小鸡，y只小兔只小兔，(-2)*(i)+(ii),得得只小兔只小兔高斯消高斯消去法去法例：求解二元一次联立方程组例：求解二元一次联立方程组用行列式解法：首先判别用行列式解法：首先判别 （1）如果如果 ，则令计算机计算，则令计算机计算 输出计算的结果输出计算的结果x1，x2。（2）如果如果D D=0 0，则或是无解，或有无穷多组解。，则或是无解，或有无穷多组解。是否为零，存在两种可能：是否为零，存在两种可能：令令通过求解过程，可以总结出算法步骤如下：通过求解过程，可以总结出算法步骤如下：S2 计算计算S3 如果如果则输出原方程无解或有无穷多组解的信息则输出原方程无解或有无穷多组解的信息;否则否则S1 输入输入S4 输出计算的结果输出计算的结果输入输入 D=a11a22-a12a21D=0开始开始输出输出 x1,x2 结结 束束 No输出无解信息输出无解信息Yes二、算法的优劣二、算法的优劣 计算量小计算量小 存贮量少存贮量少 逻辑结构简单逻辑结构简单例：用行列式解法求解线性方程组例：用行列式解法求解线性方程组:n阶方程组，要计算阶方程组，要计算n+1个个n n阶行列式的值，阶行列式的值，总共需要做总共需要做n!(n-1)(n+1)次乘法运算。次乘法运算。n=20 需要运需要运算多少次？算多少次？n=100?一、一、误差的背景介绍误差的背景介绍1.来源与分类来源与分类 从实际问题中抽象出数学模型从实际问题中抽象出数学模型 模型误差模型误差3 数值计算中的误差数值计算中的误差例例1:1:质量为质量为m的物体，在重力作用下，自由下落，的物体，在重力作用下，自由下落，其下落距离其下落距离s 与时间与时间t 的关系是：的关系是：（1.1）其中其中 g 为重力加速度。为重力加速度。通过测量得到模型中参数的值通过测量得到模型中参数的值 观测误差观测误差 求近似解求近似解 方法误差方法误差(截断误差）截断误差）机器字长有限机器字长有限 舍入误差舍入误差 用计算机、计算器和笔算，都只能用有限位小数用计算机、计算器和笔算，都只能用有限位小数来代替无穷小数或用位数较少的小数来代替位数较多来代替无穷小数或用位数较少的小数来代替位数较多的有限小数，如：的有限小数，如：=3.1415926 x=8.12345四舍五入后四舍五入后在数值计算方法中，主要研究在数值计算方法中，主要研究截断误差截断误差截断误差截断误差和和舍入误差舍入误差舍入误差舍入误差（包括初始数据的误差）对计算结果的影响！（包括初始数据的误差）对计算结果的影响！二、绝对误差、相对误差和有效数字二、绝对误差、相对误差和有效数字1 1绝对误差与绝对误差限绝对误差与绝对误差限例例 2:若用以厘米为最小刻度的尺去量桌子的长，若用以厘米为最小刻度的尺去量桌子的长，大约为大约为1.45米，求米，求1.45米的绝对误差。米的绝对误差。1.45米的米的绝对误差绝对误差=？不知道！不知道！定义定义1：设：设x是准确值是准确值，x*为为x的一个近似值的一个近似值，称，称 是近似值是近似值x的的绝对误差绝对误差绝对误差绝对误差,简称为简称为误差误差误差误差。（1.5）但实际问题往往可以估计出但实际问题往往可以估计出 不超过某个正数不超过某个正数，即，即，则称，则称 为绝对误差限，有了绝对误差限为绝对误差限，有了绝对误差限就可以知道就可以知道x范围为范围为即即x落在落在 内。在应用上，常常采用下列内。在应用上，常常采用下列写法来刻划写法来刻划x*的精度。的精度。2相对误差和相对误差限相对误差和相对误差限（1.6）定义定义2：设设x是准确值，是准确值，x*是近似值，称是近似值，称满足满足为近似值为近似值x的的相对误差相对误差相对误差相对误差，相应地，若正数，相应地，若正数 ，则称则称 为为x的的相对误差限相对误差限相对误差限相对误差限。3有效数字有效数字则说则说x*近似表示近似表示x准确到小数后第准确到小数后第n位，并从这第位，并从这第n位起位起直到最左边的非零数字之间的一切数字都称为直到最左边的非零数字之间的一切数字都称为有效数字有效数字有效数字有效数字，并把有效数字的位数称为并把有效数字的位数称为有效位数有效位数有效位数有效位数。定义定义3：如果如果（1.7）由上述定义由上述定义有效数位为有效数位为3位位有效数位为有效数位为5位位有效数位为有效数位为4位位误差的传播与积累误差的传播与积累例例3：蝴蝶效应蝴蝶效应 纽约的一只蝴蝶翅膀一拍，风和日丽的北纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！京就刮起台风来了？！NYBJ以上是一个病态问题以上是一个病态问题 4 数值计算中应该注意的一些原则数值计算中应该注意的一些原则 1要使用数值稳定的算法要使用数值稳定的算法例例4：求：求 （n=0,1,2,8）的值。的值。解：由于解：由于初值初值递推公式递推公式（1.8）注意此公式注意此公式精确精确成成立立按按 (1.8)式就可以逐步算出式就可以逐步算出What happened?!不稳定的算法不稳定的算法 ！由递推公式由递推公式（1.8）可看出，可看出，In-1的误差扩大了的误差扩大了5倍后传给倍后传给In，因而初值因而初值I0的误差对以后各步计算结果的影响，随着的误差对以后各步计算结果的影响，随着n的增大的增大愈来愈严重。这就造成愈来愈严重。这就造成I4的计算结果严重失真。的计算结果严重失真。这就是误差传播所引起的危害这就是误差传播所引起的危害这就是误差传播所引起的危害这就是误差传播所引起的危害 !改变公式：改变公式：将公式将公式变为变为不妨设不妨设I9 I10，于是由于是由可求得可求得I9 0.017，按公式按公式（1.9）可逐次求得可逐次求得（1.9）I8 0.019 I7 0.021I6 0.024 I8 0.028I4 0.034 I3 0.043I2 0.058 I1 0.088I0 0.182 稳定的算法稳定的算法 ！在我们今后的讨论中，在我们今后的讨论中，误差误差将不可回避，将不可回避，算法的算法的稳定性稳定性会是一个非常重要的话题。会是一个非常重要的话题。2要避免两个相似数相减要避免两个相似数相减在数值计算中，两个相近的数作减法时有效数字会损失。在数值计算中，两个相近的数作减法时有效数字会损失。（1.10）的值。的值。当当x=1000，y 的准确值为的准确值为0.01580 1、直接相减直接相减2、将将（1.10）改写为改写为则则 y=0.01581 例例5:求求类似地类似地 2.绝对值太小的数不宜作除数绝对值太小的数不宜作除数例例6：如分母变为如分母变为0.0011，也即分母只有，也即分母只有0.0001的变化时的变化时3.避免大数避免大数吃吃小数小数例例7：用单精度计算：用单精度计算 的的根。根。精确解为精确解为 算法算法1 1：利用求根公式：利用求根公式在计算机内，在计算机内，109存为存为0.1 1010，1存为存为0.1 101。做加法时，做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即两加数的指数先向大指数对齐，再将浮点部分相加。即1 的指数部分须变为的指数部分须变为1010，则：，则：1=0.0000000001 1010，取，取单精度时就成为：单精度时就成为：109+1=0.10000000 1010+0.00000000 1010=0.10000000 1010?算法算法2：先解出：先解出注：注：注：注：求和时从小到大相加，可使和的误差减小。求和时从小到大相加，可使和的误差减小。例例8：按从小到大、以及从大到小的顺序分别计算：按从小到大、以及从大到小的顺序分别计算4.先化简再计算，减少步骤，避免误差积累。先化简再计算，减少步骤，避免误差积累。一般来说，计算机处理下列运算的速度为一般来说，计算机处理下列运算的速度为1+2+3+40+109再利用再利用5.算法的算法的递推性递推性 计算机上使用的算法常采用递推化的形式，递推计算机上使用的算法常采用递推化的形式，递推化的基本思想是把一个复杂的计算过程归结为简单过程化的基本思想是把一个复杂的计算过程归结为简单过程的多次重复。这种重复在程序上表现为循环。递推化的的多次重复。这种重复在程序上表现为循环。递推化的优点是简化结构和节省计算量优点是简化结构和节省计算量。多项式求值：多项式求值：给定的给定的x 求下列求下列n 次多项多的值次多项多的值。解：解：1.用一般算法，即直接求和法；用一般算法，即直接求和法；2.逐项求和法；逐项求和法；3.秦九韶方法；秦九韶方法；例例9：用秦和韶方法求多项式：用秦和韶方法求多项式在在x=-0.2的值。的值。解：解：Ka5-KvK00.008330.00833v0=a510.041670.04v1=v0 x+a420.166670.15867v2=v1x+a330.50.46827v3=v2x+a2410.90635v4=v3x+a1510.81873v5=v4x+a0