Poner en cola nuestra descomposición

16

En este desafío, le pediré que encuentre una descomposición QR de una matriz cuadrada. La descomposición QR de la matriz A es dos Matrices Q y R, de modo que A = QR . En particular, buscamos que Q sea ​​una matriz ortogonal (es decir, Q T Q = QQ T = I donde I es la identidad multiplicativa y T es la transposición) y R sea ​​una matriz triangular superior (cada valor debajo de su diagonal debe ser cero)

Escribirás código que tome una matriz cuadrada por cualquier método razonable y genere una descomposición QR por cualquier método. Muchas matrices tienen múltiples descomposiciones QR, sin embargo, solo necesita una salida.

Los elementos de sus matrices resultantes deben estar dentro de dos lugares decimales de una respuesta real para cada entrada en la matriz.

Esta es una competencia de , por lo que las respuestas se puntuarán en bytes, siendo menos bytes una mejor puntuación.


Casos de prueba

Estas son solo salidas posibles, sus salidas no necesitan coincidir con todas ellas siempre que sean válidas.

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
Post Rock Garf Hunter
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Dennis

Respuestas:

5

Julia, 2 bytes

qr

La función qracepta una matriz cuadrada y devuelve una Tuplede matrices: Q y R .

Pruébalo en línea!

Alex A.
fuente
44
¡Me alegro de verte! No hay nada más corto que esto :-)
Luis Mendo
Sabía que volverías pronto. ¡Dar una buena acogida! Qué BTW incorporado ...
Erik the Outgolfer
5

Octava , 19 bytes

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

Pruébalo en línea!

Mi primera respuesta de Octave \ o /

Octave qrtiene bastantes alternativas en otros idiomas que devuelven Q y R : QRDecomposition(Mathematica), matqr(PARI / GP), 128!:0- si recuerdo correctamente - (J), qr(R) ...

Sr. Xcoder
fuente
Entonces ... ¿publicarás esa solución J o lo haré?
Adám
@ Adám no lo haré. Anímate y publícalo si quieres.
Sr. Xcoder
¿Por qué no 128!:0funciona en una matriz todo cero?
Adám
@LuisMendo ¡Muchas gracias por la solución!
Sr. 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)]

Debemos usar fracciones para garantizar una salida correcta, consulte https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process#Numerical_stability

Sangría utilizada:

  1. 1 espacio
  2. 1 pestaña
Tyilo
fuente
2
Cuando se sangra, puede guardar bytes mediante el uso ;de líneas separadas. También a menudo puede renunciar al salto de línea después :. Sugeriría jugar con estos porque puedo ver algunos lugares donde esta respuesta puede ser más corta usando esta técnica.
Post Rock Garf Hunter
@WheatWizard Gracias :)
Tyilo
1
Desafortunadamente, esto no funcionará para matrices con filas nulas.
Dennis
0

Python con numpy, 28 bytes

import numpy
numpy.linalg.qr
Tyilo
fuente