拉格朗日差值法学习笔记

你的名字 2021-10-18 06:26 289阅读 0赞

# 拉格朗日差值法学习笔记 #

1.定义：

拉格朗日插值法是以法国十八世纪数学家约瑟夫·拉格朗日命名的一种多项式插值方法。

给出不同的自变量下的函数值，拉格朗日插值法能找出恰好满足所有条件的多项式。

2.定义式：

[![f(k)=\\sum \_\{i=0\}^\{n\}y\[i\]\\prod\_\{i\\neq j\}\\frac\{k-x\[j\]\}\{x\[i\]-x\[j\]\}][f_k_sum _i_0_n_y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j]][f_k_sum _i_0_n_y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j_f_k_sum _i_0_n_y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j]

我们仔细观察可以发现，当k等于任意x\[i\]时，对于所有i’！=i，连乘中定有k=x\[i\]=x\[j\],

[![y\[\{i\}'\]\\prod\_\{\{i\}'\\neq j\}\\frac\{k-x\[j\]\}\{x\[\{i\}'\]-x\[j\]\}=0][y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j_0]][y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j_0_y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j_0]

而对于i'=i,对于任何j!=i’,k-x\[j\]=x\[i'\]-x\[j\]:

[![y\[\{i\}'\]\\prod\_\{\{i\}'\\neq j\}\\frac\{k-x\[j\]\}\{x\[\{i\}'\]-x\[j\]\}=y\[\{i\}'\]][y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j_y_i]][y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j_0_y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j_0]

而我们知道n+1个x不同的点可以确定n次多项式

则f(k)定为n次多项式下k的函数值。

3.特殊情况：

当x\[i\]值连续时，可将式子化简为：

[![f(k) = \\sum\_\{i=0\}^n y\_i \\prod\_\{i \\not = j\} \\frac\{k - j\}\{i - j\}][f_k_ _ _sum_i_0_n y_i _prod_i _not _ j_ _frac_k - j_i - j]][f_k_ _ _sum_i_0_n y_i _prod_i _not _ j_ _frac_k - j_i - j_f_k_ _ _sum_i_0_n y_i _prod_i _not _ j_ _frac_k - j_i - j]

不妨设：

[![pre\_i = \\prod\_\{j = 0\}^\{i\} k - j][pre_i _ _prod_j _ 0_i_ k - j]][pre_i _ _prod_j _ 0_i_ k - j_pre_i _ _prod_j _ 0_i_ k - j]       [![suf\_i = \\prod\_\{j = i\}^n k - j][suf_i _ _prod_j _ i_n k - j]][suf_i _ _prod_j _ i_n k - j_suf_i _ _prod_j _ i_n k - j]

则可预处理出prei，和sufi，观察可以发现，分母可以表示为阶乘之积的形式，则又可化简：

[![f(k) = \\sum\_\{i=0\}^n y\_i \\frac\{pre\_\{i-1\} \* suf\_\{i+1\}\}\{fac\[i\] \* fac\[N - i\]\}][f_k_ _ _sum_i_0_n y_i _frac_pre_i-1_ _ suf_i_1_fac_i_ _ fac_N - i]][f_k_ _ _sum_i_0_n y_i _frac_pre_i-1_ _ suf_i_1_fac_i_ _ fac_N - i_f_k_ _ _sum_i_0_n y_i _frac_pre_i-1_ _ suf_i_1_fac_i_ _ fac_N - i]

可以在线性时间内求出来。

转载于:https://www.cnblogs.com/ljk123-de-bo-ke/p/11225375.html

[f_k_sum _i_0_n_y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j]: https://latex.codecogs.com/gif.latex?f%28k%29=%5Csum&space;_%7Bi=0%7D%5E%7Bn%7Dy%5Bi%5D%5Cprod_%7Bi%5Cneq&space;j%7D%5Cfrac%7Bk-x%5Bj%5D%7D%7Bx%5Bi%5D-x%5Bj%5D%7D
[f_k_sum _i_0_n_y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j_f_k_sum _i_0_n_y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j]: https://private.codecogs.com/eqnedit.php?latex=f%28k%29=%5Csum&space;_%7Bi=0%7D%5E%7Bn%7Dy%5Bi%5D%5Cprod_%7Bi%5Cneq&space;j%7D%5Cfrac%7Bk-x%5Bj%5D%7D%7Bx%5Bi%5D-x%5Bj%5D%7D
[y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j_0]: https://latex.codecogs.com/gif.latex?y%5B%7Bi%7D'%5D%5Cprod_%7B%7Bi%7D'%5Cneq&space;j%7D%5Cfrac%7Bk-x%5Bj%5D%7D%7Bx%5B%7Bi%7D'%5D-x%5Bj%5D%7D=0
[y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j_0_y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j_0]: https://private.codecogs.com/eqnedit.php?latex=y%5B%7Bi%7D'%20rel=
[y_i_prod_i_neq j_frac_k-x_j_x_i_-x_j_y_i]: https://latex.codecogs.com/gif.latex?y%5B%7Bi%7D'%5D%5Cprod_%7B%7Bi%7D'%5Cneq&space;j%7D%5Cfrac%7Bk-x%5Bj%5D%7D%7Bx%5B%7Bi%7D'%5D-x%5Bj%5D%7D=y%5B%7Bi%7D'%5D
[f_k_ _ _sum_i_0_n y_i _prod_i _not _ j_ _frac_k - j_i - j]: https://latex.codecogs.com/gif.latex?f%28k%29&space;=&space;%5Csum_%7Bi=0%7D%5En&space;y_i&space;%5Cprod_%7Bi&space;%5Cnot&space;=&space;j%7D&space;%5Cfrac%7Bk&space;-&space;j%7D%7Bi&space;-&space;j%7D
[f_k_ _ _sum_i_0_n y_i _prod_i _not _ j_ _frac_k - j_i - j_f_k_ _ _sum_i_0_n y_i _prod_i _not _ j_ _frac_k - j_i - j]: https://private.codecogs.com/eqnedit.php?latex=f%28k%29&space;=&space;%5Csum_%7Bi=0%7D%5En&space;y_i&space;%5Cprod_%7Bi&space;%5Cnot&space;=&space;j%7D&space;%5Cfrac%7Bk&space;-&space;j%7D%7Bi&space;-&space;j%7D
[pre_i _ _prod_j _ 0_i_ k - j]: https://latex.codecogs.com/gif.latex?pre_i&space;=&space;%5Cprod_%7Bj&space;=&space;0%7D%5E%7Bi%7D&space;k&space;-&space;j
[pre_i _ _prod_j _ 0_i_ k - j_pre_i _ _prod_j _ 0_i_ k - j]: https://private.codecogs.com/eqnedit.php?latex=pre_i&space;=&space;%5Cprod_%7Bj&space;=&space;0%7D%5E%7Bi%7D&space;k&space;-&space;j
[suf_i _ _prod_j _ i_n k - j]: https://latex.codecogs.com/gif.latex?%5Cdpi%7B200%7D&space;suf_i&space;=&space;%5Cprod_%7Bj&space;=&space;i%7D%5En&space;k&space;-&space;j
[suf_i _ _prod_j _ i_n k - j_suf_i _ _prod_j _ i_n k - j]: https://private.codecogs.com/eqnedit.php?latex=%5Cdpi%7B200%7D&space;suf_i&space;=&space;%5Cprod_%7Bj&space;=&space;i%7D%5En&space;k&space;-&space;j
[f_k_ _ _sum_i_0_n y_i _frac_pre_i-1_ _ suf_i_1_fac_i_ _ fac_N - i]: https://latex.codecogs.com/gif.latex?f%28k%29&space;=&space;%5Csum_%7Bi=0%7D%5En&space;y_i&space;%5Cfrac%7Bpre_%7Bi-1%7D&space;*&space;suf_%7Bi+1%7D%7D%7Bfac%5Bi%5D&space;*&space;fac%5BN&space;-&space;i%5D%7D
[f_k_ _ _sum_i_0_n y_i _frac_pre_i-1_ _ suf_i_1_fac_i_ _ fac_N - i_f_k_ _ _sum_i_0_n y_i _frac_pre_i-1_ _ suf_i_1_fac_i_ _ fac_N - i]: https://private.codecogs.com/eqnedit.php?latex=f%28k%29&space;=&space;%5Csum_%7Bi=0%7D%5En&space;y_i&space;%5Cfrac%7Bpre_%7Bi-1%7D&space;*&space;suf_%7Bi+1%7D%7D%7Bfac%5Bi%5D&space;*&space;fac%5BN&space;-&space;i%5D%7D