高斯列主元消去法

1、數(shù)值分析大作業(yè)（高斯列主元消去法求解線性方程組）課程名稱：數(shù)值分析授課老師：宋國鄉(xiāng)指導導師：丁振國學 生：王偉偉學 號：日 期：2004/11/20高斯列主元消去法解線性方程組一：問題的提出 我們都知道，高斯列主元素消去法是計算機上常用來求解線性方程組的一種直接的方法。就是在不考慮舍入誤差的情況下，經(jīng)過有限步的四則運算可以得到線性方程組的準確解的一類方法。實際運算的時候因為只能有限小數(shù)去計算，因此只能得到近似值。在實際運算的時候，我們很多時候也常用高斯消去法。但是高斯消去法在計算機中運算的時候常會碰到兩個問題。1 一旦遇到某個主元等于0，消元過程便無法進行下去。2在長期使用中還發(fā)現(xiàn)，即使消元過

2、程能進行下去，但是當某個主元的絕對值很小時，求解出的結果與真實結果相差甚遠。為了避免高斯消去法消元過程中出現(xiàn)的上述兩個問題，一般采用所謂的選擇主元法。其中又可以分為列選主元和全面選主元兩種方法。目前計算機上常用的按列選主元的方法。因此我在這里做的也是列選主元高斯消去法。二、算法的基本思想大家知道，如果一個線性方程組的系數(shù)矩陣是上三角矩陣時，即這種方程組我們稱之為上三角方程組，它是很容易求解的。我們只要把方程組的最下面的一個方程求解出來，在把求得的解帶入倒數(shù)第二個方程，求出第二個解，依次往上回代求解。然而，現(xiàn)實中大多數(shù)線性方程組都不是上面所說的上三角方程組，所以我們有可以把不是上三角的方程通過一

3、定的算法化成上三角方程組，由此我們可以很方便地求出方程組的解。高斯消元法的目的就是把一般線性方程組簡化成上三角方程組。于是高斯消元法的基本思想是：通過逐次消元將所給的線性方程組化為上三角形方程組，繼而通過回代過程求解線性方程組。三、算法的描述1、設有n元線性方程組如下：2、第一步：如果a11!=0, 令li1= ai1/a11, I= 2,3,n用（-li1）乘第一個方程加到第i個方程上,得同解方程組：a(1)11 a(1)12 . . . a(1)1n x1 b(1)1a(1)21 a(1)22 . . . a(1)2n x2 b(1)2 . . . . . . . = .a(1)n-11

4、a(1)n-12 . . a(1)n-1n xn-1 b(1)n-1a(1)n1 a(1)n2 . . . a(1)nn xn b(1)n簡記為： A(2) x = b(2)其中 a(2)ij = a(1)ij li1 * a(1)1j , I ,j = 2,3,.,n b(2)I = b(1)I li1 * b(1)1 , I = 2,3,.,n第二步：如果a(2)22 != 0,令li2= a（2）i2/a（2）22, I= 3,n依據(jù)同樣的原理，對矩陣進行化間（省略），依次下去，直到完成！最后，得到上三角方程組： a(1)11 a(1)12 . . . a(1)1n x1 b(1)10

5、a(1)22 . . . a(1)2n x2 b(1)2 . . . . . . . = .0 0 . . a(n-1)n-1n xn-1 b(n-1)n-10 0 . . . a(n)nn xn b(n)n簡記為： A(n) x = b(n)最后從方程組的最后一個方程進行回代求解為： Xn = b(n) / a(n)nn Xi = ( b(k)k - a(k)kjxj ) / a(k)kk以上為高斯消去法的基本過程。但是如前面我們所提到的，存在的問題。1.一旦遇到某個主元等于0，消元過程便無法進行下去。2在長期使用中還發(fā)現(xiàn)，即使消元過程能進行下去，但是當某個主元的絕對值很小時，求解出的結果與

6、真實結果相差甚遠。為了避免高斯消去法消元過程中出現(xiàn)的上述兩個問題，一般采用所謂的選擇主元法。其中又可以分為列選主元和全面選主元兩種方法。目前計算機上常用的按列選主元的方法。因此我在這里做的也是列選主元高斯消去法。他的特點是：每次在系數(shù)矩陣中依次按列在主對角線及以下的元素中，選取絕對值最大的元素作為主元，將她調到主對角線上，然后用它消去主對角線以下的元素，最后化為同解的上三角形方程組去求解。由于列主元法相對高斯消元法來說就增加了選主元操作，其他的求解步驟是一樣的。四、程序流程圖 五、程序描述程序的名稱為：zealous.cpp1. 程序的結構如下：程序只能最大輸入60行60列的系數(shù)矩陣。2.程序

7、要用到的函數(shù)（1、）matrix_getElement(array,n,m);此函數(shù)的作用是獲得用戶輸入的線性方程組的系數(shù)矩陣。（2、）matrix_outputElement(array,n,m);此函數(shù)的作用是顯示用戶輸入的矩陣。（3、）selectMaxElement(array,n,m,row );此函數(shù)的作用是選擇主元素，并把此時對角線上的那列元素與主元素行交換。（4、）GAUSSProcess(array, n, m, row);此函數(shù)的作用是用主元素列進行高斯消元，把此行以后所有的行的，此列的元素變?yōu)?。（5、）GAUSSProcess_result(array, n,m)；此函

8、數(shù)的作用是顯示經(jīng)過高斯消元后的矩陣，此時的系數(shù)矩陣為一個上下三角矩陣。（6、）GAUSSCalculate_result(array, n, m);此函數(shù)的作用是對已經(jīng)消元好的矩陣，進行回代求解。并將結果輸出。六、程序代碼/-*高斯列消去法*#include#include#include#include const int N=60;/最大const int M=61;/60列，再加上等號右邊的一列值/-輸入要計算方程組的矩陣-void matrix_getElement(double ARRAYNM,int n, int m) for(int i=0;in;i+)cout請您輸入第t(i+

9、1)trow:endl;for(int j=0;jARRAYij;return;/-/-輸出用戶剛才用戶輸入的矩陣，以便用戶檢測是否輸入正確void matrix_outputElement(double ARRAYNM, int n, int m)coutyour have input the matrix as fllows:n;for(int i=0; in;i+)for(int j=0;jm;j+)coutARRAYij t t;coutendlendl;/-/-選擇主元素，并把主元行與對角線上的那一行交換void selectMaxElement(double ARRAYNM,int

10、 n, int m, int line )double max=0;double t=0;int j=0;int i=line;max=ARRAYlineline;for(i=line+1;i fabs(max) )max=ARRAYiline;j=i;if(jline)for(i=0;im;i+)t=ARRAYji;ARRAYji=ARRAYlinei;ARRAYlinei=t;/-/-用對角線上的元素消去后續(xù)行中此列的元素void GAUSSProcess(double ARRAYNM, int n, int m, int row) double ROW1M; for(int t=0;t(

11、m-row);t+) ROW1t=ARRAYrowrow+t; for(int j=(row+1); j n; j+) double ROW_CHANGEM; for(int r=0;r(m-row);r+) double mainElement=ROW10; if( fabs(mainElement) 1e-7) cout Single! press any key return.n; getchar(); return; ROW_CHANGEr=ROW1r*ARRAYjrow/ROW10; for(int h=0; h=0; p-)for(int q=n-1; qp; q-)ARRAYpm

12、-1=ARRAYpm-1 - ARRAYpq*aq;ap = ARRAYqm-1/ARRAYpp;cout-the final result as follows-:n;for(int e=0; en; e+)cout x e+1 = ae endl;/-輸出經(jīng)過高斯消去法處理后得到的矩陣-void GAUSSProcess_result(double ARRAYNM, int n, int m)cout您輸入的矩陣經(jīng)過高斯消去法處理后得到如下形式:n;for(int i=0; in;i+)for(int j=0;jm;j+)coutARRAYijtt;coutendlendl;/-/-mai

13、n函數(shù)-void main() double arrayNM; cout請輸入您要運算的矩陣的大??！n; int n=0, m=0; coutn; coutm; cout您所輸入的行為：n 您所輸入的列為：mendl; matrix_getElement(array,n,m); /獲得矩陣的元素 matrix_outputElement(array,n,m); /顯示輸入的矩陣 for(int row=0; rown; row+) /高斯消元法的主體 selectMaxElement(array,n,m,row ); GAUSSProcess(array, n, m, row); GAUSSProcess_result(array, n,m); /顯示消元后的矩陣 GAUSSCalculate_result(array,n,m); /回代求解并顯示解結果 cout This is the end!;/-七、實例本程序可以自己選擇在60個未知數(shù)的方程組，可以自己選擇線性方程組的行數(shù)和列數(shù)。例子如下：2x1x2 5x3x48；x1 3x2 6x49；2x2x3 2x45；x1 4x27x36x40；輸入您要運算的矩陣的大小!請輸入您要運算的矩陣的行數(shù)：4請輸入您要運算的