数值分析

Chapter 2 插值法

牛顿插值法

2.3 差商与牛顿插值 & 2.4 差分_哔哩哔哩_bilibili

差分

31:48

• 为什么叫向前向后差分呢？
• 向前：相对于$x_i$向前的差值$x_{i+1}-x_i$
• 向后：相对于$x_i$向前的差值$x_i-x_{i-1}$

Chapter 5. 常微分方程初值问题的数值方法

5 常微分方程的数值方法_哔哩哔哩_bilibili

一阶常微分方程的初值问题

09:55

考虑满足唯一解的情况

需要实现的目标：

通过一系列的节点，求出精确值的近似值

基本思想

将求解区间和节点离散化

注：为了方便表示，取$h_n=h$定步长，但是如果是非定步长也能计算，方法一样

一个例子

27:51

已知信息：

1. 初值$y(a)=y_0$
2. 函数$f(x,y)$的表示形式

具体计算方法如下：

33:09

计算方法

1. 欧拉方法

5.2 欧拉方法_哔哩哔哩_bilibili

基本思想：使用向前差商近似导数，从而替换导数，得到迭代公式

欧拉公式（又称为矩形公式）

$y_{n+1}=y_n+hf(x_n,y(x_n))$

如果取$y_{n+1}$近似，则称为隐式 Euler 公式

截断误差

$y(x_{n+1})-y_{n+1}=\frac{h^2}{2}{y}^{\prime \prime }(x_n)$

缺点：矩形公式的精确度很低

2. 梯形公式

29:09

梯形公式

$y_{n+1}=y_n+\frac{h}{2}[f(x_n,y(x_n)+f(x_{n+1},y(x_{n+1})))$

显式欧拉和隐式欧拉的平均计算方法

优点：精度高；缺点：计算复杂，因为含有隐式方程，不容易求解

3. 改进的欧拉公式

32:30

预测：${\hat{y}}_{n+1}=y_n+hf(x_n,y_n)$

校正：$y_{n+1}=y_n+\frac{h}{2}[f(x_n,y_n+f(x_{n+1},{\hat{y}}_{n+1}))$

这种方式又叫做两步法，前面的都是单步

局部截断误差与阶

5.2.4 局部截断误差_哔哩哔哩_bilibili

总结：

1. 欧拉法具有 1 阶精度
2. 改进的欧拉公式具有 2 阶精度

龙格-库塔方法

5.3 龙格-库塔方法_哔哩哔哩_bilibili

视频空降

基本思想：使用微分中值定理，通过某一斜率，沿直线从$x_n->x_{n+1}$

总结：

其实就是在欧拉的基础上，进行加权平均，尽可能的找更多的点近似

4 阶经典，需要记忆！！！

Chapter 6. 线性方程组的直接解法

复习 5 章 & 6 线性代数方程组的解法_哔哩哔哩_bilibili

27:49

两种数值解法

直接解法

经过算术运算，可以求得精确的方程解（如果没有舍入误差的话）

• 优点：可以在不损失精度条件下，求得低阶稠密方程组
• 缺点：高阶计算复杂，不适合求解

迭代法

通过极限过程不断逼近线性方程组的精确解

• 优点：适合解大型的稀疏方程组
• 缺点：需要不断迭代，且更加复杂（有各种精度、误差问题）

向量范数

33:55

常见范数

1. $\infty$-范数
2. 1-范数
3. 2-范数（欧式距离）
4. p-范数

向量序列与向量关系

类比于数列，向量序列就是向量组成的数列

矩阵范数

6.1 引言 & 6.2 高斯消去法_哔哩哔哩_bilibili

注：相容性代表的是两个向量之间的夹角关系，其实也代表了两个向量的相似度

常用矩阵范数

• Frobenius 范数：相当于对向量 L2 范数的推广

• 算子范数：一种更一般的形式，表示在所有向量 p-范数中，取最大的

  • 行和范数
  • 列和范数
  • 谱范数

• 谱半径

一些没那么重要的定理

重要定理证明

19:02

结论(2)可以用来进行范数估计

高斯消元法

只考虑非奇异矩阵

基本思路

1. 化为上三角阵
2. 从最底层回代，因此解出 $x_{n-1},x_{n-2},\cdots ,x_0$

误差分析

在计算机中会出现舍入误差，为了避免分母过小，分子太大导致的计算误差，我们可以在开始运算前对矩阵做等价变换

选主元消去法

6.3 高斯主元消去法 & 6.4 矩阵分解_哔哩哔哩_bilibili

列主元消去法

• 选取方法： 选取主列中绝对值最大的数作为除数

三角分解法

31:08

对于任意一个顺序主子式不为零的矩阵，都有这种 LU 分解

6.4.3 平方根分解法_哔哩哔哩_bilibili

如果上三角矩阵为单位上三角矩阵，就称为 Crout 分解，只需要考虑$A^T$的 LU 分解即可

当然，如果使用列主元法对三角分解进行优化也可以，不过要注意同时替换常数$b$

误差分析

06:46

1. 假设$A$精确，由于$b$的误差导致$x$的误差：
2. 假设$b$精确，由于$A$的误差导致$x$的误差：

通过分析可以看出，$||A||\cdot ||A^{-1}||$是放大因子，如果$A$越病态，则越难求得准确解

一些判断的经验

线性代数方程组的迭代解法

36:31

基本思想

通过对原式进行改写，得到迭代公式：$x=Bx+f$，其中，$x$，$f$为向量，$B$被称为迭代矩阵

• 优点：计算精度可控，适合求解系数为大型稀疏矩阵的方程组

因此要考虑如下几个问题：

1. 如何建立迭代格式
2. 如何才能保证迭代公式收敛？
3. 收敛速度多少？
4. 误差估计

Jacobi 迭代法

6.6.1 迭代公式 & 6.6.2 迭代法收敛性_哔哩哔哩_bilibili

一个例子 这个例子告诉我们，解线性方程组的迭代法，其基本思想是将联立方程组的求解归结为重复计算一组彼此独立的线性表达式

Jacobi 迭代的矩阵形式

这种方法进行分解后，就相当于例子中，把每个变量放一边的方法

Gauss-Seidel 迭代法

09:00

在 jacobi 迭代法的基础上进一步思考：在计算$x_{i+1}$时，$x_0-x_i$的值都已经计算出，可以带入计算$x_{i+1}$的公式中

Gauss-Seidel 分量形式

Gauss-Seidel 矩阵形式

注：两种方法都存在收敛性问题

迭代法的收敛性

收敛条件：

从上述推导可以发现，$B^k$为零矩阵，则最后的误差为 0，说明迭代法收敛；

而 $B^k$ 收敛的充要条件就是 $B$ 的谱半径 $\rho (B)<1$，==且 $\rho (B)$ 越小，则迭代收敛越快==

四个充分条件

1. 由定理可知，任意一个范数$||B||\le \rho (B)$，那么只要证明$||B||\le 1$，即可证明收敛
2. 若$A$为严格对角占优阵，则解$Ax=b$的 Jacobi 和 Gauss-Seidel 迭代均收敛
3. 若$A$为弱严格对角占优阵，且$A$为不可约矩阵，则解$Ax=b$的 Jacobi 和 Gauss-Seidel 迭代均收敛
4. 若$A$正定，则解$Ax=b$的 Jacobi 和 Gauss-Seidel 迭代均收敛

松弛迭代法

复习 6 章 & 6.6.3 松弛迭代法 SOR_哔哩哔哩_bilibili

37:13

基本思路

换个角度看 Gauss-Seidel 迭代法：将其看作增量形式，目标就是要求出增量$\frac{r_i^{(k+1)}}{a_{ii}}$

矩阵形式

收敛性判断

对于这个形式，判断其收敛性：

1. 使用充分必要条件 计算过于复杂，很难计算$H_{\omega }$
2. 使用 Kahan 必要条件
3. 使用其他充分条件

Chapter 7. 非线性方程组和方程组的数值解法

6.6.3 & 7 非线性方程组的解法_哔哩哔哩_bilibili

18:51

次数越高，其方程的解析解就越难以表示，5 次以上更是没有解析解，因此我们需要通过求解近似值的方式，不断逼近零点

二分法

基本思想

对有根区间进行折半查找…

优点：算法简单，对$f(x)$的要求不高，只要保证连续即可

缺点：不能够保证 x 的精度，无法求重根和复根

误差分析

一个例子

如果相邻两个点的变化值，不到其最后一位精度$\frac{1}{2}$，则说明精度是够的

简单迭代法

7.2 简单迭代法_哔哩哔哩_bilibili

基本思想

如果每次迭代，使得$x_k$能够收敛，就说明$x^{\ast }$是$\phi$的不动点，也就是$f=0$的根

但是不能保证每个迭代函数都一定是收敛的！！！

一个例子

同一个方程有不同的等价迭代函数：

但是计算后有的收敛，有的不收敛：

在这个例子中，有以下问题需要进行详细讨论：

1. 如何选取合适的迭代函数？
2. 迭代函数应该满足什么条件，序列$x_k$收敛？
3. 怎样加速序列$x_k$的收敛？

迭代收敛的过程

定理

p 阶收敛的迭代法

迭代加速

7.3 迭代加速_哔哩哔哩_bilibili

14:58

迭代收敛速度

Aitken 算法

基本原理

可以加速收敛的原因：

1. 实际上求出两次迭代值，然后通过加权的方式得到改进值，相比原式来说更加稳定
2. 原函数往往比较复杂，导致$\phi (x)$往往也是一个复杂函数，通过这种方式可以少计算$\phi (x)$，从而达到加速的效果

Steffensen 迭代法

收敛效果

Newton 法

基本思想

基本思想就是将非线性方程线性化，原函数做一阶 Taylor 展开，并且将二阶看作高阶无穷小量，就可以得到一个稳定的迭代公式

Newton 法的改进

Newton 下山法

基本思想

选取一个$\lambda$作为下山因子，一般下山因子从 1 开始…不断减半，使得$f(x_k)$能够保证收敛

弦截法