數(shù)值分析07線性代數(shù)方程組的直接法

1、第七章第七章( Direct Method for Solving Linear Systems)nnnnnnnnbbbbxxxXaaaaaaaaaA2121212222111211nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111（3.1） 線性方程組數(shù)值解法的分類線性方程組數(shù)值解法的分類 直接法直接法（適用于中等規(guī)模的（適用于中等規(guī)模的n n階線性方程組）階線性方程組） GaussGauss消去法及其變形消去法及其變形 矩陣的三角分解法矩陣的三角分解法 迭代法迭代法（適用于高階線性方程組）（適用于高階線性方程組） JacobiJacobi

2、迭代法迭代法 Gauss-SeidelGauss-Seidel迭代法迭代法 逐次超松弛法逐次超松弛法 共軛斜量法共軛斜量法(Gaussian Elimination)1 1三角形方程組的解法三角形方程組的解法-回代法回代法nnnnnnbxaxaxabxaxabxa221122221211111 （3.2）nnnnnnnnbxabxaxabxaxaxa2222211212111（3.3） 2 2順序高斯消去法順序高斯消去法思思路路首先將首先將A化為上三角陣化為上三角陣 ( upper-triangular matrix )，此過程稱為此過程稱為消去過程消去過程，再求解如，再求解如下形狀的方程組，

3、此過程稱為下形狀的方程組，此過程稱為回代求解回代求解 ( backward substitution )。=nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111將增廣矩陣將增廣矩陣的的第第 i 行行 + li1 第第1 1行行，得到：，得到：,)(記)1()1(nnijaAA(1 )(1 )(1 )()1Tbbbbn消元過程：消元過程：第一步第一步：設(shè)設(shè) ，計(jì)算因子，計(jì)算因子0)1(11a)1(11)1(11aalii)1(1)1(1)1(12)1(11.baaan) 2(A) 2 (b其中其中) 1(11) 1()2() 1(11) 1()2

4、(, 3 , 2, ,blbbnjialaaiiijiijij0)( kkka第第k步：步：設(shè)設(shè) ，計(jì)算因子，計(jì)算因子( )( )/(1,., )kkikikkklaaikn 將增廣矩陣將增廣矩陣的的第第 i 行行 + lik 第第k k行行，得到：，得到：(1)()()(1)()()( ,1, .,)kkkijijikkjkkkiiikkaal abbl bijkn其中其中(1)(1)(1)(1)(1)111111,11( )( )( )( ),1(1)(1)(1)11,11,1(1)(1)( ),100000kknkkkkkkkk kknkkkkkkkknkkkkn knnnnbxaaaa

5、xaaabxaabaaxb )()(/nnnnnnabx ) 1., 1()(1)()( niaxabxiiinijjiijiii回代過程：回代過程：共進(jìn)行共進(jìn)行 n 1步，得步，得到到 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa 運(yùn)算量運(yùn)算量 （Amount of Computation）（1 1）用克萊姆用克萊姆（CramerCramer）法則求解法則求解n n階線性方程組階線性方程組 每個(gè)行列式由每個(gè)行列式由n!n!項(xiàng)相加，而每項(xiàng)包含了項(xiàng)相加，而每項(xiàng)包含了n n個(gè)因子個(gè)因子相乘，乘法運(yùn)算次數(shù)為相乘，乘法運(yùn)算次數(shù)為(

6、 (n-1)n !n-1)n !次次. .,1, 2,.,iiDxinD僅考慮乘僅考慮乘( (除除) )法運(yùn)算法運(yùn)算, ,計(jì)算解向量包括計(jì)算計(jì)算解向量包括計(jì)算n+1n+1個(gè)行列式和個(gè)行列式和n n次除法運(yùn)算次除法運(yùn)算, ,乘乘( (除除) )法運(yùn)算次法運(yùn)算次數(shù)數(shù)N=(n+1)(n-1)n!+n. .當(dāng)當(dāng)n=8時(shí)時(shí),N200，0000（2） 高斯消去法高斯消去法:第第1 1個(gè)消去步個(gè)消去步， 計(jì)算計(jì)算l li1i1(i=2,3(i=2,3，n)n)， 有有n-1n-1次次除法運(yùn)算除法運(yùn)算. . 使使a aijij(1)(1)變?yōu)樽優(yōu)?a aijij(2)(2) 以及使以及使b bi i(1)(1

7、)變?yōu)樽優(yōu)閎 bi i(2)(2)有有n(n-1)n(n-1)次乘法運(yùn)算次乘法運(yùn)算. . 第第k k個(gè)消去步個(gè)消去步，有，有n-kn-k次除法運(yùn)算、次除法運(yùn)算、( (n-k+1)(n-k)n-k+1)(n-k)次次乘法運(yùn)算乘法運(yùn)算. .乘法運(yùn)算總次數(shù)為：乘法運(yùn)算總次數(shù)為： 除法運(yùn)算總次數(shù)為除法運(yùn)算總次數(shù)為: : (n-1)+ (n-1)+1=n(n-1)/2+1=n(n-1)/2311 (13nk k k)(n)n回代過程的計(jì)算回代過程的計(jì)算除法運(yùn)算次數(shù)為除法運(yùn)算次數(shù)為n次次. 乘法運(yùn)算的總次數(shù)為乘法運(yùn)算的總次數(shù)為 n+(n-1)+1=n(n-1)/2次次 Gauss Gauss消去法消去法

8、除法運(yùn)算次數(shù)為除法運(yùn)算次數(shù)為: :n(n-1)/2+n=n(n+1)/2n(n-1)/2+n=n(n+1)/2， 乘法運(yùn)算次數(shù)為乘法運(yùn)算次數(shù)為: : n(n-1)(n+1)/3+n(n-1)/2=n(n-1)(2n+5)/6 n(n-1)(n+1)/3+n(n-1)/2=n(n-1)(2n+5)/6， 通常也說通常也說GaussGauss消去法的運(yùn)算次數(shù)與消去法的運(yùn)算次數(shù)與n n3 3同階，記為同階，記為O(nO(n3 3) )(30,9890)n 為順序順序GaussGauss消去法可執(zhí)行的前提消去法可執(zhí)行的前提定理定理 1 1 給定線性方程組給定線性方程組 ，如果，如果n n階方陣階方陣

9、的所有順序主子式都不為零，即的所有順序主子式都不為零，即 則按順序則按順序GaussGauss消去法所形成的各主元素消去法所形成的各主元素 均不為零，從而均不為零，從而Gauss 消去法可順利執(zhí)行。消去法可順利執(zhí)行。AxbA( )(1,2, )kkkakn注：注：當(dāng)線性方程組的系數(shù)矩陣為對(duì)稱正定或嚴(yán)格對(duì)角當(dāng)線性方程組的系數(shù)矩陣為對(duì)稱正定或嚴(yán)格對(duì)角占優(yōu)陣時(shí)，按占優(yōu)陣時(shí)，按GaussGauss消去法計(jì)算是穩(wěn)定的。消去法計(jì)算是穩(wěn)定的。, 0, 0222112112111aaaaDaD01111kkkkkaaaaDIllustration3、列主元（、列主元（ Column pivot element

10、 ）Gauss消去法：消去法：1、輸入矩陣階數(shù)輸入矩陣階數(shù)n，增廣矩陣增廣矩陣 A(n,n+1);2、對(duì)于對(duì)于nk, 2 , 1(1) 按列選主元：選取按列選主元：選取 l 使使 0maxikniklkaa(2) 如果如果 ，交換，交換 A(n,n+1) 的第的第k行與第行與第l 行元素行元素kl (3) 消元計(jì)算消元計(jì)算 ：nkiaalkkikik,1 .1,1,1, lnkjnkiaaakjikijij3、回代計(jì)算回代計(jì)算1 ,1, ，/）（,1nniaxabxiinijjijii4 4無回代過程的主元消去法無回代過程的主元消去法算法：算法：第一步：選主元，在第一列中選絕對(duì)值最大的元素，設(shè)

11、第第一步：選主元，在第一列中選絕對(duì)值最大的元素，設(shè)第k行為主元行，行為主元行， 將主元行換至第一行，將第一個(gè)方程中將主元行換至第一行，將第一個(gè)方程中x1的系數(shù)變?yōu)榈南禂?shù)變?yōu)?，并從，并從 其余其余個(gè)方程中消去個(gè)方程中消去x1。第二步：在第二列后第二步：在第二列后n 1個(gè)元素中選主元，將第二個(gè)方程中個(gè)元素中選主元，將第二個(gè)方程中x2的的 系數(shù)變?yōu)橄禂?shù)變?yōu)?，并從其它，并從其它個(gè)方程中消去個(gè)方程中消去x2。第第k步：在第步：在第k列后列后n k個(gè)元素中選主元，換行，將第個(gè)元素中選主元，換行，將第k個(gè)方程個(gè)方程xk的系數(shù)的系數(shù) 變?yōu)樽優(yōu)?，從其它，從其它個(gè)方程中消去變量個(gè)方程中消去變量xk，nkki

12、nkkjaaaankkjaaakkjkikkijkijkkkkkjkkj, 1, 1, 11, 1,1, 1,)()1()1()()1()1()(消元公式為：消元公式為：對(duì)對(duì)k = 1, 2, , 按上述步驟進(jìn)行到第按上述步驟進(jìn)行到第n步后，方程組變?yōu)椋翰胶?，方程組變?yōu)椋?(1,)(1, 22)(1, 11nnnnnnnnaxaxax即為所求的解即為所求的解注：注：無回代的無回代的GaussGauss消元法實(shí)際上就是將消元法實(shí)際上就是將 方程組的系數(shù)矩陣化為行最簡形矩陣。方程組的系數(shù)矩陣化為行最簡形矩陣。5無回代消去法的應(yīng)用無回代消去法的應(yīng)用（1）解線性方程組系解線性方程組系設(shè)要解的線性方程組

13、系為：設(shè)要解的線性方程組系為：AX = b1, AX = b2, AX = bmniaaabxxXaaaaAinninininnnnn, 2, 1)(1,)(1, 2)(1, 111111上述方程組系可以寫為上述方程組系可以寫為AX = B = (b1, , bm)因此因此X = A-1B 即為線性方程組系的解。即為線性方程組系的解。 在計(jì)算機(jī)上只需要增加幾組右端常數(shù)項(xiàng)的存貯單元，在計(jì)算機(jī)上只需要增加幾組右端常數(shù)項(xiàng)的存貯單元，其結(jié)構(gòu)和解一個(gè)方程組時(shí)一樣。其結(jié)構(gòu)和解一個(gè)方程組時(shí)一樣。行行n21nnnnnnaaaaaaaaa212222111211)(1,)1(1,)(1,2)1(1,2)(1,

14、1)1(1, 1mnnnnmnnmnnaaaaaa系數(shù)系數(shù)右端右端（2）求逆矩陣求逆矩陣設(shè)設(shè)A = (aij)n n是非奇矩陣是非奇矩陣，A 0，且令且令nnijxAX)(1由于由于 AA-1 = AX = I因此，求因此，求A-1的問題相當(dāng)于解下列線性方程組的問題相當(dāng)于解下列線性方程組1010,0012112111nnnnnxxxAxxxA相當(dāng)于相當(dāng)于（1）中中m = n, B = I 的情形。的情形。 （3）求行列式的值求行列式的值用高斯消去法將用高斯消去法將 A化成化成)()1(11)()2(22)1(11nnnnnnaaaaaA2.2.求解三對(duì)角方程組的追趕法求解三對(duì)角方程組的追趕法

15、nnnnnnnfffxxxbacbacbacb212111122211定理：定理：若若 A 為為對(duì)角占優(yōu)對(duì)角占優(yōu) 的三對(duì)角陣，且滿足的三對(duì)角陣，且滿足 則方程組有唯一的則方程組有唯一的LU分解。分解。0,0, 0|, 0|11 iinncaabcb直接比較等式兩邊的元素，可得到計(jì)算公式直接比較等式兩邊的元素，可得到計(jì)算公式第二步第二步: 追追即解即解 ：fyL 111,fy1()(2,.,)iiiiifyyin第三步第三步: 趕趕即解即解 ：yxU 1,(1,.,1)nniiiixyxyxin第一步第一步: 對(duì)對(duì) A 作作Crout 分解分解1122111nnnA 3 3 矩陣的矩陣的三角分解

16、法三角分解法 高斯消元法的矩陣形式高斯消元法的矩陣形式 每一步消去過程相當(dāng)于左乘初等變換矩陣每一步消去過程相當(dāng)于左乘初等變換矩陣L Lk k(2)(1)(2)(1)11112111113111 , 1101 2 3001L()()iin i, ,nbbAL ALllaall記：其中(3)(2)(3)(2)222222223222 , 10101 3 4001L()()iini, ,nbbAL ALlaall記：(3)(1)(3)(1)2121 , bbAL L AL L-1ii1,1,110 10111L= 01010101 i iiiininiLllll 列 i列11211121(n)( )

17、nn(n)( )nn AL LL AbbL LL1111121( )(n)(n)nLLUAL LL AAA 的的 LU 分解分解( LU factorization )定理定理2：（矩陣的三角分解）設(shè)（矩陣的三角分解）設(shè)A為為n n實(shí)矩陣，如果實(shí)矩陣，如果解解AX = b用高斯消去法能夠完成（限制不進(jìn)行行的交用高斯消去法能夠完成（限制不進(jìn)行行的交換，即換，即 ），則矩陣），則矩陣A可分解可分解為單位下三角矩陣為單位下三角矩陣L與上三角知陣與上三角知陣U的乘積。的乘積。A = LU且這種分解是唯一的。且這種分解是唯一的。nkakkk, 2, 1, 0)(L 為單位下三角陣而為單位下三角陣而 U

18、為為一般一般上三上三角陣的分解稱為角陣的分解稱為Doolittle 分解分解 （2）L 為一般下三角陣而為一般下三角陣而 U 為為單位單位上三上三角陣的分解稱為角陣的分解稱為Crout 分解分解。 Doolittle分解法分解法 ： 通過比較法直接導(dǎo)出通過比較法直接導(dǎo)出L 和和 U 的計(jì)算公式。的計(jì)算公式。思思路路 nnnnnnnnuuullaaaa.1.11.1111211111 ),min(1jikjkkiul jiaLU 分解求解線性方程組分解求解線性方程組 LY b , UXY AXb112221313212(1)1111121n22222nnn111 1 UXnnnnn nnnyby

19、bLYbybxyxyYxylllllluuuuuu 直接三角分解法解直接三角分解法解AX = b的計(jì)算公式的計(jì)算公式niauii, 2 , 111niualii, 2 , 11111對(duì)于對(duì)于r = 2, 3, , n計(jì)算計(jì)算（2）計(jì)算計(jì)算U的第的第r行元素行元素 ), 1,( 11nrriulaurkkirkriri（3）計(jì)算計(jì)算L的第的第r 列元素列元素 (r n), 1()(11nriuulalrrrkkrikirir(1), 3 , 2(111niylbybykikikii) 1, 2, 1(1niuxuyxuyxiiknikikiinnnn(4)(5)123 12314 2521831

20、520100123 210014.3510024 (14,18,20)(14, 10, 72) ,(14, 10, 72)(1,2,3) . TTTTxxxALULyyUxx 例：用直角三角分解法解解：用分解計(jì)算公式得求解4 4 平方根法平方根法1 1矩陣的矩陣的LDRLDR分解分解定理定理3：如果如果n階矩陣階矩陣A的所有順序主子式均不等于零，的所有順序主子式均不等于零，則矩陣則矩陣A存在唯一的分解式存在唯一的分解式A = LDR其中其中L和和R分別是分別是n階單位下三角陣和單位上三角陣，階單位下三角陣和單位上三角陣，D是是n階對(duì)角元素階對(duì)角元素的不為零的對(duì)角陣，上述分解也稱為的不為零的對(duì)角

21、陣，上述分解也稱為A的的LDR分解分解。 2平方根法平方根法 如果如果A為對(duì)稱正定矩陣為對(duì)稱正定矩陣，則存在一個(gè)實(shí)的非奇異下三則存在一個(gè)實(shí)的非奇異下三角矩陣角矩陣，使使A=LLT ，且當(dāng)限定的對(duì)角元素為正時(shí)且當(dāng)限定的對(duì)角元素為正時(shí)，這種分解是唯一的這種分解是唯一的。定理定理4：（對(duì)稱正定矩陣的三角分解）（對(duì)稱正定矩陣的三角分解）將將對(duì)稱對(duì)稱 正定陣正定陣 A 做做 LU 分解分解U =uij=u11uij / uii111u22unn記為記為UD A 對(duì)稱對(duì)稱TUL 即即TLDLA 記記 D1/2 =11u22unnu2/1LDL 則則 仍是下三角陣，且有仍是下三角陣，且有TLLA 用平方根法

22、解線性代數(shù)方程組的算法用平方根法解線性代數(shù)方程組的算法（1）對(duì)矩陣對(duì)矩陣A進(jìn)行進(jìn)行Cholesky分解分解，即即A=LLT，由矩陣乘法由矩陣乘法：對(duì)于對(duì)于 i = 1, 2, n 計(jì)算計(jì)算21112ikikiiiilal1, 2, 111ijlllaljjjkikikijij（2）求解下三角形方程組求解下三角形方程組 iikikikiilylby11（3）求解求解LTX = y) 1 , 1,(1nnilxlyxiiknikkiii3改進(jìn)平方根法改進(jìn)平方根法 11111112231131222111323121nnnnnllllldddllllAikdlskkikik其中其中111121212

23、22111nnnnnlldssdsd改進(jìn)平方根法解對(duì)稱正定方程組的算法改進(jìn)平方根法解對(duì)稱正定方程組的算法 111111112, 3,jijijikkjkijijjjiiiiiikikkdainsas llsddas l對(duì) 于 計(jì) 算令令LTX = y，先解下三角形方程組先解下三角形方程組 LDY = b 得得), 2, 1(11nidyldbyiikikikkkii解上三角形方程組解上三角形方程組 LTX = Y 得得 ) 1, 2 , 1,(1nnixlyxnikkikii5 5 向量和矩陣的范數(shù)向量和矩陣的范數(shù) 1 1向量的范數(shù)向量的范數(shù)定義定義1 1：設(shè)設(shè)X R n， 表示定義在表示定義

24、在Rn上的一個(gè)實(shí)值函數(shù)上的一個(gè)實(shí)值函數(shù)，稱之為稱之為X的范數(shù)的范數(shù)，它具有下列性質(zhì)它具有下列性質(zhì)：XaaX（3）三角不等式三角不等式：即對(duì)任意兩個(gè)向量即對(duì)任意兩個(gè)向量X、Y R n，恒有恒有 YXYX(1) (1) 非負(fù)性非負(fù)性：即對(duì)一切即對(duì)一切X R n，X 0, 0(2) (2) 齊次性齊次性：即對(duì)任何實(shí)數(shù)即對(duì)任何實(shí)數(shù)a R，X R n， 設(shè)設(shè)X = (x1, x2, xn)T，則有則有nxxxX211（1）222212nTxxxXXX（2）inixX1max（3）三個(gè)常用的范數(shù)：三個(gè)常用的范數(shù)：范數(shù)等價(jià)范數(shù)等價(jià): : 設(shè)設(shè)A A 和和B B是是R R上任意兩種范數(shù)，若存在上任意兩種范數(shù)，

25、若存在 常數(shù)常數(shù) C C1 1、C C2 2 0 0 使得使得 , , 則稱則稱 A A 和和B B 等價(jià)等價(jià)。定理定理5：定義在定義在Rn上的向量范數(shù)上的向量范數(shù) 是變量是變量X分量的分量的 一致連續(xù)函數(shù)一致連續(xù)函數(shù)。 X()Xf X定理定理6 6：在在Rn上定義的任一向量范數(shù)上定義的任一向量范數(shù) 都與范數(shù)都與范數(shù) 等價(jià)等價(jià)， 即存在正數(shù)即存在正數(shù) M 與與 m ( Mm ) 對(duì)一切對(duì)一切X Rn，不等式不等式X1X11XMXXm成立成立。推論推論：Rn上定義的任何兩個(gè)范數(shù)都是等價(jià)的。上定義的任何兩個(gè)范數(shù)都是等價(jià)的。 111XXXnXnXX1XnXX2對(duì)常用范數(shù)，容易驗(yàn)證下列不等式：對(duì)常用范

26、數(shù)，容易驗(yàn)證下列不等式： 定義定義2：設(shè)給定設(shè)給定Rn中的向量序列中的向量序列 ，即即kX01, X , , kXX其中其中TknkkkxxxX)()(2)(1,若對(duì)任何若對(duì)任何i (i = 1, 2, n )都有都有*)(limikikxx則向量則向量 TnxxX),(*1*limXXkk稱為向量序列稱為向量序列 的極限的極限，或者說向量序列或者說向量序列 依坐標(biāo)收斂于向量依坐標(biāo)收斂于向量 ，記為記為kXkX*X定理定理7：向量序列向量序列Xk依坐標(biāo)收斂于依坐標(biāo)收斂于X*的充要條件是的充要條件是0lim*XXkk向量序列依范數(shù)收斂與依坐標(biāo)收斂是等價(jià)的。向量序列依范數(shù)收斂與依坐標(biāo)收斂是等價(jià)的。

27、2 2矩陣的范數(shù)矩陣的范數(shù)定義定義3：設(shè)設(shè)A為為n 階方陣階方陣，Rn中已定義了向量范數(shù)中已定義了向量范數(shù) ， 則稱則稱 為矩陣為矩陣A A的范數(shù)或模的范數(shù)或模， 記為記為 。即。即AXx1supAAXAx1sup矩陣范數(shù)的基本性質(zhì)矩陣范數(shù)的基本性質(zhì)： （1）當(dāng)）當(dāng)A = 0時(shí)，時(shí)， 0，當(dāng)，當(dāng)A 0時(shí)，時(shí)， 0AA（2）對(duì)任意實(shí)數(shù)對(duì)任意實(shí)數(shù)k 和任意和任意A，有，有AkkA（3）對(duì)任意兩個(gè)對(duì)任意兩個(gè)n階矩陣階矩陣A、B有有BABA（5）相容性相容性 對(duì)任意兩個(gè)對(duì)任意兩個(gè)n階矩陣階矩陣A、B，有有BAAB（4）對(duì)任意向量）對(duì)任意向量X Rn，和任意矩陣和任意矩陣A，有有（相容性條件）XAAX例

28、例5:5:設(shè)設(shè)A A(a(aijij)M. )M. 定義定義2,11|nijijAan證明證明：這樣定義的非負(fù)實(shí)數(shù)不是相容的矩陣范數(shù)這樣定義的非負(fù)實(shí)數(shù)不是相容的矩陣范數(shù). .證明：設(shè)1111,1111AB2222AB| 1,| 1,| 2ABAB從而| | |ABAB定理定理8：設(shè)設(shè)n 階方陣階方陣A = (aij)n n，則，則（）與）與 相容的矩陣范數(shù)是相容的矩陣范數(shù)是1xniijjaA11max（）與）與 相容的矩陣范數(shù)是相容的矩陣范數(shù)是2x12A其中其中 1為矩陣為矩陣ATA的最大特征值。的最大特征值。（）與）與 相容的矩陣范數(shù)是相容的矩陣范數(shù)是xnjijiaA1max上述三種范數(shù)分別

29、稱為矩陣的上述三種范數(shù)分別稱為矩陣的1-1-范數(shù)、范數(shù)、2-2-范數(shù)和范數(shù)和- -范數(shù)。范數(shù)?？梢宰C明可以證明, 對(duì)方陣對(duì)方陣 和和 ，有，有nnRAnx R22| | | | |FAxAx ninjijFaA112| ( (向量向量| | | |2 2的直接推廣的直接推廣) )FrobeniusFrobenius范數(shù)范數(shù): :3矩陣矩陣的范數(shù)與特征值之間的關(guān)系的范數(shù)與特征值之間的關(guān)系定理定理9：矩陣矩陣A 的任一特征值的絕對(duì)值不超過的任一特征值的絕對(duì)值不超過A的范數(shù)，即的范數(shù)，即 定義定義4：矩陣矩陣A 的諸特征值的最大絕對(duì)值稱為的諸特征值的最大絕對(duì)值稱為A的譜半徑，的譜半徑，1( )max

30、ii nA 記為：記為：1maxii nA 21max(ii nA 譜范數(shù)）并且如果并且如果A A為對(duì)稱矩陣，則為對(duì)稱矩陣，則 注注: :R Rn nn n中的任意兩個(gè)矩陣范數(shù)也是等價(jià)的。中的任意兩個(gè)矩陣范數(shù)也是等價(jià)的。定義定義5 5： 設(shè)設(shè)| | | |為為R Rn nn n上的矩陣范數(shù)，上的矩陣范數(shù)，A,BA,BR Rn nn n稱稱 |A-B|A-B|為為A A與與B B之間的距離之間的距離。定義定義6 6：設(shè)給定設(shè)給定R Rn nn n中的矩陣序列中的矩陣序列 ，若，若lim0kkAA則稱矩陣序列則稱矩陣序列 收斂于矩陣收斂于矩陣A A，記為，記為limkkAAkAkA定理定理1010

31、 設(shè)設(shè)BRBRn nn n，則由，則由B B的各冪次得到的的各冪次得到的 矩陣序列矩陣序列B Bk k, k=0,1,2k=0,1,2) )收斂于零矩陣收斂于零矩陣 （ ）的充要條件）的充要條件 為為 。 ()1Blim0kkB 求解求解 時(shí)，時(shí)，A 和和 的誤差對(duì)解的誤差對(duì)解 有何影響？有何影響？bxA bx 設(shè)設(shè) A 精確，精確， 有誤差有誤差 ，得到的解為，得到的解為 ，即，即bb xx bbxxA )(bAx 1 |1bAx 絕對(duì)誤差放大因子絕對(duì)誤差放大因子|xAxAb 又又|1bAx |1bbAAxx 相對(duì)誤差放大因子相對(duì)誤差放大因子6 線性方程組的性態(tài)和解的誤差分析線性方程組的性態(tài)

32、和解的誤差分析6 Error Analysis for . bxA 設(shè)設(shè) 精確，精確，A有誤差有誤差 ，得到的解為，得到的解為 ，即，即bA xx bxxAA )( bxxAxxA )()( )(1xxAAx |11AAAAAAxxx bxAAxAA )()(xAxAA )(xAAAAIx 111)( Wait a minute Who said that ( I + A 1 A ) is invertible?(只要只要 A充分小，使得充分小，使得|1|1|1111AAAAAAAAAAAAxx 是關(guān)鍵是關(guān)鍵的誤差放大因子，稱為的誤差放大因子，稱為A的的條件數(shù)條件數(shù)，記為，記為cond (A)

33、 ,越越 則則 A 越病態(tài)，越病態(tài)，難得準(zhǔn)確解。難得準(zhǔn)確解。|1 AA大大定義定義7：設(shè)設(shè)A 為為n 階非奇矩陣，稱數(shù)階非奇矩陣，稱數(shù) 為矩陣為矩陣A的條件數(shù)，的條件數(shù)，AA1條件數(shù)的性質(zhì)：條件數(shù)的性質(zhì)： ）cond ( A )1）cond ( kA )= cond ( A ) , k 為非零常數(shù)為非零常數(shù)）若）若 ， 則則1A1)(cond AA記為記為cond( A )。 注注: : condcond ( (A A) ) 與與 所取的范數(shù)有關(guān)所取的范數(shù)有關(guān)常用條件數(shù)有：常用條件數(shù)有：cond (A)2)(/ )(minmaxAAAATT特別地，若特別地，若 A 對(duì)稱，則對(duì)稱，則|min|max)( 2 Acondcond