拉格朗日插值

拉格朗日插值

一，介绍

　　学过FFT的人都应该知道什么叫做插值，插值的意思就是说将一个多项式从点值表达转变成系数表达。

　　在FFT的插值中为什么可以做到n log n，是因为单位复数根的关系。

　　那对于普通的插值应该怎么办呢？解方程是一种方法，但是这个在计算机中十分不现实。

　　所以有许多种插值的方法，其中比较普及的就是拉格朗日插值。

二，定义

　　　对某个多项式函数，已知有给定的k + 1个取值点：

$(x_{0},y_{0}),ldots ,(x_{k},y_{k})$

　　　其中 $x_{j}$ 对应着自变量的位置，而 $y_{j}$ 对应着函数在这个位置的取值。

　　　假设任意两个不同的xj都互不相同，那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为：

$L(x):=sum _{{j=0}}^{{k}}y_{j}ell _{j}(x)$

　　　其中每个 $ell _{j}(x)$ 为拉格朗日基本多项式（或称插值基函数），其表达式为：

$ell _{j}(x):=prod _{{i=0,\,i eq j}}^{{k}}{frac {x-x_{i}}{x_{j}-x_{i}}}={frac {(x-x_{0})}{(x_{j}-x_{0})}}cdots {frac {(x-x_{{j-1}})}{(x_{j}-x_{{j-1}})}}{frac {(x-x_{{j+1}})}{(x_{j}-x_{{j+1}})}}cdots {frac {(x-x_{{k}})}{(x_{j}-x_{{k}})}}.$ [3]

　　　拉格朗日基本多项式 $ell _{j}(x)$ 的特点是在 $x_{j}$ 上取值为1，在其它的点 $x_{i},\,i eq j$ 上取值为0。

三，例子

　　　假设有某个二次多项式函数 $f$ ，已知它在三个点上的取值为：

　　　 $f(4)=10$ $f(5)=5.25$ $f(6)=1$

　　　要求 $f(18)$ 的值。

　　　首先写出每个拉格朗日基本多项式：

$ell _{0}(x)={frac {(x-5)(x-6)}{(4-5)(4-6)}}$

$ell _{1}(x)={frac {(x-4)(x-6)}{(5-4)(5-6)}}$

$ell _{2}(x)={frac {(x-4)(x-5)}{(6-4)(6-5)}}$

　　　然后应用拉格朗日插值法，就可以得到 $p$ 的表达式（ $p$ 为函数 $f$ 的插值函数）：

$p(x)=f(4)ell _{0}(x)+f(5)ell _{1}(x)+f(6)ell _{2}(x)$

$.\,\,\,\,\,\,\,\,\,\,=10cdot {frac {(x-5)(x-6)}{(4-5)(4-6)}}+5.25cdot {frac {(x-4)(x-6)}{(5-4)(5-6)}}+1cdot {frac {(x-4)(x-5)}{(6-4)(6-5)}}$
$.\,\,\,\,\,\,\,\,\,\,={frac {1}{4}}(x^{2}-28x+136)$

　　　此时代入数值 $18$ 就可以求出所需之值： $f(18)=p(18)=-11$ 。

四，证明唯一性

　　就是说n+1个点对应的n次多项式只有一个，这个需要证明，但是一般都会直接当成结论，所以不需要去记忆。

五，优点和缺点

　　拉格朗日插值法的公式结构整齐紧凑，在理论分析中十分方便，然而在计算中，当插值点增加或减少一个时，所对应的基本多项式就需要全部重新计算，

　　于是整个公式都会变化，非常繁琐[5]。这时可以用重心拉格朗日插值法或牛顿插值法来代替。此外，当插值点比较多的时候，拉格朗日插值多项式的次数

　　可能会很高，因此具有数值不稳定的特点，也就是说尽管在已知的几个点取到给定的数值，但在附近却会和“实际上”的值之间有很大的偏差（如右下图）[6]。

　　这类现象也被称为龙格现象，解决的办法是分段用较低次数的插值多项式。

【推广】免费学中医，健康全家人

原文地址：https://www.cnblogs.com/fengzhiyuan/p/8645246.html