Для построения многочлена Ньютона по формуле (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 | Разделенная разность | ||||
| 0-го пор. | 1-го пор. | 2-го пор. | 3-го пор. | |||
| 0 | 2 | 0,693147 | ||||
| 0,405466 | ||||||
| 1 | 3 | 1,098613 | -0,058892 | |||
| 0,287682 | 0,00887416 | |||||
| 2 | 4 | 1,386295 | -0,0322695 | |||
| 0,223143 | ||||||
| 3 | 5 | 1,60943 | ||||
Интерполяционный многочлен Ньютона для заданной табличной функции имеет вид:
Далее полученный интерполяционный многочлен Ньютона можно привести к нормальному виду
и использовать его для решения задач интерполирования или прогноза.
Сплайн-интерполяция
Сплайны стали широко использоваться в вычислительной математике сравнительно недавно. В машиностроительном черчении они применяются уже давно, так как сплайны - это лекала или гибкие линейки, деформация которых позволяет провести кривую через заданные точки (xi, уi).
Используя теорию изгиба бруса при малых деформациях, можно показать, что сплайн - это группа кубических многочленов, в местах сопряжения которых первая и вторая производные непрерывны. Такие функции называются кубическими сплайнами. Для их построения необходимо задать коэффициенты, которые единственным образом определяют многочлен в промежутке между данными точками.
Например, для некоторых функций (рис.11.5) необходимо задать все кубические функции q1(x), q2(x),:qn(x).
В наиболее общем случае эти многочлены имеют вид:
где kij - коэффициенты, определяемые описанными ранее условиями, количество которых равно 4n. Для определения коэффициентов kij необходимо построить и решить систему порядка 4n.
Рис. 11.5.
Первые 2п условий требуют, чтобы сплайны соприкасались в заданных точках:
Следующие (2п-2) условий требуют, чтобы в местах соприкосновения сплайнов были равны первые и вторые производные:
Система алгебраических уравнений имеет решение, если число уравнений соответствует числу неизвестных. Для этого необходимо ввести еще два уравнения. Обычно используются следующие условия:
При построении алгоритма метода первые и вторые производные удобно аппроксимировать разделенными разностями соответствующих порядков.
Полученный таким образом сплайн называется естественным кубическим сплайном. Найдя коэффициенты сплайна, используют эту кусочно-гладкую полиноминальную функцию для представления данных при интерполяции.
