线性插值、抛物插值、Lagrange插值 | 您所在的位置:网站首页 › 二次插值法的基本思想 › 线性插值、抛物插值、Lagrange插值 |
Lagrange(拉格朗日)插值法
Lagrange插值法是一种多项式插值方法。 1. 线性插值(两点插值或一次插值)线性插值就是通过两个采样点 ( x 0 , y 0 ) (x_0,y_0) (x0,y0)和 ( x 1 , y 1 ) (x_1,y_1) (x1,y1),作一直线 p 1 ( x ) p_1(x) p1(x)来近似代替 f ( x ) f(x) f(x)。根据插值条件(定义1),有 p 1 ( x 0 ) = y 0 , p 1 ( x 1 ) = y 1 p_1(x_0)=y_0, \quad p_1(x_1)=y_1 p1(x0)=y0,p1(x1)=y1 因此,可以写出直线 p 1 ( x ) p_1(x) p1(x)的以下两种表达式: (1)点斜式: p 1 ( x ) = y 0 + y 1 − y 0 x 1 − x 0 ( x − x 0 ) p_1(x)=y_0+\frac{y_1-y_0}{x_1-x_0}(x-x_0) p1(x)=y0+x1−x0y1−y0(x−x0) (2)对称式: p 1 ( x ) = x − x 1 x 0 − x 1 y 0 + x − x 0 x 1 − x 0 y 1 p_1(x)=\frac{x-x_1}{x_0-x_1}y_0+\frac{x-x_0}{x_1-x_0}y_1 p1(x)=x0−x1x−x1y0+x1−x0x−x0y1 在点斜式中, y 1 − y 0 x 1 − x 0 \frac{y_1-y_0}{x_1-x_0} x1−x0y1−y0即为差商,即当 x 1 → x 0 x_1\to x_0 x1→x0时,它就是 y 0 ′ y_0' y0′。将其代入点斜式方程中,可得到 p 1 ( x ) p_1(x) p1(x)的极限形式: p 1 ( x ) = y 0 + y 0 ′ ( x − x 0 ) p_1(x)=y_0+y_0'(x-x_0) p1(x)=y0+y0′(x−x0) 这就是一阶Taylor(泰勒)多项式。在这里, p 1 ( x ) p_1(x) p1(x)由两项组成:一项是x的零次多项式,另一项为x的一次多项式。 p 1 ( x ) p_1(x) p1(x)的这种组成形式就是后面将要介绍的Newton(牛顿)插值公式的形式。 在对称式中,若令 x − x 1 x 0 − x 1 = l 0 ( x ) , x − x 0 x 1 − x 0 = l 1 ( x ) (1) \frac{x-x_1}{x_0-x_1}=l_0(x), \quad \frac{x-x_0}{x_1-x_0}=l_1(x) \tag{1} x0−x1x−x1=l0(x),x1−x0x−x0=l1(x)(1) 则有 p 1 ( x ) = l 0 ( x ) ⋅ y 0 + l 1 ( x ) ⋅ y 1 (2) p_1(x)=l_0(x)·y_0+l_1(x)·y_1 \tag{2} p1(x)=l0(x)⋅y0+l1(x)⋅y1(2) (1)和(2)式就是线性插值公式。其中, l 0 ( x ) l_0(x) l0(x)和 l 1 ( x ) l_1(x) l1(x)是关于x的线性多项式,称之为插值基函数。它们在节点 x 0 x_0 x0和 x 1 x_1 x1处分别满足: l 0 ( x 0 ) = 1 , l 0 ( x 1 ) = 0 l 1 ( x 0 ) = 0 , l 1 ( x 1 ) = 1 l_0(x_0)=1, \quad l_0(x_1)=0 \\ l_1(x_0)=0, \quad l_1(x_1)=1 l0(x0)=1,l0(x1)=0l1(x0)=0,l1(x1)=1 于是,可得出重要结论:满足插值条件 p 1 ( x 0 ) = y 0 , p 1 ( x 1 ) = y 1 p_1(x_0)=y_0,p_1(x_1)=y_1 p1(x0)=y0,p1(x1)=y1的一次插值多项式 p 1 ( x ) p_1(x) p1(x),可用两个插值基函数 l 0 ( x ) l_0(x) l0(x)和 l 1 ( x ) l_1(x) l1(x)进行线性组合构造。即 p 1 ( x ) = l 0 ( x ) ⋅ y 0 + l 1 ( x ) ⋅ y 1 p_1(x)=l_0(x)·y_0+l_1(x)·y_1 p1(x)=l0(x)⋅y0+l1(x)⋅y1 2. 抛物插值(三点插值或二次插值)抛物插值就是通过3个采样点 ( x 0 , y 0 ) , ( x 1 , y 1 ) (x_0,y_0),(x_1,y_1) (x0,y0),(x1,y1)和 ( x 2 , y 2 ) (x_2,y_2) (x2,y2)构造一个二次多项式 p 2 ( x ) p_2(x) p2(x)来近似代替 f ( x ) f(x) f(x)。根据插值条件(定义1),有: p 2 ( x ) = y , ( i = 0 , 1 , 2 ) p_2(x)=y, \quad(i=0,1,2) p2(x)=y,(i=0,1,2) 因此,根据插值条件,用待定系数法可以确定出二次多项式 p 2 ( x ) = a 0 + a 1 x + a 2 x 2 p_2(x)=a_0+a_1x+a_2x^2 p2(x)=a0+a1x+a2x2的各个系数。这里为避免解方程组,使用基函数线性组合的构造方法来求二次多项式 p 2 ( x ) p_2(x) p2(x)。由线性插值的结论推广可知。该二次多项式 p 2 ( x ) p_2(x) p2(x)可用3个插值基函数 l 0 ( x ) , l 1 ( x ) l_0(x),l_1(x) l0(x),l1(x)和 l 2 ( x ) l_2(x) l2(x)进行线性组合构造。即: p 2 ( x ) = l 0 ( x ) ⋅ y 0 + l 1 ( x ) ⋅ y 1 + l 2 ( x ) ⋅ y 2 (3) p_2(x)=l_0(x)·y_0+l_1(x)·y_1+l_2(x)·y_2 \tag{3} p2(x)=l0(x)⋅y0+l1(x)⋅y1+l2(x)⋅y2(3) 3个插值基函数在插值节点 x 0 , x 1 x_0,x_1 x0,x1和 x 2 x_2 x2处应该分别满足: l 0 ( x 0 ) = 1 l 0 ( x 1 ) = 0 l 0 ( x 2 ) = 0 l 1 ( x 0 ) = 0 l 1 ( x 1 ) = 1 l 1 ( x 2 ) = 0 l 2 ( x 0 ) = 0 l 2 ( x 1 ) = 0 l 2 ( x 2 ) = 1 l_0(x_0)=1 \quad l_0(x_1)=0 \quad l_0(x_2)=0 \\ l_1(x_0)=0 \quad l_1(x_1)=1 \quad l_1(x_2)=0 \\ l_2(x_0)=0 \quad l_2(x_1)=0 \quad l_2(x_2)=1 l0(x0)=1l0(x1)=0l0(x2)=0l1(x0)=0l1(x1)=1l1(x2)=0l2(x0)=0l2(x1)=0l2(x2)=1 即只要确定出3个插值基函数即可。 根据 l 0 ( x 1 ) = l 0 ( x 2 ) = 0 l_0(x_1)=l_0(x_2)=0 l0(x1)=l0(x2)=0,可假设 l 0 ( x ) = C ( x − x 1 ) ( x − x 2 ) l_0(x)=C(x-x_1)(x-x_2) l0(x)=C(x−x1)(x−x2);将 l 0 ( x 0 ) = 1 l_0(x_0)=1 l0(x0)=1代入,得: C ( x 0 − x 1 ) ( x 0 − x 2 ) = 1 C(x_0-x_1)(x_0-x_2)=1 C(x0−x1)(x0−x2)=1 即 C = 1 ( x 0 − x 1 ) ( x 0 − x 2 ) C=\frac{1}{(x_0-x_1)(x_0-x_2)} C=(x0−x1)(x0−x2)1 所以 l 0 ( x ) = ( x − x 1 ) ( x − x 2 ) ( x 0 − x 1 ) ( x 0 − x 2 ) (4) l_0(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)} \tag{4} l0(x)=(x0−x1)(x0−x2)(x−x1)(x−x2)(4) 同理 l 1 ( x ) = ( x − x 0 ) ( x − x 1 ) ( x 2 − x 0 ) ( x 2 − x 1 ) (5) l_1(x)=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)} \tag{5} l1(x)=(x2−x0)(x2−x1)(x−x0)(x−x1)(5) l 2 ( x ) = ( x − x 0 ) ( x − x 1 ) ( x 2 − x 0 ) ( x 2 − x 1 ) (6) l_2(x)=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)} \tag{6} l2(x)=(x2−x0)(x2−x1)(x−x0)(x−x1)(6) 这样,由(3)、(4)、(5)和(6)式就构成了抛物插值公式。即: p 2 ( x ) = ( x − x 1 ) ( x − x 2 ) ( x 0 − x 1 ) ( x 0 − x 2 ) ⋅ y 0 + ( x − x 0 ) ( x − x 1 ) ( x 1 − x 0 ) ( x 1 − x 2 ) ⋅ y 1 + ( x − x 0 ) ( x − x 1 ) ( x 2 − x 0 ) ( x 2 − x 1 ) ⋅ y 2 p_2(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}·y_0 + \frac{(x-x_0)(x-x_1)}{(x_1-x_0)(x_1-x_2)}·y_1+\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}·y_2 p2(x)=(x0−x1)(x0−x2)(x−x1)(x−x2)⋅y0+(x1−x0)(x1−x2)(x−x0)(x−x1)⋅y1+(x2−x0)(x2−x1)(x−x0)(x−x1)⋅y2 所以,抛物插值公式由3个二次插值基函数线性组合而成。 3. Lagrange插值Lagrange插值法就是通过多个采样点 ( x i , y i ) ( i = 0 , 1 , 2 , ⋯ , n ) (x_i,y_i)(i=0,1,2,\cdots,n) (xi,yi)(i=0,1,2,⋯,n)构造一个高次多项式 p ( x ) p(x) p(x)来近似代替 f ( x ) f(x) f(x)。关于插值节点数和多项式次数之间的关系,有如下定理: 定理1:在 n + 1 n+1 n+1个互异的插值节点 x 0 , x 1 , x 2 , ⋯ , x n x_0,x_1,x_2,\cdots,x_n x0,x1,x2,⋯,xn上,满足插值条件定义1式并且次数不高于n的代数多项式 p n ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 p_n(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0 pn(x)=anxn+an−1xn−1+⋯+a1x+a0存在且惟一。 证明:根据插值条件,有: { p n ( x 0 ) = a 0 + a 1 x 0 + a 2 x 0 2 + ⋯ + a n x 0 n = y 0 p n ( x 1 ) = a 0 + a 1 x 1 + a 2 x 1 2 + ⋯ + a n x 1 n = y 1 ⋮ p n ( x n ) = a 0 + a 1 x n + a 2 x n 2 + ⋯ + a n x n n = y n \begin{cases} p_n(x_0)=a_0+a_1x_0+a_2x_0^2+\cdots+a_nx_0^n=y_0 \\ p_n(x_1)=a_0+a_1x_1+a_2x_1^2+\cdots+a_nx_1^n=y_1 \\ \vdots \\ p_n(x_n)=a_0+a_1x_n+a_2x_n^2+\cdots+a_nx_n^n=y_n \end{cases} ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧pn(x0)=a0+a1x0+a2x02+⋯+anx0n=y0pn(x1)=a0+a1x1+a2x12+⋯+anx1n=y1⋮pn(xn)=a0+a1xn+a2xn2+⋯+anxnn=yn 该式是一个关于未知数 a 0 , a 1 , a 2 , ⋯ , a n a_0,a_1,a_2,\cdots,a_n a0,a1,a2,⋯,an的线性方程组,其系数矩阵的行列式是Vandermonde(范德蒙)行列式: V = ∣ 1 x 0 x 0 2 ⋯ x 0 n 1 x 1 x 1 2 ⋯ x 1 n ⋮ ⋮ ⋮ ⋮ ⋮ 1 x n x n 2 ⋯ x n n ∣ = ∏ n ≥ i > j ≥ 1 ( x i − x j ) V = \begin{vmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^n \\ 1 & x_1 & x_1^2 & \cdots & x_1^n \\ \vdots &\vdots &\vdots &\vdots &\vdots\\ 1 & x_n & x_n^2 & \cdots & x_n^n \end{vmatrix} = \prod_{n\geq i>j\geq1}(x_i-x_j) V=∣∣∣∣∣∣∣∣∣11⋮1x0x1⋮xnx02x12⋮xn2⋯⋯⋮⋯x0nx1n⋮xnn∣∣∣∣∣∣∣∣∣=n≥i>j≥1∏(xi−xj) 因为 x i ≠ x j ( i ≠ j ) x_i\neq x_j(i\neq j) xi=xj(i=j),所以 V ≠ 0 V\neq 0 V=0。根据Gramer法则,该线性方程组有惟一解 a 0 , a 1 , a 2 , ⋯ , a n a_0,a_1,a_2,\cdots,a_n a0,a1,a2,⋯,an,从而 p n ( x ) p_n(x) pn(x)存在且惟一。 根据定理1,由n+1个采样点可以惟一第构造出一个次数不高于n的插值多项式 p n ( x ) p_n(x) pn(x)。在构造该插值多项式时,同样采用基函数线性组合的构造方法。可认为该插值多项式 p n ( x ) p_n(x) pn(x)由n+1个插值基函数线性组合而成,其组合系数就是对应插值节点上的函数值 y i ( i = 0 , 1 , 2 , ⋯ , n ) y_i(i=0,1,2,\cdots,n) yi(i=0,1,2,⋯,n),即: p n ( x ) = l 0 ( x ) y 0 + l 1 ( x ) y 1 + ⋯ + l k ( x ) y k + ⋯ + l n ( x ) y n p_n(x)=l_0(x)y_0+l_1(x)y_1+\cdots+l_k(x)y_k+\cdots+l_n(x)y_n pn(x)=l0(x)y0+l1(x)y1+⋯+lk(x)yk+⋯+ln(x)yn 或 p n ( x ) = ∑ i = 0 n l i ( x ) y i (7) p_n(x)=\sum_{i=0}^nl_i(x)y_i \tag{7} pn(x)=i=0∑nli(x)yi(7) 在插值节点 x i x_i xi上,该多项式满足插值条件: p n ( x i ) = y i , ( i = 0 , 1 , 2 , ⋯ , k , ⋯ , n ) p_n(x_i)=y_i, \quad (i=0,1,2,\cdots,k,\cdots,n) pn(xi)=yi,(i=0,1,2,⋯,k,⋯,n) 因此,为了使插值条件成立,这n+1个插值基函数 l i ( x ) ( i = 0 , 1 , 2 , ⋯ , k , ⋯ , n ) l_i(x)(i=0,1,2,\cdots,k,\cdots,n) li(x)(i=0,1,2,⋯,k,⋯,n)在n+1个插值节点上必须分别满足: l i ( x k ) = { 0 , k ≠ i 1 , k = i l_i(x_k)=\begin{cases} 0, & k\neq i \\ 1, & k=i \end{cases} li(xk)={0,1,k=ik=i 因此,插值基函数 l i ( x ) l_i(x) li(x)有一个非零点 x i x_i xi和n个零点 x 0 , x 1 , ⋯ , x i − 1 , x i + 1 , x n x_0,x_1,\cdots,x_{i-1},x_{i+1},x_n x0,x1,⋯,xi−1,xi+1,xn,即可设 l i ( x ) = ( x − x 0 ) ( x − x i ) ⋯ ( x − x i − 1 ) ⋅ C ⋅ ( x − x i + 1 ) ⋯ ( x − x n ) = C ∏ k = 0 , k ≠ i n ( x − x k ) l_i(x)=(x-x_0)(x-x_i)\cdots(x-x_{i-1})·C·(x-x_{i+1})\cdots (x-x_n)=C\prod_{k=0, k\neq i}^n(x-x_k) li(x)=(x−x0)(x−xi)⋯(x−xi−1)⋅C⋅(x−xi+1)⋯(x−xn)=Ck=0,k=i∏n(x−xk) 再由 l i ( x i ) = 1 l_i(x_i)=1 li(xi)=1,即可确定它的常系数为 C = 1 ∏ k = 0 , k ≠ i ( x i − x k ) C=\frac{1}{\prod_{k=0,k\neq i}(x_i-x_k)} C=∏k=0,k=i(xi−xk)1,最后得到插值基函数为: l i ( x ) = ∏ k = 0 , k ≠ i n ( x − x k ) ∏ k = 0 , k ≠ i n ( x i − x k ) = ∏ k = 0 , k ≠ i n x − x k x i − x k ( i = 0 , 1 , 2 , ⋯ , n ) l_i(x)=\frac{\prod_{k=0,k\neq i}^n(x-x_k)}{\prod_{k=0,k\neq i}^n(x_i-x_k)}=\prod_{k=0,k\neq i}^n\frac{x-x_k}{x_i-x_k} \quad(i=0,1,2,\cdots,n) li(x)=∏k=0,k=in(xi−xk)∏k=0,k=in(x−xk)=k=0,k=i∏nxi−xkx−xk(i=0,1,2,⋯,n) 这样就可得到n+1个插值基函数 l i ( x ) ( i = 0 , 1 , 2 , ⋯ , n ) l_i(x)(i=0,1,2,\cdots,n) li(x)(i=0,1,2,⋯,n),代入(7)式,就得到Lagrange插值公式: p n ( x ) = ∑ i = 0 n l i ( x ) ⋅ y i = ∑ i = 0 n ( ∏ k = 0 , k ≠ i n x − x k x i − x k ) ⋅ y i (8) p_n(x)=\sum_{i=0}^nl_i(x)·y_i=\sum_{i=0}^n(\prod_{k=0,k\neq i}^n\frac{x-x_k}{x_i-x_k})·y_i \tag{8} pn(x)=i=0∑nli(x)⋅yi=i=0∑n(k=0,k=i∏nxi−xkx−xk)⋅yi(8) Lagrange插值公式具有以下特点: (1)对称性: p n ( x ) p_n(x) pn(x)与插值节点的排列顺序无关,只与 ( x i , y i ) ( i = 0 , 1 , 2 , ⋯ , n ) (x_i,y_i)(i=0,1,2,\cdots,n) (xi,yi)(i=0,1,2,⋯,n)有关。 (2)n=1为线性插值公式,n=2为抛物插值公式。 (3)当插值节点数变化时,基函数需要重新计算。 |
CopyRight 2018-2019 实验室设备网 版权所有 |