- 拉格朗日插值法
- 牛顿插值的递推
- 差商
- 牛顿插值法
上篇指出函数 f ( x ) f(x) f(x)的插值可以用一个多阶多项式 P ( x ) P(x) P(x)表示： P ( x ) = a 0 + a 1 x + a 2 x 2 + ⋯ + a n x n P(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n P(x)=a0+a1x+a2x2+⋯+anxn
拉格朗日插值法将一个多阶多项式拆分为多个多阶多项式的和，当出现新的节点值时，需要重新计算各多项式，提升了计算量。牛顿插值法解决了重新计算的问题。
牛顿插值的递推牛顿插值法使用了递推的思想。对于未知表达式的函数 f ( x ) f(x) f(x)，知道其节点 ( x 0 , f ( x 0 ) ) , ( x 1 , f ( x 1 ) ) , … , ( x n , f ( x n ) ) (x_0,f(x_0)),(x_1,f(x_1)),\dots,(x_n,f(x_n)) (x0,f(x0)),(x1,f(x1)),…,(xn,f(xn))。
假设 f k ( x ) f_k(x) fk(x)是采样完一个节点后的插值结果。第一次插值需要满足节点 ( x 0 , f ( x 0 ) ) (x_0,f(x_0)) (x0,f(x0))： f 0 ( x ) = f ( x 0 ) f 0 ( x 0 ) = f ( x 0 ) f_0(x)=f(x_0) \\ f_0(x_0)=f(x_0) f0(x)=f(x0)f0(x0)=f(x0) 对于第二次插值，需要满足节点 ( x 0 , f ( x 0 ) ) , ( x 1 , f ( x 1 ) ) (x_0,f(x_0)),(x_1,f(x_1)) (x0,f(x0)),(x1,f(x1))： f 1 ( x ) = f 0 ( x ) + b 1 ( x − x 0 ) f 1 ( x 0 ) = f ( x 0 ) f i n d : b 1 s . t . f 1 ( x 1 ) = f 0 ( x 1 ) + b 1 ( x 1 − x 0 ) = f ( x 1 ) b 1 = f ( x 1 ) − f ( x 0 ) x 1 − x 0 f_1(x)=f_0(x)+b_1(x-x_0) \\ f_1(x_0)=f(x_0) \\ \quad \\ find:\quad b_1 \\ s.t.\quad f_1(x_1)=f_0(x_1)+b_1(x_1-x_0)=f(x_1) \\ \quad \\ b_1=\frac{f(x_1)-f(x_0)}{x_1-x_0} f1(x)=f0(x)+b1(x−x0)f1(x0)=f(x0)find:b1s.t.f1(x1)=f0(x1)+b1(x1−x0)=f(x1)b1=x1−x0f(x1)−f(x0) 对于第三次插值，需要满足节点 ( x 0 , f ( x 0 ) ) , ( x 1 , f ( x 1 ) , ( x 2 , f ( x 2 ) ) ) (x_0,f(x_0)),(x_1,f(x_1),(x_2,f(x_2))) (x0,f(x0)),(x1,f(x1),(x2,f(x2)))： f 2 ( x ) = f 1 ( x ) + b 2 ( x − x 0 ) ( x − x 1 ) f 2 ( x 0 ) = f 1 ( x 0 ) = f ( x 0 ) f 2 ( x 1 ) = f 1 ( x 1 ) = f ( x 1 ) f i n d : b 2 s . t . f 2 ( x 2 ) = f 1 ( x 2 ) + b 2 ( x 2 − x 0 ) ( x 2 − x 1 ) = f ( x 2 ) b 2 = f ( x 2 ) − f ( x 1 ) x 2 − x 1 − f ( x 1 ) − f ( x 0 ) x 1 − x 0 x 2 − x 0 f_2(x)=f_1(x)+b_2(x-x_0)(x-x_1) \\ f_2(x_0)=f_1(x_0)=f(x_0) \\ f_2(x_1)=f_1(x_1)=f(x_1) \\ \quad \\ find:\quad b_2 \\ s.t.\quad f_2(x_2)=f_1(x_2)+b_2(x_2-x_0)(x_2-x_1)=f(x_2) \\ \quad \\ b_2=\frac{\frac{f(x_2)-f(x_1)}{x_2-x_1} -\frac{f(x_1)-f(x_0)}{x_1-x_0}}{x_2-x_0} f2(x)=f1(x)+b2(x−x0)(x−x1)f2(x0)=f1(x0)=f(x0)f2(x1)=f1(x1)=f(x1)find:b2s.t.f2(x2)=f1(x2)+b2(x2−x0)(x2−x1)=f(x2)b2=x2−x0x2−x1f(x2)−f(x1)−x1−x0f(x1)−f(x0) 于是，每次插值的结果都可以看成是上次插值的结果加上本次插值的影响，从而大幅减少了计算量： P ( x ) = f n − 1 ( x ) + b n ( x − x 0 ) ( x − x 1 ) … ( x − x n − 1 ) P(x)=f_{n-1}(x)+b_n(x-x_0)(x-x_1)\dots(x-x_{n-1}) \\ P(x)=fn−1(x)+bn(x−x0)(x−x1)…(x−xn−1)
我们要做的就是计算系数 b b b的表达式。
差商上面计算出了 b 1 , b 2 b_1,b_2 b1,b2的表达式。实际上系数 b b b符合差商形式。差商的计算如下所示： 一 阶 差 商 ： b 1 = f [ x 0 , x 1 ] = f ( x 1 ) − f ( x 0 ) x 1 − x 0 二 阶 差 商 ： b 2 = f [ x 0 , x 1 , x 2 ] = f [ x 0 , x 1 ] − f [ x 1 , x 2 ] x 0 − x 2 = f ( x 2 ) − f ( x 1 ) x 2 − x 1 − f ( x 1 ) − f ( x 0 ) x 1 − x 0 x 2 − x 0 三 阶 差 商 ： b 3 = f [ x 0 , x 1 , x 2 , x 3 ] = f [ x 0 , x 1 , x 2 ] − f [ x 1 , x 2 , x 3 ] x 0 − x 3 n 阶 差 商 ： b n = f [ x 0 , x 1 , … , x n ] = f [ x 0 , x 1 , … , x n − 1 ] − f [ x 1 , x 2 , … , x n ] x 0 − x n 一阶差商：\\ \quad \\ b_1=f[x_0,x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0} \\ \quad \\ 二阶差商：\\ \quad \\ b_2=f[x_0,x_1,x_2] =\frac{f[x_0,x_1]-f[x_1,x_2]}{x_0-x_2} = \frac{\frac{f(x_2)-f(x_1)}{x_2-x_1} -\frac{f(x_1)-f(x_0)}{x_1-x_0}}{x_2-x_0} \\ \quad \\ 三阶差商：\\ \quad \\ b_3 = f[x_0,x_1,x_2,x_3] = \frac{f[x_0,x_1,x_2]-f[x_1,x_2,x_3]}{x_0-x_3} \\ \quad \\ n阶差商： \\ \quad \\ b_n = f[x_0,x_1,\dots,x_n]=\frac{f[x_0,x_1,\dots,x_{n-1}]-f[x_1,x_2,\dots,x_{n}]}{x_0-x_n} 一阶差商：b1=f[x0,x1]=x1−x0f(x1)−f(x0)二阶差商：b2=f[x0,x1,x2]=x0−x2f[x0,x1]−f[x1,x2]=x2−x0x2−x1f(x2)−f(x1)−x1−x0f(x1)−f(x0)三阶差商：b3=f[x0,x1,x2,x3]=x0−x3f[x0,x1,x2]−f[x1,x2,x3]n阶差商：bn=f[x0,x1,…,xn]=x0−xnf[x0,x1,…,xn−1]−f[x1,x2,…,xn] 对于差商 f [ x 1 , x 2 , … , x n ] f[x_1,x_2,\dots,x_n] f[x1,x2,…,xn]而言，序号下标的顺序不影响差商的值。
牛顿插值法把差商代入牛顿插值递推中，就得出了牛顿插值多项式的一般形式： P ( x ) = f ( x 0 ) + f [ x 0 , x 1 ] ( x − x 0 ) + f [ x 0 , x 1 , x 2 ] ( x − x 0 ) ( x − x 1 ) + … + f [ x 0 , x 1 , … , x n ] ( x − x 0 ) ( x − x 1 ) … ( x − x n − 1 ) P(x)=f(x_0)+f[x_0,x_1](x-x_0)\\ \quad\quad\quad +f[x_0,x_1,x_2](x-x_0)(x-x_1) \\ \quad +\dots \\ +f[x_0,x_1,\dots,x_n](x-x_0)(x-x_1)\dots(x-x_{n-1}) P(x)=f(x0)+f[x0,x1](x−x0)+f[x0,x1,x2](x−x0)(x−x1)+…+f[x0,x1,…,xn](x−x0)(x−x1)…(x−xn−1) 实际插值时，只需要把上一次采样后插值的结果 P n − 1 P_{n-1} Pn−1存储下来，下一次采样时直接求 P n − 1 P_{n-1} Pn−1与新项的和就行了，节省了计算量和存储空间。
