牛顿插值算法

差商定义

称 f [ x₀ , x_k ] = ( f ( x_k ) - f ( x₀ ) ) / ( x_k - x₀ )为函数f(x)关于点x₀,x_k的一阶差商（或者均差）

0阶差商

f[x₀] = f(x₀)
f[x₁] = f(x₁)
...
f[x_k] = f(x_k)

二阶差商

f [x₀ , x₁ , x₂] = ( f [ x₁ , x₂ ] - f [ x₀ , x₁ ] ) / (x₂ - x₀)

K阶差商

f [x₀ , x₁ , ..., x_k] = ( f [ x₁ ,..., x_k-1 ,x_k] - f [ x₀ , x₁,...,x_k-1 ] ) / (x_k - x₀)

注意导数称为微商

差商的性质

f(x)的k阶差商f [x₀ , x₁ , ..., x_k]是函数值f(x₀),f(x₁),...,f(x_k)的线性组合

image.png

证明：
当k=1时

image.png

当k=2时

image.png

假设当k = n时也成立

image.png

牛顿插值法

构造多项式,经过n个点，可以找到一条n-1阶的方程

image.png

这个时候就需要已知条件，P_n(x_i) =f_i(x_i)(i=0,1,2,...,n)
当x = x₀时，P_n(x₀) = a₀ = f₀= f[x₀]
当x = x₁时，P_n(x₁) = f₁ = a₀ +a₁(x₁-x₀) = a₀+a₁(x₁ - x₀)
当x = x₂时，P_n(x₂) = f₂ = a₀ +a₁(x₂-x₀) + a₂(x₂-x₀)(x₂-x₁)
此时
a₀ =f[x₀]
a₁ = ( f₁ - f₀) / (x₁ - x₀) = f[x₀,x₁]
归纳出

a₀ =f[x₀]
a₁ =f[x₀,x₁]
a₂ =f[x₀,x₁,x₂]

image.png