7.10 Row-Based Algorithms
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.
|
| M : (Matrix Number) |
| jordan? : Any = #f |
| unitize-pivot? : Any = #f |
| pivoting : (U 'first 'partial) = 'partial |
Examples: |
| > (define M (matrix [[2 1 -1] [-3 -1 2] [-2 1 2]])) | | | > (matrix-row-echelon M) | eval:79:0: Type Checker: missing type for top-level | identifier; | either undefined or missing a type annotation | identifier: M10 | in: M | | > (matrix-row-echelon M #t) | eval:80:0: Type Checker: missing type for top-level | identifier; | either undefined or missing a type annotation | identifier: M10 | in: #t | | > (matrix-identity? (matrix-row-echelon M #t #t)) | eval:81:0: Type Checker: missing type for top-level | identifier; | either undefined or missing a type annotation | identifier: M10 | in: #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))) |
eval:83:0: Type Checker: missing type for top-level identifier; | either undefined or missing a type annotation | identifier: M10 | in: B | context...: | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/utils/tc-utils.rkt:123:0: report-all-errors | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typecheck/tc-toplevel.rkt:515:0: tc-toplevel-form | fail-to-succeed | fail-to-succeed | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/tc-setup.rkt:39:0: tc-setup | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typed-racket.rkt:24:4 | /Users/mflatt/build/macro/racket/collects/racket/private/more-scheme.rkt:148:2: call-with-break-parameterization | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/sandbox-lib/racket/sandbox.rkt:837:5: loop | eval:83:0: Type Checker: missing type for top-level identifier; | either undefined or missing a type annotation | identifier: B11 | in: B | context...: | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/utils/tc-utils.rkt:123:0: report-all-errors | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typecheck/tc-toplevel.rkt:515:0: tc-toplevel-form | fail-to-succeed | fail-to-succeed | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/tc-setup.rkt:39:0: tc-setup | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typed-racket.rkt:24:4 | /Users/mflatt/build/macro/racket/collects/racket/private/more-scheme.rkt:148:2: call-with-break-parameterization | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/sandbox-lib/racket/sandbox.rkt:837:5: loop |
|
Type Checker: Summary: 2 errors encountered |
| > (matrix-col (matrix-row-echelon MB #t #t) 3) |
eval:84:0: Type Checker: missing type for top-level |
identifier; |
either undefined or missing a type annotation |
identifier: MB |
in: 3 |
| > (matrix-solve M B) |
eval:85:0: Type Checker: missing type for top-level identifier; | either undefined or missing a type annotation | identifier: M10 | in: B | context...: | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/utils/tc-utils.rkt:123:0: report-all-errors | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typecheck/tc-toplevel.rkt:515:0: tc-toplevel-form | fail-to-succeed | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/tc-setup.rkt:39:0: tc-setup | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typed-racket.rkt:24:4 | /Users/mflatt/build/macro/racket/collects/racket/private/more-scheme.rkt:148:2: call-with-break-parameterization | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/sandbox-lib/racket/sandbox.rkt:837:5: loop | eval:85:0: Type Checker: missing type for top-level identifier; | either undefined or missing a type annotation | identifier: B11 | in: B | context...: | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/utils/tc-utils.rkt:123:0: report-all-errors | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typecheck/tc-toplevel.rkt:515:0: tc-toplevel-form | fail-to-succeed | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/tc-setup.rkt:39:0: tc-setup | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typed-racket.rkt:24:4 | /Users/mflatt/build/macro/racket/collects/racket/private/more-scheme.rkt:148:2: call-with-break-parameterization | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/sandbox-lib/racket/sandbox.rkt:837:5: loop |
|
Type Checker: Summary: 2 errors encountered |
| > (define MI (matrix-augment (list M (identity-matrix 3)))) |
eval:86:0: Type Checker: missing type for top-level |
identifier; |
either undefined or missing a type annotation |
identifier: M10 |
in: 3 |
| > (submatrix (matrix-row-echelon MI #t #t) (::) (:: 3 #f)) |
eval:87:0: Type Checker: missing type for top-level |
identifier; |
either undefined or missing a type annotation |
identifier: MI |
in: #f |
| > (matrix-inverse M) |
eval:88:0: Type Checker: missing type for top-level |
identifier; |
either undefined or missing a type annotation |
identifier: M10 |
in: M |
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: |
| | | > (values L U) | eval:90:0: Type Checker: missing type for top-level identifier; | either undefined or missing a type annotation | identifier: L14 | in: U | context...: | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/utils/tc-utils.rkt:123:0: report-all-errors | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typecheck/tc-toplevel.rkt:515:0: tc-toplevel-form | fail-to-succeed | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/tc-setup.rkt:39:0: tc-setup | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typed-racket.rkt:24:4 | /Users/mflatt/build/macro/racket/collects/racket/private/more-scheme.rkt:148:2: call-with-break-parameterization | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/sandbox-lib/racket/sandbox.rkt:837:5: loop | eval:90:0: Type Checker: missing type for top-level identifier; | either undefined or missing a type annotation | identifier: U15 | in: U | context...: | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/utils/tc-utils.rkt:123:0: report-all-errors | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typecheck/tc-toplevel.rkt:515:0: tc-toplevel-form | fail-to-succeed | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/tc-setup.rkt:39:0: tc-setup | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typed-racket.rkt:24:4 | /Users/mflatt/build/macro/racket/collects/racket/private/more-scheme.rkt:148:2: call-with-break-parameterization | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/sandbox-lib/racket/sandbox.rkt:837:5: loop |
| Type Checker: Summary: 2 errors encountered | | > (matrix* L U) | eval:91:0: Type Checker: missing type for top-level identifier; | either undefined or missing a type annotation | identifier: L14 | in: U | context...: | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/utils/tc-utils.rkt:123:0: report-all-errors | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typecheck/tc-toplevel.rkt:515:0: tc-toplevel-form | fail-to-succeed | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/tc-setup.rkt:39:0: tc-setup | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typed-racket.rkt:24:4 | /Users/mflatt/build/macro/racket/collects/racket/private/more-scheme.rkt:148:2: call-with-break-parameterization | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/sandbox-lib/racket/sandbox.rkt:837:5: loop | eval:91:0: Type Checker: missing type for top-level identifier; | either undefined or missing a type annotation | identifier: U15 | in: U | context...: | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/utils/tc-utils.rkt:123:0: report-all-errors | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typecheck/tc-toplevel.rkt:515:0: tc-toplevel-form | fail-to-succeed | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/tc-setup.rkt:39:0: tc-setup | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typed-racket.rkt:24:4 | /Users/mflatt/build/macro/racket/collects/racket/private/more-scheme.rkt:148:2: call-with-break-parameterization | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/sandbox-lib/racket/sandbox.rkt:837:5: loop | eval:91:0: Type Checker: type mismatch | expected: Number | given: Any | in: U | context...: | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/utils/tc-utils.rkt:133:21: for-loop | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/utils/tc-utils.rkt:123:0: report-all-errors | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typecheck/tc-toplevel.rkt:515:0: tc-toplevel-form | fail-to-succeed | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/tc-setup.rkt:39:0: tc-setup | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typed-racket.rkt:24:4 | /Users/mflatt/build/macro/racket/collects/racket/private/more-scheme.rkt:148:2: call-with-break-parameterization | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/sandbox-lib/racket/sandbox.rkt:837:5: loop | eval:91:0: Type Checker: type mismatch | expected: Number | given: Any | in: U | context...: | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/utils/tc-utils.rkt:133:21: for-loop | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/utils/tc-utils.rkt:123:0: report-all-errors | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typecheck/tc-toplevel.rkt:515:0: tc-toplevel-form | fail-to-succeed | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/tc-setup.rkt:39:0: tc-setup | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/typed-racket-lib/typed-racket/typed-racket.rkt:24:4 | /Users/mflatt/build/macro/racket/collects/racket/private/more-scheme.rkt:148:2: call-with-break-parameterization | /Users/mflatt/build/macro/build/user/6.2.900.4/pkgs/sandbox-lib/racket/sandbox.rkt:837:5: loop |
| Type Checker: Summary: 4 errors encountered |
|
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]]) |
|