Notes for Numerical Analysis
本文最后更新于：9 个月前
绪论
定理 设 \(\tilde{x}\) 是 \(x\) 的近似值，若 \(\tilde{x}\) 可表示为 \[ \tilde{x}= \pm a_1 . a_2 \cdots a_n \cdots \times 10^m \] 其中 \(a_i\) 是 0 到 9 中的数字, 且 \(a_1 \neq 0\). 若 \[ 0.5 \times 10^{m-n}<|\tilde{x}-x| \leq 0.5 \times 10^{m-n+1}, \] 则 \(\tilde{x}\) 恰好有 \(n\) 位有效数字.
Gram 矩阵
定理 设 \(\mathbb{S}\) 是内积空间, \(u_1, u_2, \ldots, u_n \in \mathbb{S}\), 则 \(u_1, u_2, \ldots, u_n\) 线性无关的充要 条件是矩阵 \(G\) 非奇异, 其中 \[ G=\left[\begin{array}{cccc} \left(u_1, u_1\right) & \left(u_2, u_1\right) & \cdots & \left(u_n, u_1\right) \\ \left(u_1, u_2\right) & \left(u_2, u_2\right) & \cdots & \left(u_n, u_2\right) \\ \vdots & \vdots & & \vdots \\ \left(u_1, u_n\right) & \left(u_2, u_n\right) & \cdots & \left(u_n, u_n\right) \end{array}\right] . \] 这个矩阵就称为 \(u_1, u_2, \ldots, u_n\) 的 Gram 矩阵
使用反证法，假设奇异->线性相关，假设线性相关->奇异
算子范数
（谱半径比任给的算子范数都小） 设 \(\mathbf{A} \in \mathbf{C}^{n \times n}\), 则对 \(\mathbf{C}^{n \times n}\) 上任何一种矩阵范数 \(\|\cdot\|\), 都有 \[ \rho(\mathbf{A}) \leqslant\|\mathbf{A}\| \] 证设 \(\mathbf{A}\) 的属于特征值 \(\lambda\) 的特征向量为 \(\mathbf{x}\), 取与矩阵范数 \(\|\cdot\|\) 相 容的向量范数 \(\|\cdot\|_V\) (见例 2.9), 则由 \(\mathbf{A x}=\lambda \mathbf{x}\), 可得 \[ |\lambda|\|\mathbf{x}\|_v=\|\lambda \mathbf{x}\|_v=\|\mathbf{A x}\|_v \leqslant\|\mathbf{A}\|\|\mathbf{x}\|_v \] 因为 \(\mathbf{x} \neq \mathbf{0}\), 所以 \[ |\lambda| \leqslant\|\mathbf{A}\| \] 对 \(\mathbf{A}\) 的任一特征值成立, 从而 \(\rho(\mathbf{A}) \leqslant\|\mathbf{A}\|\).
高斯变换
对任意下三角矩阵 \(L\) \[ \begin{aligned} L & =L_1\left(l_1\right) L_2\left(l_2\right) \cdots L_{n-1}\left(l_{n-1}\right) \\ & =\left[I+l_1 e_l^T\right)\left(I+l_2 e_2^T\right) \cdots\left(I+l_{n-1} l_{n-1}^T\right) \\ & =I+l_1 e^T+l_2 e_2^T+\cdots l_{n-1} e_{n-1}^T \\ & =I+\left[l_1, l_2, \cdots, l_{n-1}, 0\right] \end{aligned} \] 方阵做高斯变换之后顺序主子式不变，使用分块矩阵得到 \(\forall\ k,(LA)_{k,k}=L_{k,k}A_{k,k}+O\)，且 \(\det(L_{k,k})=1\)
LU 分解
高斯消元法 \(\mathcal{O}(n^3)\)，但做了 LU 分解 \(A=LU\Longrightarrow \begin{cases}Ly=b\\Ux=y\end{cases}\)，后者求解 \(\mathcal{O}(n^2)\)
LU 分解存在性和唯一性
设 \(A \in \mathbb{R}^{n \times n}\). 则存在唯一的单位下三角矩阵 \(L\) 和非奇异上三角矩阵 \(U\), 使得 \(A=L U\) 的充要条件是 \(A\) 的所有顺序主子矩阵 \(A_k=A(1: k, 1: k)\) 都非奇异, \(k=1,2, \ldots, n\). (板书)
- \(\Longrightarrow\) 假设存在分解 \(A=LU=L_1\cdots L_{n-1}U\)，则 \(U=L_{n-1}^{-1}\cdots L_{1}^{-1}A\)
由于 \(U\) 非奇异，其任意顺序主子矩阵非奇异，且高斯变换后不改变顺序主子式，则 \(A\) 也满足
\(\Longleftarrow\) 存在性：对 \(A\) 高斯消元得到 \(U=L_{n-1}^{-1}\cdots L_{1}^{-1}A\)，移项即可
唯一性：假设 \(A=L_1 U_1=L_2 U_2\Longrightarrow L_2^{-1}L_1=U_2U_1^{-1}\) 上三角等于下三角，则为单位阵，故 \(L_2=L_1, U_2=U_1\)
列主元 Gauss 消去法与 PLU 分解
\[ \left[\begin{array}{ccccc} a_{11}^{(1)} & \cdots & a_{1 k}^{(1)} & \cdots & a_{1 n}^{(1)} \\ & \ddots & \vdots & & \vdots \\ & & a_{k k}^{(k)} & \cdots & a_{k n}^{(k)} \\ & & \vdots & \ddots & \vdots \\ & & a_{n k}^{(k)} & \cdots & a_{n n}^{(k)} \end{array}\right] \]
选取绝对值最大的元素 \[ a_{i_k, k}=\max _{k \leq i \leq n}\left|a_{i, k}\right| \]
只要矩阵非奇异，则一定能找到非零元素，只需要记录所有的行变换，总计为 \(PA\)
列主元 LU 分解
若矩阵 \(A\) 非奇异，则存在置换矩阵 \(P\), 使得 \[ P A=L U \] 其中 \(L\) 为单位下三角矩阵, \(U\) 为上三角矩阵.
数学归纳法，\(n=1\) 显然成立，若 \(\forall\ n\leq N-1\) 均能 PLU 分解，考虑 \(n=N\)，将 \(A\) 写作 \[ A=\begin{pmatrix}a_{11} & \mathbf{a_{12}}^{T}\\\mathbf{a_{21}}& A_{22}\end{pmatrix} \] 不妨令 \(a_{11}\neq 0\)，否则可以通过置换使 \(a_{11}\neq 0\) \[ A=\begin{pmatrix}1 & \mathbf{0}^{T}\\\mathbf{a_{21}}& I_{n-1}\end{pmatrix}\cdot \begin{pmatrix}a_{11} & \mathbf{a_{12}}^{T}\\\mathbf{0}& A_{22}^{'}\end{pmatrix} \] 而 \(\det(A_{22}^{'})=\dfrac{\det(A)}{a_{11}}\neq 0\)，故能 PLU 分解，则 \[ \begin{aligned} A&=\begin{pmatrix}1 & \mathbf{0}\\\mathbf{a_{21}}& I_{n-1}\end{pmatrix}\cdot \begin{pmatrix}a_{11} & \mathbf{a_{12}}^{T}\\\mathbf{0}& P^{T}LU\end{pmatrix}\\ &=\begin{pmatrix}1 & \mathbf{0}\\\mathbf{a_{21}}& I_{n-1}\end{pmatrix}\cdot \begin{pmatrix}1 & \mathbf{0}^{T}\\\mathbf{0}& P^{T}L\end{pmatrix}\cdot \begin{pmatrix}a_{11} & \mathbf{a_{12}}^{T}\\\mathbf{0}& U\end{pmatrix}\\ &=\begin{pmatrix}1 & \mathbf{0}\\\mathbf{a_{21}}& P^{T}L\end{pmatrix}\cdot \begin{pmatrix}a_{11} & \mathbf{a_{12}}^{T}\\\mathbf{0}& U\end{pmatrix}\\ &=\begin{pmatrix}1 & \mathbf{0}\\\mathbf{0}& P^{T}\end{pmatrix}\cdot \begin{pmatrix}1 & \mathbf{0}\\\mathbf{a_{21}}& L\end{pmatrix}\cdot \begin{pmatrix}a_{11} & \mathbf{a_{12}}^{T}\\\mathbf{0}& U\end{pmatrix}\\ &=P^{'}L^{'}U^{''} \end{aligned} \] 由数学归纳法可知，该分解对 \(\forall\ n\) 成立
除法对分母敏感，列主元的稳定性大于 LU 分解性
求解方法 \(Ax=b\Longrightarrow \begin{cases}Ly=Pb\\Ux=y\end{cases}\)
全主元LU分解
选取右下角整个一块绝对值的最大值 \[ \left|a_{i_k, j_k}^{(k)}\right|=\max _{k \leq i, j \leq n}\left\{\left|a_{i, j}^{(k)}\right|\right\} \] 设矩阵 \(A\) 非奇异，则存在置换矩阵 \(P_l, P_r\)，以及单位下 三角矩阵 \(L\) 和非奇异上三角矩阵 \(U\)，使得 \[ P_l A P_r=L U \] 求解方法 \(Ax=b\Longrightarrow \begin{cases}Lz=P_{l}b\\Uy=z\\x=yP_{r}^{-1}\end{cases}\)
待定系数法（Doolittle 法）
依次比对第 \(j\) 行和第 \(j\) 列，得到相应的系数，\(j\) 从 1 到 n \[ \left[\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1 n} \\ a_{21} & a_{22} & \cdots & a_{2 n} \\ \vdots & & \ddots & \vdots \\ a_{n 1} & a_{n 2} & \cdots & a_{n n} \end{array}\right]=\left[\begin{array}{cccc} 1 & & & \\ l_{21} & 1 & & \\ \vdots & & \ddots & \\ l_{n 1} & \cdots & l_{n, n-1} & 1 \end{array}\right]\left[\begin{array}{cccc} u_{11} & u_{12} & \cdots & u_{1 n} \\ & u_{22} & & u_{2 n} \\ & & \ddots & \vdots \\ & & & u_{n n} \end{array}\right] \]
Cholesky 分解
若 \(A\) 对称正定，则 \(!\ \exists\ \) 对角线元素全为正的下三角矩阵 \(L\)，使得 \(A=LL^{T}\)
唯一性由 LU 分解可得，这里证明存在性，使用数学归纳法
显然 \(n=1\) 成立，假设 \(\forall\ n\geq N-1\) 时该分解成立，对 \(n=N\)，将 \(A\) 分解 \[ A=\begin{pmatrix}\sqrt{a_{11}} & \\\dfrac{\mathbf{a_{21}}}{\sqrt{a_{11}}}& I_{n-1}\end{pmatrix}\cdot \begin{pmatrix}1 & \\& A_{22}-\dfrac{\mathbf{a_{21}^{T}\mathbf{a_{21}}}}{a_{11}}\end{pmatrix}\cdot \begin{pmatrix}\sqrt{a_{11}} & \dfrac{\mathbf{a_{21}}^{T}}{\sqrt{a_{11}}}\\& I_{n-1}\end{pmatrix} \] 而 \(A_{22}^{'}=A_{22}-\dfrac{\mathbf{a_{21}^{T}\mathbf{a_{21}}}}{a_{11}}\) 对称正定，由归纳假设，其分解为 \(A_{22}=LL^{T}\) \[ \begin{aligned} A&=\begin{pmatrix}\sqrt{a_{11}} & \\\dfrac{\mathbf{a_{21}}}{\sqrt{a_{11}}}& I_{n-1}\end{pmatrix}\cdot \begin{pmatrix}1 & \\& A_{22}^{'}\end{pmatrix}\cdot \begin{pmatrix}\sqrt{a_{11}} & \dfrac{\mathbf{a_{21}}^{T}}{\sqrt{a_{11}}}\\& I_{n-1}\end{pmatrix}\\ \end{aligned} \]
由于 \(A\) 对称正定，则 \(A_{22}^{'}\) 也是对称正定，\(A=\tilde{L}\tilde{L}^{T}\)，取即可 \[ \mathbf{L}=\left[\begin{array}{ll} \sqrt{a_{11}} & \\ \frac{\mathbf{a}}{\sqrt{a_{11}}} & \tilde{\mathbf{L}} \end{array}\right] \] 利用对称性把复杂度减半，\(LDL^{T}\) 分解，避免在 Cholesky 分解计算平方根
特殊矩阵的 LU 分解
三对角线性方程 \[ \left[\begin{array}{cccc} b_1 & c_1 & & \\ a_1 & \ddots & \ddots & \\ & \ddots & \ddots & c_{n-1} \\ & & a_{n-1} & b_n \end{array}\right]\left[\begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array}\right]=\left[\begin{array}{c} f_1 \\ f_2 \\ \vdots \\ f_n \end{array}\right] \] 假设列对角占优，则分解为 \[ A=\left[\begin{array}{cccc} b_1 & c_1 & & \\ a_1 & \ddots & \ddots & \\ & \ddots & \ddots & c_{n-1} \\ & & a_{n-1} & b_n \end{array}\right]=\left[\begin{array}{cccc} 1 & & & \\ \gamma_1 & 1 & & \\ & \ddots & \ddots & \\ & & \gamma_{n-1} & 1 \end{array}\right]\left[\begin{array}{cccc} \alpha_1 & c_1 & & \\ & \alpha_2 & \ddots & \\ & & \ddots & c_{n-1} \\ & & & \alpha_n \end{array}\right] \] 行对角占优同理对称
扰动分析
判断矩阵是否病态的指标是矩阵条件数
设 \(A\) 非奇异，\(\|\cdot\|\) 是任一算子范数，定义 \(A\) 的条件数 \[ \kappa(A) :=\left\|A^{-1}\right\| \cdot\|A\| \] 对 \(\kappa_{2}(\cdot)\) 为谱条件数，当 \(A\) 对称时 \[ \kappa_2(A)=\frac{\max _{1 \leq i \leq n}\left|\lambda_i\right|}{\min _{1 \leq i \leq n}\left|\lambda_i\right|} \] 性质：
- \(\kappa(A) \geq 1, \quad \forall A \in \mathbb{R}^{n \times n}\).
- 对任意非零常数 \(\alpha \in \mathbb{R}\), 都有
\[ \kappa(\alpha A)=\kappa(A) . \]
- 对任意正交矩阵 \(Q \in \mathbb{R}^{n \times n}\), 有 \(\kappa_2(Q)=1\).
- 设 \(Q\) 是正交矩阵, 则对任意矩阵 \(A\) 有
\[ \kappa_2(Q A)=\kappa_2(A)=\kappa_2(A Q) . \]
定理，设 \(A\in \mathbb{R}^{n\times n}\) 且非奇异，则 \[ \min _{\mathbf{A}+\delta \mathbf{A} \text { 奇异 }}\left\{\frac{\|\delta \mathbf{A}\|_2}{\|\mathbf{A}\|_2}\right\}=\frac{1}{\operatorname{cond}(\mathbf{A})_2} \text {. } \] 考虑满足 \(||A^{-1}||_2\) 对应的向量 \(x\in \mathbb{R}^{n\times 1}\)，构造 \[ \begin{cases} y=\dfrac{A^{-1}x}{||A^{-1}||_2}\\ \delta A=-\dfrac{xy^{T}}{||A^{-1}||_2} \end{cases} \] 这样有 \((A+\delta A)y=0\)，使得 \(A+\delta A\) 奇异 \[ \begin{gathered} \mathbf{A x}=\mathbf{b} \\ (\mathbf{A}+\delta \mathbf{A})(\mathbf{x}+\delta \mathbf{x})=\mathbf{b}+\delta \mathbf{b} \end{gathered} \] 当 \(||\delta A||\) 足够小时，有 \[ \dfrac{||\delta x||}{||x||}\leq \dfrac{\kappa(A)}{1-\kappa(A)\dfrac{||\delta A||}{||A||}}\left(\dfrac{||\delta A||}{||A||}+\dfrac{||\delta b||}{||b||}\right) \] 证明：有不等式 \(\left\|\left(\mathbf{I}+\mathbf{A}^{-1} \delta \mathbf{A}\right)^{-1}\right\| \leqslant \dfrac{1}{1-\left\|\mathbf{A}^{-1} \delta \mathbf{A}\right\|} \leqslant \dfrac{1}{1-\left\|\mathbf{A}^{-1}\right\|\|\delta \mathbf{A}\|}\)
此时 \(x+\delta x=(\mathbf{A}+\delta \mathbf{A})^{-1}(b+\delta b)\)，计算 \[ \begin{aligned} \delta x&=(\mathbf{A}+\delta \mathbf{A})^{-1}(b+\delta b)-x\\ &\leq \dfrac{||\mathbf{A}^{-1}||}{1-\left\|\mathbf{A}^{-1}\right\|\|\delta \mathbf{A}\|}\cdot (b+\delta b-(\mathbf{A}+\delta \mathbf{A})x)\\ &=\dfrac{||\mathbf{A}^{-1}||}{1-\left\|\mathbf{A}^{-1}\right\|\|\delta \mathbf{A}\|}\cdot (\delta b-(\delta \mathbf{A})x)\\ &\leq \dfrac{||\mathbf{A}^{-1}||}{1-\left\|\mathbf{A}^{-1}\right\|\|\delta \mathbf{A}\|}\cdot (||\delta b|+||\delta \mathbf{A}||\ ||x|||)\\ &=\dfrac{||\mathbf{A}^{-1}||}{1-\left\|\mathbf{A}^{-1}\right\|\|\delta \mathbf{A}\|}\cdot ||\mathbf{A}||\ ||x|| \left(\dfrac{||\delta b|}{||\mathbf{A}||\ ||x||}+\dfrac{||\delta \mathbf{A}||}{||\mathbf{A}||}\right)\\ [\mathbf{A}x=b&\longrightarrow||b||=||\mathbf{A}x||\leq ||\mathbf{A}||\ ||x||]\\ &\leq \dfrac{||\mathbf{A}^{-1}||}{1-\left\|\mathbf{A}^{-1}\right\|\|\delta \mathbf{A}\|}\cdot ||\mathbf{A}||\ ||x|| \left(\dfrac{||\delta b|}{||b||}+\dfrac{||\delta \mathbf{A}||}{||\mathbf{A}||}\right)\\ \Longrightarrow \dfrac{\delta x}{||x||}&\leq \dfrac{\kappa(\mathbf{A})}{1-\kappa(\mathbf{A})\dfrac{||\delta \mathbf{A}||}{||\mathbf{A}||}}\left(\dfrac{||\delta \mathbf{A}||}{||\mathbf{A}||}+\dfrac{||\delta b||}{||b||}\right) \end{aligned} \] 当 \(A\) 固定时，\(\delta A=0\)，有 \(\dfrac{\|\delta \mathbf{x}\|}{\|\mathbf{x}\|} \leqslant\|\mathbf{A}\|\left\|\mathbf{A}^{-1}\right\| \dfrac{\|\delta \mathbf{b}\|}{\|\mathbf{b}\|}\)
迭代法概念
\(\forall\ ||\cdot||,\lim_{k\to \infty}||\mathbf{B}^{k}||^{\frac{1}{k}}=\rho(\mathbf{B})\)
\(\forall\ \epsilon >0,\mathbf{B}_{\epsilon}=\dfrac{\mathbf{B}}{\rho(\mathbf{B})+\epsilon}\) 其谱半径小于 \(1\)，则 \(||\mathbf{B}_{\epsilon}^{k}||<1\Longrightarrow ||\mathbf{B}^{k}||\leq (\rho(\mathbf{B})+\epsilon)^{k}\)，两边开 \(k\) 次方得到上界 \(LHS\leq \rho(\mathbf{B})+\epsilon\)，又 \(\rho(\mathbf{B})=\rho(\mathbf{B}^{k})^{\frac{1}{k}}\leq LHS\)。
矩阵的无穷次方趋于 \(0\) 的三个等价条件
\(\lim_{k\to \infty} \mathbf{B}^{k}=\mathbf{O]}\)
\(\rho(\mathbf{B})<1\)
\(\exists\ ||\cdot||,s.t.||\mathbf{B}||<1\)
1->2 \(\forall\ \mathbf{x}\neq \mathbf{0},\mathbf{B}^{k}\mathbf{x}=\lambda \mathbf{x}\) 同时取范数取极限得到 \(|\lambda|<1\Longrightarrow \rho(\mathbf{B})<1\)
2->3 由范数性质 \(\forall\ \epsilon >0, \exists\ ||\cdot||,s.t.||\mathbf{B}||<\rho(\mathbf{B})+\epsilon\)
3->1 由 \(||\mathbf{B}^{k}||\leq ||\mathbf{B}||^{k}\to 0\) 即可
定常迭代
一般地，对 \(Ax=b\)，取 \(A=M-N\) 其中 \(M\) 可逆 \[ (M-N)x=b,x=M^{-1}(Nx+b):=Bx+f \] 得到迭代方程 \[ x^{(k+1)}=Bx^{(k)}+f,where\begin{cases}B=M^{-1}N\\f=M^{-1}b\end{cases} \] 令 \(x^{*}\) 为正确解，定义 \(e^{(k)}:x^{(k)}-x^{*}\)，显然有 \[ \mathbf{e}^{(k)}=\mathbf{B}\left(\mathbf{x}^{(k-1)}-\mathbf{x}^*\right)=\mathbf{B} \mathbf{e}^{(k-1)} \] 故收敛的充要条件是 \(\rho(\mathbf{B})<1\)，收敛速度
设 \(x^*\) 是方程组 \(x=B x+f\) 的唯一解, \(\|\cdot\|\) 是一种向量范数, 从属它的矩阵范数 \(\|\mathbf{B}\|=q<1\), 则迭代法 \(\mathbf{x}^{(k+1)}=\mathbf{B} \mathbf{x}^{(k)}+\mathbf{f}\) 收敛且 \[ \begin{aligned} & \left\|\mathbf{x}^{(k)}-\mathbf{x}^*\right\| \leqslant \frac{q}{1-q}\left\|\mathbf{x}^{(k)}-\mathbf{x}^{(k-1)}\right\|, \\ & \left\|\mathbf{x}^{(k)}-\mathbf{x}^*\right\| \leqslant \frac{q^k}{1-q}\left\|\mathbf{x}^{(1)}-\mathbf{x}^{(0)}\right\| . \end{aligned} \]
考虑放缩 \[ \begin{aligned} \mathbf{x}^{(k)}-\mathbf{x}^* & =\mathbf{B}\left(\mathbf{x}^{(k-1)}-\mathbf{x}^*\right) \\ & =\mathbf{B}\left(\mathbf{x}^{(k-1)}-\mathbf{x}^{(k)}\right)+\mathbf{B}\left(\mathbf{x}^{(k)}-\mathbf{x}^*\right), \\ \left\|\mathbf{x}^{(k)}-\mathbf{x}^*\right\| & \leqslant\left\|\mathbf{B}\left(\mathbf{x}^{(k-1)}-\mathbf{x}^{(k)}\right)\right\|+\left\|\mathbf{B}\left(\mathbf{x}^{(k)}-\mathbf{x}^*\right)\right\| \\ & \leqslant q\left\|\mathbf{x}^{(k-1)}-\mathbf{x}^{(k)}\right\|+q\left\|\mathbf{x}^{(k)}-\mathbf{x}^*\right\| .\end{aligned} \]
定义 基于矩阵分裂的定常迭代法的平均收敛速度定义为 \[ R_k(B) \triangleq-\ln \left\|B^k\right\|^{\frac{1}{k}}, \] 渐进收敛速度定义为 \[ R(B) \triangleq \lim _{k \rightarrow \infty} R_k(B)=-\ln \rho(B) . \] 将 \(A=D-L-U\) 拆为三个部分
Jacobi 迭代法：取 \(M=D,N=L+U\) \[ x_i^{(k+1)}=\frac{1}{a_{i i}}\left(b_i-\sum_{j=1, j \neq i}^n a_{i j} x_j^{(k)}\right) \] Gauss-Seidel 迭代法：取 \(M=D-L,N=U\) \[ x_i^{(k+1)}=\frac{1}{a_{i i}}\left(b_i-\sum_{j=1}^{i-1} a_{i j} x_j^{(k+1)}-\sum_{j=i+1}^n a_{i j} x_j^{(k)}\right) \] 超松弛 迭代法：加权 \(x_i^{(k+1)}=\omega \bar{x}_i^{(k+1)}+(1-\omega) x_i^{(k)}\) 其中 \(\bar{x}_i^{(k+1)}\) 是 GS 迭代法
当 \(\omega=1\) 时为 GS 迭代
其等价拆分为 \[ \mathbf{M}=\frac{1}{\omega}(\mathbf{D}-\omega \mathbf{L}), \quad \mathbf{N}=\frac{1}{\omega}[(1-\omega) \mathbf{D}+\omega \mathbf{U}] \]
对角占优收敛性
定理：若 \(A\) 严格对角占优（或者不可约弱对角占优），则 J 迭代和 G-S 迭代法均收敛
J 迭代：收敛等价于 \(\rho(B)=\rho(D^{-1}(L+U))<1\) 令其特征值为 \(\lambda\) \[ D^{-1}(L+U)\vec{x}=\lambda\vec{x}\Longrightarrow \det(\lambda I-D^{-1}(L+U))=0 \] 由严格对角占优 \(D\) 的对角元全部非零，则 \(\det(D^{-1})\neq 0\) 提取有 \[ \det(\lambda D-(L+U))=0 \] 若 \(|\lambda| \geq 1\)，则 \(\lambda D-(L+U)\) 也是严格对角占优，矛盾，故 \(\rho(B)<1\)
GS 迭代：同理 \(\det(\lambda I-(D-L)^{-1}U)=0\Longrightarrow \det(\lambda (D-L)-U)=0\)
同理反证严格对角占优矛盾
不可约性也在上述矩阵推导中保持，因为 \(A\) 和 \(\lambda D-(L+U)\) 中零元素和非零元素的位置完全相同，同理由特殊矩阵行列式的非零性得证、
不动点迭代
若 \(\forall\ x\in[a,b],|\varphi(x)|\in [a,b],\exists\ L\in(0,1),|\varphi(x)-\varphi(y)|\leq L|x-y|, \forall\ x\in(a,b),|\varphi^{\prime}(x)|<1\)，不能保证 \(\varphi(x)\) 不动点迭代收敛
考虑 \(\varphi(x)=\sqrt{1-x^2},a=-\dfrac{\sqrt{2}}{2},b=+\dfrac{\sqrt{2}}{2}\)，满足上述条件，只有 \(x=a\) 处收敛，但取初始为无理数，在圆上会不断地跳动，永远不会达到该点，无法收敛
加速方法
Aitken 加速
假定相邻两次迭代之差的斜率相近 \[ \frac{x_{k+1}-x_*}{x_{k+2}-x_*} \approx \frac{x_k-x_*}{x_{k+1}-x_*}\Longrightarrow \overline{x_k}\approx x^{*} := x_k-\frac{\left(x_{k+1}-x_k\right)^2}{x_{k+2}-2 x_{k+1}+x_k} \]
Steffensen 加速
把与三个 \(x_i\) 相关的量集合并为一个函数，可以构造新的 \(\psi(x)\) \[ \psi(x)=x-\frac{(\varphi(x)-x)^2}{\varphi(\varphi(x))-2 \varphi(x)+x} \] 笔记就这些，学到后面主要以教材为主。。。
2017-2018 数值分析期末考试
据说是包老师第一次开《数值分析》课的期末考试试题，平均分 40 多分，包老师之后就吸取教训，考试变得简单。
1.已知 \(f(-1)=2, f(0)=0, f(1)=1\)，试求满足自然边界条件（边界二阶导为 0 ）的三次样条函数 \(f(x)=\_\_\_\_\_\_\)。
2.设 \(A=\left(\begin{array}{ll}1 & a \\ a & 5\end{array}\right)\)，则 \(\|A\|_2=\_\_\_\_\_\_\_\_\)，\(\text{cond}_{\infty}(A)=\_\_\_\_\_\_\)，若进行 Cholesky 分解 \(A=L L^T\)，则 \(L=\_\_\_\_\_\_\)，其中 \(a\) 必须满足 \(\_\_\_\_\_\_\)。
3.记切比雪夫多项式 \(T_3(x)=\cos (n \arccos (x))\)，则 \(\displaystyle\int_{-1}^1 \dfrac{T_3^2(x) d x}{\sqrt{1-x^2}}=\_\_\_\_\_\_\)。
4.给定数据 \(f(-2)=0.523, f(1)=4.141, f(2)=7.925, f^4(4)=31.014\)，则以线性最小二乘法确定的拟合函数 \(f(x)=a e^{b x}\) 当中，\(a=\_\_\_\_\_\_, b=\_\_\_\_\_\_\) 。(保留至少 3 位有效数字)
5.\(A\) 为对称正定矩阵，求证：对于方程组 \(A\mathbf{x}=\mathbf{b}\) 的 (G-S 迭代法)是收敛的。
6.设 \(a>0\)，试构造一个三阶收敛到 \(\sqrt[3]{a}\) 的迭代公式，要求只能使用四则运算。
7.设矩阵 \(A=\left(\begin{array}{ccc}6 & -0.1 & \\ -0.1 & 3 & 0.5 \\ & 0.5 & 0.2\end{array}\right)\)，试估计其特征值范围，并结合 Rayleigh 商，用逆幂迭代法计算出中间的特征真 (至少保留 3 位有效数字)，并证明该算法收敛。
8.已知函数 \(f(x)\) 在点 \(0,1,2\) 处的取值分别为 \(0,2,0\), 并且已知 \(f^{\prime}(1)=2\) 。假设三次插值多项式 \(P_3(x)\) 也满足如上条件。试求出 \(P_3(x)\)，并写出插值余项 \(R(x)=f(x)-P_3(x)\) 。(插值余项的形式写成类似 Taylor 公式的 Lagrange 余项的形式)
9.试构造加下形式的求积公式 \[ \int_0^1 f(x) d x \approx A_0 f(0)+A_1 f\left(x_1\right)+A_2 f\left(x_2\right)+A_3 f(1) \]
使得代数精度最高。
10.用线性单步法 \(\left.y_{n+1}=y_n+h\left[\alpha f\left(x_n, y_n\right)+\beta f\left(x_n+\gamma h, y_n+\theta h f\left(x_n, y_n\right)\right)\right]\right]\) 来求解初值问题 \[ \left\{\begin{array}{c} y^{\prime}(x)=f(x, y) \\ y\left(x_0\right)=y_0 \end{array}\right. \]
试给出一组参数 \(\alpha, \beta, \gamma, \theta\) 的值，使得方法至少具有 2 阶精度。(注: 答案不唯一)并且对于你给定的这一组参数，计算其绝对稳定区间。
参考答案
\(f(x)=\begin{cases}\dfrac{1}{4}(-3x^3+9x^2-2x)\quad x\in[0,1]\\\dfrac{1}{4}(3x^3+9x^2-2x)\quad x\in[-1,0]\end{cases}\)
\(\sqrt{a^2+4}+3,\dfrac{(5+|a|)^2}{5-a^2},\left(\begin{array}{l}1 \\ a & \sqrt{5-a^2}\end{array}\right),(-\sqrt{5},\sqrt{5})\)
\(\dfrac{\pi}{2}\)
\(2.05,0.680\)
教材 P85 定理 3.2 证明正定对称矩阵 SOR 迭代收敛的特殊情况 \(\omega=1\)
\(x_{k+1}=\dfrac{5}{9}x_k+\dfrac{5}{9}\dfrac{a}{x_{k}^2}-\dfrac{1}{9}\dfrac{a^2}{x_{k}^5}\)
\(-2 x^3+4 x^2,\dfrac{f^{(4)}(\xi(x))}{24}x(x-1)^2(x-2)\)
\(A_0 =\dfrac{1}{12},A_1 =\dfrac{5}{12},A_2 =\dfrac{5}{12},A_3 =\dfrac{1}{12},x_1 =\dfrac{1}{2}\pm\dfrac{\sqrt{5}}{10},x_2 =\dfrac{\sqrt{5}}{10}\mp\dfrac{1}{2}\)
\(\alpha=\beta=\dfrac{1}{2},\gamma=1,\theta=1,(-2,0)\) 改进的 Euler 方法（答案不唯一）
不得不感叹 gpt-4 的强大，上面这些题，结合 python 调用功能，几乎都能完全答对（当然有些直接暴力列方程调用
solve函数有点作弊），以至于我检查我是否算对可以直接拿 gpt-4 的结果当参考答案了。也就是说 gpt-4 做这套题能达到优秀水平，而且这题肯定不在训练数据里面，因为这套题的原始来源就是一张流传的图片，上面还有各种乱画的草稿，也没人转换为电子版本，然后这套题人类（专家？）实际平均分 40 分。。。