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

n阶线性代数方程组的一般形式

$$\begin{cases} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = b_2 \\ \vdots \\ a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nn}x_n = b_n \end{cases}$$

或写成矩阵——向量形式：Ax=b，其中A为系数矩阵，x为解向量，b为右端常向量，分别为

$$A = \begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \cdots & a_{nn} \end{pmatrix}, x = \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}, b = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{pmatrix}$$

直接消去法

顺序高斯消去法

• 消元过程

设

$$a_{kk}^{(k)}\ne0$$

对k=1,2,…,n-1计算

$$\left\{ \begin{array}{l} m_{ik} = \frac{a_{ik}^{(k)}}{a_{kk}^{(k)}} \\ a_{ij}^{(k+1)} = a_{ij}^{(k)} - m_{ik} a_{kj}^{(k)} \\ b_{i}^{(k+1)} = b_{i}^{(k)} - m_{ik} b_{k}^{(k)} \end{array} \right. \quad i,j=k+1,k+2,\ldots,n$$

• 回代过程

$$\left\{ \begin{array}{l} x_n = \frac{b_n^{(n)}}{a_{nn}^{(n)}} \\ x_i = \left( b_i^{(i)} - \sum_{j=i+1}^{n} \frac{a_{ij}^{(i)} x_j}{a_{ii}^{(i)}} \right) / a_{ii}^{(i)} \end{array} \right. \quad i = n-1,\ldots, 2, 1$$

• 特点

1. 按消元规则运算后，对角线以下元素为0，故运算中对于对角线以下元素不进行计算，以减少计算量

2. 对角线下元素对回代求解无影响，故将乘数放在该处，即a_ik/a_kk→a_ik，i=k+1,k+2,…,n以节省存储单元

3. 对角线以上元素和常数项采用“原地”工作方式，即经变换后的元素仍放在原来的位置上

   $$\left\{ \begin{array}{l} a_{ij} - a_{ik}a_{kj} \rightarrow a_{ij} \\ b_{i} - a_{ik}b_{k} \rightarrow b_{i} \end{array} \right. \quad i, j = k + 1, k + 2, \ldots, n$$

   以节省存储单元

4. 回代后的值仍被放在常数项存储单元

   $$\frac{b_n}{a_{nn}} \rightarrow b_n$$

   $$\left( b_i - \sum_{j=i+1}^{n} a_{ij} x_j \right) / a_{ii} \rightarrow b_i,\quad i = n-1, n-2, \ldots, 1$$

   以节省存储单元，这时b₁,b₂,…,b_n单元中存放的就是输出值x₁,x₂,…,x_n

• 使用条件

将第k步消x_k时用的方程及其系数分别叫作第k步的主方程和主行，而x_k的系数a_kk^(k)叫作第k步的主元素，要求各步主元素不为0

定理

• 方程组系数矩阵的顺序主子式全不为零，则高斯消去法能实现方程组的求解

  顺序主子式：设方程组系数矩阵A=(a_ij)_n，其顺序主子式

  $$D_i = \begin{vmatrix} a_{11} & \cdots & a_{1i} \\ \vdots & \ddots & \vdots \\ a_{i1} & \cdots & a_{ii} \end{vmatrix}, \quad i = 1, 2, \ldots, n$$

  非奇异矩阵：|A|≠0

• 设方程组Ax=b，如果系数矩阵A为严格对角占优矩阵，则用高斯消去法求解时，主元素a_kk^(k)全不为零

  严格对角占优矩阵：矩阵A=(a_ij)_n每一行对角元素的绝对值都大于同行其他元素绝对值之和

  $$\left| a_{ii} \right| > \sum_{\substack{j=1 \\ j \neq i}}^{n} \left| a_{ij} \right|, \quad i = 1, 2, \ldots, n$$

• 高斯消元法求解n阶线性方程组共需乘除法次数近似为1/3n³

列主元高斯消去法

顺序高斯消元法有如下两弊端：

1. 顺序消元过程中可能出现主元素a_kk^(k)=0
2. a_kk^(k)≠0，但其绝对值很小，用它作为除数也会导致其他元素的数量级急剧增大和使舍入误差扩大，影响计算结果精度

为避免在消元过程确定乘数时所用除数是零或绝对值小的数，即零主元或小主元，在每一次消元之前，要增加一个选主元的过程，将绝对值大的元素交换到主对角线的位置上。根据交换的方法又分成全选主元和列选主元两种选主元方法

全选主元是当变换到第k步时，从右下角n-k+1阶子阵中选取绝对值最大的元素，然后通过行交换与列交换将其交换到a_kk的位置上，并且保留下交换的信息，以供后面调整解向量中分量的次序时使用

列选主元是当消元到第k步时，从k列的a_kk以下（包括a_kk）的各元素中选出绝对值最大的，然后通过行交换将其交换到a_kk的位置上。交换系数矩阵中的两行（包括常数项），只相当于两个方程的位置交换了，因此，列选主元不影响求解的结果

列选主元：设主元在第l(k≤l≤n)个方程，即

$$|a_{lk}|=\max_{k\leqslant i\leqslant n}|a_{ik}|$$

若l≠k，将l和k方程互易位置，使新的a_kk成为主元，然后继续进行

列选主元比全选主元的运算量小，但一般可以满足精度要求，所以列选主元更常被采用

严格对角占优矩阵可保证a_kk^(k)就是主元

定理

• 列主元消去法在解方程组时，还可求出系数行列式。设系数矩阵

  $$A = \begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \cdots & a_{nn} \end{pmatrix}$$

  用列主元消去法将其转换为上三角形矩阵，对角线上元素为a₁₁⁽¹⁾,a₂₂⁽²⁾,…,a_nn⁽ⁿ⁾，于是行列式

  $$\det(A) = (-1)^m a_{11}^{(1)} a_{22}^{(2)} \cdots a_{nn}^{(n)}$$

  其中m为所进行的行交换次数

高斯——若尔当消去法

前述的高斯消去法有消元和回代两过程，对消元过程稍加改变使方程组化为对角形方程组Dx=b形式，其中矩阵D为对角形矩阵

$$D = \begin{pmatrix} a_{11}^{(1)} & & & \\ & a_{22}^{(2)} & & \\ & & \ddots & \\ & & & a_{nn}^{(n)} \end{pmatrix}$$

此时求解无需回代

• 特点

每次消元时利用主元将其所在列的其余元素全部消为0，即在第k次消元时，把k列中（k,k）位置以下和以上的元素消为0，但主行不进行消元

高斯——若尔当消去法执行一次归一化过程需要进行n-k+1次除法，而执行一次消去过程需要进行(n-1)(n-k+1)次乘法，因此高斯——若尔当消去法进行的乘除法总计算工作量为

$$\sum_{k=1}^{n} (n - k + 1)n = \frac{n^2}{2}(n + 1) \approx \frac{1}{2}n^3$$

高斯——若尔当消去法比高斯消去法多了约1/6的计算工作量，但高斯——若尔当消去法无需回代，算法结构稍许简单

用归一化的高斯——若尔当消去法求矩阵的逆比较方便

设A非奇异，则A^-1存在，记

$$A^{-1}=X = \begin{pmatrix} x_{11} & \cdots & x_{1n} \\ \vdots & \ddots & \vdots \\ x_{n1} & \cdots & x_{nn} \end{pmatrix}$$

则求A的逆矩阵A^-1等价于求n阶矩阵X，使AX=I，其中I为n×n的单位矩阵。将X和I分块

$$X = (x_1, x_2, \cdots, x_n), I = (e_1, e_2, \cdots, e_n)$$

其中

$$x_i = (x_{1i}, x_{2i}, \cdots, x_{ni})^T$$

$$e_1 = (1, 0, \cdots, 0)^T, \cdots, e_n = (0, \cdots, 0, 1)^T$$

则求解AX=I等价于求解系数矩阵相同的n个方程组Ax_j=e_j，j=1,2,…,n，即

$$Ax_1 = \begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}, \quad Ax_2 = \begin{pmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{pmatrix}, \quad \ldots, \quad Ax_n = \begin{pmatrix} 0 \\ \vdots \\ 0 \\ 1 \end{pmatrix}$$

可用上述高斯——若尔当消去法（或再加上选主元技术）求解这n个方程组

三角分解法

LU

• 杜里特尔分解：把A分解成一个单位下三角阵L和一个上三角阵U的乘积

• 克洛特分解：把A分解成一个下三角阵L和一个单位上三角阵U的乘积

矩阵A各阶主子式不为零，则可唯一地分解成一个单位下三角阵L和一个非奇异的上三角阵U的乘积

各阶主子式不为零也可说成顺序主子阵非奇异。上述分解即是杜里特尔分解，对于克洛特分解所需条件也是一样的

顺序主子阵非奇异，因为非奇异矩阵就不一定存在LU分解，设

$$A=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$

则|A|=-1≠0，A非奇异。若A有LU分解，即存在数a,b,c,d,使

$$\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & \\ a & 1 \end{pmatrix} \begin{pmatrix} b & d \\& c \end{pmatrix}$$

比较等式两边第一列，有b=0，ab=1

上两式不能同时成立，即A不存在LU分解

下三角形矩阵的乘积仍是下三角形矩阵

杜里特尔分解

$$\begin{pmatrix} 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{pmatrix} = \begin{pmatrix} 1 & & & \\ l_{21} & 1 & & \\ \vdots & \vdots & \ddots & \\ l_{n1} & l_{n2} & \cdots & 1 \end{pmatrix} \begin{pmatrix} u_{11} & u_{12} & \cdots & u_{1n} \\ & u_{22} & \cdots & u_{2n} \\ & & \ddots & \vdots \\ & & & u_{nn} \end{pmatrix}$$

由矩阵乘法规则

$$a_{1i} = u_{1i}, \quad i = 1, 2, \ldots, n$$

$$a_{i1} = l_{i1} u_{11}, \quad i = 2, 3, \ldots, n$$

得U的第一行元素和L的第一列元素

$$u_{1i} = a_{1i}, \quad i = 1, 2, \ldots, n$$

$$l_{i1} = \frac{a_{i1}}{u_{11}}, \quad i = 2, 3, \ldots, n$$

当得出U的前r-1行元素和L的前r-1列元素，，对于i=r,r+1,…,n，有

$$a_{ri} = \sum_{k=1}^{n} l_{rk} u_{ki} = \sum_{k=1}^{r-1} l_{rk} u_{ki} + u_{ri}$$

$$a_{ir} = \sum_{k=1}^{n} l_{ik} u_{kr} = \sum_{k=1}^{r-1} l_{ik} u_{kr} + l_{ir} u_{rr}$$

得计算U的第r行和L的第r列元素的公式

$$u_{ri} = a_{ri} - \sum_{k=1}^{r-1} l_{rk} u_{ki}, \quad i = r, r + 1, \ldots, n$$

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

A的行列式|A|=|L||U|=u₁₁u₂₂…u_nn

解线性方程组

求解线性方程组Ax=b时，当对A进行LU分解时，等价于求解LUx=b，可归结为利用递推计算相继求解两个三角形（系数矩阵为三角矩阵）方程组，用顺代，由Ly=b，求出y，再利用回代，由Ux=y求出x

• Ly=b，即计算

  $$\begin{cases} y_1 = b_1 \\ y_i = b_i - \sum_{k=1}^{i-1} l_{ik} y_k, \quad i = 2, 3, \ldots, n \end{cases}$$

• Ux=y，即计算

  $$\begin{cases} x_n = y_n / u_{nn} \\ x_i = \left( y_i - \sum_{k=i+1}^{n} u_{ik} x_k \right) / u_{ii}, \quad i = n-1, \ldots, 2, 1 \end{cases}$$

用LU直接分解的方法求解线性方程组的计算量为1/3n³，和高斯消去法需要的计算量的数量级基本相同

求逆矩阵

1. 对矩阵A和单位矩阵I组成的增广矩阵AI进行杜里特尔分解AI→LUY，其中A，I，L，U，Y∈R^n×n，L为单位下三角阵，U为上三角阵
2. 对j=1,2,…,n求解方程组系Ux=y_i，其中y_i是矩阵Y的第j列。解记为x=a_j，j=1,2,…,n
3. A^-1=(a₁,a₂,…,a_n)

克洛特分解

• 分解形式

$$\begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \cdots & a_{nn} \end{pmatrix} = \begin{pmatrix} l_{11} & & \\ l_{21} & l_{22} & \\ \vdots & \vdots & \ddots \\ l_{n1} & l_{n2} & \cdots & l_{nn} \end{pmatrix} \begin{pmatrix} 1 & u_{12} & u_{13} & \cdots & u_{1n} \\ & 1 & u_{23} & \cdots & u_{2n} \\ & & \ddots & & \vdots \\ & & & & 1 \end{pmatrix}$$

可得

$$l_{i1} = a_{i1}, \quad i = 1, 2, \cdots, n$$

$$u_{1i} = \frac{a_{1i}}{l_{11}}, \quad i = 2, 3, \cdots, n$$

且当L的前r-1列元素和U的前r-1行元素已经算出以后，对于i=r,r+1,…,n有

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

$$u_{ri} = \left( a_{ri} - \sum_{k=1}^{r-1} l_{rk} u_{ki} \right) / l_{rr}, \quad i = r + 1, r + 2, \cdots, n$$

• 解线性方程组

1. 计算l_i1，i=1,2,…,n和u_li，i=2,3,…,n

2. 对于r=2,3,…,n计算l_ir，i=r,r+1,…,n和u_ri，i=r+1,r+2,…,n

3. 求解Ly=b，即计算

   $$\begin{cases} y_1 = \frac{b_1}{l_{11}} \\ y_i = (b_i - \sum_{k=1}^{i-1} l_{ik} y_k)/l_{ii}, \quad i = 2, 3, \cdots, n \end{cases}$$

4. 求解Ux=y，即计算

   $$\begin{cases} x_n = y_n \\ x_i = y_i - \sum_{k=i+1}^{n} u_{ik} x_k, \quad i = n-1, \cdots, 2, 1 \end{cases}$$

平方根法

对称正定矩阵：矩阵A∈R^n×n满足A^T=A，且对任意非零向量x∈Rⁿ，有(Ax,x)=x^TAx＞0

• 对称正定矩阵A的对角元为正，即a_ii＞0，i=1,2,…,n
• 实对称矩阵A正定的充要条件是A的所有特征值为正
• 对称正定矩阵非奇异，其逆亦为对称正定矩阵
• 实对称矩阵A正定的充要条件是A的所有顺序主子式为正
• 正定矩阵的顺序主子阵是正定的

乔累斯基分解

• 对称正定矩阵A存在唯一的单位下三角矩阵L和对角矩阵D，使A=LDL^T

乔累斯基分解：对称正定矩阵A存在唯一的对角元素均为正数的下三角矩阵L，使A=LL^T

乔累斯基分解所需要的乘除次数约为1/6n³数量级，差不多比LU分解节省一半的工作量，但要进行n次开方运算

将A=LL^T写成

$$\begin{pmatrix} a_{11} & & \cdots& & a_{1n} \\ &\ddots& & & \\ \vdots& & a_{ii} & & \vdots \\ & & &\ddots & \\ a_{n1} & & \cdots & & a_{nn} \end{pmatrix} = \begin{pmatrix} l_{11} & & \\ l_{21} & l_{22} & \\ \vdots & & \ddots \\ l_{n1} & l_{n2} & \cdots & l_{nn} \end{pmatrix} \begin{pmatrix} l_{11} & l_{21} & \cdots & l_{n1} \\ & l_{22} & \cdots & l_{n2} \\ & & \ddots & \vdots \\ & & & l_{n} \end{pmatrix}$$

对于i=1,2,…,n，有

$$\left\{ \begin{array}{l} l_{i i}=\left(a_{i}-\sum_{k=1}^{i-1} l_{i k}^{2}\right)^{\frac{1}{2}}\\ l_{j i}=\left(a_{j}-\sum_{k=1}^{i-1} l_{j k} l_{i k}\right)/ l_{i},\quad j=i+1, i+2,\cdots, n \end{array} \right.$$

$$|A|=\left| LL^{T}\right|=|L|\left| L^{T}\right|=\prod_{i=1}^{n} l_{i}^{2}$$

• 求解对称正定方程组

将A=LL^T代入Ax=b，有LL^Tx=b，令L^Tx=y，有

$$\left\{ \begin{array}{l} L y = b \\ L^T x = y \end{array} \right.$$

相应的求解公式

$$\begin{cases} y_i = (b_i - \sum_{k=1}^{i-1} l_{ik} y_k)/l_{ii}, \quad i = 1, 2, \ldots, n \\ x_i = (y_i - \sum_{k=i+1}^{n} l_{ki} x_k)/l_{ii}, \quad i = n, n-1, \ldots, 1 \end{cases}$$

由矩阵分解公式可知

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

$$|l_{ik}| \leq \sqrt{a_{ii}}, \quad k \leq i$$

平方根法所求得的中间量l_kk是可控的，即舍入误差的增长也可控

平方根法解正定方程组的缺点是需要进行开方运算

改进平方根法

将对称正定矩阵A=(a_ij)_n×n进行LDL^T分解，可避免开方运算，其中D=diag(d_i)，且d_i＞0，L为单位下三角矩阵，则

$$\begin{pmatrix} a_{11} & & \cdots& & a_{1n} \\ &\ddots& & & \\ \vdots& & a_{ij} & & \vdots \\ & & &\ddots & \\ a_{n1} & & \cdots & & a_{nn} \end{pmatrix} = \begin{pmatrix} 1 & & \\ l_{21} & 1 & \\ \vdots & \vdots & \ddots \\ l_{n1} & l_{n2} & \cdots & 1 \end{pmatrix} \begin{pmatrix} d_1 & & \\ & d_2 & \\ & & \ddots & \\ & & & d_n \end{pmatrix} \begin{pmatrix} 1 & l_{21} & l_{31} & \cdots & l_{n1} \\ & 1 & l_{32} & \cdots & l_{n2} \\ & & \ddots & \ddots & \vdots \\ & & & 1 & l_{nj} \\ & & & & 1 \end{pmatrix}$$

对=1,2,…,n有

$$\begin{cases} l_{ij} = \left( a_{ij} - \sum_{k=1}^{j-1} l_{ik} d_k l_{jk} \right) / d_j, & j = 1, 2, \ldots, i-1 \\ d_i = a_{ii} - \sum_{k=1}^{i-1} d_k l_{ik}^2 \end{cases}$$

按此方式进行LDL^T分解避免了开方运算，但在计算每个元时多了相乘的因子，为避免重复计算，进行如下变换：A=LDL^T=TL^T，其中T=LD，辅助变量t_ij=l_ijd_j

代入得对于i=1,2,…,n计算

$$\left\{ \begin{array}{l} t_{ij} = a_{ij} - \sum_{k=1}^{j-1} t_{ik} l_{jk}, \quad j = 1, 2, \cdots, i-1 \\ l_{ij} = \frac{t_{ij}}{d_j}, \quad j = 1, 2, \cdots, i-1 \\ d_i = a_{ii} - \sum_{k=1}^{i-1} t_{ik} l_{ik} \end{array} \right.$$

• 求解对称正定方程组

Ax=b等价于求解L(DL^Tx)=b，可分解成由Ly=b求y，再由DL^Tx=y求x

$$\left\{ \begin{array}{l} y_i = b_i - \sum_{k=1}^{i-1} l_{ik} y_k, \quad i = 1, 2, \cdots, n \\ x_i = \frac{y_i}{d_i} - \sum_{k=i+1}^{n} l_{ki} x_k, \quad i = n, n-1, \cdots, 1 \end{array} \right.$$

范数

向量范数

• 1-范数（绝对值范数）

$$\|x\|_1 = \sum_{i=1}^{n} |x_i| = |x_1| + |x_2| + \cdots + |x_n|$$

• 2-范数（欧几里得范数）

$$\|x\|_2 = \left( \sum_{i=1}^{n} x_i^2 \right)^{\frac{1}{2}} = \sqrt{x_1^2 + x_2^2 + \cdots + x_n^2}$$

• ∞-范数（最大范数）

$$\|x\|_\infty = \max_{1 \leq i \leq n} |x_i| = \max_i \{|x_1|, |x_2|, \cdots, |x_n|\}$$

矩阵范数

• 行范数

$$\|A\|_\infty = \max_{1 \leq i \leq n} \sum_{j=1}^{n} |a_{ij}|$$

• 列范数

$$\|A\|_1 = \max_{1 \leq j \leq n} \sum_{i=1}^{n} |a_{ij}|$$

• 谱范数

$$\|A\|_2 = \sqrt{\lambda_{\max}(A^T A)}$$

其中λ_max(A^TA)表示矩阵A^TA的最大特征值

假设我们有一个2×2的矩阵A：

$$A=\begin{pmatrix}3&1\\1&3\end{pmatrix}$$

想要找到这个矩阵的特征值。首先，我们需要解特征方程，即det⁡(A−λI)=0，其中I是单位矩阵，λ是特征值

矩阵A的特征方程是

$$\det \begin{pmatrix}3-\lambda&1\\1&3-\lambda\end{pmatrix}=0$$

$$(3-\lambda)(3-\lambda)-1\cdot1=0$$

$$\lambda^2-6\lambda+8=0$$

$$\lambda_1=4,\lambda_2=2$$

则矩阵A的最大特征值是λ₁=4

• F范数

$$\|A\|_F = \sqrt{\sum_{i=1}^{m} \sum_{j=1}^{n} a_{ij}^2}$$

迭代法

已知线性方程组Ax=b，其中A∈R^n×n，b∈Rⁿ，A非奇异，设找到一个等价方程组x=Bx+f，从而建立迭代格式

$$x^{(k+1)}= Bx^{(k)} + f, \quad k = 0, 1, \cdots \\$$

当给定初始向量x⁽⁰⁾后，可按上式迭代，得到迭代向量序列{x^(k)}，当k→+∞时，x^(k)→x^*，则x^*是线性方程组Ax=b的解

对线性方程组Ax=b用等价方程x=Bx+f建立迭代格式x^(k+1)=Bx^(k)+f，k=0,1,…逐步求解的方法叫迭代法。若$\lim_{k \to +\infty} x^{(k)}= x^*$，则称迭代法收敛，x^*即方程组的解，否则称此迭代法发散

雅可比迭代

$$\sum_{j=1}^{n} a_{ij} x_{j} = b_{i}, \quad i=1,2,\cdots, n$$

设a_ii≠0，从上式中分离出变量x_i，将它改写成

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

据此建立得到雅可比迭代公式

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

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

迭代的收敛性

• 谱半径

矩阵A∈R^n×n的所有特征值λ_i（i=1,2,…,n）的模的最大值称为矩阵A的谱半径ρ(A)

$$\rho (A)= \max_{1 \leq i \leq n}|\lambda_i|$$

• 矩阵A的谱半径不超过矩阵A的任一种范数||A||