Для построения многочлена Ньютона по формуле (11.7) организуем циклический вычислительный процесс по . При этом на каждом шаге поиска находим разделенные разности k-го порядка. Будем помещать разделенные разности на каждом шаге в массив Y.
Тогда рекуррентная формула (11.8) будет иметь вид:
(11.9) |
В формуле Ньютона (11.7) используются разделенные разности k-го порядка, подсчитанные только для участков [x0, x0+k], т.е. разделенные разности k-го порядка для i=0. Обозначим эти разделенные разности k-го порядка как у0. А разделенные разности, подсчитанные для I > 0, используются для расчетов разделенных разностей более высоких порядков.
Используя (11.9), свернем формулу (11.7). В результате получим
(11.10) |
где
у0 - значение табличной функции (11.1) для x=x0.
- разделенная разность k-го порядка для участка [x0, x0+k].
Для вычисления Р удобно использовать рекуррентную формулу P = P(x - xk-1) внутри цикла по k.
Схема алгоритма интерполяции по Ньютону представлена на рис.11.4.
Рис. 11.4. Схема алгоритма интерполяции по Ньютону
Пример интерполяции по Ньютону
Дана табличная функция:
i | xi | yi |
0 | 2 | 0,693147 |
1 | 3 | 1,098613 |
2 | 4 | 1, 986295 |
3 | 5 | 1,609438 |
Вычислить разделенные разности 1-го, 2-го, 3-го порядков (n=3) и занести их в диагональную таблицу.
Разделенные разности первого порядка:
Разделенные разности второго порядка:
Разделенная разность третьего порядка:
Таблица 11.1. Диагональная таблица разделенных разностей | ||||||
i | xi | Разделенная разность |