Matrix decomposition: Difference between revisions

Revision as of 22:10, 20 February 2025

Revision as of 22:14, 20 February 2025

Line 6:

In [[numerical analysis]], different decompositions are used to implement efficient matrix [[algorithm]]s.

For instanceexample, 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'' an [[orthogonal matrix]] and ''R'' 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]].