数值分析——误差估计

1、1第五章第五章线性方程组直接解法线性方程组直接解法 误差估计误差估计2本讲内容本讲内容n 向量范数向量范数n 矩阵范数矩阵范数l 向量范数的定义向量范数的定义l 常见的向量范数常见的向量范数l 向量范数的性质向量范数的性质l 矩阵范数的定义矩阵范数的定义l F-范数与算子范数范数与算子范数l 矩阵范数的性质、算子范数的性质矩阵范数的性质、算子范数的性质n 误差估计误差估计3向量范数向量范数设函数设函数 f : Rn R，若，若 f 满足满足(1) f(x) 0， x Rn , 等号当且仅当等号当且仅当 x = 0 时成立时成立(2) f( x) = | | f(x) ， x Rn , R (3

2、) f(x+y) f(x) + f(y) 则称则称 f 为为 Rn 上的（向量）范数，通常记为上的（向量）范数，通常记为 | | q 4向量范数向量范数11niixx n 常见的向量范数常见的向量范数12221niixx 1maxii nxx 无穷范数（最大范数）无穷范数（最大范数） 2-范数范数 EuclidEuclid范数。范数。 1-范数范数5范数性质范数性质n 范数的性质范数的性质(1) (1) 连续性连续性设设 f f 是是 R Rn n 上的任意一个范数，则上的任意一个范数，则 f f 关于关于 x x 的每个分量是连续的的每个分量是连续的(2) (2) 等价性等价性设设 | |

3、|s s 和和 | | |t t 是是 R Rn n 上的任意上的任意两个范数，则存在常数两个范数，则存在常数 c c1 1 和和 c c2 2 ，使得对，使得对任意的任意的 x x R Rn n 有有12stscxxcx6范数性质范数性质(3) Cauchy-Schwarz 不等式不等式(4) 向量序列的收敛性向量序列的收敛性( )lim*kkxx 22( , )x yxy( )lim*0kkxx7矩阵范数矩阵范数设函数设函数 f : Rn n R，若，若 f 满足满足(1) f(A) 0， A Rn n , 且且 f(A) = 0 A = 0(2) f( A) = | | f(A) ， A

4、 Rn , R (3) f(A+B) f(A) + f(B)(4) f(AB) f(A)f(B)则称则称 f 为为 Rn n 上的（矩阵）范数，通常记为上的（矩阵）范数，通常记为 | | n 矩阵范数矩阵范数8矩阵范数矩阵范数n 常见的矩阵范数常见的矩阵范数(1) F-范数范数 (Frobenious 范数范数)12211nnijFijAa (2) 算子范数算子范数 (从属范数、诱导范数从属范数、诱导范数)其中其中 | | 是是 Rn 上的任意一个范数上的任意一个范数10supmaxnxx RxAxAAxx 9算子范数算子范数111maxnijj niAa n 常见的算子范数常见的算子范数2(

5、)TAA A 无穷范数（行范数）无穷范数（行范数） 2-范数（谱范数）范数（谱范数） 1-范数（列范数）范数（列范数）11maxniji njAa ,max)()(21nAAA的谱半径，即为10算子范数算子范数例例求矩阵求矩阵A A的各种常用范数的各种常用范数110121021A解解:1Aniijnja11max25234252 ,5 ,2max1njAnjijnia11max42 ,4 ,3max1ni2A)(maxAAT由于由于11的特征值因此先求AATAAT110121021110122011211190102特征方程为特征方程为)det(AAIT2111901020的特征值为可得AAT

6、9361. 0,9211. 2,1428. 9321121428. 9)(maxAAT2A)(maxAAT0237. 3FA)(AAtrT2926056. 31AA2AFA容易计算容易计算计算较复杂计算较复杂对矩阵元素的对矩阵元素的变化比较敏感变化比较敏感不是从属范数不是从属范数较少使用较少使用性质较好性质较好13矩阵范数性质矩阵范数性质n 矩阵范数的性质矩阵范数的性质(1) (1) 连续性：连续性：设设 f f 是是 R Rn n n n 上的任一矩阵范数，则上的任一矩阵范数，则 f f 关于关于 A A 的每个分量是连续的的每个分量是连续的(2) (2) 等价性：等价性：设设 |s s 和

7、和 |t t 是是 R Rn n n n 上上的任意两个矩阵范数，则存在常数的任意两个矩阵范数，则存在常数 c c1 1 和和 c c2 2 ，使，使得对任意的得对任意的 A A R Rn n n n 有有12stscAAcA14定理：定理：（相容性条件）相容性条件）设设 | | 是是 Rn 上的任一向量上的任一向量范数，其对应的算子范数也记为范数，其对应的算子范数也记为 | | ，则有，则有算子范数性质算子范数性质AxAxn 算子范数的性质算子范数的性质定理：定理：设设 | | 是任一算子范数，则是任一算子范数，则( )AA 15算子范数性质算子范数性质定理：定理：设设 | | 是任一算子范

8、数，若是任一算子范数，若 |B| 1 ，则，则 IB 非奇异，且非奇异，且 111IBB 定理：定理： (特征值上界特征值上界) ) 设设则则即即 A A 的谱半径不超过的谱半径不超过 A A 的任何一种算子范数的任何一种算子范数. . nnRAAA )(16 定理：定理：设设 , , 则则 的充要条件的充要条件是是B B的谱半径的谱半径( )1B0()kBk n nBR17病态矩阵病态矩阵考虑线性方程组考虑线性方程组 AxAx= =b b，如果，如果 A A 或或 b b 的的微小微小变化变化会导致解的会导致解的巨大巨大变化，则称此线性方程组是变化，则称此线性方程组是病态病态的，的，并称矩阵

9、并称矩阵 A A 是是病态病态的，反之则是的，反之则是良态良态的。的。n 病态矩阵病态矩阵例：例：1211211.00012xx 1220 xx 122.00011211.0 010 1xx 1211xx 18定理：定理：考虑线性方程组考虑线性方程组 Ax=b，设，设 A 是精确的，是精确的，b 有有微小微小的变化的变化 b，此时的解为，此时的解为 x + x ，则，则1AbxbAx 病态矩阵病态矩阵响的扰动对方程组解的影常数项b. 119设方程组设方程组 AXAX= =b b+ +b b 的解为的解为即即 ()A XXbb- -得得 A Xb即即 1XAb于是有于是有1XAb另一方面，由另一

10、方面，由得得 bA X且且0X 故故 1AXbXXX1XbAAXb由由与与有有 20定理：定理：考虑线性方程组考虑线性方程组 Ax=b，设，设 b 是精确的，是精确的，A 有有微小微小的变化的变化 A，此时的解为，此时的解为 x + x ，则，则111AxAAAAxAAA l 当当 A 充分小时，不等式右端约为充分小时，不等式右端约为1AAAA 病态矩阵病态矩阵响的扰动对方程组解的影系数矩阵A. 221q 分析表明，数分析表明，数 反映了方程组反映了方程组AXAX= =b b的解对的解对初始数据初始数据A A，b b扰动的灵敏度，可用来刻画方程组的扰动的灵敏度，可用来刻画方程组的病态程度病态程

11、度。 1AAn 矩阵的矩阵的条件数条件数定义：设定义：设 A 非奇异，则称非奇异，则称为为 A 的的条件数条件数。1Cond( )AAA 矩阵条件数矩阵条件数22n 条件数与范数有关，常用的有条件数与范数有关，常用的有无穷范数无穷范数和和2-范数范数l Cond(A)2 称为称为谱条件数谱条件数，当，当 A 对称时有对称时有1Cond( )AAA 1222Cond( )AAA 121maxCond( )minii nii nA 矩阵条件数矩阵条件数23条件数性质条件数性质n 条件数的性质条件数的性质(1) Cond(A) 1(2) Cond( A)=Cond(A), 其中其中 为任意非零实数为

12、任意非零实数(3) 若若 R 是正交矩阵，则是正交矩阵，则 Cond(R)2=1(4) 若若 R 是正交矩阵，则对任意非奇异矩阵是正交矩阵，则对任意非奇异矩阵 A，有，有 Cond(AR)2=Cond(RA)2=Cond(A)224举例举例例：例：计算计算 Cond(Hk) 其中其中 H 为为 Hilbert 矩阵矩阵解：解：k=1 时，时， Cond(H1) =1k=2 时，时，Cond(H2) =2712211/ 246, 1/ 21/ 3612HH k=3 时，时，Cond(H3) =74813211/ 21/ 3936301/ 21/ 31/ 4 , 361921801/ 31/ 41

13、/ 530180180HH Cond(H4) =28375Cond(H10) =3.5 101325for i=3:10 h=hilb(i); condA(i)=cond(h,2); %cond(h,inf)enddisp(n cond);for i=3:10 s=sprintf(%d %f,i,condA(i); disp(s);end运行后得到如下结果运行后得到如下结果:n cond3 524.0567784 15513.7387395 476607.2502426 14951058.6410057 475367356.37039387723649 4931539

14、86466.27094010 16025391750078.617000华长生制作26,783.008.183.1200.0250.0333.0250.0333.0500.0333.0500.000.1332211xxxxxx简记为简记为 .)(33bbxxHHbxHT3)60/47,12/13, 6/11( 方程组方程组 与与(6.8)(6.8)的精确解分别为的精确解分别为bxH3%,02.01018.0333HHT)4910. 0,5120. 0,0895. 0(x.)491002798. 1,487967062. 0,089512538. 1 (T xx,) , 1, 1, 1 (Tx华

15、长生制作27%182. 0bb%.2 .51xx 这就是说这就是说 与与 相对误差不超过相对误差不超过 ，而引起解的相，而引起解的相对误差超过对误差超过 . . 3Hb%30%5028 利用定义判断一个方程组是否病态，需要计算利用定义判断一个方程组是否病态，需要计算矩阵的条件数，从而涉及计算逆矩阵，极不方便矩阵的条件数，从而涉及计算逆矩阵，极不方便。注注q 用选主元消去法消元中出现小主元；用选主元消去法消元中出现小主元；q系数行列式的绝对值相对地很小系数行列式的绝对值相对地很小q系数矩阵元素间数量级上相差很大且无一定规律；系数矩阵元素间数量级上相差很大且无一定规律；q出现了相对地很大的解。出现

16、了相对地很大的解。当出现下列情况之一时，方程组很当出现下列情况之一时，方程组很可能病态可能病态： 方程组的病态性质，是方程组本身的特性。对于方程组的病态性质，是方程组本身的特性。对于病态方程组，用一般的求解方法不易求得较精确的解，而病态方程组，用一般的求解方法不易求得较精确的解，而且病态越严重，求解越困难。且病态越严重，求解越困难。29迭代迭代 改善改善(Iterative refinement)：设设Ax=b Ax=b ，其中，其中A A为非奇异矩阵，且为病态方程组为非奇异矩阵，且为病态方程组( (但不但不过分病态过分病态) ). Step 1:近似解近似解 bxA;1xStep 2:;11

17、xAbr Step 3:;111drdA Step 4:;112dxx If is exact solution，thenOtherwise go to step 2Otherwise go to step 21dbAxAbAxx11112)( 2x经验表明经验表明：若若 A 不是非常病态（例如：不是非常病态（例如： ），），则如此迭代可达到机器精度；但若则如此迭代可达到机器精度；但若 A 病态，则此算法也病态，则此算法也不能改进。不能改进。1)( Acond Approximate solution by Guassian elimination华长生制作30向后误差估计向后误差估计(Backward error analysis)(Backward error analysis)设设 为方程组为方程组Ax=bAx=b的近似解，于是可计算的近似解，于是可计算 的剩余向的剩余向量量 ，