5.1 代数插值

对应教材 5.1.1–5.1.2、定理 5.1、例 1；对应老师第 9 讲末的插值引论。 主线：先问“存在唯一吗”，再写“Lagrange/Newton 怎么算”，最后看“误差与 Runge 现象”。

5.1.1 一元函数插值

给定互异节点 $x_0,\dots,x_n$ 和函数值 $f(x_i)$，求次数不超过 $n$ 的多项式 $p_n(x)$，使 $$p_n(x_i)=f(x_i),\qquad i=0,\dots,n.$$ 设 $p_n(x)=\sum_{k=0}^n c_k\varphi_k(x)$，插值条件给出线性方程组 $$\sum_{k=0}^n c_k\varphi_k(x_i)=f(x_i),\qquad i=0,\dots,n.$$ 当 ${\varphi_k}$ 取 $1,x,\dots,x^n$ 时，系数矩阵是范德蒙德矩阵 $$V=\begin{pmatrix} 1&x_0&\cdots&x_0^n\ \vdots&&&\vdots\ 1&x_n&\cdots&x_n^n \end{pmatrix},\qquad \det V=\prod_{0\le i\lt j\le n}(x_j-x_i)\ne0.$$ 所以插值多项式存在且唯一。

老师强调的“换基”：范德蒙德矩阵的条件数随 $n$ 指数增长（等距节点下 $n=12$ 可到 $10^8$ 量级），直接解 $Vc=y$ 会丢有效数字。Lagrange/Newton 不是“另一个公式”，而是换一组基，让系数矩阵变成单位矩阵或三角矩阵。存在唯一不等于“能算出来”。

Lagrange 插值

取基函数 $$\ell_k(x)=\prod_{j\ne k}\frac{x-x_j}{x_k-x_j}, \qquad \ell_k(x_j)=\delta_{kj}.$$ 则 $$p_n(x)=\sum_{k=0}^n f(x_k)\ell_k(x).$$ 优点：公式对称、直接；缺点：增加一个节点要全部重算。

例 1（教材 5.1.1）：$f(x)=2^x$，节点 $x=-1,0,1$，$f=0.5,1,2$。二次 Lagrange 插值： $$p_2(x)=\frac{(x-0)(x-1)}{(-1-0)(-1-1)}0.5 +\frac{(x+1)(x-1)}{(0+1)(0-1)}1 +\frac{(x+1)(x-0)}{(1+1)(1-0)}2 =0.25x^2+0.75x+1.$$ 于是 $2^{0.3}\approx p_2(0.3)=1.2475$。

Newton 插值

把基换成 $$1,\quad x-x_0,\quad (x-x_0)(x-x_1),\quad\dots,\quad\prod_{j=0}^{n-1}(x-x_j),$$ 系数就是差商： $$p_n(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+f[x_0,\dots,x_n]\prod_{j=0}^{n-1}(x-x_j).$$ 差商递推： $$f[x_i]=f(x_i),\qquad f[x_i,\dots,x_{i+k}]=\frac{f[x_{i+1},\dots,x_{i+k}]-f[x_i,\dots,x_{i+k-1}]}{x_{i+k}-x_i}.$$ 例 1 的差商表：$f[-1,0]=0.5$，$f[0,1]=1$，$f[-1,0,1]=0.25$，故 $$p_2(x)=0.5+0.5(x+1)+0.25(x+1)x=0.25x^2+0.75x+1,$$ 与 Lagrange 结果相同（唯一性）。增加节点时只需在末尾加一项，这是 Newton 的优点。

余项与误差

定理 5.1（插值余项）：设 $f\in C^{n+1}[a,b]$，$p_n$ 是 $n$ 次插值多项式，则对任意 $x\in[a,b]$，存在 $\xi\in(a,b)$，使 $$R_n(x)=f(x)-p_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n(x-x_i).$$ 若 $|f^{(n+1)}(x)|\le M_{n+1}$，则 $$|R_n(x)|\le\frac{M_{n+1}}{(n+1)!}\prod_{i=0}^n|x-x_i|.$$

例 1 中 $f'''(x)=2^x(\ln2)^3$，在 $[-1,1]$ 上最大 $0.6660$，故 $$|2^{0.3}-p_2(0.3)|\le\frac{0.6660}{3!}|(0.3+1)(0.3)(0.3-1)|\approx0.0303.$$ 即 $p_2(0.3)=1.2475$ 至少有两位有效数字。

Runge 现象与分段插值

高次插值并不一定更好。Runge 例子： $$f(x)=\frac{1}{1+x^2},\qquad x\in[-5,5],$$ 取等距节点 $x_i=-5+\frac{10}{n}i$。$n$ 增大时，区间中部逼近变好，但两端剧烈振荡，$n\to\infty$ 也不一致收敛。原因：余项中的 $\prod(x-x_i)$ 在两端很大，高次多项式对节点分布极敏感。

实际计算常用分段低次插值：把区间分成小段，每段用低次多项式；必要时用三次样条保证一阶/二阶导数连续（见 5.3）。

5.1.2 二元函数插值（教材有、课堂未讲）

给定矩形网格 $(x_i,y_j)$ 上的值 $f(x_i,y_j)$，取二元多项式 $$p_{n,m}(x,y)=\sum_{k=0}^n\sum_{r=0}^m c_{kr}x^ky^r,$$ 使其在网格点上等于 $f$。基函数组在网格点上线性无关，故插值多项式存在唯一。实际常用张量积形式：先对 $x$ 插值，再对 $y$ 插值；计算量与一维同阶。

例 2（教材 5.1.2）：给四点 $(0,0,1),(1,0,2),(0,1,3),(1,1,5)$，求双一次插值 $$p(x,y)=a+bx+cy+dxy.$$ 代入得 $a=1,b=1,c=2$，再由 $p(1,1)=5$ 得 $d=1$，故 $$p(x,y)=1+x+2y+xy.$$ 双一次插值在每条网格线上都是一次函数，适合规则网格上的快速查表；它不是全局二次，不能随便外推。