Метод Гаусса вычисления определителя на C++

      Комментарии к записи Метод Гаусса вычисления определителя на C++ отключены

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

  • Автор
    Сообщения
  • #3450

    Мы уже рассматривали «Алгоритм вычисления определителя методом Гаусса«. Он сводится к приведению матрицы к треугольному виду (триангуляции) с помощью эквивалентных преобразований.

    Из блок-схемы алгоритма видно, что после того, как проведена триангуляция матрицы остается лишь посчитать произведение элементов на главной диагонали:

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

    При разработке программ, я советую вам не забывать о тестировании. При этом тестирование лучше производить автоматически, например, с использованием модульных тестов. Написать unit-тесты можно с помощью Boost Unit Test. Подробнее про это можно прочитать в статье «Юнит-тестирование. Пример. Boost Unit Test«. так, например для детерминанта могли бы быть написаны следующие тесты:

    #include "../../matrix/matrix.h"
    #include <boost/test/unit_test.hpp>
    
    BOOST_AUTO_TEST_SUITE(MatrixTest)
    
    const double Accuracy = 0.0001;
    
    BOOST_AUTO_TEST_CASE(Determinant2x2) {
      const int size = 2;
      std::vector<std::vector<double> >
              matrix = {{1, 2}, {3, 4}};
      double determinant;
    
      BOOST_CHECK_NO_THROW(determinant = gauss_determinant(matrix, size));
    
      BOOST_REQUIRE_CLOSE(determinant, -2, Accuracy);
    }
    
    BOOST_AUTO_TEST_CASE(Determinant3x3) {
      const int size = 3;
      std::vector<std::vector<double> >
              matrix = {{0, 1, 7}, {3, 4, 5}, {7, 8, 9}};
      double determinant;
    
      BOOST_CHECK_NO_THROW(determinant = gauss_determinant(matrix, size));
    
      BOOST_REQUIRE_CLOSE(determinant, -20, Accuracy);
    }
    
    BOOST_AUTO_TEST_SUITE_END()

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

    Алгоритм вычисления детерминанта, проходящий оба теста мог бы выглядеть так:

    template <typename T>
    T gauss_determinant(std::vector<std::vector<T> > &matrix, int n) {
      unsigned int swapCount = triangulation(matrix, n);
      T determinanit = 1;
      if (swapCount % 2 == 1)
        determinanit = -1;
      for (int i = 0; i < n; ++i) {
        determinanit *= matrix[i][i];
      }
      return determinanit;
    }

    Обратите внимание, что функция триангуляции возвращает количество перестановок, которое используется для инициализации начального значения детерминанта.

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