§ 5. Алгоритм решения краевой задачи — прогонка
1. Описание прогонки.
Опишем теперь простой и удобный метод решения разностной краевой задачи рассмотренного нами в § 4 вида:
Он представляет собою один из вариантов метода исключения неизвестных и носит название метода прогонки.
Запишем уравнение 
системы (1) в виде
где 
. Из уравнения
отвечающего в системе (1) номеру 
исключим 
с помощью равенства 
Результат запишем в разрешенном относительно 
виде
введя обозначения
Соотношением 
можно воспользоваться, чтобы исключить 
из уравнения
отвечающего номеру 
Результат йсключения опять запишем в явном относительно 
виде
Описанный процесс исключения можно продолжить для n = 3, 4, ...
Подставляя
в уравнение
получим
Отсюда видно, что коэффициенты получаемых в процессе исключения соотношений
вычисляются по рекуррентным формулам
Последнее из получаемых таким образом соотношений имеет вид
Так как 
то можно вычислить 
После этого 
и т. д. определятся соответственно из равенств
и т. д., пока не будет определено 
.
Повторим кратко, в чем состоит описанный сейчас вычислительный процесс.
Сначала проводится вычисление-коэффициентов 
в порядке возрастания номеров (прямая прогонка) по рекуррентным формулам (2), причем 
заданы.
Затем вычисление неизвестных 
производится также рекуррентно в порядке убывания номеров (обратная прогонка) по формулам
Отметим, что для вычисления методом прогонки решения 
системы (1), состоящей из 
уравнений, нужно проделать арифметические операции в количестве только в конечное число раз большем, чем число неизвестных. На решение произвольной линейной системы N уравнений с N неизвестными методом исключения приходится обычно затрачивать арифметические действия в количестве порядка 
Такого-сокращения числа арифметических действий при решении системы (1) методом прогонки удалось достигнуть, удачно использовав специфику этой системы.
В § 7 будет показано, что при решении описанным здесь методом прогонки краевой задачи (1), удовлетворяющей одному из указанных в § 4 условий хорошей обусловленности
или
или
выражения 
на которые приходится делить, не обращаются в нуль, а погрешности, допускаемые в процессе вычислений, не накапливаются и не приводят к возрастающим с ростом N ошибкам в вычисляемых значениях решения.
Эти два замечательных свойства прогонки — малое число арифметических действий для ее реализации и слабая чувствительность к вычислительным погрешностям — делают прогонку очень удобным вычислительным алгоритмом.
