Student[NumericalAnalysis] - Maple Programming Help

Home : Support : Online Help : Education : Student Packages : Numerical Analysis : Computation : Student/NumericalAnalysis/MatrixDecomposition

Student[NumericalAnalysis]

 MatrixDecomposition
 factor a matrix

 Calling Sequence MatrixDecomposition(A, opts)

Parameters

 A - Matrix; a square $\mathrm{nxn}$ matrix opts - (optional) equation(s) of the form keyword=value, where keyword is one of digits, method, output, showsteps; the options for factoring the matrix A

Options

 • digits = posint
 The number of digits of precision in which the computations will be performed. By default, digits will be set to the environment variable Digits.
 • method = LU, PLU, LU[tridiagonal], PLU[scaled], LDU, LDLt, Cholesky
 The type of decomposition to perform.
 – method = LU produces a factorization $A=L·U$, where $L$ and $U$ are lower and upper triangular, respectively. It is also possible to obtain the Gaussian transformation matrices generated by this decomposition.
 – method = PLU produces a factorization $P·A=L·U$, where $L$ and $U$ are lower and upper triangular, respectively, and $P$ is the permutation matrix. It is also possible to obtain Gaussian transformation and permutation matrices generated by this decomposition.
 – method = LU[tridiagonal] produces the factorization $A=L·U$ using the Crout factorization algorithm for tridiagonal matrices, where $L$ and $U$ are lower and upper triangular, respectively. Note that the matrix A must be tridiagonal; an error will be raised otherwise.
 – method = PLU[scaled] produces a factorization $P·A=L·U$, where $L$ and $U$ are lower and upper triangular, respectively, and $P$ is the permutation matrix. This method uses scaled partial pivoting. It is also possible to obtain the Gaussian transformation and permutation matrices generated by this decomposition.
 – method = LDU produces the factorization $A=L·\mathrm{D}·U$, where $L$ is a unit lower-triangular matrix, $\mathrm{D}$ is a diagonal matrix, and $U$ is the a unit upper-triangular matrix.
 – method = LDLt produces, for a symmetric real matrix A (Hermitian complex matrix A) the factorization $A=L·\mathrm{D}·\mathrm{Lt}$, where $L$ is a unit lower-triangular matrix, $\mathrm{D}$ is a diagonal matrix, and $\mathrm{Lt}$ is the transpose (Hermitian, respectively) of $L$. Note that A must be symmetric (Hermitian, respectively); an error will be raised otherwise.
 – method = Cholesky produces, for a positive definite matrix A, the factorization $A=R·\mathrm{Rt}$, where $R$ is lower triangular and $\mathrm{Rt}$ is the transpose $R$. Note that A must be positive definite; an error will be raised otherwise.
 By default, method = PLU. See the output option below for a description of the possible return value(s) for each method.
 • output = list
 The return value for the function. L represents the lower-triangular matrix, U represents the upper-triangular matrix and D represents the diagonal matrix.
 – If method = LU then output can be one or more of L, U, Mmatrices, where output = Mmatrices returns a list of Gaussian transformation matrices. By default, output = [L, U].
 – If method = PLU then output can be one or more of P, L, U, Mmatrices, Ematrices, where output = Mmatrices returns a list of Gaussian transformation matrices and output = Ematrices returns a list of permutation matrices. By default, output = [P, L, U].
 – If method = LU[tridiagonal] then output can be one or more of L, U. By default, output = [L, U].
 – If method = PLU[scaled] then output can be one or more of P, L, U, Mmatrices, Ematrices, where output = Mmatrices returns a list of Gaussian transformation matrices and output = Ematrices returns a list of permutation matrices. By default, output = [P, L, U].
 – If method = LDU then output can be one or more of L, D, U. By default, output = [L, D, U].
 – If method = LDLt then output can be one or more of L, D, Lt, where output = Lt returns the unit upper-triangular matrix. By default, output = [L, D, Lt].
 – If method = Cholesky then output can be one or more of R, Rt, where output = R returns the lower-triangular matrix and output = Rt returns the transpose of the lower-triangular matrix. By default, output = [R, Rt].
 • showsteps = true or false
 Whether to print helpful statements into the interface as the command executes. This option is only available when output = LU, PLU or PLU[scaled]. By default, showsteps = false.

Description

 • Matrix decomposition is used to reduce the general linear system A.x=b to more manageable triangular systems.
 • The MatrixDecomposition command can perform the following decompositions: LU, PLU, LU Tridiagonal, PLU Scaled, LDU, LDLt and Cholesky.

Notes

 • Matrix decomposition is also sometimes referred to as matrix factorization. The terms are interchangeable.
 • When the method is set to either LU or LDU, this procedure operates symbolically; that is, the inputs are not automatically evaluated to floating-point quantities, and computations proceed symbolically and exactly whenever possible. To obtain floating-point results, it is necessary to supply floating-point inputs.
 • Otherwise, this procedure operates numerically; that is, if the inputs are not already numeric, they are first evaluated to floating-point quantities before computations proceed. The outputs will be numeric as well. Note that exact rationals are considered numeric and are preserved whenever possible throughout the computation; therefore, one must specify floating-point inputs instead of exact rationals to obtain floating-point outputs.

Examples

 > $\mathrm{with}\left(\mathrm{Student}:-\mathrm{NumericalAnalysis}\right):$
 > $A≔\mathrm{Matrix}\left(\left[\left[1.3,4.5,7.2\right],\left[4.3,5.6,8.7\right],\left[7.0,8.4,10.1\right]\right]\right)$
 ${A}{≔}\left[\begin{array}{ccc}{1.3}& {4.5}& {7.2}\\ {4.3}& {5.6}& {8.7}\\ {7.0}& {8.4}& {10.1}\end{array}\right]$ (1)

Try an LU decomposition

 > $L,U≔\mathrm{MatrixDecomposition}\left(A,\mathrm{method}=\mathrm{LU},\mathrm{output}=\left[L,U\right]\right)$
 ${L}{,}{U}{≔}\left[\begin{array}{ccc}{1}& {0}& {0}\\ {3.307692308}& {1}& {0}\\ {5.384615385}& {1.705053851}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{1.3}& {4.5}& {7.2}\\ {0}& {-9.28461539}& {-15.11538462}\\ {0}& {0}& {-2.89668601}\end{array}\right]$ (2)
 > $M≔\mathrm{MatrixDecomposition}\left(A,\mathrm{method}=\mathrm{LU},\mathrm{output}=\left[\mathrm{Mmatrices}\right]\right)$
 ${M}{≔}\left[\left[\begin{array}{ccc}{1}& {0}& {0}\\ {-3.307692308}& {1}& {0}\\ {-5.384615385}& {0}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {0}& {0}\\ {0}& {1}& {0}\\ {0}& {-1.705053851}& {1}\end{array}\right]\right]$ (3)

Check that ${M}_{2}·{M}_{1}·A=U$

 > $M\left[2\right]·M\left[1\right]·A-U$
 $\left[\begin{array}{ccc}{0.}& {0.}& {0.}\\ {-4.00000033096148}{}{{10}}^{{-10}}& {4.00000033096148}{}{{10}}^{{-9}}& {2.40000019857689}{}{{10}}^{{-9}}\\ {1.82021508976504}{}{{10}}^{{-10}}& {-1.35468471995637}{}{{10}}^{{-8}}& {-1.04149577850876}{}{{10}}^{{-8}}\end{array}\right]$ (4)
 > $A≔\mathrm{Matrix}\left(\left[\left[3.32,1.43,2.02,9.93\right],\left[2.43,1.54,2.54,1.53\right],\left[6.54,1.21,1.04,8.54\right],\left[-3.44,0.43,2.43,1.99\right]\right]\right)$
 ${A}{≔}\left[\begin{array}{cccc}{3.32}& {1.43}& {2.02}& {9.93}\\ {2.43}& {1.54}& {2.54}& {1.53}\\ {6.54}& {1.21}& {1.04}& {8.54}\\ {-3.44}& {0.43}& {2.43}& {1.99}\end{array}\right]$ (5)

Try a PLU decomposition

 > $P,L,U≔\mathrm{MatrixDecomposition}\left(A,\mathrm{method}=\mathrm{PLU}\right)$
 ${P}{,}{L}{,}{U}{≔}\left[\begin{array}{cccc}{0}& {0}& {1}& {0}\\ {0}& {1}& {0}& {0}\\ {0}& {0}& {0}& {1}\\ {1}& {0}& {0}& {0}\end{array}\right]{,}\left[\begin{array}{cccc}{1}& {0}& {0}& {0}\\ {0.3715596330}& {1}& {0}& {0}\\ {-0.5259938838}& {0.9780264465}& {1}& {0}\\ {0.5076452599}& {0.7481104427}& {-0.1367344232}& {1}\end{array}\right]{,}\left[\begin{array}{cccc}{6.54}& {1.21}& {1.04}& {8.54}\\ {0}& {1.090412844}& {2.153577982}& {-1.643119266}\\ {0}& {0}& {0.870777418}& {8.089001865}\\ {0}& {0}& {0}& {7.929989165}\end{array}\right]$ (6)
 > $P$
 $\left[\begin{array}{cccc}{0}& {0}& {1}& {0}\\ {0}& {1}& {0}& {0}\\ {0}& {0}& {0}& {1}\\ {1}& {0}& {0}& {0}\end{array}\right]$ (7)
 > $L$
 $\left[\begin{array}{cccc}{1}& {0}& {0}& {0}\\ {0.3715596330}& {1}& {0}& {0}\\ {-0.5259938838}& {0.9780264465}& {1}& {0}\\ {0.5076452599}& {0.7481104427}& {-0.1367344232}& {1}\end{array}\right]$ (8)
 > $U$
 $\left[\begin{array}{cccc}{6.54}& {1.21}& {1.04}& {8.54}\\ {0}& {1.090412844}& {2.153577982}& {-1.643119266}\\ {0}& {0}& {0.870777418}& {8.089001865}\\ {0}& {0}& {0}& {7.929989165}\end{array}\right]$ (9)

Perform a Cholesky decomposition

 > $A≔\mathrm{Matrix}\left(\left[\left[2,-1,0\right],\left[-1,2,-1\right],\left[0,-1,2\right]\right]\right)$
 ${A}{≔}\left[\begin{array}{ccc}{2}& {-1}& {0}\\ {-1}& {2}& {-1}\\ {0}& {-1}& {2}\end{array}\right]$ (10)

First check that A is positive definite

 > $\mathrm{IsMatrixShape}\left(A,\mathrm{positivedefinite}\right)$
 ${\mathrm{true}}$ (11)
 > $G,\mathrm{Gt}≔\mathrm{MatrixDecomposition}\left(A,\mathrm{method}=\mathrm{Cholesky}\right)$
 ${G}{,}{\mathrm{Gt}}{≔}\left[\begin{array}{ccc}\sqrt{{2}}& {0}& {0}\\ {-}\frac{\sqrt{{2}}}{{2}}& \frac{\sqrt{{6}}}{{2}}& {0}\\ {0}& {-}\frac{\sqrt{{6}}}{{3}}& \frac{{2}{}\sqrt{{3}}}{{3}}\end{array}\right]{,}\left[\begin{array}{ccc}\sqrt{{2}}& {-}\frac{\sqrt{{2}}}{{2}}& {0}\\ {0}& \frac{\sqrt{{6}}}{{2}}& {-}\frac{\sqrt{{6}}}{{3}}\\ {0}& {0}& \frac{{2}{}\sqrt{{3}}}{{3}}\end{array}\right]$ (12)