Метод Гаусса решения СЛАУ на С++

      Комментарии к записи Метод Гаусса решения СЛАУ на С++ отключены

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

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

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

    template <typename T>
    std::vector<T> gauss_solving(std::vector<std::vector<T> > &matrix, std::vector<T> &free_term_column, int n);

    Напишем модульные тесты с использованием Boost Test Framework:

    BOOST_AUTO_TEST_CASE(GaussSolving_Solution) {
      const int size = 3;
      std::vector<std::vector<double> >
        matrix = {{5,7,6}, {3, 16,19}, {13,10,7}};
      std::vector<double>
        free_term_column = {73, 110, 148},
        good_solution = {8, 3, 2},
        solution;
    
      BOOST_CHECK_NO_THROW(
        solution = gauss_solving(matrix, free_term_column, size)
      );
    
      BOOST_REQUIRE_EQUAL(solution.size(), size);
      for (int i = 0; i < size; ++i) {
        BOOST_REQUIRE_CLOSE(solution[i], good_solution[i], Accuracy);
      }
    }
    
    BOOST_AUTO_TEST_CASE(GaussSolving_NoSolution) {
      const int size = 2;
      std::vector<std::vector<double> >
        matrix = {{1,2}, {4,8}};
      std::vector<double>
        free_term_column = {3,6};
    
      BOOST_CHECK_THROW(gauss_solving(matrix, free_term_column, size),
                        NoSolution);
    }

    Перед выполнением триангуляции допишем в конец каждой строки элемент столбца свободных членов и используем функцию триангуляции, рассчитанную на то, что матрица может не являться квадратной. После выполнения этих операций, выполняется обратный ход алгоритма. Мы рассматривали два варианта обратного хода, в первом — уравнения перебираются начиная с последнего, для каждого из них вычисляется сумма a[i][j]*x[j]. При обходе уравнений с конца матрицы окажется, что для каждого уравнения достаточно данных чтобы вычислить все неизвестные:

    template <typename T>
    std::vector<T> gauss_solving(std::vector<std::vector<T> > &matrix,
                                  std::vector<T> &free_term_column, int n) {
      std::vector<T> solution(n);
    
      for (int i = 0; i < n; ++i) {
        matrix[i].push_back(free_term_column[i]);
      }
      triangulation(matrix, n);
    
      for (int i = n-1; i>=0; --i) {
        if (std::abs(matrix[i][i]) < 0.0001)
          throw NoSolution();
        for (int j = i+1; j < n; ++j) {
          matrix[i][n] -= matrix[i][j]*solution[j];
        }
        solution[i] = matrix[i][n]/matrix[i][i];
      }
    
      return solution;
    }

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

    template <typename T>
    std::vector<T> gauss_solving(std::vector<std::vector<T> > &matrix,
                                  std::vector<T> &free_term_column, int n) {
      std::vector<T> solution(n);
    
      for (int i = 0; i < n; ++i) {
        matrix[i].push_back(free_term_column[i]);
      }
      triangulation(matrix, n);
    
      for (int i = n-1; i>=0; --i) {
        if (std::abs(matrix[i][i]) < 0.0001)
          throw NoSolution();
        solution[i] = matrix[i][n]/matrix[i][i];
    
        for (int j = 0; j < i; ++j) {
          matrix[j][n] -= matrix[j][i]*solution[i];
        }
      }
    
      return solution;
    }

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