数值分析

这是一篇关于数值分析的思维导图，包含矩阵特征值、 误差分析、非线性方程组求根、 插值、线性方程组数值解等。

数值分析

误差分析

绝对误差

相对误差

误差产生的原因

相近数字相减

参与运算的数量级相差过大

除数绝对值小于被除数绝对值

稳定性

迭代中的误差放大缩小问题

误差传播

估计式

四则运算误差

有效数字

插值

多项式插值

Haar条件

插值多项式的性质

对n+1个点进行n次插值得到的多项式是唯一的

于是余项也是唯一的

当原函数为不超过n次的多项式时，通过n+1个点构造的n次多项式就是原函数

Lagrange插值

插值基

插值多项式

余项

Newton插值

插值多项式

差商

递推公式

与导数的关系

对称性

差商表

Hermite插值

基于Lagrange插值的Hermite插值

在给定点的函数值和导数值均已知

插值多项式

余项

部分给定点的导数值未知

设前m个点导数值已知

插值多项式

余项

分段插值

样条插值

三弯矩方程

三转角方程

二元插值

双二次插值

双三次插值

双三次Hermite插值

拟合

最佳平方逼近

法方程（正规方程）

基向量

Legendre多项式

定义

正交性

在ρ(x)=1时正交

性质

n为奇数时多项式为奇函数,n为偶数时多项式为偶函数

递推公式

前几项

Chebyshev多项式

定义

正交性

性质

n为奇数时多项式为奇函数,n为偶数时多项式为偶函数

递推公式

前几项

Laguerre多项式

Hermite多项式

误差估计

离散数据

正交基的选取

最佳一致逼近

偏差

正偏差点

负偏差点

取到极限误差的点

Chebyshev定理

最佳一致逼近多项式一定同时存在正、负偏差点

Chebyshev交错组

最佳一致逼近多项式的唯一性

性质

最佳一致逼近多项式是一个Lagrange插值多项式

连续函数的一次最佳一致逼近多项式

高次多项式的低次最佳一致逼近多项式

微分方程数值解

常微分方程

Euler法

Taylor法

Runge-Kutta法

偏微分方程

抛物型

前向差分

后向差分

双曲型

椭圆型

有限差分

数值积分

代数精度

若公式对不超过m次的多项式进行积分都是准确的称其具有m次代数精度

数值稳定性

机械型求积公式的系数都为正数时稳定

机械型求积公式

计算方法

矩形公式

梯形公式

插值型求积公式

计算方法

取一个n次插值多项式进行积分

误差

Newton-Cotes公式

h=(b-a)/n

计算方法

取等距节点的插值型求积公式

Cotes系数

定义

性质

n>=时出现负数,此时公式不稳定

代数精度

n为奇数时至少具有n次代数精度

n为偶数时至少具有n+1次代数精度

积分余项

n为偶数

n为奇数

特殊情况

梯形公式

Simpson公式

Cotes公式

复化求积法

特殊情况

复化梯形公式

复化Simpson公式

复化Cotes公式

龙贝格积分法

依次修正的过程

Rn与8次Newton-Cotes公式不相等

高斯型求积公式

计算方法

代数精度

2n+1

余项

特殊情况

Gauss-Legendre求积公式

Gauss-Chebyshev求积公式

数值微分

插值型微分公式

两点公式

三点公式

五点公式

二维导数

向前差分

向后差分

中心差分

线性方程组数值解

条件数

定义

见矩阵范数

性质

条件数越大，扰动误差越大

非奇异矩阵条件数均大于等于1

高斯消元法

高斯主元消去法

选用余下行中主元素绝对值大的行

主元素绝对值小会造成误差

Gauss-Jordan消去法

三角分解法

LU分解

L为单位下三角矩阵,U为上三角矩阵

存在唯一性

矩阵各阶顺序主子式非零时具有唯一LU分解

Doolittle分解

LU分解的紧凑格式

对称矩阵的分解

对称正定矩阵的分解

Cholesky分解

平方根法

改进平方根法

三对角矩阵的分解

追赶法

迭代法

Jacobi迭代法

对角元均非0

加性分解

A=L+D+U

向量形式

表达式中会有“洞”

收敛的充要条件

A和2D-A均对称正定

Gauss-Seidel迭代法

向量形式

超松弛迭代法（SOR法）

ω<1时称为欠松弛迭代法,ω>1时称为超松弛迭代法,ω=1时为Jacobi迭代法(或Gauss-Seidel迭代法)

同步迭代

异步迭代

收敛的必要条件

0<ω<2

收敛条件

迭代法收敛当且仅当H的谱半径小于1

迭代法收敛的充分条件为算子范数小于1

特殊情况

行严格对角占优矩阵的Jacobi迭代法和Gauss-Seidel迭代法收敛

对称正定矩阵的Gauss-Seidel迭代法收敛

0<ω<2,A为对称正定矩阵则A的SOR法收敛

0<ω<=1,A为行严格对角占优矩阵则A的SOR法收敛

非线性方程组求根

迭代法

Newton迭代法

与最优化的Newton迭代有类似的结论

下山法

λ从1开始减半搜索，找到使单调条件成立的值

弦截法

抛物线法（Muller法）

收敛性

对于单根具有2阶收敛速度

Aitken法

将点附近的导数视作常数，通过两个点估计出来

收敛速度

定义

充分条件

代数方程求根

秦九韶算法

Newton算法

劈因子法

收敛性

局部收敛性

矩阵特征值

Gerschgorin定理

Rayleigh商

定义

性质

幂法

用于计算主特征值和对应特征向量

规范化幂法

加速方法

原点位移法

Rayleigh商加速

A为对称矩阵

反幂法

原点位移法

收敛条件

Jacobi法

要求矩阵对称

计算方法

即乘以旋转矩阵使非对角元尽量为0

收敛性

Jacobi过关法

QR算法

用于计算所有特征值

QR分解

Gram-Schmidt法

Givens变换法

Householder变换法

即使用反射变换使每一行只剩两个元素非零

计算方法

原点位移

二分法