大连理工大学矩阵与数值分析第1章-计算方法

大连理工大学研究生教育大楼矩阵与数值分析大连理工大学工科硕士研究生数学公共基础课程授课教师基本信息•姓名：孟兆良•工作单位：数学科学学院•办公地点：创新园大厦（大黑楼）A1035室•联系电话：84708351-8035(o)•EMAIL:[e-mail]创业园大厦主讲教材参考书目(Reference)科学和工程计算基础施妙根顾丽珍编著（清华大学出版社）数值方法（MATLAB版）[美]陈渝等译李晓梅审校（电子工业出版社）矩阵论简明教程许仲张凯院等编著科学出版社John.H.MathewsKurtisD.Fink课程的总成绩考核要求期末考试平时作业数值实验占20%；占10%；占70%；知识，只有当它靠积极的思考得来而不是凭记忆得来的时候，才是真正的知识。列夫托尔斯泰第1章绪论1.1计算机科学计算研究对象与特点1.2误差分析与数值方法的稳定性1.3向量与矩阵的范数科学计算、理论计算和实验并列为三大科学方法。我们所学习的内容属于一门新学科——科学计算。即现代意义下的计算数学。主要研究在计算机上可计算的有效算法及其相关理论。本课程主要研究现代、行之有效数值方法1.1计算机科学计算研究对象与特点主要内容包括：微分方程数值解法本课程主要研究用计算机求解各种数学问题的数值计算方法及其理论与软件实现数值代数数值逼近（数值微分积分）bAx0xfxfxfxxfxbad00,,utuutfu矩阵分析简介0kkA0kkAAAAsin、efdttdAdttba)(A三、有好的计算复杂性，既要时间复杂性好，是指节省时间，又要空间复杂性好，是指节省存储量，这也是建立算法要研究的问题，它关系到算法能否在计算机上实现。课程的特点：一、构造计算机可行的有效算法二、给出可靠的理论分析，即对任意逼近并达到精度要求，保证数值算法的收敛性和数值稳定性，并可进行误差分析。四、数值实验，即任何一个算法除了从理论上要满足上述三点外，还要通过数值试验证明是行之有效的。考察，线性方程组的解法早在18世纪Cramer已给出了求解法则：Cramer’sRuler什么是有效算法？nnnnnnbxaxaxa221122222121bxaxaxann11212111bxaxaxannDiDAdetiAdetix1,2,,,in（D≠0）Cramer’sRuler第i列iDD这一结果理论上是非常漂亮的，它把线性方程组的求解问题归结果为计算n+1个n阶行列式问题。111212122212nnnnnnaaaaaaaaa1112121nnnnnaaaaaa1b2bnb对于行列式的计算，理论上又有著名的Laplace展开定理。这样理论上我们就有了一种非常漂亮的求解线性方程组的方法。然而我们做一简单的计算就会发现,由于这一方法的运算量大得惊人，以至于完全不能用于实际计算。ininiiiiAaAaAaD2211detA其中Aij表示元素aij的代数余子式。设计算k阶行列式所需要的乘法运算的次数为mk，则容易推出1kkmkkm于是，我们有1211nnnmnnmnnnnm112132nnnnnnnn!n这样，利用Cramer法和Laplace展开定理来求解一个n阶线性方程组，所需的乘法运算次数就大于在算法中运用行列展开计算，则总的的乘法运算次数将达：若使用每秒百亿次的串行计算机计算,一年可进行的运算应为：26！=4.0329×1026（次）13(亿年)365(天)×24(小时)×3600(秒)×1010≈3.1536×1017（次）以求解25阶线性方程组为例，如果用Cramer法则求解，共需要耗费时间为：264.032910173.15361091.278810（n+1）n!=(n+1)!它远远超出目前所了解的人类文明历史！这就是研究数值方法的必要性。随着科学技术的发展，出现的数学问题也越来越多样化，有些问题用消去法求解达不到精度，甚至算不出结果，从而促使人们对消去法进行改进，又出现了主元消去法，大大提高了消去法的计算精度。而著名的Gauss消元法，它的计算过程已作根本改进，成为有效算法，使得可在不到一秒钟之内即可完成上述计算Cramer算法是“实际计算不了”的。任务。1.2误差分析与数值方法的稳定性1.2.1误差来源与分类1.2.2误差的基本概念和有效数字1.2.3函数计算的误差估计1.2.4数值方法的稳定性和避免误差危害的基本原则1.2.1误差来源与分类用计算机解决科学计算问题时经常采用的处理方式是将连续的问题离散化、用有限代替无限等，并且用数值分析所处理的一些数据，不论是原始数据，还是最终结果，绝大多数都是近似的，因此在此过程中，误差无处不在。误差的来源主要从以下几个方面：实际问题数学模型计算机数值结果编程实现算法数值计算方法计算机科学计算的流程图模型误差方法误差或称为截断误差观测误差舍入误差型的解之间的误差生的误差，如用有限代替无限的过程所产生的误差1．模型误差2.截断误差由实际问题抽象出数学模型，要简化许多条件，这就不可避免地要产生误差．实际问题的解与数学模从数学问题转化为数值问题的算法时所产截断误差通常是指用一个基本表达式替换一个相当复杂的算术表达式时所引起的误差。这一术语从用截断Taylor级数替换一个复杂的算术表达式的技术中衍生而来。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误差的基本概念和有效数字设x为精确值，ax因此误差x-a也未知。称通常准确值x是未知的，为近似值a的绝对误差，简称误差。a为x的一个近似值，aeax绝对误差界误差x-a可正可负。绝对误差（误差）则叫做近似值a的误差界（限）。ae它总是正数。定义定义ea使得（1-1）设x为精确值，若有常数a为x的一个近似值，例如，用毫米刻度的米尺测量一长度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相对误差也可正可负。xaxaax是的平方项级，故可忽略不计。xaxaxxxax2)(2xax这是由于两者之差axax211xax下面我们看看相对误差的作用有两个量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例其相对误差为：则其绝对误差：其相对误差为：又有两个量上例说明绝对误差有较大变化，相对误差相同。作为精确值的度量，绝对误差可能会引起误会，而相对误差由于考虑到准确值本身的大小而更有意义。相对误差的绝对值上界叫做相对误差界（限），记为：相对误差界（限）aeaaxa其近似值,求a718.2a71828182.2e00028182.0aeae718.20003.0aae已知，因此其绝对误差界为：相对误差界为：不是唯一的。的绝对误差界和相对误差界。解：0.00030.0002。此例计算中不难发现，绝对误差界和相对误差界并例1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-2）一个数字，,01a（1-3）则称a为x的具有n位有效数字的近似值。定义1.3设x为精确值，a为x的一个近似值，表示为：可以是有限或无限小数形式，其中ai(i=1,2,…,n)是0到9中的如果其绝对误差界n为正整数，k为整数，k10naaa21.01021axnk0003.0ae，2718.0101a,27182.0107182.211a00009.01ae在例1中，而的具有4位有效字的近似值。因其绝对误差界为故a1也只是e的具有4位有效数字的近似值。再取71828182.2e3nk,4n即a是那么，可知由于a的绝对误差界为，31021，310212718.01002718.01a0271828182.0x作为也具有4位有效数字。同样我们可以分析出51021000002.0ax5nk。4n这是因为：那么，有这表明：有效数字位数与小数点的位置无关的近似值，，00.138a,0312.0b。41086.0c,1013800.03a,10312.01b。41086.0c21021ax23n5n下列近似值的绝对误差限均为0.005，问它们解：首先将它们表示成标准形式则由已知条件，各有几位有效数字？例2即a有5位有效数字；21021bx21n1n21021cx24n2n即b有1位有效数字；同理，由由即c无有效数字。,10312.01b,1086.04c如果一个近似值是由精确值经四舍五入得到的，那么，从这个近似值的末尾数向前数起直到再无非零数字止，所数到的数字均为有效数字一般来说，绝对误差与小数位数有关，相对误差与有效数字位数有关其表达形式如xaa（1-4）xaa（2）如果其相对误差界满足（1-5）（1）如果a有位n有效数字，则其相对误差界满足则a至少具有n位有效数字。设实数x为某个精确值，a为它的一个近似值，定理1.1nkaaaa21.01011110,2na11110,2(1)na由（1-2）可得到a（1-6）,102111na结论（1）成立。证1110ka1110)1(kaaaxaxa1nk102111101kaxaana1110)1(2所以如果a有n位有效数字，那么再由（1-5）和（1-6）1nkaa