Previous Page Next Page Contents

linalg::matlinsolve -- solving systems of linear equations

Introduction

linalg::matlinsolve(A, b) computes the general solution of the equation A*x = b.

Call(s)

linalg::matlinsolve(A, b)
linalg::matlinsolve(A, b, list)
linalg::matlinsolve(A, b <, Special> <, Unique>)
linalg::matlinsolve(A, B)
linalg::matlinsolve(A)

Parameters

A - an m x n matrix of a domain of category Cat::Matrix
B - an m x k matrix of a domain of category Cat::Matrix
b - an m-dimensional column vector, i.e., a m x 1 matrix of a domain of category Cat::Matrix
list - a list of n elements of the component ring of A

Options

Special - Computes one particular solution of the system A*x = 0.
Unique - Checks whether the system has a unique solution and returns the solution, or the value NIL otherwise.

Returns

a vector, a list [s, kern] (possibly empty), where s is a solution vector and kern is a list of basis vectors for the kernel of A, a matrix, or the value NIL.

The matrix and the vectors, respectively, are of the domain type Dom::Matrix(R), where R is the component ring of A.

Related Functions

linsolve, linalg::expr2Matrix, linalg::nullspace, linalg::matlinsolveLU, linalg::wiedemann, numeric::matlinsolve

Details

Option: Special

Option: Unique

Example 1

We solve the linear system:

+-       -+       +-    -+
|   1, 2  |       |   1  |
|         | * x = |      |
|  -1, 2  |       |  -1  |
+-       -+       +-    -+

over the reals. First we enter the coefficient matrix and the right-hand side:

>> MatR := Dom::Matrix(Dom::Real):
   A := MatR([[1, 2], [-1, 2]]); b := MatR([1, -1])
                                +-       -+
                                |   1, 2  |
                                |         |
                                |  -1, 2  |
                                +-       -+
      
                                 +-    -+
                                 |   1  |
                                 |      |
                                 |  -1  |
                                 +-    -+

Next we call linalg::matlinsolve to solve the system:

>> x := linalg::matlinsolve(A, b)
                                  +-   -+
                                  |  1  |
                                  |     |
                                  |  0  |
                                  +-   -+

We see that the system has exactly one solution. The vector x satisfies the matrix equation given above:

>> A * x 
                                 +-    -+
                                 |   1  |
                                 |      |
                                 |  -1  |
                                 +-    -+

Example 2

The system:

+-        -+       +-   -+
|   1,  2  |       |  1  |
|          | * x = |     |
|  -1, -2  |       |  0  |
+-        -+       +-   -+

does not have a solution over R (in fact, over no component domain):

>> A := MatR([[1, 2], [-1, -2]]): b := MatR([1, 0]):
   linalg::matlinsolve(A, b)
                                    []

Example 3

We solve the linear system:

+-                  -+       +-    -+
|  1, 1, -4, -7, -6  |       |  30  |
|                    | * x = |      |
|  0, 1, -3, -5, -7  |       |  70  |
+-                  -+       +-    -+

over the rational numbers. First we enter the coefficient matrix and the right-hand side:

>> MatQ := Dom::Matrix(Dom::Rational):
   A := MatQ([[1, 1, -4, -7, -6], [0, 1, -3, -5, -7]]); 
   b := MatQ([30, 17])
                          +-                  -+
                          |  1, 1, -4, -7, -6  |
                          |                    |
                          |  0, 1, -3, -5, -7  |
                          +-                  -+
      
                                 +-    -+
                                 |  30  |
                                 |      |
                                 |  17  |
                                 +-    -+

Next we call linalg::matlinsolve to solve the system:

>> sol:= linalg::matlinsolve(A, b)
             -- +-    -+  -- +-   -+  +-   -+  +-    -+ -- --
             |  |  13  |  |  |  1  |  |  2  |  |  -1  |  |  |
             |  |      |  |  |     |  |     |  |      |  |  |
             |  |  17  |  |  |  3  |  |  5  |  |   7  |  |  |
             |  |      |  |  |     |  |     |  |      |  |  |
             |  |   0  |, |  |  1  |, |  0  |, |   0  |  |  |
             |  |      |  |  |     |  |     |  |      |  |  |
             |  |   0  |  |  |  0  |  |  1  |  |   0  |  |  |
             |  |      |  |  |     |  |     |  |      |  |  |
             |  |   0  |  |  |  0  |  |  0  |  |   1  |  |  |
             -- +-    -+  -- +-   -+  +-   -+  +-    -+ -- --

The result is to be interpreted as follows: The first vector of the list sol is a particular solution of the linear system:

>> A * sol[1]
                                 +-    -+
                                 |  30  |
                                 |      |
                                 |  17  |
                                 +-    -+

The second entry of the list contains a basis for the null space of A, i.e., the solution space of the corresponding homogenous system A * x = 0 (the kernel of A). The basis returned is given as a list of vectors.

The following input checks this fact by computing the product A * x for each vector x of the list sol[2]:

>> map(sol[2], x -> A * x)
                      -- +-   -+  +-   -+  +-   -+ --
                      |  |  0  |  |  0  |  |  0  |  |
                      |  |     |, |     |, |     |  |
                      |  |  0  |  |  0  |  |  0  |  |
                      -- +-   -+  +-   -+  +-   -+ --

Any solution of the linear system can be represented as a sum of a particular solution (here: sol[1]) and a linear combination of the basis vectors of the kernel of A. Hence our input system has an infinite number of solutions.

For example, another solution of the system is given by:

>> x := sol[1] + 1*sol[2][1] + 1/2*sol[2][2] - 2*sol[2][3]
                                +-      -+
                                |   17   |
                                |        |
                                |  17/2  |
                                |        |
                                |    1   |
                                |        |
                                |   1/2  |
                                |        |
                                |   -2   |
                                +-      -+
>> A * x
                                 +-    -+
                                 |  30  |
                                 |      |
                                 |  17  |
                                 +-    -+

If we identify the columns of the coefficient matrix A of our linear system with the variables x1,x2,x3,x4,x5, then we see from the general solution that the variables x3,x4,x5 act as free parameters. They can be assigned arbitrary rational values to obtain a unique solution.

By giving a list of values for these variables as a third parameter to linalg::matlinsolve, we can select a certain vector from the set of all solutions of the linear system. For example, to select the same vector x as chosen in the previous input, we enter:

>> linalg::matlinsolve(A, b, [0, 0, 1, 1/2, -2])
                                +-      -+
                                |   17   |
                                |        |
                                |  17/2  |
                                |        |
                                |    1   |
                                |        |
                                |   1/2  |
                                |        |
                                |   -2   |
                                +-      -+

If one is only interested in a particular solution and does not need the general solution of the linear system, one may enter:

>> linalg::matlinsolve(A, b, Special)
                                 +-    -+
                                 |  13  |
                                 |      |
                                 |  17  |
                                 |      |
                                 |   0  |
                                 |      |
                                 |   0  |
                                 |      |
                                 |   0  |
                                 +-    -+

This call suppresses the computation of the kernel of A.

Example 4

If the linear system is given in form of equations the function linalg::expr2Matrix can be used to form the corresponding matrix equation:

>> delete x, y, z:
   Ab := linalg::expr2Matrix(
     [x + y + z = 6, 2*x + y + 2*z = 10, x + 3*y + z = 10]
   )
                             +-             -+
                             |  1, 1, 1,  6  |
                             |               |
                             |  2, 1, 2, 10  |
                             |               |
                             |  1, 3, 1, 10  |
                             +-             -+

The result here is the extended coefficient matrix of the input system, i.e., the right-hand side vector b is the 4th column vector of the matrix Ab. Since we did not specify a component ring for this matrix, the standard component ring for matrices, the domain Dom::ExpressionField(), was chosen.

To solve the linear system, we call:

>> linalg::matlinsolve(Ab)
                       -- +-   -+  -- +-    -+ -- --
                       |  |  4  |  |  |  -1  |  |  |
                       |  |     |  |  |      |  |  |
                       |  |  2  |, |  |   0  |  |  |
                       |  |     |  |  |      |  |  |
                       |  |  0  |  |  |   1  |  |  |
                       -- +-   -+  -- +-    -+ -- --

We see that the system has an infinite number of solutions. The third variable z acts as a free parameter and therefore can have any (complex) value.

To get the general solution in parameter form, one may use parameters for the variables x, y, z of the input system:

>> delete u, v, w:
   sol := linalg::matlinsolve(Ab, [u, v, w])
                               +-         -+
                               |  - w + 4  |
                               |           |
                               |     2     |
                               |           |
                               |     w     |
                               +-         -+

This is possible here because we perform the matrix computations over Dom::ExpressionField() which allows to compute with symbolical (arithmetical) expressions.

To select a certain vector from the set of solutions, for example, the solution for w=1, we enter:

>> x := subs(sol, w = 1)
                                  +-   -+
                                  |  3  |
                                  |     |
                                  |  2  |
                                  |     |
                                  |  1  |
                                  +-   -+

Example 5

Suppose that we have a system of linear equations with a sparse structure, i.e., with a coefficient matrix having many zero components. For example:

>> eqs := {x1 + x5 = 0, x2 - x4 = 1, x3 + 2*x5 = 2, x4 - x5 = -1}:
   Ab := linalg::expr2Matrix(eqs)
                         +-                     -+
                         |  0,  1, 0, -1, 0, -1  |
                         |                       |
                         |  1,  0, 0,  2, 0,  2  |
                         |                       |
                         |  0, -1, 1,  0, 0,  1  |
                         |                       |
                         |  0,  0, 0,  1, 1,  0  |
                         +-                     -+

As linalg::matlinsolve does not exploit the sparsity of the given coefficient matrix, we recommend not to solve the system with linalg::matlinsolve, but to use the function linsolve which directly works on the equations and therefore preserves the sparse structure of the input system:

>> linsolve(eqs)
            [x3 = 2 x1 + 2, x4 = - x1 - 1, x2 = -x1, x5 = -x1]

If a system is given in matrix form, we recommend to use the function numeric::matlinsolve with option Symbolic instead of linalg::matlinsolve even for exact computations. This function works more efficiently than linalg::matlinsolve and is able to exploit sparsity:

>> A := linalg::delCol(Ab, 5): b := linalg::col(Ab, 6):
   numeric::matlinsolve(A, b)
                       -- +-      -+  +-      -+ --
                       |  |   2.0  |  |  -2.0  |  |
                       |  |        |  |        |  |
                       |  |  -1.0  |  |   1.0  |  |
                       |  |        |  |        |  |
                       |  |    0   |, |    0   |  |
                       |  |        |  |        |  |
                       |  |    0   |  |    0   |  |
                       |  |        |  |        |  |
                       |  |    0   |  |    1   |  |
                       -- +-      -+  +-      -+ --

Note that the function numeric::matlinsolve always works over a subfield of the complex numbers and does not allow to specify the domain of computation. Without the option Symbolic numeric::matlinsolve converts input data to floating point numbers.

Example 6

Let us check whether the matrix equation

+-       -+       +-      -+
|   1, 2  |       |  4, 2  |
|         | * X = |        |
|  -2, 3  |       |  6, 3  |
+-       -+       +-      -+

has a unique solution over the integers.

We start by entering the coefficient matrix and the right-hand side matrix:

>> MatZ := Dom::Matrix(Dom::Integer):
   A := MatZ([[1, 2], [-2, 3]]); B := MatZ([[4, 2], [6, 3]])
                                +-       -+
                                |   1, 2  |
                                |         |
                                |  -2, 3  |
                                +-       -+
      
                                +-      -+
                                |  4, 2  |
                                |        |
                                |  6, 3  |
                                +-      -+

Next we solve the matrix equation:

>> X := linalg::matlinsolve(A, B)
                                +-      -+
                                |  0, 0  |
                                |        |
                                |  2, 1  |
                                +-      -+

The equation indeed has a unique solution (otherwise the answer of linalg::matlinsolve would be the empty list []). Let us check the result:

>> A * X
                                +-      -+
                                |  4, 2  |
                                |        |
                                |  6, 3  |
                                +-      -+

Background

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000