Matrix decomposition: Difference between revisions

Revision as of 06:04, 15 June 2023

Revision as of 14:02, 15 June 2023

Line 8:

For instance, when solving a [[system of linear equations]] <math>A \mathbf{x} = \mathbf{b}</math>, the matrix ''A'' can be decomposed via the [[LU decomposition]]. The LU decomposition factorizes a matrix into a [[lower triangular matrix]] ''L'' and an [[upper triangular matrix]] ''U''. The systems <math>L(U \mathbf{x}) = \mathbf{b}</math> and <math>U \mathbf{x} = L^{-1} \mathbf{b}</math> require fewer additions and multiplications to solve, compared with the original system <math>A \mathbf{x} = \mathbf{b}</math>, though one might require significantly more digits in inexact arithmetic such as [[floating point]].

Similarly, the [[QR decomposition]] expresses ''A'' as ''QR'' with ''Q'' as an [[orthogonal matrix]] and ''R as'' an upper triangular matrix. The system ''Q''(''R'''''x''') = '''b''' is solved by ''R'''''x''' = ''Q''^T'''b''' = '''c''', and the system ''R'''''x''' = '''c''' is solved by '[[Triangular matrix#Forward and back substitution|back substitution]]'. The number of additions and multiplications required is about twice that of using the LU solver, but no more digits are required in inexact arithmetic because the QR decomposition is [[numerically stable]].

== Decompositions related to solving systems of linear equations ==