高斯-约旦消元法的 Kotlin 实现

最让我头疼的几门课已经考完试了，讲讲前几天复习线性代数的时候学到的东西

主要是一开始突发奇想，我能不能写一个 Kotlin 程序，输入矩阵，一键计算矩阵的秩，并输出其行最简形式，然后查阅资料的时候认识到了高斯-约旦消元法

高斯-约旦消元法#

高斯-约旦消元法（Gauss-Jordan Elimination）是线性代数中解线性方程组的重要方法，由德国数学家卡尔・弗里德里希・高斯（Carl Friedrich Gauss）提出，后经威廉・约旦（Wilhelm Jordan）改进完善。

高斯-约旦消元法的目标是将矩阵转换为最简行阶梯形矩阵（Reduced Row Echelon Form，简称 RREF），使得每个主元为 1，且主元所在列的其他元素全为 0。矩阵的行最简形式在求解线性方程组、求逆矩阵等问题中具有关键作用。

以下是高斯-约旦消元法的 Kotlin 实现：

1
/**
2
* 计算矩阵的行最简形式
3
* @return 矩阵的秩
4
*/
5
fun computeRREF(matrix: Array<DoubleArray>): Int {
6
    val rows = matrix.size
7
    val cols = if (rows > 0) matrix[0].size else 0
8
    var rank = 0
9
    var pivotRow = 0
10
    var pivotCol = 0
11

12
    while (pivotRow < rows && pivotCol < cols) {
13
        // 寻找当前列的主元
14
        var maxRow = pivotRow
15
        for (i in pivotRow + 1..<rows) {
16
            if (abs(matrix[i][pivotCol]) > abs(matrix[maxRow][pivotCol])) {
17
                maxRow = i
18
            }
19
        }
20

21
        // 如果当前列所有元素都是0，则处理下一列
22
        if (abs(matrix[maxRow][pivotCol]) < 1e-10) {
23
            pivotCol++
24
            continue
25
        }
26

27
        // 交换行
28
        if (maxRow != pivotRow) {
29
            val temp = matrix[pivotRow]
30
            matrix[pivotRow] = matrix[maxRow]
31
            matrix[maxRow] = temp
32
        }
33

34
        // 归一化主元行
35
        val divisor = matrix[pivotRow][pivotCol]
36
        for (j in pivotCol..<cols) {
37
            matrix[pivotRow][j] /= divisor
38
        }
39

40
        // 消元操作，使主元所在列的其他元素为0
41
        for (i in 0..<rows) {
42
            if (i != pivotRow) {
43
                val factor = matrix[i][pivotCol]
44
                for (j in pivotCol..<cols) {
45
                    matrix[i][j] -= factor * matrix[pivotRow][j]
46
                }
47
            }
48
        }
49

50
        // 处理下一行和下一列
51
        pivotRow++
52
        pivotCol++
53
        rank++
54
    }
55

56
    return rank
57
}

主元选择#

在每一轮迭代中，算法会遍历当前列（从当前行开始），找到绝对值最大的元素作为主元。这一步称为主元选择，目的是减少浮点数计算中的舍入误差。若当前列所有元素的绝对值均小于极小值，则认为该列无主元，跳过并处理下一列。

1
// 寻找主元
2
var maxRow = pivotRow
3
for (i in pivotRow + 1 until rows) {
4
    if (abs(matrix[i][pivotCol]) > abs(matrix[maxRow][pivotCol])) {
5
        maxRow = i
6
    }
7
}
8

9
// 检查主元是否为0
10
if (abs(matrix[maxRow][pivotCol]) < 1e-10) {
11
    pivotCol++
12
    continue
13
}

行交换与归一化#

找到主元后，将其所在行与当前处理行交换，确保主元位于目标位置。随后将主元行的所有元素除以主元值，使主元变为 1，这是行最简形矩阵的基本要求。

1
// 行交换
2
if (maxRow != pivotRow) {
3
    val temp = matrix[pivotRow]
4
    matrix[pivotRow] = matrix[maxRow]
5
    matrix[maxRow] = temp
6
}
7

8
// 归一化主元行
9
val divisor = matrix[pivotRow][pivotCol]
10
for (j in pivotCol until cols) {
11
    matrix[pivotRow][j] /= divisor
12
}

消元操作#

消元是算法的关键步骤：对于每一行（除主元行外），计算当前行在主元列的元素与主元行的系数，通过线性组合将该列元素消为 0。

1
// 消元操作
2
for (i in 0 until rows) {
3
    if (i != pivotRow) {
4
        val factor = matrix[i][pivotCol]
5
        for (j in pivotCol until cols) {
6
            matrix[i][j] -= factor * matrix[pivotRow][j]
7
        }
8
    }
9
}

有了这个程序，至少让我在复习线性代数的时候方便了不少

高斯-约旦消元法#

主元选择#

行交换与归一化#

消元操作#

文章分享

音乐