数值分析作业插值法2

埃尔米特插值

不仅要求函数值重合，而且要求若干阶导数也重合，这种插值问题称为埃尔米特插值问题。

低次埃尔米特插值多项式

1. 二点三次埃尔米特插值多项式

   **问题描述：**给定区间 $[x_0,x_1]$ 两端点的函数值与导数值：

   $x$	$x_0$	$x_1$
   $f(x)$	$y_0$	$y_1$
   $f^{\prime }(x)$	$m_0$	$m_1$

   要求构造三次多项式 $H_3(x)$，满足：
   $$\{\begin{array}{ll}{H}_3(x_0)=y_0,& H_3(x_1)=y_1\\ H_3^{\prime }(x_0)=m_0,& H_3^{\prime }(x_1)=m_1\end{array}$$

   ---

   解法形式

   设 $H_3(x)$ 为：
   $$H_3(x)={\alpha }_0(x)y_0+{\alpha }_1(x)y_1+{\beta }_0(x)m_0+{\beta }_1(x)m_1$$
   其中 ${\alpha }_i(x)$ 和 ${\beta }_i(x)$ 为基函数（三次式），满足以下条件：

   1. 插值条件：

      • ${\alpha }_i(x_j)={\delta }_{ij}$（${\delta }_{ij}$ 为克罗内克函数）
      • ${\alpha }_i^{\prime }(x_j)=0$
      • ${\beta }_i(x_j)=0$
      • ${\beta }_i^{\prime }(x_j)={\delta }_{ij}$

   2. 基函数构造：
      [
      \alpha_i(x) = (a_i x + b_i) l_i^2(x), \quad \beta_i(x) = c_i(x - x_i) l_i^2(x)
      ]
      其中 $l_i(x)=\frac{x-x_j}{x_i-x_j}$（$j\ne i$）为拉格朗日基函数。

   ---

   基函数推导

   ${\alpha }_0(x)$ 的构造
   通过条件 ${\alpha }_0(x_0)=1$ 和 ${\alpha }_0^{\prime }(x_0)=0$，解得：
   $$\{\begin{array}{l}{a}_0=-\frac{2}{x_0-x_1},\\ b_0=1+\frac{2x_0}{x_0-x_1}\end{array}$$
   最终形式为：
   $${\alpha }_0(x)=\left(1-2\frac{x-x_0}{x_0-x_1}\right){\left(\frac{x-x_1}{x_0-x_1}\right)}^2$$
   $${\alpha }_1(x)=\left(1-2\frac{x-x_1}{x_1-x_0}\right){\left(\frac{x-x_0}{x_1-x_0}\right)}^2$$
   ${\beta }_i(x)$ 的构造
   $${\beta }_0(x)=(x-x_0){\left(\frac{x-x_1}{x_0-x_1}\right)}^2,{\beta }_1(x)=(x-x_1){\left(\frac{x-x_0}{x_1-x_0}\right)}^2$$

   ---

   最终表达式
   $$H_3(x)=y_0\left(1-2\frac{x-x_0}{x_0-x_1}\right){\left(\frac{x-x_1}{x_0-x_1}\right)}^2$$

   • $$y_1\left(1-2\frac{x-x_1}{x_1-x_0}\right){\left(\frac{x-x_0}{x_1-x_0}\right)}^2$$
   • $$m_0(x-x_0){\left(\frac{x-x_1}{x_0-x_1}\right)}^2$$
   • $$m_1(x-x_1){\left(\frac{x-x_0}{x_1-x_0}\right)}^2$$

   $$\sum _{i=0}^1{\alpha }_i(x)=1\text{（当 f(x)=1 时）}$$

   余项为：
   $$R(x)=\frac{1}{4!}{f}^{(4)}(\xi )(x-x_0{)}^2(x-x_1{)}^2,\xi \in (x_0,x_1)$$

2. 三点三次带一个导数值的插值多项式

   问题描述
   给定函数表如下：

   $x$	$x_0$	$x_1$	$x_2$
   $f(x)$	$y_0$	$y_1$	$y_2$
   $f^{\prime }(x)$		$m_1$

   要求构造三次多项式 $H_3(x)$，满足：
   $$\{\begin{array}{ll}{H}_3(x_i)=y_i,& i=0,1,2\\ H_3^{\prime }(x_1)=m_1& \end{array}$$

   解法形式
   利用满足插值条件的 Newton 插值多项式，设：
   $$H_3(x)=y_0+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)+k(x-x_0)(x-x_1)(x-x_2)$$
   其中 $k$ 为待定系数。

   待定系数求解
   通过导数条件 $H_3^{\prime }(x_1)=m_1$ 确定 $k$：
   $$H_3^{\prime }(x_1)=f[x_0,x_1]+f[x_0,x_1,x_2](x_1-x_0)+k(x_1-x_0)(x_1-x_2)=m_1$$
   解得：
   $$k=\frac{m_1-f[x_0,x_1]-f[x_0,x_1,x_2](x_1-x_0)}{(x_1-x_0)(x_1-x_2)}$$

   最终表达式
   将 $k$ 代入后，$H_3(x)$ 的完整形式为：
   $$H_3(x)=y_0+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)$$

   • $$\frac{m_1-f[x_0,x_1]-f[x_0,x_1,x_2](x_1-x_0)}{(x_1-x_0)(x_1-x_2)}(x-x_0)(x-x_1)(x-x_2)$$

   余项为：
   $$R(x)=\frac{1}{4!}{f}^{(4)}(\xi )(x-x_0)(x-x_1{)}^2(x-x_2),\xi \in (x_0,x_2)$$

一般埃尔米特插值多项式

问题描述
已知节点 $x_0,x_1,\dots ,x_n$ 处的函数值 $y_0,y_1,\dots ,y_n$ 和导数值 $y_0^{\prime },y_1^{\prime },\dots ,y_n^{\prime }$，要求构造次数为 $2n+1$ 的多项式 $H_{2n+1}(x)$（这样的Hermite 插值唯一），满足：
$$\{\begin{array}{l}{H}_{2n+1}(x_i)=y_i,\\ H_{2n+1}^{\prime }(x_i)=y_i^{\prime }\end{array}(i=0,1,\dots ,n)$$

解法形式
设多项式为：
$$H_{2n+1}(x)=\sum _{i=0}^n{y}_i{\alpha }_i(x)+\sum _{i=0}^n{y}_i^{\prime }{\beta }_i(x)$$
其中基函数 ${\alpha }_i(x)$ 和 ${\beta }_i(x)$ 满足：
$$\{\begin{array}{ll}{\alpha }_i(x_j)={\delta }_{ij},& {\alpha }_i^{\prime }(x_j)=0\\ {\beta }_i(x_j)=0,& {\beta }_i^{\prime }(x_j)={\delta }_{ij}\end{array}$$

${\alpha }_i(x)$ 和 ${\beta }_i(x)$ 均为 $2n+1$ 次多项式。
基函数构造

${\alpha }_i(x)$ 的构造

1. 零点性质：${\alpha }_i(x)$ 在 $x_0,x_1,\dots ,x_n$ 处有二重零点（除 $x_i$ 外）。

2. 形式假设：
   $${\alpha }_i(x)=[A_{i}x+B_i]l_i^2(x)$$
   其中 $l_i(x)={\prod }_{\begin{array}{c}j\ne i\end{array}}\frac{x-x_j}{x_i-x_j}$ 为拉格朗日基函数。

3. 条件求解：

   • ${\alpha }_i(x_i)=1\Rightarrow B_i=1$
   • ${\alpha }_i^{\prime }(x_i)=0\Rightarrow A_i=-2l_i^{\prime }(x_i)$

   最终形式为：
   $${\alpha }_i(x)=\left[1-2l_i^{\prime }(x_i)(x-x_i)\right]l_i^2(x)$$

${\beta }_i(x)$ 的构造

1. 零点性质：${\beta }_i(x)$ 在 $x_0,x_1,\dots ,x_n$ 处有二重零点（除 $x_i$ 外）。

2. 形式假设：
   [
   \beta_i(x) = C_i (x - x_i) l_i^2(x)
   ]

3. 条件求解：

   • ${\beta }_i^{\prime }(x_i)=1\Rightarrow C_i=1$

   最终形式为：
   $${\beta }_i(x)=(x-x_i)l_i^2(x)$$

余项分析
设区间 $[a,b]$ 满足 $a=x_0<x_1<\cdots <x_n=b$，且 $f\in C^{2n+2}[a,b]$，则插值余项为：
$$R_n(x)=\frac{f^{(2n+2)}(\xi )}{(2n+2)!}{\left[\prod _{i=0}^n(x-x_i)\right]}^2$$
其中 $\xi \in (a,b)$。

分段低次插值

分段线性插值

定义
设已知节点 $a<x_0<x_1<\cdots <x_n=b$ 处的函数值为 $f_0,f_1,\dots ,f_n$，记区间宽度：
$$h_k=x_{k+1}-x_k,h=\underset{k}{\max }{h}_k$$
分段线性插值通过折线段连接插值点逼近 $f(x)$，构造折线函数 $I_h(x)$ 满足：

1. 连续性：$I_h(x)\in C[a,b]$
2. 插值条件：$I_h(x_k)=f_k(k=0,1,\dots ,n)$
3. 分段线性：在每段区间 $[x_k,x_{k+1}]$ 上，$I_h(x)$ 为线性函数。

分段线性插值函数可表示为：
$$I_h(x)=\sum _{k=0}^n{f}_k{l}_k(x)$$
其中 $l_k(x)$ 为分段线性基函数。

基函数定义
基函数 $l_k(x)$ 在区间内的表达式为：
$$l_k(x)=\{\begin{array}{ll}\frac{x-x_{k-1}}{x_k-x_{k-1}},& x\in [x_{k-1},x_k](k\ne 0)\\ \frac{x-x_{k+1}}{x_k-x_{k+1}},& x\in [x_k,x_{k+1}](k\ne n)\\ 0,& x\notin [x_{k-1},x_{k+1}]\end{array}$$

区间分段表达式
左半区间 $[x_{k-1},x_k]$：
$$I_h(x)=\frac{x-x_{k-1}}{x_k-x_{k-1}}{f}_k+\frac{x-x_k}{x_{k-1}-x_k}{f}_{k-1}$$

右半区间 $[x_k,x_{k+1}]$：
$$I_h(x)=\frac{x-x_{k+1}}{x_k-x_{k+1}}{f}_k+\frac{x-x_k}{x_{k+1}-x_k}{f}_{k+1}$$

收敛性与性质

1. 一致收敛性：当 $h\to 0$ 时，$I_h(x)$ 在 $[a,b]$ 上一致收敛到 $f(x)$。

2. 光滑性缺失：分段线性插值函数仅连续（$C^0$），但不可导（失去原函数的光滑性）。

插值误差
$$\underset{x_k\le x\le x_{k+1}}{\max }|f(x)-I_h(x)|\le \frac{M_2}{2}\underset{x_k\le x\le x_{k+1}}{\max }|(x-x_k)(x-x_{k+1})|$$
或
$$\underset{a\le x\le b}{\max }|f(x)-I_h(x)|\le \frac{M_2}{8}{h}^2$$
其中
$$M_2=\underset{a\le x\le b}{\max }|f^{\prime \prime }(x)|$$

分段三次 Hermite 插值

问题描述
在节点 $x_0<x_1<\cdots <x_n$ 上已知函数值 $f_k$ 和导数值 $f_k^{\prime }=m_k$，构造分段插值多项式函数 $I_h(x)$ 满足：

1. 光滑性：$I_h\in C^1[a,b]$
2. 插值条件：
   $$I_h(x_k)=f_k,I_h^{\prime }(x_k)=f_k^{\prime }(k=0,1,\dots ,n)$$
3. 分段三次多项式：在每段区间 $[x_k,x_{k+1}]$ 上，$I_h(x)$ 为三次多项式。

全局表达式
插值函数可表示为：
$$I_h(x)=\sum _{k=0}^n\left[f(x_k){\alpha }_k(x)+f^{\prime }(x_k){\beta }_k(x)\right]$$

区间局部表达式
在区间 $[x_k,x_{k+1}]$ 上的具体形式为：
$$\begin{array}{rl}{I}_h(x)=& {\left(\frac{x-x_{k+1}}{x_k-x_{k+1}}\right)}^2\left(1+2\frac{x-x_k}{x_{k+1}-x_k}\right)f_k\\ & {\left(\frac{x-x_k}{x_{k+1}-x_k}\right)}^2\left(1+2\frac{x-x_{k+1}}{x_k-x_{k+1}}\right)f_{k+1}\\ & {\left(\frac{x-x_{k+1}}{x_k-x_{k+1}}\right)}^2(x-x_k)f_k^{\prime }\\ & {\left(\frac{x-x_k}{x_{k+1}-x_k}\right)}^2(x-x_{k+1})f_{k+1}^{\prime }\end{array}$$

（基函数 ${\alpha }_k(x)$ 和 ${\beta }_k(x)$ 的定义已在前面详细给出，此处可省略重复内容以保持简洁）

${\alpha }_k(x)$ 的分段表达式
$${\alpha }_k(x)=\{\begin{array}{ll}{\left(\frac{x-x_{k-1}}{x_k-x_{k-1}}\right)}^2\left(1+2\frac{x-x_k}{x_{k-1}-x_k}\right),& x\in [x_{k-1},x_k](k\ne 0)\\ {\left(\frac{x-x_{k+1}}{x_k-x_{k+1}}\right)}^2\left(1+2\frac{x-x_k}{x_{k+1}-x_k}\right),& x\in [x_k,x_{k+1}](k\ne n)\\ 0,& \text{其他区间}\end{array}$$

${\beta }_k(x)$ 的分段表达式
$${\beta }_k(x)=\{\begin{array}{ll}{\left(\frac{x-x_{k-1}}{x_k-x_{k-1}}\right)}^2(x-x_k),& x\in [x_{k-1},x_k](k\ne 0)\\ {\left(\frac{x-x_{k+1}}{x_k-x_{k+1}}\right)}^2(x-x_k),& x\in [x_k,x_{k+1}](k\ne n)\\ 0,& \text{其他区间}\end{array}$$

样条插值

样条插值的概念

对于给定节点 $a=x_0<x_1<\cdots <x_n=b$，若存在函数 $s(x)$ 满足：

1. 在每个小区间 $[x_j,x_{j+1}]$ 上是一个次数不超过3的多项式；
2. 在每一个内节点上具有直到二阶的连续导数，
   则称 $s(x)$ 是节点 $x_0,x_1,\cdots ,x_n$ 上的三次样条函数。

若在节点上给定函数值 $f(x_j)=y_j(j=0,\cdots ,n)$，并满足
3. $s(x_j)=y_j,j=0,\cdots ,n$
则称 $s(x)$ 是三次样条插值函数。

三次样条插值函数 $s(x)$ 的确定：

$$s(x)=\{\begin{array}{ll}{s}_1(x),& x_0\le x\le x_1,\\ ⋮& \\ s_n(x),& x_{n-1}\le x\le x_n.\end{array}$$
在每个 $[x_j,x_{j+1}]$ 上要确定4个待定系数，共 $4n$ 个参数。因二阶导数连续，故在内节点 $x_j$ 上满足连续性条件：
$$\begin{array}{c}s(x_j-0)=s(x_j+0),s^{\prime }(x_j-0)=s^{\prime }(x_j+0),\\ s^{\prime \prime }(x_j-0)=s^{\prime \prime }(x_j+0),(j=1,\cdots ,n-1)\end{array}$$
再加上插值条件，共 $4n-2$ 个条件。还需2个条件，通常在两个端点加上边界条件。

常见三种边界条件：

1. 第一种边界条件：$s^{\prime }(x_0)=y_0^{\prime },s^{\prime }(x_n)=y_n^{\prime }$。
2. 第二种边界条件：$s^{\prime \prime }(x_0)=y_0^{\prime \prime },s^{\prime \prime }(x_n)=y_n^{\prime \prime }$。
   特别地，自然边界条件：$s^{\prime \prime }(x_0)=0,s^{\prime \prime }(x_n)=0$。
3. 第三种边界条件（周期边界条件）：
   $$s^{\prime }(x_0+0)=s^{\prime }(x_n-0),s^{\prime \prime }(x_0+0)=s^{\prime \prime }(x_n-0).$$
   注意：因插值条件 $y_0=y_n$，故 $s(x_0+0)=s(x_n-0)$ 已经成立。

三次样条插值函数的建立

求三次样条插值函数常用三弯矩法和三转角法。

三转角法：假定 $s^{\prime }(x_j)=m_j(j=0,\cdots ,n)$，根据分段三次埃尔米特插值多项式，
$$s(x)=\sum _{j=0}^n\left[f_j{\alpha }_j(x)+m_j{\beta }_j(x)\right]$$
由插值条件、连续性条件和边界条件，可得关于 $m_j$ 的三对角方程组，求出 $m_j$，得到三次样条插值函数。

三弯矩法：令 $s^{\prime \prime }(x_j)=M_j,j=0,\cdots ,n,h_j=x_{j+1}-x_j$
则 $s^{\prime \prime }(x)=\frac{x_{j+1}-x}{h_j}{M}_j+\frac{x-x_j}{h_j}{M}_{j+1},x\in [x_j,x_{j+1}]$
$$\begin{array}{rl}{s}^{\prime }(x)& =-\frac{(x_{j+1}-x{)}^2}{2h_j}{M}_j+\frac{(x-x_j{)}^2}{2h_j}{M}_{j+1}+c_1,\\ s(x)& =\frac{(x_{j+1}-x{)}^3}{6h_j}{M}_j+\frac{(x-x_j{)}^3}{6h_j}{M}_{j+1}+c_{1}x+c_2,\\ s(x_j)& =\frac{1}{6}{h}_j^2{M}_j+c_1{x}_j+c_2=y_j,\\ s(x_{j+1})& =\frac{1}{6}{h}_j^2{M}_{j+1}+c_1{x}_{j+1}+c_2=y_{j+1},\\ c_1& =\frac{y_{j+1}-y_j}{h_j}-\frac{1}{6}{h}_j(M_{j+1}-M_j),\\ c_2& =\frac{y_j{x}_{j+1}-y_{j+1}{x}_j}{h_j}-\frac{1}{6}{h}_j(x_{j+1}{M}_j-x_j{M}_{j+1}).\end{array}$$

$$s(x)=\frac{(x_{j+1}-x{)}^3}{6h_j}{M}_j+\frac{(x-x_j{)}^3}{6h_j}{M}_{j+1}+\left(y_j-\frac{M_j{h}_j^2}{6}\right)\frac{x_{j+1}-x}{h_j}+\left(y_{j+1}-\frac{M_{j+1}{h}_j^2}{6}\right)\frac{x-x_j}{h_j}$$

$$s^{\prime }(x)=-\frac{(x_{j+1}-x{)}^2}{2h_j}{M}_j+\frac{(x-x_j{)}^2}{2h_j}{M}_{j+1}+\frac{y_{j+1}-y_j}{h_j}-\frac{M_{j+1}-M_j}{6}{h}_j.$$

为了求 $M_0,\cdots ,M_n$，要用导数连续条件：$s^{\prime }(x_j+0)=s^{\prime }(x_j-0)$。
$$\begin{array}{rl}{s}^{\prime }(x_j+0)& =-\frac{h_j}{3}{M}_j-\frac{h_j}{6}{M}_{j+1}+\frac{y_{j+1}-y_j}{h_j},\\ s^{\prime }(x_{j+1}-0)& =\frac{h_j}{6}{M}_j+\frac{h_j}{3}{M}_{j+1}+\frac{y_{j+1}-y_j}{h_j},\\ s^{\prime }(x_j-0)& =\frac{h_{j-1}}{6}{M}_{j-1}+\frac{h_{j-1}}{3}{M}_j+\frac{y_j-y_{j-1}}{h_{j-1}}.\\ \frac{h_{j-1}}{6}{M}_{j-1}+\frac{h_{j-1}+h_j}{3}{M}_j+\frac{h_j}{6}{M}_{j+1}& =\frac{y_j-y_{j-1}}{h_{j-1}}-\frac{y_{j+1}-y_j}{h_j},j=1,\cdots ,n-1,\end{array}$$

$${\mu }_j{M}_{j-1}+2M_j+{\lambda }_j{M}_{j+1}=d_j,j=1,\cdots ,n-1,$$
其中 $d_j=6f[x_{j-1},x_j,x_{j+1}]$，
$${\lambda }_j=\frac{h_j}{h_{j-1}+h_j},{\mu }_j=\frac{h_{j-1}}{h_{j-1}+h_j}.$$

在第一边界条件下：
$$\left[\begin{array}{ccccc}2& 1& & & \\ {\mu }_1& 2& {\lambda }_1& & \\ & \ddots & \ddots & \ddots & \\ & & {\mu }_{n-1}& 2& {\lambda }_{n-1}\\ & & & 1& 2\end{array}\right]\left[\begin{array}{c}{M}_0\\ M_1\\ ⋮\\ M_{n-1}\\ M_n\end{array}\right]=$$
$$$\left[\begin{array}{c}{d}_0\\ d_1\\ ⋮\\ d_{n-1}\\ d_n\end{array}\right]$$

$$\begin{gathered} {\lambda }_0=1,{\mu }_n=1, \\ {d}_0=\frac{6}{h_0}\left(f[x_0,x_1]-f_0^{\prime }\right), \\ {d}_j=6\frac{f[x_j,x_{j+1}]-f[x_{j-1},x_j]}{h_{j-1}+h_j}=6f[x_{j-1},x_j,x_{j+1}],j=1,2,\dots ,n-1, \\ {d}_n=\frac{6}{h_{n-1}}\left(f_n^{\prime }-f[x_{n-1},x_n]\right). \end{gathered}$$
第二边界条件矩阵方程
$$\left[\begin{array}{cccc}2& {\lambda }_1& & \\ {\mu }_2& 2& {\lambda }_2& \\ & \ddots & \ddots & \ddots \\ & & {\mu }_{n-1}& 2\end{array}\right]$$
$$\left[\begin{array}{c}{M}_1\\ M_2\\ ⋮\\ M_{n-1}\end{array}\right]=$$

$$\left[\begin{array}{c}{d}_1-{\mu }_1{f}_0^{\prime \prime }\\ d_2\\ ⋮\\ d_{n-1}-{\lambda }_{n-1}{f}_n^{\prime \prime }\end{array}\right]$$
边界条件约束：
$$\{\begin{array}{l}{M}_0=f_0^{\prime \prime },\\ M_n=f_n^{\prime \prime }.\end{array}$$

第三边界条件（周期边界条件）矩阵方程
$$\left[\begin{array}{ccccc}2& {\lambda }_1& & & {\mu }_1\\ {\mu }_2& 2& {\lambda }_2& & \\ & \ddots & \ddots & \ddots & \\ & & {\mu }_{n-1}& 2& {\lambda }_{n-1}\\ {\lambda }_n& & & {\mu }_n& 2\end{array}\right]\left[\begin{array}{c}{M}_1\\ M_2\\ ⋮\\ M_{n-1}\\ M_n\end{array}\right]=$$

$$\left[\begin{array}{c}{d}_1\\ d_2\\ ⋮\\ d_{n-1}\\ d_n\end{array}\right]$$

特殊约束条件
$$\{\begin{array}{l}{x}_0=x_n(\text{周期条件}),\\ M_0=M_n(\text{弯矩周期约束}),\\ {\mu }_n{M}_{n-1}+2M_n+{\lambda }_n{M}_1=d_n(\text{闭环方程}).\end{array}$$

参数定义
$$\begin{array}{rl}{\mu }_n& =\frac{h_{n-1}}{h_{n-1}+h_0}(\text{末节点弯矩传递系数}),\\ {\lambda }_n& =\frac{h_0}{h_{n-1}+h_0}(\text{首节点弯矩传递系数}),\\ d_n& =6f[x_{n-1},x_n,x_1](\text{三阶差商计算}).\end{array}$$

误差界与收敛性

设 $f(x)\in C^4[a,b]$，$S(x)$ 满足第一或第二边界条件，
令 $h=\underset{0\le i\le n-1}{\max }{h}_i$，其中 $h_i=x_{i+1}-x_i$，则有估计式：
$$\underset{a\le x\le b}{\max }\left|f^{(k)}(x)-s^{(k)}(x)\right|\le C_k\left(\underset{a\le x\le b}{\max }\left|f^{(4)}(x)\right|\right)h^{4-k}$$
其中常数项系数为：
$$\{\begin{array}{l}{C}_0=\frac{5}{384},\\ C_1=\frac{1}{24},\\ C_2=\frac{3}{8}\end{array}(k=0,1,2).$$