由于篇幅太长所以将笔记分成了两部分 (上 & 下)

# 数值计算下

# 线性方程组的直接解法

常用的数值解法分为直接法和迭代法。

一、直接法

直接法是指不考虑计算过程中的舍入误差，通过有限步运算得到方程精确解的方法。

1. 高斯消元法（Gauss elimination）：通过逐步消元将线性方程组转化为上三角方程组，然后进行回代求解。
2. 平方根法（Cholesky decomposition）：主要用于对称正定矩阵的求解，将矩阵分解为特定形式进行求解。
3. 主元素法（Pivoting method）：通过选择主元素提高计算的稳定性和精度。
4. 三角分解法（LU decomposition）：将系数矩阵分解为下三角矩阵和上三角矩阵的乘积，然后求解两个三角方程组得到解。
5. 追赶法（TDMA）：主要用于求解三对角线性方程组。

直接法适用于小型稠密矩阵。

二、迭代法

迭代法采用逐次逼近的方法，从某一个初始解出发，按照某种迭代格式逐步逼近方程组的解，直至满足精度要求。

1. 雅可比（Jacobi）迭代法。
2. 高斯 - 塞德尔（Gauss-Seidel）迭代法。
3. 松弛 SOR 迭代法。

迭代法适用于大型稀疏矩阵。

# 高斯消元法

高斯消元法（Gaussian Elimination）是一种用于求解线性方程组的直接方法。

一、基本思想

1. 通过一系列的初等行变换将线性方程组的增广矩阵化为行阶梯形矩阵。
2. 再进一步化为行最简形矩阵，从而得到方程组的解。

二、具体步骤

1. 首先，对于线性方程组，其中是系数矩阵，是未知数向量，是常数向量。将其写成增广矩阵的形式。
2. 然后进行初等行变换：
   • 对换两行。
   • 以非零数乘某一行。
   • 把某一行的若干倍加到另一行上。
3. 目标是把增广矩阵化为行阶梯形矩阵：
   • 从上往下，逐行进行处理。使得每一行第一个非零元素（称为主元）所在的列，下面的行中该列元素全为零。
4. 接着进一步化为行最简形矩阵：
   • 使得每一行的主元变为 1，并且主元所在列的其他元素变为零。
5. 最后进行回代求解：
   • 从最后一行开始，依次求出每个未知数的值。

消元法全部计算量：$S = S_1 + S_2=\frac{n}{3}(n^{2}+3n - 1)$。

高斯消元法的限制：$a_{kk}^{(k)}\neq0$，$k = 1,2,\cdots,n - 1$。

定理：方程$Ax = b$ 可以使用高斯消元法求解的充要条件是$A$ 的所有顺序主子式不为 0，即

$$\begin{vmatrix}a_{11}&\cdots&a_{1i}\\\vdots&\ddots&\vdots\\a_{i1}&\cdots&a_{ii}\end{vmatrix}\neq0$$

$\forall i = 1,2,\cdots,n$。$|A|\neq0$ 可以保证方程组有唯一解，但不能保证高斯消元法可以进行。

当$|a_{kk}^{(k)}|\to0$ 时，舍入误差会被放大，导致计算失败。

原因：

$$\epsilon\left(x_{1}^{*} / x_{2}^{*}\right)\leq\frac{\vert x_{1}^{*}\vert\epsilon\left(x_{2}^{*}\right)+\vert x_{2}^{*}\vert\epsilon\left(x_{1}^{*}\right)}{\vert x_{2}^{*}\vert^{2}}$$

选取绝对值最大的为主元。

主元素法分析

主元素法分析：

1. 若$\vert A\vert\neq0$，则$\vert a_{kk}\vert\cdots\vert a_{nk}\vert$ 一定至少有一非零元。（否则$\vert A\vert = 0$）。
2. 主元素法的适用范围：$\vert A\vert\neq0$。
3. 主元素法在一定程度上克服了高斯消元中的不稳定现象。
   • 列主元系法增加了$\sum^{n - 1}_{i=1}\left(n-i\right)$ 次比较操作。
   • 全主元素法增加了$\sum_{i = 1}^{n - 1}[(n - i + 1)^{2}-1]$ 次比较操作。
4. 不论哪种方式选出主元，再按上面步骤进行计算，都称为选主元的高斯消元法。
5. 计算经验与理论分析均表明：列主元素法与全主元素法具有同样良好的数值稳定性。实际中常采用列主元素法求解中小型稠密方程组。

# 三角分解

# LU 分解

LU 分解（LU Decomposition）是线性代数中一种重要的矩阵分解方法。它将一个方阵$A$ 分解为一个下三角矩阵$L$ 和一个上三角矩阵$U$ 的乘积，即$A = LU$。

其中，$L$ 是一个下三角矩阵，即矩阵中的所有元素都位于主对角线及其下方，且主对角线元素通常为 1（在一些特殊的 LU 分解形式中，如 Crout 分解，$L$ 的主对角线元素不一定为 1）；$U$ 是一个上三角矩阵，即矩阵中的所有元素都位于主对角线及其上方。

并不是所有方阵都可以进行 LU 分解，一个方阵$A$ 可以进行 LU 分解的一个常见的充分条件是它的所有顺序主子式都不为 0。

LU 分解的主要应用包括：

1. 求解线性方程组：给定线性方程组$Ax = b$，可将其转换为两个更简单的方程组$Ly = b$ 和$Ux = y$，先解下三角方程组得到$y$，再解上三角方程组得到$x$。
2. 计算矩阵的行列式：由于行列式可以通过对角线元素的乘积来计算，而$A$ 的行列式等于$L$ 和$U$ 的行列式的乘积，对于标准 LU 分解，$L$ 的行列式为 1，所以$A$ 的行列式的值即为$U$ 的对角线元素乘积。
3. 求矩阵的逆：利用$A^{-1} = U^{-1}L^{-1}$，由于$L$ 和$U$ 是三角矩阵，它们的逆相对容易计算。

杜利特尔算法的具体步骤如下：

设矩阵$A$ 为$n×n$ 矩阵，$L$ 和$U$ 的初始值设定如下：

$L$ 为单位下三角矩阵，即$L(i, i) = 1$（主对角线元素为 1），$L(i, j) = 0$（$i < j$ 时，非主对角线元素为 0）；

$U$ 初始化为全零矩阵。

对于$r$ 从 1 到$n-1$ 进行以下操作：

1. 计算$U$ 的第$r$ 行元素：

   $u_{rj} = a_{rj} - \sum_{k=1}^{r-1} l_{rk}u_{kj} \quad (j = r, r + 1, \cdots, n)$

2. 计算$L$ 的第$r$ 列元素（$r \neq n$）：

   $l_{ir} = \frac{a_{ir} - \sum_{k=1}^{r-1} l_{ik}u_{kr}}{u_{rr}} \quad (i = r + 1, r + 2, \cdots, n)$

经过这些步骤，最终得到的$L$ 和$U$ 矩阵即为$A$ 的 LU 分解结果。

通过解方程组$Ly = b$ 和$Ux = y$，获得最终的结果。

# 平方根法 - 乔列斯基分解法

乔列斯基（Cholesky）分解是对于对称正定矩阵的一种分解方法。

若矩阵

$$A=\begin{bmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n}\\\vdots&\vdots&\ddots&\vdots\\a_{n1}&a_{n2}&\cdots&a_{nn}\end{bmatrix}$$

则存在下三角矩阵

$$L=\begin{bmatrix}l_{11}&0&\cdots&0\\l_{21}&l_{22}&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\l_{n1}&l_{n2}&\cdots&l_{nn}\end{bmatrix}$$

使得$A = LL^T$，其中

$$L^T=\begin{bmatrix}l_{11}&l_{21}&\cdots&l_{n1}\\0&l_{22}&\cdots&l_{n2}\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&l_{nn}\end{bmatrix}$$

通过比较法可得计算下三角矩阵$L$ 中元素的公式为：

1. 计算主对角线元素$l_{jj}$：$l_{jj}=\sqrt{a_{jj}-\sum_{k = 1}^{j - 1}l_{jk}^{2}}$，$j = 1,2,\cdots,n$.
2. 计算非主对角线元素$l_{ij}$（$i>j$）：$l_{ij}=\frac{1}{l_{jj}}\left(a_{ij}-\sum_{k = 1}^{j - 1}l_{ik}l_{jk}\right)$.

紧凑法：对角类似 LU 分解步骤，但是需要开发，后续元素类似 LU 分解，要除子方阵的坐上顶角元素

见例题

# 改进的平方根法

$LDL^T$

设$A$ 为对称正定阵，则$A$ 可唯一分解为$A = LDL^T$，其中$L$ 为单位下三角阵，$D$ 为对角阵。即：

$A=\begin{bmatrix}1&0&\cdots&0\\l_{21}&1&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\l_{n1}&l_{n2}&\cdots&1\end{bmatrix}\begin{bmatrix}d_{1}&&&\\&d_{2}&&\\&&\ddots&\\&&&d_{n}\end{bmatrix}\begin{bmatrix}1&l_{21}&\cdots&l_{n1}\\0&1&\cdots&l_{n2}\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&1\end{bmatrix}$

LDLT 分解过程

借助 LU 分解可得：

$A=\begin{bmatrix}1&0&\cdots&0\\l_{21}&1&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\l_{n1}&l_{n2}&\cdots&1\end{bmatrix}\begin{bmatrix}d_{1}&&&\\&d_{2}&&\\&&\ddots&\\&&&d_{n}\end{bmatrix}\begin{bmatrix}1&l_{21}&\cdots&l_{n1}\\0&1&\cdots&l_{n2}\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&1\end{bmatrix}=\begin{bmatrix}1&0&\cdots&0\\l_{21}&1&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\l_{n1}&l_{n2}&\cdots&1\end{bmatrix}\begin{bmatrix}d_{1}&d_{1}l_{21}&\cdots&d_{1}l_{n1}\\0&d_{2}&\cdots&d_{2}l_{n2}\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&d_{n}\end{bmatrix}$

其分解过程为：

$d_{i}=a_{ii}-\sum_{k = 1}^{i - 1}l_{ik}^{2}d_{k}$.

$l_{ij}=\frac{1}{d_{j}}\left(a_{ij}-\sum_{k = 1}^{j - 1}l_{ik}l_{jk}d_{k}\right)$.

# 平方根与改进的平方根法小结

一、平方根法

1. 对于对称正定阵$A$ 完成乔列斯基分解后，可转化为方程组求解：
   • $L y = b$；
   • $L^{\top}x = y$.

二、改进的平方根法

1. 对于对称正定阵$A$ 完成$LDL^T$ 分解后，可转化为：
   • $L y = b$；
   • $DL^{\top}x = y$，进一步可写成$L^{\top}x = D^{-1}y$.

三、共同点与优势

1. 二者都只适用于对称正定阵。
2. 引入辅助量后，计算量差不多。
3. 改进的平方根法不需要开方运算，计算量约为高斯消元法的一半$\Omega\left(\frac{n^3}{6}\right)$，且不必选主元，数值稳定性良好。

# 追赶法

追赶法与三对角矩阵分解定理

一、三对角矩阵

一个 $n \times n$ 的三对角矩阵 $A$ 具有如下形式：

$$A = \begin{bmatrix} b_1 & c_1 & 0 & \cdots & 0 \\ a_2 & b_2 & c_2 & \cdots & 0 \\ 0 & a_3 & b_3 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & b_n \end{bmatrix}$$

其中 $a_i$、$b_i$、$c_i$ 为已知系数。

二、三对角矩阵分解定理

对于三对角矩阵

$$A=\begin{bmatrix}b_{1}&c_{1}&&&\\a_{2}&b_{2}&c_{2}&&\\&a_{3}&b_{3}&c_{3}&\\&&\ddots&\ddots&\ddots\\&&a_{n - 1}&b_{n - 1}&c_{n - 1}\\&&&a_{n}&b_{n}\end{bmatrix}$$

若满足

$$\begin{cases}\vert b_{1}\vert>\vert c_{1}\vert>0\\\vert b_{i}\vert>\vert a_{i}\vert+\vert c_{i}\vert,a_{i}c_{i}\neq0,i = 2,\cdots,n - 1\\\vert b_{n}\vert>\vert a_{n}\vert\end{cases}$$

则它可以分解为

$$A = LU=\begin{bmatrix}\alpha_{1}&&&&\\r_{2}&\alpha_{2}&&&\\&r_{3}&\alpha_{3}&&\\&&\ddots&\ddots&\\&&&r_{n}&\alpha_{n}\end{bmatrix}\begin{bmatrix}1&\beta_{1}&&&\\&1&\beta_{2}&&\\&&\ddots&\ddots&\\&&&1&\beta_{n - 1}\\&&&&1\end{bmatrix}$$

三对角阵的分解实质是 LU 分解的应用，其系数可由以下公式确定：

1. $\alpha_{1}=b_{1}$。
2. $\beta_{1}=c_{1}/b_{1}$。
3. $\beta_{i}=c_{i}/(b_{i}-a_{i}\beta_{i - 1}),i = 2,\cdots,n - 1$。
4. $r_{i}=a_{i},i = 2,\cdots,n$。
5. $\alpha_{i}=b_{i}-\alpha_{i}\beta_{i - 1},i = 2,\cdots,n$。

追赶法是一种高效的求解三对角线性方程组的方法，其计算复杂度为 $O(n)$，远低于一般的高斯消元法的 $O(n^3)$。

# 向量范数与矩阵范数

一、向量的范数

向量的范数是衡量向量大小的一种度量方式。

1. 常见的向量范数有以下几种：

   • $l_1$ 范数：也称为曼哈顿范数，对于向量$x=(x_1,x_2,\cdots,x_n)$，其$l_1$ 范数定义为$\vert\vert x\vert\vert_1=\sum_{i=1}^{n}\vert x_i\vert$。
   • $l_2$ 范数：也称为欧几里得范数，对于向量$x=(x_1,x_2,\cdots,x_n)$，其$l_2$ 范数定义为$\vert\vert x\vert\vert_2=\sqrt{\sum_{i=1}^{n}x_i^2}$。
   • $l_{\infty}$ 范数：也称为最大范数，对于向量$x=(x_1,x_2,\cdots,x_n)$，其$l_{\infty}$ 范数定义为$\vert\vert x\vert\vert_{\infty}=\max_{1\leq i\leq n}\vert x_i\vert$。

2. 向量范数的性质：

   • 非负性：对于任意向量$x$，$\vert\vert x\vert\vert\geq0$，当且仅当$x=0$ 时，$\vert\vert x\vert\vert=0$。
   • 齐次性：对于任意向量$x$ 和标量$\alpha$，$\vert\vert\alpha x\vert\vert=\vert\alpha\vert\vert\vert x\vert\vert$。
   • 三角不等式：对于任意向量$x$ 和$y$，$\vert\vert x + y\vert\vert\leq\vert\vert x\vert\vert+\vert\vert y\vert\vert$。

二、矩阵的范数

矩阵的范数也是一种度量矩阵大小的方式。

1. 常见的矩阵范数有以下几种：

   • 矩阵的$l_1$ 范数：对于矩阵$A=(a_{ij})_{m\times n}$，其$l_1$ 范数定义为$\vert\vert A\vert\vert_1=\max_{1\leq j\leq n}\sum_{i=1}^{m}\vert a_{ij}\vert$，即矩阵每一列元素绝对值之和的最大值。
   • 矩阵的$l_2$ 范数：也称为谱范数，对于矩阵$A$，其$l_2$ 范数定义为$\vert\vert A\vert\vert_2=\sqrt{\lambda_{max}(A^TA)}$，其中$\lambda_{max}(A^TA)$ 表示矩阵$A^TA$ 的最大特征值。
   • 矩阵的$l_{\infty}$ 范数：对于矩阵$A=(a_{ij})_{m\times n}$，其$l_{\infty}$ 范数定义为$\vert\vert A\vert\vert_{\infty}=\max_{1\leq i\leq m}\sum_{j=1}^{n}\vert a_{ij}\vert$，即矩阵每一行元素绝对值之和的最大值。
   • 弗罗贝尼乌斯范数（Frobenius norm）：对于矩阵$A=(a_{ij})_{m\times n}$，其弗罗贝尼乌斯范数定义为$\vert\vert A\vert\vert_F=\sqrt{\sum_{i=1}^{m}\sum_{j=1}^{n}\vert a_{ij}\vert^2}$。

2. 矩阵范数的性质：

   • 非负性：对于任意矩阵$A$，$\vert\vert A\vert\vert\geq0$，当且仅当$A=0$ 时，$\vert\vert A\vert\vert=0$。
   • 齐次性：对于任意矩阵$A$ 和标量$\alpha$，$\vert\vert\alpha A\vert\vert=\vert\alpha\vert\vert\vert A\vert\vert$。
   • 三角不等式：对于任意矩阵$A$ 和$B$，$\vert\vert A + B\vert\vert\leq\vert\vert A\vert\vert+\vert\vert B\vert\vert$。
   • 相容性：对于任意矩阵$A$ 和$B$，$\vert\vert AB\vert\vert\leq\vert\vert A\vert\vert\vert\vert B\vert\vert$。

向量的范数和矩阵的范数在数值分析、线性代数、优化问题等领域中都有广泛的应用。

# 线性方程组的迭代解法

都是基于不动点，或者说序列收敛的原理进行迭代，所以迭代的前提是递推序列能够收敛。

# 雅可比（Jacobi）迭代法

一、基本原理

对于方程组$\sum_{j = 1}^{n}a_{ij}x_{j}=b_{i}\ (i = 1,2,\cdots,n)$，记作$Ax = b$，其中$A$ 为非奇异阵且$a_{ii}\neq0\ (i = 1,2,\cdots,n)$。

1. 将矩阵$A$ 分裂为$A = D - L - U$，其中：

   $$D=\begin{pmatrix}a_{11}&&&\\&a_{22}&&\\&&\ddots&\\&&&a_{nn}\end{pmatrix}$$

   是对角矩阵。

   $$L = -\begin{pmatrix}0&&&\\a_{21}&0&&\\a_{31}&a_{32}&0&\\\vdots&\vdots&\ddots&\ddots&\\a_{n1}&a_{n2}&\cdots&a_{n,n - 1}&0\end{pmatrix}$$

   是下三角矩阵（不包括对角元素）。

   $$U = -\begin{pmatrix}0&a_{12}&a_{13}&\cdots&a_{1n}\\&0&a_{23}&\cdots&a_{2n}\\&&\ddots&\vdots\\&&&0&a_{n - 1,n}\\&&&&0\end{pmatrix}$$

   是上三角矩阵（不包括对角元素）。

2. 将方程组的第$i$ 个方程用$a_{ii}$ 去除再移项，得到等价方程组

   $$x_{i}=\frac{1}{a_{ii}}\left(b_{i}-\sum_{\substack{j = 1\\j\neq i}}^{n}a_{ij}x_{j}\right)\ (i = 1,2,\cdots,n)$$

二、迭代公式

1. 从初始向量$x^{(0)}=(x_{1}^{(0)},x_{2}^{(0)},\cdots,x_{n}^{(0)})^{T}$ 开始，根据迭代公式

   $x_{i}^{(k + 1)}=\frac{1}{a_{ii}}\left(b_{i}-\sum_{\substack{j = 1\\j\neq i}}^{n}a_{ij}x_{j}^{(k)}\right)$

   进行迭代，其中$x^{(k)}=(x_{1}^{(k)},x_{2}^{(k)},\cdots,x_{n}^{(k)})^{T}$ 为第$k$ 次迭代向量。

2. 迭代公式的矩阵形式为

   $$\begin{cases}x^{(0)}&(初始向量)\\x^{(k + 1)}=B_{0}x^{(k)} + f\end{cases}$$

   其中$B_{0}=I - D^{-1}A = D^{-1}(L + U)$ 称为雅可比方法迭代矩阵，$f = D^{-1}b$。

三、特点

1. 公式简单，每迭代一次只需计算一次矩阵和向量乘法。
2. 在用计算机计算时，需要两组工作单元，以存储$x^{(k)}$ 及$x^{(k + 1)}$。

雅可比迭代法适用于一些系数矩阵具有特定结构的线性方程组求解，但其收敛速度可能较慢，且收敛性取决于系数矩阵的性质。

# 高斯 - 塞得尔 (Gauss-Seidel) 迭代法

高斯 - 塞德尔（Gauss-Seidel）迭代法也是一种求解线性方程组的迭代方法。

一、基本原理

对于线性方程组$Ax = b$，其中$A$ 是$n\times n$ 的非奇异矩阵，$x$ 是$n$ 维未知向量，$b$ 是$n$ 维已知向量。

1. 同样将矩阵$A$ 分解为$A = D - L - U$，其中：

   • $D$ 是对角矩阵，由$A$ 的对角元素组成。
   • $L$ 是下三角矩阵（不包括对角元素）。
   • $U$ 是上三角矩阵（不包括对角元素）。

2. 将线性方程组$Ax = b$ 改写为$(D - L)x = Ux + b$，进一步得到$x = (D - L)^{-1}Ux + (D - L)^{-1}b$.

   确切的说是$(D - L)x^{(k+1)} = Ux^{(k)} + b$, 进一步得到 $x^{(k+1)} = (D - L)^{-1}Ux^{(k)} + (D - L)^{-1}b$

   于是 Gauss-Seidel 迭代公式的矩阵形式为

   $$x^{(k+1)}=Gx^{(k)}+f\\ G=(D-L)^{-1}U,\quad f=(D-L)^{-1}b.$$

二、迭代公式

1. 从一个初始向量$x^{(0)}=(x_{1}^{(0)},x_{2}^{(0)},\cdots,x_{n}^{(0)})^{T}$ 开始，进行迭代。

   $x_{i}^{(k + 1)}=\frac{1}{a_{ii}}\left(b_{i}-\sum_{j = 1}^{i - 1}a_{ij}x_{j}^{(k + 1)}-\sum_{j = i + 1}^{n}a_{ij}x_{j}^{(k)}\right)\ (i = 1,2,\cdots,n)$。

2. 迭代公式的矩阵形式为

   $\begin{cases}x^{(0)}&(初始向量)\\x^{(k + 1)}=(D - L)^{-1}Ux^{(k)} + (D - L)^{-1}b\end{cases}$.

三、特点

1. 与雅可比迭代法相比，高斯 - 塞德尔迭代法在计算$x_{i}^{(k + 1)}$ 时，使用了已经更新的$x_{1}^{(k + 1)},\cdots,x_{i - 1}^{(k + 1)}$ 的值，而雅可比迭代法在计算$x_{i}^{(k + 1)}$ 时只使用上一次迭代的$x^{(k)}$ 的值。
2. 通常情况下，高斯 - 塞德尔迭代法的收敛速度比雅可比迭代法快。
3. 但收敛性仍然取决于系数矩阵$A$ 的性质。如果矩阵$A$ 是严格对角占优矩阵或对称正定矩阵等，高斯 - 塞德尔迭代法通常是收敛的。

# 迭代法基本定理

对于一阶定常迭代法$x^{(k + 1)} = Bx^{(k)} + f$，迭代法收敛的充要条件是谱半径$\rho(B)<1$.

对于一个方阵$A$，其谱半径$\rho(A)$ 定义为$A$ 的特征值的模的最大值。

1. 首先求出矩阵$A$ 的特征值。

   • 求解特征方程$\vert A-\lambda I\vert = 0$，其中$I$ 是单位矩阵，$\lambda$ 为待求的特征值。
   • 对于$n\times n$ 的矩阵，这个特征方程是一个$n$ 次多项式方程，求解这个方程可以得到$n$ 个特征值$\lambda_1,\lambda_2,\cdots,\lambda_n$。

2. 然后计算特征值的模$\vert\lambda_i\vert$。

3. 最后确定谱半径$\rho(A)=\max\{\vert\lambda_1\vert,\vert\lambda_2\vert,\cdots,\vert\lambda_n\vert\}$，即特征值的模的最大值。

若$A$ 为严格对角占优矩阵则雅可比和高斯 - 赛德尔迭代法均收敛

优点：充分利用已经获得的最新数据
缺点：更新过程顺序执行，不适合并行

# 超松弛（SOR）迭代法

一、常见的线性方程组求解方法除了高斯 - 塞德尔迭代法还有：

1. 直接法：如高斯消元法等，通过有限步运算直接求得方程组的精确解。适用于系数矩阵规模较小或结构特殊的情况。
2. 雅可比迭代法：将系数矩阵分裂为对角矩阵、下三角矩阵和上三角矩阵之和，通过迭代逐步逼近方程组的解。
3. 共轭梯度法：一种适用于求解对称正定线性方程组的迭代方法，具有收敛速度快的特点。

二、超松弛（SOR）迭代法

1. 基本思想：

   SOR 迭代法是对高斯 - 塞德尔迭代法的一种修正，旨在通过引入一个控制因子（松弛因子）ω 来更好地控制收敛速度。

   记$\Delta x^{(k)} = x^{(k + 1)} - x^{(k)}$ 为迭代格式的修正量，将迭代格式看成是前一步值加上一个修正量得到的。在修正量$\Delta x^{(k)}$ 上乘以一个控制因子 ω。

   当 ω>1 时为超松弛迭代；当 ω<1 时为低松弛迭代。

2. 公式推导：

   • 若$x^{(k + 1)}$ 为雅可比迭代格式，则有：
     $x^{(k + 1)}=(1-\omega)x^{(k)}+\omega\left((I-D^{-1}A)x^{(k)}+D^{-1}b\right)=\left(I-\omega D^{-1}A\right)x^{(k)}+\omega D^{-1}b$，称为阻尼雅可比法。

   • 若$x^{(k + 1)}$ 为高斯 - 塞德尔迭代格式，则有：
     $x^{(k + 1)}=(1-\omega)x^{(k)}+\omega\left(D^{-1}\left(Lx^{(k + 1)}+Dx^{(k)} - 1\right)\right)=(D-\omega L)^{-1}((1-\omega)D+\omega U)x^{(k)}+\omega(D-\omega L)^{-1}$，称为逐次超松弛迭代法（SOR）

     B=L_{\omega}=(D-\omega L)^{-1}((1-\omega)D+\omega U),\quad f=\omega(D-\omega L)^

3. 迭代过程：

   • 首先用高斯 - 塞德尔迭代法定义辅助量$\tilde{x}_{i}^{(k + 1)}=\left(b_{i}-\sum_{j = 1}^{i - 1}a_{ij}x_{j}^{(k + 1)}-\sum_{j = i + 1}^{n}a_{ij}x_{j}^{(k)}\right)/a_{ii}$。
   • 再由$x^{(k)}$ 与$\tilde{x}^{(k + 1)}$ 的加权平均定义$x^{(k + 1)}$，即：$x_{i}^{(k + 1)}=x_{i}^{(k)}+\omega\left(\tilde{x}_{i}^{(k + 1)}-x_{i}^{(k)}\right)=(1-\omega)x_{i}^{(k)}+\omega\tilde{x}_{i}^{(k + 1)}=x_{i}^{(k)}+\omega\left(b_{i}-\sum_{j = 1}^{i - 1}a_{ij}x_{j}^{(k + 1)}-\sum_{j = i}^{n}a_{ij}x_{j}^{(k)}\right)/a_{ii}$.

   笔算直接用公式就行了，写代码用矩阵分解

4. 收敛条件：

   • SOR 迭代法收敛的必要条件是$0<\omega<2$。
   • 若$Ax = b$，且$A$ 为对称正定阵，$0<\omega<2$，则 SOR 迭代法收敛。
   • 若$Ax = b$，且$A$ 为严格对角占优矩阵，$0<\omega\leq1$，则 SOR 迭代法收敛。

# 非线性方程与方程组的数值解法

# 二分法

非线性方程二分法求根是一种用于求解方程$f(x)=0$ 的数值方法，主要适用于求解在给定区间$[a,b]$ 上连续且$f(a)$ 与$f(b)$ 异号的情况。

一、基本原理

1. 由于函数$f(x)$ 在区间$[a,b]$ 上连续且$f(a)$ 与$f(b)$ 异号，根据零点定理可知，在区间$[a,b]$ 内至少存在一个根。
2. 取区间的中点$c=(a + b)/2$.
3. 然后判断$f(c)$ 的值：
   • 如果$f(c)=0$，那么$c$ 就是方程的根。
   • 如果$f(c)$ 与$f(a)$ 异号，则说明根在区间$[a,c]$ 内，此时令$b = c$.
   • 如果$f(c)$ 与$f(b)$ 异号，则说明根在区间$[c,b]$ 内，此时令$a = c$.
4. 重复上述步骤，不断缩小根所在的区间，直到达到所需的精度。

二、精度分析

1. 每次迭代后，区间长度变为原来的一半。
2. 经过$k$ 次迭代后，区间长度为$(b - a)/2^{k}$.
3. 此时，根的近似值$x_k$ 与精确值$x^*$ 之间的误差满足$\vert x^* - x_k\vert\leq(b - a)/2^{k + 1}$.
4. 给定精度$\epsilon$，只需使$(b - a)/2^{k + 1}\leq\epsilon$，可求得$k$ 值。即有$k\geq\log_2\frac{b - a}{\epsilon}-1$.

三、优点和缺点

1. 优点：

   • 二分法是一种可靠的方法，只要满足条件，一定能收敛到方程的根。
   • 算法简单，容易实现。

2. 缺点：

   • 收敛速度相对较慢，是线性收敛。
   • 要求函数在区间上连续且两端点函数值异号，条件较为严格。

# 不动点迭代及其收敛性

一、不动点迭代的概念

对于方程$f(x)=0$，通过变换将其转化为等价形式$x=\varphi(x)$。若所求的$x$ 满足$f(x^*) = 0$，则$x^*=\varphi(x^*)$，此时$x^*$ 为函数$\varphi(x)$ 的一个不动点。构造迭代方程$x_{k + 1}=\varphi(x_k)$，若对任何$x\in[a,b]$，序列$\{x_k\}$ 有极限$\lim\limits_{k\to\infty}x_k = x^*$，则称该迭代方程收敛，这种迭代法称为不动点迭代法.

二、收敛性分析

2. 压缩映象原理：
   • 设$\varphi(x)\in C[a,b]$ 满足以下条件：
     • 对任意$x\in[a,b]$，有$a\leq\varphi(x)\leq b$。
     • 存在常数$0<L<1$，对任意$x,y\in[a,b]$ 有$\vert\varphi(x)-\varphi(y)\vert\leq L\vert x - y\vert$。
   • 则$\varphi(x)$ 在$[a,b]$ 存在唯一不动点$x^*$，且对任意$x_0\in[a,b]$，由$x_{k + 1}=\varphi(x_k)$ 得到的序列$\{x_k\}$ 有$\lim\limits_{k\to\infty}x_k = x^*$，并有误差估计$\vert x_k - x^*\vert\leq\frac{L^k}{1 - L}\vert x_1 - x_0\vert$。
3. 条件$\vert\varphi(x)-\varphi(y)\vert\leq L\vert x - y\vert$：
   • 设$\varphi(x)\in C^1[a,b]$ 且对任意$x\in[a,b]$ 都有$\vert\varphi'(x)\vert\leq L<1$。
   • 根据拉格朗日中值定理，对任意$x,y\in[a,b]$，有$\vert\varphi(x)-\varphi(y)\vert=\vert\varphi'(\xi)(x - y)\vert\leq L\vert x - y\vert$，其中$\xi\in(a,b)$。
   • 故上述定理中的条件常被表述成$\vert\varphi'(x)\vert<1$。

三、总结

不动点迭代法是一种通过不断迭代函数$\varphi(x)$ 来逼近方程$f(x)=0$ 的根的方法。其收敛性取决于函数$\varphi(x)$ 的性质，特别是满足一定的压缩条件时，迭代序列能够收敛到唯一的不动点。在实际应用中，需要根据具体问题选择合适的变换函数$\varphi(x)$，并分析其收敛性，以确保迭代法的有效性。

# 不动点加速迭代

斯特芬森（Steffensen）迭代法是一种加速迭代收敛的方法。

一、基本原理

对于方程$f(x)=0$，将其转化为等价形式$x=\varphi(x)$，构造迭代公式$x_{n + 1}=\varphi(x_n)$。斯特芬森迭代法是在这个基础上进行改进。

设$y_n=\varphi(x_n)$，$z_n=\varphi(y_n)$，则斯特芬森迭代公式为：

$$x_{n + 1}=x_n-\frac{(y_n - x_n)^2}{z_n - 2y_n + x_n}$$

# 牛顿迭代法

# 牛顿迭代法原理

1. 基本思路：
   • 牛顿法的核心是将非线性方程$f(x)=0$ 线性化。
2. 推导过程：
   • 假设方程$f(x)=0$ 有根$x_k$，将$f(x)$ 在$x_k$ 处展开，得到$f(x)\approx f(x_k)+f'(x_k)(x - x_k)$。
   • 由于$f(x)=0$，所以可以近似表示为$f(x_k)+f'(x_k)(x - x_k)=0$。
   • 化简这个等式得到$x=x_k-\frac{f(x_k)}{f'(x_k)}$。
3. 迭代公式：
   • 根据上述化简结果，牛顿法的迭代公式为$x_{k + 1}=x_k-\frac{f(x_k)}{f'(x_k)}$，其中$k = 0,1,\cdots$。

牛顿法通过不断迭代这个公式来逼近非线性方程的根。每次迭代都基于当前的近似根$x_k$，利用函数值$f(x_k)$ 和导数值$f'(x_k)$ 来计算下一个更接近真实根的近似值$x_{k+1}$.

牛顿迭代法的收敛性：牛顿迭代格式在$x^*$ 附件至少平凡收敛。

# 简化牛顿法

简化牛顿法又称平行弦法

1. 定义

   简化牛顿法是将牛顿迭代公式$\varphi(x) = x - \frac{f(x)}{f'(x)}$ 中的$f'(x)$ 用常数$C$ 代替，得到新的迭代公式。

2. 收敛性

   为了在$x^*$（根的真实值）附近有更好的收敛性，令$\left|\varphi'(x^*)\right|=\left|1 - \frac{f'(x^*)}{C}\right| = 0$，由此得到$C = f'(x^*)$。然而在实际应用中，很难得到$x^*$ 的值，所以通常取$C = f'(x_0)$，其中$x_0$ 是初始值。

<img src="数值计算下.assets/image-20241114221700148.png" alt="image-20241114221700148" style="zoom:50%;" />

引例 Sigmod

题目内容如下：

用牛顿迭代求解函数$f(x)=\text{sig}(x) - 0.5$ 的根，其中$\text{sig}(x)=\frac{e^{x}}{1 + e^{x}}$ 被称为 sigmoid 函数。

解答

1. 由图像知，$x = 0$ 是$f(x)$ 的根。
2. 牛顿迭代格式为：

   $$x_{k + 1}=x_{k}-\frac{f(x_{k})}{f^{\prime}(x_{k})}=x_{k}-\frac{\frac{e^{x_{k}}}{1 + e^{x_{k}}}-0.5}{e^{x_{k}}\left(\frac{1}{1 + e^{x_{k}}}-\frac{e^{x_{k}}}{\left(1 + e^{x_{k}}\right)^{2}}\right)}=x_{k}-\frac{\frac{e^{x_{k}}}{1 + e^{x_{k}}}-0.5}{e^{x_{k}}\left(\frac{1 + e^{x_{k}}-e^{x_{k}}}{\left(1 + e^{x_{k}}\right)^{2}}\right)}=x_{k}-\frac{\frac{e^{x_{k}}}{1 + e^{x_{k}}}-0.5}{\frac{e^{x_{k}}}{\left(1 + e^{x_{k}}\right)^{2}}}=x_{k}-\left(\frac{e^{2x_{k}}-1}{2e^{x_k}}\right)$$

   选不同初值迭代结果如下：

   初值$x_{0}$/k	0	1	2	3	4
   $x_{0}=1.5$	1.500 000	-0.629 280	0.042 362	-0.000 013	0.000 000
   $x_{0}=2.5$	2.500 000	-3.550 205	13.845 65	-515287.6	inf

<img src="数值计算下.assets/image-20241114221906890.png" alt="image-20241114221906890" style="zoom:33%;" />

1. 平行弦法

• 对于方程$f(x) = 0$，牛顿迭代公式为$x_{k + 1}=x_{k}-\frac{f(x_{k})}{f^{\prime}(x_{k})}$。

  • 平行弦法是将牛顿迭代公式中的$f^{\prime}(x)$ 用常数$C$ 代替，迭代公式变为x_{k + 1}=x_{k}-\frac{f(x_{k})}

  • 在本题中$f(x)=\text{sig}(x)-0.5=\frac{e^{x}}{1 + e^{x}}-0.5$，$f^{\prime}(x)=\frac{e^{x}}{\left(1 + e^{x}\right)^{2}}$.