一、线性方程组求解

• 在 MATLAB 中，关于线性方程组的解法一般分为两类：一类是直接法，就是在没有舍入误差的情况下，通过有限步的矩阵初等运算来求得方程组的解；另一类是迭代法，就是先给定一个解的初始值，然后按照一定的迭代算法进行逐步逼近，求出更精确的近似解。

1. 线性方程组的直接解法

• 线性方程组的直接解法大多基于高斯消元法、主元素消元法、平方根法和追赶法等。在 MATLAB 中，这些算法已经被编成了现成的库函数或运算符，因此，只需调用相应的函数或运算符即可完成线性方程组的求解。

1.1 利用左除运算符的直接解法

• 线性方程组求解最简单的方法就是使用左除运算符 ，系统会自动根据输入的系数矩阵判断选用哪种方法进行求解。
• 对于线性方程组 $Ax=b$，可以利用左除运算符 求解：$$x=A\setminus b$$
• 当系数矩阵 $A$ 为 $N\times N$ 的方阵时，MATLAB 会自行用高斯消元法求解线性方程组。若右端项 $b$ 为 $N\times 1$ 的列向量，则 $x=A\setminus b$ 可获得方程组的数值解 $x$（$N\times 1$ 的列向量）。
• 若右端项 $b$ 为 $N\times M$ 的矩阵，则 $x=A\setminus b$ 可同时获得系数矩阵 $A$ 相同的 $M$ 个线性方程组的数值解 $x$（为 $N\times M$ 的矩阵），即 $x(:,j)=A\setminus b(:,j),j=1,2,\dots ,M$。
• 这里需要注意的是，如果矩阵 $A$ 是奇异的或接近奇异的，则 MATLAB 会给出警告信息。
• 例如，我们用直接解法求解下列线性方程组。$$\{\begin{array}{c}2x_1+x_2-5x_3+x_4=13\\ x_1-5x_2+7x_4=-9\\ 2x_2+x_3-x_4=6\\ x_1+6x_2-x_3-4x_4=0\end{array}$$
• 程序如下：

>> A=[2,1,-5,1;1,-5,0,7;0,2,1,-1;1,6,-1,-4];
>> b=[13,-9,6,0]';
>> x=A

• 程序运行结果如下：

x =

  -66.5556
   25.6667
  -18.7778
   26.5556

1.2 利用矩阵的分解求解线性方程组

• 矩阵分解是指根据一定的原理用某种算法将一个矩阵分解成若干个矩阵的乘积。常见的矩阵分解有 LU 分解、QR 分解、Cholesky 分解，以及 Schur 分解、Hessenberg 分解、奇异分解等。
• 通过这些分解方法求解线性方程组的有点是运算速度快，可以节省存储空间。
• （1） LU 分解。矩阵的 LU 分解就是将一个矩阵表示为一个变换下三角阵和一个上三角阵的乘积形式。线性代数中已经证明，只要方阵 $X$ 是非奇异的，LU 分解总是可以进行的。
• MATLAB 提供的 lu 函数用于对矩阵进行 LU 分解，其调用格式如下。
• ① [L,U]=lu(X)：产生一个上三角阵 U 和一个变换形式的下三角阵 L（行交换），使之满足 $X=LU$。注意，这里的矩阵 $X$ 必须是方阵。
• ② [L,U,P]=lu(X)：产生一个上三角阵 U 和一个下三角阵 L 以及一个置换矩阵 P，使之满足 $PX=LU$。当然矩阵 $X$ 同样必须是方阵。
• 当使用第一种格式时，矩阵 $L$ 往往不是一个下三角阵，但可以通过行交换成为一个下三角阵。
• 例如，我们设 $$A=\left[\begin{array}{ccc}1& -1& 1\\ 5& -4& 3\\ 2& 1& 1\end{array}\right]$$
• 则对矩阵 $A$ 进行 LU 分解的程序如下：

>> A=[1,-1,1;5,-4,3;2,1,1];
>> [L,U]=lu(A)

L =

    0.2000   -0.0769    1.0000
    1.0000         0         0
    0.4000    1.0000         0


U =

    5.0000   -4.0000    3.0000
         0    2.6000   -0.2000
         0         0    0.3846

• 为检验结果是否正确，输入如下程序：

>> LU=L*U

LU =

     1    -1     1
     5    -4     3
     2     1     1

• 说明结果是正确的。例中所获得的矩阵 $L$ 并不是一个下三角阵，但经过各行互换之后，即可获得一个下三角阵。
• 利用第二种格式对矩阵 $A$ 进行 LU 分解，程序如下：

>> [L,U,P]=lu(A)

L =

    1.0000         0         0
    0.4000    1.0000         0
    0.2000   -0.0769    1.0000


U =

    5.0000   -4.0000    3.0000
         0    2.6000   -0.2000
         0         0    0.3846


P =

     0     1     0
     0     0     1
     1     0     0

>> LU=L*U		%这种分解其乘积不为A

LU =

     5    -4     3
     2     1     1
     1    -1     1

>> inv(P)*L*U	%考虑矩阵P后的结果

ans =

     1    -1     1
     5    -4     3
     2     1     1

• 实现 LU 分解后，线性方程组 $Ax=b$ 的解 $x=U\setminus (L\setminus b)$ 或 $x=U\setminus (L\setminus Pb)$，这样可以大大提高运算速度。
• 例如，我们用 LU 分解求解下列线性方程组。$$\{\begin{array}{c}2x_1+x_2-5x_3+x_4=13\\ x_1-5x_2+7x_4=-9\\ 2x_2+x_3-x_4=6\\ x_1+6x_2-x_3-4x_4=0\end{array}$$
• 程序如下：

>> A=[2,1,-5,1;1,-5,0,7;0,2,1,-1;1,6,-1,-4];
>> b=[13,-9,6,0]';
>> [L,U]=lu(A)

L =

    1.0000         0         0         0
    0.5000    1.0000         0         0
         0   -0.3636    0.4773    1.0000
    0.5000   -1.0000    1.0000         0


U =

    2.0000    1.0000   -5.0000    1.0000
         0   -5.5000    2.5000    6.5000
         0         0    4.0000    2.0000
         0         0         0    0.4091

>> x=U(L)

x =

  -66.5556
   25.6667
  -18.7778
   26.5556

• 或采用 LU 分解的第二种格式，程序如下：

>> [L,U,P]=lu(A);
>> x=U(LP*b);

• 将得到与上面相同的结果。
• （2） QR 分解。对矩阵 $X$ 进行 QR 分解，就是把 $X$ 分解为一个正交矩阵 $Q$ 和一个上三角矩阵 $R$ 的乘积形式。QR 分解只能对方阵进行。MATLAB 的函数 qr 可用于对矩阵进行 QR 分解，其调用格式如下。
• ① [Q,R]=qr(X)：产生一个正交矩阵 $Q$ 和一个上三角阵 $R$，使之满足 $X=QR$。
• ② [Q,R,E]=qr(X)：产生一个正交矩阵 $Q$、一个上三角阵 $R$ 以及一个置换矩阵 $E$，使之满足 $XE=QR$。
• 例如，我们设 $$A=\left[\begin{array}{ccc}1& -1& 1\\ 5& -4& 3\\ 2& 7& 10\end{array}\right]$$
• 则对矩阵 $A$ 进行 $QR$ 分解的命令如下：

>> A=[1,-1,1;5,-4,3;2,7,10];
>> [Q,R]=qr(A)

Q =

   -0.1826   -0.0956   -0.9785
   -0.9129   -0.3532    0.2048
   -0.3651    0.9307   -0.0228


R =

   -5.4772    1.2780   -6.5727
         0    8.0229    8.1517
         0         0   -0.5917

• 为检验结果是否正确，输入如下程序：

>> QR=Q*R

QR =

    1.0000   -1.0000    1.0000
    5.0000   -4.0000    3.0000
    2.0000    7.0000   10.0000

• 说明结果是正确的。此时，我们利用第二种格式对矩阵 $A$ 进行 QR 分解：

>> [Q,R,E]=qr(A)

Q =

   -0.0953   -0.2514   -0.9632
   -0.2860   -0.9199    0.2684
   -0.9535    0.3011    0.0158


R =

  -10.4881   -5.4347   -3.4325
         0    6.0385   -4.2485
         0         0    0.4105


E =

     0     0     1
     0     1     0
     1     0     0

>> Q*R/E		%验证A=Q*R*inv(E)

ans =

    1.0000   -1.0000    1.0000
    5.0000   -4.0000    3.0000
    2.0000    7.0000   10.0000

• 在实现 QR 分解后，线性方程组 $Ax=b$ 的解为 $x=R\setminus (Q\setminus b)$ 或 $x=E\setminus (R\setminus (Q\setminus b))。$
• 例如，我们用 QR 分解求解下列线性方程组。$$\{\begin{array}{c}2x_1+x_2-5x_3+x_4=13\\ x_1-5x_2+7x_4=-9\\ 2x_2+x_3-x_4=6\\ x_1+6x_2-x_3-4x_4=0\end{array}$$
• 程序如下：

>> A=[2,1,-5,1;1,-5,0,7;0,2,1,-1;1,6,-1,-4];
>> b=[13,-9,6,0]';
>> [Q,R]=qr(A);
>> x=R(Q)

• 程序运行结果如下：

x =

  -66.5556
   25.6667
  -18.7778
   26.5556

• 或采用 QR 分解的第二种格式，程序如下：

>> [Q,R,E]=qr(A);
>> x=E*(R(Q))

x =

  -66.5556
   25.6667
  -18.7778
   26.5556

• 将得到与上面相同的结果。
• （3） Cholesky 分解。如果矩阵 $X$ 是对称正定的，则 Cholesky 分解将矩阵 $X$ 分解成一个下三角阵和一个上三角阵的乘积。设上三角阵为 $R$，则下三角阵为其转置，即 $X=R^{\prime }R$。MATLAB 函数 chol(X) 用于对矩阵 $X$ 进行 Cholesky 分解，其调用格式如下。
• ① R=chol(X)：产生一个上三角阵$R$，使 $R^{\prime }R=X$。若 $X$ 为非对称正定，则输出一个出错信息。
• ② [R,p]=chol(X)：这个命令格式将不输出出错信息。若 $X$ 为对称正定的，则 $p=0$，$R$ 与上述格式得到的结果相同，否则 $p$ 为一个正整数。如果 $X$ 为满秩矩阵，则 $R$ 为一个阶数为 $q=p-1$ 的上三角阵，且满足 $R^{\prime }R=X(1:q,1:q)$。
• 例如，我们设 $$A=\left[\begin{array}{ccc}2& 1& 1\\ 1& 2& -1\\ 1& -1& 3\end{array}\right]$$
• 则对矩阵 $A$ 进行 Cholesky 分解的命令如下：

>> A=[2,1,1;1,2,-1;1,-1,3];
>> R=chol(A)

R =

    1.4142    0.7071    0.7071
         0    1.2247   -1.2247
         0         0    1.0000

• 可以验证 $R^{\prime }R=A$，输入如下程序：

>> R'*R

ans =

    2.0000    1.0000    1.0000
    1.0000    2.0000   -1.0000
    1.0000   -1.0000    3.0000

• 说明结果是正确的。此时，我们利用第二种格式对矩阵 $A$ 进行 Cholesky 分解：

>> [R,p]=chol(A)

R =

    1.4142    0.7071    0.7071
         0    1.2247   -1.2247
         0         0    1.0000


p =

     0

• 结果中出现 $p=0$，这表示矩阵 $A$ 是一个正定矩阵。如果试图对一个非正定矩阵进行 Cholesky 分解，则将得出错误信息，所以，chol 函数还可以用来判定矩阵是否为正定矩阵。
• 实现 Cholesky 分解后，线性方程组 $Ax=b$ 的解为 $R^{\prime }Rx=b$，所以 $x=R\setminus (R^{\prime }\setminus b)。$
• 例如，我们用 Cholesky 分解求解下列线性方程组。$$\{\begin{array}{c}2x_1+x_2-5x_3+x_4=13\\ x_1-5x_2+7x_4=-9\\ 2x_2+x_3-x_4=6\\ x_1+6x_2-x_3-4x_4=0\end{array}$$
• 程序如下：

>> A=[2,1,-5,1;1,-5,0,7;0,2,1,-1;1,6,-1,-4];
>> b=[13,-9,6,0]';
>> R=chol(A)
错误使用 chol
矩阵必须为正定矩阵。

• 命令执行时，出现错误信息，说明 $A$ 为非正定矩阵。

2. 线性方程组的迭代解法

• 迭代法是一种不断用变量的旧值递推新值的过程，是用计算机解决问题的一种基本方法。它利用计算机运算速度快，适合做重复性操作的特点，让一组指令重复执行，在每次执行这组指令时，都从变量的原值推出它的新值。
• 迭代解法非常适合求解大型稀疏矩阵的方程组。在数值分析中，迭代解法主要包括 Jacobi 迭代法、Gauss-Serdel 迭代法、超松弛迭代法和两步迭代法。
• 首先，我们用一个例子说明迭代法的思想。
• 为了求解线性方程组 $$\{\begin{array}{c}10x_1-x_2=9\\ -x_1+10x_2-2x_3=7\\ -2x_2+10x_3=6\end{array}$$
• 将方程改写为 $$\{\begin{array}{c}{x}_1=10x_2-2x_3-7\\ x_2=10x_1-9\\ x_3=\frac{1}{10}(6+2x_2)\end{array}$$
• 这种形式的好处是将一组 $x$ 代入右端，可以立即得到另一组 $x$。如果两组 $x$ 相等，那么它就是方程组的解，不等时可以继续迭代。
• 例如，选取初值 $x_1=x_2=x_3=0$，则经过一次迭代后， 得到 $x_1=-7$，$x_2=-9$，$x_3=0.6$，然后再继续迭代。可以构造方程的迭代公式为 $$\{\begin{array}{c}{x}_1^{(k+1)}=10x_2^{(k)}-2x_3^{(k)}-7\\ x_2^{(k+1)}=10x_1^{(k)}-9\\ x_3^{(k+1)}=\frac{1}{10}(6+2x_2^{(k)})\end{array}$$

2.1 Jacobi 迭代法

• 对于线性方程组 $Ax=b$，如果 $A$ 是非奇异方阵，且 $a_{ii}\ne 0(i=1,2,\dots ,n)$，则可将 $A$ 分解为 $A=D-L-U$，其中 $D$ 为对角阵，其元素为 $A$ 的对角元素，$L$ 与 $U$ 为 $A$ 的下三角阵取反和上三角阵取反：$$L=-\left[\begin{array}{cccc}0& & & \\ a_{2,1}& 0& & \\ ⋮& \ddots & \ddots & \\ a_{n,1}& \cdots & a_{n,n-1}& 0\end{array}\right]$$$$U=-\left[\begin{array}{cccc}0& a_{1,2}& \cdots & a_{1,n}\\ & 0& \ddots & ⋮\\ & & \ddots & a_{n-1,n}\\ & & & 0\end{array}\right]$$
• 于是 $Ax=b$ 转化为 $$x=D^{-1}(L+U)x+D^{-1}b$$
• 与之对应的迭代公式为 $$x^{k+1}=D^{-1}(L+U)x^k+D^{-1}b$$
• 这就是 Jacobi 迭代公式。如果序列 $\left\{x^{k+1}\right\}$ 收敛于 $x$，则 $x$ 必是方程 $Ax=b$ 的解。
• Jacobi 迭代法的 MATLAB 函数文件 jacobi.m 如下：

function [y,n]=jacobi(A,b,x0,ep)
if nargin==3
    ep=1.0e-6;
elseif nargin<3
    error
    return
end
D=diag(diag(A));    %求A的对角矩阵
L=-tril(A,-1);      %求A的下三角阵
U=-triu(A,1);       %求A的上三角阵
B=D(L+U);
f=D;
y=B*x0+f;
n=1;                %迭代次数
while norm(y-x0)>=ep
    x0=y;
    y=B*x0+f;
    n=n+1;
end

• 例如，我们用 Jacobi 迭代法求解下列线性方程组。设迭代初值为 0，迭代精度为 $10^{-6}$。$$\{\begin{array}{c}10x_1-x_2=9\\ -x_1+10x_2-2x_3=7\\ -2x_2+10x_3=6\end{array}$$
• 在程序中，我们调用函数文件 jacobi.m，程序如下：

>> A=[10,-1,0;-1,10,-2;0,-2,10];
>> b=[9,7,6]';
>> [x,n]=jacobi(A,b,[0,0,0]',1.0e-6)

• 程序运行结果如下：

x =

    0.9958
    0.9579
    0.7916


n =

    11

2.2 Gauss-Serdel 迭代法

• 在 Jacobi 迭代过程中，计算 $x_i^{(k+1)}$ 时，$x_1^{(k+1)},\dots ,x_{i-1}^{(k+1)}$ 已经得到，不必再用 $x_1^{(k)},\dots ,x_{i-1}^{(k)}$，即原来的迭代公式 $D{x}^{(k+1)}=(L+U)X^{(k)}+b$ 可以改进为 $D{x}^{(k+1)}=L^{(k+1)}+X^{(k)}+b$，于是得到 $$x^{(k+1)}=(D-L{)}^{-1}U{x}^{(k)}+(D-L{)}^{-1}b$$
• 该式即为 Gauss-Serdel 迭代公式。和 Jacobi 迭代公式相比，Gauss-Serdel 迭代用新分量代替旧分量，精度会高些。
• Gauss-Serdel 迭代法的 MATLAB 函数文件 gauseidel.m 如下：

function [y,n]=gauseidel(A,b,x0,ep)
if nargin==3
    ep=1.0e-6;
elseif nargin<3
    error
    return
end
D=diag(diag(A));    %求A的对角矩阵
L=-tril(A,-1);      %求A的下三角阵
U=-triu(A,1);       %求A的上三角阵
G=(D-L)U;
f=(D-L);
y=G*x0+f;
n=1;                %迭代次数
while norm(y-x0)>=ep
    x0=y;
    y=G*x0+f;
    n=n+1;
end

• 例如，我们用 Gauss-Serdel 迭代法求解下列线性方程组。设迭代初值为 0，迭代精度为 $10^{-6}$。$$\{\begin{array}{c}10x_1-x_2=9\\ -x_1+10x_2-2x_3=7\\ -2x_2+10x_3=6\end{array}$$
• 在程序中，我们调用函数文件 gauseidel.m，程序如下：

>> A=[10,-1,0;-1,10,-2;0,-2,10];
>> b=[9,7,6]';
>> [x,n]=gauseidel(A,b,[0,0,0]',1.0e-6)

• 程序运行结果如下：

x =

    0.9958
    0.9579
    0.7916


n =

     7
     

• 由此可见，一般情况下 Gauss-Serdel 迭代比 Jacobi 迭代要收敛快一些。但这也是不绝对的，在某些情况下，Jacobi 迭代收敛而 Gauss-Serdel 迭代却可能不收敛。
• 例如，我们分别用 Jacobi 迭代和 Gauss-Serdel 迭代法求解下列线性方程组，看是否收敛。$$\left[\begin{array}{ccc}1& 2& -2\\ 1& 1& 1\\ 1& 2& 1\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}9\\ 7\\ 6\end{array}\right]$$
• 程序如下：

>> a=[1,2,-2;1,1,1;2,2,1];
>> b=[9;7;6];
>> [x,n]=jacobi(a,b,[0;0;0])

x =

   -27
    26
     8


n =

     4

>> [x,n]=gauseidel(a,b,[0;0;0])

x =

   NaN
   NaN
   NaN


n =

        1012

• 可见对此方程，用 Jacobi 迭代收敛，而 Gauss-Serdel 迭代不收敛。因此，在使用迭代法时，要考虑算法的收敛性。

3. 求线性方程的通解

• 线性方程组的求解分为两类：一类是求方程组的唯一解（即特解），另一类是求方程组的无穷解（即通解）。这里对线性方程组 $Ax=b$ 的求解理论进行归纳。
• （1） 当系数矩阵 $A$ 是一个满秩方阵时，方程 $Ax=b$ 称为恰定方程，方程有唯一 解 $x=A^{-1}b$，这是最基本的一种情况。一般用 $x=A\setminus b$ 求解速度更快。
• （2） 当方程组右端向量 $b=0$ 时，方程称为齐次方程组。齐次方程组总有零解，因此称解 $x=0$ 为平凡解。当系数矩阵 $A$ 的秩小于 $n$（$n$ 为方程组中未知变量的个数）时，齐次方程组有无穷多个非平凡解，其通解中包含 $n$-rank(4) 个线性无关的解向量，用 MATLAB 的函数 null(A,'r') 可求得基础解系。
• （3） 当方程组右端向量 $b\ne 0$ 时，系数矩阵的秩 rank(4) 与其增广矩阵的秩 rank([A,b]) 是判断其是否有解的基本条件。
• ① 当 rank<(A)=rank([4,b])=n 时，方程组有唯一解：$xr=A\setminus b$ 或 $x=pinv(A)\ast b$。
• ② 当 rank(4)=rank([A,b])<n 时，方程组有无穷多个解，其通解 = 方程组的一个特解 + 对应的齐次方程组 $Ax=0$ 的通解。可以用 $A\setminus b$ 求得方程组的一个特解，用 null(A,'r') 求得该方程组所对应的齐次方程组的基础解系，基础解系中包含 $n$-rank(4) 个线性无关的解向量。
• ③ 当 rank(A)<rank([A,b]) 时，方程组无解。
• 下面，我们写一个求解线性方程组的函数文件 line_solution.m。

function [x,y]=line_solution(A,b)
[m,n]=size(A) ;
y=[];
if norm(b)>0    %非齐次方程组
    if rank(A)==rank([A,b])
        if rank(A)==n   %有唯一解
            disp('原方程组有唯一解x');
            x=A; 
        else    %方程组有无穷多个解，基础解系
            disp('原方程组有无穷个解，特解为x,其齐次方程组的基础解系为y');
            x=A; 
            y=null(A,'r');
        end
    else
        disp('方程组无解');  %方程组无解
        x=[];
    end
else        %齐次方程组
    disp('原方程组有零解x') ;
    x=zeros(n,1);   %0解
    if rank(A)<n
        disp('方程组有无穷个解，基础解系为y');    %非0解
        y=null(A,'r');
    end
end

• 例如，我们求解方程组。$$\{\begin{array}{c}{x}_1-2x_2+3x_3-x_4=1\\ 3x_1-x_2+5x_3-3x_4=2\\ 2x_1+x_2+2x_3-2x_4=3\end{array}$$
• 程序如下：

>> A=[1,-2,3,-1;3,-1,5,-3;2,1,2,-2];
>> b=[1;2;3];
>> [x,y]=line_solution(A,b)

• 程序运行结果如下：

方程组无解

x =

     []


y =

     []
     

• 表明该方程无解。
• 例如，我们求方程组的通解。$$\{\begin{array}{c}{x}_1+x_2-3x_3-x_4=1\\ 3x_1-x_2-3x_3+4x_4=4\\ x_1+5x_2-9x_3-8x_4=0\end{array}$$
• 程序如下：

>> format rat	%指定有理式格式输出
>> A=[1,1,-3,-1;3,-1,-3,4;1,5,-9,-8];
>> b=[1;4;0];
>> [x,y]=line_solution(A,b)
>> x,y
>> format short	%恢复默认的短格式输出

• 程序运行结果如下：

警告: 秩亏，秩 = 2，tol =  8.837264e-15。 
> 位置：line_solution (第 11 行)

x =

       0       
       0       
      -8/15    
       3/5     


y =

       3/2           -3/4     
       3/2            7/4     
       1              0       
       0              1       

• 所以原方程的通解为 $$X=k_1\left[\begin{array}{c}3/2\\ 3/2\\ 1\\ 0\end{array}\right]+k_2\left[\begin{array}{c}-3/4\\ 7/4\\ 0\\ 1\end{array}\right]+\left[\begin{array}{c}0\\ 0\\ -8/15\\ 3/5\end{array}\right]$$
• 其中，$k_1、k_2$ 为任意常数。