用稀疏矩阵解决联立方程组

森之张卫东

用稀疏矩阵解决联立方程组

为了解说明稀疏矩阵在MATLAB中应用，我们将用全矩阵和稀疏矩阵来解决下面的联立方程组。

1.0x1 + 0.0x2 + 1.0x3+ 0.0x4 + 0.0x5 + 2.0x6 + 0.0x7- 1.0x8 = 3.0

0.0x1 + 1.0x2 + 0.0x3+ 0.4x4 + 0.0x5 + 0.0x6 + 0.0x7+ 0.0x8 = 2.0

0.5x1 + 0.0x2 + 2.0x3+ 0.0x4 + 0.0x5 + 0.0x6 - 1.0x7+ 0.0x8 = -1.5

0.0x1 + 0.0x2 + 0.0x3+ 2.0x4 + 0.0x5 + 1.0x6 + 0.0x7+ 0.0x8 = 1.0

0.0x1 + 0.0x2 + 1.0x3+ 1.0x4 + 1.0x5 + 0.0x6 + 0.0x7+ 0.0x8 = -2.0

0.0x1 + 0.0x2 + 0.0x3+ 1.0x4 + 0.0x5 + 1.0x6 + 0.0x7+ 0.0x8 = 1.0

0.5x1 + 0.0x2 + 0.0x3+ 0.0x4 + 0.0x5 + 0.0x6 + 1.0x7+ 0.0x8 = 1.0

0.0x1 + 1.0x2 + 0.0x3+ 0.0x4 + 0.0x5 + 0.0x6 + 0.0x7+ 1.0x8 = 1.0

---

答案

为了解决这一问题，我们将创建一个方程系数的全矩阵，并用sparse函数把他转化为稀疏矩阵。我们用两种方法解这个方程组，比较它们的结果和所需的内存。

代码如下：

% Script file: simul.m

%

% Purpose:

% This program solves a system of 8 linear equations in 8

% unknowns (a*x = b), using both full and sparse matrices.

%

% Record of revisions:

% Date      Programmer      Description of change

% ====      ========      ===============

% 10/14/98  S. J. Chapman     Originalcode

%

% Define variables:

% a                --Coefficients of x (full matrix)

% as               --Coefficients of x (sparse matrix)

% b                 --Constantcoefficients (full matrix)

% bs                --Constantcoefficients (sparse matrix)

% x                 --Solution(full matrix)

% xs                --Solution(sparse matrix)

% Define coefficients of the equation a*x = b for

% the full matrix solution.

a = [

1.0 0.0 1.0 0.0 0.0 2.0 0.0 -1.0; ...

0.0 1.0 0.0 0.4 0.0 0.0 0.0 0.0; ...

0.5 0.0 2.0 0.0 0.0 0.0 -1.0 0.0; ...

0.0 0.0 0.0 2.0 0.0 1.0 0.0 0.0; ...

0.0 0.0 1.0 1.0 1.0 0.0 0.0 0.0; ...

0.0 0.0 0.0 1.0 0.0 1.0 0.0 0.0; ...

0.5 0.0 0.0 0.0 0.0 0.0 1.0 0.0; ...

0.0 1.0 0.0 0.0 0.0 0.0 0.0 1.0

];

b = [ 3.0 2.0 -1.5 1.0 -2.0 1.0 1.0 1.0]';

% Define coefficients of the equation a*x = b for

% the sparse matrix solution.

as = sparse(a);

bs = sparse(b);

% Solve the system both ways

disp ('Full matrix solution:');

x = a\b

disp ('Sparse matrix solution:');

xs = as\bs

% Show workspace

disp('Workspace contents after the solutions:')

whos

运行这个程序，结果如下

>> simul

Full matrix solution:

x =

    0.5000

    2.0000

   -0.5000

   -0.0000

   -1.5000

    1.0000

    0.7500

   -1.0000

Sparse matrix solution:

xs =

   (1,1)       0.5000

   (2,1)       2.0000

   (3,1)      -0.5000

   (5,1)      -1.5000

   (6,1)       1.0000

   (7,1)       0.7500

   (8,1)      -1.0000

Workspace contents after the solutions:

  Name      Size                    Bytes  Class

  a         8x8                       512  double array

  as        8x8                       276  double array (sparse)

  b         8x1                        64  double array

  bs        8x1                       104  double array (sparse)

  x         8x1                        64  double array

  xs        8x1                        92  double array (sparse)

Grand total is 115 elements using 1112 bytes

两种算法得到了相同的答案。注意用稀疏矩阵产生的结果不包含x4，因为它的值为0。注意b的稀疏形式占的内存空间比全矩阵形式还要大。这种情况是因为稀疏矩阵除了元素值之外必须存储它的行号和列号，所以当一个矩阵的大部分元素都是非零元素，用稀疏矩阵将降低运算效率。