Очередь Наше Разложение

16

В этом задании я попрошу вас найти QR-разложение квадратной матрицы. QR-разложение матрицы A - это две матрицы Q и R, такие что A = QR . В частности, мы ищем, чтобы Q была ортогональной матрицей (то есть Q T Q = QQ T = I, где I - мультипликативная единица, а T - транспонирование), а R - верхней треугольной матрицей (каждое значение ниже ее диагонали должно быть ноль).

Вы напишите код, который принимает квадратную матрицу любым разумным способом и выводит QR-разложение любым методом. Многие матрицы имеют несколько QR-разложений, однако вам нужно только выводить их один раз.

Элементы ваших результирующих матриц должны находиться в двух десятичных разрядах от фактического ответа для каждой записи в матрице.

Это код-гольф соревнование поэтому ответы будут оцениваться в байтах, причем меньшее количество байтов будет лучшим результатом.

Тестовые случаи

Это только возможные выходы, ваши выходы не должны соответствовать всем этим, пока они действительны.

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 Пост Рок Гарф Хантер
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Деннис

Ответы:

5

Юлия, 2 байта

qr

Функция qrпринимает квадратную матрицу и возвращает Tupleматрицы: Q и R .

Попробуйте онлайн!

Алекс А.
источник
4
Рад вас видеть! Это не становится короче этого :-)
Луис Мендо
Я знал, что ты скоро вернешься. Добро пожаловать! Что за встроенный
КСТАТИ
5

Октава , 19 байт

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

Попробуйте онлайн!

Мой первый октавский ответ \ о /

У Octave qrесть довольно много альтернатив на других языках, которые возвращают и Q, и R : QRDecomposition(Mathematica), matqr(PARI / GP), 128!:0- если я правильно помню - (J), qr(R) ...

Мистер Xcoder
источник
Итак ... вы опубликуете это решение J или я?
Адам
@ Адам, я не буду. Идите и опубликуйте его, если хотите.
г-н Xcoder
Почему не 128!:0работает с нулевой матрицей?
Адам
2
Работает ли он на всех нулевых матрицах?
Адам
@ LuisMendo Большое спасибо за исправление!
Мистер Кскодер
1

Python 2, 329 324 байта

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

Мы должны использовать дроби, чтобы обеспечить правильный вывод, см. Https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process#Numeric_stability

Используемый отступ:

  1. 1 пробел
  2. 1 вкладка
Tyilo
источник
2
При отступе вы можете сохранять байты, используя ;отдельные строки. Вы также можете часто отказаться от разрыва строки после :. Я бы посоветовал поиграть с ними, потому что я вижу несколько мест, где этот ответ может быть короче с использованием этой техники.
Пост Рок Гарф Хантер
@WheatWizard Спасибо :)
Tyilo
1
К сожалению, это не будет работать для матриц с пустыми строками.
Деннис
0

Питон с NumPy, 28 байт

import numpy
numpy.linalg.qr
Tyilo
источник