Gegeven is een reële matrix $$A$$ met $$N$$ rijen en $$N$$ kolommen. We willen deze matrix schrijven als product van twee reële $$N \times N$$ matrices $$Q$$ en $$R$$, namelijk:$$ A = Q R $$ waarbij:

• de matrix $$Q$$ orthgonaal is (m.a.w. $$Q Q^T = Q^T Q = I_N$$) met ($$I_N$$ de $$N \times N$$ eenheidsmatrix)
• de matrix $$R$$ een bovendriehoeksmatrix is (m.a.w. $$R_{ij} = 0$$ voor $$i > j$$)

Om dit te realiseren, passen we een reeks van $$N - 1$$ spiegelingen in $$N$$ dimensies toe, waarbij elke spiegeling gekenmerkt wordt door een orthogonale matrix $$Q_i$$. De spiegeling met rangnummer $$i$$ zorgt dat de kolom met rangnummer $$i$$ van de getransformeerde matrix nullen vertoont op alle rijen $$j > i$$ van die kolom.

Onderstaand algoritme genereert de gezochte matrices $$Q$$ en $$R$$.

• Herhaal onderstaande stappen voor $$i = 0$$ t.e.m. $$N - 2$$.
• Construeer de vector $$k$$ als volgt (componenten $$k_0, k_1, ... k_{N-1}$$):
  • beschouw de kolom met rangnummer $$i$$ van de matrix $$A$$
  • neem $$k_j = 0$$ voor $$j < i$$
  • neem $$k_j = A_{ji}$$ voor $$j \ge i$$
• Noem de vector $$e$$ de eenheidsvector in richting $$i$$ (m.a.w. $$e[i] = 1$$ en $$e[j] = 0$$ voor $$j \ne i$$)
• Construeer de vector $$u$$ namelijk $$u = k - ||k|| e $$ (hierin staat ||k|| voor de lengte van de vector $$k$$ (de wortel uit de som van de kwadraten van de componenten van $$k$$))
• De vector $$v$$ is de genormeerde versie van de vector $$u$$, namelijk $$v = u/||u||$$
• De gezochte spiegeling in deze stap wordt gekenmerkt door de matrix $$Q_i = I_N - 2 v v^T$$ (hierin wordt de vector $$v$$ als kolommatrix voorgesteld, en is $$I_N$$ de $$N \times N$$ eenheidsmatrix
• Pas de spiegeling toe op $$A$$, m.a.w. de matrix $$A$$ wordt aangepast naar $$Q_i A$$, waarbij kolom $$i$$ van deze getransformeerde matrix nu nullen vertoont beneden de hoofddiagonaal.
• Herhaal voorgaande stappen voor alle stappen $$i$$ (0 t.e.m. $$N-1$$).

Voorgaand algoritme construeert stapsgewijs de matrix $$R$$ via $$R = Q_{N-1} Q_{N-2} ... Q_1 Q_0 A$$. We hebben dus dat $$A = (Q_{N-1} Q_{N-2} ... Q_1 Q_0)^T R$$ (vermits alle $$Q_i$$ orthogonaal zijn), waarmee de gezochte $$Q$$-matrix dus wordt : $$Q = (Q_{N-1} Q_{N-2} ... Q_1 Q_0)^T$$.

Schrijf de functie QR() met als enig argument een reële $$N \times N$$ matrix, en die als resultaat een tuple teruggeeft, bestaande uit de matrices $$Q$$ en $$R$$ die je bekomt door bovenstaand algoritme te volgen.

LET OP : het is NIET toegelaten om in deze oefening gebruik te maken van lijsten. De oplossing mag enkel gebruik maken van NumPy-rijen of tabellen.

Merk op dat je resultaat, ten behoeve van de evaluatie in Dodona, afgebroken wordt op 4 decimalen (defunctie format_t() uit het verbeterscript zorgt hiervoor). Je resultaat wordt ook omgezet naar een lijst, maar let erop dat het resultaat van je functie WEL DEGELIJK een NumPy-tabel MOET zijn.

Voorbeeld

Voor

A = 
[[ 1.  2.  3.  4.]
 [ 3.  2.  1.  4.]
 [ 4.  4.  3.  3.]
 [ 1.  2.  2.  1.]]

komt er

Q, R = QR(A)
print(Q)
#[[  1.92450090e-01   6.02464076e-01   7.74596669e-01  -5.82867088e-16]
# [  5.77350269e-01  -5.16397779e-01   2.58198890e-01  -5.77350269e-01]
# [  7.69800359e-01   8.60662966e-02  -2.58198890e-01   5.77350269e-01]
# [  1.92450090e-01   6.02464076e-01  -5.16397779e-01  -5.77350269e-01]]
print(R)
#[[  5.19615242e+00   5.00370233e+00   3.84900179e+00   5.58105260e+00]
# [ -5.48478474e-16   1.72132593e+00   2.75412149e+00   1.20492815e+00]
# [ -7.87088995e-16   8.30351827e-17   7.74596669e-01   2.84018779e+00]
# [  1.28197512e-16   1.33255625e-16  -5.82867088e-16  -1.15470054e+00]]
print(np.dot(Q, R))
#[[ 1.  2.  3.  4.]
# [ 3.  2.  1.  4.]
# [ 4.  4.  3.  3.]
# [ 1.  2.  2.  1.]]