Loading [MathJax]/extensions/TeX/AMSmath.js
RMVL  
Robotic Manipulation and Vision Library
全部  命名空间 文件 函数 变量 类型定义 枚举 枚举值 宏定义  
函数插值方法

Lagrange 插值Newton 插值 两种基函数选取方式介绍函数插值

作者
赵曦
日期
2024/01/11
版本
1.0

上一篇教程:光源控制器
下一篇教程:最小二乘法


1. Lagrange 插值多项式

一般对于一个未知函数,若能从已知的一系列点近似地使用多项式函数 p(x)代替原函数 f(x),并且满足

p(x_i)=f(x_i)=y_i\tag{1-1}

p(x)称为插值多项式。

也就是说, p(x)可以表示成多项式 \mathbb P[x]_n的形式,即

p(x)=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}\tag{1-2}

对于 n个点,我们可以列出如下表格

\begin{array}{c|cc}x&x_1&x_2&x_3&\cdots&x_n\\\hline f(x)&y_1&y_2&y_3&\cdots&y_n\end{array}

根据 \text{(1-1)},将 n个点分别代入 p(x),可以得到

\left\{\begin{align} p(x_1)&=a_0+a_1x_1+a_2x_1^2+\cdots+a_{n-1}x_1^{n-1}=f(x_1)=y_1\\ p(x_2)&=a_0+a_1x_2+a_2x_2^2+\cdots+a_{n-1}x_2^{n-1}=f(x_2)=y_2\\ &=\qquad\qquad\vdots\\ p(x_n)&=a_0+a_1x_n+a_2x_n^2+\cdots+a_{n-1}x_n^{n-1}=f(x_n)=y_n \end{align}\right.\tag{1-3a}

要求解 a_0a_1\cdotsa_{n-1},可以将 \text{(1-3a)}改写成

X\boldsymbol a=\begin{bmatrix}1&x_1&\cdots&x_1^{n-1}\\1&x_2&\cdots&x_2^{n-1}\\\vdots&\vdots&\ddots& \vdots\\1&x_n&\cdots&x_n^{n-1}\end{bmatrix}\begin{bmatrix}a_0\\a_1\\\vdots\\a_{n-1}\end{bmatrix}= \begin{bmatrix}y_1\\y_2\\\vdots\\y_n\end{bmatrix}=\boldsymbol f\tag{1-3b}

我们选取的一组基是 \left(1,x,x^2,\cdots,x^n\right),在这里系数矩阵 X是个 Vandermonde 矩阵,求解起来比较复杂。希望寻找一组合适的基,使得 \boldsymbol a的求解比较简单,如果在某组基 (l_0(x),l_1(x),l_2(x),\cdots,l_{n-1}(x))下,系数矩阵 X变为单位矩阵,即 X=I,此时 \boldsymbol a=\boldsymbol f,此时插值多项式就可以写为

p(x)=y_1l_0(x)+y_2l_1(x)+y_3l_2(x)+\cdots+y_nl_{n-1}(x)\tag{1-4}

要使得 X=I,也就是需要满足

l_i(x_j)=\left\{\begin{align}1,\quad i=j\\0,\quad i\neq j\end{align}\right.\tag{1-5}

可以取

l_i(x)=\prod\limits_{j=0,j\neq i}^{n-1}\frac{x-x_j}{x_i-x_j}=\frac{(x-x_0)(x-x_1)\cdots(x-x_{i-1})(x-x_{i+1})\cdots(x-x_{n-1})}{(x_i-x_0)(x_i-x_1)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_{n-1})}\tag{1-6}

这就是 Lagrange 插值基函数, \text{(1-4)}被称为 Lagrange 插值多项式。

示例

使用以下节点进行二次插值

\begin{array}{c|ccc}x&1&2&3\\\hline f(x)&2&1&2\end{array}

解答

\begin{align} l_0(x)&=\prod\limits_{j=0,j\neq0}^2\frac{x-x_j}{x_i-x_j}=\frac{(x-2)(x-3)}{(1-2)(1-3)}=\frac12(x-2)(x-3)\\ l_1(x)&=\prod\limits_{j=0,j\neq1}^2\frac{x-x_j}{x_i-x_j}=\frac{(x-1)(x-3)}{(2-1)(2-3)}=-(x-1)(x-3)\\ l_2(x)&=\prod\limits_{j=0,j\neq2}^2\frac{x-x_j}{x_i-x_j}=\frac{(x-1)(x-2)}{(3-1)(3-2)}=\frac12(x-1)(x-2)\\ \end{align}

因此,得到:

\begin{align}p(x)&=y_1l_0(x)+y_2l_1(x)+y_3l_2(x)\\&=(x-2)(x-3)-(x-1)(x-3)+(x-1)(x-2)\\&=x^2-4x+5\end{align}

注解
一般的, nn次插值得到的插值多项式是唯一的,读者可以自行使用待定系数法验证

2. Newton 插值多项式

相关类 rm::Interpolator

Lagrange 插值基函数存在一些问题,比如当我们需要在原先节点的基础上再次增加若干个节点,这会导致之前计算出的基函数全部失效,需要重新计算。为此我们需要引入新的插值基函数,这里使用 Newton 插值基函数来避免这一问题。

Newton 插值基函数的表达式如下

l_i(x)=\left\{\begin{array}{lr}1&i=0\\\prod\limits_{j=0}^{i-1}(x-x_j)&i\neq0\end{array}\right.\tag{2-1}

Newton 插值多项式可以写为以下形式

p(x)=a_0l_0(x)+a_1l_1(x)+a_2l_2(x)+\cdots+a_{n-1}l_{n-1}(x)\tag{2-2}

其中插值系数 a_i\ (i=0,1,2,\cdots,n-1)表示为

\begin{align}a_0&=f\left(x_0\right)\\a_1&=f\left[x_0,x_1\right]=\frac{f(x_0)-f(x_1)}{x_0-x_1}\\ a_2&=f\left[x_0,x_1,x_2\right]=\frac{f\left[x_0,x_1\right]-f\left[x_1,x_2\right]}{x_0-x_2}\\ &\ \vdots\\a_{n-1}&=f\left[x_0,x_1,\cdots,x_{n-1}\right]\end{align}\tag{2-3}

示例

使用以下节点进行 3 次插值

\begin{array}{c|cccc}x&0&1&2&3\\\hline f(x)&0&1&3&2\end{array}

解答

列差商表

\begin{array}{c|cc}x&f(x)&1阶&2阶&3阶\\\hline0&0\\1&1&\frac{1-0}{1-0}=1\\2&3&\frac{3-1}{2-1}=2&\frac{2-1} {2-0}=\frac12\\3&2&\frac{2-3}{3-2}=-1&\frac{-1-2}{3-1}=-\frac32&\frac{-\frac32-\frac12}{3-0}=-\frac23\\\end{array}

可以得到

\begin{align}p(x)&=0+x+\frac12x(x-1)-\frac23x(x-1)(x-2)\\&=-\frac23x^3+\frac52x^2-\frac56x\end{align}