МЧА: Лекция 2. Интерполяционные формулы Ньютона

Теорема о существовании интерполяционного многочлена.
Первая интерполяционная формула Ньютона.
Вторая интерполяционная формула Ньютона.
Примеры решения задач

1 Теорема о существовании интерполяционного многочлена

Пусть на отрезке $[a,b]$ в $n+1$ узле $x_k = x_0 + kh \ (k = 0,1,2,...,n)$ заданы значения ограниченной функции $f(x)$ : $y_0 = f(x_0), y_1 = f(x_1), y_2 = f(x_2), ... , y_n = f(x_n)$ . Поставим задачу нахождения полинома $P_n(x)$ степени не $n$ выше такого, чтобы выполнялось условие

$f(x_i) = P_n(x_i), \ i = 0,1,...,n.\ \ \$ (1.10)

Теорема 1. Существует и притом единственный многочлен степени не выше $n$ , для которого выполняется условие (1.10).

Доказательство. Пусть многочлен $P_n(x)$ имеет вид (1.3). Используя (1.10) для определения коэффициентов $a_i$ , получим систему (1.4) линейных алгебраических уравнений, которую запишем в виде

$ \begin{matrix} a_0 x_0^n + a_1 x_0^{n-1} + a_2 x_0^{n-2} + ... + a_n = f(x_0),\ a_0 x_1^n + a_1 x_1^{n-1} + a_2 x_1^{n-2} + ... + a_n = f(x_1),\ ...................................................................... \ a_0 x_n^n + a_1 x_n^{n-1} + a_2 x_n^{n-2} + ... + a_n = f(x_n), \end{matrix} $ $\qquad \qquad \qquad \ \ \ \$ (1.11)

Определитель системы (1.11) является определителем Вандермонда и имеет вид

$D = \prod_{ i, j=0 \ i>j}^n(x_i - x_j) \neq 0$ .

Следовательно, для системы различных между собой узлов система (1.11) имеет единственное решение. Теорема доказана.

2 Первая интерполяционная формула Ньютона

Очевидно, что условие (1.10) эквивалентно условию

$\Delta^m P_n(x_0) = \Delta^m y_0, \quad m = 1,2,...,n. \qquad \qquad$ (1.12)

Будем искать интерполяционный полином в виде

$P_n(x) = a_0 + a_1(x - x_0) + ... + a_n(x - x_0) \cdot (x - x_1) \cdot \ldots \cdot (x - x_{n-1}). \qquad \qquad$ (1.13)

Значения коэффициентов $a_0, a_1, ... , a_n$ находим из условия совпадения значений исходной функции и многочлена в узлах. Полагая $x = x_0$ из (1.13) найдем $P_n(x_0) = y_0 = a_0$ . Далее, последовательно придавая $x$ значения $x_1$ и $x_2$ получаем,

$y_1 = P_n(x_1) = a_0 + a_1(x_1 - x_0) = a_0 + a_1 h, \ y_2 = P_n(x_2) = a_0 + a_1 (x_2 - x_0) + a_2(x_2 - x_0)(x_2 - x_1) = a_0 + a_1 2 h + a_2 2 h^2$

Откуда, применяя (1.12), для коэффициента $a_1$ получим выражение $a_1 = \frac {\Delta y_0}{1! h}$ , а для $a_2$ - $a_2 = \frac {\Delta^2 y_0}{2! h^2}$ .(из учебника "Численные методы на базе Mathcad")

Продолжая наши рассуждения, запишем формулу для любого $a_i$ : $a_i = \frac {\Delta^i y_0}{i! h^i}$ . Подставляя в (1.13) выражения для коэффициентов $a_i$ через конечные разности, получим первую интерполяционную формулу Ньютона

$P_n(x) = y_0 + \frac {\Delta y_0}{1! h} (x- x_0) + ... + \frac {\Delta^n y_0}{n! h^n}(x-x_0)(x - x_1) \cdot ... \cdot (x - x_{n-1}). \qquad \qquad$ (1.14)

При $h \rightarrow 0$ справедливы следующие пределы

$\lim_{h \rightarrow 0} \frac{\Delta^k y_0}{h^k} = \left ( \frac {d^k y}{dx^k} \right )_{x=x_0} = y^{(k)}(x_0), \ \lim_{h \rightarrow 0} (x - x_0) \cdot ... \cdot (x - x_{n-1}) = (x - x_0)^n$ .

Отсюда следует, что при $h \rightarrow 0$ интерполяционный полином (1.14) принимает вид полинома Тейлора

$P_n(x) = y(x_0) + y^{(1)}(x_0)(x - x_0) + \frac {y^{(2)}(x_0)}{2!} (x - x_0)^2 + ... + \frac {y^{ \left ( n \right ) }(x_0)}{n!} (x - x_0)^n$ .

Для практический целей формулу Ньютона (1.14) удобнее записывать в несколько ином виде. Введем переменную $q = \frac {x - x_0}{h}$ . Тогда $x - x_0 = qh$ . Таким образом, для полинома $P_n(x)$ получим выражение

$P_n(x(q)) = y_0 + q \Delta y_0 + \frac {q(q-1)}{2!} \Delta^2 y_0 + ... + \frac {q(q-1)(q-2)...(q-n+1)}{n!} \Delta^n y_0. \qquad \qquad$ (1.15)

Формулу (1.15) выгодно использовать для интерполирования в окрестности начального значения $x_0$ . Поэтому ее часто называют формулой для интерполирования вперед. В этой формуле из таблицы конечных разностей используются $\Delta^k f_0$ верхней диагонали.

Остаточный член в формуле (1.15) имеет вид

$R_n(x) = h^{n+1} \frac {q(q-1)...(q-n)}{(n+1)!}f^{(n+1)}(\xi)$ ,

где $\xi$ – некоторая внутренняя точка наименьшего промежутка, содержащего все узлы $x_i, \ i = 1,2,..., n$ и точку $x$ . При наличии дополнительного узла $x_{n+1}$ на практике пользуются более удобной приближенной формулой

$R_n(x) \approx \frac {\Delta^{n+1}y_0}{(n+1)!}q(q-1)...(q-n)$ .

При $n = 1$ из (1.15) получается формула линейного интерполирования

$P_1(x) = y_0 + q \Delta y_0$ .

При $n = 2$ из (1.15) имеет место формула параболического или квадратического интерполирования

$P_2(x) = y_0 + q \Delta y_0 + \frac {q(q-1)}{2!} \Delta^2 y_0$ .

3 Вторая интерполяционная формула Ньютона

Первая интерполяционная формула Ньютона практически неудобна для интерполирования функций в конце таблицы. Поэтому когда точка интерполирования лежит вблизи точки $x_n$ удобно пользоваться второй интерполяционной формулой Ньютона, которая имеет вид

$P_n(x) = y_n + \frac {\Delta y_n}{1! h}(x - x_n) + ... + \frac {\Delta^n y_n}{n! h^n}(x - x_n)(x - x_{n-1}) \cdot ... \cdot (x - x_1) . \qquad \qquad$ (1.16)

Вводя новую переменную $q = \frac {x-x_n}{h}$ , эту формулу перепишем в виде

$P_n(x(q)) = y_n + q \Delta y_{n-1} + \frac {q(q+1)}{2!} \Delta^2 y_{n-2}+ ... + \frac {q(q+1)(q+2)...(q+n-1)}{n!} \Delta^n y_0. \qquad \qquad$ (1.17)

В формуле (1.17) из таблицы конечных разностей используются $\Delta^k f_i$ нижней диагонали.

Остаточный член формулы (1.17) имеет вид

$R_n(x) = h^{n+1} \frac {q(q+1) ... (q+n)}{(n+1)!}f^{(n+1)}(\xi), \qquad \qquad \qquad \qquad$ (1.17')

где точка $\xi$ имеет тот же смысл, что и ранее.

Отметим, что формулы Ньютона используются и для экстраполирования функций. Если $\overline{x} < x_0$ , то для экстраполирования назад используют первую интерполяционную формулу Ньютона. Если $\overline{x} > x_0$ , то для экстраполирования вперед используют вторую интерполяционную формулу Ньютона. Следует заметить, что операция экстраполирования менее точна, чем операция интерполирования в узком смысле.

4 Примеры решения задач

Используя первую или вторую интерполяционную формулу Ньютона для равноотстоящих узлов интерполяции вычислить значение функции, заданной таблично в точке $x = C$ . Оценить погрешность интерполяционной формулы.

Построить таблицу данных из условия $y_i = x_i^4 + x_i^2 + \left ( 1 + \frac {10}{K} \right ), \ K = 13, \ x_0 = \frac {5}{K}, \ x_i = x_0 + i \cdot h, \ h = 0.2 \ (i = 1,2,3), \ C = 0.885$ .

Решение.

Поскольку точка $C$ лежит ближе к концу отрезка интерполирования и узлы $x_i$ – равноотстоящие, поэтому применяем вторую формулу Ньютона для равноотстоящих узлов (1.17) и учитываем, что $q = \frac {x - x_n}{h}$ .

Составляем таблицу конечных разностей :

$i$	$x$	$f$	$\Delta f$	$\Delta^2 f$	$\Delta^3 f$
0	0.385	1.93943	0.28915	0.24747	0.13152
1	0.585	2.22857	0.53662	0.37899
2	0.785	2.76519	0.9156
3	0.985	3.68079