Формула Ньютона является другой классической формулой для построения интерполяционного многочлена. Она позволяет получить уникальный многочлен степени $n$, проходящий через заданный набор $(n+1)$ узловых точек $(x_k, y_k),{}_{k \in \left\{0, ..., n\right\}}$:
$$P(x) = f[x_0] + f[x_0,x_1](x-x_0) + f[x_0,x_1,x_2](x-x_0)(x-x_1) + \cdots + f[x_0, x_1, ..., x_n](x-x_0)(x-x_1)\cdots(x-x_{n-1})$$или
$$P(x) = \sum_{i=0}^n{\left(f[x_0, ..., x_i] \cdot \prod_{j=0}^{i-1}{(x-x_j)}\right)}$$, где:
- $x_i$ — координаты узловых точек,
- $y_i$ — значения функции в этих точках,
- $f[...]$ = разделённые разности.
Разделённые разности $f[...]$ вычисляются по формуле
$$f[x_j, x_{j+1}, ..., x_{k-1}, x_k] = \frac{f[x_{j+1}, ..., x_{k-1}, x_k] - f[x_j, x_{j+1}, ..., x_{k-1}]}{x_k-x_j}$$с начальными условиями $f[x_j] = y_j$.
Ссылки #
- Jean-Paul Berrut and Lloyd N. Trefethen, Barycentric Lagrange Interpolation, SIAM Review, Vol. 46, No. 3, pp. 501–517, 2004.