Format liczbowy
Komentarze dotyczące rozwiązania
Bez opisu (tylko odpowiedź)
a
b
c
d
x
y
z
clear
i
Randomize
3131313131351515151515≈83137
Jak obliczyć rozkład QR obrotami Givensa
Zastosuj sekwencję 2-wymiarowych obrotów płaszczyznowych, aby zerować wpisy poniżej diagonali jeden po drugim. Każdy obrót Givensa określony jest dwoma wpisami, na których działa. Skumulowany iloczyn obrotów to Q, a obrócona macierz to R.
Obroty Givensa — przykład pracujący (3×3)
Zapisz macierz początkową
A
:
A
=
1
1
0
1
0
1
0
1
1
Rozkład
QR
to przedstawienie macierzy
A
w postaci:
A
=
Q
*
R
.
Macierz
Q
jest macierzą ortonormalną.
Macierz
R
jest macierzą trójkątną górną.
Możemy wykorzystać obroty Givensa, aby wyzerować wszystkie elementy poniżej głównej przekątnej macierzy
A
.
Metoda ta jest iteracyjna i w jednej iteracji wyzerujemy jeden element.
W ostatniej iteracji, gdy wszystkie elementy poniżej głównej przekątnej zostaną wyzerowane, otrzymamy macierz
R
.
Podczas obliczania macierzy
R
w każdej iteracji będziemy obliczać macierz
G
, aby wyzerować elementy poniżej głównej przekątnej.
Możemy obliczyć macierz
Q
poprzez pomnożenie wszystkich transponowanych macierzy
G
.
Będziemy wyzerować elementy w kolejności od góry do dołu i od lewej do prawej.
W każdej iteracji musimy zdefiniować następujące zmienne:
a
to element macierzy Aₖ₋₁, który znajduje się na głównej przekątnej w tej samej kolumnie co element, który chcemy wyzerować .a
=
a
0
k - 1
0
i,i
;
b
to element macierzy Aₖ₋₁, który chcemy wyzerować .b
=
a
0
k - 1
0
j,i
;
// gdzie
j
to numer wiersz, w którym znajduje się element, który chcemy wyzerować.i
to numer kolumna, w którym znajduje się element, który chcemy wyzerować.k
to numer iteracji.Aₖ₋₁
to macierz obliczona w poprzedniej iteracji.Następnie musimy obliczyć następujące wartości:
r
=
a
2
0
+
b
2
0
;
c
=
a
r
;
s
= -
b
r
;
Teraz możemy skonstruować macierz
G
:
1)
Bazą macierzy G jest macierz jednostkowa rozmiaru n na n.// gdzie
n
to liczba wierszy macierzy A.2)
Element pod indeksem [i,i] jest równy c.g
0
i,i
=
c
;
3)
Element pod indeksem [j,j] jest równy c.g
0
j,j
=
c
;
4)
Element pod indeksem [j,i] jest równy s.g
0
j,i
=
s
;
5)
Element pod indeksem [i,j] jest równy -s.g
0
i,j
=
-s
;
Po skonstruowaniu macierzy
G
możemy ją pomnożyć przez macierz
A
0
k - 1
z lewej strony i otrzymamy macierz
A
0
k
.
W tym kroku wyzerujemy element pod indeksem
j,i
.
Pomnożymy również macierz
Q
0
k - 1
przez macierz
G
T
0
i otrzymamy macierz
Q
0
k
.
2
Iteracja 1W pierwszej iteracji macierz
A
0
0
jest równa oryginalnej macierzy
A
.
A
0
0
=
1
1
0
1
0
1
0
1
1
Zapisz początkową macierz
Q
0
0
, która jest równa macierzy jednostkowej.
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
41
100
;
c
=
a
r
=
1
1
41
100
=
71
100
;
s
= -
b
r
= -
1
1
41
100
=
-
71
100
;
G
=
c
s
0
-s
c
0
0
0
1
=
71
100
-
71
100
0
71
100
71
100
0
0
0
1
;
Macierz
A
0
1
A
0
1
=
G
0
·
A
0
0
=
71
100
-
71
100
0
71
100
71
100
0
0
0
1
·
1
1
0
1
0
1
0
1
1
=
1
41
100
0
0
71
100
-
71
100
1
71
100
71
100
1
Macierz
G
T
0
G
T
0
=
71
100
71
100
0
-
71
100
71
100
0
0
0
1
Macierz
Q
0
1
Q
0
1
=
Q
0
0
·
G
T
0
=
1
0
0
0
1
0
0
0
1
·
71
100
71
100
0
-
71
100
71
100
0
0
0
1
=
71
100
71
100
0
-
71
100
71
100
0
0
0
1
3
Iteracja 2i
=
2
;
j
=
3
;
a
=
a
0
k - 1
0
i,i
=
a
0
1
0
2,2
=
-
71
100
;
b
=
a
0
k - 1
0
j,i
=
a
0
1
0
3,2
=
1
;
r
=
a
2
0
+
b
2
0
=
-
71
100
2
0
+
1
2
0
=
1
11
50
;
c
=
a
r
=
-
71
100
1
11
50
=
-
29
50
;
s
= -
b
r
= -
1
1
11
50
=
-
41
50
;
G
=
1
0
0
0
c
s
0
-s
c
=
1
0
0
0
-
29
50
-
41
50
0
41
50
-
29
50
;
Macierz
A
0
2
A
0
2
=
G
0
·
A
0
1
=
1
0
0
0
-
29
50
-
41
50
0
41
50
-
29
50
·
1
41
100
0
0
71
100
-
71
100
1
71
100
71
100
1
=
1
41
100
0
0
71
100
1
11
50
0
71
100
41
100
-1
3
20
Macierz
G
T
0
G
T
0
=
1
0
0
0
-
29
50
41
50
0
-
41
50
-
29
50
Macierz
Q
0
2
Q
0
2
=
Q
0
1
·
G
T
0
=
71
100
71
100
0
-
71
100
71
100
0
0
0
1
·
1
0
0
0
-
29
50
41
50
0
-
41
50
-
29
50
=
71
100
71
100
0
41
100
-
41
100
41
50
29
50
-
29
50
-
29
50
4
Macierz Q, RQ
=
Q
0
2
=
71
100
71
100
0
41
100
-
41
100
41
50
29
50
-
29
50
-
29
50
R
=
A
0
2
=
1
41
100
0
0
71
100
1
11
50
0
71
100
41
100
-1
3
20
Answer
A = Q · RQ
=
71
100
71
100
0
41
100
-
41
100
41
50
29
50
-
29
50
-
29
50
R
=
1
41
100
0
0
71
100
1
11
50
0
71
100
41
100
-1
3
20
Rozmiar3×3MetodaRotacja Givensa