数值计算方法-第1章课件

现代数值计算方法现代数值计算方法中国科学技术大学中国科学技术大学工程科学学院近代力学系工程科学学院近代力学系授课教师：刘难生授课教师：刘难生联系电话：联系电话：63603345(O)办公室：办公室：力学一楼力学一楼522课程内容课程内容2022-11-5数值计算方法引引 言言22121世纪信息社会的两个主要特征：世纪信息社会的两个主要特征：“计算机无处不在计算机无处不在”“数学无处不在数学无处不在”2121世纪信息社会对科技人才的要求世纪信息社会对科技人才的要求：-会用数学解决实际问题会用数学解决实际问题-会用计算机进行科学计算会用计算机进行科学计算课程内容课程内容2022-11-5数值计算方法引引 言言3 科学方法论的巨大变革科学方法论的巨大变革：如果说如果说伽伽利略和牛顿利略和牛顿在科学发展史上奠定了实验在科学发展史上奠定了实验和理论这两大科学方法的支柱，那么由和理论这两大科学方法的支柱，那么由冯冯.诺依曼诺依曼研制的现代电子计算机把计研制的现代电子计算机把计算推上了人类科学活动的前沿，使计算算推上了人类科学活动的前沿，使计算成为成为第三种方法第三种方法。课程内容课程内容2022-11-5数值计算方法引引 言言4理论研究科学实验科学计算计算数学诺贝尔奖得主诺贝尔奖得主,计算物理学家计算物理学家 WilsonWilson提出提出 现代科学研究的三大支柱现代科学研究的三大支柱课程内容课程内容2022-11-5数值计算方法引引 言言5数值计算方法是计算数学的一个主要组成部分，数值计算方法是计算数学的一个主要组成部分，定义：定义：“什么是什么是数值计算方法？数值计算方法？”它主要研究使用计算机求解各种科学与工程计算它主要研究使用计算机求解各种科学与工程计算问题的数值方法（近似方法）问题的数值方法（近似方法）;对求得的解的精对求得的解的精度进行评估以及在计算机上实现求解等。度进行评估以及在计算机上实现求解等。数值计算方法已经成为计算机处理实际问题数值计算方法已经成为计算机处理实际问题的一个重要手段，从宏观天体运动学到微观分子的一个重要手段，从宏观天体运动学到微观分子细胞学，从工程系统到社会经济系统，无一能离细胞学，从工程系统到社会经济系统，无一能离开数值计算方法。因此，数值计算与计算机模拟开数值计算方法。因此，数值计算与计算机模拟被称为被称为“第三种研究科学方法第三种研究科学方法”。课程内容课程内容2022-11-5数值计算方法引引 言言6数值计算方法的数值计算方法的主要任务主要任务借助计算机提供切实可行的数学算法借助计算机提供切实可行的数学算法.想的精确度想的精确度;收敛且稳定收敛且稳定;误差可以分析或估计误差可以分析或估计.所提出的算法必须具有：可靠的理论分析所提出的算法必须具有：可靠的理论分析;理理时间复杂性好时间复杂性好_指节省时间；指节省时间；空间复杂性好空间复杂性好_指节省存储量。指节省存储量。计算复杂性好计算复杂性好 通过数值实验证明算法行之有效通过数值实验证明算法行之有效.课程内容课程内容2022-11-5数值计算方法引引 言言7实际物理问题实际物理问题简化简化数学问题数学问题编写计算程序编写计算程序计算得出结果计算得出结果科学计算解题过程科学计算解题过程建立数学模型建立数学模型选取计算方法选取计算方法课程内容课程内容2022-11-5数值计算方法课程内容课程内容8涉及的数学问题：涉及的数学问题：1）求解线性方程组，即）求解线性方程组，即AnnXn1=Bn1 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111很多数值方法最后都归结为很多数值方法最后都归结为（或最后一步）线性方程组（或最后一步）线性方程组求根，如求根，如FEM、FDM、FVM和优化方法等和优化方法等。2）非线性方程（组）求根）非线性方程（组）求根代数方程和超越方程求根，如：代数方程和超越方程求根，如：0)sin(1/1xx）（xf(x)0510152025-1-0.500.511.5f(x)=sin(x)f(x)=1/(x+1)h(x)Pn(x)课程内容课程内容2022-11-5数值计算方法课程内容课程内容9涉及的数学问题：涉及的数学问题：3）矩阵特征值问题的计算）矩阵特征值问题的计算4）函数插值和数据拟合）函数插值和数据拟合使得使得iiixxA插值函数插值函数 :)(xPniinyxP)(ni,.,1,0 xiyix1y1x2y2xn-1yn-1xnyn已知列表函数：已知列表函数：ni,.,1,0拟合函数拟合函数 :整体最贴近整体最贴近 ，)(xh）（iiyx,给定矩阵给定矩阵 ，求，求 和和 ，nnAiix课程内容课程内容2022-11-5数值计算方法课程内容课程内容10涉及的数学问题：涉及的数学问题：5）数值积分）数值积分定积分的数值近似定积分的数值近似f(x)=e-x/4cos(x)f(x)xbadxxfI)(数值解：数值解：求函数求函数y=y(x)在一系列离散点上在一系列离散点上y(xi)的函数的函数近似近似值值yi00)(,),(yxybaxyxfdxdy定解条件定解条件一维面积分、二维体积分一维面积分、二维体积分y(xi)yi6）常微分方程的数值求解）常微分方程的数值求解初值问题初值问题课程内容课程内容2022-11-5数值计算方法第一章第一章 数值计算中的误差分析数值计算中的误差分析 11本章内容：本章内容：1 1 误差与数值计算的误差分析误差与数值计算的误差分析2 2 选用和设计算法应遵循的原则选用和设计算法应遵循的原则课程内容课程内容2022-11-5数值计算方法1 误差与数值计算的误差分析误差与数值计算的误差分析 12一、误差的来源与分类一、误差的来源与分类模型误差模型误差对实际问题进行抽象和简化得到数学模型对实际问题进行抽象和简化得到数学模型mgdtsdm22例例1:质量为质量为m的物体，在重力作用下自由下落，的物体，在重力作用下自由下落，其下落距离其下落距离s 与时间与时间t 的关系是：的关系是：其中其中 g 为重力加速度。为重力加速度。抽象简化：抽象简化：1）质点简化假设；）质点简化假设；2）忽略空气阻力；等等。）忽略空气阻力；等等。课程内容课程内容2022-11-5数值计算方法一、误差的来源与分类一、误差的来源与分类13例例2:均质、粘性可压缩流体运动方程的普遍形式为均质、粘性可压缩流体运动方程的普遍形式为1)不可压缩流动假设不可压缩流动假设0u惯性力惯性力 =体积力体积力 +压力压力&粘性力粘性力pFudtd3/2uSIpp2/)(TuuSuFupdtd2)无粘假设无粘假设0pdtd Fu3)小小Reynolds数假设数假设(忽略惯性力忽略惯性力)uFp0课程内容课程内容2022-11-5数值计算方法一、误差的来源与分类一、误差的来源与分类 14观测观测误差误差数学模型中由实验测量得到的物理参量数学模型中由实验测量得到的物理参量截断截断误差误差有限过程（数值解）逼近无限过程（精确解）有限过程（数值解）逼近无限过程（精确解）卡文迪许实验卡文迪许实验示意图示意图 近似代替时，数值方法的截断误差是近似代替时，数值方法的截断误差是例如，当函数例如，当函数 用用TaylorTaylor多项式多项式 f x ()200001!2!nnnfffPxfxxxn (1)1(1)!nnnnfRxf xPxxn,0 x例如：重力加速度例如：重力加速度g，光速，光速C，万有引力常数万有引力常数G，等等，等等课程内容课程内容2022-11-5数值计算方法一、误差的来源与分类一、误差的来源与分类 15舍入误差舍入误差机器字长有限，只能对超过位数的数字舍入机器字长有限，只能对超过位数的数字舍入 用计算机、计算器和笔算，都只能用有限位用计算机、计算器和笔算，都只能用有限位小数来代替无穷小数或用位数较少的小数来小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数，如：代替位数较多的有限小数，如：四舍五入四舍五入或简单舍入或简单舍入e .单精度单精度双精度双精度相当于相当于物理截断物理截断课程内容课程内容2022-11-5数值计算方法一、误差的来源与分类一、误差的来源与分类 16四舍五入后四舍五入后0000074.01416.31000033.0333.031238.12350.00005x在数值计算方法中，主要研究在数值计算方法中，主要研究和和（包括初始数据的误差）对计算结果的影响！（包括初始数据的误差）对计算结果的影响！课程内容课程内容1 误差与数值计算的误差分析误差与数值计算的误差分析 二、误差与有效数字二、误差与有效数字绝对误差绝对误差与绝对误差与绝对误差限限例例:若若用以毫米为用以毫米为最小刻度的尺去量桌子的长，大最小刻度的尺去量桌子的长，大约约为为8484mmmm，求，求84mm84mm的的绝对误差。绝对误差。84mm的的绝对误差绝对误差=？不知道！不知道！是近似值是近似值 的的,简称为简称为。*x定义定义：设设 是是准确值准确值，为为 的一个近似值，称的一个近似值，称 x*xx*)(xxxE2022-11-517数值计算方法0)(0)(xExE*x弱（或亏）近似值弱（或亏）近似值强（或盈）近似值强（或盈）近似值课程内容课程内容二、误差与有效数字二、误差与有效数字*xxx*xx即即 落在落在 内。内。x在应用上，常常采用下列写法来刻划在应用上，常常采用下列写法来刻划 的精度。的精度。*x就可以知道就可以知道 的范围为的范围为x但实际问题往往可以估计出但实际问题往往可以估计出 不不超过某个正数超过某个正数 ，|)(|xE即即 ，则称，则称 为为绝对误差限绝对误差限，有了绝对误差限，有了绝对误差限|*|xx*,*xx上例中，直尺以毫米为上例中，直尺以毫米为最小最小刻度，所以误差不超刻度，所以误差不超过过0.50.5毫米，毫米，即即mmxmm5.845.83课程内容课程内容二、误差与有效数字二、误差与有效数字 相对误差与相对误差限相对误差与相对误差限为近似值为近似值 的的相对误差相对误差，即绝对误差与精确值之比。，即绝对误差与精确值之比。*x定义定义：设设 是是准确值，准确值，是近似值是近似值，是近似是近似 值值的的误差误差,称称x*x)(xExxxxxExEr*)()(*)(*xxxxEr通常取通常取课程内容课程内容二、误差与有效数字二、误差与有效数字事实上，事实上，当当 较小时较小时xxExEr)()()/)(1)/)()()(*)(*)()(-*)(222xxExxExExxxExxxExxxxxExxExxE是是 的的二次方项级二次方项级,故可忽略故可忽略不计。不计。)(xEr|*|)(|*xxxxEr定义定义：若存在若存在 ，使得，使得0则称则称 为近似值为近似值 的的相对误差限相对误差限。*x课程内容课程内容二、误差与有效数字二、误差与有效数字当已知当已知 时，测量时，测量100m100m物体的相对误差为物体的相对误差为cmxEr1|)(|%01.0100001|)(|xEr测量测量10m10m物体的相对误差为物体的相对误差为%1.010001|)(|xEr相对误差更能刻画误差的特性，在实际问题中更为关注。相对误差更能刻画误差的特性，在实际问题中更为关注。杨改兰杨改兰课程内容课程内容二、误差与有效数字二、误差与有效数字 有效数字有效数字四舍五入四舍五入定义：定义：如果如果lxx1021*则说则说 近似表示近似表示 准确到小数后第准确到小数后第 位，并从这位，并从这由上述定义由上述定义2102172.2e5102171828.2e*xx第第 位位起直到最左边的非零数字之间的一切数字都起直到最左边的非零数字之间的一切数字都称为称为有效数字有效数字并把有效数字的位数称为并把有效数字的位数称为有效位数有效位数。准确到小数后第准确到小数后第2位位准确到小数后第准确到小数后第5位位ll课程内容课程内容二、误差与有效数字二、误差与有效数字定义定义:*121210101010mnnxaaa *若近似值若近似值 的误差限是某一位的半个单位的误差限是某一位的半个单位,*x也即，若也即，若*1102m nxx有有 位位有效数字。有效数字。n*x其中，其中，是是1 1到到9 9中的一个数字；中的一个数字；是是0 0到到9 9中一个数字；中一个数字；为为整数，且整数，且 1a2naam该位该位到到 的的左边左边第一位非零数字共有第一位非零数字共有 位位,*xn就说就说 有有 位位有效数字有效数字。*xn课程内容课程内容二、误差与有效数字二、误差与有效数字取取 作作 的近似值，的近似值，就有三位有效数字；就有三位有效数字；*3.14x*x取取 作作 的近似值，的近似值，就有五位有效数字。就有五位有效数字。*3.1416x*x例：例：5位有效数字的近似值位有效数字的近似值358.467 358.467 358.47358.470.00427511 0.00427511 0.00427510.00427518.000034 8.000034 8.00008.00008.0000348.00003410103 3 8000.08000.0课程内容课程内容二、误差与有效数字二、误差与有效数字 误差限与有效数字的关系误差限与有效数字的关系Th1.1Th1.1：对于用对于用 式表示的近似数式表示的近似数 ,*x若若 具有具有 位有效位有效数字，数字，n*xnmxxxE1021|*|)(|则其则其绝对绝对误差误差限限为为所以，当所以，当 一定时，一定时，m有效位数字位数有效位数字位数 越多，越多，其绝对误差限越小。其绝对误差限越小。n课程内容课程内容二、误差与有效数字二、误差与有效数字 则则 至少具有至少具有 位位有效数字。有效数字。*xn数字，则其数字，则其相对误差限相对误差限为为Th1.2Th1.2：对于用对于用 式表示的近似数式表示的近似数 ,若若 具有具有 位位有效有效*xn*x反之反之，若，若 的的相对误差限相对误差限为为*x)1(1*1021|)(|nraxE)1(1*10)1(21|)(|nraxE课程内容课程内容二、误差与有效数字二、误差与有效数字证明：证明：反之反之,由由有有 位位有效数字。有效数字。n则则 至至少少*x*121210101010mnnxaaa 因为因为则有则有111110)1(|*|10mmaxa所以所以）1(111*102110102/1|*|*|)(nmnmraaxxxxE)(|*|*|*xExxxr）（1(1111012110)1(nmaanm 1021课程内容课程内容二、误差与有效数字二、误差与有效数字Th1.3Th1.3：反之反之,若若 的的相对误差的绝对值相对误差的绝对值大于大于 ，*x1102n有有 位位有效数字。有效数字。n则则 至至多多*x则则 的的相对误差的绝对值相对误差的绝对值必大于必大于 ;11102n*x设设mnnaaaax10.0*121其中其中 为整数为整数,为为正整数正整数,。nm01a若若 至多有至多有 位位有效数字有效数字,即即 是是有效数字有效数字,*xnna而而 不是不是有效数字有效数字,1na课程内容课程内容二、误差与有效数字二、误差与有效数字证明：证明：不是有效数字不是有效数字 反之反之,若若 则则 1*1102m nx 1110210m nm 11102n*1102nxxx1110102nm11102m n 11102mn1na因为因为|*|*|)(*xxxxErn1021即即 至多至多有有 位位有效数字有效数字.*xn 不是不是有效数字，有效数字，1na所以所以|*|*|)(*xxxxEr课程内容课程内容1 误差与数值计算的误差分析误差与数值计算的误差分析 三、数值计算的误差估计三、数值计算的误差估计 单元函数的误差传播单元函数的误差传播变量近似变量近似2022-11-5xx*)(*)(*xfyxfy相关性相关性？TaylorTaylor展开展开，.)*(!2)()*)()(*)(2xxxfxxxfxfxf近似近似，)*)()*()(xxxfxfxf*)(yyyE)(xf函数值近似函数值近似结果误差结果误差，)(xE测量误差测量误差y=f(x)课程内容课程内容三、数值计算的误差估计三、数值计算的误差估计2022-11-5所以，所以，绝对误差限绝对误差限|)(|yEr|*|)(|yyyE类似地，相对误差类似地，相对误差，|)(|)(|)(|xfxExfyyyyEr*)(*)()(xxyxf相对相对误差限误差限，|)(|)(|)(|xExfxxfr，|)(|)(|xfxxfyxyx，)()()(xExfxxfrxx*真实真实误差误差估计估计误差误差f(x)课程内容课程内容三、数值计算的误差估计三、数值计算的误差估计 多元函数的误差估计多元函数的误差估计由由TaylorTaylor展开估计展开估计,可微函数可微函数 ,如果如果12,nx xx),.,(21nxxxfy 的近似值的近似值为为 ,则则 的近似为的近似为*12,nx xxy*)*,.,*,(*21nxxxfy于是函数于是函数值值 的的绝对误差绝对误差*y)(yE*)(yyyE*)*,.,*,(),.,(2121nnxxxfxxxfniiiinxxxxxxf121*)(*)*,.,*,(增长因子增长因子niiixExf1)()*(*)(*)*)*,.,*,(121iiniiinxxEyxxxxxf课程内容课程内容三、数值计算的误差估计三、数值计算的误差估计 另外，相对误差估计式为另外，相对误差估计式为绝对误差限绝对误差限为为*)()(yyEyErniiixExfyE1|)(|)*(|)(|增长因子增长因子)()*(*1irniiixExfyx相对误差限相对误差限为为|)(|)*(|*|)(|1irniiirxExfyxyE课程内容课程内容三、数值计算的误差估计三、数值计算的误差估计 四则运算的误差估计四则运算的误差估计1 1）和、差的误差）和、差的误差2121),(xxxxfy|)(|)(|1121xExxx|)(|)(|21xExE|)(|)(|1211121xExxxxxxr|)(|)(|22121211xExxxxExxxrra)a)当当 和和 同号，同号，1x2x2121|0|0|2211xxxxyxxxxb)b)当当 和和 异号（相当于减法），且异号（相当于减法），且 1x2x021 xx，1|0|222211xxxxxx则则有有21xxy相对误差放大，尽量相对误差放大，尽量避免相近的数相减避免相近的数相减!|)(|)(|2221xExxx|)(|yE|)(|)(|2212221xExxxxxxr|)(|yEr讨论：讨论：课程内容课程内容三、数值计算的误差估计三、数值计算的误差估计2 2）积的误差）积的误差2121),(xxxxfy|)(|)(|1121xExxx|)(|)(|2112xExxEx|)(|)(|2212221xExxxxxxr|)(|)(|21xExErr乘以大数，放大乘以大数，放大绝对误差绝对误差3 3）商的误差）商的误差2121/),(xxxxfy|)(|)/(|1121xExxx|)(|/|)(|1/|222112xExxxEx除以小数，放大除以小数，放大绝对误差绝对误差|)(|/)/(|1211121xExxxxxxr|)(|)(|21xExErr相对误差不变相对误差不变相对误差不变相对误差不变|)(|)(|2221xExxx|)(|yE|)(|yEr|)(|)(|1211121xExxxxxxr|)(|)/(|2221xExxx|)(|yE|)(|/)/(|2212221xExxxxxxr|)(|yEr课程内容课程内容三、数值计算的误差估计三、数值计算的误差估计例例:已已测得某场地长测得某场地长 的的值为值为 ,宽宽 的的值为值为l*110lmd ,已知已知 ,.试求试求*80dm*0.2llm*0.1ddm面积面积 的绝对误差限与相对误差限的绝对误差限与相对误差限.Sld解解:因因 其中其中*80,110,SSdmlmld,SSSlddlld由积的误差估计式得由积的误差估计式得|)(|)(|)(|*dEdslElsyE）（）（课程内容课程内容三、数值计算的误差估计三、数值计算的误差估计而而于是于是绝对误差限绝对误差限为为相对误差限相对误差限为为,2.0|)(|mlE|)(|sE|)(|sErmdE1.0|)(|227m2)1.01102.080(m|*|)(|ssE|*|)(|dlsE%31.0880027课程内容课程内容2022-11-5数值计算方法2 选用和设计算法时应遵循的原则选用和设计算法时应遵循的原则 38主要遵循的原则：主要遵循的原则：算法有效性算法有效性结果精度好结果精度好计算效率高计算效率高计算代价小计算代价小算法是否稳定？算法是否稳定？算法逻辑简单？算法逻辑简单？计算次数计算次数和存储量少？和存储量少？课程内容课程内容2022-11-5数值计算方法2 选用和设计算法时应遵循的原则选用和设计算法时应遵循的原则 39一、选用数值稳定的计算公式一、选用数值稳定的计算公式 数值计算在设计算法时首先关心的是由它数值计算在设计算法时首先关心的是由它产生的计算结果的稳定性，而算法的稳定性与产生的计算结果的稳定性，而算法的稳定性与舍入误差是否增长密切相关。一个算法如果输舍入误差是否增长密切相关。一个算法如果输入数据有微小扰动（即误差），而在计算过程入数据有微小扰动（即误差），而在计算过程中舍入误差不增长，则称此算法是中舍入误差不增长，则称此算法是数值稳定的数值稳定的，否则称其为，否则称其为数值不稳定数值不稳定。算法的数值稳定性算法的数值稳定性课程内容课程内容2022-11-5数值计算方法一、选用数值稳定的计算公式一、选用数值稳定的计算公式40例：例：求定积分求定积分 10(0,1,2,8)5nnxIdx nx的值的值.解：解：直接积分可产生直接积分可产生递推公式递推公式若取初值若取初值)2.1ln(5ln6lndx51100 xI11105515(1)5nnnxIxdxIxn课程内容课程内容2022-11-5数值计算方法一、选用数值稳定的计算公式一、选用数值稳定的计算公式41可得可得递推公式递推公式)8,2,1(,51)2.1ln(10nInIInn按公式就可以逐步算出按公式就可以逐步算出101 50.09II 05.052112II083.053123II165.054134II025.155145II952.456156IIWhat happened?!不稳定的算法不稳定的算法 ！注意此公式注意此公式精确精确成成立，且立，且0nI 课程内容课程内容2022-11-5数值计算方法一、选用数值稳定的计算公式一、选用数值稳定的计算公式42NYBJ蝴蝶效应蝴蝶效应这是一个这是一个病态病态问题，根源在于问题，根源在于误差的传播、积累和放大误差的传播、积累和放大。纽约的一只蝴蝶翅膀一拍，风和日纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了丽的北京就刮起台风来了？！？！课程内容课程内容2022-11-5数值计算方法一、选用数值稳定的计算公式一、选用数值稳定的计算公式43递递推推公式公式的稳定性分析的稳定性分析1501II原式为原式为近似式近似式1501II0I为原始数据读入的计算机数为原始数据读入的计算机数于是：于是：5-5-0011）（IIII舍入误差舍入误差进一步进一步2/2/15151212IIII21122)5-(-5-）（IIII误差传播公式误差传播公式nnnnnIIII)5-(-5-11）（7105.09765625)5-(10不稳定！不稳定！误差指数误差指数放大！放大！课程内容课程内容2022-11-5数值计算方法一、选用数值稳定的计算公式一、选用数值稳定的计算公式44由误差传播公式可由误差传播公式可看出，看出，的的误差放大误差放大了了1nI5 5倍倍后传给后传给 ，因而初值，因而初值 的误差对以后各步的误差对以后各步nI0I这就造成这就造成 的计算结果的计算结果严重失真。严重失真。4I计算结果的影计算结果的影响，随着响，随着 的增大愈来愈严重。的增大愈来愈严重。n要怎么做才能解决这个问要怎么做才能解决这个问题呢题呢?课程内容课程内容2022-11-5数值计算方法一、选用数值稳定的计算公式一、选用数值稳定的计算公式45可求得可求得I9 0.017，按改写后的公式可逐次求得按改写后的公式可逐次求得不妨设不妨设I9 I10，于是由于是由逆递逆递推推公式公式)1(511nnInI)101(51109II将公式将公式变为变为nIInn151课程内容课程内容2022-11-5数值计算方法一、选用数值稳定的计算公式一、选用数值稳定的计算公式46I8 0.019 I7 0.021I6 0.024 I8 0.028I4 0.034 I3 0.043I2 0.058 I1 0.088I0 0.182 稳定的算法稳定的算法 ！在我们今后的讨论中，在我们今后的讨论中，误差误差将不可回避，将不可回避，算法的算法的稳定性稳定性会是一个非常重要的话题。会是一个非常重要的话题。误差指数误差指数减小！减小！课程内容课程内容2022-11-5数值计算方法一、选用数值稳定的计算公式一、选用数值稳定的计算公式47注：注：递推递推公式公式的的舍入误差以舍入误差以5的幂次增长进行的幂次增长进行传播，因此是传播，因此是数值不稳定的，数值不稳定的，而而逆递逆递推推公式公式的的舍入误差在一定范围内以舍入误差在一定范围内以0.2的幂次进行传的幂次进行传播，随着播，随着n的增大，误差逐步减少，因此该算的增大，误差逐步减少，因此该算法是法是数值稳定的数值稳定的。因此，可以看出数值不稳定的算法是不能使用因此，可以看出数值不稳定的算法是不能使用的，实际计算中对任何输入数据都是数值稳定的算的，实际计算中对任何输入数据都是数值稳定的算法，称为法，称为无条件稳定。无条件稳定。而对某些数据数值稳定，对而对某些数据数值稳定，对其它数据数值不稳定的算法，称为其它数据数值不稳定的算法，称为条件稳定条件稳定。课程内容课程内容2022-11-5数值计算方法二、注意选择适当的算法二、注意选择适当的算法48如果算法效率低，则计算量大，精度一般也降低，如果算法效率低，则计算量大，精度一般也降低，这是由于计算过程中的这是由于计算过程中的误差积累。误差积累。例：例：333323213123232221211313212111bxaxaxabxaxaxabxaxaxa33323232221312111aabaabaabDx 33331232211311121abaabaabaDx 33231222211121131baabaabaaDx 333231232221131211aaaaaaaaaD Cramer法则法则线代理论线代理论计算速度百万亿次计算速度百万亿次(10 14flops)，计算量为：乘法计算量为：乘法(n+1)(n-1)n!次，加法次，加法(n+1)n!次。次。n=20时，乘法次数为时，乘法次数为211920!9.71020，需要需要106秒秒 100天。天。课程内容课程内容2022-11-5数值计算方法二、注意选择适当的算法二、注意选择适当的算法49适当的算法能极大的减小计算量适当的算法能极大的减小计算量解法解法 乘法乘法 加法加法 年代年代 耗时耗时Gauss-Jordan n3/2 次次 n3/2 次次Gauss n3/3 次次 n3/3 次次1950s 90天天Gauss-Seidel Iteration O(n2)1960s 1秒秒 Wave Front Method(FEM)O(n ln n)1970s 10-5秒秒 Incomplete Facterization O(n ln n)1980s 10-5秒秒 Multigrid Method O(n)1980s 10-6秒秒 例：例：3D FEM，n=102102102=10=106 6(百万节点百万节点)，10 12flops课程内容课程内容2022-11-5数值计算方法三、简化计算步骤避免误差积累三、简化计算步骤避免误差积累50一般来说一般来说，算法的计算量（次数）愈小，算法的计算量（次数）愈小例例1：多项式求值：给定的多项式求值：给定的x 求下列求下列n 次多项式的值。次多项式的值。nnxaxaxaaxP2210)(解：解：1.1.用一般算法，即直接求和法；用一般算法，即直接求和法；舍入误差积累机会愈小舍入误差积累机会愈小计算耗费机时愈小计算耗费机时愈小nnxaxaxaaxP2210)(乘法：乘法：1 2 n=n(n+1)/21 2 n=n(n+1)/2次次加法：加法：1 1 1=n1 1 1=n次次运算速度：运算速度：exp ,课程内容课程内容2022-11-5数值计算方法三、简化计算步骤避免误差积累三、简化计算步骤避免误差积累51算法的递推性算法的递推性计算机上使用的算法常采用计算机上使用的算法常采用递推化递推化的形式，的形式，递推化的基本思想是递推化的基本思想是把一个复杂的计算过程把一个复杂的计算过程归结为简单过程的多次重复。这种重复在程序归结为简单过程的多次重复。这种重复在程序上表现为循环。递推化的优点是简化结构和节上表现为循环。递推化的优点是简化结构和节省计算量。省计算量。课程内容课程内容2022-11-5数值计算方法三、简化计算步骤避免误差积累三、简化计算步骤避免误差积累52解解：2.2.秦九韶方法秦九韶方法(即即HornorHornor算法）算法）:乘法：乘法：1 1 1=n1 1 1=n次次加法：加法：1 1 1=n1 1 1=n次次).)()(1210nnaaxaxaxaxPn-1个个例例2：三角函数逼近三角函数逼近02642)!2()1(.!6!4!21cosnnnnxxxxx2|2|xx直接计算直接计算利用三角函数的周期性延拓得到利用三角函数的周期性延拓得到否者正负交错级数不易收敛，易导致计否者正负交错级数不易收敛，易导致计算次数过多，有效位数丢失而降低精度算次数过多，有效位数丢失而降低精度课程内容课程内容2022-11-5数值计算方法三、简化计算步骤避免误差积累三、简化计算步骤避免误差积累53实例实例：用秦九韶方法求用秦九韶方法求多项多项式，式，x=-0.2。543200833.004167.016667.05.01)(xxxxxxP解：解：Ka5-KvK00.008330.00833v0=a510.041670.04v1=v0 x+a420.166670.15867v2=v1x+a330.50.46827v3=v2x+a2410.90635v4=v3x+a1510.81873v5=v4x+a0课程内容课程内容2022-11-5数值计算方法三、简化计算步骤避免误差积累三、简化计算步骤避免误差积累54例例3 3:求求10001)1(1nnn若直接逐项求和，运算次数多且误差积累可观若直接逐项求和，运算次数多且误差积累可观。可化简为可化简为10001)1(1nnn1001111 1次除法和次除法和1 1次加法！次加法！10001)111(nnn课程内容课程内容2022-11-5数值计算方法三、简化计算步骤避免误差积累三、简化计算步骤避免误差积累55若直接逐项求和，若直接逐项求和，计算项数计算项数 n 1000才可满足误差要求。才可满足误差要求。令令例例4 4:求求1)2/1(1nnn，要求误差小于，要求误差小于1010-6-6.1)(1)(nxnnxf有有1)111(lim)1(1)1(1NnnfNn)1(1)(1)1()(1nnxnnfxfn1)(1(1)1(nxnnnx利用上式求解，满足误差要求仅需利用上式求解，满足误差要求仅需70余项！余项！课程内容课程内容2022-11-5数值计算方法四、尽量避免两个相近的数相减四、尽量避免两个相近的数相减56在数值计算中，两个相近的数作减法时在数值计算中，两个相近的数作减法时有效数字会损失有效数字会损失。例例1 1:求求xxy1的值。的值。当当x=1000，y 的准确值为的准确值为0.01580 02.062.3164.3110001001y(1)直接相减直接相减只有只有1位有效数字位有效数字课程内容课程内容2022-11-5数值计算方法四、尽量避免两个相近的数相减四、尽量避免两个相近的数相减57类似地类似地 yxyxlnlnln2sin2cos2sin)sin(xxx(2)若若将将原式原式改写为改写为xxy1则则 y=0.01581有有3 3位有效数字！位有效数字！xx11课程内容课程内容2022-11-5数值计算方法五、绝对值太小的数不宜作除数五、绝对值太小的数不宜作除数58例：例：2.2718001.07182.2如分母变为如分母变为0.0011，也即分母只有，也即分母只有0.0001的变化时的变化时1.24710011.07182.22718.22471.1247.1结果相差这么结果相差这么大大!课程内容课程内容2022-11-5数值计算方法六、防止大数六、防止大数“吃吃”小数小数59精确解为精确解为110291 x,x 算法算法1 1：利用求根公式：利用求根公式aacbbx242010)110(992xx课程内容课程内容2022-11-5数值计算方法六、防止大数六、防止大数“吃吃”小数小数60在计算机内，在计算机内，109存为存为0.1 1010，1存为存为0.1 101。做做加加02422aacbbx109+1 法法时，两加数的指数先向大指数对齐，再将时，两加数的指数先向大指数对齐，再将浮点浮点部分部分相加。相加。即即1 的指数部分须变为的指数部分须变为1010，则，则：取取单精度时就成为：单精度时就成为：1=0.0000000001 1010，=0.10000000 1010,1024921aacbbx=0.10000000 1010+0.00000000 1010课程内容课程内容2022-11-5数值计算方法六、防止大数六、防止大数“吃吃”小数小数61算法算法2 2：先解出先解出9211024)(aacbbsignbx再利用再利用acxx21求和时从小到大相加，可使和的误差减小。求和时从小到大相加，可使和的误差减小。例例2 2：按从小到大、以及从大到小的顺序分别计算按从小到大、以及从大到小的顺序分别计算1+2+3+40+109110109912xacx2022-11-562数值计算方法&教材教材 现代数值计算方法现代数值计算方法 肖筱南等编著（北京大学出版社肖筱南等编著（北京大学出版社）&参考书目参考书目 实用计算方法实用计算方法 张善杰等编著（南京大学出版社）张善杰等编著（南京大学出版社）数值分析方法数值分析方法 奚梅成奚梅成 刘儒勋刘儒勋 （中国科学技术大学出版社）（中国科学技术大学出版社）现代科学与工程计算现代科学与工程计算 孟大志孟大志 刘伟刘伟(高等教育出版社高等教育出版社)数值分析与科学计算数值分析与科学计算 Jeffery J.Leader Jeffery J.Leader 著，张威，刘志军，著，张威，刘志军，李艳红等译，（清华大学出版社李艳红等译，（清华大学出版社)2022-11-563数值计算方法课程内容课程内容2022-11-5数值计算方法课程内容课程内容64定义：定义：数值计算方法也称计算方法或数值方法，数值计算方法也称计算方法或数值方法，是研究科学与工程技术中数学问题的数值解及是研究科学与工程技术中数学问题的数值解及其理论的一个数学分支。其理论的一个数学分支。主要任务：主要任务：研究适用于在计算机上实现的数值计算研究适用于在计算机上实现的数值计算方法及与此相关的理论，如方法的方法及与此相关的理论，如方法的收敛性、稳定收敛性、稳定性及误差分析、计算效率性及误差分析、计算效率等。等。解决科学问题的步骤：解决科学问题的步骤：物理问题数学模型数值解程序设计数值计算方法