QR decomposition with lower triangular matrix using Householder reflection

1.8k Views Asked by At

Problem

Find householder matrices $H_1,H_2,\cdots,H_n$ such that

$$ H_n\cdots H_1 A = L $$

where $A$ : $n \times n$ matrix and $L$ : $n \times n$ lower triangular matrix.


Try

By defining $v_k:= [\cdots, sgn(x_k) |x_k|, \cdots]$ and $H_k := I - 2v_kv_k^T/v_k^Tv_k$, we can make

$$ H_n\cdots H_1 A = U $$

where $U$ : $n \times n$ upper triangular matrix

But I'm currently stuck at how to define $v_k$ to make RHS lower triangular.

1

There are 1 best solutions below

6
On BEST ANSWER

Start from the last column, you are then in almost the same setting as for the $QR$ with upper $R$: you start with the column that will be transformed to a column with only zeros except for one coefficient (but it will be $\lambda e_n$ instead of $\lambda e_1$), and continue as usual.

Alternately, you can do that with the same algorithm as usual ($QR$ with upper $R$), by first reversing the order of the columns and rows of $A$, and doing the same afterwards on $Q$ and $R$. You can apply this to all Householder reflections, and you can check that a "reversed" reflection $H_k$ is still a Householder reflection with reversed $v_k$.

Note that if $f$ is the function that reverses the order of rows and columns, then $f(AB)=f(A)f(B)$. I don't know if it has a specific notation.