程序猿成长之路之番外篇——矩阵算法

今天在复习线性代数知识的过程中，用java语言简单实现了一下矩阵算法。

数学知识回顾

1.什么是矩阵
在数学领域，矩阵就像一个表格，将数据排放进去，形成一个矩形。我们习惯用一个大括号把矩阵内的数据包括进来。

1.矩阵
在数学领域，矩阵就像一个表格，将数据排放进去，形成一个矩形。我们习惯用一个大括号把矩阵内的数据包括进来。

2. 矩阵的运算
矩阵可以进行加法、乘法运算，如果是个方形矩阵也可以转置或者求逆。此外，加法和乘法都有结合律、分配律等定律。

矩阵加法运算：

矩阵乘法运算：
运算规则相对较为繁琐：

1. A(m,n) * B(n,k) = C(m,k) // 具有m行n列的矩阵A 乘以具有n行k列的矩阵B结果为m行k列的矩阵c
2. 运算过程如下图：就拿C(1,1) – 结果矩阵的第一行第一列的元素来说，它等于A(1,1) * B(1,1) + A(1,2) * B(2,1) = 1 * 2 + 2 * 6 = 14
   
3. 矩阵的转置
   
4. 矩阵求逆
   我们知道伴随矩阵 = Det(矩阵A) * 矩阵的逆
   我们又知道 伴随矩阵 = Σ(Aij 的代数余子式), i,j∈（0,size))
   因此可以求出矩阵的逆 = |伴随矩阵| / Det(矩阵A)
   求逆的难点在于获取代数余子式。

算法实现

1. 编写matrix类

package matrixUtils;

import java.util.Arrays;

class Matrix {
	@Override
	public String toString() {
		String str = "";
		for (int i = 0; i < arr.length;i++) {
			str += Arrays.toString(arr[i]);
			str +="\n";
		}
		return str;
	}
	//宽度
	private final int width;
	//高度
	private final int height;
	//数组
	private final double[][] arr;
	
	Matrix(int width, int height) {
		this.width = width;
		this.height = height;
		arr = new double[height][width];
	}
	
	Matrix(int width, int height, double[][] arr) {
		this.width = width;
		this.height = height;
		this.arr = arr;
	}
	
	public int getWidth() {
		return width;
	}
	public int getHeight() {
		return height;
	}
	public double[][] getArr() {
		return arr;
	}
	public void setArrVal(int x, int y, double val) {
		arr[x][y] = val;
	}
	public boolean compareTo(Matrix matrix) {
		//比较
		return this.width == matrix.width 
				& this.height == matrix.height;
	}
	public void setArrVals(int startIndex, int[][] val) {
		int size = val[0].length;
		size *= val.length;
		if (startIndex < 0 || size <= 0){
			return;
		}
		//count计数器
		for (int i = 0; i < size;i++) {
			arr[i / val[0].length][i % val[0].length] = val[i/val[0].length][i % val[0].length];
		}
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

2. 编写工厂类

public class MatrixFactory {
	private static final int MAX_SIZE = 1 << 30;
	/**
	 * 获取实例
	 */
	public static Matrix getInstance(int width, int height) {
		if (width < 0 || width > MAX_SIZE) {
			throw new IllegalArgumentException("宽度有误");
		}
		if (height < 0 || height > MAX_SIZE) {
			throw new IllegalArgumentException("高度有误");
		}
		return new Matrix(width, height);
	}
	
	public static Matrix getInstance(int width, int height, double[][] arr) {
		if (width < 0 || width > MAX_SIZE) {
			throw new IllegalArgumentException("宽度有误");
		}
		if (height < 0 || height > MAX_SIZE) {
			throw new IllegalArgumentException("高度有误");
		}
		return new Matrix(width, height, arr);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

3. 矩阵乘法
   设计思路：设置一个计数器m，用于获取结果的列值，当m == matrix2的宽度时，也就是说当前已经完成对i行的处理，结果保存进matrix中，让i（行数）加1并且m重置为0，否则让结果列数自加。

	/**
	 * 矩阵相乘
	 * @param matrix
	 * @return
	 */
	public static Matrix multiply(Matrix matrix1,Matrix matrix2) {
		//生成一个新的矩阵
		if (matrix1 == null || matrix2 == null) {
			throw new IllegalArgumentException("矩阵不匹配，请检查");
		}
		if (matrix1.getWidth() != matrix2.getHeight()) {
			throw new IllegalArgumentException("矩阵不匹配，请检查");
		}
		//新建一个矩阵
		Matrix resMatrix = MatrixFactory.getInstance(
				matrix2.getWidth(),matrix1.getHeight()
		);
		int m = 0; //m - matrix2的列数
		for (int i = 0; i < matrix1.getHeight();) {
			int sum = 0; //sum - 求和
			for(int j = 0; j < matrix1.getWidth(); j++) {
				/**
				 * 按照matrix1 第i行 * matrix2 第m列 得到结果保存
				 */
				sum += matrix1.getArr()[i][j] * matrix2.getArr()[j][m];
			}
			resMatrix.setArrVal(i, m, sum);
			if (m == matrix2.getWidth() - 1) {
				i++;
				m=0;
			} else {
				m++;
			}
		}
		return resMatrix;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

4. 矩阵转置
   设计思路： arr[i][j] == arr[j][i]。(i,j位置上的数据互换）

/**
	 * 矩阵反转
	 * @param matrix
	 * @return
	 */
	public static Matrix reverse(Matrix matrix) {
		//生成一个新的矩阵
		if (matrix == null) {
			throw new IllegalArgumentException("矩阵不匹配，请检查");
		}
		//生成一个新的矩阵
		Matrix resMatrix = MatrixFactory.getInstance(
				matrix.getHeight(), matrix.getWidth()
		);
		for(int i =0; i <matrix.getHeight();i++) {
			for (int j = 0; j < matrix.getWidth(); j++) {
				//如果行列值一样就跳过
				if (i == j) {
					resMatrix.setArrVal(i, j, matrix.getArr()[i][j]);
					continue;
				}
				resMatrix.setArrVal(j, i, matrix.getArr()[i][j]);
			}
		}
		return resMatrix;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

5. 矩阵求det
   设计思路：利用递归，每次的余子式size-1，到了size为2时就直接使用余子式公式进行计算。

/**
	 * 获取矩阵det
	 * @param matrix
	 * @return
	 */
	public static double getMatrixDet(Matrix matrix) {
		if (matrix == null) {
			throw new IllegalArgumentException("矩阵不匹配，请检查");	
		}
		int height = matrix.getHeight();
		int width = matrix.getWidth();
		if (height != width) {
			throw new IllegalArgumentException("矩阵不匹配，请检查");	
		}
		return getMatrixDet(matrix,width);
	}
	
	/**
	 * 获取矩阵det
	 * @param matrix
	 * @param width
	 * @return
	 */
	private static double getMatrixDet(Matrix matrix, int size) {
		if (size <= 1) {
			return matrix.getArr()[0][0];
		} else if (size == 2) {
			return matrix.getArr()[0][0] * matrix.getArr()[1][1] - 
					matrix.getArr()[0][1] * matrix.getArr()[1][0];
 		}
		// 计算det,每次分解成大小为size-1的数组
		int det = 0;
		
		double[][] arr = matrix.getArr();
		for(int i = 0; i < arr[0].length; i++) {
			//获取余子式
			Matrix temp = getSubMatrix(0,i,size-1,arr);
			//统计det的值
			det += (Math.pow(-1, i)) * arr[0][i] * getMatrixDet(temp,size-1);
		}
		return det;
	}
	/**
	 * 获取余子式
	 * @param x - 要去除的第几行
	 * @param y - 要去除的第几列
	 * @param size 余子式size
	 * @param arr 原数组
	 * @return
	 */
	private static Matrix getSubMatrix(int x, int y,int size,double[][] arr) {
		//每次进行temp数组的填充
		Matrix temp = new Matrix(size,size);
		int addRow = 0; //填充计数
		for (int j = 0; j <= size; j++) {
			int addColumn = 0; //填充计数
			//跳过当前一行
			if (j == x) {
				addRow++;
				continue;
			}
			for (int m = 0; m < size + addColumn; m++) {
				//i列删除
				if (m == y) {
					addColumn++;
					continue;
				}
				//从第一行开始算，自动跳过第y列的数据
				temp.setArrVal(j-addRow,m - addColumn,arr[j][m]);
			}
		}
		return temp;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

6. 矩阵求逆
   设计思路：利用公式 伴随矩阵 = det(矩阵) * 矩阵进行求解

	/**
	 * 求逆矩阵
	 * @param matrix
	 * @return
	 */
	public static Matrix inverse(Matrix matrix) {
		if (matrix.getWidth() != matrix.getHeight()) {
			throw new IllegalArgumentException("矩阵不匹配，请检查");
		}
		/**
		 * AX = B
		 * A-1AX=A-1A
		 * X=A-1B
		 */
		int size = matrix.getHeight(); //size
		double[][] arr = matrix.getArr(); //arr
		//结果矩阵
		Matrix resMatrix = MatrixFactory.getInstance(size,size);
		double det = getMatrixDet(matrix); //计算det
		for (int i = 0; i < Math.pow(size,2); i++) { //size * size = length
			//获取每一项的余子式
			Matrix temp = getSubMatrix(i/size, i%size, size-1, arr);
			resMatrix.setArrVal(i/size, i%size, Math.pow(-1, i) 
					* getMatrixDet(temp) / (det * 1.0)); //计算余子式的det / 总det
		}
		return reverse(resMatrix); //转置
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28