Kolejka naszego rozkładu

16

W tym wyzwaniu poproszę Cię o znalezienie rozkładu QR macierzy kwadratowej. Rozkład macierzy A na QR to dwie macierze Q i R takie, że A = QR . W szczególności szukamy Q jako macierzy ortogonalnej (to znaczy Q T Q = QQ T = I, gdzie I to tożsamość multiplikatywna, a T to transpozycja), a R to górna macierz trójkątna (każda wartość poniżej jej przekątnej musi zero).

Napisz kod, który przyjmuje macierz kwadratową dowolną rozsądną metodą i generuje rozkład QR dowolną metodą. Wiele macierzy ma wiele rozkładów QR, jednak zawsze potrzebujesz tylko jednego wyjściowego.

Elementy macierzy wynikowych powinny znajdować się w obrębie dwóch miejsc po przecinku rzeczywistej odpowiedzi dla każdego wpisu w macierzy.

Jest to konkurs golfowy , więc odpowiedzi będą oceniane w bajtach, przy czym mniej bajtów oznacza lepszy wynik.

Przypadki testowe

Są to tylko możliwe dane wyjściowe, twoje dane wyjściowe nie muszą pasować do nich wszystkich, o ile są prawidłowe.

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 Post Rock Garf Hunter
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Dennis

Odpowiedzi:

5

Julia, 2 bajty

qr

Funkcja qrprzyjmuje macierzy kwadratowej i zwraca Tuplemacierzy: Q i R .

Wypróbuj online!

Alex A.
źródło
4
Miło cię widzieć! Nie jest krótszy niż to :-)
Luis Mendo
Wiedziałem, że wkrótce wrócisz. Witamy spowrotem! Co za wbudowana BTW ...
Erik the Outgolfer
5

Oktawa , 19 bajtów

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

Wypróbuj online!

Moja pierwsza odpowiedź Octave \ o /

Octave qrma całkiem sporo alternatyw w innych językach, które zwracają zarówno Q, jak i R : QRDecomposition(Mathematica),matqr (PARI / GP), 128!:0- jeśli dobrze pamiętam - (J), qr(R) ...

Pan Xcoder
źródło
Więc… opublikujesz to rozwiązanie J, czy mam?
Adám
@ Adám nie będę. Śmiało i opublikuj go, jeśli chcesz.
Pan Xcoder,
Dlaczego nie 128!:0działa na matrycy zera zero‽
Adám
2
Czy to działa na macierzach zerowych?
Adám
@LuisMendo Wielkie dzięki za naprawę!
Pan Xcoder,
1

Python 2, 329 324 bajty

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)]

Musimy używać ułamków, aby zapewnić poprawną wydajność, patrz https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process#Numerical_stability

Zastosowane wcięcie:

  1. 1 miejsce
  2. 1 zakładka
Tyilo
źródło
2
Po wcięciu możesz zapisać bajty, używając ;do oddzielania linii. Często możesz też zrezygnować z podziału linii :. Proponuję bawić się nimi, ponieważ widzę kilka miejsc, w których ta odpowiedź może być krótsza przy użyciu tej techniki.
Post Rock Garf Hunter
@WheatWizard Thanks :)
Tyilo
1
Niestety nie zadziała to dla macierzy o zerowych wierszach.
Dennis
0

Python z numpy, 28 bajtów

import numpy
numpy.linalg.qr
Tyilo
źródło