Mettre en file d'attente notre décomposition

16

Dans ce défi, je vous demanderai de trouver une décomposition QR d'une matrice carrée. La décomposition QR de la matrice A est deux matrices Q et R telles que A = QR . En particulier, nous recherchons Q pour être une matrice orthogonale (c'est-à-dire Q T Q = QQ T = I où I est l'identité multiplicative et T est la transposée) et R pour être une matrice triangulaire supérieure (chaque valeur en dessous de sa diagonale doit être zéro).

Vous écrirez du code qui prend une matrice carrée par n'importe quelle méthode raisonnable et génère une décomposition QR par n'importe quelle méthode. De nombreuses matrices ont plusieurs décompositions QR, mais vous n'avez besoin que d'une seule sortie.

Les éléments de vos matrices résultantes doivent se trouver à deux décimales près d'une réponse réelle pour chaque entrée de la matrice.

Il s'agit d'une compétition de code-golf donc les réponses seront notées en octets avec moins d'octets étant un meilleur score.

Cas de test

Ce ne sont que des sorties possibles, vos sorties n'ont pas besoin de correspondre à toutes celles-ci tant qu'elles sont valides.

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
la source
Les commentaires ne sont pas pour une discussion approfondie; cette conversation a été déplacée vers le chat .
Dennis

Réponses:

5

Julia, 2 octets

qr

La fonction qraccepte une matrice carrée et renvoie une Tupledes matrices: Q et R .

Essayez-le en ligne!

Alex A.
la source
4
Ravi de vous voir! Ça ne fait pas plus court que ça :-)
Luis Mendo
Je savais que tu reviendrais sous peu. Nous saluons le retour! Quel BTW intégré ...
Erik the Outgolfer
5

Octave , 19 octets

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

Essayez-le en ligne!

Ma première réponse Octave \ o /

Octave qra plusieurs alternatives dans d'autres langages qui retournent à la fois Q et R : QRDecomposition(Mathematica), matqr(PARI / GP), 128!:0- si je me souviens bien - (J), qr(R) ...

M. Xcoder
la source
Alors… allez-vous publier cette solution J ou dois-je?
Adám
@ Adám, je ne le ferai pas. Allez-y et postez-le si vous le souhaitez.
M. Xcoder
Pourquoi ne 128!:0fonctionne pas sur une matrice entièrement nulle?
Adám
2
Fonctionne-t-il sur des matrices entièrement nulles?
Adám
@LuisMendo Merci beaucoup pour la correction!
M. Xcoder,
1

Python 2, 329 324 octets

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

Nous devons utiliser des fractions pour assurer une sortie correcte, voir https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process#Numerical_stability

Indentation utilisée:

  1. 1 espace
  2. 1 onglet
Tyilo
la source
2
En retrait, vous pouvez enregistrer des octets en utilisant ;des lignes séparées. Vous pouvez également souvent renoncer à la rupture de ligne après :. Je suggérerais de jouer avec ceux-ci car je peux voir quelques endroits où cette réponse peut être plus courte en utilisant cette technique.
Post Rock Garf Hunter
@WheatWizard Merci :)
Tyilo
1
Malheureusement, cela ne fonctionnera pas pour les matrices avec des lignes nulles.
Dennis
0

Python avec numpy, 28 octets

import numpy
numpy.linalg.qr
Tyilo
la source