绪论
1. 数值分析的定义与重要性
- 数值分析，亦称计算方法，是研究使用计算机求解各种数学问题的算法与理论的科学。
- 数值分析结合了理论与计算，广泛应用于天气预报、飞机设计、石油勘探、金融分析、生物医学等多个领域。
2. 数值分析的学科特点
- 面向计算机：算法设计基于计算机的特点，只能包含基本运算（加、减、乘、除和逻辑运算）。
- 可靠的理论支持：需要算法的收敛性、稳定性和误差分析。
- 计算复杂性：包括时间和空间复杂性分析。
- 数值实验验证：需要通过实验来验证算法的有效性。
3. 学习数值分析的要点
- 掌握算法的原理和思想。
- 熟悉算法的处理步骤和计算公式。
- 注重误差分析，理解收敛性与稳定性。
- 通过练习题巩固理论，上机实践加强动手能力。
4. 误差分析☆
- 误差来源：模型误差、观测误差、舍入误差和方法误差。
- 误差的分类：绝对误差、相对误差和有效数字。
- 误差传播与积累：在数值计算中，误差可能传播并积累，导致结果不稳定。
5. 算法稳定性
- 稳定性定义：若一个算法对初始误差敏感，且在计算中误差快速增大，则该算法是不稳定的。
- 减少误差的策略：避免相近数相减、大数吃小数；选择稳定算法；化简运算步骤等。
6. 数值分析的主要内容
- 包括误差分析、插值、函数逼近、数值积分与微分、线性方程组解法、矩阵特征值等。
7. 数值计算中的常用方法
- 近似替代、离散化、递推化（迭代法）等。递推化是将复杂的计算简化为多次简单的重复，适合编程实现。
通过系统学习数值分析，学生可以掌握解决实际数学问题的能力，尤其是在现代计算机辅助的科学与工程计算中有广泛应用。
误差分析
概念
- 绝对误差：
- 近似值与真实值的偏差大小
- 绝对误差有正负，表示近似值是偏大还是偏小
- 有单位
- 相对误差：
- 误差相对于真实值的比例，通常用于衡量误差的严重程度
- 无量纲
- 绝对误差限：
- 近似值与真实值之间的最大可能偏差
- 描述近似值的精度范围
- 非负数
- 相对误差限：
- 相对误差的最大可能比例
- 描述近似值的相对精度
- 无量纲
有效数字
- 定义
是一个整数，表示数量级。
- 误差限
- 是真实值。
- 是近似值。
- 是误差限的数量级。
例
假设近似值 ，其有效数字为 位，数量级 （因为 ）。
误差限：
真实的x范围：
- 相对误差限
- 用来衡量有效数字位数
- 如满足上述公式，则至少具有位有效数字。
例
误差运算
- 一元函数
跟求导的法则一样。（本质上就是用Taylor公式推的）
- 多元函数
插值
Lagrange插值
基于两点式，本质上是对自变量进行线性组合
多次的Lagrange插值基函数也有相应多的次数
插值基函数
性质
- 保证插值节点的有效性
插值多项式
余项
令，则
Newton插值
特点：递推性，不影响之前的插值公式
一般在递推的过程中求出
递推式
差商
类似于微分
零阶
一阶
二阶（注意分母的跨度）
k阶
性质
- 对称性
- 差商中元素位置可以任意
- k阶差商可以表示为函数值的线性组合
- 如果函数在定义域上n阶可导
差值多项式
余项
Hermite插值
特点：节点上的数值、导数和高阶导数都相等
Tarlor型
就是Taylor公式
差值多项式
余项
三点一阶导
插值条件
求法
A为待定系数，用条件2确定
余项
另外地，可以将导数值的条件看成一个插值节点，然后用Newton插值法做（多一个节点）
两点三次Hermite插值
给定两个节点和，以及函数值、和导数值、，目标是构造一个三次多项式，使得
思想：待定系数列方程组求解
设多项式为
要满足以下条件
解得
余项
函数逼近
内积
性质
满足以下条件
满足Cauchy-Schwartz不等式
函数内积
加权
Gram矩阵
- 非奇异线性无关
最佳逼近元
略
正交多项式
Legendre（勒让德）多项式
首项系数为1的情况
性质
- 正交性
- 与任意n-1次多项式正交（因为所有多项式都可以用Legendre多项式线性表示）
- 奇偶性
- n为奇，P为奇
- n为偶，P为偶
- 因为积分区间都为，奇偶性可以简化积分步骤
- 递推关系
特殊值
Chebshev（切比雪夫）多项式
性质
- 带权正交性
- 奇偶性
- 与Legendre多项式相同
最佳平方逼近
“平方”逼近的概念来自函数的2-范数，定义详见范数章节。
最佳平方逼近函数
确定系数来用基函数表示平方误差最小的逼近函数。
为了找到最佳平方逼近函数需要求解法方程组
法方程组
- 是基函数的内积
- 是原函数与基函数的内积
求解即可
例
特别地，在基函数正交时，有
- 如果用Legendre多项式作为基函数
平方逼近误差
由此可得Bessel不等式
数值积分与数值微分
插值型求积公式
- 用个插值节点求得的插值函数，就有次代数精度
例
思路
用插值多项式（易求积分）来代替原函数求积分
故原积分可以表示为
对Lagrange插值基函数积分
特别地
- 时，
- 当时，
收敛充要条件
Newton-Cotes公式
通过在被积函数的等距节点上进行多项式插值来近似计算定积分
一般形式：
C为Cotes系数
Cotes系数性质
- 归一性
- 对称性
梯形公式（一阶N-C）
Cotes系数
余项
复化梯形公式
将区间分成个子区间，每个子区间宽度（步长）为
余项
Simpson公式（二阶N-C）
余项
复化Simpson公式
将区间分成个子区间，每个子区间宽度（步长）为
余项
插值型求导公式
两点公式
矩阵
特征值
满足
- 为特征值，为其对应的特征向量
- 全体特征值为的谱
- 特征值之积为行列式：
求法
解方程（特征多项式）即可。
谱半径
绝对值最大的特征值的绝对值
迹
特征值之和，对角线之和
条件数
对于可逆矩阵的条件数：
特别地，当v=2，即谱范数中，条件数可以写成：
如果A对称，则
这里的max和min都以绝对值为比较标准。
矩阵正定性的判定方法
范数
用来衡量广义上的长度
性质
正定性
范数大于等于0，等于零当且仅当元素为0
正齐性
三角不等式
向量范数
对于向量
无穷范数
- 绝对值的最大值
1-范数
- 绝对值之和
2-范数
- 平方和开根号
p-范数
- p次幂和开p次根号
函数范数
对
无穷范数
- 绝对值的最大值
1-范数
- 绝对值积分
2-范数
- 平方积分开根号
矩阵范数
性质
- 还需满足
- 一种范数满足小于1，则所有范数都满足。
对于矩阵
无穷范数（行范数）
- 行向量 各分量绝对值 的和 的最大值
1-范数（列范数）
- 列向量 各分量绝对值 的和 的最大值
2-范数（谱范数）
- 与转置矩阵的乘积的特征向量的绝对值最大值开根号
F-范数（弗罗贝尼乌斯范数）
- 所有元素平方和开根号
解线性方程组的直接方法
Gauss消去法
- 用初等行变换将矩阵化为阶梯形的方法（详请翻阅高等代数）
- 每次变换的比例系数都是该行最左侧的非零元素和参照行对应位置的比值
- 即第k次变换需要在右下角的子矩阵中进行操作，比例系数看的是子矩阵的第一列各项与第一列第一行的数的比值。
- 每次变换后需要将需要进行操作的子矩阵第一列中绝对值的最大项所在行变换到第一行去，保证运算稳定性和避免左上角元素为0。（列主元消去法）
注意事项
- 变换矩阵时不要对行同除公因数来简化计算，算法中没有这一步
- 列主元消去法中是看的绝对值的最大值
迭代公式
- 在计算机运行时，每次的比例系数会存储在矩阵左下方的无用区域中，减少内存占用。（紧凑型LU分解）
Gauss-Jordan消去法
- 在Gauss消去法的基础上，每步消元把该列非对角线上的元素全消掉。
- 最后得到的系数矩阵是对角矩阵。
例
Gauss-Jordan消元法也是求逆矩阵的一个方法，高代也讲过，好用爱用
例
- 在高斯消元过程中，约化后的对角元与矩阵A的顺序主子式D满足以下关系：（设消元后得到的上三角矩阵为）
- 其中顺序主子式为对角元素乘积：
- Gauss消元法解线性方程组的条件是约化后的所有对角元不为0，等价于系数矩阵的所有顺序主子式不为0。（不一定要正定）
- 每进行一次行变换都可以视作左乘一个初等矩阵，故高斯消元的操作可以用左乘一个非奇异矩阵来表示。
- 由此可以对矩阵进行三角分解。
三角分解
LU分解
- 条件：系数矩阵正定（顺序主子式不为0）
- 不正定就不能用Gauss分解
- 其中都是单位下三角矩阵。均可逆。
令，则有
其中L是单位下三角矩阵，U是上三角矩阵。
这就是矩阵的LU分解。
- LU分解具有唯一性
Doolittle（杜利特尔）直接分解法（LU分解）
求LU矩阵→适用于所有可以用Gauss消元法解决的方程
- U矩阵按Gauss消元法求
- L矩阵在求U矩阵的过程中求
实际上，就是Gauss消去法中得到的比例系数放在相应作用的位置
在求U矩阵的每一步中将系数记录下来就行。
例
- 分解之后原线性方程组化为
- 所以原方程组可以化为求解两个三角方程组
- 两个方程都是三角矩阵形式，易于求解，代值就行了
- 先算y再算x
平方分解（）
在LU分解的基础上
- 适用于对称矩阵（改进的平方分解法）
- 将进一步分解为
- 由于A具有对称性
- 求法
- 求得之后，将的对角部分提取做出来作为，然后直接写成即可。
- 原方程组化为：
由分解的唯一性得
故
- 适用于对称正定矩阵（传统平方分解法）
- 在的基础上，将拆分为两部分和合并
- 直接求法
- 分解公式
原方程组化为
推导
例
最好还是列出矩阵乘法的式子按照题目推，防止公式记错
追赶法
追赶法用来解决三对角方程组
步骤
解线性方程组的迭代法
基本思路
- 基于不动点原理，逐步逼近精确解
- 逐步逼近是一个递归的过程
- 递归公式就是迭代公式
- 目标就是要找到一个合适的迭代公式
- 迭代产生的结果与精确值的误差可以用其范数来衡量
- 迭代收敛即得到的结果收敛于精确值
Jocabi迭代法
原理
对
划分系数矩阵
- D-对角矩阵
- L-下三角
- U-上三角
将移项，乘逆，则
步骤
例
- 整理为迭代形式（这一步移项已经体现出系数矩阵的划分）
- 加上迭代
Gauss-Seidel迭代法
原理
将移项，乘逆，则
其实就是在Jacobi迭代法的基础上，在单次迭代的过程中将代入的值进行实时更新，而不是全部方程迭代完一次在进行更新
步骤
在上述的加上迭代中，实时地将更新的值代入
SOR超松弛迭代法
原理
在G-S迭代法的基础上，引入松弛因子
用来控制G-S迭代法的作用率，通常
步骤
在G-S迭代法的基础上，加入的控制
一般迭代法的收敛性
充要条件
对于迭代矩阵B
- B收敛于零矩阵
- 每个元素都收敛于0
- B谱半径小于1
充分条件
- 存在某种范数使得B的范数小于1
收敛速度
- 谱半径越小，收敛速度越快
- 收敛速度之比为
特殊迭代法的收敛性☆
迭代法 | 严格对角占优矩阵 | 对称正定矩阵 |
雅可比迭代法 | 收敛 | 不一定收敛， |
高斯-赛德尔迭代法 | 收敛 | 收敛 |
SOR 法 | 时收敛（充要） 时收敛（充分） | 时收敛 |
非线性方程（组）的数值解法
二分法
找
Newton法
思想
将非线性方程用线性逼近
求切线
得到迭代公式
如果是方程组：
则迭代公式
其中Jocabi矩阵为导数矩阵：
为了避免逆矩阵求解，先求线性方程组计算更新量
然后更新解
收敛条件
- 初始接近真实解
- 在解附近连续可微
- 方程组在解附近非奇异
