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 odbiciami Householdera
Konstruuj odbicia zerujące wpisy poniżej diagonali kolumna po kolumnie. Każde odbicie określone jest wektorem kolumnowym będącym poddanym redukcji; iloczyn odbić daje Q (ortogonalne), a odbita macierz to R (górnotrójkątna).
Odbicia Householdera — przykład pracujący (2×2)
Zapisz macierz początkową
A
:
A
=
3
4
1
2
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ą.
Aby wykonać rozkład
QR
za pomocą metody odbić Householdera, należy wykonać następujące czynności:
1)
Oblicz wektor odbicia Householdera v dla każdej kolumny a macierzy A.2)
Dla każdej kolumny a macierzy A obliczamy macierz Householdera H.3)
Po zastosowaniu transformacji Householdera do wszystkich kolumn macierzy A, otrzymana przekształcona macierz A' będzie górną macierzą trójkątną R.4)
Macierz ortogonalna Q jest otrzymywana poprzez pomnożenie wszystkich macierzy Householdera H.Aby wykonać rozkład
QR
za pomocą metody odbić Householdera, należy wykonać następujące czynności dla każdej kolumny
a
macierzy
A
:
1)
Oblicz normę ‖a‖ kolumny a.2)
Zdefiniuj znak(s) kolumny a.s
= -
sgn
(
a
[
i
])
;
// gdzie
sgn(a)
= 1 jeśli a[i] ≥ 0, a -1 w przeciwnym razie.a[i]
jest i-tym elementem kolumny a.i
jest numerem kolumny.3)
Oblicz wektor odbicia Householdera .v
=
a
-
s
*
a
*
e
0
i
;
// gdzie
eᵢ
jest wektorem bazy standardowej, gdzie i-ty element jest równy 1, a wszystkie pozostałe elementy są równe 0.i
jest numerem kolumny.4)
Znormalizuj wektor odbicia Householdera .v_norm
=
v
v
;
5)
Oblicz macierz Householdera .H
0
i
=
I
- 2 *
v_norm
*
v_norm
T
0
;
6)
Zastosuj transformację Householdera do macierzy .A'
0
i
=
H
0
i
*
A'
0
i - 1
;
7)
Oblicz macierz .Q
0
i
=
Q
0
i - 1
*
H
0
i
;
2
Iteracja 1W pierwszej iteracji macierz
A'
0
0
jest równa oryginalnej macierzy
A
.
A'
0
0
=
3
4
1
2
Zapisz początkową macierz
Q
0
0
, która jest równa macierzy jednostkowej.
Q
0
0
=
1
0
0
1
Wektor
a
jest równy
1
-tej kolumnie macierzy
A'
0
0
.
a
=
3
4
Oblicz normę
a
kolumny
a
:
.
a
=
5
;
Zdefiniuj znak(
s
) kolumny
a
:
.
s
= -
sgn
(
a
[
1
])
= -
sgn
-(
3
) = -(
1
) =
-1
;
Zapisz
1
-ty wektor bazy standardowej.
e
0
1
=
1
0
Oblicz wektor odbicia Householdera
:
.
v
=
a
-
s
*
a
*
e
0
1
=
3
4
-
-1
*
5
*
1
0
=
3
4
-
-5
0
=
8
4
;
Znormalizuj wektor odbicia Householdera
:
.
v_norm
=
v
v
=
89
100
9
20
Oblicz wektor odbicia Householdera
:
.
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
Zastosuj transformację Householdera do macierzy
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
Oblicz macierz
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
Iteracja 2Wektor
a
jest równy
2
-tej kolumnie macierzy
A'
0
1
.
a
=
0
2
5
Oblicz normę
a
kolumny
a
:
.
a
=
2
5
;
Zdefiniuj znak(
s
) kolumny
a
:
.
s
= -
sgn
(
a
[
2
])
= -
sgn
-(
2
5
) = -(
1
) =
-1
;
Zapisz
2
-ty wektor bazy standardowej.
e
0
2
=
0
1
Oblicz wektor odbicia Householdera
:
.
v
=
a
-
s
*
a
*
e
0
2
=
0
2
5
-
-1
*
2
5
*
0
1
=
0
2
5
-
0
-
2
5
=
0
4
5
;
Znormalizuj wektor odbicia Householdera
:
.
v_norm
=
v
v
=
0
1
Oblicz wektor odbicia Householdera
:
.
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
Zastosuj transformację Householdera do macierzy
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
Oblicz macierz
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
Macierz 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
Rozmiar2×2MetodaOdbicia Householdera