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

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

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

高斯-约旦消元法

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

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

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

/**
 * 计算矩阵的行最简形式
 * @return 矩阵的秩
 */
fun computeRREF(matrix: Array<DoubleArray>): Int {
    val rows = matrix.size
    val cols = if (rows > 0) matrix[0].size else 0
    var rank = 0
    var pivotRow = 0
    var pivotCol = 0

    while (pivotRow < rows && pivotCol < cols) {
        // 寻找当前列的主元
        var maxRow = pivotRow
        for (i in pivotRow + 1..<rows) {
            if (abs(matrix[i][pivotCol]) > abs(matrix[maxRow][pivotCol])) {
                maxRow = i
            }
        }

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

        // 交换行
        if (maxRow != pivotRow) {
            val temp = matrix[pivotRow]
            matrix[pivotRow] = matrix[maxRow]
            matrix[maxRow] = temp
        }

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

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

        // 处理下一行和下一列
        pivotRow++
        pivotCol++
        rank++
    }

    return rank
}

主元选择

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

// 寻找主元
var maxRow = pivotRow
for (i in pivotRow + 1 until rows) {
    if (abs(matrix[i][pivotCol]) > abs(matrix[maxRow][pivotCol])) {
        maxRow = i
    }
}

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

行交换与归一化

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

// 行交换
if (maxRow != pivotRow) {
    val temp = matrix[pivotRow]
    matrix[pivotRow] = matrix[maxRow]
    matrix[maxRow] = temp
}

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

消元操作

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

// 消元操作
for (i in 0 until rows) {
    if (i != pivotRow) {
        val factor = matrix[i][pivotCol]
        for (j in pivotCol until cols) {
            matrix[i][j] -= factor * matrix[pivotRow][j]
        }
    }
}

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