Number format
Solution comments
Without description (answer only)
a
b
c
d
x
y
z
clear
i
Randomize
3131313131351515151515≈83137
How to compute QR decomposition by Householder reflections
Construct reflectors that zero out subdiagonal entries column by column. Each reflector is determined by the column vector being reduced; the product of the reflectors gives Q (orthogonal), and the reflected matrix is R (upper triangular).
Householder reflections — worked example (2×2)
Write the initial matrix
A
:
A
=
3
4
1
2
QR
decomposition is a representation of the matrix
A
in the form:
A
=
Q
*
R
;
Matrix
Q
is an orthonormal matrix;
Matrix
R
is an upper triangular matrix;
To perform
QR
decomposition using the Householder reflections method, need to do the following:
1)
Calculate the Householder reflection vector v for each column a of the matrix A2)
For each column a of the matrix A, we will calculate the Householder matrix H3)
After we apply the Householder transformation to all columns of matrix A, the resulting transformed matrix A' will be the upper triangular matrix R4)
The orthogonal matrix Q is obtained by multiplying all the Householder matrices HTo perform
QR
decomposition using the Householder reflection method, need to do the following for each column
a
of the matrix
A
:
1)
Compute the norm ‖a‖ of the column a2)
Define the sign(s) of column as
= -
sgn
(
a
[
i
])
;
// where
sgn(a)
= 1 if a[i] ≥ 0, and -1 otherwisea[i]
is the i-th element of column ai
is the column number3)
Calculate the Householder reflection vectorv
=
a
-
s
*
a
*
e
0
i
;
// where
eᵢ
is the standard basis vector where i-th element is 1 and all other elements are 0i
is the column number4)
Normalize the Householder reflection vectorv_norm
=
v
v
;
5)
Calculate the Householder matrixH
0
i
=
I
- 2 *
v_norm
*
v_norm
T
0
;
6)
Apply the Householder transformation to the matrixA'
0
i
=
H
0
i
*
A'
0
i - 1
;
7)
Calculate the matrixQ
0
i
=
Q
0
i - 1
*
H
0
i
;
2
Iteration 1At the first iteration, the matrix
A'
0
0
is equal to the original matrix
A
:
A'
0
0
=
3
4
1
2
Write the initial matrix
Q
0
0
, which is equal to the identity matrix:
Q
0
0
=
1
0
0
1
The vector
a
is equal to the
1
-th column of the matrix
A'
0
0
:
a
=
3
4
Compute the norm
a
of the column
a
:
a
=
5
;
Define the sign(
s
) of column
a
:
s
= -
sgn
(
a
[
1
])
= -
sgn
-(
3
) = -(
1
) =
-1
;
Write the
1
-th standard basis vector:
e
0
1
=
1
0
Calculate the Householder reflection vector
:
v
=
a
-
s
*
a
*
e
0
1
=
3
4
-
-1
*
5
*
1
0
=
3
4
-
-5
0
=
8
4
;
Normalize the Householder reflection vector
:
v_norm
=
v
v
=
89
100
9
20
Calculate the Householder reflection vector
:
H
0
1
=
I
- 2 *
v_norm
*
v_norm
T
0
=
1
0
0
1
- 2 *
89
100
9
20
*
89
100
9
20
=
=
89
100
9
20
·
89
100
9
20
=
4
5
2
5
2
5
1
5
=
1
0
0
1
- 2 *
4
5
2
5
2
5
1
5
=
=
4
5
2
5
2
5
1
5
·
2
=
4
5
*
2
2
5
*
2
2
5
*
2
1
5
*
2
=
1
3
5
4
5
4
5
2
5
=
1
0
0
1
−
1
3
5
4
5
4
5
2
5
=
1
-
1
3
5
0
-
4
5
0
-
4
5
1
-
2
5
=
-
3
5
-
4
5
-
4
5
3
5
Apply the Householder transformation to the matrix
A'
0
1
:
A'
0
1
=
H
0
1
·
A'
0
0
=
-
3
5
-
4
5
-
4
5
3
5
·
3
4
1
2
=
-5
0
-2
1
5
2
5
Calculate the matrix
Q
0
1
:
Q
0
1
=
Q
0
0
·
H
0
1
=
1
0
0
1
·
-
3
5
-
4
5
-
4
5
3
5
=
-
3
5
-
4
5
-
4
5
3
5
3
Iteration 2The vector
a
is equal to the
2
-th column of the matrix
A'
0
1
:
a
=
0
2
5
Compute the norm
a
of the column
a
:
a
=
2
5
;
Define the sign(
s
) of column
a
:
s
= -
sgn
(
a
[
2
])
= -
sgn
-(
2
5
) = -(
1
) =
-1
;
Write the
2
-th standard basis vector:
e
0
2
=
0
1
Calculate the Householder reflection vector
:
v
=
a
-
s
*
a
*
e
0
2
=
0
2
5
-
-1
*
2
5
*
0
1
=
0
2
5
-
0
-
2
5
=
0
4
5
;
Normalize the Householder reflection vector
:
v_norm
=
v
v
=
0
1
Calculate the Householder reflection vector
:
H
0
2
=
I
- 2 *
v_norm
*
v_norm
T
0
=
1
0
0
1
- 2 *
0
1
*
0
1
=
=
0
1
·
0
1
=
0
0
0
1
=
1
0
0
1
- 2 *
0
0
0
1
=
=
0
0
0
1
·
2
=
0
*
2
0
*
2
0
*
2
1
*
2
=
0
0
0
2
=
1
0
0
1
−
0
0
0
2
=
1
-
0
0
-
0
0
-
0
1
-
2
=
1
0
0
-1
Apply the Householder transformation to the matrix
A'
0
2
:
A'
0
2
=
H
0
2
·
A'
0
1
=
1
0
0
-1
·
-5
0
-2
1
5
2
5
=
-5
0
-2
1
5
-
2
5
Calculate the matrix
Q
0
2
:
Q
0
2
=
Q
0
1
·
H
0
2
=
-
3
5
-
4
5
-
4
5
3
5
·
1
0
0
-1
=
-
3
5
-
4
5
4
5
-
3
5
4
Matrix Q, RQ
=
Q
0
2
=
-
3
5
-
4
5
4
5
-
3
5
R
=
A'
0
2
=
-5
0
-2
1
5
-
2
5
Answer
A = Q · RQ
=
-
3
5
-
4
5
4
5
-
3
5
R
=
-5
0
-2
1
5
-
2
5
SIZE2×2METHODHouseholder reflections