【文章內(nèi)容簡介】 ???????nkjlulaunkiulalnkiullaukkkrrjkrkjkjkrrkirikikkrrkirikikkk???類似地，有，故有所以根據(jù)由于關(guān)于 L, U元素的存放 從（ 322），（ 323）可以看出。 A的元素 aij在計算出 或 以后就不再有用了 。 ijl iju浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 31 故 L,U的非零元素便可以存放在矩陣 A中的相應(yīng)位置上了。 最后， A所存放的元素是： ????????????nnnnnnlllulluul??????212222111211 容易證明： 1. 即是 Gauss消去法 中各次的主元素。 nnll ,11 ?浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 32 2. 如果 A 的各階主子矩陣均非奇異， 上述過程可以一直進行到底。 矩陣 A 除了以上介紹的 LU 分解以外， 還有一種重要的分解方法可以用于求解 線性方程組。即 QR 分解。 定理 ：任意矩陣 A，總是以分解成正交 矩陣 Q 與上三角矩陣 R 的乘積： 如果 A 是非奇異的，則在規(guī)定 R的對角元 素的符號下，分解式是唯一的。 如果 ， 則 Q 是正交矩陣 RQA ??T ??1浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 33 常見的有 Householder 正交三角分解 有了正交三角分解以后，解方程組 就變得非常簡單： bQRXbQ RXbAXT??? 用 Householder 變換進行分解。從而 求解線性方程組的過程是非常穩(wěn)定的。也 不必選主元。特別在方程性質(zhì)不太好時， 更顯其優(yōu)越性，但計算量大。 Householder 正交三角分解還有其他用途。 浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 34 PROGRAM EXAMPLE DIMENSION A(5,5),B(3),IND(3),C(3) DATA B /, A(1,1)= ?????? A(3,3)= N=3 NP=5 CALL LUDCMP(A,N,NP,IND,D) CALL LUBKSB(A,N,NP,IND,B) WRITE(*,*) B C(1)=1. C(2)=2. C(3)=3. CALL LUBKSB(A,N,NP,IND,C) WRITE (*,*) C STOP END 浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 35 ?????????????? ??????????????????????????????? ?????????????????? ???? ?????????????????????4350000000000002940000000000003110064200294L U B K S BL U B K S BL U D C M PBA的變化：前同的變化：???????????321 D 的值：浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 36 程序手稿 原程序文件 目標程序 執(zhí)行程序 輸出結(jié)果 編輯（ WS） 編譯（ F77） 連結(jié)（ LINK） 執(zhí)行（程序名） 庫 修改 圖 程序調(diào)試流程圖 浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 37 迭代改進 由前面討論，我們知道，由于各種原因， 特別是方程組本身的病態(tài)，將會導(dǎo)致解與真 解之間的誤差不能達到令人滿意的程度。有 各種處理病態(tài)方程組的方法。這里介紹一種 簡單實用的方法。它還可以用于一般方程組 的高精度求解。 該方法的基本思想是利用迭 代逐步改善解的精度 （關(guān)鍵在于在迭代過程 中有些運算需用雙精度進行） 迭代改善過程的框圖如下： 浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 38 LUAA ?的三角分解作? ? ? ? ? ? bxL U xx ?? 011 ：求三角方程組的解? ? ? ???? AXb ??用雙精度計算殘向量：? ? ? ? ? ???? ??L UZZ ：求出解的改善量? ? ? ? ? ???? Zxx ??? 1求改善解：? ? ??? ?Z? ? ? ?????????11 xx? ? xx ??1?結(jié)束是 否 圖 迭代改善過程 浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 39 由上圖可知，迭代改進的計算，只要 在開始時作一次三角分解。以后只是反復(fù) 求解三角方程組就可以獲得解的改善。 關(guān)于解的改善的程度有以下結(jié)論： 假設(shè)在浮點數(shù)的尾數(shù)是 t 位（二進制）的 計算機上用消去法計算。 A 的條件數(shù)為 一般可設(shè) 則：經(jīng)過一次迭代，解的精度近似地改善 了 tp 位。因此迭代次數(shù) k 滿足 k(tp)?t 就夠了。 或近似地用估算式： ? ? pACo n d 2? tp ??0? ?? ? ????????? 112lo g Zxtk浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 40 奇異值分解 （ SVD） 解方程組時，常常會出現(xiàn)奇異或十分 接近于奇異的情況。用通常的 Gauss消去法 或者 LDU分解法難以得到滿意的解。對這 類問題，我們有一個有效的方法，它叫 奇 異值分解法 Singular Value Deposition 它不但可以診斷出問題所在，而且有時能 給出一個有用的數(shù)值結(jié)果。 SVD方法基于下面這個線性代數(shù)定理， 由于定理本身不是我們研究的重點，這里 不加證明。 浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 41 定理： 對任意 M?N矩陣 A， 這里 M?N，它都可以分解成下列形式： A=UWVT 其中： U是 M?N列正交矩陣； V是 N?N 正交矩陣； W是 N?N對角矩陣。且對角元素非負。 即： ? ? ? ?NlkuuVwwwUAklMiilikTn????????????????????,1121?且?浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 42 IVVUUNlkvvTTNjkljljk???????用矩陣表示：,1,1? 由于 V是方陣，故它還是行正交即 不管矩陣 A是否奇異。 SVD分解都能做到。而且它“幾乎”是唯一的。即允許 U， V的列進行變換并進行 W相應(yīng)交換的前提下是唯一的。 如果 A是 N?N方陣，則 U， V， W都是方陣。且分解式可寫為： .IVV T ?浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 43 ? ?? ?TjTjUwdi agVAVwdi agUA??????????????????? 11由此 但是，如果其中有一些 或十分接 近于 0，即 A奇異或接近奇異，那么 A1 就難以求得。因此， SVD分解可以通過 判斷 的大小來分析 A的性態(tài)。 當 A是奇異時 ，我們就考慮 0?jwjw? ? ? ? ? ?jj wwAC o n d m inm a x?? ?243 ??? bAx nn在某種意義下的解。 浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 44 由代數(shù)知識，有 當 rank(A)rank(A,b)時 ， （ 324）為矛盾方程組。無解。 當 rank(A)=rank(A,b)時 ， （ 324）有無窮多解。 在這些解中。有一個 最小長度解 在某些場合是有意義的。 在求這個解以前，先介紹幾個重要的概念。 1.（ 324）定義了一個從向量空間 x到向 量空間 b的線性映射 A。 2. 如果Ａ奇異，則有 ,使得 m in )( 2 ?x0?x浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 45 0?AX ? ?253? 所有滿足（ 325）的 x全體稱 Ａ的零空間 。 零空間的維數(shù)稱為零度 。 ３ . 所有存在原象 x, 使得（ 324）成立的向量 b的全體稱為 Ａ的域 。 域的維數(shù)稱為Ａ的秩 。 ４ . 如果Ａ非奇異，則零空間只有零向量； 零度＝０；Ａ的秩＝Ｎ； 如果Ａ奇異，則零度 0。 秩 N。 但可以證明： 零度＋秩＝Ｎ 。 現(xiàn)在再看看ＳＶＤ分解的意義。 浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 46 ＳＶＤ分解事實上分別構(gòu)造了Ａ的零 空間和域的各一組正交基。 由所有 對應(yīng)的Ｕ的第 j列向量 是張成域的一組正交基 。 由所有 對應(yīng)的Ｖ的第 j列向量 是張成零空間的一組正交組 。 現(xiàn)在考慮（ 324）的解。如果 的域， 則方程有無窮解。因為零空間的任何向量的 0?jw0?jwAb?? ? bxVwwwuuuuTnjnj?????????????????????121,,浙江大學(xué)研究生學(xué)位課程 《實用數(shù)值計算方法》 47 ? ?? ? ? ?? ? buxvwuxvwxvwxvwxvwxvwuuuxVwwwwuuuxAkwnkkTkkniiTiiTnnTjjTTnjTnjn????????????