我的高斯-乔丹消除有什么问题？

Question

问题解决了。请看一下我自己在这个StackOverflow问题中的答案，了解如何。

但是，这是新的（并且正确工作的）代码：

显示器与下面相同。

/**
  * Returns the identity matrix of the specified dimension
  * @param size the number of columns (i.e. the number of rows) of the desired identity matrix
  * @return the identity matrix of the specified dimension
  */
def getIdentityMatrix(size : Int): scala.collection.mutable.Seq[scala.collection.mutable.Seq[Double]] = {
  scala.collection.mutable.Seq.tabulate(size)(r => scala.collection.mutable.Seq.tabulate(size)(c => if(r == c) 1.0 else 0.0))
}

  /**
    * This algorithm processes column by column.
    * STEP 1. It finds the greatest coefficient for the current column (called 'a') and, if it equals 0, returns NULL (since the matrix
    * can't be inverted) ; otherwise (STEP 2.), it swaps the pivot's line with this new line and the pivot becomes the adequate coefficient
    * of this new line
    * STEP 3. It divides the pivot's line by the pivot
    * STEP 4. It sets each of the current column's coefficient to 0 by subtracting the corresponding lines by the pivot's line
    * @return
    */
  def getGaussJordanInvertedMatrix: (Matrix, Matrix) = {

    // We get first the matrix to be inverted, second the identity one
    val mutable_being_inversed_matrix : collection.mutable.Seq[collection.mutable.Seq[Double]] = scala.collection.mutable.Seq(content.map(ms => scala.collection.mutable.Seq(ms:_*)):_*)
    val identity_matrix : collection.mutable.Seq[collection.mutable.Seq[Double]] = getIdentityMatrix(content.length)  // We get the identity matrix. It will be modified
                                                                      // as the original matrix will.

    var id_last_pivot : Int = 0  // ID of the last pivot, i.e. ID of the current column
    content.indices.foreach(general_id_column => {
      println("Current column : " + general_id_column)

      //  STEP 1.
      val id_line_with_max_coefficient_in_this_column = (id_last_pivot until content.length).maxBy(id_line_in_this_column => Math.abs(mutable_being_inversed_matrix(id_line_in_this_column)(general_id_column)))

      if(mutable_being_inversed_matrix(id_line_with_max_coefficient_in_this_column)(general_id_column) == 0) {
        println("The Gauss-Jordan elimination's algorithm returns an error : indeed, the matrix can't be inverted")

      } else {

        //  STEP 2.
        val tmp_line : scala.collection.mutable.Seq[Double] = mutable_being_inversed_matrix(id_last_pivot)
        mutable_being_inversed_matrix(id_last_pivot) = mutable_being_inversed_matrix(id_line_with_max_coefficient_in_this_column)
        mutable_being_inversed_matrix(id_line_with_max_coefficient_in_this_column) = tmp_line

        val identity_tmp_line : scala.collection.mutable.Seq[Double] = identity_matrix(id_last_pivot)
        identity_matrix(id_last_pivot) = identity_matrix(id_line_with_max_coefficient_in_this_column)
        identity_matrix(id_line_with_max_coefficient_in_this_column) = identity_tmp_line
        println("\nSWAP DONE")
        println(Console.BLUE + "Original matrix :\n" + Console.RESET + mutable_being_inversed_matrix.mkString("\n"))
        println(Console.RED + "Identity matrix :\n" + Console.RESET + identity_matrix.mkString("\n"))

        //  STEP 3.
        val tmp = mutable_being_inversed_matrix(id_last_pivot)(general_id_column)
        mutable_being_inversed_matrix(id_last_pivot) = mutable_being_inversed_matrix(id_last_pivot).map(coefficient => coefficient / tmp)
        identity_matrix(id_last_pivot) = identity_matrix(id_last_pivot).map(coefficient => coefficient / tmp)

        println("\nDIVISION DONE")
        println(Console.BLUE + "Original matrix :\n" + Console.RESET + mutable_being_inversed_matrix.mkString("\n"))
        println(Console.RED + "Identity matrix :\n" + Console.RESET + identity_matrix.mkString("\n"))

        //  STEP 4.
        content.indices.foreach(id_line => {
          val tmp = mutable_being_inversed_matrix(id_line)(general_id_column)

          if(id_line != id_last_pivot) {
            content.indices.foreach(id_column => {
              mutable_being_inversed_matrix(id_line)(id_column) -= mutable_being_inversed_matrix(id_last_pivot)(id_column) * tmp
              identity_matrix(id_line)(id_column) -= identity_matrix(id_last_pivot)(id_column) * tmp
            })
          }

        })

        println("\nSUBTRACTION & MULTIPLICATION DONE")
        println(Console.BLUE + "Original matrix :\n" + Console.RESET + mutable_being_inversed_matrix.mkString("\n"))
        println(Console.RED + "Identity matrix :\n" + Console.RESET + identity_matrix.mkString("\n"))
        println()

        id_last_pivot += 1

      }

    })

    (new Matrix(identity_matrix), new Matrix(mutable_being_inversed_matrix))
  }

我试图实现Gauss-Jordan消去法的Scala版本来反转矩阵(注意:可变集合和命令式范例用于简化实现——我试图不使用它们来编写算法，但这几乎是不可能的，因为算法包含嵌套步骤)。

单位矩阵不能很好地转换为反演的结果。换句话说：单位矩阵变换为倒矩阵（这是高斯-乔丹消除的结果）是不正确的。

考虑这个矩阵（A）：

（2.0，-1.0,0.0）

(-1.0, 2.0, -1.0)

（0.0，-1.0,2.0）

而这个（B）：

(1.0, 0.0, 0.0)

（0.0、1.0、0.0）

（0.0,0.0,1.0）

如果我们应用高斯-乔丹消去，A变成：

(1.0, 0.0, 0.0)

（0.0、1.0、0.0）

（0.0,0.0,1.0）

如果我们应用高斯-乔丹消除，B 变为：

(0.75 0.5 0.25)

(0.5 1 0.5)

(0.25 0.5 0.75)

如果我们应用我的实现，A就没有问题，因为我得到了以下矩阵：

(1.0, 0.0, 0.0)

（0.0、1.0、0.0）

（0.0,0.0,1.0）

但是，如果我们应用我的实现，则B没有很好地转换，因为我获得了以下矩阵：

(1.0, 0.5, 0.0)

(1.0, 0.5, 0.6666666666666666)

(0.0, 1.0, 0.33333333333333337)

它分 3 个步骤逐列进行。这些步骤是：

1. 我们在当前列^2中找到max^1系数。如果它等于 0，则表示矩阵无法反转，算法返回此错误。否则，我们将包含最大系数的行与包含枢轴的线交换：换句话说，我们用列的最大系数更改枢轴（注意：整行被交换）。^1 ： max 是仅用于除法精度原因（在 STEP 2 中完成的除法）的函数。另一个功能是随机函数。

^2 ： 当前列中的最大系数从第 （z 1） 行找到，其中 z 是我们使用的最后一个枢轴的 ID（即：最后一个工作列的 ID）

我们将包含我们在 STEP 1 得到的枢轴的整行除以枢轴，将枢轴设置为 1（在后面的句子中，表达式“枢轴”系统地指的是我们在 STEP 1 得到的这个枢轴）。顺便说一下，请注意一个不太重要的事实，即同一条线的其他系数也被划分（参见“我们划分整条线”）。

我们将当前列的每一整行自身乘以枢轴线，以将当前列所有系数设置为0。顺便说一句，请注意一个不太重要的事实，即这些相同行的其他系数也会被减去（参见“我们减去每整行”）。

步骤 3 和 STEP 2 在步骤 1 中实现（即：这些是嵌套的步骤）。步骤 3 必须在步骤 2 之后实现（以利用步骤 3 中实现的 {减法和乘法} 中的枢轴值 = 1。

val m : Matrix = new Matrix(Seq(Seq(2, -1, 0), Seq(-1, 2, -1), Seq(0, -1, 2)))

val m : Matrix = new Matrix(Seq(Seq(2, -1, 0), Seq(-1, 2, -1), Seq(0, -1, 2)))
println("ORIGINAL MATRIX =\n" + m)
println
val result : (Matrix, Matrix) = m.getGaussJordanInvertedMatrix
println()
println("RESULT =\n" + Console.BLUE + "Original matrix :\n" + Console.RESET + result._2 + Console.RED + "\nIdentity matrix :\n" + Console.RESET + result._1)

/**
  * Returns the identity matrix of the specified dimension
  * @param size the number of columns (i.e. the number of rows) of the desired identity matrix
  * @return the identity matrix of the specified dimension
  */
def getIdentityMatrix(size : Int): scala.collection.mutable.Seq[scala.collection.mutable.Seq[Double]] = {
  scala.collection.mutable.Seq.tabulate(size)(r => scala.collection.mutable.Seq.tabulate(size)(c => if(r == c) 1.0 else 0.0))
}

  /**
    * This algorithm processes column by column.
    * STEP 1. It finds the greatest coefficient for the current column (called 'a') and, if it equals 0, returns NULL (since the matrix
    * can't be inverted) ; otherwise (STEP 2.), it swaps the pivot's line with this new line and the pivot becomes the adequate coefficient
    * of this new line
    * STEP 3. It divides the pivot's line by the pivot
    * STEP 4. It sets each of the current column's coefficient to 0 by subtracting the corresponding lines by the pivot's line
    * @return
    */
  def getGaussJordanInvertedMatrix: (Matrix, Matrix) = {

    // We get first the matrix to be inverted, second the identity one
    val mutable_being_inversed_matrix : collection.mutable.Seq[collection.mutable.Seq[Double]] = scala.collection.mutable.Seq(content.map(ms => scala.collection.mutable.Seq(ms:_*)):_*)
    val identity_matrix : collection.mutable.Seq[collection.mutable.Seq[Double]] = getIdentityMatrix(content.length)  // We get the identity matrix. It will be modified
                                                                      // as the original matrix will.

    var id_last_pivot : Int = 0  // ID of the last pivot, i.e. ID of the current column
    content.indices.foreach(general_id_column => {
      println("Current column : " + general_id_column)

      //  STEP 1.
      val id_line_with_max_coefficient_in_this_column = (id_last_pivot until content.length).maxBy(id_line_in_this_column => Math.abs(mutable_being_inversed_matrix(id_line_in_this_column)(general_id_column)))

      if(mutable_being_inversed_matrix(id_line_with_max_coefficient_in_this_column)(general_id_column) == 0) {
        println("The Gauss-Jordan elimination's algorithm returns an error : indeed, the matrix can't be inverted")

      } else {

        //  STEP 2.
        val tmp_line : scala.collection.mutable.Seq[Double] = mutable_being_inversed_matrix(id_last_pivot)
        mutable_being_inversed_matrix(id_last_pivot) = mutable_being_inversed_matrix(id_line_with_max_coefficient_in_this_column)
        mutable_being_inversed_matrix(id_line_with_max_coefficient_in_this_column) = tmp_line

        val identity_tmp_line : scala.collection.mutable.Seq[Double] = identity_matrix(id_last_pivot)
        identity_matrix(id_last_pivot) = identity_matrix(id_line_with_max_coefficient_in_this_column)
        identity_matrix(id_line_with_max_coefficient_in_this_column) = identity_tmp_line
        println("\nSWAP DONE")
        println(Console.BLUE + "Original matrix :\n" + Console.RESET + mutable_being_inversed_matrix.mkString("\n"))
        println(Console.RED + "Identity matrix :\n" + Console.RESET + identity_matrix.mkString("\n"))

        //  STEP 3.
        mutable_being_inversed_matrix(id_last_pivot) = mutable_being_inversed_matrix(id_last_pivot).map(coefficient => coefficient / mutable_being_inversed_matrix(id_last_pivot)(general_id_column))
        identity_matrix(id_last_pivot) = identity_matrix(id_last_pivot).map(coefficient => coefficient / mutable_being_inversed_matrix(id_last_pivot)(general_id_column))

        println("\nDIVISION DONE")
        println(Console.BLUE + "Original matrix :\n" + Console.RESET + mutable_being_inversed_matrix.mkString("\n"))
        println(Console.RED + "Identity matrix :\n" + Console.RESET + identity_matrix.mkString("\n"))

        //  STEP 4.
        content.indices.foreach(id_line => {
          val tmp = mutable_being_inversed_matrix(id_line)(general_id_column)

          if(id_line != id_last_pivot) {
            content.indices.foreach(id_column => {
              mutable_being_inversed_matrix(id_line)(id_column) -= mutable_being_inversed_matrix(id_last_pivot)(id_column) * tmp
              identity_matrix(id_line)(id_column) -= mutable_being_inversed_matrix(id_last_pivot)(id_column) * tmp
            })
          }

        })

        println("\nSUBTRACTION & MULTIPLICATION DONE")
        println(Console.BLUE + "Original matrix :\n" + Console.RESET + mutable_being_inversed_matrix.mkString("\n"))
        println(Console.RED + "Identity matrix :\n" + Console.RESET + identity_matrix.mkString("\n"))
        println()

        id_last_pivot += 1

      }

    })

    (new Matrix(identity_matrix), new Matrix(mutable_being_inversed_matrix))
  }

你可以在这里找到我的实现的执行：https://jsfiddle.net/wwhdu32x/

您可以在这里找到一个故障排除:https://jsfiddle.net/wwhdu32x/1/(以“错误”开头的注释被写入-注意:这个故障排除只涉及第一次迭代，即第一列)。

为什么我的身份矩阵没有很好的转换？我该怎么处理呢？

Answer 1

问题解决了。问题已经更新，其中包括新代码（旧代码仍然可用，以便进行比较）。有两个错误（下面的“STEP XYZ”引用了相应的源代码的STEP，而不是这个StackOverflow问题中提到的步骤，它们的呈现方式有点不同）：

> < li>

关于单位矩阵的减法没有使用单位矩阵的系数(步骤4)。错误修复:< code > identity _ matrix(id _ line)(id _ column)-= identity _ matrix(id _ last _ pivot)(id _ column)* tmp

其次，在第3步中，我忘记将数据透视存储在临时变量中，以便用它划分两个矩阵（原始矩阵和同一性矩阵）。如果不存储它，在对原始矩阵进行划分后，数据透视的值发生了变化。错误修复：

    val tmp = mutable_being_inversed_matrix(id_last_pivot)(general_id_column)
    mutable_being_inversed_matrix(id_last_pivot) = mutable_being_inversed_matrix(id_last_pivot).map(coefficient => coefficient / tmp)
    identity_matrix(id_last_pivot) = identity_matrix(id_last_pivot).map(coefficient => coefficient / tmp)