Runge现象
例 1 . $f(x)=\frac1{1+x^2}, x\in[-5,5]$
解 . $x_i=-5+\frac{i}{10}$ $i=0,1,\cdots,n$
=============== n= 5
Max error at point 0.0 with error 0.4326923076923076
=============== n= 10
Max error at point -4.7 with error 1.9156430502192496
=============== n= 20
Max error at point 4.870 with error 59.768327839903954
=============== n= 40
Max error at point 4.950 with error 104371.93698015573
$n=10$
定义 1 . Runge现象
注
=============== n= 5
Max error at cheby point 0.0 with error 0.5559113388123956
=============== n= 10
Max error at cheby point -0.7800000000000002 with error 0.10914672464976671
=============== n= 20
Max error at cheby point -1.1099999999999999 with error 0.01533291731815517
=============== n= 40
Max error at cheby point 0.9500000000000002 with error 0.00028938783946064195
克服Runge现象
分段插值
$\{x_i\}_{i=0}^n$ 分段线性
$[x_{i},x_{i+1}]$
\[p_i(x)=f(x_i)\frac{x-x_{i+1}}{x_i-x_{i+1}}+f(x_{i+1})\frac{x-x_i}{x_{i+1}-x_i}
\]
\[g(x)=\begin{cases}
p_i(x), \quad x\in[x_i,x_{i+1}] \\
\end{cases}
\]
$[x_i, x_{i+1}]$
\[f(x)-p_i(x)=\frac{f''(\xi_i)}{2!}(x-x_i)(x-x_{i+1}) , \xi_i\in(x_i,x_{i+1})
\]
\[\begin{aligned}
|f(x)-g(x)|\leq &\max_{i=0,\cdots,n-1} |\frac{f''(\xi_i)}{2!}(x-x_i)(x-x_{i+1})| \\
\leq &\max_{i=0,\cdots,n-1} |\frac{f''(\xi_i)}{2!}|\left(\frac{x_{i+1}-x_i}2\right)^2
\end{aligned}
\]
$M_2=\max(|f''(x)|)$ $h=\max(x_{i+1}-x_i)$
\[|f(x)-p(x)|\leq \frac{M_2}8 h^2
\]
\[R=|f(x)-p(x)|\leq \frac{M_2}8 h^2
\]
$\displaystyle\lim_{h\to0}R=0$
插值函数整体只有连续性，没有可导性
问题 .
样条插值
定义 2 . 3次样条函数
3次样条插值函数
$(x_i, f(x_i))$ $i=0,1,\cdots,n$ $S(x)$
\[S(x_i)=f(x_i), \quad i=0,1,\cdots,n
\]
$S(x)$ $[x_i, x_{i+1}]$ $s_i(x)$
\[\begin{aligned}
s_i(x) = a_i + b_i x+c_i x^2+d_i x^3,& x\in[x_i, x_{i+1}] , \\
& i=0,1,\cdots,n-1
\end{aligned}
\]
$\{a_i, b_i, c_i, d_i\}$ $4n$
\[\begin{aligned}
s_i(x_i)=f(x_i), &i=0,1,\cdots, n-1 \\
s_i(x_{i+1})=f(x_{i+1}),& i=0,1,\cdots,n-1 \\
s'_i(x_i)=s'_{i-1}(x_i),& i=1,2,\cdots,n-1 \\
s''_i(x_i)=s''_{i-1}(x_i),& i=1,2,\cdots,n-1 \\
\end{aligned}
\]
$4n$ $4n-2$
边界条件 $4n$
m关系式
$m_i, i=0,1,\cdots,n$ $[x_i, x_{i+1}]$ $s_i(x)$
\[\begin{cases}
s_i(x_i)=f(x_i),& s_i(x_{i+1})=f(x_{i+1}) \\
s'_i(x_i)=m_i,& s'_i(x_{i+1})=m_i
\end{cases}
\]
\[\begin{aligned}
s_i(x)=&\frac1{h_i^3}(h_i+2(x-x_i))(x-x_{i+1})^2f(x_i) \\
&+\frac1{h_i^3}(h_i-2(x-x_{i+1}))(x-x_i)^2f(x_{i+1}) \\
&+\frac1{h_i^2}(x-x_i)(x-x_{i+1})^2m_i \\
&+\frac1{h_i^2}(x-x_{i+1})(x-x_i)^2m_{i+1} \\
\end{aligned}
\]
\[s''_i(x_i)=s''_{i-1}(x_i), i=1,2,\cdots,n
\]
\[\begin{aligned}
s''_i(x)=&\frac6{h_i^3}(h_i+2(x-x_{i+1}))f(x_i) \\
&+\frac6{h_i^3}(h_i-2(x-x_i))f(x_{i+1}) \\
&+\frac2{h_i^2}(3(x-x_{i+1})+h_i)m_i \\
&+\frac2{h_i^2}(3(x-x_i)-h_i)m_{i+1} \\
\end{aligned}
\]
\[\begin{aligned}
s''_i(x_i)=&\frac6{h_i^3}(h_i+2(x_i-x_{i+1}))f(x_i) \\
&+\frac6{h_i^3}(h_i-2(x_i-x_i))f(x_{i+1}) \\
&+\frac2{h_i^2}(3(x_i-x_{i+1})+h_i)m_i \\
&+\frac2{h_i^2}(3(x_i-x_i)-h_i)m_{i+1} \\
=&\frac6{h_i}\frac{f(x_{i+1})-f(x_i)}{h_i} \\
&+\frac2{h_i}(-2m_i-m_{i+1}) \\
\end{aligned}
\]
\[\begin{aligned}
s''_i(x_{i+1})=&\frac6{h_i^3}(h_i+2(x_{i+1}-x_{i+1}))f(x_i) \\
&+\frac6{h_i^3}(h_i-2(x_{i+1}-x_i))f(x_{i+1}) \\
&+\frac2{h_i^2}(3(x_{i+1}-x_{i+1})+h_i)m_i \\
&+\frac2{h_i^2}(3(x_{i+1}-x_i)-h_i)m_{i+1} \\
=&-\frac6{h_i}\frac{f(x_{i+1})-f(x_i)}{h_i} \\
&+\frac2{h_i}(m_i+2m_{i+1}) \\
\end{aligned}
\]
$i=1,2,\cdots,n-1$
\[\begin{aligned}
\frac{h_{i}}{h_i+h_{i-1}}m_{i-1}+&2m_i+\frac{h_{i-1}}{h_i+h_{i-1}}m_{i+1} \\
=3\bigg(&\frac{h_{i}}{h_i+h_{i-1}}\frac{f(x_{i})-f(x_{i-1})}{h_{i-1}} \\
&+\frac{h_{i-1}}{h_i+h_{i-1}}\frac{f(x_{i+1})-f(x_{i})}{h_{i}}
\bigg)
\end{aligned}
\]
\[\begin{aligned}
\displaystyle\lambda_i=\frac{h_{i}}{h_i+h_{i-1}}>0, \quad \mu_i=1-\lambda_i \\
c_i=3(\lambda_if[x_{i-1},x_i]+\mu_if[x_i, x_{i+1}])
\end{aligned}
\]
\[\begin{pmatrix}
\lambda_1 & 2 & \mu_1 \\
& \lambda_2 & 2 & \mu_2 \\
& & \ddots & \ddots & \ddots & \\
& & & \lambda_{n-1} & 2 & \mu_{n-1}
\end{pmatrix}
\begin{pmatrix} m_0 \\ m_1 \\ m_2 \\ \vdots \\ m_{n-1} \\ m_n \end{pmatrix}
=\begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_{n-1} \end{pmatrix}
\]
$n+1$ $n-1$
$x_0<x_1<\cdots<x_n$ 边界条件
$x_0$ $x_n$ $m_0$ $m_n$
\[\begin{pmatrix}
2 & \mu_1 \\
\lambda_2 & 2 & \mu_2 \\
& \ddots & \ddots & \ddots \\
& & \lambda_{n-1} & 2
\end{pmatrix}
\begin{pmatrix} m_1 \\ m_2 \\ \vdots \\ m_{n-1} \end{pmatrix}
=\begin{pmatrix} c_1-\lambda_1m_0 \\ c_2 \\ \vdots \\ c_{n-1}-\mu_nm_n \end{pmatrix}
\]
$\lambda_i, \mu_i\in(0,1)$ $(n-1)\times(n-1)$
$x_0$ $x_n$ $M_0$ $M_n$
\[\begin{aligned}
M_n=&s''_{n-1}(x_n)=-\frac{6}{h_{n-1}}f[x_{n-1},x_n]+\frac2{h_{n-1}}(m_{n-1}+2m_n) \\
M_0=&s''_{0}(x_0)=\frac{6}{h_{0}}f[x_{0},x_1]-\frac2{h_{0}}(m_{1}+2m_0)
\end{aligned}
\]
\[\begin{aligned}
m_{n-1}+2m_n =& 3f[x_{n-1},x_n]+\frac{h_{n-1}}2M_n \\
2m_0+m_{1} = &3f[x_0,x_1]-\frac{h_0}2M_0
\end{aligned}
\]
\[\begin{pmatrix}
2 & 1 & \\
\lambda_1 & 2 & \mu_1 \\
& \lambda_2 & 2 & \mu_2 \\
& & \ddots & \ddots & \ddots & \\
& & & \lambda_{n-1} & 2 & \mu_{n-1} \\
& & & & 1 & 2
\end{pmatrix}
\begin{pmatrix} m_0 \\ m_1 \\ m_2 \\ \vdots \\ m_{n-1} \\ m_n \end{pmatrix}
=\begin{pmatrix} 3f[x_0,x_1]-\frac{h_0}2M_0 \\
c_1 \\ c_2 \\ \vdots \\ c_{n-1} \\
3f[x_{n-1},x_n]+\frac{h_{n-1}}2M_n
\end{pmatrix}
\]
$f(x)$ $x_n-x_0$ $f(x_0)=f(x_n)$ $f'(x_0)=f'(x_n)$ $f''(x_0)=f''(x_n)$
\[\begin{aligned}
m_0=&m_n \\
s''_0(x_0)=&s''_{n-1}(x_n)
\end{aligned}
\]
M关系式
m关系式 $M_i$ $i=0,1,\cdots,n$ $[x_{i}, x_{i+1}]$ $s_i(x)$
\[\begin{aligned}
s_i(x_i)=f(x_i), & s_i(x_{i+1})=f(x_{i+1}) \\
s''_i(x_i)=M_i, & s''_i(x_{i+1})=M_{i+1}
\end{aligned}
\]
\[s_i(x)=a_i+b_i(x-x_i)+c_i(x-x_i)^2+d_i(x-x_i)^3
\]
$a_i, b_i, c_i, d_i$
$s_i(x)$ $s''_i(x)$
\[s''_i(x)=M_i\frac{x-x_{i+1}}{x_i-x_{i+1}}+M_{i+1}\frac{x-x_i}{x_{i+1}-x_i}
\]
\[s_i(x)=\frac{M_{i+1}}{6h_i}(x-x_i)^3+\frac{M_i}{6h_i}(x_{i+1}-x)^3+ax+b
\]
$a$ $b$ $a$ $b$
\[\begin{aligned}
s_i(x)=&\frac{M_{i+1}}{6h_i}(x-x_i)^3+\frac{M_i}{6h_i}(x_{i+1}-x)^3 \\
&+c(x_{i+1}-x)+d(x-x_i)
\end{aligned}
\]
\[s'_i(x_i)=s'_{i-1}(x_i) , i=1,2,\cdots,n-1
\]
\[\mu_iM_{i-1}+2M_i+\lambda_iM_{i+1}=d_i, i=1,2,\cdots,n-1
\]
$d_i=6f[x_{i-1},x_i,x_{i+1}]$
作业 $f(x)$ $x_n-x_0$
注 scipy
