数值分析

参考清华大学出版社的《数值分析与算法（第3版）》和慕课上东北大学的数值分析课件，快来看看吧！

数值分析

• 1.绪论
  • 误差来源和分类
    • 模型误差
    • 观测误差
    • 截断误差
      • 求解数学模型所用的数值方法通常是一种近似方法，这种因方法产生的误差称为
    • 舍入误差
      • 由于计算机只能对有限位数进行运算，在运算中像 等都要按舍入原则保留有限位
    • 在数值分析中，我们总假定数学模型是准确的，因而不考虑模型误差和观测误差，主要研究截断误差和舍入误差对计算结果的影响
  • 有效数字
  • 数值计算原则
    • 1.避免两个相近的数相减
      • 方法一：改变算法
      • 方法二：若找不到适当方法代替，在计算机上采用双倍字长计算，以提高精度
    • 2.防止大数吃掉小数
      • 方法：在求和或求差的过程中采用有小到大的运算过程
    • 3.绝对值太小的数不宜做除数
    • 4.简化计算程序，减少计算次数
    • 5.选用数值稳定性好的算法
• 2.解线性方程组的直接方法
  • 顺序高斯消去法
    • 顺序高斯消去法又叫高斯消去法，是一种规则化的加减消元法，其基本思想是通过逐次消元计算，把一般线性方程组的求解转化为等价的上三角方程组的求解
  • 列主元高斯消去法
    • 为了提高计算的数值稳定性，在消元过程中采用选择主元的方法。常采用的是列主元消去法和全主元消去法
    • 只要IAI≠0，列主元高斯消去法就可以顺利进行。
  • 直接三角分解法
    • 相较于高斯消去法，在方程右端项发生变化的时候，LU分解只需要执行前代和回代过程即可，而高斯消去法要重复消去过程，计算量直接翻倍
    • Doolittle分解方法，将L和U放在同一个矩阵，L的主对角元素为1，如果矩阵L对角元不进行单位化，称为Courant分解。
  • 平方根法
  • 追赶法
  • 范数
  • 向量范数
    • 非负性、其次性、三角不等式
  • 矩阵范数
    • 子主题
• 3.解线性方程组的迭代法
  • 一阶定常迭代法
    • 下面三种都属于一阶定常迭代法，由于雅可比需要将主对角元作为分母，G-S和SOR都是由雅可比扩展得到，所以这三种都要求主对角元不为0
    • 一阶定常迭代收敛的条件是迭代矩阵的谱半径小于1
    • 雅可比迭代法
    • 高斯-赛德尔迭代
    • SOR迭代
      • 计算结果与前一步结果加权平均，ω为松弛因子，ω＝1时，就是G-S迭代，ω=0时，解不会变化，没有意义
  • 共轭梯度法
    • 最速下降法
      • 这种将对称正定线性方程组的求解问题转换为求多元二次函数最小值问题的方法称为变分原理
    • 共轭梯度法
      • 因为最速下降法只搜索重复的方向，而没有搜索全局
• 4.非线性方程求根
  • 线性方程是方程式中仅包含未知量一次方项和常数项的方程，除此之外的方程都是非线性方程
  • 二分法
  • 简单迭代法
    • 不动点迭代法
    • • 这是全局收敛条件，还有局部收敛的概念
      • 条件1保证φx的值在定义域内
      • 条件2说明曲线变化缓慢
    • • 收敛阶越高越好
  • 牛顿迭代法
    • 至少二阶收敛
    • 无法保证全局收敛要求二阶连续导数每步迭代要计算导数，计算量大
  • 牛顿下山法
    • 又叫阻尼牛顿法
    • 防止初始值偏离解导致发散，只有λ接近1才能保证超线性收敛速度
  • 牛顿迭代法变形
    • 简化牛顿迭代法
      • 线性收敛
    • 平行弦法
      • 仅仅在x0处计算导数，之后通过做平行弦求解
      • 收敛性差
    • 割线法
      • 用差商近似导数，避免了导数计算，1.618阶收敛，但是需要两个初始值
    • 通过将导数替换成近似导数，拟牛顿法
    • 求重根的牛顿迭代法
• 5.插值与逼近
  • 函数插值
    • 可视为特殊的函数逼近问题，要求在插值节点处误差函数的值为0
    • 多项式插值法
      • 拉格朗日插值法
        • 优点：结构对称，便于理论分析但是，如果增加或减少一个插值节点，公式变化较大
      • 牛顿插值法
      • 多项式插值通过构造单个多项式，满足所有的插值要求，得到的插值函数光滑性好，易于进行理论分析，但是在插值节点较多时，构造出的插值多项式往往存在以下缺点
        • 收敛性差
          • 龙格现象
        • 保凸性差
        • 数值稳定性差
    • 分段线性插值
      • 但是在导函数上不连续
    • 分段埃尔米特插值
      • 插值条件不仅仅是函数值，还考虑导数甚至高阶导的插值要求，得到的插值多项式为埃尔米特插值多项式
      • 两点三次埃尔米特插值
      • 分段埃尔米特插值一阶导数连续，但是需要一阶导数已知，这在实际中很难办到，一种办法是根据已有数据求导数，利用一阶差商，为保形分段插值
    • 样条插值函数
      • 属于分段多项式插值，具有更高阶的光滑性
      • 三次样条插值
        • 函数由分段三次多项式拼接而成，具有整体的二阶光滑性
  • 连续函数逼近
    • 最小二乘逼近
      • 法方程方法
        • 意义为，在逼近函数类中，这一平面上，各个基方向上，逼近函数与原函数有相同的投影
        • 基函数选取不当会导致法方程系数矩阵病态，比如单项式函数（1，x，x²...）当n较大时，法方程的系数矩阵高度病态
        • 用正交函数族做最佳平方逼近
          • 系数矩阵退化为对角矩阵
          • 计算方便，算法稳定性好，便于基函数的增加、删除
  • 离散数据曲线拟合
    • 最小二乘法
      • 同函数逼近过程，为了避免矩阵病态，构造正交基函数
      • 区别在于，无法利用已知的正交函数族
• 6.数值积分与数值微分
  • 数值积分
    • 机械求积公式
    • 牛顿-柯特斯公式
      • 在积分区间上取等距节点，构造插值型求积公式，为牛顿-柯特斯公式
      • 常用的低阶牛顿-柯特斯公式
        • 梯形公式（n=1）
        • 辛普森公式（n=2）
        • 柯特斯公式（n=4）
      • 高阶牛顿-柯特斯公式是不稳定的
    • 复合求积法
      • 复合梯形公式
      • 复合辛普森公式
    • 龙贝格积分算法
      • 以复合梯形求积公式的误差展开式为依据，在形成步长逐次减半的梯形值序列的同时，通过查尔斯外推法构造收敛阶更高的值序列
      • 对被积函数的光滑性要求很高
      • 且只适于等距节点
    • 高斯求积公式
      • 高斯点为正交多项式的零点
      • 函数逼近中，有提出正交函数族
      • 不同正交多项式有不同的高斯求积公式
        • 高斯-勒让德求积公式
  • 数值微分
    • 有限差分公式
      • 利用差商构造数值微分公式
      • 向前差分公式
      • 向后差分公式
      • 具有一阶准确度
      • 中心差分公式
        • 具有二阶准确度
    • 插值型求导公式
      • 根据离散点上的值构造插值多项式，用插值多项式的导数近似
      • 两点插值
      • 三点插值
    • 数值微分的外推算法
      • 与有梯形求积公式外推得到更高阶的积分公式类似
      • 利用查尔斯外推技术得到更准确的导数值
• 7.常微分方程数值解法
  • 常微分方程ODE ordinary differential equation，未知函数是单变量函数
    • 显式常微分方程
    • 隐式常微分方程
  • 偏微分方程PDE partial differential equation
  • 大多数常微分方程组都无法解析求解，只能得到解的数值近似。数值解与解析解有很大差别，它是解函数在离散点集上近似值的列表，因此求解常微分方程的数值方法也称为离散变量法
    • 数值解常采用步进式的计算过程，单步法和多步法
  • 有限差分法
    • • • 欧拉法
          • 最简单的常微分方程初值问题解法
          • 是一种显格式单步法
• 奇异矩阵
  • 讨论非奇异矩阵与奇异矩阵的前提：该矩阵A为方阵，即n=m,行列数相等，非方阵矩阵谈不上奇异与非奇异。
  • 判断矩阵A行列式是否为0，若行列式|A|=0,则矩阵A为奇异矩阵
• 步长折半的复合求积公式