数值计算

数值计算指有效使用数字计算机求数学问题近似解的方法与过程，以及由相关理论构成的学科。数值计算主要研究如何利用计算机更好的解决各种数学问题，包括连续系统离散化和离散形方程的求解，并考虑误差、收敛性和稳定性等问题。本思维导图是对计算方法的总结，可以用于高数，线性代数等学习中！

数值计算

• 非线性方程
  • 求一元非线性方程根的三个步骤
    • 判断根的存在性
    • 确定根的初始近似值
    • 根的精确化
  • 逐步扫描法确定方程初始近似根
    • f(x0)f(x0+h)<0,
      • 是 x*必在(x0, x0+h)中，故取x0或x0+h作为初始近
      • 否 x0=x0+h，继续扫描
  • 近似根逐步精确化
    • 二分法
      • 计算步骤
        • y=fa ,x=(a+b)/2 if (fx==0) over else if(y*fx<0) x=b （后半段） else x=a（前半段）
        • b-a<ε break
      • 误差分析
        • |x*-xk|<=(b-a)/2^(2k+1)<=ε
    • 迭代法
      • 基本思想
        • f(x)=0 变成->x=g(x)
          • Xk=g(xk-1) ，k=1，2... |Xk–Xk-1|<ε为近似值
      • 收敛条件
        • 利用迭代法的几何意义
        • |g´(x)|≤q<1
      • 误差估值定理
        • |x*- xk| ≤|xk-xk-1|q/(1-q)≤|x1-x0|qk/(1-q)
    • 牛顿迭代法（牛顿切线法）
      • 基本思想
        • Taylor f(x)≈f(xk) + f ´(xk)(x-xk)
      • 公式
        • xk+1=xk–f(xk)/f ´(xk) 也即g(x)=x–f(x)/f ´(x)
      • 几何意义
        • 逐次用切线与x轴的交点来逼近曲线 y=f(x)与x轴的交点x*;
      • 初值选择
        • 使f(x0)与f " (x0)同号，即 f(x0)f "(x0)>0不仅可以保证牛顿迭代法收敛，而且收敛速度较快。
    • 弦截法
    • 埃特金迭代法
• 线性方程组
  • 直接法（经过有限步运算就能求得精确解的方法）
    • 顺序高斯消去法
      • 消元
      • 回代
      • 缺点
        • 主元素 akk(k) = 0 时, 消元过程将无法继续进行
        • 即使akk(k) ≠ 0时，但如果绝对值很小，用它作除 数也会导致其它元素的数量级急剧增大和舍入误差扩 大, 将严重影响计算结果的精度。
    • 选主元高斯消去法
      • 列主元高斯消去法
        • 基本思想
          • 在第k次消元时，从k列中选出绝对值最大的元素，然后通过行交换将其交换到k行上，再做第k次消元（同顺序高斯消去法）；
        • 程序
      • 全主元高斯消去法
    • 高斯—约当消去法
      • 基本思想
        • 经过n次消元后系数矩阵就成为对角阵，无回代过程的主元素消去法
    • 矩阵三角分解法
      • 基本思想
        • 将系数矩阵分解为两个三角形矩阵之积，即A=LU。其中: L为一个下三角矩阵,U为一个上三角矩阵。然后将解方程组Ax=b的过程化为解Ly=b和Ux=y两个方程组的过程。
      • 步骤
        • 1三角分解 2 求x值 3求y值
  • 迭代法（用某种极限过程去逐步逼近精确解的方法） （未知数n较多即方程较多，系数矩阵稀疏方程组）
    • 雅可比迭代法
      • 收敛条件
    • 高斯-赛得尔迭代法
      • 收敛条件
    • 松弛迭代法
• 插值法和曲线拟合
  • 插值法
    • 插值定理
      • φ(xi) = yi
    • 插值余项
      • 截断误差记为 Rn(x)=f(x)-Pn(x)
    • 拉格朗日插值公式
      • 一次插值（线性插值）
        • P1(x)=y0+(y1-y0)/(x1-x0)*(x-x0) （线性插值多项式） P1(x)=y0L0(x)+y1L1(x ) （拉格朗日线性插值多项式） L0(x)=(x-x1)/(x0-x1),L1(x)=(x-x0)/(x1-x0)
      • 二次插值（抛物线插值）
        • P2(x)=y0(x-x1)(x-x2)/[(x0-x1)(x0-x2)] +y1(x-x0)(x-x2)/[(x1-x0)(x1-x2)] +y2 (x-x0)(x-x1)/[(x2-x0)(x2-x1)]
      • n次插值
        • Pn(x)=L0(x)y0+L1(x)y1+…+Ln(x)yn
      • 插值余项
      • 程序
        • 子主题
    • 牛顿插值
      • 差商表
        • 子主题
      • 牛顿插值多项式公式
        • n=1 P1(x) = f(x0) + f [x0,x1](x-x0)线性插值 n=2 P2(x)=f(x0)+f [x0,x1](x-x0)+f [x0,x1,x2](x-x0)(x-x1)抛物线插值
      • 按秦九韶方法求多项式的值。
        • 子主题
    • 缺点
      • 列表函数中的点往往是通过实验、测量或计算得来的, 而实验、测量或计算得来的数据经常带有误差,
  • 曲线拟合
    • 基本思想
      • 曲线拟合求出的近似曲线 y =φ(x) 不要求完全通过所有 n+1个已知点 , 只要求求 得的近似曲线 y =φ(x) 能反映数据的基本趋势即可
      • 最小二乘法
      • 代数多项式拟合（法方程组）
      • 步骤
        • 1画草图2 写出拟合曲线 3 写出法方程组 并求解4 带入拟合曲线
• 数值积分与微分
  • 牛顿-科斯特公式
    • 插值求积公式 f(x)的定积分= Ai*f(xi)的求和。
    • 科特斯系数
      • 定义：ci^n=1/(b-a)*, xi=x0+i*h(插值节点等距)时,ci^n是科特斯系数
      • n=1 c1=c2=1/2 n=2 c1=c3=1/6 c2=4/6
      • 性质：1求和为一 2 对称性 3 n>=8 有负值 稳定性较差。
    • 公式
      • f(x)的定积分 约等于(b-a)* f(xI)*ci^n的求和。ci^n=(b-a)Ai
      • n=1 约等于(b-a)(1/2f(x0)+(1/2)f(x1)即为梯形公式 n=2 约等于 （b-a)(1/6 f(x0)+4/6f(x1)+1/6f(x2))即为抛物线公式
    • 余项（截断误差）=f($)^(n+1)/(n+1)!(x-x0)(x-x1)...(x-xn)dx的不定积分
  • 复化合求积公式及其误差
    • 梯形公式：~*h(01) + *h(12)+...+*h(n-1 n)
    • 抛物线公式
  • 变步长求积公式
  • 龙贝格求积法(主次半分加速法）
    • 基本思想
    • 过程T1 T2 S1 T4 S2 C1 T8 S2 C2 R1 T16 S8 C4 R2
• 常微分方程
  • 用差商代替倒数
    • 欧拉法
      • 改进的欧拉法
      • 预测-校长公式
  • 用数值积分方法
    • 四阶龙格 -库塔法
      • 格式数量 k1 k2 k3 k4 y1
      • 局部截断误差 o(h^5)
      • 线性多步法和单步法的比较
  • Taylor展开式
• 计算方法
  • 误差来源
  • 误差概念
  • 误差传播是否受控制（数值稳定性）
  • 减少误差运算（算法的若干原则）
    • 秦九韶算法