23高斯列主元消去法

1、2.3 高斯列主元消去法解線性方程組一：?jiǎn)栴}的提出我們都知道，高斯列主元素消去法是計(jì)算機(jī)上常用來(lái)求解線性方程組的一種直接的方法。 就是在不考慮舍入誤差的情況下， 經(jīng)過(guò)有限步的四則運(yùn)算可以得到 線性方程組的準(zhǔn)確解的一類方法。 實(shí)際運(yùn)算的時(shí)候因?yàn)橹荒苡邢扌?shù)去計(jì)算， 因 此只能得到近似值。 在實(shí)際運(yùn)算的時(shí)候， 我們很多時(shí)候也常用高斯消去法。 但是 高斯消去法在計(jì)算機(jī)中運(yùn)算的時(shí)候常會(huì)碰到兩個(gè)問(wèn)題。1 一旦遇到某個(gè)主元等于 0 ，消元過(guò)程便無(wú)法進(jìn)行下去。 2在長(zhǎng)期使用中還發(fā)現(xiàn)， 即使消元過(guò)程能進(jìn)行下去， 但是當(dāng)某個(gè)主元的絕對(duì)值 很小時(shí)，求解出的結(jié)果與真實(shí)結(jié)果相差甚遠(yuǎn)。為了避免高斯消去法消元過(guò)程中出現(xiàn)的

2、上述兩個(gè)問(wèn)題， 一般采用所謂的選擇主元 法。其中又可以分為列選主元和全面選主元兩種方法。 目前計(jì)算機(jī)上常用的按列 選主元的方法。因此我在這里做的也是列選主元高斯消去法。二、算法的基本思想 大家知道，如果一個(gè)線性方程組的系數(shù)矩陣是上三角矩陣時(shí)， 即這種方程組 我們稱之為上三角方程組， 它是很容易求解的。 我們只要把方程組的最下面的一 個(gè)方程求解出來(lái)， 在把求得的解帶入倒數(shù)第二個(gè)方程， 求出第二個(gè)解， 依次往上 回代求解。 然而，現(xiàn)實(shí)中大多數(shù)線性方程組都不是上面所說(shuō)的上三角方程組， 所 以我們有可以把不是上三角的方程通過(guò)一定的算法化成上三角方程組， 由此我們 可以很方便地求出方程組的解。 高斯消元

3、法的目的就是把一般線性方程組簡(jiǎn)化成三角方程組。 于是高斯消元法的基本思想是： 通過(guò)逐次消元將所給的線性方程r >a(1)11a(1)12. . . a(1)1nX1a(1)21a(1)22. . . a(1)2nX2L丿l 丿用（-li1 ）乘第一個(gè)方程加到第i個(gè)方程上,得同解方程組:an-11 an-12. .an-1nb（1）ib（1）2Xn-1b(1)n-1an1an2 . a nnXnb(1)n組化為上三角形方程組，繼而通過(guò)回代過(guò)程求解線性方程組。三、算法的描述1、設(shè)有n元線性方程組如下:a11Ka1nXb1MOM M=Man1LannXib2、第一步v:如果an !=0,令li

4、1 = ai1/a11, I=2,3,，n簡(jiǎn)記為:A x = b (2)其中aj = a j i1 * a1j , I ,j = 2,3,.,nb（2）i = b i -lii * b i , I = 2,3,.,n第二步：如果a22 != 0,令li2= a （2）i2/a （2）22, 1= 3, ,n依據(jù)同樣的原理，對(duì)矩陣進(jìn)行化間（省略），依次下去，直到完成！最后，得到上三角方程組：r r 冷a11a12.a(1)1nX1b(1)10a22 .a (1)2nX2b(1)2JL JL J0 0.a(n-1)n-1nXn-1b(n-1)n-10 0 .a (n) nnXnb(n)n簡(jiǎn)記為：A

5、（n）x = b（n）最后從方程組的最后一個(gè)方程進(jìn)行回代求解為：YXn = b （n） / a （n）nnI Xi = （ b（k）k -a（k）kjXj ）/a（k）kk以上為高斯消去法的基本過(guò)程。但是如前面我們所提到的，存在的問(wèn)題1.一旦遇到某個(gè)主元等于0，消元過(guò)程便無(wú)法進(jìn)行下去。2在長(zhǎng)期使用中還發(fā)現(xiàn)， 即使消元過(guò)程能進(jìn)行下去， 但是當(dāng)某個(gè)主元的絕對(duì)值 很小時(shí)，求解出的結(jié)果與真實(shí)結(jié)果相差甚遠(yuǎn)。 為了避免高斯消去法消元過(guò)程中出 現(xiàn)的上述兩個(gè)問(wèn)題， 一般采用所謂的選擇主元法。 其中又可以分為列選主元和全 面選主元兩種方法。 目前計(jì)算機(jī)上常用的按列選主元的方法。 因此我在這里做的 也是列選主元高

6、斯消去法。 他的特點(diǎn)是： 每次在系數(shù)矩陣中依次按列在主對(duì)角線 及以下的元素中， 選取絕對(duì)值最大的元素作為主元， 將她調(diào)到主對(duì)角線上， 然后 用它消去主對(duì)角線以下的元素， 最后化為同解的上三角形方程組去求解。 由于列 主元法相對(duì)高斯消元法來(lái)說(shuō)就增加了選主元操作，其他的求解步驟是一樣的。 四、程序流程圖main()函數(shù)入口五、程序描述程序的名稱為：zealous.cpp1.程序的結(jié)構(gòu)如下:線性方程組系數(shù)矩陣的輸入函數(shù)高 斯 列 主 元 消 去 法用戶查看矩陣系數(shù)的函數(shù)高斯主元素消去法的實(shí)現(xiàn)回代求出結(jié)果的函數(shù)找主元素并換行的函數(shù)主元素消去法后續(xù)個(gè)行中此列的元素使之為0的函數(shù)回代求解，并輸出結(jié)果的函數(shù)

7、回代過(guò)程結(jié)果輸出程序只能最大輸入60行60列的系數(shù)矩陣。2程序要用到的函數(shù)(1、)matrix_getElement(array,n,m);此函數(shù)的作用是獲得用戶輸入的線性方程組的系數(shù)矩陣。(2、)matrix_outputElement(array,n,m);此函數(shù)的作用是顯示用戶輸入的矩陣。(3、)selectMaxElement(array,n,m,row);此函數(shù)的作用是選擇主元素，并把此時(shí)對(duì)角線上的那列元素與主元素行交換。(4、)GAUSSProcess(array, n, m, row);此函數(shù)的作用是用主元素列進(jìn)行高斯 消元，把此行以后所有的行的，此列的元素變?yōu)?。(5、)GAU

8、SSProcess_result(array, n,m);此函數(shù)的作用是顯示經(jīng)過(guò)高斯消元 后的矩陣，此時(shí)的系數(shù)矩陣為一個(gè)上下三角矩陣。(&) GAUSSCalculate_result(array, n, m);此函數(shù)的作用是對(duì)已經(jīng)消元好的矩 陣，進(jìn)行回代求解。并將結(jié)果輸出六、程序代碼/*高斯列消去法 *#include<stdio.h>#include<math.h> #include<iostream.h>#include <iomanip.h>const int N=60;/ 最大const int M=61;/60 列，再加上等號(hào)

9、右邊的一列值/ 輸入要計(jì)算方程組的矩陣 void matrix_getElement(double ARRAYNM,int n, int m)for(int i=0;i<n;i+)cout<<" 請(qǐng)您輸入第 "<<"t"<<(i+1)<<"t"<<"row:"<<endl;for(int j=0;j<m;j+) cin>>ARRAYij;return;/ 輸出用戶剛才用戶輸入的矩陣，以便用戶檢測(cè)是否輸入正確void ma

10、trix_outputElement(double ARRAYNM, int n, int m)cout<<"your have input the matrix as fllows:n"for(int i=0; i<n;i+)for(int j=0;j<m;j+) cout<<ARRAYij<< "t"<< "t"cout<<endl<<endl;/ 選擇主元素，并把主元行與對(duì)角線上的那一行交換void selectMaxElement(double

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

12、, int n, int m, int row)double ROW1M;for(int t=0;t<(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_CH

13、ANGEr=ROW1r*ARRAYjrow/ROW10;for(int h=0; h<(m-row); h+)ARRAYjh+row = ARRAYjh+row-ROW_CHANGEh;/ 用回代的方法求出線性方程組的解 void GAUSSCalculate_result(double ARRAYNM, int n, int m)double aN; an-1=ARRAYn-1m-1/ARRAYn-1n-1;for(int p=n-2; p>=0; p-)for(int q=n-1; q>p; q-)ARRAYpm-1=ARRAYpm-1 - ARRAYpq*aq;ap =

14、 ARRAYqm-1/ARRAYpp;cout<<"the final result asfollows:n"for(int e=0; e<n; e+)cout<< "x"<< e+1 << "=" << ae << endl;/ 輸出經(jīng)過(guò)高斯消去法處理后得到的矩陣 -void GAUSSProcess_result(double ARRAYNM, int n, int m) :n"cout<<" 您輸入的矩陣經(jīng)過(guò)高斯消去法處

15、理后得到如下形式 for(int i=0; i<n;i+)for(int j=0;j<m;j+) cout<<ARRAYij<<"t"<<"t"cout<<endl<<endl;/main 函數(shù) void main()"<<" 您 所 輸 入 的 列 為 ：/ 獲得矩陣的元素/ 顯示輸入的矩陣/ 高斯消元法的主體/ 顯示消元后的矩陣/ 回代求解并顯示解結(jié)果double arrayNM;cout<<" 請(qǐng)輸入您要運(yùn)算的矩陣的大??！

16、n" int n=0, m=0;cout<<" 請(qǐng)輸入您要運(yùn)算的矩陣的行數(shù)： " cin>>n;cout<<" 請(qǐng)輸入您要運(yùn)算的矩陣的列數(shù)： " cin>>m;cout<<" 您 所 輸 入 的 行 為 ： "<<n<<" "<<m<<endl;matrix_getElement(array,n,m); matrix_outputElement(array,n,m);for(int row=0; r

17、ow<n; 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!"/七、實(shí)例本程序可以自己選擇在 60 個(gè)未知數(shù)的方程組，可以自己選擇線性方程組的 行數(shù)和列數(shù)。例子如下：2x1 + x2 5x3 + x4 =8 ;x1 3x2 6x4 = 9;2x2x3 2x4= 5；x1 4x2 7x3 6x4 = 0 ； 輸入您要運(yùn)算的矩陣的大小 !請(qǐng)輸入您要運(yùn)算的矩陣的行數(shù)： 4請(qǐng)輸入您要運(yùn)算的矩陣的列數(shù)： 5您所輸入的行為： 4 您所輸入的列為： 5請(qǐng)您輸入第 1 row:21-518請(qǐng)您輸入第 2 row:1-33 row:4 row:等用戶輸入以上的數(shù)據(jù)后，出現(xiàn)結(jié)果如下圖所示：9請(qǐng)您輸入第02-12-5請(qǐng)您輸入第14-7602haue input the natr ix as1f L ldus :_51ti1-30-fc92-12'5