Matematické Fórum

Sustava ma prave jedno riesenie ak je matica regularna, mam napad ako zabezpecit regularitu pri danej hustote prvkov, ale kladnu definitnost zatial neviem.

Ak si zoberies uplne lubovolnu maticu , tak potom

bude regulana ak zoberies dostatocne male konretne potrebujes ale potom je regularna aj matica - co je vyhodnejsie ak chces mat cele cisla. T.j. moj navod je takyto

zober si uplne lubovolu maticu (s danou hustotou nenulovych prvkov ako potrebujes) vypocitaj jej Frobeniovu normu

a zvol si nejake cele cislo a potom poloz - hustota nenulovych prvkov sa ti moze zmenit maximalne o - kde n je rozmer matice, co by snad pre velke nemusel byt problem.

BTW: aku hustotu nenulovych prvkov priblizne potrebujes.

Ahoj, veľká vďaka, že si mi napísal, zatiaľ tomu rozumiem len čiastočne, ale dumám nad tým. Možno sem teraz napíšem aj blbosť, ale to vyplýva z prvej vety tohto príspevku.
Hustotu chcem mať takú, aby v matici bolo maximálne do 20 miliónov prvkov, teda qôli obmedzeniam veľkosti RAM pamäti počítača. T. j. pri matici n=50000 by bola hustota max. 0.8 %, pri n=10000 max. 20 %. Programujem to tak, že indexy mám v ushort, teda v 16-bitovej premennej, takže maximálne bude n=65536. ;)

Pochopil som to správne?

A=I+vv^{T}
v=(1 2 3)
neviem, ako sa v Latexe píše matica, takže
a11=1^2+1
a12=1*2
a13=1*3
a21=2*1
a22=2^2+1
a23=2*3
a31=3*1
a32=3*2
a33=3^2+1

takže
    (2 2 3)
A=(2 5 6)
    (3 6 10)

som ju skontroloval v mojej aplikácii, je kladne definitná. Len ja som zle pochopil z literatúry. Myslel som si, že aii musí byť väčší alebo rovný ako súčet ostatných prvkov v riadku resp. v stlpci. A zrejme postačuje ak je väčší alebo rovný najväčšiemu prvku v riadku, či stĺpci.

Obdivujem Ťa, excelentný nápad :)
Som ja so svojimi vedomosťami ešte ďaleko od toho, aby som tak do toho videl ako Ty, aby som niečo takéto dal.

Opýtam sa, ak mám užívateľom zadanú maticu a chcem skontrolovať, či je kladne definitná, stačí ak overím symetrickosť a potom pomocou Choleského rozkladu, zistím, že nevznikne žiaden prvok na diagonále, ktorý by bol rovný nule alebo mal imaginárnu zložku? Stačí len tieto 2 veci overiť? Dík.

Ehm, asi som sa pomýlil, myslím, že stačí len overiť pomocou Choleského rozkladu, veď ak je kladne definitná, je aj symetrická a aj regulárna, že?

Ale čo ak mám užívateľom zadanú maticu a chcem vedieť, či má práve jedno riešenie, teda h(A) = n, či ako sa zapisuje že hodnosť matice A je rovná stupňu matice. Viem, že je singulárny rozklad, SVD, ale neviem ho použiť, hľadal som niekde postup, ale asi je to pre mňa príliš komplikované. Je nutné pri SVD vypočítať vlastné čísla ? Lebo niekde to používajú a niekde nie, teda je asi viacero verzií. Hľadám takú, ktorá je čo najviac numericky stabilná. Ak poznáš literatúru, kde je SVD algoritmus normálne uvedený, privítam to. Ešte raz veľký dík.

(Som Ti napísal do "reputácie", ale omylom som tam napísal "matematická" namiesto "lineárna") :-o

co sa tyka nejakych efektivnych algoritmov na overovanie kladnej definitnosti, tak neviem poradit - vyzera, ze ta choleskeho dekompozicia funguje iba na symetricke matice, ale uprimne .. moc sa v tom nevyznam (to je z mojho pohladu uz numericka matematika)

ono plati ze ak je matica pozitivne definitna tak je aj regularna (co je pre stvorcove matice to iste ako, ze hodnost je rovna rozmeru), btw regularnost sa da testovat aj tak, ze vypocitas determinant a pozries sa ci je rozny od nuly - ale to moze byt pre obrovske matice problematicke

avsak pozor kladne definitna matica nemusi byt nutne symetricka.

ten sposob na generovanie co ma napadol vsak vyrobi vzdy symetricku maticu, ale to som predpokladal, ze by nemusel byt problem.

inak cele to vychadza z takejto uvahy:

pozorovanie 1: sucet kladne semi-definitnych matic je kladne semi-definitna matica, avsak ak je z nich apon jedna kladne definitna, tak vysledok bude kladne definitna matica.

pozorovanie 2: pre lubovolnu maticu je kladne semi-definitna a symetricka

pozorovanie 3: lubovolna diagonalne matica, ktora ma vsetky prvny na diagonale kladne je kladne definitna.

takze najjednoduchsia moznost bola zobrat lebo vektor je taka jednoducha matica a jednotkova je zase taka co najjednoduchsia diagonalna

ale mohol by si zobrat aj trebars
kde D je diagonalna s kladnymi clenmi na diag., A je lubovolna a B je lubovolna antisymetricka
(totizto antisymetricke matice su kladne semi-definitne) - a takto by si vedel vygenerovat aj nesymetricke matice
len si musis dat pozor na to co sa deje s tou hustotou nenulovych prvkov.

cize chces nieco taketo:



(D je diagonalna - nemusi byt nutne jednotkova staci ak ma kladne prvky)
v - ma k nenulovych prvkov a n-k nulovych
w - ma n-k nenulovych prvkov a k nulovych
a to tak, ze sa tie prekryvaju nuly jedneho s nenulami druheho

potom bude vysladna matica kladne definitna (a teda samozrejme aj regularna) a nebude mat ziaden trivialny (s iba jednym nenulovym cislom) riadok ci stlpec.

Pocet nenulovych prvkov bude takze hustota bude aspon 0.5 co velmi nevyhovuje tvojim podmienkam, takze na to treba ist trochu inak

keby si ale zobral viac vektorov povedzme a to az s tym ze pocty nenulovych prvkov by mali zaradom az a to zase tak aby na i-tej pozicii mal prve jeden z nich nenulovy prvok a ostatne nulove
napr.
( 1, 2, 0, 0, 0, 0)
( 0, 0,-1,-2, 0, 0)
( 0, 0, 0, 0, 1,-1)
tak potom matica
bude kladne definitna a bez trivialnych riadkov a pocet nenulovych prvkov bude mat

pricom minimum dosiahneme ak co zodpoveda potom vyslednej hustute

teda v tvojom pripade n=50000 by si potreboval 125 takychto vektorov a kazdy so 400 nenulovymi prvkami a budes mat vyslednu hustotu 0.008 aku si chcel

este poznamenajme, ze vlastne vsetky tie vektory mozes napchat do jedneho pola velkosti n x 2
v[i,j] kde v[i,0] je nenulove cislo a v[i,1] je cislo od 1 do p ktore ti povie o ktory vektor sa vlastne jedna
a tu diagonalnu (ak by si chcel nieco ine ako jednotkovu) tak tiez napchas do pola D velkosti n

for (i=0,i<n,i++){
A[i,i]=D[i]+v[i,0]^2
for(j=i+1,j<n,j++)
    if (v[i,1]==v[j,1]) then A[i,j]=A[j,i]=v[i,0]*v[j,0]
    else A[i,j]=A[j,i]=0
}