Формат чисел
Коментарі рішення
Без опису (тільки відповідь)
a
b
c
d
x
y
z
clear
i
Randomize
3131313131351515151515≈83137
Як обчислити QR-розкладання методом поворотів Гівенса
Застосуйте послідовність двовимірних поворотів площини для обнулення піддіагональних елементів один за одним. Кожен поворот Гівенса визначається двома елементами, на які він діє. Кумулятивний добуток поворотів — це Q, а піддана поворотам матриця — R.
Розв'язаний приклад поворотів Гівенса (3×3)
Запишемо вихідну матрицю
A
:
A
=
1
1
0
1
0
1
0
1
1
QR
розкладання є представленням матриці
A
у вигляді:
A
=
Q
*
R
;
Матриця
Q
– ортонормована матриця;
Матриця
R
– верхня трикутна матриця;
Ми можемо використовувати обертання Гівенса, щоб зробити всі елементи нижче головної діагоналі матриці
A
рівними нулю;
Цей метод є ітеративним, і на кожній ітерації ми будемо перетворювати один елемент в нуль;
На останній ітерації, коли всі елементи нижче головної діагоналі перетворяться в нуль, ми отримаємо матрицю
R
;
Під час обчислення матриці
R
на кожній ітерації ми будемо обчислювати матрицю
G
, щоб перетворити елементи нижче головної діагоналі в нуль;
Ми можемо обчислити матрицю
Q
, перемноживши всі транспоновані матриці
G
;
Ми будемо обнуляти елементи відгори донизу зліва направо;
На кожній ітерації нам потрібно визначити наступні змінні:
a
- це елемент матриці Aₖ₋₁, який знаходиться на головній діагоналі в тому ж стовпці, що й елемент, який ми хочемо перетворити в нульa
=
a
0
k - 1
0
i,i
;
b
- це елемент матриці Aₖ₋₁, який ми хочемо перетворити в нульb
=
a
0
k - 1
0
j,i
;
// де
j
- це номер рядки, в якому є елемент, який ми хочемо перетворити в нульi
- це номер стовпця, в якому є елемент, який ми хочемо перетворити в нульk
- це номер ітераціїAₖ₋₁
- це матриця, розрахована на попередній ітераціїДалі нам потрібно обчислити наступні значення:
r
=
a
2
0
+
b
2
0
;
c
=
a
r
;
s
= -
b
r
;
Тепер ми можемо побудувати матрицю
G
:
1)
- Основа матриці G є одиничною матрицею розміру n на n// де
n
- це кількість рядків матриці A2)
Елемент під індексом [i,i] дорівнює cg
0
i,i
=
c
;
3)
Елемент під індексом [j,j] дорівнює cg
0
j,j
=
c
;
4)
Елемент під індексом [j,i] дорівнює sg
0
j,i
=
s
;
5)
Елемент під індексом [i,j] дорівнює -sg
0
i,j
=
-s
;
Після побудови матриці
G
ми можемо помножити її на матрицю
A
0
k - 1
зліва, і отримаємо матрицю
A
0
k
;
На цьому етапі ми обнуляємо елемент під індексом
j,i
;
Ми також помножимо матрицю
Q
0
k - 1
на матрицю
G
T
0
і отримаємо матрицю
Q
0
k
;
2
Ітерація 1На першій ітерації матриця
A
0
0
дорівнює вихідній матриці
A
:
A
0
0
=
1
1
0
1
0
1
0
1
1
Запишемо початкову матрицю
Q
0
0
, яка дорівнює одиничній матриці:
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
;
Матриця
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
Матриця
G
T
0
G
T
0
=
71
100
71
100
0
-
71
100
71
100
0
0
0
1
Матриця
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
Ітерація 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
;
Матриця
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
Матриця
G
T
0
G
T
0
=
1
0
0
0
-
29
50
41
50
0
-
41
50
-
29
50
Матриця
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
Матриця 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
Розмір3×3МетодПоворот Гівенса