插值 是指在一系列已知数值中，对两个已知值之间的数值进行估算的过程。当我们面对的数值序列其间隔差并不完全相同时，牛顿均差插值公式 便是一种非常实用的插值技术。假设 $f(x0), f(x1), f(x2)………f(xn)$ 是函数 $y=f(x)$ 分别对应自变量 $x=x0, x1, x_2…xn$ 的 $(n+1)$ 个值，且这些自变量之间的间隔并不相同。那么，一阶均差定义如下
f[x_0, x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0}
二阶均差定义如下
f[x_0, x_1, x_2]=\frac{f[x_1, x_2]-f[x_0, x_1]}{x_2-x_0}
以此类推… 均差具有关于自变量的对称性，即均差的大小与自变量的排列顺序无关。 因此，$f[x0, x1]=f[x1, x0]$， $f[x0, x1, x2]=f[x2, x1, x0]=f[x1, x2, x0]$。通过利用一阶均差、二阶均差等，我们可以构建一个表格，这个表格被称为均差表。均差表如下： !image
牛顿均差插值公式的优势
- 这些公式在插值计算中非常有用。
- 通过均差表，我们可以方便地计算出高阶差值。
- 每一阶段中各列的差值可以通过计算当前值与其紧邻的后继值之差轻松得出。
- 我们会连续计算 y 变量两个相邻值之间的差，直到最终差值消失或变为常数。
牛顿均差插值公式
> f(x)=f(x0)+(x-x0)f[x0, x1]+(x-x0)(x-x1)f[x0, x1, x2]+……………………..+(x-x0)(x-x1)…(x-xk–1)f[x0, x1, x2…xk]
示例：
> 输入： 求 x=7 处的值
> 输出： x=7 处的值为 13.47
下面让我们来看看牛顿均差插值法的具体实现。
C++
CODEBLOCK_d878130f
Java
// Java program for implementing
// Newton divided difference formula
import java.text.*;
import java.math.*;
class GFG{
// Function to find the product term
static float proterm(int i, float value, float x[])
{
float pro = 1;
for (int j = 0; j < i; j++) {
pro = pro * (value – x[j]);
}
return pro;
}
// Function for calculating
// divided difference table
static void dividedDiffTable(float x[], float y[][], int n)
{
for (int i = 1; i < n; i++) {
for (int j = 0; j < n – i; j++) {
y[j][i] = (y[j][i – 1] – y[j + 1]
[i – 1]) / (x[j] – x[i + j]);
}
}
}
// Function for applying Newton‘s
// divided difference formula
static float applyFormula(float value, float x[],
float y[][], int n)
{
float sum = y[0][0];
for (int i = 1; i < n; i++) {
sum = sum + (proterm(i, value, x) * y[0][i]);
}
return sum;
}
// Function for displaying
// divided difference table
static void printDiffTable(float y[][],int n)
{
DecimalFormat df = new DecimalFormat("#.####");
df.setRoundingMode(RoundingMode.HALF_UP);
for (int i = 0; i < n;