Уравнения в частных
производных > Прогонка
АЛГОРИТМ ПРОГОНКИ
приводит к системе линейных уравнений Aun+1=b с матрицей А и вектором правых частей уравнений b=un:
(начальные условия)
Нетрудно видеть, что матрица А имеет диагональное преобладание (а точнее, является трехдиагональной)
Применять для таких разреженных матриц типовые алгоритмы (в частности, алгоритм Гаусса), например, встроенную функцию lsolve, расточительно. Для таких задач (а кним приводит огромное количество неявных разностных схем для различных дифференциальных уравнений) разработан чрезвычайно эффективный алгоритм, называемый прогонкой.
Сначала применяются формулы "обратного хода" прогонки:
начальные значения:
правое гр.усл.
а затем "прямого хода", в результате которого определяется ответ
левое гр.усл.
В итоге затрачивается порядка М операций вместо М2, как в традиционных методах!
И вот, как будет выглядеть решение (1-й шаг), при отношении Куранта:
