Метод конечных разностей

Материал из Википедии — свободной энциклопедии

Метод конечных разностей — широко-известный и простейший метод интерполяции. Его суть заключается в замене дифференциальных коэффициэнтов уравнения на разностные коэффициэнты^[1], что позволяет свести решение дифференциального уравнения к решению его разностного аналога.

Последнее может быть иллюстрировано небольшим примером:

Рассмотрим квадратичный многочлен p(x) = 2x² − 3x + 2 и предположим, что мы знаем его табличные значения p(0), p(0,1), p(0,2), p(0,3), p(0,4) и т. д. В представленной ниже таблице первая колонка содержит табличные значения полинома, вторая — разность между двумя верхними соседними значениями из первой колонки, а третья — разность между двумя соседями из второй колонки:

p(0)=2,0
	2,0−1,72=0,28
p(0,1)=1,72		0,28−0,24=0,04
	1,72−1,48=0,24
p(0,2)=1,48		0,24−0,20=0,04
	1,48−1,28=0,20
p(0,3)=1,28		0,20−0.16=0.04
	1,28−1,12=0,16
p(0,4)=1,12

Заметим, что значения в третьем столбце — одинаковы. Это не случайность. Фактически, если мы начинаем таблицу для любого полинома степени n, колонка с номером n + 1 будет всегда содержать константу. Этот решающий факт делает работоспособным указанный метод.

Мы составляли таблицу слева-направо, но точно также её можно рассчитать и справа-налево, вычислив, таким образом, недостающие значения полинома.

Для вычисления p(0,5) мы воспользуемся значениями самой нижней диагонали. Начиная с самого нижнего значения в последней колонке 0.04. Затем продолжим вторую колонку вычтя 0,04 из 0,16 и получив значение 0,12. Таким же образом мы заполним первую колонку, вычитая из её нижнего значения 1,12 полученное нами на предыдущем шаге число 0,12 из второй колонки. p(0,5) будет равным 1,12-0,12 = 1,0. Для вычисления p(0,6) используется тот же самый алгоритм: берётся 0,04 из третьей колонки, вычитается из нижнего значения (теперь уже 0,12) во второй колонке, получившееся 0,08 прописывается в нижнюю часть второй колонки и затем вычитается из нижнего значения в первой колонке (как мы помним — 1,0). Результат — 0,92 является значением p(0,6).

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