计算机科学技术张宏伟矩阵答案.pdf

1 目录目录 第一章 误差分析与向量与矩阵的范数. 1 第二章 矩阵变换和计算 . 14 第三章 逐次逼近法. 32 附录 I 矩阵分析介绍 . 45 第一章第一章 误差分析与向量与矩阵的范数误差分析与向量与矩阵的范数 一、内容提要一、内容提要 本章要求掌握绝对误差、相对误差、有效数字、误差限的定义及其相互关系；掌握数 值稳定性的概念、 设计函数计算时的一些基本原则和误差分析； 熟练掌握向量和矩阵范数的 定义及其性质。 1误差的基本概念和有效数字 1） 绝对绝对误差和相对误差相对误差的基本概念 设实数x为某个精确值，a为它的一个近似值，则称ax为近似值a的绝对误差绝对误差，简称 为误差误差 当0x时， x ax 称为a的相对误差相对误差在实际运算中，精确值x往往是未知的，所 以常把 a ax 作为a的相对误差 2） 绝对绝对误差界界和相对误差界相对误差界的基本概念 设实数x为某个精确值，a为它的一个近似值，如果有常数 a e，使得 a eax 称 a e为a的绝对误差界，或简称为误差界误差界称 a ea 是a的相对误差界相对误差界 此例计算中不难发现，绝对误差界和相对误差界并不是唯一的，但是它们越小，说明a 近似x的程度越好，即a的精度越好 3） 有效数字 设实数x为某个精确值，a为它的一个近似值，写成 n k aaaa 21 . 0 10 = 它可以是有限或无限小数的形式，其中), 2 , 1(=iai是9, 1, 0中的一个数字，ka, 0 1 为整 数如果 nk ax 10 2 1 则称a为x的具有n位有效数字有效数字的近似值 2 如果a有n位有效数字，则a的相对误差界满足： n aa ax 1 1 10 2 1 。 4 4） 函数计算的误差估计） 函数计算的误差估计 如果),( 21n xxxfy=为n元函数，自变量 n xxx, 21 的近似值分别为 n aaa, 21 ， 则 )(),(),( 1 2121kk n k a k nn ax x f aaafxxxf = 其中 ),( 21n k a k aaaf xx f = ，所以可以估计到函数值的误差界，近似地有 k a n k a k ann e x f eaaafxxxf = 1 2121 ),(),( 如果令2=n， 设 21, x x的近似值分别为 21, a a， 其误差界为 1 11a eax和 22 ax 2 a e， 取 ),( 21 xxfy =为 21, x x之间的四则运算，则它们的误差估计为， 1121 aaaa eee+ ； 1121 21aaaa eaeae+ ； 2 2 21 11 2 1 a eaea e aa a a + ， 0 2 a 。 数相加或减时，其运算结果的精度不会比原始数据的任何一个精度高 对于两个数作相减运算时，由于其相对误差界： 2121 2121 aa ee aa e aaaa + 。 如果 1 x和 2 x是两个十分接近的数，即 1 a和 2 a两个数十分接近，上式表明计算的相对误 差会很大，导致计算值 21 aa 的有效数字的位数将会很少。 对于两个数作相除运算时，由于其相对误差界： 2 2 21 11 2 1 a eaea e aa a a + 。 从关系式中可以看出，如果 2 x很小，即 2 a很小，计算值 2 1 a a 的误差可能很大。 5） 数值稳定性的概念、设计算法时的一些基本原则 算法的数值稳定性： 一个算法在计算过程中其舍入误差不增长称为数值稳定。 反之， 成为数值不稳定。不稳定的算法是不能使用的。 在实际计算中应尽量避免出现两个相近的数相减。 在实际计算中应尽力避免绝对值很小数作除数。 注意简化运算步骤，尽量减少运算次数。 多个数相加，应把绝对值小的数相加后，再依次与绝对值大的数相加。 2 2向量和矩阵范数 把任何一个向量或矩阵与一个非负实数联系起来， 在某种意义下， 这个实数提供了向量 和矩阵的大小的度量。对于每一个范数，相应地有一类矩阵函数，其中每一个函数都可以看 作矩阵大小的一种度量。 3 范数的主要的应用：范数的主要的应用： 一、研究这些矩阵和向量的误差估计一、研究这些矩阵和向量的误差估计。 二、研究矩阵和向量的序列以及级数的收敛准则。二、研究矩阵和向量的序列以及级数的收敛准则。 1 1）向量范数）向量范数 定义定义 存在 n R（n维实向量空间）上的一个非负实值函数，记为xxf=)(，若该函数 满足以下三个条件：即对任意向量x和y以及任意常数R（实数域） （1）非负性非负性 0x，并且0=x的充分必要条件为0=x; （2）齐次性齐次性xx=； （3）三角不等式三角不等式yxyx+ 则称函数为 n R上的一个向量范数 常用三种的向量范数 设任意维向量 T n xxx),( 21 =x， （ T x为向量x的转置） ， = = n i i x 1 1 x， 向量的 1-范数 ()2 1 , 2 1 1 2 2 xxxxxx= = = T n i i ， 向量的 2-范数 i ni xx = 1 max， 向量的-范数 一般情况下，对给定的任意一种向量范数，其加权的范数可以表为 xxW W =， 其中 W 为对角矩阵，其对角元作为它的每一个分量的权系数。 向量范数的连续性范数的连续性定理 n R上的任何向量范数x均为x的连续函数。 向量范数的等价性定理范数的等价性定理 设 和 为 n R上的任意两种向量范数，则存在两个与向量 x无关的正常数 c1和 c2，使得下面的不等式成立 xxx 21 cc，其中 n xR. 2). 矩阵范数 定义 存在 nn R（nn维复矩阵集合）上的一个非负实值函数，记为AAf=)(，对 4 任意的A, nn RB均满足以下条件： （1）非负性：对任意矩阵A均有0A，并且0=A的充分必要条件为OA =; （2）齐次性：AA=，C； （3）三角不等式：BABA+, nn RBA,； （4）相容性：BAAB, nn RBA,， 则称为 nn R上的矩阵范数。 我们可定义如下的矩阵范数： = = m i n j ij m a 11 1 A，矩阵的 1 m-范数 ( ) 2 1 11 2 = = m i n j ij F aA，矩阵的F-范数（Frobenius）范数。 （矩阵范数与向量范数相容性矩阵范数与向量范数相容性定义） 对于一种矩阵范数 M 和一种向量范数 V ，如 果对任意 nn 矩阵A和任意 n 维向量 x, 满足 VMV xAAx， 则称矩阵范数矩阵范数 M 与向量范数与向量范数 V 是相容的是相容的。 3 3）矩阵的算子范数）矩阵的算子范数 定理定理 已知 n R上的向量范数 V ，A为 nn 矩阵，定义 V V V M V Ax x Ax A xx10 maxmax = = 则 M A是一种矩阵范数，且与已知的向量范数相容，称之为矩阵的算子范数。矩阵的算子范数。 三种常用的矩阵的算子范数三种常用的矩阵的算子范数 = = m i ij nj a 1 1 1 maxA； (列范数) = = n j ij mi a 1 1 maxA (行范数) 5 , )( max 2 AAA T = （谱范数） 其中)( max AAT表示矩阵AAT的最大特征值。 对任何算子范数，单位矩阵 nn RI 的范数为 1，即1=I。 可以证明：可以证明： 任意给定的矩阵范数必然存在与之相容的向量范数；任意给定的向量范数必然存在任意给定的矩阵范数必然存在与之相容的向量范数；任意给定的向量范数必然存在 与之相容的矩阵范数（如从属范数） 与之相容的矩阵范数（如从属范数） 一个矩阵范数可以与多种向量范数相容 （如矩阵一个矩阵范数可以与多种向量范数相容 （如矩阵 1 m范数与向量范数与向量p-范数相容） ； 多种范数相容） ； 多种 矩阵范数可以与一个向量范数相容 （如矩阵矩阵范数可以与一个向量范数相容 （如矩阵F范数和矩阵范数和矩阵2范数与向量范数与向量2范数相容） 。范数相容） 。 从属范数一定与所定义的向量范数相容，但是矩阵范数与向量范数相容却未必有从从属范数一定与所定义的向量范数相容，但是矩阵范数与向量范数相容却未必有从 属关系。 （如，属关系。 （如， F 与向量与向量 2 、 1 m 与向量与向量 1 相容，但无从属关系） 。相容，但无从属关系） 。 并非任意的矩阵范数与任意的向量范数相容。并非任意的矩阵范数与任意的向量范数相容。 4）矩阵范数的性质 设为 nn R矩阵空间的一种矩阵范数，则对任意的 n 阶方阵A均有 AA )( 其中其中()0detmax)(=AIA为方阵为方阵A的谱半径。的谱半径。 注意：注意：当 T AA =时，()()()( max 2 maxmax 2 AA=AAAAT。 对于任给的0, 则存在 nn R上的一种算子范数 M （依赖矩阵A和常数） ， 使得 +)(AA M 对于 nn R上的一种算子矩阵范数，如果 nn RA且A1, 则AI n 可逆且 () A AI 1 1 1 n 二、典型例题分析二、典型例题分析 例例 1 11 1：下列近似值的绝对误差限均为 0.005，问它们各有几位有效数字？ 002.138=a，0312 . 0 =b， 4 1086 . 0 =c 解：解： 现将近似值写成标准形式： 3 10138002 . 0 =a, 1 10312 . 0 =b, 4 1086 . 0 =c, 在直接根据有效数字定义得出， 6 2 10 2 1 ax = nk23= n5=n，即a有 5 位有效数字； 2 10 2 1 bx = nk21=n1=n，即b有 1 位有效数字； 2 10 2 1 cx = nk24=n2=n，即c无有效数字。 例例 1 12 2：已知x的相对误差为003 . 0 ，求 m a的相对误差。 解：解：此题要利用函数计算的误差估计，即取( ) m xxf=，( ) 1 = m xmxf，则由 ( )( )( )()axafafxf ，可推出 ()axamax mmm 1 ，故 m a的相对误差为 m a ax m a ax m mm 003 . 0 = 。 例例 1 13 3：此为减少运算次数达到避免误差危害的例子 利用 3 位算术运算求( )5 . 12 . 31 . 6 23 +=xxxxf在71 . 4 =x处的值。 表中给出了传统的方法的计算的中间结果。 在这里我们使用了两种取值法： 截断法和舍入法。 x 2 x 3 x 2 1 . 6 x x2 . 3 精确值 4.71 22.1841 104.487 111 135.323 01 15.072 3 位数值（截断法） 4.71 22.1 104 135 15.0 3 位数值（舍入法） 4.71 22.1 104 135 15.1 精确值：()5 . 1072.1501323.135111487.10471 . 4 +=f899263.14= 3 位数值（截断法） ：()()() 5 . 135 . 1 0 . 1513410471 . 4 =+=f 3 位数值（舍入法） ：()()() 4 . 135 . 1 1 . 1513510571 . 4 =+=f 上述 3 位数值方法的相对误差分别是 05 . 0 899263.14 5 . 13899263.14 + ，截断法 06 . 0 899263.14 4 . 13899263.14 + ，舍入法 作为另一种办法，用秦九韶方法（嵌套法）可将( )xf写为 ( )5 . 12 . 31 . 6 23 +=xxxxf()()5 . 12 . 31 . 6+=xxx 那么，3 位数值（截断法） ：()()() 2 . 145 . 171 . 4 2 . 371 . 4 1 . 671 . 4 71 . 4 =+=f ()5 . 171 . 4 2 . 371 . 4 38 . 1 += ()5 . 171 . 4 2 . 354 . 6 += 7 5 . 171 . 4 34 . 3 += 2 . 145 . 1 7 . 15=+= 3 位数值（舍入法） ：()()() 2 . 145 . 171 . 4 2 . 371 . 4 1 . 671 . 4 71 . 4 =+=f ()5 . 171 . 4 2 . 371 . 4 38 . 1 += ()5 . 171 . 4 2 . 355 . 6 += 5 . 171 . 4 35 . 3 += 3 . 145 . 1 8 . 15=+= 则相对误差分别是 5004 . 0 899263.14 2 . 14899263.14 + ， （截断法） 0025 . 0 899263.14 3 . 14899263.14 + ， （舍入法） 可见使用秦九韶方法 （嵌套法） 已将截断近似计算的相对误差减少到原方法所得相对误 差的%10之内。对于舍入近似计算则改进更大，其相对误差已减少%95以上。 多项式在求值之前总应以秦九韶方法（嵌套法）表示，原因是这种形式使得算术运算次 数最小化。 本例中误差的减小是由于算术运算次数从 4 次乘法和 3 次加法减少到 2 次乘法和 3 次加法。减少摄入误差的一种办法是减少产生误差的运算的次数。 例例 1 14 4：已知近似值21 . 1 1= a，65 . 3 2 =a，81 . 9 3 =a均为有效数字，试估计如下算 术运算的相对误差。 321 aaa+ 解：由已知， 2 11 10 2 1 10 2 1 = nk ax； 2 22 10 2 1 ax； 2 33 10 2 1 ax。 令 () 321321 ,xxxxxxf+=，() 321321 ,aaaaaaf+=， 由函数运算的误差估计式 () 321 ,xxxf() 321 ,aaaf ()() 11321 , 1 axaaafx+()() 22321 , 2 axaaafx+()() 33321 , 3 axaaafx ()() () 33221112 axaxaaxa+= 从而，相对误差可写成 ()() () 321 321321 , , aaaf aaafxxxf () 321 33221112 ,aaaf axaxaaxa+ + + 81 . 9 63 . 3 21 . 1 165 . 3 21 . 1 2 10 2 1 00206 . 0 = 若000 . 3 =x，100 . 3 =a， 8 则绝对误差1 . 0= ax， 相对误差为： 1 10333 . 0 0333 . 0 000 . 3 100 . 0 = = x ax ； 若0003000 . 0 =x，0003100 . 0 =a， 则绝对误差 4 101 . 0 = ax， 相对误差为： 1 10333 . 0 0003000 . 0 000100 . 0 = = x ax ； 若 4 103000 . 0 =x， 4 103100 . 0 =a， 则绝对误差 3 101 . 0 = ax， 相对误差为： 1 4 3 10333 . 0 103000 . 0 101 . 0 = = x ax ； 这个例子说明绝对误差有较大变化时，相对误差相同。作为精确性的度量，绝对误差 可能引起误解，而相对误差由于考虑到了值的大小而更有意义。 例例 1 15 5：在 2 R中用图表示下面的点集，并指出它们的共同性质。 2 Rxxx=, 1 1 1 S， 2 Rxxx=, 1 2 2 S， 2 Rxxx= , 1 3 S 解： 这些点集的共同性质是：它们都是有界、闭的、凸的，关于原点对称的。 例例 1 16 6：+= n xxxx （2）对任给C， nT n Cxxx=),( 21 x，则 2 22 2 2 1 222 2 2 1 2 xx=+=+= nn xxxxxx （3） 对任给 nT n Cxxx=),( 21 x， nT n Cyyy=),( 21 y则由 Cauchy-Schiwatz 不等式： 22 ),(),(),(yxyyxxyx=可得 ),(),(),(),(),( 2 2 yyyxxyxxyxyx+=+ yx 2 2 2 2 ),(2yyxx+ 2 2 2 2 2yyxx+, = 2 22 )(yx+。 由向量范数的定义， 2 为 n C空间上的向量范数。 例例 1 18 8 设A= 420 001 ，求 1 m A、 F A、 1 A、 A和 2 A。 解：解：7421 3 1 2 1 1 =+= =j ij i m aA；21421 22 3 1 2 2 1 =+= =j ij i F aA 44, 2, 1maxmax 1 2 1 1 1 = = nj i ij nj aA；66, 1maxmax 1 3 1 1 = = nj j ij ni aA； 注意到，A T A= 40 20 01 420 001 = 1680 840 001 ，令 ()()()()()01641641 1680 840 001 det= = AAI T 得，)(AAT20=，从而5220)( max 2 =AATA。 1.1.4 4 习题解答习题解答 1、解解 10 （1）有定义， 1 A= 3, A= 5, F A=14, 2 A=1027 +及)(A= 3。 (2) 4 )12, 4, 0, 3(R= T x，则 1 x= 19, x= 12, 2 x= 13。 (3)（是） ；为给定向量 1-范数的加权的范数，其中取对角矩阵， = 3 2 1 W 。 （不是） ；不满足向量范数性质 1； （不是） ；不满足向量范数性质 1。 (4) a =8.3667。因43666002653 . 8 70 =，8 1= a，要是得相对误差限不超过 %1 . 0，即001 . 0 70 a a ，则001 . 0 10 16 1 2 10 70 1 1 1 = n n aa a 时，有4=n。 2、只就（2）证明 ，由定义可得， 2 1 22 2 1 222 maxmax = =xnxxxxx n k k k n k kk k 从而， xxxn 2 。 3、首先，证明Pxx P =是一向量范数。事实上， 1） 因 nn RP是非奇异矩阵， 故0x，0Px， 故0=Px时，0=x， 且当0=x 时，0=Px，于是，Pxx P =0当且仅当0=x时，Pxx P =0 成立； 2）对R，()() PP xPxPxxPx=； 3）() PPP yxPyPxPyPxyxPyx+=+=+=+。 故 P x是一向量范数。再 () Px PxPAP Px PAx x Ax A xx P P x P 1 000 maxmaxmax =， 令Pxy =，因P非奇异，故x与y为一对一，于是于是 () 1 1 0 max =PAP y yPAP A y P 4、证明：(1)，由算子范数的定义 () () 1maxmaxmaxmaxmax 2 2 2 2 0 2 2 0 2 2 0 2 2 0 2 2 2 2 0 2 2 = x x x xx x UxUx x UxUx x Ux x H x HH x H xx U； 11 证明：(2)， = 2 AU()()AUAU H max =()()UAAU HH max =()AAH max = 2 A， = 2 UA()()UAUA H max =()()AUUA H max =()AAH max = 2 A。 此结论表明酉阵具有保 2-范数的不变性。 5、解： （1）由于 1 10 2 1 A xe，由有效数字定义可知， A x有 2 位有效数字；又2 1= a， 再由相对误差界的公式， 121 10 4 1 10 22 1 = A A x xe ； （2）由于 3 10 2 1 A xe，由有效数字定义可知， A x有 4 位有效数字；又2 1= a， 再由相对误差界的公式， 341 10 4 1 10 22 1 = A A x xe ； （3）由于 3 10 2 1 A xe，由有效数字定义可知， A x有 2 位有效数字；又2 1= a， 再由相对误差界的公式， 121 10 4 1 10 22 1 = A A x xe ； （4）由于 5 10 2 1 A xe，由有效数字定义可知， A x有 4 位有效数字；又2 1= a， 再由相对误差界的公式， 341 10 4 1 10 22 1 = A A x xe 。 6、给定方程0126 2 =+xx，利用961.12168 ，求精确到五位有效数字的根。 并求两个根的绝对误差界和相对误差界。 解： 由二次方程求根公式知，16813 1 +=x，16813 2 =x。 若利用961.12168 ， 则近似根961.25 1= a具有 5 位有效数字，而16813 2 =x 2 039 . 0 961.1213a=， 只有 2 位有效数字。若改用 16813 2 =x + = 961.25 1 16813 1 038519 . 0 2 a= 则此方程的两个近似根 1 a， 2 a均具有 5 位有效数字。它们的绝对误差界和相对误差界分别 为： 352 11 10 2 1 10 2 1 = ax； 451 1 11 10 50 1 10 252 1 = a ax 12 651 22 10 2 1 10 2 1 = ax； 451 2 22 10 6 1 10 32 1 = a ax 。 7 = += 50 1 100 1 545494 i i i i s，其中8 . 0= i ，2= i 计算机作加减法时，先将相加数阶码对齐，根据字长舍入，则 个100 666 100000008 . 0 100000008 . 0 1054549 . 0 +=s 个50 66 10000002 . 0 10000002 . 0 + 6 1054549 . 0 = 545494 与 6 1000008 . 0 和 6 1000002 . 0 在计算机上做和时，545494由于阶码升为 5 位尾数左移变成机器零，这便说明用小数做除数或用大数做乘数时，容易产生大的舍入误 差，应尽量避免 若改变运算次序，先把 i 100相加， i 50相加。再与54549相加。即 6 50100 1054549 . 0 228 . 08 . 0+= 个个 s 62 1054549 . 0 50102 . 0108 . 0+= 5456701054567 . 0 1054549 . 0 1000018 . 0 1054549 . 0 108 . 1 66662 =+=+= 8分析：分析：由于)1ln()( 2 =xxxf，求)(xf的值应看成复合函数。先令 1 2 =xxy， 由于开方用六位函数表， 则y的误差为已知， 故应看成)ln()(yygz=， 由y的误差限 * yy 求)(yg的误差限)ln()ln( * yy 。 解：解：当30=x时求13030 2 =y，用六位开方表得 167 . 0 100167 . 0 9833.2930 1* = y，其具有 3 位有效数字。故 431* 10 2 1 10 2 1 10 2 1 = nk yy。 由)ln()(yygz=，得 y yg 1 )(=，故 y yy zz * * 。于是， 24 * * * 103 . 010 0167 . 0 5 . 0 y yy zz。 13 若用公式)1ln()( 2 +=xxxf，令1 2 +=xxy，此时)ln()(yygz=，则 599833 . 0 109833.599833.2930 2* =+=y，其具有 6 位有效数字。故 462* 10 2 1 10 2 1 10 2 1 = nk yy。 而 y yy zz * * 。于是， 64 * * * 10834 . 0 10 9833.59 5 . 0 y yy zz 可见，用公式)1ln()( 2 +=xxxf计算更精确。 9解解：方法（1）的误差由 Taylor 展开可得， 10 1 5 5 !10 e ae，其中在5与 0 之间。而方法（2）得误差是 1 9 0 1 9 0 10 1 5 ! 5 5 !10! 5 = = += i i i i i e i ae = 1 9 0 1 9 0 10 10 ! 5 5 !10! 5 5 !10 = = + i i i i i e i e = = = = 9 0 5 10 9 0 5 10 ! 5 !10 5 ! 5 !10 5 i i i i i e i e e ，其中055。 由此可知方法（2）得误差是方法（1）的 7 . 143 1 ! 5 1 9 0 =i i i 倍，故方法（2）给出较准确的 近似值。 10解：所给出的 5 个公式可分别看作 ( )()61= xxf，( )() 6 1 1 += xxf，( )()3 2 23xxf=，( )()3 2 23xxf=， ( )() 3 3 23 +=xxf，( )xxf7099 4 = 取2=x的近似值4 . 1=a时，相应函数的计算值。而=02 . 0 2a。利用函 数计算的误差估计公式可得： ()( )( )06144 . 0 4 . 061622 5 5 aaafaff； 14 ()( )01308 . 0 4 . 26162 7 7 11 + aaff； ()( )24 . 0 4 . 062362 2 22 aaff； ()( )+ 005302 . 0 2362 4 33 aaff； ()( )702 44 aff。由此可见，使用公式 () 3 223 1 + 计算时误差最小。 11以（2）和（3）为例其它同理 解：解： （2）只需取 + =+ x x x xx x x x x 11 211 ； （3） ) 1(1 1 ) 1( 1 1 2 + =+= + + NN NN x dx N N arctgarctgarctg。 注：令NNarctgarctg=+=),1(，则N=tg，1tg+= N。 由于NNarctgarctg+=) 1(，由差角公式： tgtg1 tgtg )(tg + = 。得 tgtg1 tgtg arctg + =，进而有 ) 1(1 1 ) 1( + =+ NN NNarctgarctgarctg。 第二章第二章 矩阵变换和计算矩阵变换和计算 一、内容提要一、内容提要 本章以矩阵的各种分解变换为主要内容，介绍数值线性代数中的两个基本问题：线性 方程组的求解和特征系统的计算， 属于算法中的直接法。 基本思想为将计算复杂的一般矩阵 分解为较容易计算的三角形矩阵. 要求掌握 Gauss（列主元）消去法、矩阵的（带列主元的） LU分解、平方根法、追赶法、条件数与误差分析、QR 分解、Shur 分解、Jordan 分解和奇 异值分解. (一) 矩阵的三角分解及其应用 1矩阵的三角分解及其应用 考虑一个n阶线性方程组bAx =的求解，当系数矩阵具有如下三种特殊形状：对角矩 阵D，下三角矩阵L和上三角矩阵U，这时方程的求解将会变得简单. = n d d d D 2 1 , = nnnn lll ll l L 21 2221 11 , = nn n n u uu uuu U 222 12111 . 15 对于bDx =，可得解为 iii dbx/=,ni, 2 , 1=. 对于bLx =，可得解为 1111 /lbx =, ii i k kikii lxlbx/ )( 1 1 = =,ni, 3 , 2=. 对于bUx =，可得解为 nnnn