2. Разностные уравнения первого порядка
Предположим, что надо вычислить сумму
(1)
Вычисления обычно
организуются следующим образом. Задается
начальное значение
и затем последовательно, начиная с
,
находятся числа
,
связанные рекуррентным соотношением
,
,
.
(2)
Для численного произведения
(3)
достаточно задать
начальное значение
и воспользоваться рекуррентными
соотношениями
,
,
.
(4)
Уравнения (2) и (4) являются частными случаями линейного разностного уравнения первого порядка.
,
,
(5)
где
заданные
числа,
искомые
числа. Для уравнения (5) рассматривается
задача с начальными условиями или задача
Коши, которая состоит в отыскании всех
,
,
при заданном начальном значении
.
Ясно, что решение задачи Коши для
уравнения (5) существует и единственно.
Запишем решение
уравнения (5) в явном виде. Подставляя в
(5) вместо
выражение
,
получим
.
Теперь можно
подставить сюда выражение для
и т.д. В результате получим формулу
(доказать и
расписать)
,
.
,
(6)
где
(7)
Строго доказать
формулу (6) можно индукцией по числу
при каждом фиксированном
.
Нам потребуется формула (6) при
,
т.е.
,
.
,
(8)
где, согласно (7)
(9)
В частности, если
(5) является уравнением с постоянными
коэффициентами, т.е.
для всех
,
то из (8) получим
,
.
(10)
Явную формулу (8)
можно использовать для получения оценок
решения
через начальные данные
,
заданные коэффициенты
и правые части
.
Лемма
1. Если
для некоторого
выполнены неравенства
,
,
(11)
то для решения уравнения (5) справедливы оценки
,
.
(12)
Доказательство. Из (9) и (11) получаем, что
,
.
Отсюда и из (8) следуют оценки (12).
2. Разностные уравнения второго порядка
Рассмотрим теперь линейные разностные уравнения второго порядка
,
,
(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)
при
вместо
вычислена величина
.
Тогда на следующем шаге вычислений,
т.е. при
вместо
получим величину
и погрешность окажется равной
Отсюда получим,
что
,
т.е. погрешность не возрастает.
-