Unsere Zersetzung in die Warteschlange stellen

16

In dieser Aufgabe werde ich Sie bitten, eine QR-Zerlegung einer quadratischen Matrix zu finden. Die QR-Zerlegung der Matrix A ist zwei Matrizen Q und R, so dass A = QR ist . Insbesondere suchen wir, dass Q eine orthogonale Matrix ist ( dh Q T Q = Q Q T = I, wobei I die multiplikative Identität und T die Transponierte ist) und R eine obere Dreiecksmatrix ist (jeder Wert unter seiner Diagonale muss sein) Null sein).

Sie werden Code schreiben, der mit jeder vernünftigen Methode eine quadratische Matrix annimmt und mit jeder Methode eine QR-Zerlegung ausgibt. Viele Matrizen haben mehrere QR-Zerlegungen, Sie müssen jedoch immer nur eine ausgeben.

Elemente Ihrer resultierenden Matrizen sollten bei jedem Eintrag in der Matrix innerhalb von zwei Dezimalstellen von einer tatsächlichen Antwort entfernt sein.

Dies ist ein Code-Golf- Wettbewerb, bei dem die Antworten in Bytes gewertet werden, wobei weniger Bytes eine bessere Punktzahl sind.

Testfälle

Dies sind nur mögliche Ausgaben, Ihre Ausgaben müssen nicht mit allen übereinstimmen, solange sie gültig sind.

0 0 0     1 0 0   0 0 0
0 0 0 ->  0 1 0   0 0 0
0 0 0     0 0 1 , 0 0 0

1 0 0     1 0 0   1 0 0
0 1 0 ->  0 1 0   0 1 0
0 0 1     0 0 1 , 0 0 1

1 2 3     1 0 0   1 2 3
0 3 1 ->  0 1 0   0 3 1
0 0 8     0 0 1 , 0 0 8

0 0 1     0 0 1   1 1 1
0 1 0 ->  0 1 0   0 1 0
1 1 1     1 0 0 , 0 0 1

0 0 0 0 1     0 0 0 0 1   1 0 0 0 1
0 0 0 1 0     0 0 0 1 0   0 1 1 1 0
0 0 1 0 0 ->  0 0 1 0 0   0 0 1 0 0
0 1 1 1 0     0 1 0 0 0   0 0 0 1 0
1 0 0 0 1     1 0 0 0 0 , 0 0 0 0 1
code-golf math matrix factoring Weizen-Assistent
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Dennis

Antworten:

5

Julia, 2 Bytes

qr

Die Funktion qrnimmt eine quadratische Matrix und gibt eine Tupleder Matrizen: Q und R .

Probieren Sie es online!

Alex A.
quelle
4
Schön dich zu sehen! Es wird nicht kürzer als das :-)
Luis Mendo
Ich wusste, dass du gleich zurückkommen würdest. Willkommen zurück! Was für eine eingebaute BTW ...
Erik der Outgolfer
5

Oktave , 19 Bytes

@(x)[[q,r]=qr(x),r]

Probieren Sie es online!

Meine erste Oktavantwort \ o /

Octave qrhat eine ganze Reihe von Alternativen in anderen Sprachen, die sowohl Q als auch R zurückgeben : QRDecomposition(Mathematica), matqr(PARI / GP), 128!:0- wenn ich mich recht entsinne - (J), qr(R) ...

Mr. Xcoder
quelle
Also ... wirst du diese J-Lösung posten oder soll ich?
Adám
@Adam werde ich nicht. Mach weiter und poste es, wenn du willst.
Mr. Xcoder
Warum funktioniert es nicht 128!:0mit einer Nullmatrix?
Adám
2
Funktioniert es mit All-Zero-Matrizen?
Adám
@ LuisMendo Vielen Dank für die Lösung!
Mr. Xcoder
1

Python 2, 329 324 Bytes

import fractions
I=lambda v,w:sum(a*b for a,b in zip(v,w))
def f(A):
 A,U=[map(fractions.Fraction,x)for x in zip(*A)],[]
 for a in A:
    u=a
    for v in U:u=[x-y*I(v,a)/I(v,v)for x,y in zip(u,v)]
    U.append(u)
 Q=[[a/I(u,u)**.5 for a in u]for u in U];return zip(*Q),[[I(e,a)*(i>=j)for i,a in enumerate(A)]for j,e in enumerate(Q)]

Wir müssen Brüche verwenden, um eine korrekte Ausgabe sicherzustellen. Siehe https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process#Numerical_stability

Einrückung verwendet:

  1. 1 Leerzeichen
  2. 1 tab
Tyilo
quelle
2
Wenn eingerückt, können Sie Bytes speichern, indem Sie ;Zeilen trennen. Sie können auch oft auf den Zeilenumbruch verzichten :. Ich würde vorschlagen, mit diesen zu spielen, da ich einige Stellen sehen kann, an denen diese Antwort mit dieser Technik kürzer sein kann.
Wheat Wizard
@ WheatWizard Danke :)
Tyilo
1
Leider funktioniert dies nicht für Matrizen mit Nullzeilen.
Dennis
0

Python mit Numpy, 28 Bytes

import numpy
numpy.linalg.qr
Tyilo
quelle