Приведения матрицы к треугольному виду на С++

      Комментарии к записи Приведения матрицы к треугольному виду на С++ отключены

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

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

    Во многих математических алгоритмах при обработке матриц требуется их приведение к треугольному виду (триангуляция). Подробно алгоритм триангуляции описан в статье: «Алгоритм триангуляции матрицы«. Рассмотрим реализацию этого алгоритма на С++.

    Блок-схема алгоритма:

    Матрицу будем рассматривать как вектор, элементами которого являются другие вектора (std::vector). В нашей реализации будет использоваться алгоритм с выбором максимального элемента в столбце. Перед обращением в ноль элементов i-того столбца с помощью эквивалентных преобразований мы выполним поиск в нем максимального элемента и перестановку строки, содержащей этот элемент с i-той строкой. Для этого нам потребуется функция, выполняющая поиск максимума:

    template <typename T>
    int col_max(const std::vector<std::vector<T> > &matrix, int col, int n) {
      T max = std::abs(matrix[col][col]);
      int maxPos = col;
      for (int i = col+1; i < n; ++i) {
        T element = std::abs(matrix[i][col]);
        if (element > max) {
          max = element;
          maxPos = i;
        }
      }
      return maxPos;
    }

    При наличии такой функции, для реализации представленного выше алгоритма не хватает лишь функции перестановки строк. Однако, в силу того, что мы используем вектор из векторов в качестве матрицы — можно использовать стандартную функцию std::swap. Такое решение является не только стандартным, но и очень эффективным, т.к. эта функция использует move-семантику. Использование семантики перемещения означает, что перестановка строк будет выполнена за постоянное время, не зависящее от количества «перемещаемых элементов». Читать подробнее про семантику перемещения и оценку трудоемкости алгоритмов.

    template <typename T>
    int triangulation(std::vector<std::vector<T> > &matrix, int n) {
      unsigned int swapCount = 0;
      for (int i = 0; i < n-1; ++i) {
        unsigned int imax = col_max(matrix, i, n);
        if (i != imax) {
          swap(matrix[i], matrix[imax]);
          ++swapCount;
        }
        for (int j = i + 1; j < n; ++j) {
          T mul = -matrix[j][i]/matrix[i][i];
    
          for (int k = i; k < n; ++k) {
            matrix[j][k] += matrix[i][k]*mul;
          }
        }
      }
      return swapCount;
    }

    Стоит обратить внимание на то, что функция подсчитывает количество перестановок строк при выполнении триангуляции. Это нужно, например потому, что такие перестановки влияют на значение детерминанта — он меняет свой знак при каждой перестановке.

    Рассмотренной реализацией можно, например, заменить значительную часть кода при решения СЛАУ методом Гаусса-Жордана.

  • #3949

    В некоторых случаях требуется приводить к треугольному виду матрицу, не являющуюся квадратной. При этом не подойдет алгоритм, описанный выше. Например, такая операция нужна при решении СЛАУ методом Гаусса, т.к. расширенная матрица системы содержит также столбец свободных членов (ее размерность N на N+1). При выполнении операции над элементами строки матрицы (например, умножение на константу, сложение или перестановка с элементами другой строки) действия должны выполняться и с элементов столбца свободных членов.

    Описанная выше функция не подойдет, однако ее можно доработать:

    template <typename T>
    int triangulation(std::vector<std::vector<T> > &matrix, int n) {
      unsigned int swapCount = 0;
    
      if (0 == n)
        return swapCount;
    
      const int num_cols = matrix[0].size();
      for (int i = 0; i < n-1; ++i) {
        unsigned int imax = col_max(matrix, i, n);
        if (i != imax) {
          swap(matrix[i], matrix[imax]);
          ++swapCount;
        }
    
        for (int j = i + 1; j < n; ++j) {
          T mul = -matrix[j][i]/matrix[i][i];
          for (int k = i; k < num_cols; ++k) {
            matrix[j][k] += matrix[i][k]*mul;
          }
        }
      }
      return swapCount;
    }

    Тут при обработке элементов строки элементы перебираются не до n-1, а до matrix[0].size()-1. Полагаем, что все строки матрицы имеют одинаковую длину.

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