►Math Library
▼7 Matrices and Linear Algebra
On this page:
matrix-gauss-elim
matrix-row-echelon
matrix-lu
  top  ← prev  up  next → 

7.10 Row-Based Algorithms

procedure

(matrix-gauss-elim M 
  [jordan? 
  unitize-pivot? 
  pivoting]) 
 → (Values (Matrix Number) (Listof Index))
  M : (Matrix Number)
  jordan? : Any = #f
  unitize-pivot? : Any = #f
  pivoting : (U 'first 'partial) = 'partial
Wikipedia: Gaussian elimination, Gauss-Jordan elimination Implements Gaussian elimination or Gauss-Jordan elimination.

If jordan? is true, row operations are done both above and below the pivot. If unitize-pivot? is true, the pivot’s row is scaled so that the pivot value is 1. When both are true, the algorithm is called Gauss-Jordan elimination, and the result matrix is in reduced row echelon form.

If pivoting is 'first, the first nonzero entry in the current column is used as the pivot. If pivoting is 'partial, the largest-magnitude nonzero entry is used, which improves numerical stability on average when M contains inexact entries.

The first return value is the result of Gaussian elimination.

The second return value is a list of indexes of columns that did not have a nonzero pivot.

See matrix-row-echelon for examples.

procedure

(matrix-row-echelon M    
  [jordan?    
  unitize-pivot?    
  pivoting]) → (Matrix Number)
  M : (Matrix Number)
  jordan? : Any = #f
  unitize-pivot? : Any = #f
  pivoting : (U 'first 'partial) = 'partial
Wikipedia: Row echelon form Like matrix-gauss-elim, but returns only the result of Gaussian elimination.

Examples:

> (define M (matrix [[2 1 -1] [-3 -1 2] [-2 1 2]]))
> (matrix-row-echelon M)

- : (Array Real)

(mutable-array #[#[-3 -1 2] #[0 5/3 2/3] #[0 0 1/5]])

> (matrix-row-echelon M #t)

- : (Array Real)

(mutable-array #[#[-3 0 0] #[0 5/3 0] #[0 0 1/5]])

> (matrix-identity? (matrix-row-echelon M #t #t))

- : Boolean

#t

The last example shows that M is invertible.

Using matrix-row-echelon to solve a system of linear equations (without checking for failure):
> (define B (col-matrix [8 -11 -3]))
> (define MB (matrix-augment (list M B)))
> (matrix-col (matrix-row-echelon MB #t #t) 3)

- : (Array Real)

(array #[#[2] #[3] #[-1]])

> (matrix-solve M B)

- : (Array Real)

(array #[#[2] #[3] #[-1]])

Using matrix-row-echelon to invert a matrix (also without checking for failure):
> (define MI (matrix-augment (list M (identity-matrix 3))))
> (submatrix (matrix-row-echelon MI  #t #t) (::) (:: 3 #f))

- : (Array Real)

(array #[#[4 3 -1] #[-2 -2 1] #[5 4 -1]])

> (matrix-inverse M)

- : (Array Real)

(array #[#[4 3 -1] #[-2 -2 1] #[5 4 -1]])

procedure

(matrix-lu M [fail])

 → (Values (U F (Matrix Number)) (Matrix Number))
  M : (Matrix Number)
  fail : (-> F) = (λ () (error ...))
Wikipedia: LU decomposition Returns the LU decomposition of M (which must be a square-matrix?) if one exists. An LU decomposition exists if M can be put in row-echelon form without swapping rows.

Because matrix-lu returns a unit lower-triangular matrix (i.e. a lower-triangular matrix with only ones on the diagonal), the decomposition is unique if it exists.

Examples:

> (define-values (L U)
    (matrix-lu (matrix [[4 3] [6 3]])))
> (values L U)

- : (values (Array Real) (Array Real))

(mutable-array #[#[1 0] #[3/2 1]])

(mutable-array #[#[4 3] #[0 -3/2]])

> (matrix* L U)

- : #(struct:#<syntax:/home/ryan/projects/release/site/build/user/6.3/pkgs/math-lib/math/private/array/typed-array-struct.rkt:49:13 Array>

      (Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Real)))

(array #[#[4 3] #[6 3]])

If M does not have an LU decomposition, the first result is the result of applying the failure thunk fail, and the second result is the original argument M:
> (matrix-lu (matrix [[0 1] [1 1]]))

matrix-lu: contract violation

  expected: LU-decomposable matrix

  given: (array #[#[0 1] #[1 1]])

> (matrix-lu (matrix [[0 1] [1 1]]) (λ () #f))

- : (values (U False (Array Real)) (Array Real))

#f

(array #[#[0 1] #[1 1]])

  top  ← prev  up  next →