Важное редактирование
Проблема решена. Пожалуйста, посмотрите на мой собственный ответ в этом вопросе StackOverflow, чтобы узнать как.
Однако, вот новый (и правильно работающий) код:
Displayer
Дисплей такой же, как показано ниже.
Моя правильная и рабочая реализация
/**
* 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))
}
Я пытаюсь реализовать Scala-версию исключения Гаусса-Джордана, чтобы инвертировать матрицу (примечание: изменяемые коллекции и императивная парадигма используются для упрощения реализации - я пытался написать алгоритм без, но это практически невозможно, следовательно, к тому, что алгоритм содержит вложенные шаги).
Моя проблема
Тождественная матрица недостаточно хорошо преобразована в результат инверсии. Другими словами: преобразование единичной матрицы в инвертированную матрицу (что является результатом исключения Гаусса-Джордана) является некорректным.
Пример * * тысяча двадцать-одна
Рассмотрим эту матрицу (A):
(2,0, -1,0, 0,0)
(- 1,0, 2,0, -1,0)
(0,0, -1,0, 2,0)
А этот (Б):
(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. Если он равен 0, это означает, что матрица не может быть инвертирована, и алгоритм возвращает эту ошибку. В противном случае, мы меняем строку, содержащую коэффициент max, на строку, содержащую пивот: другими словами, мы меняем шарнир с максимальным коэффициентом столбца (Примечание: все строки меняются местами).
^ 1: max - используемая функция только из соображений точности делений (деления выполняются в ШАГЕ 2). Другая функция будет случайной.
^ 2: максимальный коэффициент в текущем столбце находится из (z + 1) -ой строки, где z - это идентификатор последнего использованного нами пивота (то есть: идентификатор последнего обработанного столбца)
Мы делим целую строку, содержащую стержень, который мы получили на шаге 1, на стержень, чтобы установить стержень на 1 (в более поздних предложениях выражение «стержень» систематически относится к этому стержню, который мы получили на шаге 1 ). Кстати, обратите внимание на менее важный факт, что другие коэффициенты этой же линии также делятся (см. «Мы делим всю линию»).
Мы вычитаем каждую целую строку текущего столбца по отдельности, умножая ее на строку, чтобы установить для коэффициента всего текущего столбца значение 0. Кстати, обратите внимание на менее важный факт, что другие коэффициенты этих же строк также вычитается (ср. «мы вычитаем каждую целую строку»).
ШАГ 3 и ШАГ 2 реализуются в ШАГЕ 1 (т.е. это вложенные ШАГИ). ШАГ 3 должен быть реализован после того, как STEP 2 (использовать значение поворотного в = 1 в {вычитаний и умножений} реализуется в STEP 3.
Устранение Гаусса-Джордана: моя неработающая реализация
Input
val m : Matrix = new Matrix(Seq(Seq(2, -1, 0), Seq(-1, 2, -1), Seq(0, -1, 2)))
Неработающая реализация этого алгоритма
Displayer
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/ (комментарии, начинающиеся с «ОШИБКА» написаны - примечание: это устранение неполадок касается только первой итерации, то есть первого столбца).
Мой вопрос
Почему моя матрица идентичности плохо трансформирована? Как я мог справиться с этим?