数值分析笔记
求解方程
二分法
时间复杂度:
定义1.5 令
定理1.6 假设函数
根据定理1.6,近似误差之间的关系
定义1.7 如果迭代方法对于一个足够接近
定理1.6的结论是当
如果误差小于
,解精确到小数点后 位.
牛顿法
用
二次收敛性
定义 令
定理 令
重根问题和改进的Newton方法
Newton方法不能二次收敛到重根,如
定理
定理 若已知
或者可以通过计算
割线法
思想是用差商代替Newton法中的导数. 取
它满足超线性收敛
一般当
事实上对于割线法的收敛阶有(当
插值
数据和插值函数
对
方便的做法是利用Newton差商.
Newton插值多项式
插值误差
龙格现象
略,大一上写过文章.
Hermite插值
Chebyshev插值
希望找到最佳的一致逼近
取
Chebyshev多项式 满足
令
三次样条插值
- 自然三次样条:
. - 曲率调整样条:
. - 钳制边界条件:
. - 抛物线端点的三次样条:
. - 非纽结三次样条:
误差:设
Bezier曲线
最小二乘
离散
给定函数
给定
有时
而
数据线性化
连续
在一般的Euclid空间中,给定函数
权函数和正交基
权函数
最小二乘问题
给定函数
如果
Gram-Schmidt 正交化过程
是想把
设
当
首一性还可以得到以下性质
QR分解
完全QR分解 对于
计算的复杂度为
Gram-Schimidt 正交
朴素的和改进的版本p194
过程需要大约
计算
Householder 反射
令
设
其实每步选模长的正负号时应该与原位置的正负号相反,书上忽略了这一点.
Householder变换做QR分解的复杂度
只考虑向量与向量相乘,矩阵与向量相乘,矩阵与矩阵相乘的计算 对
- 若还需要Q,则大约需要
次乘法和加减法.
QR decompositon - Wikipedia https://en.wikipedia.org/wiki/QR_decomposition
数值微分和积分
数值微分
有限差分公式
二点前向差分公式
如果误差是
三点中心差分公式(二阶中心差分公式)
五点中心差分公式
二阶导数的三点中心差分公式
舍入误差
以三点中心差分公式为例,加上机器误差,总误差的绝对值上界是
外推
如果有
一个例子是用二阶中心差分公式进行外推,得到的其实是四阶公式.
且误差项仅和
数值积分
基本上都是用插值公式和误差导出积分的公式和误差.
梯形法则
Simpson法则
误差的证明
首先误差
另一方面,用Newton插值,可以认为再在
这下可以使用积分中值定理了,计算得到
从该表达式知Simpson法则的代数精度为3.
3阶Newton-Cotes公式(Simpson3/8公式)
复合梯形法则
对于
数值精度是2阶,代数精度是1阶.
复合Simpson公式
如果
注意使用
舍入误差对复合积分公式的影响
中点法则
当
Taylor展开至二阶即可得到误差. 与梯形法则相比,中点法则的误差只有一半.
复合中点法则
另一个开Newton-Cotes法则
Romberg积分
一个表格
其中
这里
Romberg积分第二列最后一项和复合Simpson法则的结果一致. 事实上,Romberg积分的第一列定义为连续的复合梯形法则,第二列是复合Simpson项,即复合梯形法则的外推是复合Simpson法则.
Romberg积分的常用停止条件是计算新的一行直到相邻的对角线元素
自适应积分
为什么要自适应: - 高阶导数不易计算 - 有些区域变化缓慢
高斯积分
高斯积分具有
三点Gauss积分
关于正交多项式系,有这样的定理:
如果
证明可以参考
多项式以及相关内容 https://zhuanlan.zhihu.com/p/270620896
### 正交多项式 |
Legendre多项式:在 |
这里Legendre多项式非首一,而是满足 |
正交性: |
奇偶性: |
若令 |
更多关于正交多项式还可以参考 |
逆问题解析 https://zhuanlan.zhihu.com/p/352724194
还有一类正交多项式Laguerre多项式,其对应的权函数
接下去我们要证明插值节点恰为Legendre多项式的根,这跟首项系数无关.
高斯积分
我们想用
定理:Gauss积分方法,在
并不需要解那个很复杂的非线性方程组,只要说明Gauss积分方法能够具有
阶代数精度,就可由唯一性得知它就是最好的插值法. 然而事实上Lengdre多项式的根确实是那个很复杂的非线性方程组的根,这一点很难直接证明.
在一般区间
Gauss积分的误差:
可以考虑
Gauss-Chebyshev 积分
权函数
此时希望
反常积分的计算
尝试利用数值方法计算
该积分有一个奇点
最简单的想法
高维积分的计算
这会牵扯到许多极限换序和收敛性的问题.
特征值与奇异值
Gerschgorin 圆盘定理 略
幂迭代法
幂迭代法线性收敛
Rayleigh商 如果有近似特征向量
定理:设
先取逆再进行幂迭代可以得到绝对值最小的特征值(注意特征向量不变).
为了避免对矩阵
逆向幂迭代
p469
Rayleigh商迭代(RQI)
可利用Rayleigh商估计最大特征值,Rayleigh商迭代对称矩阵三次收敛,一般则二次收敛.
QR算法
- 利用Householder变换
作相似约化:对称阵约化为三对角,非对称阵约化为上Hessenberg矩阵 - 利用QR分解构造迭代序列. 分解
,计算
约化到上Hessenberg矩阵大约
SVD
对称矩阵的SVD简化为
低秩逼近
另一种SVD的方法
考虑
其他SVD相关性质
Frobenius范数:
设
数值代数
方程组的求解——高斯消去法和LU分解
朴素的Gauss消去法
再经历回代的操作,回代计算复杂度是
如果某时主元为0,会导致Gauss消去法终止.
LU分解
如果
一般 LU 分解的复杂度是
LU分解相比经典的 Gauss 消去法,更适合求解
矩阵范数
- 算子范数
- 无穷范数
有 范数 有 ; 对任意满足相容性的范数成立
误差放大和条件数
令
定义
方阵
的条件 cond( ) 为最大的误差放大因子. 阶矩阵 的条件数为 一般可以取无穷范数
线性方程组-迭代法 0.2:条件数 https://zhuanlan.zhihu.com/p/388053510
Q: 证明矩阵
证: 注意误差放大因子
PA=LU 分解
淹没问题 p80
部分主元 第一步选择第
然后
迭代方法
不动点迭代:
设
连续松弛迭代(SOR) - 引入参数
迭代基本定理 设
收敛速度:
定义:
定理:
稀疏矩阵计算
稀疏矩阵:非零元密度远小于1的矩阵. 对于很大的
应用例:有限差分离散泊松方程
Cholesky 分解
如果
证 归纳
共轭梯度法
等价极值问题
定理
证 注意
那么我们就把一个求方程根的问题转化为了一个求函数极小值的问题
最速下降法
每次找一个方向
,使得 其中系数 通过求一维问题的极小获得.若
,则该方向为最速下降方向. 有 ,且 和 正交.
计算可以得到
误差估计
证 用归纳法,然后用Kantorovich不等式,具体推导略. Kantorovich不等式可以见
康托洛维奇(Kantorovich)不等式的一种初等证明 https://zhuanlan.zhihu.com/p/271983329
最速下降法当矩阵条件数过大,即最大与最小特征值相差极大时收敛非常慢,不具有实际应用意义 ### 共轭梯度法
是方向, 是残差(标量), 是经过 步得到的估计
极小问题可迭代计算,每次找方向 ,使 其中系数 通过求一维问题的极小获得搜索方向两两共轭,且
其中的系数由共轭性质确定.
共轭向量 定义
共轭梯度法有误差估计,收敛速度为(K为矩阵条件数)
有限步收敛性定理 设
证 首先
由共轭性质,
而
故
共轭梯度法
选择的搜索方向为负梯度方向和前一个搜索方向的组合,使得所得到的余项与前面的余项两两正交.
负梯度方向即为残差
令
证明实际上
共轭梯度法复杂度还是
总结算法如下 初始:
For (新残差) End For
(下标可能与书本有所不同)
预条件 若
目标是选择合适的矩阵
雅可比预条件子
高斯-赛德尔预条件子
对称连续过松弛(SSOR),中预条件子定义为
经过一些化简可以得到有预条件的算法
初始条件 初始: For (新残差) End For
在SSOR下,不需要求
可以将具备SSOR的共轭梯度法与一般的迭代法作比较.