Fila de nossa decomposição

16

Neste desafio, pedirei que você encontre uma decomposição QR de uma matriz quadrada. A decomposição QR da matriz A é duas matrizes Q e R, de modo que A = QR . Em particular, estamos procurando Q ser uma matriz ortogonal (ou seja, Q T Q = QQ T = I, onde I é a identidade multiplicativa e T é a transposição) e R uma matriz triangular superior (todos os valores abaixo de sua diagonal devem seja zero).

Você escreverá um código que utiliza uma matriz quadrada por qualquer método razoável e gera uma decomposição QR por qualquer método. Muitas matrizes têm várias decomposições QR, no entanto, você só precisa da saída uma.

Os elementos das matrizes resultantes devem estar dentro de duas casas decimais de uma resposta real para cada entrada na matriz.

Esta é uma competição de código-golfe , portanto as respostas serão pontuadas em bytes, com menos bytes sendo uma pontuação melhor.

Casos de teste

Essas são apenas saídas possíveis; suas saídas não precisam corresponder a todas, desde que 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
code-golf math matrix factoring Post Rock Garf Hunter
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Dennis

Respostas:

5

Julia, 2 bytes

qr

A função qraceita uma matriz quadrada e retorna uma Tupledas matrizes: Q e R .

Experimente online!

Alex A.
fonte
4
É bom te ver! Ele não fica mais curto do que isso :-) #
45675 Luis Mendo
Eu sabia que você voltaria em breve. Bem vindo de volta! O que um BTW embutido ...
Erik the Outgolfer
5

Oitava , 19 bytes

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

Experimente online!

Minha primeira resposta do Oitava \ o /

O Octave's qrtem muitas alternativas em outros idiomas que retornam Q e R : QRDecomposition(Mathematica), matqr(PARI / GP), 128!:0- se bem me lembro - (J), qr(R) ...

Mr. Xcoder
fonte
Então ... você vai postar essa solução J ou devo?
Adám
@ Adám não vou. Vá em frente e publique, se quiser.
Sr. Xcoder
Por que não 128!:0funciona em uma matriz de zero‽
Adám
2
Funciona em matrizes totalmente zero?
Adám
@LuisMendo Muito obrigado pela correção!
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)]

Devemos usar frações para garantir a saída correta, consulte https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process#Numerical_stability

Recuo usado:

  1. 1 espaço
  2. 1 guia
Tyilo
fonte
2
Quando recuado, você pode salvar bytes usando ;para separar linhas. Você também pode frequentemente renunciar à quebra de linha depois :. Eu sugeriria brincar com eles, porque eu posso ver alguns lugares em que essa resposta pode ser mais curta usando essa técnica.
Post Rock Garf Hunter
@WheatWizard Thanks :)
Tyilo
1
Infelizmente, isso não funcionará para matrizes com linhas nulas.
Dennis
0

Python com numpy, 28 bytes

import numpy
numpy.linalg.qr
Tyilo
fonte