Вычисление определителя разложением по строке на С++

Программирование Программирование на С++ Решение задач на С++ Реализация численных методов на С++ Вычисление определителя разложением по строке на С++

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 1 месяц, 2 нед. назад.

  • Автор
    Сообщения
  • #5509
    @admin

    Непосредственно алгоритм описан в соответствующей статье. Теперь рассмотрим его реализацию. Реализацию более эффективного алгоритма вы можете найти по ссылке «Метод Гаусса вычисления определителя на C++«.

    Для того, чтобы посчитать определитель «в лоб» по формуле, нам понадобиться функция удаления из матрицы i-ой строки и j-го столбца. Затем матрицу без строки и без столбца мы загоним в рекурсию и так до тех пор, пока размер матрицы на станет 2х2, это и будет условием выхода из рекурсии.

    Исходный код функции удаления строки и столбца из матрицы на C/C++:

    void getMatrixWithoutRowAndCol(int **matrix, int size, int row, int col, int **newMatrix) {
      int offsetRow = 0; 
      int offsetCol = 0; 
      for(int i = 0; i < size-1; i++) {
        if(i == row) {
          offsetRow = 1; 
        }
     
        offsetCol = 0;
        for(int j = 0; j < size-1; j++) {
          if(j == col) {
            offsetCol = 1; 
          }
     
          newMatrix[i][j] = matrix[i + offsetRow][j + offsetCol];
        }
      }
    }

    На вход функции подается матрица, ее размеры и столбец, который необходимо «вычернкуть». Алгоритм заключается в следующем: копируем элементы исходной матрицы до заданной строки и слолбца «один к одному», а затем «перепрыгиваем» через удаляемые строку и столбец. Переменные offsetRow и offsetCol хранят «смещение» индекса — при обработке элементов левее удаляемого столбца offsetCol равен нулю, для элементов правее — единице. Значение изменяется как только мы дойдем до нужного столбца/строки ((i == row)).

    Естественно, память под новую матрицу должна быть заранее выделена и надо не забыть ее освободить после использования.

    Займемся, наконец, вычислением определителя. На вход функция принимает только саму матрицу и ее размер. Проверяем размер матрицы, если он больше чем 2х2 уходим считать в рекурсию. Сначала создаем матрицу равную текущей с вырезанной нулевой строкой(по ней раскладываем) и j-ым столбцом, затем в цикле накручиваем сумму из формулы в переменную det.

    int matrixDet(int **matrix, int size) {
      int det = 0;
      int degree = 1; 
     
      if(size == 1) {
        return matrix[0][0];
      }
    
      if(size == 2) {
        return matrix[0][0]*matrix[1][1] - matrix[0][1]*matrix[1][0];
      }
     
      int **newMatrix = new int*[size-1];
      for(int i = 0; i < size-1; i++) {
        newMatrix[i] = new int[size-1];
      }
    
      for(int j = 0; j < size; j++) {
        getMatrixWithoutRowAndCol(matrix, size, 0, j, newMatrix);
    
        det = det + (degree * matrix[0][j] * matrixDet(newMatrix, size-1));
    
        degree = -degree;
      }
    
      for(int i = 0; i < size-1; i++) {
        delete [] newMatrix[i];
      }
      delete [] newMatrix;
     
      return det;
    }

    Для случаев когда размер меньше двух — вычисление идет по заранее известной формуле. В остальных случаях — рекурсивно. На каждом шаге создается матрица меньшего размера (newMatrix), заполняется с помощью описанной выше функции, рекурсивно считается ее определитель, затем (это важно), память из под матрицы освобождается.

    Асимптотическая сложность алгоритма по памяти чудовищна — для матрицы NxN мы порядка N раз выдяляем память под порядка NxX элементов. Таким образом, для матрицы дробных чисел (пускай 8 байт) размером 1000х1000 этот алгоритм затратит порядка 7 Гигабайт оперативной памяти.

Для ответа в этой теме необходимо авторизоваться.