大连理工大学-矩阵与数值分析绪论

计算机科学计算（第一版）施吉林张宏伟金光日编高等教育出版社本课件在张宏伟老师提供课件基础上略加改动而成，谨此致谢！第1章绪论1.1计算机科学计算研究对象与特点科学计算（计算方法、计算数学、数值分析）：计算机上求解数学问题的离散近似算法主要内容包括：微分方程数值解法本课程研究用计算机求解各种数学问题的数值计算方法、理论与软件实现数值代数数值逼近（数值微分积分）bAx0xfxfxfxxfxbad00,,utuutfu课程特点：一、构造计算机可行的有效算法：计算量与存储量。二、给出实用的理论分析结果，如算法收敛性和稳定性。考察线性方程组早在18世纪Gramer已给出了求解法则：什么是有效算法？nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111DiDAdetnnnnnnaaaaaaaaa212222111211iAdetnnnnnnabaabaaba122211111ix,DDii1…，n（D≠0），Gramer’sRuler从理论上讲Gramer法则是一个求线性方程组的数值方法，且对阶数不高的方程组行之有效。但是在计算机上，它是否实际可行？在算法中的乘、除运算次数将达使用每秒一亿次的串行计算机计算,一年可进行的运算应为：21！=9.7×1020次(9.7×1020)(3.5)(3.097×1015)30(万年)365(天)×24(小时)×3600(秒)×1093.5×1015（次）以求解20阶线性方程组为例，如果用Gramer法则求解，共需要耗费时间为：1.2误差分析与数值方法的稳定性1.2.1误差来源与分类误差的主要来源：实际问题数学模型计算机数值结果数值计算方法计算流程与误差来源模型误差观测误差截断误差舍入误差1．模型误差：实际问题的解与数学模型的解之间的误差，来源于数学模型对实际问题的的简化。2.观测误差：初始数据大多数是由观测而得到的。由于观测手段的限制，得到的数据常有误差。截断误差这一术语来源：截断Taylor级数，用Taylor级数的有限项近似替代Taylor级数的无穷和。3.截断误差：数学模型与数值计算模型的误差，如有限代替无限、离散代替连续的误差。x2xe例如，求的值。利用无穷级数：前项和1n截断误差则数值方法的误差是2xe，近似代替函数给定2xe!!3!212642nxxxxn=!!3!212642nxxxxn!112nxnxs,!11222nxxnxnexsexR104.舍入误差例如，产生的误差就是舍入误差。41421.1200000365.0E用近似代替，4121.12由于计算机字长有限而造成的计算过程中误差。模型和观测两种误差不在本课程的讨论范围。这里主要讨论截断误差与舍入误差，而截断误差将结合具体算法讨论.初始数据误差也常常归结为舍入误差.下面讨论误差估计几个基本问题1.误差的基本概念设为精确值，xax因此误差也未知。ax称通常准确值是未知的，x为近似值的绝对误差，简称误差。为的一个近似值，axaeax绝对误差界（限）误差可正可负。ax绝对误差（误差）则叫做近似值的误差界（限）。ae它总是正数。定义1.4定义1.5设为精确值，x为的一个近似值，若有常数ax使得（1-13）例如，用毫米刻度的米尺测量一长度，读出和该长度接近的刻度，xa是的近似值，ax它的误差限是，mm5.0于是mm.5.0ax如读出的长度为，mm765则有.5.0765x虽然从这个不等式不能知道准确的是多少，但可知x绝对误差界（限）,5.7655.764x结果说明在区间内.x]5.765,5.764[对于一般情形，aeax即,aaeaxea也可以表示为.aeax但要注意的是，误差的大小并不能完全表示近似值的好坏.实际计算中，如果真值未知时，xxax若，0xxax称为近似值的相对误差。a作为的相对误差，a条件是较小。xax通常取相对误差（误差）则将近似值的误差与准确值的比值aax定义相对误差也可正可负，其绝对值上界叫做相对误差界（限）axaxxaxaax2是的平方项级，故可忽略不计。xaxaxxxax2)(xaxxax112aea记为：相对误差界（限）这是由于例，有两个量，000.3x,100.3aax则xax又例如，有两个量4103000.000.3000xaxxax,103100.031004a绝对误差相对误差绝对误差相对误差则=-0.100.31.0,10333.01,101.0343103.0101.0110333.0上例中，绝对误差有较大变化，而相对误差相同。相对误差由于考虑到准确值本身的大小常常更有意义。其近似值,求718.2a71828182.2e00028182.0aeae0001110375.0718.20003.0aaea已知，因此其绝对误差界为：相对误差界为：的绝对误差界和相对误差界。解：0.00030.0002。注意：绝对误差界和相对误差界并非唯一。例1当准确值位数比较多时，常常按四舍五入的原则得到的前几位近似值，xxa14159265.3πx取3位,14.31a取5位,1416.32a它们的误差界可以取为：,102114.3π2例如00159265.01a00000735.02a.10211416.3π4误差界的确定nkaaaa21.010（1-14）的一个数字，为整数，ka,01.1021nkax（1-15）则称为的具有位有效数字的近似值。anx定义1.6设为精确值，x为的一个近似值，表为ax可以是有限或无限小数形式，其中是0到9中),,1(niain为使下式成立的最大正整数，nkaaaa21.010其中na1a非零，是四舍五入得到的，则如果一个近似值是由精确值经四舍五入得到的，那么，从这个近似值的末尾数（可以是零）向前数起直到再无非零数字止，所数到的数字均为有效数字有效数字位数与小数点的位置无关一般来说，绝对误差与小数位数有关，相对误差与有效数字位数有关00.138a0312.0b41086.0c,1013800.03a,10312.01b。41086.0c21021ax23n5n下列近似值的绝对误差限均为0.005，问它们各有几位有效数字？解：则由已知条件，练习1即a有5位有效数字；21021bx21n1n21021cx24n2n有1位有效数字；即b无有效数字。即c减小舍入误差影响的几个原则：1.避免两个相近的数做减法两个具有n个有效数字的相近数相减后，常常损失有效数字。例如在三位有效数字计算机上求解方程01162xx一个根为,9.1594.700.8)638fl(1x有三位有效数字。而另一个根为,06.094.700.8)638fl(2x只有一位有效数字。方程)0(,02abcbxax的改进求根公式：,4)sgn(21aacbbbx12axcx当x很小时，用下面近似公式计算!7!5!3)!7!5!3(sin753753xxxxxxxxxx例2.防止“大数吃小数”计算,6301510001iix4.0i在五位有效数字计算机上，由于加减法要对齐小数点，63415400)fl(63015))fl(fl(6301540001iiδ630150.4)fl(63015导致“大数吃小数”。因此，应该小数相加后，再与大数相加：3.避免小数做除数或大数做乘数例如，xaxaax11若,01x,0)(flxa则绝对误差比xa增大xa1倍。21xx当021xx时，有可能溢出！即为所求。0111)(axaxaxaxpnnnnnkkxt,10kkkxaxaaunu)(xpn次乘法和2)1(nn例如，直接逐项求和计算若令，则有递推公式（秦九韶算法，霍纳算法）：需次乘法，n2,,,2,1nk1kktxtkkkktauu1n次加法。4.巧用等价公式减少运算次数需要n次加法。,510dxxxInn15nnII由于则递归算法如下：,511nnInI1.,1511nnInI2.7,,2,1,0n101dxxndxxxn10155计算积分解：dxxxn105dxxxxnn10155n11820.056ln0I0210.07I算出由71,,II计算出07,,II由5.选择稳定的算法（稳定性：舍入误差的积累影响不大)nI方法1n01820.01820.01820.0120880.00880.00900.00580.00580.00500.0456730431.00343.00343.00830.00431.00165.00284.00284.00250.10240.00240.00210.00210.09580.4933.24方法2设0I的近似值为0I，然后按方法1计算71,,II的近似值71,,II。如果最初计算时误差为000IIE递推过程的舍入误差不记，并记nnnIIE077567775)1()5)(5()5(EEEIIE，则有舍入误差放大了倍，因此是数值不稳定的。125,7857按方法2计算时，记初始误差为777IIE，则有772100051515151EEEIIE因此公式2是数值稳定的。1.2向量与矩阵的范数实数或复数的大小由非负实数度量。xxfxx（2）齐次性yxyx（3）三角不等式注意到满足以下三个条件：xxf)(0x（1）非负性当且仅当时0x0x向量和矩阵的范数：向量和矩阵的“长度”或“大小”。科学计算中离不开矩阵和向量的运算。运算过程的收敛、稳定、误差等问题都基于“距离”、“长度”、“大小”的概念，都用范数来描述。1.2.1向量范数0x（1）非负性并且当且仅当时0x0xxx（2）齐次性yxyx（3）三角不等式则称函数为上的一个向量范数．nC以及任意复（实）常数xxf)(,y,该函数满足nC（或）上的一个非负，若对任意向量和定义在实值函数，记为x定义1.1nR)nR（或,),,,(21Tnxxxx记任意ｎ维向量(为向量的转置），常用的向量范数有Txxniix11x(1-1)(1-2)xxxxHnii21122(为向量的共轭转置）Hxxinixx1max(1-3)pxpnipip1,11x(1-4)ix表示的模．上述四种范数分别称为１，2，∞范数和p-范数ix2n前面三种范数为p-范数当ｐ＝１，2，∞时的特例。例如，当时，。事实上，pxpxpinipxx1max两边开次方得p,)(111xxpnippnx,1limppn由于xpx故容易验证以上三种范数均满足范数定义中的三个条件。下面我们分析一下向量的１，2和∞-范数的几何意义，以,),(221RTxxx1xnipx111xpininx1maxpnx为例。1x2x111112x12x1x2x111112221xx1x2x11111,1ma