计算方法 期末总结

思维导图

绪论

算法的性质：
有穷性、确切性、有输入输出、可行性
算法的描述方法：
自然语言、伪代码、流程图、N-S流程图
算法设计思想：

• 化大为小的缩减技术：二分法
• 化难为易的校正技术：开方法
• 化粗为精的松弛技术：加权平均 超松弛 割圆术

误差来源：

• 模型/描述误差
• 观测误差
• 舍入如茶
• 初值误差

计算方法只研究后两类误差

误差的度量：
绝对误差$e(x^{\ast })=x-x^{\ast }$
绝对误差限$|e(x^{\ast })|=|x-x^{\ast }|<\epsilon$
相对误差$e_r(x^{\ast })=e(x^{\ast })/x\approx e(x^x)/x^{\ast }$
相对误差限
有效数字：
$x^{\ast }=10^m\ast x_1{x}_2{x}_3....x_p$
$|e|<=0.5\ast 10^{m-n}$，则具有n位有效数字
$x^{\ast }$准确到末位时，称有效数

选择算法原则：

• 避免相近的数相减
• 避免很小的数作分母
• 避免大数淹没小数
• 选用稳定性好的算法

插值

用多项式替代真实函数，该多项式存在且唯一（克莱姆法则证明）

拉格朗日插值

$L_n(x)={\sum }_{i=0}^n{\phi }_i(x)y_i={\sum }_{i=0}^n({\prod }_{j=0,j!=i}^n\frac{x-x_j}{x_i-x_j})y_i$
其中，$\phi (x)$是插值基函数
本质上拉格朗日插值函数是加权和
特点：

• 插值点需要等距
• 新点进入需要重新计算基函数
• 高次插值的精度不一定高，可能产生龙格现象

牛顿插值

差商：
零阶差商：$f(x_i)=y_i$
一阶差商：$f(x_i,x_j)=\frac{f(x_j)-f(x_i)}{x_j-x_i}$
二阶差商：$f(x_i,x_j,x_k)=\frac{f(x_j,x_k)-f(x_i,x_j)}{x_k-x_i}$
可用表格法计算差商，对角线上的是系数
牛顿插值多项式：
$p_n(x)=f(x_0)+f(x_0,x_1)(x-x_0)+...+f(x_0,x_1,...,x_n)(x-x_0)(x-x_1)...(x-x_{n-1})$
特点：

• 和拉格朗日插值结果一致
• 不需要重新计算基函数
• 不需要插值点等距

埃米尔特Hermite插值（切触插值）

两点三次插值：
$p_3(x)=y_0{\phi }_0(x)+y_1{\phi }_1(x)+y_0^{\prime }{\psi }_0(x)+y_1^{\prime }{\psi }_1(x)$
其中${\phi }_0(x)=(1+2\frac{x-x_0}{x_1-x_0})(\frac{x-x_1}{x_0-x_1}{)}^2$
${\phi }_1(x)=(1+2\frac{x-x_1}{x_0-x_1})(\frac{x-x_0}{x_1-x_0}{)}^2$
${\psi }_0(x)=(x-x_0)(\frac{x-x_0}{x_0-x_1}{)}^2$
${\psi }_1(x)=(x-x_1)(\frac{x-x_0}{x_1-x_0}{)}^2$
特点：

• 具有导数值

分段插值

大一统的方法，在段内，想用哪种插就用哪种插！

数值积分

正统方法是牛顿-莱布尼茨公式，但是我们又算不出来，不想算，咋办呢

代数精度

一个公式，对于不超过m次的任意多项式都准确，但对m+1次有不准确的，那么具有m阶代数精度。
简化一下，用1，x，$x^2$往里带就行

机械求积

${\int }_a^{b}f(x)dx=(b-a){\sum }_{i=0}^n{\lambda }_{i}f(x_i)$ 加权和

梯形求积公式

${\int }_a^{b}f(x)dx=(b-a)/2(f(a)+f(b))$

牛顿-科特斯公式

将求积区间[a,b]划分为n等分，用等分点构造拉格朗日插值，用L(x)代替f(x)

n	求积系数1	求积系数2	求积系数3	求积系数4	求积系数5
1	1/2	1/2
2	1/6	4/6	1/6
3	1/8	3/8	3/8	1/8
4	7/90	16/45	2/15	16/45	7/90

其中n=1为梯形求积公式，n=2为辛普森公式，n=4为科特四公式
奇数的代数精度和前一个偶数一样，所以正常人没人用奇数的
代数精度分别为1，3，3，5

复化求积公式

跟分段插值一样
复化梯形：$I=\frac{b-a}{2n}(f(a)+2{\sum }_{i=1}^{n-1}f(x_i)+f(b))$
复化辛普森公式：$I=\frac{b-a}{6n}(f(a)+4{\sum }_{i=0}^{n-1}f(x_{i+1/2})+2{\sum }_{i=1}^{n-1}f(x_i)+f(b))$
复化柯特斯公式：$I=\frac{b-a}{90n}(f(a)+32{\sum }_{i=0}^{n-1}f(x_{i+1/4})+12{\sum }_{i=0}^{n-1}f(x_{i+1/2})+32{\sum }_{i=0}^{n-1}f(x_{i+3/4})+14{\sum }_{i=1}^{n-1}f(x_i)+7f(b))$

龙贝格算法(kao)?

$T_1=(b-a)/2(f(a)+f(b))$ 一个梯形
$T_{2n}=1/2T_1+2/h{\sum }_{i=0}^{n-1}f(x_{i+1/2})$
$S_n=4/3T_{2n}-1/3T_n$
$C_n=16/15S_{2n}-1/15S_n$
$R_n=64/63C_{2n}-1/63C_n$

高斯公式

求积节点不是等分，而是一些特殊点
${\int }_a^{b}f(x)dx=\frac{b-a}{2}{\int }_{-1}^{1}g(t)dt$，见资料积分区间转换
一点：${\int }_{-1}^{1}f(x)dx\approx 2f(0)$
两点：${\int }_{-1}^{1}f(x)dx\approx f(-\frac{1}{\sqrt{3}})+f(\frac{1}{\sqrt{3}})$
三点：${\int }_{-1}^{1}f(x)dx\approx \frac{5}{9}f(-\sqrt{\frac{3}{5}})+\frac{8}{9}f(0)+\frac{5}{9}f(\sqrt{\frac{3}{5}})$
一般积分区间的高斯公式

方程求根的迭代法

$x_{k+1}=\phi (x_k)$
导数的绝对值<=1时，收敛

开方算法

$x_0>0$
$x_{k+1}=\frac{1}{2}(x_k+\frac{a}{x_k})$

牛顿法（重点）

泰勒展开前两项，得到$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$
使用条件：

• 介值定理
• f’(x)!=0
• f’'(x)存在且不变号
• x0选点必须使得f’'(x)f(x0)>0

如此才能收敛

收敛速度

$\frac{e_{k+1}}{e_k^p}$->C 则迭代过程是p阶收敛的
牛顿法为平方收敛

牛顿下山法

要求|函数值|单调下降
得到$x_{k+1}=x_k-\lambda \frac{f(x_k)}{f^{\prime }(x_k)}$
$0<\lambda <1$，称下山因子，逐步探索下山因子，从1开始，如果有一步始终找不到，则重选初值

（单点）弦截法

令$f^{\prime }(x_k)\approx \frac{f(x_k)-f(x_0)}{x_k-x_0}$，用割线代替切线

快速/两点 弦截法

需要两个初值x0和x1

埃特金迭代公式

$\overline{x_{k+1}}=\phi (x_k)$ 牛顿一次
$\widetilde{x_{k+1}}=\phi (\overline{x_{k+1}})$ 再牛顿一次
$x_{k+1}=\widetilde{x_{k+1}}-\frac{(\widetilde{x_{k+1}}-\overline{x_{k+1}}{)}^2}{\widetilde{x_{k+1}}-2\overline{x_{k+1}}+x_k}$ 奇怪的加权！

线性方程组的迭代法

Jacobi

$x_{k+1}=-D^{-1}(L+U)x+D^{-1}b$
移过去，用xk算

Gauss-Seidel

$x_{k+1}=-(D+L{)}^{-1}Ux+(D+L{)}^{-1}b$
移过去，用$x_{k+1}$算

收敛判断

Jacobi迭代法和Gauss-Seidel迭代法的收敛性

范数

向量的1范数=x绝对值之和
2范数=欧氏距离
无穷范数=绝对值的最大值

矩阵的1范数是列范数，对每列的绝对值求和，找个最大的列
2范数是谱范数 $||A|{|}_2=\sqrt{{\lambda }_{max}(A^{T}A)}$
无穷范数是行范数，也许因为它是横着的吧(?

谱半径：A绝对值最大的特征值
对任意矩阵范数，谱半径都<=范数，所以范数要是<1，迭代法是不是就必然收敛了呢~

线性方程组的直接法

高斯消元法

化成上下三角形，这也要说？

列主元消元法

换行再消元

矩阵分解法

可以分解为LU 一个下三角和一个上三角的乘积，其中一个是单位的

• Doolittle分解法
  先横着算u，再竖着算l
• crout分解法
  先竖着算l，再横着算u

有公式但是记不住，现推吧

• 平方根法分解 A=$L{L}^T$ 有公式
• Cholesky分解 正定矩阵分解为$A=LD{L}^T$代价<平方根
• 追赶法 三对角矩阵适用 消元+回代

常微分方程的差分法

欧拉格式

向前的$y(x_{n+1})\approx y(x_n)+hf(x_n,y(x_n))$
向后的（隐式）$y(x_{n+1})\approx y(x_n)+hf(x_{n+1},y(x_{n+1}))$
两步$y(x_{n+1})\approx y_{n-1}+2hf(x_n,y(x_n))$ 无法直接启动
梯形格式 $y(x_{n+1})\approx \frac{h}{2}(f(x_n,y(x_n))+f(x_{n+1},y(x_{n+1}))$这也是隐式的，也没法用（二阶）

改进的欧拉格式

二阶代数精度
先预报，再校正
预报值$\overline{y(x_{n+1})}=y(x_n)+hf(x_n,y(x_n))$
校正值$y(x_{n+1})\approx y(x_n)+\frac{h}{2}(f(x_n,y(x_n))+f(x_{n+1}\overline{y(x_{n+1})})$
可以简化表示为：