Nilai Eigen dari Matriks

11

Diberi matriks kuadrat, mengeluarkan nilai eigen matriks. Setiap nilai eigen harus diulang beberapa kali sama dengan multiplisitas aljabarnya.

Nilai eigen dari matriks Aadalah nilai-nilai skalar λseperti itu, untuk beberapa vektor kolom v, A*v = λ*v. Mereka juga solusi untuk polinomial karakteristik A: det(A - λ*I) = 0(di mana Iadalah matriks identitas dengan dimensi yang sama dengan A).

Output harus akurat hingga 3 digit signifikan. Semua input dan output akan berada dalam kisaran nilai numerik untuk bahasa pilihan Anda.

Builtin dapat diterima, tetapi Anda disarankan untuk memasukkan solusi yang tidak menggunakan builtin.

Uji Kasus

Dalam kasus uji ini, Imerupakan unit imajiner. Bilangan kompleks ditulis dalam bentuk a + b*I. Semua output memiliki 3 digit presisi yang signifikan.

[[42.0]] -> [42.0]
[[1.0, 0.0], [0.0, 1.0]] -> [1.00, 1.00]
[[1.0, 2.0, 3.0], [4.0, 5.0, 6.0], [7.0, 8.0, 9.0]] -> [16.1, -1.12, -1.24e-15]
[[1.2, 3.4, 5.6, 7.8], [6.3, 0.9, -5.4, -2.3], [-12.0, -9.7, 7.3, 5.9], [-2.5, 7.9, 5.3, 4.4]] -> [7.20 + 5.54*I, 7.20 - 5.54*I, -4.35, 3.75]
[[-3.22 - 9.07*I, 0.193 + 9.11*I, 5.59 + 1.33*I, -3.0 - 6.51*I, -3.73 - 6.42*I], [8.49 - 3.46*I, -1.12 + 6.39*I, -8.25 - 0.455*I, 9.37 - 6.43*I, -6.82 + 8.34*I], [-5.26 + 8.07*I, -6.68 + 3.72*I, -3.21 - 5.63*I, 9.31 + 3.86*I, 4.11 - 8.82*I], [-1.24 + 9.04*I, 8.87 - 0.0352*I, 8.35 + 4.5*I, -9.62 - 2.21*I, 1.76 - 5.72*I], [7.0 - 4.79*I, 9.3 - 2.31*I, -2.41 - 7.3*I, -7.77 - 6.85*I, -9.32 + 2.71*I]] -> [5.18 + 16.7*I, -24.9 - 2.01*I, -5.59 - 13.8*I, 0.0438 - 10.6*I, -1.26 + 1.82*I]
[[-30.6 - 73.3*I, 1.03 - 15.6*I, -83.4 + 72.5*I, 24.1 + 69.6*I, 52.3 + 2.68*I, 23.8 + 98.0*I, 96.8 + 49.7*I, -26.2 - 5.87*I, -52.4 + 98.2*I, 78.1 + 6.69*I], [-59.7 - 66.9*I, -26.3 + 65.0*I, 5.71 + 4.75*I, 91.9 + 82.5*I, -94.6 + 51.8*I, 61.7 + 82.3*I, 54.8 - 27.8*I, 45.7 + 59.2*I, -28.3 + 78.1*I, -59.9 - 54.5*I], [-36.0 + 22.9*I, -51.7 + 10.8*I, -46.6 - 88.0*I, -52.8 - 32.0*I, -75.7 - 23.4*I, 96.2 - 71.2*I, -15.3 - 32.7*I, 26.9 + 6.31*I, -59.2 + 25.8*I, -0.836 - 98.3*I], [-65.2 - 90.6*I, 65.6 - 24.1*I, 72.5 + 33.9*I, 1.47 - 93.8*I, -0.143 + 39.0*I, -3.71 - 30.1*I, 60.1 - 42.4*I, 55.6 + 5.65*I, 48.2 - 53.0*I, -3.9 - 33.0*I], [7.04 + 0.0326*I, -12.8 - 50.4*I, 70.1 - 30.3*I, 42.7 - 76.3*I, -3.24 - 64.1*I, 97.3 + 66.8*I, -11.0 + 16.5*I, -40.6 - 90.7*I, 71.5 - 26.2*I, 83.1 - 49.4*I], [-59.5 + 8.08*I, 74.6 + 29.1*I, -65.8 + 26.3*I, -76.7 - 83.2*I, 26.2 + 99.0*I, -54.8 + 33.3*I, 2.79 - 16.6*I, -85.2 - 3.64*I, 98.4 - 12.4*I, -27.6 - 62.3*I], [82.6 - 95.3*I, 55.8 - 73.6*I, -49.9 + 42.1*I, 53.4 + 16.5*I, 80.2 - 43.6*I, -43.3 - 3.9*I, -2.26 - 58.3*I, -19.9 + 98.1*I, 47.2 + 62.4*I, -63.3 - 54.0*I], [-88.7 + 57.7*I, 55.6 + 70.9*I, 84.1 - 52.8*I, 71.3 - 29.8*I, -3.74 - 19.6*I, 29.7 + 1.18*I, -70.6 - 10.5*I, 37.6 + 99.9*I, 87.0 + 19.0*I, -26.1 - 82.0*I], [69.5 - 47.1*I, 11.3 - 59.0*I, -84.3 - 35.1*I, -3.61 - 35.7*I, 88.0 + 88.1*I, -47.5 + 0.956*I, 14.1 + 89.8*I, 51.3 + 0.14*I, -78.5 - 66.5*I, 2.12 - 53.2*I], [0.599 - 71.2*I, 21.7 + 10.8*I, 19.9 - 97.1*I, 20.5 + 37.4*I, 24.7 + 40.6*I, -82.7 - 29.1*I, 77.9 + 12.5*I, 94.1 - 87.4*I, 78.6 - 89.6*I, 82.6 - 69.6*I]] -> [262. - 180.*I, 179. + 117.*I, 10.3 + 214.*I, 102. - 145.*I, -36.5 + 97.7*I, -82.2 + 89.8*I, -241. - 104.*I, -119. - 26.0*I, -140. - 218.*I, -56.0 - 160.*I]
Mego
sumber
Sandbox
Mego
2
Terkait Terkait
Martin Ender
Terkait ? Mungkin terkait ? (tergantung pada pendekatannya)
user202729

Jawaban:

12

Haskell , 576 554 532 507 byte

Tidak ada built-in!

import Data.Complex
s=sum
l=length
m=magnitude
i=fromIntegral
(&)=zip
t=zipWith
(x!a)b=x*a+b
a#b=[[s$t(*)x y|y<-foldr(t(:))([]<$b)b]|x<-a]
f a|let c=[1..l a];g(u,d)k|m<-[t(+)a b|(a,b)<-a#u&[[s[d|x==y]|y<-c]|x<-c]]=(m,-s[s[b|(n,b)<-c&a,n==m]|(a,m)<-a#m&c]/i k)=snd<$>scanl g(0<$c<$c,1)c
p?x|let f=foldl1(x!);c=l p-1;n=i c;q p=init$t(*)p$i<$>[c,c-1..];o=f(q p)/f p;a|d<-sqrt$(n-1)*(n*(o^2-f(q$q p)/f p)-o^2)=n/last(o-d:[o+d|m(o-d)<m(o+d)])=last$p?(x-a):[x|m a<1e-9]
z[a,b]=[-b/a]
z p=p?0:z(init$scanl1(p?0!)p)

Cobalah online!

Banyak terima kasih @ ØrjanJohansen untuk total -47 byte!

Penjelasan

Pertama ini menghitung polinomial karakteristik dengan algoritma Faddeev-LeVerrier yang merupakan fungsinya f. Kemudian fungsi zmenghitung semua akar polinomial itu dengan iterasi gyang menerapkan Metode Laguerre untuk menemukan root, setelah root ditemukan dihapus dan gdipanggil lagi sampai polinomial memiliki derajat 1 yang sepele dipecahkan oleh z[a,b]=[-b/a].

Tidak disatukan

Aku kembali inline fungsi sum, length, magnitude, fromIntegral, zipWithdan (&)serta pembantu kecil (!). Fungsi faddeevLeVerrierdapat disamakan dengan f, rootsuntuk zdan guntuk laguerremasing-masing.

-- Transpose a matrix/list
transpose a = foldr (zipWith(:)) (replicate (length a) []) a

-- Straight forward implementation for matrix-matrix multiplication
(#) :: [[Complex Double]] -> [[Complex Double]] -> [[Complex Double]]
a # b = [[sum $ zipWith (*) x y | y <- transpose b]|x<-a]


-- Faddeev-LeVerrier algorithm
faddeevLeVerrier :: [[Complex Double]] -> [Complex Double]
faddeevLeVerrier a = snd <$> scanl go (zero,1) [1..n]
  where n = length a
        zero = replicate n (replicate n 0)
        trace m = sum [sum [b|(n,b)<-zip [1..n] a,n==m]|(m,a)<-zip [1..n] m]
        diag d = [[sum[d|x==y]|y<-[1..n]]|x<-[1..n]]
        add as bs = [[x+y | (x,y) <- zip a b] | (b,a) <- zip as bs]
        go (u,d) k = (m, -trace (a#m) / fromIntegral k)
          where m = add (diag d) (a#u)


-- Compute roots by succesively removing newly computed roots
roots :: [Complex Double] -> [Complex Double]
roots [a,b] = [-b/a]
roots   p   = root : roots (removeRoot p)
  where root = laguerre p 0
        removeRoot = init . scanl1 (\a b -> root*a + b)

-- Compute a root of a polynomial p with an initial guess x
laguerre :: [Complex Double] -> Complex Double -> Complex Double
laguerre p x = if magnitude a < 1e-9 then x else laguerre p new_x
  where evaluate = foldl1 (\a b -> x*a+b)
        order' = length p - 1
        order  = fromIntegral $ length p - 1
        derivative p = init $ zipWith (*) p $ map fromIntegral [order',order'-1..]
        g  = evaluate (derivative p) / evaluate p
        h  = (g ** 2 - evaluate (derivative (derivative p)) / evaluate p)
        d  = sqrt $ (order-1) * (order*h - g**2)
        ga = g - d
        gb = g + d
        s = if magnitude ga < magnitude gb then gb else ga
        a = order /s
        new_x = x - a
ბიმო
sumber
1
Sebagai satu-satunya pengajuan yang tidak menggunakan builtin, ini harus menjadi jawaban dengan suara tertinggi.
Buah Esolanging
+1 untuk menghitung sesuatu yang terkait dengan penentu dalam waktu kurang dari n!!
user202729
Terima kasih teman-teman! @ user202729: Awalnya saya mengawasi !dan benar-benar bingung: D
ბიმო
6

Oktaf , 4 byte

@eig

Cobalah online!

Hanya dua byte lebih dari MATL yang setara dengan bahasa golf!

Menentukan pegangan fungsi anonim ke eigbuilt-in. Menariknya, filosofi desain MATLAB bertentangan dengan banyak bahasa high-end, yang suka digunakan DescripteFunctionNamesTakingArguments(), sedangkan MATLAB dan akibatnya Oktaf cenderung mendapatkan nama fungsi yang sesingkat mungkin. Misalnya, untuk mendapatkan s ubset dari eigenvalues (misalnya, terkecil nbesarnya mutlak), Anda menggunakan eigs.

Sebagai bonus, inilah fungsi (berfungsi di MATLAB, dan secara teori bisa bekerja di Oktaf tetapi fungsi mereka solvetidak sesuai dengan tugas) yang tidak menggunakan built-in, tetapi secara simbolis menyelesaikan masalah nilai eigen det(A-λI)=0,, dan mengubahnya ke bentuk numerik menggunakanvpa

@(A)vpa(solve(det(A-sym('l')*eye(size(A)))))
Sanchises
sumber
3

MATL , 2 byte

Yv

Cobalah online!

Penjelasan

Saya mengikuti saran biasa dalam aljabar linear numerik: alih-alih menulis fungsi Anda sendiri, gunakan built-in yang secara khusus dirancang untuk menghindari ketidakstabilan numerik.

Kebetulan, ini lebih pendek. ¯ \ _ (ツ) _ / ¯

Luis Mendo
sumber
Ini menimbulkan pertanyaan, berapa lama tanpa itu Yv?
Sanchises
@ Berasal saya tidak yakin. Saya mungkin akan melakukannya dengan mencari akar ( ZQ) dari polinom karakteristik. Tetapi secara eksplisit menghitung koefisien dari polinomial mungkin banyak pekerjaan
Luis Mendo
2

Mathematica, 11 byte

Eigenvalues

Cobalah online!

J42161217
sumber
Ya, saya mengharapkan jawaban bawaan sebelum mengklik "1 jawaban baru untuk pertanyaan ini". Mari kita tunggu jawaban non-builtin ... / Pada dasarnya solusi Mathematica sering <kata pertama dalam judul>
user202729
Built-in non-murni terpendek yang saya dapatkan adalah First@Eigensystem@#&(20 byte)
Tn. Xcoder
7
Saya sebenarnya setuju dengan user202729 di sini. Meskipun sangat menyenangkan untuk bercanda tentang Mathematica yang memiliki builtin untuk semuanya, itu sangat menjengkelkan baik sebagai poster tantangan dan menjawab untuk melihat jawaban builtin yang setara dengan sesuatu yang Anda coba relatif sulit untuk dilakukan. Golfing (IMO) adalah tentang mencoba menemukan algoritma terpendek dan implementasi dari algoritma tersebut, tetapi jawaban bawaan mengambilnya dari "olahraga".
caird coinheringaahing
2
@cairdcoinheringaahing Kita harus benar-benar mulai mempraktikkan proposal xnor .
Martin Ender
1

R , 22 byte

function(m)eigen(m)$va

Cobalah online!

Dibawa msebagai matriks. Frustasi, eigenfungsi dalam R mengembalikan objek kelas eigen, yang memiliki dua bidang values:, nilai eigen, dan vectors, vektor eigen.

Namun, yang lebih menjengkelkan, argumen opsional only.valuesmengembalikan a listdengan dua bidang, yang valuesberisi nilai eigen, dan vectors, disetel ke NULL, tetapi karena eigen(m,,T)juga 22 byte, ini merupakan pembasuhan.

Giuseppe
sumber
1

Julia , 12 byte

n->eig(n)[1]

Cobalah online!

Sayangnya, eigmengembalikan nilai eigen dan vektor eigen, sebagai tupel, jadi kami membuang 9 byte lagi untuk mengubah dan mengambil item pertama.

Uriel
sumber
0

Python + numpy, 33 byte

from numpy.linalg import*
eigvals
Uriel
sumber