计算方法.md

二、插值(关注误差)

1. 拉格朗日插值

拉格朗日插值权重： $l_i(x)=\prod_{{j\neq i}{j=0}}^{n}\frac{x-x_j}{x_i-x_j}$ 拉格朗日插值函数： $L_n(x)=\sum_{i=0}^{n}l_i(x)y_i$

2.牛顿插值(为增删节点方便)

差商： $f[x_i,x_j]=\frac{f(x_i)-f(x_j)}{x_i-x_j}\space\space\space\space(i\neq j,x_i\neq x_j)$ $f[x_i,x_j,x_k]=\frac{f[x_i,x_j]-f[x_j,x_k]}{x_i-x_k}\space\space\space\space(i\neq k)$ 公式： $f(x)=f(x_0)+fx_0,x_1+fx_0,x_1,x_2(x-x_1)+\cdots+fx_0,\cdots,x_n\cdots(x-x_{n-1})+fx,x_0,\cdots,x_n\cdots(x-x_{n-1})(x-x_n))$ 余项特性： $R_n(x)=\frac{f^{n+1}(\xi)}{(n+1)!}w_{n+1}(x)$ $\left|R_n(x)\right|\leq \frac{M}{(n+1)!}w_{n+1}(x)$ $M=max_{a\leq x\leq b}|f^{n+1}(x)|$

3.分段线性插值(为避免Runge现象)

n=1:线性插值
n=2:抛物插值

4.三阶厄米插值(三点一导数情况非常重要)

例：设$x_0\neq x_1\neq x_2$，已知$f(x_0)$、$f(x_1)$、$f(x_2)$和$f'(x_1)$，求多项式$P(x)$满足$P(x_i)=f(x_i)$，$i=0,1,2$且$P'(x_1)=f'(x_1)$，并估计误差。
权重的计算公式： $h_i(x)=[1-2l_i'(x_i)(x-x_i)]l_i^2(x)$
$\hat{h_i}(x)=(x-x_i)l_i^2(x)$
插值公式：
$P_3(x)=\sum_{i=0}^{2}h_i(x)f(x_i)+\hat{h_k}(x)f'(x_k)$

5.牛顿前插、后插公式

6.快速Fourier变换

三、积分(关注代数精度)

代数精度：

$f(x)=x^i\space\space\space\space i=0,1,\cdots ,m$精确成立，$f(x)=x^{m+1}$不精确成立，则有m次代数精度

1.插值积分

矩形积分(0次)

$\int_{a}^{b}f(x)dx=(b-a)f[\theta a+(1-\theta)b]$

梯形积分(1次)

$\int_{a}^{b}f(x)dx=\frac{b-a}{2}[f(a)+f(b)]$

Simpson积分(3次)

$\int_{a}^{b}f(x)dx=\frac{b-a}{6}[f(a)+4f(\frac{a+b}{2})+f(b)]$

插值积分(N+1个节点至少N次)

$\int_{a}^{b}f(x)dx=\sum_{n=0}^{N}A_nf(x_n)\space\space\space\space A_n=\int_{a}^{b}ln(x)dx$

Newton-Cotes公式