zcmimi's blog

平面上n+1个点可以确定一个n次多项式F(x)

拉格朗日插值法可以根据n+1个点确定一个n次多项式

设这n个点为(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)

构造多项式 \displaystyle \ell_i(x)=\prod_{j=0,i\neq j}^n \frac{x-x_j}{x_i-x_j}

可以发现\ell_i(x)只有在x_i时取值为1,在其他点取值为0

构造多项式\displaystyle F(x)=\sum_{i=0}^n y_i\ell_i(x)

那么F(x_i)=y_i,也就是保证F经过这n个点

复杂度:O(n^2)

拉格朗日插值法
comment评论
Search
search