LU & QR Factorisation Flashcards
How does LU factorisation work?
Matrix A is expressed as matrices LU
If Matrix A is m x n
L is a lower-triangular matrix m x m (with 1s down leading diagonal)
U is an upper echelon matrix of shape m x n
(This means that the matricies are compatible to multiply and produce an m x n matrix)
Describe the L matrix
Lower triangular (zeros above leading diagonal) with ones along leading diagonal
Square, m x m matrix (where m is the number of rows in A)
Describe the U matrix
Upper-echelon matrix (zeros below leading diagonal)
Same shape as A (m x n)
How does basic LU factorisation work?
Extract the top row of matrix A, and write it along the top of the matrix. Down the left side of the matrix, write whatever factor you must use to make the leftmost digit in the extracted row equal to the leftmost digit in the row in question (for instance, if you extracted a 3 from the top row, and you have a 6 in the new row, your factor is 2). Then, multiply the whole row by this factor, and write this in a new matrix (som in the second row, following the earlier example, you would rewrite the extracted row, all multiplied by two). After this has been performed for each row, subtract from each row the extracted row multiplied by the relevant factor, and write the result as a new matrix, which can be added to the other matrix just made to produce the old one. This should give you a full matrix of scaled rows, plus another matrix with zeros in the first row and column. Then, repeat this process until the other matrix being added is just zeros.
To construct the L matrix, take each column of factors as a vector, and then stack them side by side to form the lower-triangular matrix.
To construct the U matrix, take each extracted row and stack them in order to form the upper-echelon matrix.
How could you use LU factorisation to find the solution x to the equation Ax = b?
Ax = (LU)x = L(Ux) = b
Find c from Lc = b then find x from Ux = c
Use substitution in both cases
Describe how partial pivoting works for LU factorisation
When extracting rows, the row to be extracted is now selected so as to avoid pivoting on a zero. To do this, the largest value in the column is selected as the pivot.
How does one create an equation in the form PA = LU from partial pivoting?
L•, a square matrix but not necessarily lower triangular, is formed as in the basic method be compiling the columns, and U is formed from the rows. However, we want to rearrange L• with P to form L, a lower triangular matrix. L = PL•, where P is also an m x m matrix of orthogonal unit vectors ([1 0 0] etc) which rearrange the rows of L. Since A = L•U, PL•U = LU = PA, giving us the form required.
What is the theory behind a A = QR factorisation?
An orthogonal set of vectors derived from the column space of A form matrix Q, and are then multiplied by factors in R (which is upper triangular, and thereby easier to solve).
Describe how the q vectors are selected and how they form the Q matrix in QR factorisation
The q vectors are an orthonormal set of vectors describing the column space of matrix A. They are of unit magnitude. The first one is formed by normalising column a1 of matrix A (a1/|a1| ). The second is formed by taking a2 and subtracting the portion parallel to a1, then normalising (a2’ = a2 - (q1.a2)q1 a’2/(|a’2|) = q2
This process is repeated for a3 etc.
Once all q vectors are found, the are put side by side as columns to form the Q matrix.
Describe how the R matrix is formed in QR factorisation
The R matrix is an upper triangular matrix formed of factor that multiply with Q to make A. The terms are the dot product of the corresponding q and a columns (Q^t is effectively Q^-1). For instance, the first two rows will be: ([a1.q1 a2.q1 a3.q1…],[0 a2.q2 a3.q2…] etc)
How do you simplify the least squares solution to Ax=b with QR factorisation?
Short answer: R x = R t Q t b
AtAx=Atb
(QR)tQRx = (QR)tb
RtQtQRx = RtQtb
QtQ = I
RtRx = RtQtb
R and therefore Rt are infertile
Rx = Qtb
Qtb is trivial, and then Rx is solved by back substitution.