Реализация метода прогонки решения СЛАУ на С++

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

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

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

    Метод прогонки предназначен для решения трехдиагональных систем линейных алгебраических уравнений (такие системы часто появляются при решении ряда прикладных задач).

    Пусть матрица системы уравнений находится в массиве matA[N][N], а столбец свободных членов — в массиве matB[N].

    В алгоритме часто используется значение N-1, т.к. по-особому обрабатывается последняя строка матрицы:
    int N1 = N - 1;

    Во время работы алгоритма рассчитываются вспомогательные массивы:
    double y, a[N], B[N], matRes[N];

    Во время прямого хода алгоритма заполняются массивы a и B:

      y = matA[0][0];
      a[0] = -matA[0][1] / y;
      B[0] = matB[0] / y  ;
    
      for (int i = 1; i < N1; i++) {
        y = matA[i][i] + matA[i][i - 1] * a[i - 1];
        a[i] = -matA[i][i + 1] / y;
        B[i] = (matB[i] - matA[i][i - 1] * B[i - 1]) / y;
      }

    На обратном ходе из коэффициентов рассчитываются корни системы уравнения:

      matRes[N1] = (matB[N1] - matA[N1][N1 - 1] * B[N1 - 1]) / (matA[N1][N1] + matA[N1][N1 - 1] * a[N1 - 1]);
      for (int i = N1 - 1; i >= 0; i--) {
        matRes[i] = a[i] * matRes[i + 1] + B[i];
      }

    После этого корни системы будут находится в массиве matRes.

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

    Наконец, в ряде случаев алгоритм может не сработать -если при вычислении значения y[i] на прямом ходе алгоритма получится число, близкое к нулю. В этом алгоритме мы не может выполнять перестановку строк, как мы поступали в похожей ситуации в алгоритме Гаусса, т.к. матрица является трехдиагональной и алгоритму важен порядок строк и столбцов.

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