【正文】 《數(shù)值方法》實驗報告 1 線性方程組 AX=B 的數(shù)值計算方法實驗 【 摘要 】 在自然科學(xué)與工程技術(shù)中很多問題的解決常常歸結(jié)為解線性代數(shù)方程組。例如電學(xué)中的網(wǎng)絡(luò)問題，船體數(shù)學(xué)放樣中建立三次樣條函數(shù)問題，用最小二乘法求實驗數(shù)據(jù)的曲線擬合問題，解非線性方程組的問題，用差分法或者有限元法解常微分方程，偏微分方程邊值問題等都導(dǎo)致求解線性方程組。線性代數(shù)方面的計算方法就是研究求解線性方程組的一些數(shù)值解法與研究計算矩陣的特征值及特征向量的數(shù)值方法。關(guān)于線性方程組的數(shù)值解法一般有兩類：直接法和迭代法。 關(guān) 鍵 字 高斯消元法、三角分解法、高斯 賽德 爾迭代、稀疏矩陣 一、 實驗?zāi)康? 、三角分解法、高斯 — 賽德爾迭代發(fā)的編程技巧。 AX=B的數(shù)值計算方法。 。 二、 實驗原理 數(shù)學(xué)上，高斯消元法是線性代數(shù)規(guī)劃中的一個算法，可用來為線性方程組求解。 高斯（ Gauss）夏鷗按法其實是將一般的線性方程組變換為三角形（上三角）方程組求解問題（消元法），只是步驟規(guī)范，便于編寫計算機程序。 一般高斯消元法包括兩過程：先把方程組化為同解的上三角形方程組，再按相反順序求解上三角方程組。前者稱為消去 或消元過程，后者稱回代過程。消去過程實際上是對增廣矩陣作行初等變換。 對一般的 n 階方程組，消去過程分 n1 步：第一步消去 11a 下方元素。第二步消去 22a 下方元素， ......，第 n1 步消去 1n1na ， 下方元素。即第 k 步將第 k 行的適當(dāng)倍數(shù)加于其后各行，或可說是從 k+1~n 行減去第 k 行的適當(dāng)倍數(shù)，使它們第k 列元素變?yōu)榱?，而其余列元素減去第 k 行對應(yīng)列元素的倍數(shù)。 《數(shù)值方法》實驗報告 2 三角分解法是將原正方 (square)矩陣分解成一個上三角形矩陣或是排列 (permuted) 的上三角形矩陣和一個 下三角形矩陣，這樣的分解法又稱為 LU 分解法。它的用途主要在簡化一個大矩陣的行列式值的計算過程，求 反矩陣，和求解聯(lián)立方程組。不過要注意這種分解法所得到的上下三角形矩陣并非唯一，還可找到數(shù)個不同 的一對上下三角形矩陣，此兩三角形矩陣相乘也會得到原矩陣。 — 賽德爾迭代 高斯－賽德爾迭代（ Gauss– Seidelmethod）是數(shù)值線性代數(shù)中的一個迭代法，可用來求出線性方程組解的近似值。 研究雅可比迭代法，我們發(fā)現(xiàn)在逐個求 ）（ 1kX? 的分量時，當(dāng)計算到 ）（ 1kiX? 時 ,分量 ）（ 1k1X? ， ......， ）（ 1k1iX? 都已經(jīng)求得，而仍用舊分量 k1X ， ......， ）（ k1iX 計算 ）（ 1kiX? 。由于新計算出的分量比舊分量準(zhǔn)確些，因此設(shè)想一旦新分量 ）（ 1k1X? ， ......， ）（ 1k1iX? 求出，馬上就用新分量 ）（ 1k1X? ， ......， ）（ 1k1iX? 代替雅可比迭代法中 k1X ， ......， ）（ k1iX 來求 ）（ 1kiX? 這就是高斯 賽德爾 (GaussSeidel)迭代法。 把矩陣 A 分解成 ULDA ??? (6) 其中 ? ?nna,.. .,a,ad i a gD 2211? , U,L?? 分別為 A 的主對角元除外的下三角和上三角部分 ,于是 ,方程組 (1)便可以寫成 ? ? bUxxLD ??? 即 22 fxBx ?? 其中 ? ? ? ? bLDf,ULDB 1212 ?? ???? (7) 以 2B 為迭代矩陣構(gòu)成的迭代法 (公式 ) ? ? ? ? 221 fxBx kk ??? (8) 稱為高斯 — 塞德爾迭代法 (公式 ),用變量表示的形式 為 ???? ?,...,k,n,ixaxabax ijnij)k(jij)k(jijiii)k(i210211 11 111??? ???? ?? ????? (9) 《數(shù)值方法》實驗報告 3 矩陣中非零元素的個數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)，并且非零元素的分布沒有規(guī)律，則稱該矩陣為稀疏矩陣 (sparse matrix)；與之相區(qū)別的是，如果非零元素的分布存在規(guī)律（如上三角矩陣、下三角矩陣、對角矩陣），則稱該矩陣為特殊矩陣。 常見于進行大量數(shù)據(jù)計算。 三、 實驗內(nèi)容 1 許多科學(xué)應(yīng)用包含的矩陣帶有很多的零。在實際情況中很重要的三角形線性方程組有如下形式： d1x1+c1x2 =b1 a1x1+d2x2+c2x3 =b2 a2x2+d3x3+c3x4 =b3 aN2xN2+dN1xN1+cN1xN =bN1 aN1xN1+dNxN =bN 構(gòu)造一個程序求解三角形線性方程組?？杉俣ú恍枰凶儞Q，而且可用第 k 行消去第 k+1 行的 xk。 1 求解線性方程組 AX=B，其中 A=1 3 5 72 1 3 50 0 2 52 6 3 1???????????? B=1234???????????? 使用三角分解法求解 X。 2 求解線性方程組 AX=B，其中 A=[aij]NN， ,aij=ij1；而且 B=[bij]N1， b11=N，當(dāng) i≥時， bij=(iN1)/(i1)。 對 N=3， 7， 11 的 情況分別求解。精確解為 X=[1 1 … 1 1]’。對得到的結(jié)果與精確解的差異進行解釋。 3 《數(shù)值方法》實驗報告 4 通過重復(fù)求解 N 各線性方程組 ACJ=EJ，其中 J=1， 2， … ， N 來得到 A1, 則 A[C1 C2 … CN]=[E1 E2 … EN] 而且 A1=[C1 C2 … CN] 保證對 LU 分解只計算一次 ! 3 設(shè)有如下三角線性方程組，而且系數(shù)矩陣具 有嚴(yán)格對角優(yōu)勢： d1x1+c1x2 =b1 a1x1+d2x2+c2x3 =b2 a2x2+d3x3+c3x4 =b3 aN2xN2+dN1xN1+cN1xN =bN1 aN1xN1+dNxN =bN （ i） 根據(jù)方程組（ 1），式（ 2）和式（ 3），設(shè)計一個算法來求解上述方程組。算法必須有效地利用系數(shù)矩陣的稀疏性。 a11x1+a12x2+ a1jxj+ +a1NxN=b1 a21x1+a22x2+ a2jxj+ +a2NxN=b2 方程組（ 1） aj1x1+aj2x2+ ajjxj+ +ajNxN=bj aN1x1+aN2x2+