第五章 线性方程组的直接解法

5.1 预备知识

5.1.1 特征值与特征向量

• 矩阵 $\mathit{A}$$\bm A$.

  • 谱 $\sigma (\mathit{A})$$\sigma(\bm A)$ 即全体特征值.

  • 谱半径 $\rho (\mathit{A})={\displaystyle \underset{1\le i\le n}{max}\left|{\lambda }_i\right|}$$\rho(\bm A) = \d\max_{1 \le i \le n} \vqty{\lambda_i}$.

  • 特征多项式 $p(\lambda )=\det (\lambda \mathit{I}-\mathit{A})$$p(\lambda) = \det(\lambda \bm I - \bm A)$.

  • 特征方程 $p(\lambda )=(\lambda -{\lambda }_1)(\lambda -{\lambda }_2)\cdots (\lambda -{\lambda }_n)=0$$p(\lambda) = (\lambda - \lambda_1) (\lambda - \lambda_2) \cdots (\lambda - \lambda_n) = 0$.

  • $\det \left(\mathit{A}\right)={\lambda }_1{\lambda }_2\cdots {\lambda }_n$$\det(\bm A) = \ssto{\lambda}{n}{}$.

  • $\mathrm{tr}\left(\mathit{A}\right)={\displaystyle \sum _{i=1}^n{a}_{ii}={\displaystyle \sum _{i=1}^n{\lambda }_i}}$$\tr(\bm A) = \insum a_{ii} = \insum \lambda_i$.

• 特征值与特征向量的性质

  • ${\mathit{A}}^{\mathrm{T}}$$\bm A\trans$ 有相同的特征值 $\lambda$$\lambda$ 与特征向量 $\mathit{x}$$\bm x$.

  • 若 $\mathit{A}$$\bm A$ 非奇异，则 ${\mathit{A}}^{-1}$$\bm A\inv$ 的特征值为 ${\lambda }^{-1}$$\lambda\inv$，特征向量为 $\mathit{x}$$\bm x$.

  • 若 $\mathit{A}$$\bm A$ 非奇异，则 ${\mathit{A}}^{\ast }$$\bm A\adj$ 的特征值为 $\left|\mathit{A}\right|{\lambda }^{-1}$$\vqty{\bm A} \lambda\inv$，特征向量为 $\mathit{x}$$\bm x$.

  • 相似矩阵 $\mathit{B}={\mathit{S}}^{-1}\mathit{A}\mathit{S}$$\bm B = \bm S\inv \bm A \bm S$ 有相同的特征多项式.

  • 哈密顿-凯莱定理：$\lambda (\mathit{I}\pm \mathit{A})=1\pm \lambda (\mathit{A})$$\lambda(\bm I \pm \bm A) = 1 \pm \lambda(\bm A)$.

  • $\rho (\mathit{B}{)}^k=\rho (\mathit{B})$$\rho(\bm B)^k = \rho(\bm B)$

• ${\mathit{A}}^{\mathrm{T}}\mathit{A}$$\bm A\trans \bm A$ 和 $\mathit{A}{\mathit{A}}^{\mathrm{T}}$$\bm A \bm A\trans$.

  • 二者是对称矩阵.

  • 二者的特征值相等，且非负.

  • 二者的 $2-$$2-$范数相等.

5.1.2 常见的特殊矩阵

• 对角

  • 对角矩阵：$\mathrm{\forall }i\ne j:a_{ij}=0$$\forall i \ne j \colon a_{ij} = 0$.

  • 三对角矩阵：$\mathrm{\forall }|i-j|>1:a_{ij}=0$$\forall \vqty{i - j} > 1 \colon a_{ij} = 0$.

• 上三角

  • 上三角矩阵：$\mathrm{\forall }i>j:a_{ij}=0$$\forall i > j \colon a_{ij} = 0$.

  • 单位上三角矩阵：$(\mathrm{\forall }i>j:a_{ij}=0)\wedge (\mathrm{\forall }i:a_{ii}=1)$$( \forall i > j \colon a_{ij} = 0 ) \and (\forall i \colon a_{ii} = 1)$.

  • 严格上三角矩阵：$\mathrm{\forall }i>j-1:a_{ij}=0$$\forall i > j-1 \colon a_{ij} = 0$.

  • 上海森伯格阵：$\mathrm{\forall }i>j+1:a_{ij}=0$$\forall i > j + 1 \colon a_{ij} = 0$.

• 对称

  • 对称矩阵：${\mathit{A}}^{\mathrm{T}}=\mathit{A}$$\bm A\trans = \bm A$.

  • 埃尔米特矩阵：${\mathit{A}}^{\mathrm{H}}:=\bar{A}{}^{\mathrm{T}}=\mathit{A}$$\bm A\conj := \overline A{}\trans = \bm A$.

  • 对称正定矩阵：$({\mathit{A}}^{\mathrm{T}}=\mathit{A})\wedge (\mathrm{\forall }\mathbf{0}\ne \mathit{x}\in {\mathbb{R}}^n:(\mathit{A}\mathit{x},\mathit{x})={\mathit{x}}^{\mathrm{T}}\mathit{A}\mathit{x}>0)$$(\bm A\trans = \bm A) \and \pqty{\forall \bm 0 \ne \bm x \in \R^n \colon (\bm A \bm x, \bm x) = \bm x\trans \bm A \bm x > 0}$.

    • 性质 1：$\mathrm{\forall }i:{\lambda }_i>0$$\forall i \colon \lambda_i > 0$.

    • 性质 2：$\mathrm{\forall }i:a_{ii}>0$$\forall i \colon a_{ii} > 0$.

• 其他

  • 正交矩阵：${\mathit{A}}^{-1}={\mathit{A}}^{\mathrm{T}}$$\bm A\inv = \bm A\trans$.

  • 酉矩阵：${\mathit{A}}^{-1}={\mathit{A}}^{\mathrm{H}}$$\bm A\inv = \bm A\conj$.

  • 初等置换阵、置换阵.

5.1.3 矩阵的常用定理

• 定理 1：矩阵 $\mathit{A}\in {\mathbb{R}}^{n\times n}$$\bm A \in \R^{n \cp n}$ 非奇异的等价命题：

  • $\mathrm{\forall }\mathit{b}\in {\mathbb{R}}^n:\mathit{A}\mathit{x}=\mathit{b}$$\forall \bm b \in \R^n \colon \bm A \bm x = \bm b$ 有唯一解.

  • $\mathit{A}\mathit{x}=\mathbf{0}$$\bm A \bm x = \bm 0$ 有唯一解 $\mathit{x}=\mathbf{0}$$\bm x = \bm 0$.

  • $\det \left(\mathit{A}\right)\ne 0$$\det(\bm A) \ne 0$.

  • $\mathrm{\exists }{\mathit{A}}^{-1}:\mathit{A}{\mathit{A}}^{-1}=\mathit{E}$$\exist \bm A\inv \colon \bm A \bm A\inv = \bm E$.

  • $\mathrm{rank}(\mathit{A})=n$$\rank(\bm A) = n$.

• 定理 2：设 $\mathit{A}\in {\mathbb{R}}^{n\times n}$$\bm A \in \R^{n \cp n}$ 为对称正定矩阵，则

  • $\det \left(\mathit{A}\right)\ne 0$$\det(\bm A) \ne 0$，并且 ${\mathit{A}}^{-1}$$\bm A\inv$ 也是对称正定矩阵.

  • 顺序主子阵 $\begin{array}{c}\mathrm{\forall }k:{\mathit{A}}_k=\left(\begin{array}{ccc}{a}_{11}& \cdots & a_{1k}\\ ⋮& & ⋮\\ a_{k1}& \cdots & a_{kk}\end{array}\right)\end{array}$$\forall k \colon \bm A_k = \begin{pmatrix} a_{11} & \cdots & a_{1k} \\ \vdots & & \vdots \\ a_{k1} & \cdots & a_{kk} \end{pmatrix}$ 是对称矩阵.

  • $\mathit{A}$$\bm A$ 的特征值 $\mathrm{\forall }i:{\lambda }_i>0$$\forall i \colon \lambda_i > 0$，并且 $\mathrm{\forall }k:\det \left({\mathit{A}}_k\right)>0$$\forall k \colon \det(\bm A_k) > 0$.

• 定理 3：对称阵 $\mathit{A}\in {\mathbb{R}}^{n\times n}$$\bm A \in \R^{n \cp n}$ 正定的充分条件：

  • $\mathrm{\forall }i:{\lambda }_i>0$$\forall i \colon \lambda_i > 0$.

  • $\mathrm{\forall }k:\det \left({\mathit{A}}_k\right)>0$$\forall k \colon \det(\bm A_k) > 0$.

• 定理 4：若尔当标准型

  • 若尔当块：$\begin{array}{c}{\mathit{J}}_i={\left(\begin{array}{ccccc}{\lambda }_i& 1& & & \\ & {\lambda }_1& 1& & \\ & & \ddots & \ddots & \\ & & & {\lambda }_i& 1\\ & & & & {\lambda }_i\end{array}\right)}_{n_i\times n_i}\end{array}$$\bm J_i = \pmatrix{ \lambda_i & 1 &&& \\ & \lambda_1 & 1 && \\ && \ddots & \ddots & \\ &&& \lambda_i & 1 \\ &&&& \lambda_i }_{n_i \cp n_i}$.

  • 若尔当标准型：${\mathit{P}}^{-1}\mathit{A}\mathit{P}=\left(\begin{array}{}\begin{array}{}{\mathit{J}}_1({\lambda }_1)\end{array}\\ & \begin{array}{}{\mathit{J}}_2({\lambda }_2)\end{array}\\ & & \begin{array}{}\ddots \end{array}\\ & & & \begin{array}{}{\mathit{J}}_r({\lambda }_r)\end{array}\end{array}\right)$$\bm P\inv \bm A \bm P = \mqty(\dmat{ \bm J_1(\lambda_1), \bm J_2(\lambda_2), \ddots, \bm J_r(\lambda_r) })$.

  • 若 $\mathrm{\forall }i\ne j:{\lambda }_i\ne {\lambda }_j$$\forall i \ne j \colon \lambda_i \ne \lambda_j$，则 $\mathrm{\forall }i:{\mathit{J}}_i$$\forall i \colon \bm J_i$ 均为一阶，于是标准型变为对角矩阵.

5.2 高斯消去法

5.2.1 高斯消去法

定理 5 设 $\mathit{A}\mathit{x}=\mathit{b}$$\bm A \bm x = \bm b$，其中 $\mathit{A}\in {\mathbb{R}}^{n\times n}$$\bm A \in \R^{n \cp n}$，

1. 若 $\mathrm{\forall }k:a_{kk}^{(k)}\ne 0$$\forall k \colon a_{kk}^{(k)} \ne 0$，则可如下计算：

   1. 消元计算：$\mathit{A}\mathit{x}=\mathit{b}$$\bm A \bm x = \bm b$ 化为 ${\mathit{L}}^{-1}\mathit{A}\mathit{x}\equiv \mathit{U}\mathit{x}={\mathit{L}}^{-1}\mathit{b}$$\bm L\inv \bm A \bm x \equiv \bm U \bm x = \bm L\inv \bm b$.

      $$\{\begin{array}{ll}{m}_{ik}=a_{ik}^{(k)}/a_{kk}^{(k)},& i=k+1,\cdots ,n,\\ a_{ij}^{(k+1)}=a_{ij}^{(k)}-m_{ik}{a}_{kj}^{(k)},& i,j=k+1,\cdots ,n,\\ b_i^{(k+1)}=b_i^{(k)}-m_{ik}{b}_k^{(k)},& i=k+1,\cdots ,n.\end{array}$$

   2. 回代计算：求解 $\mathit{U}\mathit{x}={\mathit{L}}^{-1}\mathit{b}$$\bm U\bm x = \bm L\inv \bm b$.

      $$\{\begin{array}{l}{x}_n=b^{(n)}/a_{nn}^{(n)},\\ x_k=(b_k^{(k)}-{\displaystyle \sum _{j=k+1}^n{a}_{kj}^{(k)}{x}_j})/a_{kk}^{(k)},& k=n-1,n-2,\cdots ,1.\end{array}$$

2. 若 $\mathit{A}$$\bm A$ 为非奇异矩阵，则可通过高斯消去法和行交换将方程组约化为 $\mathit{U}\mathit{x}={\mathit{L}}^{-1}\mathit{b}$$\bm U \bm x = \bm L\inv \bm b$.

备注 加减和乘除的次数均为 $\mathcal{O}(n^3)$$\cal O(n^3)$.

定理 6 约化的主元素非零的充要条件是 $\mathit{A}$$\bm A$ 的顺序主子式 $\mathrm{\forall }k:D_k\ne 0$$\forall k \colon D_k \ne 0$，即

推论 若 $\mathit{A}$$\bm A$ 的顺序主子式 $\mathrm{\forall }k:D_k\ne 0$$\forall k \colon D_k \ne 0$，则

5.2.2 矩阵的三角分解

定理 7（LU 分解） 若 $\mathit{A}\in {\mathbb{R}}^{n\times n}$$\bm A \in \R^{n \cp n}$ 且 $\mathrm{\forall }i:D_i\ne 0$$\forall i \colon D_i \ne 0$，则可唯一分解为单位下三角矩阵和上三角矩阵的乘积，即 $\mathit{A}=\mathit{L}\mathit{U}$$\bm A = \bm L \bm U$.

备注 有三种分解方式：

1. Doolittle 分解

   $$\begin{array}{c}\mathit{A}=\mathit{L}\mathit{U}=\left[\begin{array}{cccc}1& & & \\ l_{21}& 1& & \\ ⋮& ⋮& \ddots & \\ l_{n1}& l_{n2}& \cdots & 1\end{array}\right]\left[\begin{array}{cccc}{u}_{11}& u_{12}& \cdots & u_{1n}\\ & u_{22}& \cdots & u_{2n}\\ & & \ddots & ⋮\\ & & & u_{nn}\end{array}\right].\end{array}$$

2. Crout 分解

   $$\begin{array}{c}\mathit{A}=\mathit{L}\mathit{U}=\left[\begin{array}{cccc}{l}_{11}& & & \\ l_{21}& l_{22}& & \\ ⋮& ⋮& \ddots & \\ l_{n1}& l_{n2}& \cdots & l_{nn}\end{array}\right]\left[\begin{array}{cccc}1& u_{12}& \cdots & u_{1n}\\ & 1& \cdots & u_{2n}\\ & & \ddots & ⋮\\ & & & 1\end{array}\right].\end{array}$$

3. LDU 分解

   $$\begin{array}{c}\mathit{A}=\mathit{L}\mathit{D}\mathit{U}=\left[\begin{array}{cccc}1& & & \\ l_{21}& 1& & \\ ⋮& ⋮& \ddots & \\ l_{n1}& l_{n2}& \cdots & 1\end{array}\right]\left[\begin{array}{}\begin{array}{}{d}_1\end{array}\\ & \begin{array}{}{d}_2\end{array}\\ & & \begin{array}{}\ddots \end{array}\\ & & & \begin{array}{}{d}_n\end{array}\end{array}\right]\left[\begin{array}{cccc}1& u_{12}& \cdots & u_{1n}\\ & 1& \cdots & u_{2n}\\ & & \ddots & ⋮\\ & & & 1\end{array}\right].\end{array}$$

算法 1（列主元消去法）

定理 8（列主元的 LU 分解） 若 $\mathit{A}$$\bm A$ 非奇异，则存在排列矩阵 $\mathit{P}$$\bm P$ 使得 $\mathit{P}\mathit{A}=\mathit{L}\mathit{U}$$\bm P \bm A = \bm L \bm U$.

5.2.3 三角矩阵的求解

1. $\mathit{U}\mathit{x}=\mathit{d}$$\bm U \bm x = \bm d$ 和 $\mathit{L}\mathit{x}=\mathit{d}$$\bm L \bm x = \bm d$.

   1. 上三角矩阵：依次计算 $i=n,n-1,\cdots ,1$$i = n, n-1, \cdots, 1$.

      $$x_i=(d_i-{\displaystyle \sum _{j=i+1}^n{u}_{ij}{x}_j})/u_{ii}.$$

   2. 下三角矩阵：依次计算 $i=1,2,\cdots ,n$$i = \oneton$.

      $$x_i=(d_i-{\displaystyle \sum _{j=1}^{i-1}{u}_{ij}{x}_j})/u_{ii}.$$

2. 乘除法次数

   1. 乘法次数：$0+1+2+\cdots +(n-1)={\displaystyle \frac{n(n-1)}{2}}$$0 + 1 + 2 + \cdots + (n-1) = \dfrac{n(n-1)}{2}$，$O(n^2)$$O(n^2)$.

   2. 除法次数：$n$$n$.

   3. 加减次数：${\displaystyle \frac{n(n+1)}{2}}$$\dfrac{n(n+1)}{2}$，$O(n^2)$$O(n^2)$.

3. 逆矩阵求解公式：设 $\mathit{A}={\mathit{U}}^{-1}$$\bm A = \bm U\inv$，则 $\mathit{A}$$\bm A$ 亦为上三角矩阵.

   $$\{\begin{array}{ll}{a}_{ii}={\displaystyle \frac{1}{u_{ii}}},& i=1,2,\cdots ,n,\\ a_{ij}=-{\displaystyle \sum _{k=i+1}^j{\displaystyle \frac{u_{ik}{s}_{kj}}{u_{ii}}},}& \begin{array}{c}j=i+1,i+2,\cdots ,n,\\ i=n-1,n-2,\cdots ,1.\end{array}\end{array}$$

5.3 矩阵三角分解法

5.3.1 直接三角分解

• 思路

  • 将 $\mathit{A}$$\bm A$ 分解为 $\mathit{A}=\mathit{L}\mathit{U}$$\bm A = \bm L \bm U$.（每次计算左上角的一圈）

  • 将 $\mathit{A}\mathit{x}=\mathit{b}$$\bm A \bm x = \bm b$ 分解为 $\{\begin{array}{l}\mathit{L}\mathit{y}=\mathit{b},\\ \mathit{U}\mathit{x}=\mathit{y}.\end{array}$$\begin{cases} \bm L \bm y = \bm b, \\ \bm U \bm x = \bm y. \end{cases}$

  • 先求出 $\mathit{y}$$\bm y$，再求出 $\mathit{x}$$\bm x$，时间复杂度 $\mathcal{O}(n^3)$$\cal O(n^3)$.

• 算法 1：不选主元的三角分解

  • 单位下三角：杜利特尔（Doolittle）分解

    $$\{\begin{array}{ll}{u}_{1j}=a_{1j},& j=1,2,\cdots ,n,\\ l_{i1}=a_{i1}/u_{11},& i=2,3,\cdots ,n.\end{array}$$
    $$\{\begin{array}{lll}{u}_{ij}& =a_{ij}-{\displaystyle \sum _{k=1}^{i-1}{l}_{ik}{u}_{kj},}& j=i,i+1,\cdots ,n,\\ l_{ij}& =(a_{ij}-{\displaystyle \sum _{k=1}^{j-1}{l}_{ik}{u}_{kj}})/u_{jj},& i=j+1,\cdots ,n,j\ne n.\end{array}$$

  • 单位上三角：克劳特（Crout）分解

    $$\{\begin{array}{ll}{l}_{i1}=a_{i1},& i=1,2,\cdots ,n,\\ u_{1j}=a_{1j}/l_{11},& i=2,3,\cdots ,n.\end{array}$$
    $$\{\begin{array}{ll}{l}_{ij}=a_{ij}-{\displaystyle \sum _{k=1}^{j-1}{l}_{ik}{u}_{kj},}& i=j,j+1,\cdots ,n,\\ u_{ij}=(a_{ij}-{\displaystyle \sum _{k=1}^{i-1}{l}_{ik}{u}_{kj}})/l_{ii},& j=i+1,i+2,\cdots ,n,i\ne n.\end{array}$$

• 算法 2：选主元的三角分解法

  • 单位下三角：由于 $u_{ii}$$u_{ii}$ 会作为分母，应使之尽可能大.

  • 单位上三角

• 算法 2‘：求逆矩阵，$\mathcal{O}(n^3)$$\cal O(n^3)$.

  1. 分解为 $\mathit{P}\mathit{A}=\mathit{L}\mathit{U}$$\bm P\bm A = \bm L \bm U$.

  2. 计算 ${\mathit{U}}^{-1}$$\bm U\inv$.

  3. 计算 ${\mathit{U}}^{-1}{\mathit{L}}^{-1}$$\bm U\inv \bm L\inv$

  4. 计算 ${\mathit{A}}^{-1}={\mathit{U}}^{-1}{\mathit{L}}^{-1}\mathit{P}$$\bm A\inv = \bm U\inv \bm L\inv \bm P$.

5.3.2 平方根法

定理 9 若 $n$$n$ 阶对称矩阵 $\mathit{A}$$\bm A$ 所有顺序主子式非零，则可唯一分解为 $\mathit{A}=\mathit{L}\mathit{D}{\mathit{L}}^{\mathrm{T}}$$\bm A = \bm L \bm D \bm L\trans$.

定理 10 $n$$n$ 阶对称正定矩阵 $\mathit{A}$$\bm A$ 可唯一分解为 $\mathit{A}=\mathit{L}{\mathit{L}}^{\mathrm{T}}$$\bm A = \bm L \bm L\trans$（限定 $\mathit{L}$$\bm L$ 对角元素为正），称为楚列斯基（Cholesky）分解.

平方根法 利用楚列斯基分解求解对称正定方程组 $\mathit{A}\mathit{x}=\mathit{b}$$\bm A \bm x = \bm b$.

1. 求解 $\mathit{A}=\mathit{L}{\mathit{L}}^{\mathrm{T}}$$\bm A = \bm L \bm L\trans$.

   $$\{\begin{array}{ll}{l}_{ii}=\sqrt{a_{ii}-{\displaystyle \sum _{k=1}^{j-1}{l}_{ik}^2}},& i=1,2,\cdots ,n,\\ l_{ij}=(a_{ij}-{\displaystyle \sum _{k=1}^{j-1}{l}_{ik}{l}_{kj}})/l_{jj},& i>j.\end{array}$$

2. 求解 $\mathit{L}\mathit{y}=\mathit{b}$$\bm L \bm y = \bm b$.

3. 求解 ${\mathit{L}}^{\mathrm{T}}\mathit{x}=\mathit{y}$$\bm L\trans \bm x = \bm y$.

改进的平方根法 为避免开方，分解为 $\mathit{A}=\mathit{L}\mathit{D}{\mathit{L}}^{\mathrm{T}}$$\bm A = \bm L \bm D \bm L\trans$.

5.3.3 追赶法

问题 $\mathit{A}\mathit{x}=\mathit{f}$$\bm A \bm x = \bm f$，其中

并且

1. $\left|b_1\right|>\left|c_1\right|>0$$\vqty{b_1} > \vqty{c_1} > 0$.

2. $\left|b_i\right|\ge \left|a_i\right|+\left|c_i\right|,a_i,c_i\ne 0,i=2,3,\cdots ,n-1$$\vqty{b_i} \ge \vqty{a_i} + \vqty{c_i}, a_i, c_i \ne 0, i = 2, 3, \cdots, n-1$.

3. $\left|b_n\right|>\left|a_n\right|>0$$\vqty{b_n} > \vqty{a_n} > 0$.

分析 如下分解

于是

归纳可证，对于 $\mathrm{\forall }i$$\forall i$，有 $\left|{\alpha }_i\right|>\left|c_i\right|>0$$\vqty{\alpha_i} > \vqty{c_i} > 0$ 和 $0<\left|{\beta }_i\right|<1$$0 < \vqty{\beta_i} < 1$，于是

算法

1. 求解 ${\beta }_i$$\beta_i$.

   $$\{\begin{array}{l}{\beta }_1={\displaystyle \frac{c_1}{b_1}},\\ {\beta }_i={\displaystyle \frac{c_i}{b_i-a_i{\beta }_{i-1}}},& i=2,3,\cdots ,n-1.\end{array}$$

2. 求解 $\mathit{L}\mathit{y}=\mathit{f}$$\bm L \bm y = \bm f$.

   $$\{\begin{array}{l}{y}_1={\displaystyle \frac{f_1}{b_1}},\\ y_i={\displaystyle \frac{f_i-a_i{y}_{i-1}}{b_i-a_i{\beta }_{i-1}}},& i=2,3,\cdots ,n.\end{array}$$

3. 求解 $\mathit{U}\mathit{x}=\mathit{y}$$\bm U \bm x = \bm y$.

   $$\{\begin{array}{l}{x}_n=y_n,\\ x_i=y_i-{\beta }_i{x}_{i+1},& i=n-1,n-2,\cdots ,1.\end{array}$$

5.4 向量和矩阵的范数

5.4.1 向量范数

• 列向量 $\mathit{x},\mathit{y}$$\bm x, \bm y$ 的数量积

  • 若为实数：$(\mathit{x},\mathit{y})={\mathit{y}}^{\mathrm{T}}\mathit{x}={\displaystyle \sum _{i=1}^n{x}_i{y}_i}$$(\bm x, \bm y) = \bm y\trans \bm x = \insum x_i y_i$.

  • 若为复数：$(\mathit{x},\mathit{y})={\mathit{y}}^{\mathrm{H}}\mathit{x}={\displaystyle \sum _{i=1}^n{x}_i\overline{y_i}}$$(\bm x, \bm y) = \bm y\conj \bm x = \insum x_i \overline{y_i}$.

• 数量积的性质（$\mathit{x},\mathit{y}\in {\mathbb{C}}^n,\alpha \in \mathbb{C}$$\bm x, \bm y \in \C^n, \alpha \in \C$）

  • $(\mathit{x},\mathit{x})\ge 0$$(\bm x, \bm x) \ge 0$，当且仅当 $\mathit{x}=\mathbf{0}$$\bm x = \bm 0$ 取等.

  • $(\alpha \mathit{x},\mathit{y})=\alpha (\mathit{x},\mathit{y})$$(\alpha \bm x, \bm y) = \alpha (\bm x, \bm y)$.

  • $(\mathit{x},\alpha \mathit{y})=\bar{\alpha }(\mathit{x},\mathit{y})$$(\bm x, \alpha \bm y) = \overline\alpha (\bm x, \bm y)$.

  • $(\mathit{x},\mathit{y})=\overline{(\mathit{y},\mathit{x})}$$(\bm x, \bm y) = \overline{(\bm y, \bm x)}$.

  • $({\mathit{x}}_1+{\mathit{x}}_2,\mathit{y})=({\mathit{x}}_1,\mathit{y})+({\mathit{x}}_2,\mathit{y})$$(\bm x_1 + \bm x_2, \bm y) = (\bm x_1, \bm y) + (\bm x_2, \bm y)$.

  • 柯西·施瓦茨不等式：$|(\mathit{x},\mathit{y})|\le \Vert \mathit{x}{\Vert }_2\Vert \mathit{y}{\Vert }_2$$\vqty{(\bm x, \bm y)} \le \norm\big{\bm x}_2 \norm\big{\bm y}_2$.

• 向量的范数

  • 定义 1（非负性）$\Vert \mathit{x}\Vert \ge 0$$\norm\big{\bm x} \ge 0$ 当且仅当 $\mathit{x}=\mathbf{0}$$\bm x = \bm 0$ 时取等.

  • 定义 2（齐次性）$\mathrm{\forall }\alpha \in \mathbb{C}:\Vert \alpha \mathit{x}\Vert =\left|\alpha \right|\cdot \Vert \mathit{x}\Vert$$\forall \alpha \in \C \colon \norm\big{\alpha \bm x} = \vqty{\alpha} \cdot \norm\big{\bm x}$.

  • 定义 3（三角不等式）$\Vert {\mathit{x}}_1+{\mathit{x}}_2\Vert \le \Vert {\mathit{x}}_1\Vert +\Vert {\mathit{x}}_2\Vert$$\norm \big{\bm x_1 + \bm x_2} \le \norm\big{\bm x_1} + \norm\big{\bm x_2}$.

  • 性质：$|\Vert \mathit{x}\Vert -\Vert \mathit{y}\Vert |\le \Vert \mathit{x}-\mathit{y}\Vert$$\vqty{\Norm{\bm x} - \Norm{\bm y}} \le \Norm{\bm x - \bm y}$.

• 常用的范数

  • $p-$$p-$范数：$\Vert \mathit{x}{\Vert }_p={\left({\displaystyle \sum _{i=1}^n{\left|x_i\right|}^p}\right)}^{\frac{1}{p}},p\ge 1$$\norm\big{\bm x}_p = \pqty{\insum \vqty{x_i}^p}^\tfrac{1}{p}, p \ge 1$.

  • $1-$$1-$范数：$\Vert \mathit{x}{\Vert }_1={\displaystyle \sum _{i=1}^n\left|x_i\right|}$$\norm\big{\bm x}_1 = \insum \vqty{x_i}$.

  • $2-$$2-$范数：$\Vert \mathit{x}{\Vert }_2=\sqrt{(\mathit{x},\mathit{x})}$$\norm\big{\bm x}_2 = \sqrt{(\bm x, \bm x)}$.（欧氏范数）

  • $\mathrm{\infty }-$$\infty-$范数：$\Vert \mathit{x}{\Vert }_{\mathrm{\infty }}={\displaystyle \underset{1\le i\le n}{max}\left|x_i\right|}$$\norm\big{\bm x}_\infty = \d\max_{1 \le i \le n} \vqty{x_i}$.（最大范数）

  • 加权范数：$\Vert \mathit{x}{\Vert }_{\mathit{W}}=\Vert \mathit{W}\mathit{x}\Vert ,\mathit{W}\in {\mathbb{R}}^{n\times n}$$\norm\big{\bm x}_\bm W = \norm\big{\bm W \bm x}, \bm W \in \R^{n \cp n}$.

• 收敛

  • 依绝对值收敛

  • 依范数收敛

  • 依概率收敛

• 向量范数的性质

  • $N(\mathit{x})=\Vert \mathit{x}\Vert$$N(\bm x) = \Norm{\bm x}$ 是 $\mathit{x}$$\bm x$ 的连续函数.

  • 向量范数的等价性：$\mathrm{\forall }\Vert \cdot {\Vert }_s,\Vert \cdot {\Vert }_t,\mathrm{\exists }{c}_1,c_2>0,\mathrm{\forall }\mathit{x}\in {\mathbb{R}}^n:$$\forall \Norm{\cdot}_s, \Norm{\cdot}_t, \exist c_1, c_2 > 0, \forall \bm x \in \R^n \colon$

    $$c_1\Vert \mathit{x}{\Vert }_s\le \Vert \mathit{x}{\Vert }_t\le c_2\Vert \mathit{x}{\Vert }_s.$$

  • 向量收敛等价条件：$\underset{n\to \mathrm{\infty }}{lim}{\mathit{x}}^{(n)}=\mathit{x}\iff \underset{n\to \mathrm{\infty }}{lim}\Vert {\mathit{x}}^{(k)}-\mathit{x}\Vert =\mathbf{0}$$\nlim \bm x^{(n)} = \bm x \RLA \nlim \Norm{\bm x^{(k)} - \bm x} = \bm 0$.

5.4.2 矩阵范数

• $\mathrm{F}-$$\rm F-$范数（Frobenius 范数）

  • $F(\mathit{A})\equiv \Vert \mathit{A}{\Vert }_{\mathrm{F}}:={\left({\displaystyle \sum _{i,j}{a}_{ij}^2}\right)}^{\frac{1}{2}}$$F(\bm A) \equiv \Norm{\bm A}_\rm F := \pqty{\dsum_{i, j} a_{ij}^2}^{\tfrac{1}{2}}$.

  • $\Vert \mathit{A}{\Vert }_{\mathrm{F}}=\sqrt{\mathrm{tr}\left({\mathit{A}}^{\mathrm{T}}\mathit{A}\right)}=\sqrt{{\displaystyle \sum _{i=1}^n{\lambda }_i}}$$\Norm{\bm A}_\rm F = \sqrt{\tr(\bm A\trans \bm A)} = \sqrt{\insum \lambda_i}$.

• 方阵的范数（模）

  • 正定条件：$\Vert \mathit{A}\Vert \ge 0$$\Norm{\bm A} \ge 0$ 当且仅当 $\mathit{A}=\mathbf{0}$$\bm A = \bm 0$ 时取等.

  • 齐次条件：$\mathrm{\forall }c\in \mathbb{R}:\Vert c\mathit{A}\Vert =\left|c\right|\cdot \Vert \mathit{A}\Vert$$\forall c \in \R \colon \Norm{c \bm A} = \vqty{c} \cdot \Norm{\bm A}$.

  • 三角不等式：$\Vert \mathit{A}+\mathit{B}\Vert \le \Vert \mathit{A}\Vert +\Vert \mathit{B}\Vert$$\Norm{\bm A + \bm B} \le \Norm{\bm A} + \Norm{\bm B}$.

  • 矩阵相容性：$\Vert \mathit{A}\mathit{B}\Vert \le \Vert \mathit{A}\Vert \cdot \Vert \mathit{B}\Vert$$\Norm{\bm A \bm B} \le \Norm{\bm A} \cdot \Norm{\bm B}$.

• 相容性：$\mathrm{\forall }x\in {\mathbb{R}}^n,\mathrm{\forall }\mathit{A}\in {\mathbb{R}}^{n\times n}:\Vert \mathit{A}\mathit{x}\Vert \le \Vert \mathit{A}\Vert \cdot \Vert \mathit{x}\Vert$$\forall x \in \R^n, \forall \bm A \in \R^{n \cp n} \colon \Norm{\bm A \bm x} \le \Norm{\bm A} \cdot \Norm{\bm x}$.

• 方阵的算子范数（从属范数）

  • 对于向量范数 $\Vert \mathit{x}{\Vert }_v$$\Norm{\bm x}_v$，

  • 定义算子范数 $\Vert \mathit{A}{\Vert }_v={\displaystyle \underset{\mathit{x}\ne \mathbf{0}}{max}{\displaystyle \frac{\Vert \mathit{A}\mathit{x}{\Vert }_v}{\Vert \mathit{x}{\Vert }_v}}}$$\Norm{\bm A}_v = \d\max_{\bm x \ne \bm 0} \dfrac{\Norm{\bm A \bm x}_v}{\Norm{\bm x}_v}$.

  • 于是算子范数是范数，且满足相容性.

• 常用的算子范数

  注：以下是定理，而非定义.

  另外，我不喜欢 “列范数” 和 “行范数” 这两个名字.

  • $1-$$1-$范数即对第 1 维求和（即每一行相加，或同一列中所有元素相加）后寻找最大值.

  • $\mathrm{\infty }-$$\infty-$范数即对第 2 维求和（即每一列相加，或同一行中所有元素相加）后寻找最大值.

  • $1-$$1-$范数（列范数）$\Vert \mathit{A}{\Vert }_1={\displaystyle \underset{1\le j\le n}{max}{\displaystyle \sum _{i=1}^n\left|a_{ij}\right|}}$$\Norm{\bm A}_1 = \d\max_{1 \le j \le n} \insum \vqty{a_{ij}}$.

  • $2-$$2-$范数（谱范数）$\Vert \mathit{A}{\Vert }_2=\sqrt{{\lambda }_{max}({\mathit{A}}^{\mathrm{T}}\mathit{A})}$$\Norm{\bm A}_2 = \sqrt{\lambda_\max(\bm A\trans \bm A)}$.

  • $\mathrm{\infty }-$$\infty-$范数（行范数）$\Vert \mathit{A}{\Vert }_{\mathrm{\infty }}={\displaystyle \underset{1\le i\le n}{max}{\displaystyle \sum _{j=1}^n\left|a_{ij}\right|}}$$\Norm{\bm A}_\infty = \d\max_{1 \le i \le n} \dsum_{j=1}^n \vqty{a_{ij}}$.

• 正交

  • 正交矩阵：${\mathit{Q}}^{\mathrm{T}}\mathit{Q}=\mathit{E}$$\bm Q\trans \bm Q = \bm E$.

  • 正交变换：$\mathit{y}=\mathit{Q}\mathit{x}$$\bm y = \bm Q \bm x$

    • 条件一：$\Vert \mathit{y}\Vert =\Vert \mathit{x}\Vert$$\Norm{\bm y} = \Norm{\bm x}$.

    • 条件二：夹角不变.

  • 谱范数和 F 范数在正交变换下保持不变.

    • $\Vert \mathit{Q}\mathit{A}{\Vert }_F=\Vert \mathit{A}\mathit{Q}{\Vert }_F=\Vert \mathit{A}{\Vert }_F$$\Norm{\bm Q \bm A}_F = \Norm{\bm A \bm Q}_F = \Norm{\bm A}_F$.

    • $\Vert \mathit{Q}\mathit{A}{\Vert }_2=\Vert \mathit{A}\mathit{Q}{\Vert }_2=\Vert \mathit{A}{\Vert }_2$$\Norm{\bm Q \bm A}_2 = \Norm{\bm A \bm Q}_2 = \Norm{\bm A}_2$.

• 矩阵范数的定理

  • 对于 $\mathrm{\forall }\mathit{A}\in {\mathbb{R}}^{n\times n}$$\forall \bm A \in \R^{n \cp n}$，谱半径是范数的下确界.

    • $\mathrm{\forall }\Vert \cdot \Vert :\rho (\mathit{A})\equiv {\displaystyle \underset{1\le i\le n}{max}\left|{\lambda }_i\right|\le \Vert \mathit{A}\Vert }$$\forall \Norm{\cdot} \colon \rho(\bm A) \equiv \d\max_{1 \le i \le n} \vqty{\lambda_i} \le \Norm{\bm A}$.

    • $\mathrm{\forall }\epsilon >0,\mathrm{\exists }\Vert \cdot {\Vert }_{\epsilon }:\Vert \mathit{A}{\Vert }_{\epsilon }\le \rho (\mathit{A})+\epsilon$$\forall \ve > 0, \exist \Norm{\cdot}_\ve \colon \Norm{\bm A}_\ve \le \rho(\bm A) + \ve$.

    • 对于对称阵：$\Vert \mathit{A}{\Vert }_2=\rho (\mathit{A})$$% \forall (\bm A = \bm A\trans) \colon \Norm{\bm A}_2 = \rho(\bm A)$.

  • 矩阵序列的敛散性.

  • 若 $\Vert \mathit{B}\Vert <1$$\Norm{\bm B} < 1$，则 $\mathit{I}\pm \mathit{B}$$\bm I \pm \bm B$ 可逆，且 $\Vert {(\mathit{I}\pm \mathit{B})}^{-1}\Vert \le {\displaystyle \frac{1}{1-\Vert \mathit{B}\Vert }}$$\Norm{\pqty{\bm I \pm \bm B}\inv} \le \dfrac{1}{1 - \Norm{\bm B}}$.

5.4.3 范数杂项

不那么重要（但同样有趣）的例子与性质.

• 范数的大小关系

  • $\Vert \mathit{x}{\Vert }_{\mathrm{\infty }}\le \Vert \mathit{x}{\Vert }_1\le n\Vert \mathit{x}{\Vert }_{\mathrm{\infty }}$$\Norm{\bm x}_\infty \le \Norm{\bm x}_1 \le n \Norm{\bm x}_\infty$.

  • ${\displaystyle \frac{1}{\sqrt{n}}}\Vert \mathit{A}{\Vert }_{\mathrm{F}}\le \Vert \mathit{A}{\Vert }_2\le \Vert \mathit{A}{\Vert }_{\mathrm{F}}$$\dfrac{1}{\sqrt n} \Norm{\bm A}_\rm F \le \Norm{\bm A}_2 \le \Norm{\bm A}_\rm F$.

• 其他的向量范数

  • 若 $\mathit{P}\in {\mathbb{R}}^{n\times n}$$\bm P \in \R^{n \cp n}$ 非奇异，则 $\Vert \mathit{x}{\Vert }_{\mathit{P}}:=\Vert \mathit{P}\mathit{x}\Vert$$\Norm{\bm x}_\bm P := \Norm{\bm P \bm x}$ 是向量范数.

  • 若 $\mathit{A}\in {\mathbb{R}}^{n\times n}$$\bm A \in \R^{n \cp n}$ 为对称正定矩阵，则

    • $\Vert \mathit{x}{\Vert }_{\mathit{A}}=\sqrt{(\mathit{A}\mathit{x},\mathit{x})}$$\Norm{\bm x}_\bm A = \sqrt{(\bm A \bm x, \bm x)}$ 是向量范数.

    • 作分解 $\mathit{A}=\mathit{L}{\mathit{L}}^{\mathrm{T}}$$\bm A = \bm L \bm L\trans$，则 $\Vert \mathit{x}{\Vert }_{\mathrm{A}}=\Vert {\mathit{L}}^{\mathrm{T}}\mathit{x}{\Vert }_2$$\Norm{\bm x}_\rm A = \Norm{\bm L\trans \bm x}_2$.

• 若 $\mathit{A}$$\bm A$ 非奇异，则

  • ${\displaystyle \frac{1}{\Vert {\mathit{A}}^{-1}{\Vert }_{\mathrm{\infty }}}}=\underset{\mathit{y}\ne \mathbf{0}}{min}{\displaystyle \frac{\Vert \mathit{A}\mathit{y}{\Vert }_{\mathrm{\infty }}}{\Vert \mathit{y}{\Vert }_{\mathrm{\infty }}}}$$\dfrac{1}{\Norm{\bm A\inv}_\infty} = \min_{\bm y \ne \bm 0} \dfrac{ \Norm{\bm A \bm y}_\infty }{ \Norm{\bm y}_\infty }$.

5.5 误差分析

5.5.1 矩阵的性态

• 线性方程组 $\mathit{A}\mathit{x}=\mathit{b}$$\bm A \bm x = \bm b$ 的误差，其中 $\mathit{A}$$\bm A$ 非奇异，$\mathit{b}\ne \mathbf{0}$$\bm b \ne \bm 0$.

  • 只考虑 $\mathit{b}$$\bm b$ 有误差 $\delta \mathit{b}$$\delta \bm b$.

    $$\begin{array}{rl}& \{\begin{array}{l}\mathit{A}(\mathit{x}+\delta \mathit{x})=\mathit{b}+\delta \mathit{b},\\ \mathit{A}\mathit{x}=\mathit{b},\mathit{A}\delta \mathit{x}=\delta \mathit{b}.\end{array}\\ \Rightarrow & \{\begin{array}{l}\Vert \delta \mathit{x}\Vert =\Vert {\mathit{A}}^{-1}\delta \mathit{b}\Vert \le \Vert {\mathit{A}}^{-1}\Vert \Vert \delta \mathit{b}\Vert ,\\ \Vert \mathit{b}\Vert =\Vert \mathit{A}\mathit{x}\Vert \le \Vert \mathit{A}\Vert \Vert \mathit{x}\Vert .\end{array}\\ \Rightarrow & {\displaystyle \frac{\Vert \delta \mathit{x}\Vert }{\Vert \mathit{x}\Vert }}\le \Vert {\mathit{A}}^{-1}\Vert \Vert \mathit{A}\Vert {\displaystyle \frac{\Vert \delta \mathit{b}\Vert }{\mathit{b}}}.\end{array}$$

  • 只考虑 $\mathit{A}$$\bm A$ 有误差 $\delta \mathit{A}$$\delta\bm A$，并且 $\Vert {\mathit{A}}^{-1}\Vert \Vert \delta \mathit{A}\Vert <1$$\Norm {\bm A\inv} \Norm{\delta\bm A} < 1$.

    $$\begin{array}{cc}\begin{array}{rl}& (\mathit{A}+\delta \mathit{A})(\mathit{x}+\delta \mathit{x})=\mathit{b}\\ \Rightarrow & (\mathit{A}+\delta \mathit{A})\delta \mathit{x}=-\delta \mathit{A}\mathit{x}\\ \Rightarrow & \mathit{A}(\mathit{I}+{\mathit{A}}^{-1}\delta \mathit{A})\delta \mathit{x}=-\delta \mathit{A}\mathit{x}\\ \Rightarrow & \delta \mathit{x}=-(\mathit{I}+{\mathit{A}}^{-1}\delta \mathit{A}{)}^{-1}{\mathit{A}}^{-1}\delta \mathit{A}\mathit{x}\\ \Rightarrow & \Vert \delta \mathit{x}\Vert \le {\displaystyle \frac{\Vert {\mathit{A}}^{-1}\Vert \Vert \delta \mathit{A}\Vert \Vert \mathit{x}\Vert }{1-\Vert {\mathit{A}}^{-1}\delta \mathit{A}\Vert }}\\ \Rightarrow & {\displaystyle \frac{\Vert \delta \mathit{x}\Vert }{\Vert \mathit{x}\Vert }}\le {\displaystyle \frac{\Vert {\mathit{A}}^{-1}\Vert \Vert \mathit{A}\Vert \frac{\Vert \delta \mathit{A}\Vert }{\Vert \mathit{A}\Vert }}{1-\Vert {\mathit{A}}^{-1}\Vert \Vert \mathit{A}\Vert \frac{\Vert \delta \mathit{A}\Vert }{\Vert \mathit{A}\Vert }}}\end{array}& \begin{array}{rl}& (\mathit{A}+\delta \mathit{A})(\mathit{x}+\delta \mathit{x})=\mathit{b}\\ \Rightarrow & \mathit{A}\delta \mathit{x}=-\delta \mathit{A}(\mathit{x}+\delta \mathit{x})\\ \Rightarrow & \delta \mathit{x}=-{\mathit{A}}^{-1}\delta \mathit{A}(\mathit{x}+\delta \mathit{x})\\ \Rightarrow & \Vert \mathit{x}\Vert \le \Vert {\mathit{A}}^{-1}\Vert \Vert \delta \mathit{A}\Vert \Vert \mathit{x}+\delta \mathit{x}\Vert \\ \Rightarrow & {\displaystyle \frac{\Vert \delta \mathit{x}\Vert }{\Vert \mathit{x}+\delta \mathit{x}\Vert }}\le \Vert {\mathit{A}}^{-1}\Vert \Vert \mathit{A}\Vert {\displaystyle \frac{\Vert \delta \mathit{A}\Vert }{\Vert \mathit{A}\Vert }}\\ \\ \\ \\ \end{array}\end{array}$$

  • 同时考虑 $\delta \mathit{A}$$\delta \bm A$ 和 $\delta \mathit{b}$$\delta \bm b$，并且 $\Vert {\mathit{A}}^{-1}\Vert \Vert \delta \mathit{A}\Vert <1$$\Norm {\bm A\inv} \Norm{\delta\bm A} < 1$.

    $$\begin{array}{rl}& (\mathit{A}+\delta \mathit{A})(\mathit{x}+\delta \mathit{x})=\mathit{b}+\delta \mathit{b}\\ \Rightarrow & (\mathit{A}+\delta \mathit{A})\delta \mathit{x}=\delta \mathit{b}-\delta \mathit{A}\mathit{x}\\ \Rightarrow & \Vert \delta \mathit{x}\Vert \le {\displaystyle \frac{\Vert {\mathit{A}}^{-1}\Vert }{1-\Vert {\mathit{A}}^{-1}\delta \mathit{A}\Vert }}(\Vert \delta \mathit{b}\Vert +\Vert \delta \mathit{A}\Vert \Vert \mathit{x}\Vert )\\ \Rightarrow & {\displaystyle \frac{\Vert \delta \mathit{x}\Vert }{\Vert \mathit{x}\Vert }}\le \Vert \delta \mathit{x}\Vert \le {\displaystyle \frac{\Vert {\mathit{A}}^{-1}\Vert \Vert \mathit{A}\Vert }{1-\Vert {\mathit{A}}^{-1}\Vert \Vert \delta \mathit{A}\Vert }}({\displaystyle \frac{\Vert \delta \mathit{b}\Vert }{\Vert \mathit{b}\Vert }}+{\displaystyle \frac{\Vert \delta \mathit{A}\Vert }{\Vert \mathit{A}\Vert }})\end{array}$$

• 非奇异矩阵 $\mathit{A}$$\bm A$ 的 条件数 $\mathrm{cond}(\mathit{A}{)}_v=\Vert {\mathit{A}}^{-1}{\Vert }_v\Vert \mathit{A}{\Vert }_v$$\cond(\bm A)_v = \Norm{\bm A\inv}_v \Norm{\bm A}_v$.

  • 当 $\mathrm{cond}(\mathit{A})\gg 1$$\cond(\bm A) \gg 1$ 时，矩阵是病态的.

  • 当 $\mathrm{cond}(\mathit{A})\ll 1$$\cond(\bm A) \ll 1$ 时，矩阵是良态的.

5.5.2 矩阵条件数

• 常用的条件数

  • 无穷条件数：$\mathrm{cond}(\mathit{A}{)}_{\mathrm{\infty }}=\Vert {\mathit{A}}^{-1}{\Vert }_{\mathrm{\infty }}\Vert \mathit{A}{\Vert }_{\mathrm{\infty }}$$\cond(\bm A)_\infty = \Norm{\bm A\inv}_\infty \Norm{\bm A}_\infty$.

  • 谱条件数：$\mathrm{cond}(\mathit{A}{)}_2=\sqrt{{\displaystyle \frac{{\lambda }_{max}({\mathit{A}}^{\mathrm{T}}\mathit{A})}{{\lambda }_{min}(\mathit{A}{\mathit{A}}^{\mathrm{T}})}}}$$\cond(\bm A)_2 = \sqrt{\dfrac{\lambda_\max(\bm A\trans \bm A)}{\lambda_\min(\bm A \bm A\trans)}}$.

• 谱条件数的性质

  • 对称阵的谱条件数：$\mathrm{cond}(\mathit{A}{)}_2={\displaystyle \frac{max\left|\lambda \right|}{min\left|\lambda \right|}}$$\cond(\bm A)_2 = \dfrac{\max\vqty{\lambda}}{\min\vqty{\lambda}}$.

  • 正交矩阵的谱条件数：$\mathrm{cond}(\mathit{A}{)}_2=1$$\cond(\bm A)_2 = 1$.

  • 若 $\mathit{R}$$\bm R$ 正交，$\mathit{A}$$\bm A$ 非奇异，则 $\mathrm{cond}(\mathit{R}\mathit{A}{)}_2=\mathrm{cond}(\mathit{A}\mathit{R}{)}_2=\mathrm{cond}(\mathit{A}{)}_2$$\cond(\bm R \bm A)_2 = \cond(\bm A \bm R)_2 = \cond(\bm A)_2$.

• 一般的条件数的性质

  • $\mathrm{cond}(\mathit{A}{)}_v=\Vert {\mathit{A}}^{-1}{\Vert }_v\Vert \mathit{A}{\Vert }_v\ge \Vert {\mathit{A}}^{-1}\mathit{A}{\Vert }_v=1$$\cond(\bm A)_v = \Norm{\bm A\inv}_v \Norm{\bm A}_v \ge \Norm{\bm A\inv \bm A}_v = 1$.

  • $\mathrm{\forall }c\ne 0:\mathrm{cond}(c\mathit{A}{)}_v=\mathrm{cond}(\mathit{A}{)}_v$$\forall c \ne 0 \colon \cond(c \bm A)_v = \cond(\bm A)_v$.

  • $\mathrm{cond}(\mathit{A}\mathit{B})\le \mathrm{cond}(\mathit{A})\mathrm{cond}(\mathit{B})$$\cond(\bm A \bm B) \le \cond(\bm A) \cond(\bm B)$.

• （常见矩阵的条件数）

• 病态矩阵的判断

  • 若使用主元素消去法时出现了小主元，则一般为病态.

  • 若矩阵的行列式较小（某些行近似线性相关），则可能为病态.

  • 若矩阵元素间数量积相差很大且无规则，则可能为病态.

• 病态矩阵的求解

  • 选主元的消去法

  • 采用高精度（双倍字长）

  • 预处理：将 $\mathit{A}\mathit{x}=\mathit{b}$$\bm A \bm x = \bm b$ 转化为 $\{\begin{array}{l}\mathit{P}\mathit{A}\mathit{Q}\mathit{y}=\mathit{P}\mathit{b},\\ \mathit{y}={\mathit{Q}}^{-1}\mathit{x}.\end{array}$$\begin{cases} \bm P \bm A \bm Q \bm y = \bm P \bm b, \\ \bm y = \bm Q\inv \bm x. \end{cases}$，使得 $\mathrm{cond}(\mathit{P}\mathit{A}\mathit{Q})<\mathrm{cond}(\mathit{A})$$\cond(\bm P\bm A\bm Q) < \cond(\bm A)$.

  • 当矩阵的元素大小不均时，对行引进比例因子，使得所有行按 $\mathrm{\infty }-$$\infty-$范数的长度相近.

• 事后误差估计：对于非奇异矩阵 $\mathit{A}$$\bm A$，$\mathit{x}$$\bm x$ 和 ${\mathit{x}}^{\ast }$$\bm x^*$ 分别是 $\mathit{A}\mathit{x}=\mathit{b}\ne \mathbf{0}$$\bm A \bm x = \bm b \ne \bm 0$ 的精确解和近似解，剩余向量 $\mathit{r}=\mathit{b}-\mathit{A}{\mathit{x}}^{\ast }$$\bm r = \bm b - \bm A \bm x^*$，则

  $${\displaystyle \frac{\Vert \mathit{x}-{\mathit{x}}^{\ast }\Vert }{\Vert \mathit{x}\Vert }}\le \mathrm{cond}(\mathit{A})\cdot {\displaystyle \frac{\Vert \mathit{r}\Vert }{\Vert \mathit{b}\Vert }}.$$

5.5.3 迭代改善法

1. 求近似解

   1. 选主元三角分解：$\mathit{P}\mathit{A}=\mathit{L}\mathit{U}$$\bm P \bm A = \bm L \bm U$.

   2. 求解 $\mathit{A}{\mathit{x}}_1=\mathit{b}$$\bm A \bm x_1 = \bm b$，即 $\{\begin{array}{l}\mathit{L}\mathit{y}=\mathit{P}\mathit{b},\\ \mathit{U}{\mathit{x}}_1=\mathit{y}.\end{array}$$\begin{cases} \bm L \bm y = \bm P \bm b, \\ \bm U \bm x_1 = \bm y. \end{cases}$

2. 迭代：$k=1,2,\cdots ,N_0$$k = \oneto{N_0}$，

   1. ${\mathit{r}}_k=\mathit{b}-\mathit{A}{\mathit{x}}_k$$\bm r_k = \bm b - \bm A \bm x_k$.

   2. 求解 $\mathit{A}{\mathit{d}}_k={\mathit{r}}_k$$\bm A \bm d_k = \bm r_k$，即 $\mathit{L}\mathit{U}{\mathit{d}}_k=\mathit{P}{\mathit{r}}_k$$\bm L \bm U \bm d_k = \bm P \bm r_k$.

   3. 如果 $\Vert {\mathit{d}}_k{\Vert }_{\mathrm{\infty }}/\Vert {\mathit{x}}_k{\Vert }_{\mathrm{\infty }}\le \epsilon$$\left. \Norm{\bm d_k}_\infty \right/ \Norm{\bm x_k}_\infty \le \ve$，则停止计算.

   4. ${\mathit{x}}_{k+1}={\mathit{x}}_k+{\mathit{d}}_k$$\bm x_{k+1} = \bm x_k + \bm d_k$.

如果矩阵非常病态，则上述算法仍可能不收敛.