Рассмотрим теперь линейные разностные уравнения второго порядка
, 
, (13)
где 
заданные коэффициенты и правая часть и 
искомое решение. В дальнейшем будем предполагать, что 
, 
для всех 
.
Уравнение (13) имеет бесконечное множество решений. Каждое отдельное решение называется частным решением уравнения (13). Для того чтобы из совокупности всех решений уравнения (13) выделить единственное решение, необходимо задать те или иные дополнительные условия.
Задача Коши состоит в отыскании решения 
, 
, уравнения (13), удовлетворяющего при 
заданным начальным условиям
, 
. (14)
Если для всех допустимых , то уравнение (13) можно разрешить относительно 
, т.е. записать в виде
(15)
Отсюда следует, что задача Коши имеет единственное решение.
Краевая задача состоит в отыскании решения уравнения
, , (16)
удовлетворяющего дополнительным условиям
, 
, (17)
где 
заданные числа. В частности, при 
получаем краевые условия первого рода
, 
, (18)
а при 
краевые условия второго рода.
Рассмотрим задачу (16), (17). Система линейных алгебраических уравнений (16) имеет трехдиагональную матрицу, т.е. матрицу, все элементы которой, не лежащие на главной и двух побочных диагоналях, равны нулю.
Для численного решения систем с трехдиагональными матрицами применяется метод прогонки, который представляет собой вариант метода последовательного исключения неизвестных.
Приведем вывод расчетных формул метода прогонки. Будем искать решение системы (16) в виде
, 
, (19)
где 
неизвестные пока коэффициенты. Отсюда найдем
,
.
Подставляя полученные выражения для 
в уравнение (16)
, , (16)
приходим при к уравнению
,
откуда
.
Последнее уравнение будет выполнено, если коэффициенты 
выбрать так, чтобы выражения в квадратных скобках обращались в нуль. А именно, достаточно положить
, 
, . (20)
Соотношения (20) представляют собой нелинейные разностные уравнения первого порядка. Для их решения необходимо задать начальные значения 
. Эти начальные значения находим из требования эквивалентности условия (19) при 
, т.е. условия 
первому из условий (17), а именно . Таким образом, получаем
. (21)
Нахождение коэффициентов по формулам (20), (21) называется прямой прогонкой. После того как прогоночные коэффициенты , , найдены, решение системы (16), (17) находится по рекуррентной формуле (19), начиная с 
. Для начала счета по этой формуле требуется знать 
, которое определяется из уравнений
, 
,
откуда
.
Нахождение по формулам
, 
, (22)
(23)
называется обратной прогонкой. Алгоритм решения системы (16), (17), определяемый по формулам (20)-(23), называется методом прогонки.
Метод прогонки можно применить, если знаменатели выражений (20) и (23) не обращаются в нуль. Покажем, что для возможности применения метода прогонки достаточно потребовать, чтобы коэффициенты системы (16), (17) удовлетворяли условиям
, , 
, , (24)
, 
. (25)
Сначала докажем по индукции, что при условиях (24), (25) модули прогоночных коэффициентов 
, 
не превосходят единицы. Согласно (21), (25) имеем 
. Предположим, что 
для некоторого и докажем, что 
. Из оценок
и условий (24) получаем
,
т.е. знаменатели выражений (20) не обращаются в нуль. Более того,
.
Следовательно, , . Далее, учитывая второе из условий (25) и только что доказанное неравенство 
, имеем
,
т.е. не обращается в нуль и знаменатель в выражении для .
К аналогичному выводу можно прийти и в том случае, когда условия (24), (25) заменяются условиями
, , 
, , (26)
, 
. (27)
В этом случае из предположения следует
, 
,
т.е. все прогоночные коэффициенты, начиная со второго, по модулю строго меньше единицы. При этом 
.
Таким образом, при выполнении условий (24), (25) (так же как и условий (26), (27)) система (16), (17) эквивалентна системе (20) – (23). Поэтому условия (24), (25) или условия (26), (27) гарантируют существование и единственность решения системы (16), (17) и возможность нахождения этого решения методом прогонки. Кроме того, доказанные неравенства , , обеспечивают устойчивость счета по рекуррентным формулам (22), (23). Последнее означает, что погрешность, внесенная на каком-либо шаге вычислений, не будет возрастать при переходе к следующим шагам. Действительно, пусть в формуле (22) при 
вместо 
вычислена величина 
. Тогда на следующем шаге вычислений, т.е. при 
вместо 
получим величину 
и погрешность окажется равной
Отсюда получим, что 
, т.е. погрешность не возрастает.
