Solution comments
Without description (answer only)
a
b
c
d
x
y
z
AC
i
Randomize
Number format
3131313131351515151515≈52188552198585858586
Round to
Digits after decimal point
10
How to compute QR decomposition by Givens rotations
Apply a sequence of 2-by-2 plane rotations to zero out subdiagonal entries one at a time. Each Givens rotation is determined by the two entries it acts on. The cumulative product of rotations is Q, and the rotated matrix is R.
Givens rotations — worked example (3×3)
Write the initial matrix
A
:
A
=
1
1
0
1
0
1
0
1
1
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;
We can use Givens rotations to make all elements below the main diagonal of matrix
A
zero;
This method is iterative and in one iteration we will convert one element to zero;
At the last iteration, when all the elements below the main diagonal will be converted to zero, we will get the matrix
R
;
During calculation matrix
R
at each iteration, we will calculate matrix
G
to convert elements below the main diagonal to zero;
We can calculate matrix
Q
by multiplying all transposed matrices
G
;
We will zero the elements in order from top to bottom from left to right;
At each iteration we need to define the following variables:
a
is the element of matrix Aₖ₋₁, which is located on the main diagonal in the same column as the element that we want to turn to zeroa
=
a
0
k - 1
0
i,i
;
b
is the element of matrix Aₖ₋₁ that we want to turn to zerob
=
a
0
k - 1
0
j,i
;
// where
j
is the number of the row in which there is an element that we want to turn to zeroi
is the number of the column in which there is an element that we want to turn to zerok
is the iteration numberAₖ₋₁
is the matrix calculated on the previous iterationNext, we need to calculate the following values:
r
=
a
2
0
+
b
2
0
;
c
=
a
r
;
s
= -
b
r
;
Now we can construct the matrix
G
:
1)
The basis of the matrix G is a identity matrix of size n by n// where
n
is the number of rows of matrix A2)
Element under index [i,i] is equal to cg
0
i,i
=
c
;
3)
Element under index [j,j] is equal to cg
0
j,j
=
c
;
4)
Element under index [j,i] is equal to sg
0
j,i
=
s
;
5)
Element under index [i,j] is equal to -sg
0
i,j
=
-s
;
After constructing the matrix
G
, we can multiply it by the matrix
A
0
k - 1
from the left, and we will get the matrix
A
0
k
;
In this step, we will zero out the element under index
j,i
;
We will also multiply the matrix
Q
0
k - 1
by the matrix
G
T
0
and get the matrix
Q
0
k
;
2
Iteration 1At the first iteration, the matrix
A
0
0
is equal to the original matrix
A
:
A
0
0
=
1
1
0
1
0
1
0
1
1
Write the initial matrix
Q
0
0
, which is equal to the identity matrix:
Q
0
0
=
1
0
0
0
1
0
0
0
1
i
=
1
;
j
=
2
;
a
=
a
0
k - 1
0
i,i
=
a
0
0
0
1,1
=
1
;
b
=
a
0
k - 1
0
j,i
=
a
0
0
0
2,1
=
1
;
r
=
a
2
0
+
b
2
0
=
1
2
0
+
1
2
0
=
1
517766953
1250000000
;
c
=
a
r
=
1
1
517766953
1250000000
=
1767766953
2500000000
;
s
= -
b
r
= -
1
1
517766953
1250000000
=
-
1767766953
2500000000
;
G
=
c
s
0
-s
c
0
0
0
1
=
1767766953
2500000000
-
1767766953
2500000000
0
1767766953
2500000000
1767766953
2500000000
0
0
0
1
;
Matrix
A
0
1
A
0
1
=
G
0
·
A
0
0
=
1767766953
2500000000
-
1767766953
2500000000
0
1767766953
2500000000
1767766953
2500000000
0
0
0
1
·
1
1
0
1
0
1
0
1
1
=
1
517766953
1250000000
0
0
1767766953
2500000000
-
1767766953
2500000000
1
1767766953
2500000000
1767766953
2500000000
1
Matrix
G
T
0
G
T
0
=
1767766953
2500000000
1767766953
2500000000
0
-
1767766953
2500000000
1767766953
2500000000
0
0
0
1
Matrix
Q
0
1
Q
0
1
=
Q
0
0
·
G
T
0
=
1
0
0
0
1
0
0
0
1
·
1767766953
2500000000
1767766953
2500000000
0
-
1767766953
2500000000
1767766953
2500000000
0
0
0
1
=
1767766953
2500000000
1767766953
2500000000
0
-
1767766953
2500000000
1767766953
2500000000
0
0
0
1
3
Iteration 2i
=
2
;
j
=
3
;
a
=
a
0
k - 1
0
i,i
=
a
0
1
0
2,2
=
-
1767766953
2500000000
;
b
=
a
0
k - 1
0
j,i
=
a
0
1
0
3,2
=
1
;
r
=
a
2
0
+
b
2
0
=
-
1767766953
2500000000
2
0
+
1
2
0
=
1
1123724357
5000000000
;
c
=
a
r
=
-
1767766953
2500000000
1
1123724357
5000000000
=
-
1443375673
2500000000
;
s
= -
b
r
= -
1
1
1123724357
5000000000
=
-
8164965809
10000000000
;
G
=
1
0
0
0
c
s
0
-s
c
=
1
0
0
0
-
1443375673
2500000000
-
8164965809
10000000000
0
8164965809
10000000000
-
1443375673
2500000000
;
Matrix
A
0
2
A
0
2
=
G
0
·
A
0
1
=
1
0
0
0
-
1443375673
2500000000
-
8164965809
10000000000
0
8164965809
10000000000
-
1443375673
2500000000
·
1
517766953
1250000000
0
0
1767766953
2500000000
-
1767766953
2500000000
1
1767766953
2500000000
1767766953
2500000000
1
=
1
517766953
1250000000
0
0
1767766953
2500000000
1
1123724357
5000000000
0
1767766953
2500000000
816496581
2000000000
-1
193375673
1250000000
Matrix
G
T
0
G
T
0
=
1
0
0
0
-
1443375673
2500000000
8164965809
10000000000
0
-
8164965809
10000000000
-
1443375673
2500000000
Matrix
Q
0
2
Q
0
2
=
Q
0
1
·
G
T
0
=
1767766953
2500000000
1767766953
2500000000
0
-
1767766953
2500000000
1767766953
2500000000
0
0
0
1
·
1
0
0
0
-
1443375673
2500000000
8164965809
10000000000
0
-
8164965809
10000000000
-
1443375673
2500000000
=
1767766953
2500000000
1767766953
2500000000
0
816496581
2000000000
-
816496581
2000000000
8164965809
10000000000
1443375673
2500000000
-
1443375673
2500000000
-
1443375673
2500000000
4
Matrix Q, RQ
=
Q
0
2
=
1767766953
2500000000
1767766953
2500000000
0
816496581
2000000000
-
816496581
2000000000
8164965809
10000000000
1443375673
2500000000
-
1443375673
2500000000
-
1443375673
2500000000
R
=
A
0
2
=
1
517766953
1250000000
0
0
1767766953
2500000000
1
1123724357
5000000000
0
1767766953
2500000000
816496581
2000000000
-1
193375673
1250000000
Answer
A = Q · RQ
=
1767766953
2500000000
1767766953
2500000000
0
816496581
2000000000
-
816496581
2000000000
8164965809
10000000000
1443375673
2500000000
-
1443375673
2500000000
-
1443375673
2500000000
R
=
1
517766953
1250000000
0
0
1767766953
2500000000
1
1123724357
5000000000
0
1767766953
2500000000
816496581
2000000000
-1
193375673
1250000000
SIZE3×3METHODGivens rotation