董波老师-大连理工大学-矩阵数值分析课件第一章

大连理工大学研究生教育大楼矩阵与数值分析大连理工大学工科硕士研究生数学公共基础课程授课教师基本信息•姓名：董波•工作单位：数学科学学院•办公地点：创新园大厦（大黑楼）B1113室•EMAIL:[e-mail]创业园大厦主讲教材参考书目(Reference)科学和工程计算基础施妙根顾丽珍编著（清华大学出版社）数值方法（MATLAB版）[美]陈渝等译李晓梅审校（电子工业出版社）矩阵论简明教程许仲张凯院等编著科学出版社John.H.MathewsKurtisD.Fink课程的总成绩考核要求期末考试平时作业数值实验占20%；占10%；占70%；第1章绪论作业：P272、3、7、8、10、12（3）、13222222344ccxxbbacbbac、（2）第1章绪论1.1计算机科学计算研究对象与特点1.2误差分析与数值方法的稳定性1.3向量与矩阵的范数科学计算、理论计算和实验并列为三大科学方法。我们所学习的内容属于一门新学科——科学计算。即现代意义下的计算数学。主要研究在计算机上可计算的有效算法及相关理论。1.1计算机科学计算研究对象与特点主要内容包括：微分方程数值解法本课程主要研究用计算机求解各种数学问题的数值计算方法及其理论与软件实现数值代数数值逼近（数值微分积分）bAxxfxfxxfxbad00,,utuutfu矩阵分析简介0kkA0kkAAAAsin、efdttdAdttba)(A三、有好的计算复杂性，既要时间复杂性好，是指节省时间，又要空间复杂性好，是指节省存储量，这也是建立算法要研究的问题，它关系到算法能否在计算机上实现。解决实际问题：一、构造计算机可行的有效算法二、给出可靠的理论分析，即对任意逼近达到精度要求，保证数值算法的收敛性和数值稳定性，并可进行误差分析。四、数值实验，即任何一个算法除了从理论上要满足上述三点外，还要通过数值试验证明是行之有效的。考察线性方程组的解法什么是有效算法？nnnnnnbxaxaxa221122222121bxaxaxann11212111bxaxaxannDiDAdetiAdetix1,2,,,in（D≠0）第i列iDD理论非常漂亮计算n+1个n阶行列式111212122212nnnnnnaaaaaaaaa1112121nnnnnaaaaaa1b2bnbCramer求解法则(18世纪)Laplace展开定理11detiiininaAaAA线性方程组的求解Laplace展开定理表示元素的代数余子式ijAija实际计算困难（运算量大得惊人）1kkmkkm于是，我们有1211nnnmnnmnnnnm112132nnnnnnnn!n利用Cramer法和Laplace展开定理来求解一个n阶线性方程组，所需的乘法运算次数就大于设计算阶行列式所需要的乘法运算的次数为，则kmk(1)!(1)!nnn总的的乘法运算次数将达：若使用每秒百亿次的串行计算机计算,一年可进行的运算应为：26！=4.0329×1026（次）13(亿年)365(天)×24(小时)×3600(秒)×1010≈3.1536×1017（次）求解25阶线性方程组共需要耗费时间为：264.032910173.15361091.278810它远远超出目前所了解的人类文明历史！这就是研究数值方法的必要性随着科学技术的发展，出现的数学问题也越来越多样化，有些问题用消去法求解达不到精度，甚至算不出结果，从而促使人们对消去法进行改进，又出现了主元消去法，大大提高了消去法的计算精度。而著名的Gauss消元法，它的计算过程已作根本改进，成为有效算法，使得可在不到一秒钟之内即可完成上述计算Cramer算法是“实际计算不了”的。任务。1.2误差分析与数值方法的稳定性1.2.1误差来源与分类1.2.2误差的基本概念和有效数字1.2.3函数计算的误差估计1.2.4数值方法的稳定性和避免误差危害的基本原则1.2.1误差来源与分类用计算机解决科学计算问题时经常采用的处理方式是将连续的问题离散化、用有限代替无限等，并且用数值分析所处理的一些数据，不论是原始数据，还是最终结果，绝大多数都是近似的，因此在此过程中，误差无处不在。实际问题数学模型计算机数值结果编程实现算法数值计算方法计算机科学计算的流程图模型误差方法误差或称为截断误差观测误差舍入误差型的解之间的误差生的误差，如用有限代替无限的过程所产生的误差1．模型误差2.截断误差由实际问题抽象出数学模型，要简化许多条件，这就不可避免地要产生误差．实际问题的解与数学模从数学问题转化为数值问题的算法时所产x2xe例如，求的值的运算，我们可用无穷级数：我们可用它的前项和1n截断误差则数值方法的误差是2xe，近似代替函数给定2xe!!3!212642nxxxxn=!!3!212642nxxxxn!112nxnxsxsexRxn210,!1122nxxne计算过程中也可能产生误差测手段的限制，得到的数据必然有误差3.观测误差4.舍入误差例如，就是舍入误差。21.41420.0000135E产生的误差用1.4142近似代替，2初始数据大多数是由观测而得到的。由于观以计算机为工具进行数值运算时，由于计算机的字长有限，原始数据在计算机上的表示往往会有误差，在1.41421351.4142模型和观测两种误差不在本课程的讨论范围这里主要讨论算法的截断误差与舍入误差，而截分析初始数据的误差通常也归结为舍入误差研究计算结果的误差是否满足精度要求就是：断误差将结合具体算法讨论误差估计问题1.2.2误差的基本概念和有效数字ax称aeax绝对误差界绝对误差（误差）它总是正数。定义定义ea使得若有常数设为精确值，x为的一个近似值，xa为近似值的绝对误差，简称误差。a误差可正可负。ax因此误差也未知。ax通常准确值是未知的，x设为精确值，x为的一个近似值，xa则叫做近似值的误差界（限）。aea例如，用毫米刻度的米尺测量一长度x，读出和该长度接近的刻度a，a是x的近似值，它的误差界是0.5mm，于是有0.5xamm如若读出的长度为765mm，则有，5.0765x虽然从这个不等式不能知道准确的x是多少，但可知绝对误差界,5.7655.764x结果说明x在区间[764.5，765.5]内。对于一般情形，aeax即可以表示为aae也可以表示为。aeax但要注意的是，误差的大小并不能完全表示近似值的好坏。x,aea实际计算中，如果真值未知时，x若，0x称为近似值a的相对误差。作为a的相对误差，条件是较小。xax通常取相对误差（误差）则将近似值的误差与准确值的比值定义axxaxxaxa相对误差也可正可负。相对误差的绝对值上界叫做相对误差界（限），记为：相对误差界（限）aeaaxa有两个量x=3.000，a=3.100，1.0axxax，0.300xaxxax,0.310a绝对误差相对误差绝对误差相对误差则其绝对误差：00.31.0,10333.01,101.0242103.0101.0110333.0例其相对误差为：则其绝对误差：其相对误差为：又有两个量作为精确值的度量，绝对误差可能会引起误会，而相对误差由于考虑到准确值本身的大小而更有意义。其近似值,求a718.2a71828182.2e00028182.0aeae718.20003.0aae已知其绝对误差界为：相对误差界为：的绝对误差界和相对误差界。解：0.00030.0002。绝对误差界和相对误差界并不是唯一的例0001110375.0当准确值x位数比较多时，人们常常按四舍五入的原则得到x的前几位近似值a，14159265.3πx,14.31a,1416.32a那么，它们的误差界的取法应为：,102114.3π2例如00159265.01a00000735.02a.10211416.3π4误差界的取法取3位：取5位：a（1-14）一个数字，,01a（1-15）则称a为x的具有n位有效数字的近似值。定义设x为精确值，a为x的一个近似值，表示为：可以是有限或无限小数形式，其中ai(i=1,2,…,n)是0到9中的如果其绝对误差界n为正整数，k为整数，k10naaa21.01021axnk0003.0ae,27182.0107182.211a00009.01ae其绝对误差界为取3nk,4n，其绝对误差界为，31021，310212.71828182e对于，下面的各个值的有效数字的位数。12.718100.2718a取2718.01002718.01a0271828182.0x作为也具有4位有效数字。取51021000002.0ax5nk。4n的近似值，的具有4位有效字的近似值。e是a故是的具有4位有效数字的近似值。e1a有效数字位数与小数点的位置无关如果一个近似值是由精确值经四舍五入得到的，那么，从这个近似值的末尾数向前数起直到再无非零数字止，所数到的数字均为有效数字一般来说，绝对误差与小数位数有关，相对误差与有效数字位数有关其表达形式如xaaxaa（2）如果其相对误差界满足定理nkaaaa21.01011110,2na11110,2(1)na设实数为某个精确值，为它的一个近似值，ax（1）如果有位有效数字，则其相对误差界满足an则至少具有位有效数字。an由（1-14）可得到a（1-18）,102111na结论（1）成立。证1110ka1110)1(kaaaxaxa1nk102111101kaxaana1110)1(2所以如果a有n位有效数字，那么再由（1-17）和（1-18）1nkaa111110)1(210)1(,1021nk由定义1.6知，a具有n位有效数字。1.2.3函数计算的误差估计设一元函数具有二阶连续导数，()fx自变量的一个x近似值为，a作为的近似，()fa()fx其误差应如何估计？近似绝对误差估计式：ax的二次项，得到忽略axaf)(')()(afxf近似相对误差界为：'()()faxafa()()()fxfafa用Taylor展开的方法来估计其误差)()(afxf)(xf,2)()()(2'''axfaxafafaxaf)(',2)(2''axf移项取绝对值得,,,,21naaa的近似值分别为则),,,(),,,(2121nnaaafxxxf其中12(,,,).nkkafaaafxx可以估计到函数值的误差界为n元函数，如果),,,(21nxxxfnxxx,,,21自变量nk1akxf)(kkaxnk1akxfkkax),,,(),,,(2121nnaaafxxxf1212()xxaa1212xxaa1122xaxa2221112121),(),(axxfaxxfaafxxfaa从而得到四则运算的估计式：两个近似数相加减，其运算结果的精度不比原始数据的任何一个精度高计算中应尽力避免小数作除数1122xaxa211axa122axa21112222axaaxaa112xaa12222axaa2121,xxx