Алгоритм для преобразование матрицы в треугольную?

Question

[serhiops]

При помощи преобразования матрицы в треугольный вид, удобно находить ее ранг и детерминант. Я написал следующий метод:

toUpperTriangle() {

    for (let i = 0; i < this.rows-1; i++) {

      let divider = this.get(i, i) || 1;
      for (let j = i+1; j < this.rows && i < this.cols; j++) {
        
        const firstElement = this.get(j, i);
        for (let k = 0; k < this.cols; k++) {
          const res = this.get(j, k) - this.get(i, k) / divider * firstElement;
          this.set(j, k, res);
          
        }
        
      }
      
    }

  }

где this.rows - количество строк, this.cols - количесвто столбцов, методы get и set берут и устанавливают данные по соответсвующим индексам матрицы(индексация начинается с 0).
Этот метод работает для большинства матриц, но в некоторых дает сбой, напрмер:
Входная матрица -

[
  [4, 2, -2, 1, 5],
  [12, 6, 1, 0, 3],
  [0, 0, -1, 0, 0],
  [-2, 0, 0, 0, 0],
]

Выходная -

[
  [4, 2,  -2, 1, 5],
  [0, 0, 7, -3, -12],
  [0, 0, -1, 0, 0],
  [0, 1, 0, 3.5, 14.5]
}

Пока что в голову лезет вариант пересортировывать рядки матрицы по количеству последовательных 0 в начале после каждого преобразования рядка.
Буду рад любой помощи и примерам кода на любых языках

Comments

[mayton2019]

Почитайте про метод Гаусса-Жордана. Там есть шаг связанный с сведением матрицы к треугольной.

Answer 1

[Александр Скуснов]

Что интересно, так это то, что лучше сделать две треугольные матрицы, чем одну: так называемое LU-разложение (ролик Натана Куца). У метода Гаусса сложность О(N^3), а у LU - O(N^2), поэтому этот метод намного быстрее для огромных матриц.
Там тоже можно переставлять неудачные строки (пример в ролике).

Answer 2

[Wataru]

Надо на каждой итерации искать среди оставшихся строк ту, у которой в данном столбце стоит максимальное по модулю значение. Менять местами эту строку с i-ой, потом все точно так же.

Если считатете определитель, то надо еще помнить, что при помене двух строк местами, его знак меняется на противоположный - запоминайте, сколько раз помены сделали.