第2章-列主元消去法平方根法追趕法

1、2.1.2Gauss列主元消去法與帶列主元的LU分解的作用，我們稱其為主元。（2） 數(shù)值計算中，應盡量避免小數(shù)作除數(shù)，下面的例子說明小主元對解的影響。元素起著非常關鍵（1）看下面的例子，其中上溢，計算不可行。其解存在且唯一。而在Gauss消去法的第k步消元過程中，1.Gauss列主元消去法 例4 在一臺八位十進制的計算機上，用Gauss消去法解線性方程組在八位十進制的計算機上，進行兩次消元 顯然有無窮多解。解：線性方程組有唯一解。但實際上det(A)0， 在計算過程中的舍入誤差使解的面目全非了，這些均是由于小主元作除數(shù)所致。Gauss列主元消去法： 為避免小主元作除數(shù)、或0作分母，首先在第k列

2、主對角元以下（含主對角元） 將在消元過程中，每一步都按列選主元的Gauss消去中增加選主元的過程，即在第k步消元時，在Gauss消去法元素中挑選絕對值最大的數(shù)，使得該數(shù)位于主對角線上，將該絕對值最大的數(shù)稱為列主元。法稱之為Gauss列主元消去法。并通過初等行交換，然后再繼續(xù)消元。例5 用Gauss列主元消去法解例4中的方程組。解：=用回代法求 得數(shù)值解為： 方程組的精確解為:第二次選列主元，交換第二行和第四行，左乘置換矩陣P2: 第三次選列主元，交換第三行和第四行，左乘置換矩陣P3: 最后一次消元，消去第三列主對角元以下的非零元，左乘L3:2.帶列主元的LU分解 第一次選列主元，交換第一行和第

3、三行，左乘置換矩陣P1:第一次消元，消去第一列主對角元以下的非零元，左乘L1:第二次消元，消去第二列主對角元以下的非零元，左乘L2:的按列選主元的LU分解，還是以例1中的系數(shù)由上述Gauss列主元消去過程可以得到矩陣矩陣A為例來說明。實際上，上述過程可以表示為顯然， 似乎并不是一個單位下三角矩陣。我們將上式改寫為進一步（組合）得即由 的定義知=從而，記和顯然，和分別與 結構相同,角部分的元素進行相應的對調(diào)。 令只是下三從而有則有這樣，我們得到另一種形式的矩陣分解： 一般地,如果A為n階方陣，進行Gauss列類似的，可以改寫成：主元消去過程為：其中， （k=1,2,n-2）與Lk的結構相同，只是

4、下三角部分元素經(jīng)過了則P、單位下三角矩陣L和上三角矩陣U，對調(diào)。因此，令定理2.2對任意n階矩陣A，均存在置換矩陣使得用Gauss列主元消去法解如下方程組并給出 解：PA=LU分解。例6用回代法求解,得即 下面求相應的PA=LU分解第一次選列主元，交換第1行和第3行，左乘置換矩陣P1 第一次消元，用L1左乘(P1A),即 第二次選列主元，交換第2行和第3行，即左乘置換矩陣 第二次消元，用L2左乘(P2L1P1A),即注意：則分解應為：即有：用列主元Gauss消去法解如下方程組，并利用得到的解：上三角矩陣求出det(A)的值。練習題 從而求得方程組解：又，則而一般情形下，其中k為交換次數(shù)，這里k

5、=2。那么返回本節(jié)2.1.3 對稱正定矩陣的Cholesky分解 A為半正定對稱矩陣，對任何xRn，(Ax, x) 0。A為正定對稱矩陣，如果x0Rn，恒有(Ax, x) 0。A為正定(半正定)對稱矩陣A為正定(半正定)對稱矩陣A的特征值為正（非負）。A的各階順序主子式為正（非負）。正定（半正定）對稱矩陣的定義和某些性質(zhì)：大家已經(jīng)知道，對于一般方陣，為了消除LU分解的局限性和誤差的過分積累，而采用選主元的方法。但對于對稱正定矩陣而言，選主元卻是完全不必要的。將對稱正定陣 A 做 LU 分解，得到L和U，U =uij=1*11 由A 的LU分解的唯一性即記 D1/2 =則 是下三角矩陣u22un

6、nu11進一步即 ，由A 對稱，得從而得到對稱正定陣Cholesky的分解：定理2.3（Cholesky分解） 對任意n階對稱正定矩陣 A，角矩陣L 使 A=LLT 成立，均存在下三進一步地, 如果規(guī)定 L陣A的Cholesky分解。的對角元為正數(shù)，則L是唯一確定的。稱其為對稱正定矩因此，若線性方程組Ax=b的系數(shù)矩陣是對稱（1）求A的Cholesky分解：A=LLT；（2）求解：Ly=b 得 y；（3）求解：LTx=y 得 x；定理2.3證明過程也提供計算Cholesky分解的方法。下面我們主要介紹計算Cholesky分解的更簡便正定的，我們自然可以按如下的步驟求其解：的方法直接分解法。設利

7、用矩陣乘法規(guī)則和L的下三角結構得到： 首先，由 得再由ai1=l11li1，得這樣便得到了矩陣L的第一列。假定已算出L的第j-1列元素，由得再由得i = j+1, j+2,n Cholesky方法(平方根法)解線性代數(shù)方程組：（1）對矩陣A進行Cholesky分解，即 A=LLT，對于 j =1,2,n 計算i = j+1, j+2,n 計算次序為： （2）求解下三角形方程組 Ly= b 得 y （3）求解上三角形方程組 LTx= y 得 x由得因此在分解過程中L元素的數(shù)量級不會增長，由此推出 ，k=1,2,j。故平方根法通常是數(shù)值穩(wěn)定的，不必選主元。由于A的元素aij被用來計算出lij后不再

8、使用，所以可將L的元素存儲在A的對應位置上。容易算出平方根法的運算量，僅是Gauss消去法的一半。用Cholesky方法解線性方程組Ax=b, 其中解:因此，A為對稱正定矩陣，故存在 A=LLT 。L的諸元素：例7顯然AT=A, 且由分解公式依次計算出從而得 求下三角方程組Ly=b的解，得再上三角方程組LTx=y的解，得2.1.4 三對角矩陣的三角分解 設三對角矩陣如果A存在LU分解A=LU,可知L和U有如下形式利用矩陣乘法規(guī)則得到： 追趕法解三對角形方程組的算法：（1）對矩陣A進行LU分解，公式如下：計算次序是： （2）求解下三角形方程組Ly=f （3）求解上三角形方程組Ux = y定理2.4 設具有三對角形式的矩陣A，滿足條件可用追趕法求解，且解唯一。則方程組證 由（2-26）和條件（1）知， 且有下面用歸納法證明，且有假設從（2-26）和條件（3），知故得出 再應用條件（2），得從而可得故方程組 Ax=f 的解存在唯一。又因為于是有即追趕法計算過程中的中間數(shù)有界，不會產(chǎn)生大的變化，從而說明它通常是數(shù)值穩(wěn)定的。 且定理條件中有或 ，如果有某個，則可化成低階方程組求解。解過程僅須5n-4次乘除和3(n-1)次加減運算，總共計其中 di,li,ui和xi分別存在數(shù)組c,a,b和 f 中。追趕法公式簡單，計算量和存儲量都小。整個求僅需4個一