炎龍牙

高斯消去法的基本原理
AX=B
其中，A為係數矩陣，X為變數列矩陣，B為常數列矩陣。
假設方程組有equnum方程式個數、有varnum未知個數
我們可以將係數矩陣A和常數列矩陣B，組合成一個廣域矩陣A'，在對矩陣中的每一個元素進行消去去操作。
請參閱：演算法筆記- Linear Equation
求解：

    class Program
    {
        static readonly int MaxNum = 10;
        static int[,] ary = {{1,2,-5,5},
                          {2,4,6,1},
                          {3,1,7,4}};

        static int[] un_result = new int[MaxNum];

        static void Main(string[] args)
        {
            //高斯消去法
            //線性方程式

            int i, type;
            int equnum, varnum;
            int[] result = new int[MaxNum]; //儲存方程式的解
            equnum = 3; //方程式個數
            varnum = 3; //未知數個數

            type = GaussFun(equnum, varnum, result);
            if (type == -1)  //無解
            {
                Console.WriteLine("該方程式無解!\n");
            }
            else if (type == -2) //只有浮點數解
            {
                Console.WriteLine("該方程式只有浮點數解，無整數解!\n");
            }
            else if (type > 0) //無窮多解
            {
                Console.WriteLine(string.Format("該方程式有無窮多解!自由變數量為{0}\n", type));
                for (i = 0; i < varnum; i++)
                {
                    if (un_result[i] != 0) //判斷不確定變數
                    {
                        Console.WriteLine(string.Format("x{0}是不確定的\n", i + 1));
                    }
                    else //輸出一組解
                    {
                        Console.WriteLine(string.Format("x{0}：{1}\n", i + 1, result[i]));
                    }
                }
            }
            else //唯一解
            {
                Console.WriteLine("該方程式的解為：\n");
                for (i = 0; i < varnum; i++)
                {
                    Console.WriteLine(string.Format("x{0}：{1}\n", i + 1, result[i]));
                }
            }
            Console.ReadLine();
        }

        #region 高斯消去演算法
        static int GaussFun(int equ, int var, int[] result)
        {
            int i, j, k;
            int col = 0;
            int max;
            int temp, un_x_num, un_index = 0;
            int nu1, nu2;
            int gcdtmp, lcmtmp; //利用遞迴求GCD(最大公因數)與LCM(最小公倍數)
            int ta, tb;

            for (k = 0; k < equ && col < var; k++, col++)  //迴圈處理每一行 
            {
                max = k;        //儲存絕對值最大的行號
                for (i = k + 1; i < equ; i++)
                {
                    if (Math.Abs(ary[i, col]) > Math.Abs(ary[max, col]))
                    {
                        //儲存絕對值最大的行號
                        max = i;
                    }
                }
                if (max != k)
                {
                    for (j = k; j < var + 1; j++)  //當前列左側為0，交換當前右側資料
                    {
                        temp = ary[k, j];
                        ary[k, j] = ary[max, j];
                        ary[max, j] = temp;

                    }
                }
                if (ary[k, col] == 0)  //如果col列第k行以下是0，則處理目前行的下一列
                {
                    k--;
                    continue;
                }
                for (i = k + 1; i < equ; i++) //尋找消去的行
                {
                    if (ary[i, col] != 0)
                    {
                        nu1 = Math.Abs(ary[i, col]);
                        nu2 = Math.Abs(ary[k, col]);
                        while (nu2 != 0)   //輾轉相除求最大公因數 
                        {
                            temp = nu2;
                            nu2 = nu1 % nu2;
                            nu1 = temp;
                        }
                        gcdtmp = nu1;
                        lcmtmp = (Math.Abs(ary[i, col]) * Math.Abs(ary[k, col])) / gcdtmp;

                        ta = lcmtmp / Math.Abs(ary[i, col]);
                        tb = lcmtmp / Math.Abs(ary[k, col]);
                        if (ary[i, col] * ary[k, col] < 0) //如果符號不相符
                        {
                            tb = -tb; // 異號兩邊相加
                        }
                        for (j = col; j < var + 1; j++) //迴圈消去
                        {
                            ary[i, j] = ary[i, j] * ta - ary[k, j] * tb;
                        }
                    }
                }
            }
            for (i = k; i < equ; i++) //判斷最後一行，最後一列
            {
                if (ary[i, col] != 0) //若不等於0 表示無解
                {
                    return -1;
                }
            }
            if (k < var) //不確定的變數至少有 VAR-K 個
            {
                for (i = k - 1; i >= 0; i--) //權圈處理非零行
                {
                    un_x_num = 0; //判斷該行不確定變數的數量
                    for (j = 0; j < var; j++)
                    {
                        if (ary[i, j] != 0 && un_result[j] != 0) //不確定變數判斷
                        {
                            un_x_num++; //不確定變數+1
                            un_index = j;
                        }
                    }
                    if (un_x_num > 1)
                    {
                        continue; //若超過一個無法求解
                    }
                    temp = ary[i, var];
                    for (j = 0; j < var; j++)
                    {
                        if (ary[i, j] != 0 && j != un_index)
                        {
                            temp -= ary[i, j] * result[j];//每次剪去前一係數及解的積
                        }
                    }
                    result[un_index] = temp / ary[i, un_index]; //求出變數
                    un_result[un_index] = 0;  //該變數是確定的
                }
                return var - k;  //自由變數有Var -K
            }
            for (i = var - 1; i >= 0; i--) //求解  
            {
                temp = ary[i, var];
                for (j = i + 1; j < var; j++)
                {
                    if (ary[i, j] != 0)
                    {
                        temp -= ary[i, j] * result[j]; //每次減去前一項係數及解的積
                    }
                }

                if (temp % ary[i, j] != 0) //如不能整除
                {
                    return -2; //傳回有浮點數解、但無整數解
                }
                result[i] = temp / ary[i, i];
            }
            return 0; //唯一解
        }
        #endregion

    }

水滴可成涓流，涓流可成湖泊大海。
汲取累積知識，將知識堆積成常識；將常識探究成學識；將學識簡化為知識；授人自省。