高斯消元法解线性方程(java实现)

LinearEquation.java

package cn.huge.math;

public class LinearEquation {

    public static float[] gauss(Matrix matrix) throws Exception {
        //1.获得增广矩阵的参数，判断增广矩阵是否满足唯一解的形式
        // 比如 3行4列，  5行6列，这种格式才能解
        if(!(matrix.getRows()>1 && matrix.getRows()+1==matrix.getCols()))
        {
            throw new Exception("增广矩阵不合法");
        }

        //2. 判断每一行是否有主元，如果没有则交换
        //三次后，看是否还有没有主元的
        int times = 3;
        boolean hasNoMain =  false;
        while(times>=0) {
            hasNoMain = false;
            for (int i = 0; i < matrix.getRows(); i++) {
                float value = matrix.getValue(i, i);
                if (value == 0.0) { //没有主元，和下一行交换下
                    hasNoMain = true;
                    int changeRow = -1;
                    for (int x = i + 1; x < matrix.getRows() - 1; ++x) {
                        if (matrix.getValue(x % matrix.getRows(), x % matrix.getRows()) != 0.0) {
                            changeRow = x;
                        }
                    }

                    if (changeRow < 0) {
                        throw new Exception("找不到合法的主元行");
                    }

                    matrix.swapRow(changeRow, i);
                }
            }
            times --;
            if (!hasNoMain) break;
        }

        if (hasNoMain)throw new Exception("找不到合法的主元行");

        //3. 除主元外，利用上下行消掉其他元
        //下矩阵处理
        for (int i = 0; i < matrix.getRows(); i++) {

            for(int j =0; j < i; ++j){
                dissElement(matrix, i, j);
            }
        }

        //上矩阵处理
        //刚好相反，从后往前算
        for (int i = matrix.getRows()-1; i >=0; i--) {

            for(int j =matrix.getCols()-2; j > i; --j){
                dissElement(matrix, i, j);
            }
        }



        //4. 将主元变为1
        //将主元除增广最后一列值为结果
        float r[] = new float[matrix.getRows()];
        for (int i = 0; i < matrix.getRows(); i++) {
            float f = matrix.getValue(i,matrix.getCols()-1)/matrix.getValue(i,i);
            r[i] = f;
        }
        return r;
    }

    /**
     * 消元
     * @param matrix
     * @param i
     * @param j
     */
    private static void dissElement(Matrix matrix, int i, int j) {
        if (matrix.getValue(i, j) != 0.0) { //需要消元
            //利用主元行消除当前行对应的列，比如现在是第三行
            //则用第1行消除第1列，用第2行消除第2列
            float z = matrix.getValue(i, j) / matrix.getValue(j, j);

            for (int k = 0; k < matrix.getCols(); k++) {
                float f = matrix.getValue(i, k) - matrix.getValue(j, k) * z;
                matrix.setValue(i, k, f);
            }
        }
    }
}

Matrix.java

package cn.huge.math;

import java.util.ArrayList;
import java.util.List;

public class Matrix {

    private List<List<Float>> data;

    public Matrix(float data[][]) {
        this.data = new ArrayList<>();
        for (float[] datum : data) {
            List<Float> objects = new ArrayList<>();
            for (float v : datum) {
                objects.add(v);
            }
            this.data.add(objects);
        }
    }

    public int getRows() {
        return data.size();
    }

    public int getCols() {
        return data.get(0).size();
    }

    /**
     * 交换行
     * @param i1 哪一行
     * @param i2 到哪一行
     */
    public void swapRow(int i1, int i2){
        if (i1==i2)return;
        if (i1>i2){
            int temp = i2;
            i2 = i1;
            i1 = temp;
        }

        List<Float> row2 = data.remove(i2);
        List<Float> row1 = data.remove(i1);

        data.add(i1, row2);
        data.add(i2, row1);

    }

    public float getValue(int row, int col){
        return data.get(row).get(col);
    }


    public void setValue(int row, int col, float value) {
        data.get(row).set(col, value);
    }

    @Override
    public String toString() {
        String s = "";

        for (int i = 0; i < getRows(); i++) {
            for (int j = 0; j < getCols(); j++) {
                s += " "+ getValue(i,j) ;
            }
            s+="\n";
        }

        return s;
    }
}

matrix.py

#coding=utf-8

class Matrix:
    
    '''
    data的格式为增广矩阵
    [[1,2,3],
     [1,2,3]]
    '''
    def __init__(self, data):
        self.data = data

    def getRows(self):
        return len(self.data)

    def getCols(self):
        return len(self.data[0])

    def swapRow(self, i1, i2):
        self.data[i1],self.data[i2] = self.data[i2],self.data[i1]

    def getValue(self, row, col):
        return self.data[row][col]

    def setValue(self, row, col, value):
        self.data[row][col] = value
    
    def __str__(self):
        return str(self.data)
        
def gauss(matrix):
    # 1.获得增广矩阵的参数，判断增广矩阵是否满足唯一解的形式
    # 比如 3行4列，  5行6列，这种格式才能解
    if (not (matrix.getRows()>1 and matrix.getRows()+1==matrix.getCols())):
        raise Exception,"增广矩阵不合法"

    # 2. 判断每一行是否有主元，如果没有则交换
    # 三次后，看是否还有没有主元的
    times = 3
    hasNoMain =  False
    while(times>=0):
        hasNoMain = False
        for i in range(0,matrix.getRows()):
            value = matrix.getValue(i, i)
            if (value == 0.0): #没有主元，和下一行交换下
                hasNoMain = True
                changeRow = -1
                for x in range(i + 1, x < matrix.getRows() - 1):
                    if (matrix.getValue(x % matrix.getRows(), x % matrix.getRows()) != 0.0):
                        changeRow = x
                    
                if (changeRow < 0):
                    raise Exception,"找不到合法的主元行"

                matrix.swapRow(changeRow, i)
            
        times -=1
        if not hasNoMain:
            break

    if (hasNoMain):
        raise Exception,"找不到合法的主元行"

    #3. 除主元外，利用上下行消掉其他元
    #下矩阵处理
    for i in range(0,matrix.getRows()):
        for j in range(0,i):
            dissElement(matrix, i, j)
        
    #上矩阵处理
    #刚好相反，从后往前算
    i = matrix.getRows()-1
    while i >=0:
        j = matrix.getCols()-2
        while j > i:
            dissElement(matrix, i, j)
            j -= 1
        i -= 1


    #4. 将主元变为1
    #将主元除增广最后一列值为结果
    r = []
    for i in range(0,matrix.getRows()):
        f = matrix.getValue(i,matrix.getCols()-1)/matrix.getValue(i,i)
        r.append(f)

    return r


'''
    * 消元
    * @param matrix
    * @param i
    * @param j
'''
def dissElement(matrix, i, j):
    #需要消元
    #利用主元行消除当前行对应的列，比如现在是第三行
    #则用第1行消除第1列，用第2行消除第2列
    if (matrix.getValue(i, j) != 0.0): 
        z = matrix.getValue(i, j) / matrix.getValue(j, j) * 1.0

        for k in range(0,matrix.getCols()):
            f = matrix.getValue(i, k) - matrix.getValue(j, k) * z
            matrix.setValue(i, k, f)
           

def main():
    matrix = Matrix([ [1,0,-3,8],[2,2,9,7],[0,1,5,-2] ])
    print gauss(matrix)


if __name__ == '__main__':
    main()