Tauruser

3.2 Gauss消去法

3.2.1　順序消去法

　　Gauss消去法就是將方程組(3.1.1)通過(n-1)步消元，將(3.1.1)轉(zhuǎn)化為上三角方程組
　　　　　　　(3.2.1)
再回代求此方程組的解.
　　下面記增廣矩陣，即
　　　
　　第1步　設(shè)，計(jì)算l，記為，若用乘第一行加到第i行，可消去,用Gauss變換矩陣表示
　　　　
令　　　
其中
　　一般地，假定已完成了(k-1)步消元，即已將轉(zhuǎn)化為以下形式：
　　　
　　第k步，假定，計(jì)算
　　　　　　　(3.2.2)
記，，則
　　　
其中
　　　　　(3.2.3).
當(dāng)k=1,2，…,n-1則可得到，即方程組(3.2.1).

　　直接回代解(3.2.1)得，
　　　　　(3.2.4)
并且有，由以上順序消去過程可得如下定理.
　　定理2.1　設(shè)非奇異，則通過兩行互換總可使，k=1,2，…,n-1.可將方程組(3.1.1)轉(zhuǎn)化為(3.2.1)并求得方程組(3.1.1)的解為(3.2.4)，且有.
　　如果不做行交換，則使的條件如下.

　　定理2.2　非奇異，且各階順序主子式， 則，k=1,2，…,n-1.
　　證明　用歸納法，當(dāng)，故.現(xiàn)假設(shè)(k-1)成立，即，對(duì)i=1，2，…,k-1已推出，故Gauss消去法能進(jìn)行(k-1)步消元，A已約化為，即
　　　

　　　　　

故對(duì)k=1,2,…,n均成立，證畢.
　　在整個(gè)消去法消元過程中，k從1到(n-1)共需乘除法運(yùn)算次數(shù)為
　　　　　
加減法次數(shù)為
　　　　　
回代過程中由公式(3.2.4)可知乘除法次數(shù)為，加減法次數(shù)為，于是Gauss消去法的乘除法總次數(shù)為，加減法次數(shù)為
　　例3.4　用Gauss消去法解方程組
　　　　　　
并求detA.
　　解　消元得
　　　
再由(3.2.4)回代，得解

講解：

　　Gauss 消去法是將方程組AX＝b,通過消元轉(zhuǎn)化為上三角方程組（3，2，1）求解，消元第一步做完后有
　　　　　　　　　
　　用矩陣表示
　　第K－1步完成后得到
　　當(dāng)，可做K步，得到
　　得到，對(duì)應(yīng)的方程組就是（3.2.1），利用公式（3.2.4）就可求得解。
　　定理2.2給出了進(jìn)行順序消去法的條件，即A的所有順序生子式，而方程（3.1.1）解存在唯一的條件是

好了，原理講完了，貼我的例程。

#include? < iostream >
#include? < vector >
#include? < cmath >
using ? namespace ?std;
class ?CGAUSSSOLVEEQU
{
private :
????vector < vector < double >> ?m_equset;
????vector < double > ?m_answer;
????unsigned? int ?m_n;
public :
???? void ?inputEquSet();
???? void ?solveEquSet();
???? void ?outputAnswer();
} ;
void ?CGAUSSSOLVEEQU::inputEquSet()
{
???? double ?dtemp;
????vector < double > ?vtemp;
????cout << " 請輸入你的方程個(gè)數(shù)： " ;
????cin >> m_n;
????cout << " 請按照向量的形式輸入各變量的系數(shù)。最后一位為b。每個(gè)方程一行: " << endl;
???? for (unsigned? int ?i( 0 );i < m_n; ++ i)
???? {
????????m_equset.push_back(vtemp);
???????? for (unsigned? int ?j( 0 );j <= m_n; ++ j)
???????? {????
????????????cin >> dtemp;
????????????m_equset[i].push_back(dtemp);
????????}
???????? if (m_equset[i].size() != m_n + 1 )
???????? {
????????????cout << " 輸入有誤，請重新輸入上一個(gè)方程。 " << endl;
???????????? -- i;
????????}
????}
????
}

void ?CGAUSSSOLVEEQU::solveEquSet()
{
????vector < vector < double >> ::iterator?iter;
????iter = m_equset.begin();
???? for (unsigned? int ?m( 0 );m < m_n - 1 ; ++ m)
???? {
???????? // 將絕對(duì)值最大的主元素移上去。此舉是為了減少誤差
???????? for (vector < vector < double >> ::iterator?iter2 = iter + 1 ;iter2 != m_equset.end(); ++ iter2)
???????? {
???????????? if (fabsl(iter -> front()) < fabsl(iter2 -> front()))
???????????? {
????????????????swap( * iter, * iter2);
????????????}
????????}
???????? // 進(jìn)行消元
???????? for (unsigned? int ?i = m + 1 ;i < m_n; ++ i)
???????? {
???????????? double ?dm;
????????????dm = m_equset[i][m] / m_equset[m][m];
???????????? for (unsigned? int ?j = m;j < m_n + 1 ; ++ j)
???????????? {
????????????????m_equset[i][j] -= dm * m_equset[m][j];
????????????}
????????}
???????? ++ iter;
????}
???? // 初始化m_answer向量
???? for (unsigned? int ?i( 0 );i < m_n; ++ i)?m_answer.push_back( 0 );
???? // 求解答案
????m_answer[m_n - 1 ] = m_equset[m_n - 1 ][m_n] / m_equset[m_n - 1 ][m_n - 1 ];

???? for ( int ?i = m_n - 2 ;i >= 0 ; -- i)
???? {
????????m_answer[i] = m_equset[i][m_n];
???????? for ( int ?j = m_n - 1 ;j > i; -- j)
????????????m_answer[i] -= m_answer[j] * m_equset[i][j];
????????m_answer[i] /= m_equset[i][i];
????}

????
}

void ?CGAUSSSOLVEEQU::outputAnswer()
{
???? for (unsigned? int ?i( 1 );i <= m_n; ++ i)
???? {
????????cout << " x( " << i << " )= " << m_answer[i - 1 ] << endl;
????}
}

int ?main()
{
????CGAUSSSOLVEEQU?myEqu;
????myEqu.inputEquSet();
????myEqu.solveEquSet();
????myEqu.outputAnswer();
???? return ? 0 ;
}

// Power?By?Tauruser?2006.6.4