Haowei Hub 博客归档相册标签分类关于
A Brief Review of Numerical Analysis
|基本功
字数总计: 11.6k|阅读时长: 34 分钟

参考资料：

  1. 数值分析 第五版 (李庆扬，王能超，易大义)

  2. 数值计算方法与算法（张韵华，奚梅成，陈效群）

  3. 数值方法 （关治，陆金甫）

  4. Linear Algebra Done Right（Sheldon Axler）

1 基础

1.1 误差

1.1.1 误差定义

绝对误差: 设 为精确值, 为近似值, 为误差或绝对误差

  1. 有限计算，截断误差
  2. 有限精度，舍入误差

相对误差：称为相对误差

1.1.2 有效数字

  1. 误差界 :
    • 相对误差界
  2. 有效位数： 当 的误差界为某一位的半个单位，则这一位到第一个非零位的位数称为 的有效位数。
    • 四舍五入： 绝对误差界可以取为被保留的最后数位上的半个单位
    • 近似值的有效数字位数越多, 相对误差界就可以越小, 反之也成立
  3. 的近似值 3.141 具有几位有效位数? 的近似值 3.142 具有几位有效位数?
    1. --> -2 位的半个单位 --> 3.141 --> 3 位
    2. --> -3 位的半个单位 --> 3.142 --> 4 位

1.1.3 误差来源

  1. 原始误差：模型误差 (忽略次要因素, 如空气阻力物理模型, 数学模型）
  2. 测量误差：观测误差 (测量引起的误差)
  3. 方法误差：截断误差（算法本身引起）
  4. 计算误差：合入误差（计算机表示数据引起）

1.1.4 误差估计

可以把 当做微分算子，绝对误差估计公式可以类比求导公式

  1. 绝对误差估计：

由此推导：

  1. 相对误差估计：

1.1.5 避免误差危害

  1. 选择收敛、稳定的算法
  2. 提高数值计算精度
    1. 尽可能使用 double 等高精度的表示
    2. 需要在内存、计算时间与计算精度之间作出平衡
  3. 尽可能避免两个相近的数相减
  4. 尽可能避免绝对值很小的数作除数
  5. 尽可能避免大数 “吃” 小数的现象

1.1.6 病态问题与条件数

对于一个给定的函数 ，在点 处的条件数 通常定义为：

  • 如果 远大于 1，那么问题在 附近是病态的（ill-conditioned），对输入的微小变化非常敏感。
  • 如果 接近 1 或小于 1，那么问题在 附近是良态的（well-conditioned），对输入的微小变化相对不敏感。
  • 用于量化函数对输入的微小变化的敏感性。如果一个问题的条件数很高，那么它对输入的微小错误或变化可能会非常敏感，从而导致输出结果有很大的不确定性。

1.1.7 数值方法的稳定性

如果初始数据微小的改变将会引起最后结果的改变也是微小的, 就称此算法是数值稳定的, 否则称数值不稳定的. 1. 指数型 2. 线性型

1.2 线性代数

1.2.1 行向量和列向量

设我们有一个矩阵 , 这个矩阵是用于将向量 变换到 的。

  1. 列向量描述了基向量如何变换：矩阵 的列向量实际上描述了原始向量空间（输入空间）中的基向量经过矩阵 变换后在目标向量空间（输出空间）中的位置。
  2. 行向量描述了变换后的向量如何与目标空间的基向量相互作用：矩阵 的行向量则与输出空间有关。具体来说, 行向量描述了输出向量 在目标空间中与每个坐标轴（即目标空间的基向量）的关系。

1.2.2 矩阵的特征值、相似变换

  1. 特征值： 假设我们有一个矩阵 , 我们想找到一个非零向量 和一个标量 , 使得：
    • 特征值 可以理解为矩阵 作用于特定向量时的“拉伸或压缩因子”。如果 , 表示这个向量没有被拉伸或压缩; 如果 , 表示向量被拉伸; 如果 , 表示向量被压缩。
    • 特征向量 是那些在矩阵 作用下只会被拉伸或压缩，而不会改变方向的向量。
      • 代数重数：特征值在特征多项式中出现的次数
      • 几何重数：特征值对应的线性独立特征向量的个数
    • 我的理解：考虑拉橡皮筋的场景，如果阿玮用力拉它，它会朝某个方向拉长。这个“用力拉”的动作就像矩阵，而橡皮筋的各个方向就像不同的特征向量，拉长的程度（比如，拉长了多少倍）就像特征值。
  2. 相似变换： 一种改变矩阵的方式, 但不改变其特征值。如果我们有两个矩阵 和 , 并且存在一个可逆矩阵 使得：
    • 那么我们说 和 是相似的。
  3. 对角化：可以对角化，如果存在一个可逆矩阵 和一个对角矩阵 , 使得：
    1. 我的理解
      1. 从旧基到新基
        1. 在原始坐标系（或旧基）中，矩阵 对向量的作用可能包括旋转、拉伸和压缩。
        2. 在新坐标系（或新基）中，找到一种方式使得 只进行拉伸和压缩，而不进行旋转。
      2. 的列就是 的特征向量，它们组成了新的基。在这个新基下，变成了一个对角矩阵 ，只有对角线上有非零元素。这意味着 在新基下的作用只是沿着坐标轴进行拉伸或压缩。

1.2.3 线性空间和内积空间

  1. 线性空间：线性空间是一个集合，里面的元素（我们可以称之为“向量”）满足两个基本运算：加法和标量乘法。
    1. 封闭性: 在这个空间内做加法或标量乘法, 结果仍然在这个空间内。
    2. 可交换性:
    3. 可结合性:
    4. 存在零向量: 有一个特殊的向量, 加上任何向量都不会改变那个向量。
    5. 存在逆向量：对于每一个向量, 都有另一个向量, 两者相加结果是零向量。
  2. 内积空间：引入“距离”和“角度”
    1. 线性:
    2. 对称性:
    3. 正定性: , 当且仅当 是零向量时等于 0 。

1.2.4 几种常见矩阵的性质

  1. 行列式
    1. 矩阵看作一个从平面到平面的变换, 行列式是变换后平行四边形的面积与原平行四边形面积（这里假设是单位正方形, 面积为 1) 的比值。
    2. 对于 矩阵，看作一个从三维空间到三维空间的变换。行列式这时就是变换后的平行六面体体积与原平行六面体 (单位立方体, 体积为 1) 的比值。
  2. 线性相关：线性相关的向量在几何空间中共线或位于同一条直线上，而线性无关的向量不共线，它们构成了向量空间中的基，可以用来表示空间中的各种向量。
  3. 正交矩阵：只能旋转或者反射，不会拉伸或压缩任何向量。
    1. 对于正交矩阵，其特征值要么是 1（对应于旋转），要么是 −1（对应于反射）。
    2. 显然，正交矩阵行列式绝对值为 1：用正交矩阵变换一个向量或一个形状时，阿玮不会改变它的“体积”。阿玮只是在旋转或反射它。
  4. 初等矩阵
    1. 行交换矩阵: 交换两行。
    2. 行倍乘矩阵: 将某一行乘以一个非零常数。
    3. 行倍加矩阵: 将某一行的若干倍加到另一行。
  5. 可约矩阵：一个 矩阵 是可约的, 如果存在一个置换矩阵 , 使得 可以被分为如下的块状对角形式：
    1. 其中 和 是子矩阵, 至少有一个是非方块的。
    2. 我的理解：组织一场派对。把朋友们分成几个不同的小组，比如高中同学、大学同学、工作同事等。现在，想要确定派对的座位安排，以便每个人都能与他们的小组成员坐在一起。如果能够通过调换座位，让所有高中同学坐在一起，并且让所有大学同学坐在一起，而不需要让高中同学和大学同学混坐，那么这个派对矩阵就是可约的。
  6. 对角占优矩阵：一个 方阵 是对角占优的, 如果对于所有的 (行号)，都有:
    • 每一个对角线元素的绝对值都大于或等于其所在行中其他元素绝对值的总和。
  7. 奇异矩阵：一个矩阵 是奇异的, 当且仅当 。
    1. 奇异矩阵是一个无法完全表示所有信息的矩阵。
    2. 非奇异矩阵是一种完整的矩阵，没有冗余信息，可以用来精确表示数据和进行计算。
  8. 对称矩阵
  9. 正定矩阵：
    1. 所有的特征值都是正数（大于零）。
    2. 所有的主子矩阵的行列式都是正数。主子矩阵是通过从A中删除一些行和列而得到的矩阵。

1.2.5 范数

1.2.5.1 向量范数

对任一向量 , 按照一个规则确定一个实数与它对应, 记该实数为 , 即映射: 。

  1. 满足下面三个性质:
    1. 非负性 , 且
    2. 齐次性
    3. 三角不等式 ，则称 为向量范数
  2. -范数：
  3. 无穷范数：
  4. 范数等价性：
  5. 收敛性：向量序列 收敛的充分必要条件为序列的每个分量收敛，即
  6. 连续性：范数 是关于坐标 的连续函数
    1. 按照连续性的定义，我们需要证明对于任何 , 存在 使得当 时, 有 。
    2. 根据三角不等式性质, 我们有 则可得到
    3. 同样的, 我们也有则可得到从 (1) 和 (2) 我们可以得到
    4. 现在, 设定 。当 时, 我们得到

1.2.5.2 矩阵范数

矩阵作为线性算子的“强度”

  1. 诱导矩阵范数 / 从属范数
  2. 性质：
    1. 非负 + 齐次 + 三角不等式
    2. (相容性)
      • 我的理解：
        • 当阿玮用一个强矩阵（即矩阵范数大）去变换一个长向量（即向量范数大）时，得到的新向量（）也会是一个“强”或“长”的向量
        • 变换后的向量的长度至多是原始向量长度与矩阵的“最大拉伸能力”的乘积。
          • 矩阵不仅可能“拉伸”向量，还可能“压缩”或“旋转”它
    3. (可乘性)
  3. 常见矩阵范数
    1. 为矩阵的谱半径（矩阵所有特征值绝对值的最大值）
      1. 矩阵的"谱"（Spectrum）指其所有特征值的集合
      2. 我的理解：
        • 矩阵作用于向量时"拉伸"或"压缩"效果的上限
        • 描述了特征值（谱）在复平面上的几何范围（半径）
    2. 若 为矩阵 的特征值, 则 （相容性可推之）
    3. 矩阵的任一矩阵范数均不小于其谱半径
      • 我的理解：矩阵范数通常考虑矩阵作用于所有可能向量的效果，而谱半径仅考虑矩阵作用于其特征向量的效果（通过特征值来描述）
  4. 矩阵的条件数
    1. 若矩阵 A 非奇异, 称 为 的条件数，其中 表示矩阵的某种范数
    2. 条件数反应了矩阵对误差的放大率
    3. 我的理解：度量了当输入（或者右侧向量）发生微小改变时，输出（或者解）会有多大的变化。一个具有低条件数的矩阵通常更为“稳定”，而具有高条件数的矩阵则可能更为“不稳定”。

1.3 课后习题导引

1.3.1 习题 10

1.3.2 习题 11

  1. 1-范数:
  2. 2-范数：
  3. 无穷范数:

1.3.3 习题 12

1.3.3.1 第 1 小问

  1. 根据无穷范数的定义, 我们有 。由于每个 都小于或等于 , 我们可以得出 。
  2. 同样, 由于 的每一项都是非负的, 所以 。

1.3.3.2 第 2 小问

  1. 首先, 由于每个 都是非负的, 我们可以得出 ，从中我们得出 。
  2. 接下来, 我们注意到 对所有 成立, 所以 , 从中我们得出 。

1.3.4 习题 13

关于 2-范数的求解：

  1. 首先计算 ；

  2. 然后求解特征方程 :

1.3.4.1 第 1 小问

  2. 2-范数:

  3. 无穷范数: #### 1.3.4.2 第 2 小问

  4. 1-范数:

  5. 2 -范数:

  6. 无穷范数:

1.3.5 习题 14

1.3.5.1 第 1 小问

由于单位矩阵的范数是 , 所以我们可以得到:

现在我们可以解出 的范数, 得到:

1.3.5.2 第 2 小问

  1. 三角性：
  2. 子乘性:

由矩阵范数的性质, 得:

利用矩阵范数的三角不等式和矩阵范数的乘法性质, 得：

因此:

1.3.6 习题 16

1.3.6.1 定义法

  1. 非负性:

由于 是对称正定矩阵, 所以 是非负的, 且只有在 时等于 0 。因此, , 且当 时, 。 2. 齐次性: 3. 三角不等式:

1.3.6.2 Cholesky 分解法

首先, 我们验证非负性：

由于 是一个向量, 而且内积总是非负的, 我们可以得出 ,并且 当且仅当 .

接下来, 验证齐次性:

最后, 验证三角不等式:

考虑 , 我们有

由Cauchy-Schwarz 不等式来得到

因此

取平方根得到

故， 是 上的一种范数。

2 线性代数方程组的直接解法

直接解法： 1. 采用消元 (初等变换)、矩阵分解等技巧; 2. 从理论上来说, 直接法经过有限次四则运算（假设运算无舍入误差），可以得到线性方程组的精确解； 3. 但因数值计算有含入误差，得到的仍然是近似解

  1. 时间复杂度:
  2. 空间复杂度:
  3. 理论上可经过有限次四则运算得到准确解, 但因数值计算有舍入误差, 得到的仍然是近似解
  4. 适用情况: 中等规模

2.1 消元法

  1. 基本思想：通过初等变换，将一般的线性方程组等价变换为特珠形式的线性方程组，如上/下三角方程组、对角方程组，进行求解

  2. 求解步骤：消元 + 回代

2.1.1 概念

  • 对角形线性方程组 image.png
    • 时间复杂度:
  • 上三角方程组 image.png
    • 时间复杂度:
  • 下三角方程组 image.png
    • 时间复杂度:
  • 初等变换
    1. 交换
    2. 倍乘
    3. 倍加

2.1.2 顺序 Gauss 消元法

先将矩阵化为上/下三角矩阵，再回代求解

2.1.2.1 步骤

  1. 选择主元：从第一列开始，选择一个非零元素作为主元（pivot），通常选择当前列的绝对值最大的元素作为主元以减少计算误差。

  2. 行交换：如果必要的话，通过行交换将主元移到当前行的对角线位置。

  3. 消元：使用行的加减运算，通过主元消除该列下方的所有其他元素，使它们变为 0。

  4. 向前迭代：将上述过程应用于主元以下的子矩阵。

  5. 回代：当矩阵变为上三角形式后，可以从最后一行开始，逐步回代求出所有未知数的值。

考虑一个线性方程组, 可以表示为 , 其中 是一个 的矩阵, 是未知变量的列向量, 是常数项的列向量。

例如, 假设我们有一个三元一次方程组:

将其写成增广矩阵的形式:

接下来, 使用高斯消元法对该矩阵进行操作, 目标是将左侧的矩阵 转化为上三角矩阵:

第一步, 如果 是 0 或者绝对值不是第一列中最大的, 我们可能需要交换行。然后, 用第一行乘以 并从第二行减去, 用第一行乘以 并从第三行减去, 消除 和 。

第二步, 对第二列重复此过程, 选择 作为主元, 消除其下方的元素。

第三步, 对第三列重复此过程, 这时应该已经是一个上三角矩阵了。

最后的增广矩阵可能看起来像这样: 其中, 表示操作后的新矩阵元素, 表示新的常数项。

回代: 从最后一行开始, 我们可以解出 , 然后代入上一行解出 , 以此类推, 直到解出所有变量。

以上消去和回代过程含总的乘除法次数为 , 加减法次数为 .

2.1.2.2 顺序消去能实现的条件

image.png
  1. 设 , 若对 的顺序主子式 , , 则每步消去过程的对角元 .
  2. 逆定理也成立

可以从几何的角度去理解（摘自《矩阵分析》）：

有三个平面，在三维空间中它们可能相交于一点，这一点就是这三个平面方程所代表线性方程组的唯一解。我们的目标是要找到这个点。

顺序高斯消去法可以想象成逐步移除这些平面之间的冗余信息，最终留下一个可以清晰定义交点的系统。在每一步，我们实际上在做的是使用一个平面去“削减”另一个平面的一个维度。从几何角度看，这相当于将其中一个平面投影到另外一个平面上，这样做的结果是我们减少了问题的维度，从而使问题简化。

在第一步中，我们可能会取第一个方程代表的平面，并用它来消去其他两个方程中的 分量。这在几何上意味着我们将其他两个平面沿着与第一个平面相交的线投影，这样每个平面都不再与 轴相交。

接下来，我们取这两个新平面中的一个，消去第三个方面的 分量。几何上，我们再次做了投影，这一次我们将一个平面投影到另一个平面上，从而得到一条直线，它是最初两个平面的交集。

最后，我们沿着这条直线进一步消去 分量，最终找到三个平面交点的确切位置。

在几何意义上，一个非零的 阶主子式意味着这 个维度构成的子空间有非零的“体积”，或者说，它们是线性独立的。如果在某个步骤中 阶主子式为 0，那么几何上这表示我们试图在一个“扁平”的子空间内求解，其中的点并不构成一个具有体积的空间，也就是说这些点（或者说方程）在几何上是相关的，没有一个唯一的交点。

注意 1：当我们谈论一个矩阵的k阶主子式时，我们实际上是在讨论矩阵中选取的k行和k列形成的一个小矩阵（子矩阵），它在原矩阵的左上角开始。这个子矩阵的行列式给出了由这些行和列对应的向量张成的k维子空间的“体积”。

注意 2：在二维空间中，两个线性独立的向量会张成一个有面积的平行四边形。如果这两个向量是线性相关的（比如一个是另一个的倍数），它们会落在同一条直线上，平行四边形的面积会是零。在三维空间中，三个线性独立的向量会张成一个有体积的平行六面体。如果这些向量中的任意两个或三个是线性相关的，那么它们会落在同一个平面上，平行六面体的体积会是零。

顺序高斯消去法要成功地实现，各阶顺序主子式不为零是必要的条件。这确保了在每一步我们都可以在一个具有“体积”的子空间中工作，方程组在几何上是相互独立的，从而我们可以找到一个唯一的解——即所有这些多维平面的公共交点。如果任何一个主子式为零，我们就失去了唯一解的可能性，因为在几何上，至少有两个平面是共线或者共面的，它们不再在一个唯一的点上相交，而是可能在一条线上或者一个平面上有无数个交点。

2.1.2.3 矩阵的三角分解

假设我们有一个可逆矩阵 。我们要做的, 就是找到两个特殊的矩阵 和 , 使得 。这里, 是一个下三角矩阵, 它的对角线上全是 1, 所有的非零元素都位于对角线或对角线以下的位置; 而 是一个上三角矩阵, 它所有的非零元素都位于对角线或对角线以上的位置。image.png

当谈论矩阵时, 我们可以想象它为向量空间内的一个变换, 即一个向量被拉伸、压缩、旋转和/或反射。在三角分解中, 我们可以把这个变换想象成两步进行：首先是一个拉伸或压缩（由 表示）, 接着是一个仅在各个坐标轴方向上拉伸或压缩（由 表示)。

是一个下三角矩阵, 我们可以将其视为一系列的剪切和缩放变换, 这些变换沿着坐标轴进行, 并且它们是依次作用的。例如, 在二维中, 可以先沿 轴压缩, 然后沿 轴剪切变换一个向量。

而 , 上三角矩阵, 则描述了一系列不会改变 坐标的变换。在二维中, 可能首先在 轴方向拉伸向量, 然后进行一个沿 轴的剪切。

通过将 分解为 , 我们实际上是在说：任何由 描述的变换可以先通过 描述的剪切和缩放, 然后通过 描述的坐标轴方向的变换来完成。

2.1.2.4 列主元素消去法

image.png image.png

在普通的高斯消元法中，如果某一步骤中行的主元（即该行对角线位置的元素）很小，那么它可能导致数值计算上的不稳定，特别是当主元接近零时，错误可能会被放大。

  1. 构造增广矩阵：
    • 将线性方程组写为矩阵形式，并将常数项并入形成增广矩阵。
  2. 选择主元并进行行交换：
    • 从第一列开始，在当前列选择绝对值最大的元素作为主元。
    • 如果这个主元不在当前行的对角线位置，就通过行交换，将含有主元的行移到对角线位置。
  3. 消元过程：
    • 用主元所在行去乘以适当的系数并加到下面的行上，使得这些行的当前主元列的系数变为0。
    • 这个过程将矩阵的下三角部分变成零，最终形成一个上三角矩阵。
  4. 对下一列重复步骤：
    • 对于矩阵的每一列，重复步骤2和3的操作，每一次迭代都将矩阵的非零部分向上推一个阶梯。
    • 需要注意的是，每次迭代后，矩阵的非零部分都将减少一行和一列。
  5. 回代解方程：
    • 一旦获得上三角矩阵，就可以从最后一行开始，依次解出每个未知数。
    • 通过将已经求得的未知数代入到前面的行中，可以逐个求解出所有未知数。

2.1.3 直接三角分解方法

2.1.3.1 Doolittle 分解方法

假设我们有一个 的矩阵 , 如下所示:

我们的目标是找到两个矩阵 和 , 使得 。按照 Doolittle 方法, 我们假设 是一个下三角矩阵, 其对角线上的元素全为 1 , 而 是一个上三角矩阵。下面, 我会一步步地进行分解。

步骤 1: 我们从 的第一行开始, 确定 的第一行。

步骤 2: 使用 的第一行和 的第一行, 我们可以计算出 的第一列。

步骤 3: 接下来, 我们利用 的第一列和 的第一行来更新矩阵 , 这样我们就可以继续计算 和 的其他元素。

具体来说, 我们先设定:

和

从 开始, 我们有: - 对于第一行 的元素, , 因此 。 - 接下来, , 所以 。 - 最后, , 因此 。

现在 的第一行已经确定:

接下来, 我们使用 的第二行来解 的第二行和 的第二列。

  • 由于 的第二行第一个元素与 的第一行第一个元素的乘积等于 的第二行第一个元素 (即, ), 我们可以得出 。

接下来的步骤只需重复这个过程, 解出所有 和 的元素即可。

参考例 2.3.1

2.1.3.2 三对角方程组的追赶法

三对角方程组的一般形式可以用矩阵来表示, 就像这样:

在这里, 分别是对角线下方、对角线和对角线上方的系数, 而 是结果向量的元素。可知系数矩阵有如下的三角分解形式:

这个分解的过程可以帮助我们简化原始方程组的求解过程, 因为它把一个复杂的问题转换成了两个更容易解决的问题: 1. 首先解 , 其中 是一个中间向量。 2. 然后解 , 这样我们就得到了最终的解 。 在 中, 代表 的非对角线上的元素, 而在 中, 是对角线元素, 是非对角线上的元素。因为 的对角线元素都是 1, 所以我们不需要显示它们。 要开始这个过程, 我们首先需要计算 的对角线元素 和 的非对角线元素 , 这是通过以下关系进行的: - - 对于 - 对于

给出如下例子：首先, 我们的方程组为:

对于这个方程组, 我们有 。按照追赶法的步骤, 我们首先计算 和 。 1. 2. 3. 4. 5.

现在, 我们已经有了 和 的所有非零元素: 接下来, 我们解 来找到 。 1. 2. 3. 因此,

最后一步是解 来得到 。 1. 2. 3. 最终, 解为

参考例 2.3.2 #### 2.1.3.3 对称正定矩阵的 Cholesky 分解、平方根法

2.1.3.3.1 Cholesky 分解

  1. 对称矩阵是一个方形矩阵, 它满足性质 , 其中 表示矩阵 的转置, 即矩阵的行和列互换。在对称矩阵中, 任何一个位置上的元素 都等于它对角线对称位置的元素 。

  2. 正定矩阵则是更特殊的一类对称矩阵。一个对称矩阵 是正定的, 如果对于所有非零向量 , 都有 。直观上, 你可以将正定性看作是矩阵版的“正数”概念。

Cholesky 分解可以表达为：对于一个给定的对称正定矩阵 , 我们可以将它分解为 , 其中 是一个下三角矩阵, 而 是 的转置。这里的重点在于分解后的 矩阵, 它比原矩阵 要“简单”得多, 因为它是下三角的, 这使得进一步的计算更加容易处理。其物理意义可以看作是找到一个变换，这个变换能够将原始的“复杂”系统转化为更加“简单”的系统，使得其结构和性质更加清晰易懂，同时保留了原系统的本质特性。

以一个 矩阵为例, 让我们考虑矩阵 如下:

我们希望找到一个下三角矩阵 使得 。 应该是这样的形式:

在 Cholesky 分解中, 我们会逐元素地求解 矩阵。对于 矩阵, 我们首先解 使得 , 因此 。然后, 我们用 解 使得 , 所以 。最后, 我们解 使得 , 得出 。

现在让我们带入具体的数值来完成这个分解。

考虑矩阵 为:

那么: 1. 2. 3.

因此, Cholesky 分解得到的 矩阵为:

所以, 将重新构成原始矩阵 。

2.1.3.3.2 平方根法 / Cholesky 方法

Cholesky分解只适用于正定对称矩阵，它利用了矩阵的对称性和正定性质来减少计算量。具体来说，它大约只需要高斯消元法一半的运算量。这是因为它只需要计算一个下三角矩阵，而不是两个不同的矩阵（如在LU分解中）。

  1. 对给定的正定对称矩阵 执行 Cholesky 分解，得到下三角矩阵 和它的转置 ，满足 。
    • .
  2. 解方程组 得到向量 。
  3. 解方程组 得到最终的解向量 。
2.1.3.3.3 加边 Cholesky 方法

假设我们已经有了一个 的矩阵 的 Cholesky 分解, 即 。现在, 我们增加了一行和一列, 形成了 的矩阵 。

矩阵 可以分块表示为:

其中, 是一个 的列向量, 是一个标量。 我们的目标是构造 , 使得 。为此, 我们可以把 表示为:

这里 是一个 的列向量, 而 是一个标量。我们要找到合适的 和 , 使得 符合 的分解。

因为 , 我们可以通过求解 来找到 , 这里 可以通过向前替换法求得。接着, 我们要确保 满足 , 因为这是 的最后一个元素, 也就是 的最后一个对角元素。

这样我们就能通过 和 中的 和 来计算出 。

参考例 2.3.5

2.1.4 矩阵的条件数与病态方程组

2.1.4.1 扰动方程组、病态现象

  1. 扰动方程组涉及的是一个原始方程组经过微小变化后的新方程组。原始方程组可以写作 , 其中 是一个已知的矩阵, 是已知的向量, 而 是我们要求解的末知向量。如果 或 发生了微小变化, 比如变成了 或 , 其中 和 非常小, 新的方程组 就是扰动后的方程组。
  2. 病态现象描述的是一个数学问题的数值解对初始条件或者输入数据的微小变化极其敏感。在这种情况下，即便是很小的扰动，也可能导致输出结果的巨大偏差。

2.1.4.2 矩阵的条件数

  1. 条件数其实是一个衡量矩阵敏感度的数值，它描述了输入数据的微小变化如何影响输出结果的变化。
    1. 如果一个矩阵的条件数很大，那么线性方程组的解在系数矩阵有微小变化时，解会产生很大的变化，这意味着求解过程可能是不稳定的。相反，条件数小意味着方程组的解对系数矩阵的微小变动不那么敏感，求解过程更稳定。
    2. 条件数还与方程求解的精度有关。在实际计算中，由于舍入误差和数据误差的存在，条件数大的方程组可能导致最终解的大幅度误差
  2. 条件数的数学定义是矩阵 的范数 与其逆矩阵的范数 的乘积： 。
  3. 因
    • 解释了条件数的下限。条件数是矩阵的范数和其逆的范数的乘积，至少是 1。这是因为单位矩阵（）的范数是 1，并且任何矩阵与其逆的乘积等于单位矩阵。所以，这告诉我们即使是理想情况下，求解线性方程组时也会有一个基础的误差扩散界限。条件数等于 1 是最理想的情况，意味着没有误差放大。
  4. .
    • 证明：.
    • 表明条件数与矩阵的缩放无关。这说明了条件数是一个相对的度量，它不受矩阵是否被缩放的影响。在物理意义上，这意味着改变度量单位不会影响方程组解的稳定性。
  5. 若 为正交矩阵, 则 .
    • 如果 是正交矩阵, 则 并且 。于是:
    • 说明了正交矩阵的条件数为 1。正交矩阵的列（或行）向量是单位向量，并且两两正交，这使得它们不会放大误差，因此它们的条件数最理想。在物理问题中，使用正交变换通常不会引入额外的误差。
  6. 若 为正交矩阵, 则
    • 假设 是正交矩阵, 因此 , 并且 。那么：
    • 同样可以证明 。
    • 表明正交变换不改变条件数。这意味着无论是左乘还是右乘一个正交矩阵，都不会影响系统解的稳定性。在实际应用中，这意味着可以通过正交变换来简化问题，而不用担心会增加误差。
  7. 设 与 为 按模最大和最小的特征值, 则
    • 设 与 分别是矩阵 按模最大和最小的特征值。那么对于 2 -范数, 有:.因此:
    • 给出了条件数的一个估计，它关联了矩阵的最大和最小特征值。条件数至少与最大特征值与最小特征值的绝对值之比一样大。这提供了一种评估矩阵条件数大小的方法，并指出了特征值接近零的矩阵（即奇异矩阵或近似奇异矩阵）将有很高的条件数，导致数值不稳定。

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

采用迭代、分块、预条件处理等技巧；将线性方程的解视为某种极限过程的向量序列，近似解。

  1. 高阶稀疏线性方程组
  2. 主要运算：矩阵与向量的乘法
  3. 选代格式的构造
  4. 收敛性、收敛速度

3.1 向量序列和矩阵序列的极限

  1. 向量序列的极限
    1. 假设我们有一个向量序列 , 其中每一个 都是 中的一个向量。我们说这个序列收敛向量 , 如果对于任意给定的 , 存在一个正整数 , 使得当 时, 有:
    2. 逐分量观察: 如果 , 那么 收敛到 当且仅当每一个分量 都收敛到 $a_{i}。即：向量序列的收敛性等价于由向量分量构成的 个数列的收敛性
  2. 矩阵序列的极限
    1. 对于矩阵序列 , 其中每一个 都是 的矩阵, 我们说这个序列收敛到矩阵 , 如果对于任意给定的 , 存在一个正整数 , 使得当 时, 有: 。
    2. 计算 并观察是否趋近于零。

3.2 线性方程组的求解

所讨论的方程组是

其中 。记 或写成

3.3 迭代法

  1. 基本思想：将线性方程组 等价变形为 , 构造迭代关系式: 。
  2. 收敛性分析
    1. 若向量序列 收敛到 , 则
    3. 向量序列 收敛
  3. 定理：收敛的充要条件：
    • 推论：若矩阵 的范数 , 则 收敛

3.3.1 J迭代法

基本思想：求解第 个方程得到第 个未知量。

假设我们有一个线性方程组 , 其中 是一个 矩阵, 和 是 向量。

在分量形式下, 原方程 可以写作:

其中 是 的元素, 是 的元素, 是 的元素。 现在，我们把每个方程中的对角线元素 单独拿出来:

然后, 我们解出 :

表示为矩阵形式。首先, 我们把矩阵 分解为三个部分：对角矩阵 , 下三角矩阵 和上三角矩阵 。

这里, 包含 的对角元素, 而 和 包含 的下三角和上三角元素, 但对角线上的元素都是 0 。

接下来, 我们重新排列 这个方程, 使其变为:

然后, 我们对这个方程进行迭代:

  1. 定理：为严格行/列对角占优矩阵，则 J 迭代收敛。
  2. 通常，对角元越占优，收敛速度就越快。

3.3.2 G-S 迭代法

基本思想：使用最新计算出的分量进行迭代。

对于 , 按照以下公式更新 :

其中， 是迭代次数。

表示为矩阵形式，则有

将其改写为:

进一步整理, 得到:

最后, 解出 :

  1. 定理：为严格行/列对角占优矩阵或对称正定矩阵，则 G-S 迭代收敛。

3.3.3 SOR 迭代法

基本思想：当 时，收敛将会很慢，取 和 的一个适当的加权平均来改进 G-S 迭代收敛。

在超松弛迭代法中, 我们引入一个超松弛因子 , 来加速收敛。更新公式变为：

当 时, 这个方法就退化为普通的 G-S 方法。但当 在 1 和 2 之间时, 这个方法通常会比 G-S 更快地收敛。

可以用矩阵形式来SOR方法。首先, 将矩阵 分解为三个部分：对角矩阵 , 下三角矩阵 和上三角矩阵 。即：

其中 是对角矩阵，包含 的对角元素; 是 的严格下三角部分 (不包括对角线)， 是 的严格上三角部分 (不包括对角线)。

然后，SOR 方法的迭代步骤可以写成矩阵形式：

或者更紧湊地：

这里, 是超松驰因子, 。

  • 收敛性
    1. 定理 1：SOR 迭代收敛的必要条件是
    2. 定理 2：若 为对称正定矩阵，则当 时，SOR 迭代恒收敛

4 非线性方程和方程组的数值解法

非线性方程求根，通常需给定初值或求解范围，用迭代法求解。

4.1 二分法 / 对分法

理论基础：介值定理

假设我们有一个连续函数 , 在区间 上连续。现在, 我们知道在点 和点 处，函数的值分别是 和 。假设 小于零, 而 大于零 (或者反过来)，我们想要找到一个点 ，位于区间 内, 使得函数的值 正好等于零。

  1. 对区间 不断进行细分，缩小搜索区间 image.png

    1. 输入：,
    2. 终止条件：区间长度足够小 或
    3. 输出：

4.1.1 试位法

仍设 是方程 (4.1.1) 的一个有根区间, 且 , 并设在 上的根是惟一的, 令 . 对于区间 , 要在 找一点 , 它一般不取作 , 的中点, 而取为点 和 连线与 轴的交点, 即

如果 , 就找到了方程的根, 如 , 仍同二分法构造新的有根区间, 即 时, 令 , 否则令 .

4.2 不动点迭代法

基本思想：将方程 转换成等价形式 , 给定初值 , 构造迭代序列：。若收敛，则。

  1. 如何构造迭代格式？
  2. 是否收敛？迭代速度？
  3. 收敛的条件？
  • 一个区间上不动点的存在性和惟一性：
    1. 设 , 且 ，则 在 上一定存在不动点。
    2. 若 , 且存在常数 , 使 ，则 在 的不动点是惟一的。
      • Lipschitz 条件的理解：阿玮走在一条直路上，这条路可以是平坦的，也可以是起伏的。如果这条路是一个函数 ，那么 Lipschitz 条件就像是给这条路设定一个“最大坡度”。如果一个问题满足 Lipschitz 条件，那么我们可以更有信心地说，我们的数值方法将给出一个好的、接近真实解的答案。
  • 误差估计公式：
  • 构造迭代格式的要素
    1. 等价形式要满足
    2. 初值取自 的充分小值域

4.3 收敛性

4.3.1 全局收敛性

  1. 阿玮打开了高德地图，无论在这座大山的哪个位置出发，只要阿玮遵循高德地图的导航，最终都能到达山顶。--> 从任何初始点出发，都能到达同一个目标。
  2. 对于迭代方程 ,如果从任何初始点 出发, 都能趋近于同一个固定点 , 那么我们说该迭代方程具有全局收敛性。

4.3.2 局部收敛性

  1. 阿玮正在爬山，现在处于山脚下。阿玮的目标是到达山顶。局部收敛性就像是阿玮已经接近山顶，只需再走几步就能到达。在这个“局部”区域内，无论阿玮从哪个点出发（只要足够接近山顶），阿玮都能成功到达山顶。
  2. 给定一个迭代方程 , 如果从某个初始点 开始, 经过有限次迭代后, 能够趋近于某个固定点 , 那么我们说该迭代方程在该固定点 附近具有局部收敛性。

4.3.3 阶收敛

假设序列 收玫到 , 即 当 。如果存在一个常数 和一个整数 , 使得 - 那么我们说该序列具有 阶收敛性。 - 称为渐近误差常数. - 高阶收敛通常意味着更快地找到精确解，从而节省计算资源。 - 当 时, 也称 线性收敛, 时称超线性收敛, 时称平方收敛。

4.4 Newton 选代法

想象一下阿玮正在山上追逐一个滚动的球。阿玮想知道这个球最终会停在哪里，也就是找到这个山的最低点。Newton 迭代法就像是阿玮每次都走到当前位置的“最陡峭”的方向，直到阿玮找到那个最低点。

image.png
  1. 假设我们有一个函数 , 我们想找到 使得 。
    1. 选择一个初始点 。
    2. 进行迭代: 。
  2. 逻辑解释：
    1. 初始点 : 就像阿玮站在山上的一个点, 开始观察周围的地形。
    2. 导数 : 这是阿玮站在 这一点, 朝哪个方向最陡峭。也就是说, 阿玮应该朝哪个方向走, 才能最快地到达山脚。
    3. 迭代公式: 阿玮不断地按照这个“最陡峭”的方向走, 也就是不断地用迭代公式更新阿玮的 值, 直到 非常接近于零。
  3. 核心思想：局部近似
    1. 假设阿玮有一个复杂的函数 , 在某一点 附近, 阿玮可以用一个切线来近似这个函数。这个切线的方程是:
    2. 当这个切线与 轴交点时, , 解这个方程, 阿玮会得到:
  4. 收敛性：局部二阶收敛的。
    • 当阿玮越接近真正的零点时，误差会以二次的速度减小。
  5. 重根情形：
    1. 表示为 。其中 是一个在 处非零的可微函数, 是根的重数。
    2. 标准的 Newton 迭代法会遇到问题：其收敛速度会降低，甚至可能不收敛。这是因为在 处, 一阶导数 , 这会影响迭代公式 的效率。
    3. 方法 1：修正的 Newton 迭代法
    4. 方法 2：令 ，求出 的迭代格式

4.5 弦截法 / 割线法

image.png
  1. 基本思想：用一条弦线来近似替代原函数 ,然后找到这条弦线与 轴的交点，作为方程 的近似解。
  2. 选取两个初始点 和
  3. 这条弦的方程可以表示为:
  4. 找到这条弦与 轴的交点：
  5. 解得：。现在得到了一个新的点 , 这个点会比 和 更接近真正的根。
  6. 接下来可以用 和 重复这个过程, 直到找到一个足够接近真正根的点。

4.6 迭代加速收敛的方法

4.6.1 Aitken 加速方法

给定一个迭代序列 , Aitken 加速方法用以下公式生成一个新的序列 :

4.6.2 Steffensen 迭代方法

把关于函数 的不动点迭代与加速技巧结合起来。核心思想是用一个局部的二次逼近来加速收敛。

4.7 课后习题导引

4.7.1 习题 1

证明方程 在 有惟一的根. 用二分法求这个根, 要求误差界不超过 . 若要误差界不超过 或 , 分析各要多少次二分.

  1. 介值定理：
    1. 连续+区间端点值异号--> 至少有一个根
    2. 单调递增 --> 唯一根
  2. 二分法的误差界为：(Page 97)
    1. 对于误差界不超过 , 我们有 解这个不等式, 我们得到 。所以, 为了达到 的精度, 我们需要至少 4 次迭代。
      • 具体的迭代过程，参考例 4.2.1 的格式
    2. 对于误差界不超过 或 , 我们可以按照同样的方式解决。得到 (对于 的精度) 和 (对于 的精度)。

4.7.2 习题 2

用试位法求 在 的根, 要求误差界不超过 .

参考例 4.2.2

4.7.3 习题 3

方程 在 有一个根. 对下列 3 种迭代法, 试分别取区间 , 讨论迭代法在 的收敛性. 取 , 用其中一种收敛最快的方法求这个根, 使误差界不超过 . - 方程化为 , 迭代公式 ; - 方程化为 , 迭代公式 ; - 方程化为 , 迭代公式 .

参考书 102 页定理 4.3.3（Banach不动点定理）和例 4.3.2：设 为 的不动点, 在 的某个邻域 上存在且连续, 满足 , 则迭代法局部收敛。以下是一个证明示例：

又迭代收敛。

4.7.4 习题 4

分析方程 有多少个根, 且 - 对最小的根, 确定 及函数 使 对任意的 收敛； - 对其余的根, 也分别确定函数 , 讨论 的局部收敛性; - 用上述迭代法求方程的各个根, 使误差界不超过 .

  1. 画图来初步了解方程的根的数量和大致位置
  2. 找区间
  3. 牛顿法迭代：

4.7.5 习题 5

参考例 4.4. 1

4.7.6 习题 6

方程 有一个根, 试证明对任意的 , 迭代法 产生的序列 收玫到方程的根. 并取 . 用此迭代法求根, 要求误差界不超过 .

4.7.7 习题 7

$$ 迭代函数为又即迭代收敛于的根

$$

4.7.8 习题 8

参考例 4.5.4

4.7.9 习题 9

参考例 4.5.5

4.7.10 习题 10

设方程 . 试分别求此方程从小到大的第一个和第二个正根, 要求误差界不超过 .

  1. 证明：Banach 不动点定理（导数绝对值小于 1）
  2. 迭代计算

4.7.11 习题 11

是方程 的根, 确定这个根是几重根.

运用重根定理：如果 但 , 那么 是 的 重根。

4.7.12 习题 12

  1. 由迭代函数 , 在不动点 处有迭代方程
    • 可得
  2. 根据局部收敛阶定理, 令不动点处的尽量高的各阶导为 0 , 得:
  3. 求解线性方程组得 . 且因 , 故迭代收敛阶为 3 阶.

5 矩阵特征值问题的计算方法

6 插值法

7 函数逼近

8 数值积分与数值微分

9 常微分方程初值问题的数值解法

文章作者: Haowei
文章链接: http://howiehsu0126.github.io/2023/10/18/数值分析/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Haowei Hub！
数学数值分析