第1章数值分析与科学计算引论.

数值分析NumericalAnalysis数值分析简史•1955周恩来领导10年科技规划，提出发展几个新技术，包括计算技术（计算机，程序设计，计算数学），半导体技术，自动化技术。•1956成立计算技术研究所筹备处，主任华罗庚，手下有两个组（计算机与计算数学）。在其领导下于数学所成立计算方法讨论班。•1958计算所成立，带半军事性质，并且与苏联合作在中科院计算研究所造出104机。北大，吉大，复旦，南大相继成立计算数学专业。57－59年吉大聘请苏联梅索夫斯基开办讲义班，其中参与者有李荣华，冯果忱，李岳生，李庆扬，蒋尔雄，康立山，徐翠薇等。数值分析简史1977年开始写国内的教材•李荣华，冯果忱《微分方程数值解》•李岳生等《数值逼近论》•曹志浩等《数值代数》和《矩阵计算与方程求根》这三门课程为1984年在国内几所重点大学开设的“计算数学及其应用软件专业主干课程。信息与计算科学简史•1958年计算数学专业•1984年“计算数学及其应用软件”加强计算机课程的分量•1998年“信息与计算科学”加强信息课程的分量•信息与计算科学，就其范畴与研究内容而言，是数学、计算机科学、信息工程等广泛学科的交叉，远超出数学学科的范围。•作为数学学科下的一个理科专业，信息与计算科学专业应该主要研究信息技术的核心基础与运用现代计算工具高效求解科学与工程问题的数学理论与方法（或更简明地说，研究定向于信息技术、计算技术的数学基础）。当今主流研究分支1.微分方程数值解是信息与计算数学的主要分支。（气象、物理、力学等诸多领域）1.数值代数和最优化是科学计算、运筹学的基础学科。（在材料科学,生命科学,信息科学,交通,通讯以及金融中的计算问题）2.反问题无疑是最热门的方向之一。（图像处理，信号处理）3.计算数学的应用型分支：与具体的应用结合形成新的学科，比如说计算流体力学、计算空气动力学、计算力学、计算物理。中国计算数学•冯康(1920—1993)•有限元方法•辛几何算法•中国近代数学能超越西方或与之并驾齐驱的主要原因有三个，主要是讲能够在数学历史上很出名的有三个：一个是陈省身在示性类方面的工作，一个是华罗庚在多复变函数方面的工作，一个是冯康在有限元计算方面的工作。---丘成桐，中国数学发展之我见1998,3,11，中国科学报(丘成桐,哈佛大学教授，Fields奖获得者)•“在当代世界科技发展的史册上，我国科技工作者也书写了光辉的篇章。在数学领域创立的多复变函数的调和分析，有限元方法和辛几何算法，示性类及示嵌类的研究数学机械化与证明理论，关于哥德巴赫猜想的研究，在国际上都引起了强烈反响。”---江泽民,在两院院士大会上的讲话,2002,5,28.中国计算数学院士•石钟慈院士---非协调有限元方法•林群院士-----外推方法•崔俊芝（工程院院士）---数值计算数值分析课程所需的基础•数学分析、泛函分析•高等代数、矩阵分析•常微分方程、数学物理方程•高级程序设计语言•提问：数值分析是做什么用的？数学建模构造算法程序设计上机计算求出结果实际问题近似解输入复杂问题或运算......),(,)(,,ln,,xfdxddxxfbxAxaxbax数值分析计算机第一章数值分析与科学计算引论§1数值分析的对象、作用与特点一、研究对象数值分析也称计算方法.它根椐实际问题的数学模型提出求解问题的数值计算方法.二、学科特点算法能在计算机上实现，并有好的计算复杂性；面向计算机，提供切实可行的有效算法；有可靠理论，对算法进行误差分析，并能达到精度要求；通过数值实验证明算法行之有效；利用MATLAB等软件在计算机上实现数值计算，解决实际问题.三、实际应用§2数值计算的误差一.来源与分类从实际问题中抽象出数学模型——模型误差通过测量得到模型中参数的值——观测误差求(数学表达的)近似解——方法误差(截断误差)模型的准确解与用数值方法求得的准确解之差称为“截断误差”。机器字长有限——舍入误差简化…实际算法:有限、四则运算化…（理论计算误差）dxex102近似计算:例大家一起猜？dxe2x1011/e解：将作Taylor展开后再积分2xe91!4171!3151!21311)!4!3!21(10864210dxxxxxdxe2xS4R4,104Sdxe2x取则111!5191!414R称为截断误差005091!414.R这里7430024010333014211013114....S0010200050..|舍入误差|006000100050102...dxe-x的总体误差计算=0.747……由截去部分引起由留下部分引起二.传播与积累例：蝴蝶效应——武汉的一只蝴蝶翅膀一拍，风和日丽的上海就刮起台风来了？！WHSH以上是一个病态问题关于本身是病态的问题，我们还是留给数学家去头痛吧！......210110,,,n,dxexeIxnn例：计算11nnInI公式一:注意此公式精确成立632120560111100.edxeeIx记为*0I80001050.IIE则初始误差111111110010nI)e(ndxexeIdxexennnn391414231519594249414122764807131632896000121030592000111088128000101............367879440111415*13*14*12*13*11*12*10*11*9*10*0*1.II.II.II.II.II.II.II????!!!发生了什麽?!考察第n步的误差nE|)1()1(|||||*11*nnnnnnInIIIE||!01En||Enn我们有责任改变。造成这种情况的是不稳定的算法迅速积累,误差呈递增走势.可见初始的小扰动801050||.E)1(1111nnnnInIInI公式二:注意此公式与公式一在理论上等价。方法：先估计一个IN,再反推要求的In(nN)。11)1(1NINeNNNINNeI11)1(121*可取0*NNNIIEN,时当632120560)1(11367879440)1(210838771150)1(1110773517320)1(1210717792140)1(1310668702200)1(1410638169180)1(151042746233016116121*1*0*2*1*11*10*12*11*13*12*14*13*15*14*15.II.II.II.II.II.II.II.eI取我们很幸运！考察反推一步的误差：||1)1(1)1(1||*1NNNNENININE以此类推，对nN有：||)1(...)1(1||NnEnNNE误差逐步递减,这样的算法称为稳定的算法。在我们今后的讨论中，误差将不可回避，算法的稳定性会是一个非常重要的话题。三、误差与误差限绝对误差xxe**其中x为精确值，x*为x的近似值。10006074302..dxex，例如：**εxx上常记为||*e*ε，称为绝对误差限，一般地，的上限记为注：e*理论上讲是唯一确定的，可能取正，也可能取负。e*0时，x*称为强近似值，e*0时，x*称为弱近似值e*0不唯一，当然e*越小越具有参考价值。由于通常准确值x是不知道的，所以误差e*的准确值也不可能求出，但根据具体情况，可事先估计出误差的范围——误差绝对值不能超过某个正数，我们把叫做误差绝对值的“上界”，或称“误差限”。****x≤x≤**x││xx*≤*工程四、相对误差与相对误差限xeer**||***xεεrx的相对误差限常定义为注：从的定义可见，实际上被偷换成了，而后才考察其上限。那么这样的偷换是否合法？严格的说法是，与是否反映了同一数量级的误差？关于此问题的详细讨论可见教材p5。*r*re**xexe***xe***xeer实际计算中，相对误差通常取为：相对误差五、有效数字若近似值x*的误差限是某一位的半个单位,该位到x*的第一位非零数字共有n位,就说x*有n位有效数字.1415.3*;8979321415926535.3例:问：有几位有效数字？请证明你的结论。*43*用科学计数法，记（其中）。若（即的截取按四舍五入规则），则有n位有效数字，精确到。mnaa.ax10021*01anm.xx1050||*na*xnm10六、有效数字与相对误差的关系有效数字相对误差限11121102102101001050*nnmnnmra.aaa.a.x*ε*ε已知x*有n位有效数字，则其相对误差限为相对误差限有效数字nmmnmnr.aaa.aaxεxx105010)1()1(210100)1(210|*|*|*|111121111110)1(21*nraε已知x*的相对误差限可写为则可见x*至少有n位有效数字。1、代数运算的误差估计七误差估计1.1加法和减法结果的误差则有和的误差分别为与设近似数),()(****yexeyx)()()()(****yyxxyxyx)()()(****yexeyxe于是)()()(****yxyx注：和与差的相对误差的估计，相对稍稍复杂一点，其结果更有意思。留待后述。误差限:2、函数值的误差估计问题：对于y=f(x)，若用x*取代x，将对y产生什么影响？分析：e*(y)=f(x*)f(x)e*(x)=x*xMeanValueTheorem=f’()(x*x)x*与x非常接近时，可认为f’()f’(x*)，则有：|e*(y)||f’(x*)|·|e*(x)|即：x*产生的误差经过f作用后被放大/缩小了|f’(x*)|倍。故称|f’(x*)|为放大因子（amplificationfactor）或绝对条件数（absoluteconditionnumber）.)()()()!1(1)()()())((!1)()(][)(1)1(0)()1(baaxfnxRbxaxRaxafkxfxfbxanbaxfnnnnnkkkn式中，则时有有限导数阶的连续导数，当上有定义，且有一直到，在闭区间若函数附：泰勒公式当自变量有误差时，计算函数值的误差（限）也可利用函数的泰勒展开式进行估计.)()())((***xxfxf数的误差限的高阶项，可得计算函忽略)(*x)(*之间与介于xx)(2)()()()()()(2)())(()()(*2***2****xfxxfxfxfxxfxxxfxfxf*)()(*|)(|xfyey*er*)(*|)(|xxex*er)(**)(*)(****)(**)(*)(xexfxfxxxxxfxxxxfxfr相对误差条件数f的条件数在某一点是小\大，则称f在该点是好条件的\坏条件的。对函数值的相对误差（限），我们可有：为的误差于是函数值，的近似值为，则的近似值为，而为多元函数时，若当)(),,(,,,,),,(****2*1***2*12121AeAxxxfAAxxxxxxxxxfAfnnnn的相对误差限为而*A**11***11**1**),,(),,(),,()(knkknkkkknnnexfxxxxxfxxfxxfAAAe；)()(*1**knkkxxfA