Молодогвардейцев 454015 Россия, Челябинская область, город Челябинск 89085842764
MindHalls logo

Рекурсивное вычисление определителя квадратной матрицы на C/C++

Доброго времени суток, дорогие друзья! Я практически не затрагивал алгоритмы с матрицами в своем блоге, разве что показал параллельную реализацию умножения матриц с помощью OpenMP. И сейчас я буду это исправлять, и начну, пожалуй, с вычисления определителя квадратной матрицы. Программное нахождение определителя матрицы это не самая простая задача, именно поэтому для начала я реализую его рекурсивной функцией и только для квадратной матрицы. В тот момент, когда доберусь до матрицы любого размера, обязательно оставлю здесь ссылку.

Формулы вычисления определителя

Формулу через перестановки даже нет смысла рассматривать, потому что она включает в себя n! слагаемых. Вместо этого кратко глянем на значения определителя для матриц разного размера.

Для матриц размера 1х1

Значением определителя является единственный элемент матрицы.

Для матриц размера 2х2

Легко посчитать по формуле через перестановки. det = M[0][0]*M[1][1] — M[0][1]*M[1][0], где M — матрица. В реализации алгоритма эта формула будет использована в условии выхода из рекурсии.

Для матриц NxN

Для матриц такого размера уже придется уходить в рекурсию по формуле

Где M является дополнительным минором к элементу a1j. Минор в свою очередь это определитель матрицы без 1-ой строки и j-го столбца, вот здесь и появится рекурсия. Такая формула называется разложением по строке.

Еще один способ нахождения определителя заключается в том, чтобы методом Гаусса привести матрицу к ступенчатому виду(когда выше главной диагонали нули). Сделать это можно путем последовательного выполнения трех операций: сложение двух строк, поменять две строки местами, умножить строку на константу. После этих преобразований достаточно будет просто перемножить элементы на главной диагонали и получить определитель.

Формулы взяты со статьи на википедии, где описаны достаточно доступно и подробно. Кажется, бери да реализуй, но какую выбрать? Самым эффективным алгоритмом является метод Гаусса, приведение матрицы к ступенчатому виду составит всего O(n3) операций, но он же и является самым тяжелым в реализации. Возможно я его когда нибудь напишу, ну а пока придется довольствоваться нахождением определителя разложением по строке.

Реализация поиска определителя разложением по строке

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

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

//Возвращает матрицу matrix без row-ой строки и col-того столбца, результат в newMatrix
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++) {
        //Пропустить row-ую строку
        if(i == row) {
            offsetRow = 1; //Как только встретили строку, которую надо пропустить, делаем смещение для исходной матрицы
        }

        offsetCol = 0; //Обнулить смещение столбца
        for(int j = 0; j < size-1; j++) {
            //Пропустить col-ый столбец
            if(j == col) {
                offsetCol = 1; //Встретили нужный столбец, проускаем его смещением
            }

            newMatrix[i][j] = matrix[i + offsetRow][j + offsetCol];
        }
    }
}

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

Важно! Не пренебрегайте очищением памяти от дополнительной матрицы на каждом шаге рекурсии, иначе будет серьезная утечка памяти в программе.

Исходный код функции рекурсивного нахождения определителя матрицы на C/C++

//Вычисление определителя матрицы разложение по первой строке
int matrixDet(int **matrix, int size) {
    int det = 0;
    int degree = 1; // (-1)^(1+j) из формулы определителя

    //Условие выхода из рекурсии
    if(size == 1) {
        return matrix[0][0];
    }
    //Условие выхода из рекурсии
    else if(size == 2) {
        return matrix[0][0]*matrix[1][1] - matrix[0][1]*matrix[1][0];
    }
    else {
        //Матрица без строки и столбца
        int **newMatrix = new int*[size-1];
        for(int i = 0; i < size-1; i++) {
            newMatrix[i] = new int[size-1];
        }

        //Раскладываем по 0-ой строке, цикл бежит по столбцам
        for(int j = 0; j < size; j++) {
            //Удалить из матрицы i-ю строку и j-ый столбец
            //Результат в newMatrix
            getMatrixWithoutRowAndCol(matrix, size, 0, j, newMatrix);

            //Рекурсивный вызов
            //По формуле: сумма по j, (-1)^(1+j) * matrix[0][j] * minor_j (это и есть сумма из формулы)
            //где minor_j - дополнительный минор элемента matrix[0][j]
            // (напомню, что минор это определитель матрицы без 0-ой строки и j-го столбца)
            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;
}

Заключение

Такая реализация будет очень долго считать определитель у матриц размером больше 15, именно поэтому моим следующим шагом станет распараллеливание этого алгоритма с помощью директив OpenMP, интересно будет посмотреть на результат ускорения. А на сегодня у меня все, спасибо за внимание!