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

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

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

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

  • Автор
    Сообщения
  • #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;
    }

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

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

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