# 计算方法复习
# 第一章 绪论
误差
绝对误差：
相对误差：
精确位数d：
误差传递：加法误差等于每个加数误差之和，乘法误差等于每个乘数相对误差之和。
数值稳定性：误差在运算过程中稳定不增长，就说数值稳定。
减少误差准则
- 避免相近数相减
- 避免大数吃小数
- 绝对值太小不能作除数
- 减少运算次数
# 第二章 非线性方程的解法（收敛阶）
二分法/试值法
- 对于区间[a,b]，二分法所需次数
- 试值法使用两点形成的割线与x轴交点做分割，比二分法收敛更快。
不动点迭代法
将f(x)转化为x=g(x)的形式。
不动点原理：
第k次绝对误差为
牛顿迭代法
基于tylor公式转化，迭代公式为 x_{k+1} = x_k - \frac{f(x_k)}{f^，(x_k)}
割线法
牛顿迭代法中的
收敛阶
二次收敛，线性收敛
# 第三章 线性方程组的解法（未看视频）
向量/矩阵范数的计算
- 向量1-范数：绝对值之和
- 向量2-范数：平方之和再开根号
- 向量∞范数：最大的绝对值
- 矩阵1-范数：列绝对值和
- 矩阵2-范数：\sqrt{A^TA的最大特征值}或\sqrt{谱半径}
- 矩阵∞范数：行绝对值和
三角分解法
将矩阵 A分解为下三角矩阵 L 和上三角矩阵 U，即 A=LU 。
紧凑矩阵：
行 自 己 左 上 列 自 己 左 上 主 元 追赶法
Jacobi迭代法
将A分解，结果为：A=D−L−U 其中 D 为对角矩阵，L 为严格下三角部分，U 为严格上三角部分。
将
迭代公式：
每一步使用前一轮的所有值。
Gauss-Seidel迭代法
在每一步迭代中，当前已更新的值立即用于后续计算。收敛速度较jacobi快。与雅可比迭代区别就是，优先使用最新鲜的值。
公式：
# 第四章 插值法（分段线性插值）
Lagrange插值
拉格朗日基函数：
Newton插值
先算差商：
一 阶 差 商 二 阶 差 商 三 阶 差 商 分段线性插值
# 第五章 曲线拟合
最小二乘拟合函数
直线拟合
二次多项式拟合
# 第六章 数值微分
不单独考
# 第七章 数值积分
代数精度
针对某个公式存在精度，则分别令
插值型求积公式
梯形公式（一阶插值多项式）
辛普森公式（二次插值多项式）
复化梯形求积公式：将区间分成n个小区间
插值型求积公式的代数精度
梯形为一次。
辛普森为三次。
Gauss求积公式的代数精度（2n+1）
一点公式（n=1）：精度为三次。
两点公式（n=2）：精度为五次。
三点公式（n=3）：精度为七次。
两点Gauss求积公式
# 第八章 数值优化
黄金分割搜索法
适用于单峰函数，将区间按照黄金比例分割，缩小区间范围。
斐波那契搜索法
通过斐波那契数列确定分割点，比黄金分割法对小区间更高效。
# 第九章 微分方程求解（未看视频）
欧拉公式
用折线近似积分曲线，将区间划分为小段并用初值和斜率计算后续点。
公式： $y_{k+1}=y_k+hf(x_k,y_k) $其中h是步长。
heun方法
在欧拉方法基础上，通过求两点斜率的平均值提高精度。
公式：
常见公式的精度
若某算法的局部截断误差为
欧拉法整体截断误差：
heun法整体截断误差：