Antri Dekomposisi Kami

16

Dalam tantangan ini saya akan meminta Anda untuk menemukan dekomposisi QR dari matriks persegi. Dekomposisi QR dari matriks A adalah dua Matriks Q dan R sehingga A = QR . Secara khusus kami sedang mencari Q menjadi matriks ortogonal (yaitu Q T Q = QQ T = I di mana saya adalah identitas perkalian dan T adalah transpose) dan R menjadi matriks segitiga atas (setiap nilai di bawah keharusan diagonalnya menjadi nol).

Anda akan menulis kode yang mengambil matriks persegi dengan metode apa pun yang masuk akal dan mengeluarkan dekomposisi QR dengan metode apa pun. Banyak matriks memiliki beberapa dekomposisi QR tetapi Anda hanya perlu satu keluaran.

Elemen dari matriks hasil Anda harus berada dalam dua tempat desimal dari jawaban aktual untuk setiap entri dalam matriks.

Ini adalah kompetisi kode-golf sehingga jawaban akan dinilai dalam byte dengan lebih sedikit byte menjadi skor yang lebih baik.

Uji Kasus

Ini hanya output yang mungkin, output Anda tidak perlu cocok dengan semua ini selama mereka valid.

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 Posting Rock Garf Hunter
sumber
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
Dennis

Jawaban:

5

Julia, 2 byte

qr

Fungsi qrmenerima matriks persegi dan mengembalikan Tuplematriks: Q dan R .

Cobalah online!

Alex A.
sumber
4
Senang bertemu Anda! Tidak ada yang lebih pendek dari ini :-)
Luis Mendo
Saya tahu Anda akan segera kembali. Selamat datang kembali! BTW yang built-in ...
Erik the Outgolfer
5

Oktaf , 19 byte

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

Cobalah online!

Jawaban Oktaf pertama saya \ o /

Octave's qrmemiliki beberapa alternatif dalam bahasa lain yang mengembalikan Q dan R : QRDecomposition(Mathematica), matqr(PARI / GP), 128!:0- jika saya ingat dengan benar - (J), qr(R) ...

Tuan Xcoder
sumber
Jadi ... akankah Anda memposting solusi J atau harus saya?
Adám
@ Adám saya tidak akan. Silakan dan kirim jika Anda mau.
Tn. Xcoder
Mengapa tidak 128!:0bekerja pada matriks semua nol‽
Adám
2
Apakah ini berfungsi pada semua matriks nol?
Adám
@LuisMendo Terima kasih banyak untuk perbaikannya!
Tn. Xcoder
1

Python 2, 329 324 byte

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

Kita harus menggunakan pecahan untuk memastikan hasil yang benar, lihat https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process#Numerical_stability

Lekukan yang digunakan:

  1. 1 ruang
  2. 1 tab
Tyilo
sumber
2
Saat menjorok Anda dapat menyimpan byte dengan menggunakan ;untuk memisahkan baris. Anda juga dapat sering mengabaikan jeda baris setelah :. Saya akan menyarankan bermain-main dengan ini karena saya dapat melihat beberapa tempat jawaban ini bisa lebih pendek menggunakan teknik ini.
Post Rock Garf Hunter
@WheatWizard Terima kasih :)
Tyilo
1
Sayangnya, ini tidak akan berfungsi untuk matriks dengan baris nol.
Dennis
0

Python dengan numpy, 28 byte

import numpy
numpy.linalg.qr
Tyilo
sumber