Generieren symmetrischer positiver definitiver Matrizen mithilfe von Indizes

8

Ich habe versucht, Testfälle für CG auszuführen, und ich muss Folgendes generieren:

symmetrische positive definitive Matrizen
mit einer Größe> 10.000
VOLL DICHTE
Verwenden Sie nur Matrixindizes und gegebenenfalls 1 Vektor (wie $A(i,j) = \dfrac{x(i) - x(j)}{(i+j)}$ )
Mit einer Bedingungsnummer von weniger als 1000.

Ich habe versucht:

Generieren von Zufallsmatrizen mit A=rand(N,N)und dann A'ASym. PD. [Dies erhöht die Bedingungsnummer]
Wenn Sie den Vektor-Appraoch wie gezeigt verwenden, kann ich anscheinend keine Funktion erhalten, (x,i,j)die Sym und PD gewährleistet.

Nach langem Experimentieren kam ich auf Folgendes:

a(it,jt) = (vec(it)+vec(jt))/((it-1)^2+(jt-1)^2);Wenn $it \neq jt$

a(it,it) = x(it)wenn $it=jt$

Aber das ist PD bis etwa 500x500.

XLATMR . [Bei all der Einstufung und Skalierung ist es zu schwer zu verstehen. Zumal ich die zugrunde liegende lineare Algebra nicht verstehen kann]

Kann mir jemand eine Funktion in x (Vektor) und i, j (Indizes) geben, die die oben genannten Anforderungen erfüllt?

linear-algebra Anfrage
quelle

1

Versuchen Sie , den diagonalen Einträgen Ihrer Matrix eine große Zahl

(in der Reihenfolge der Bedingungsnummer) hinzuzufügen . Dies entspricht dem Hinzufügen von

zu jedem Ihrer Eigenwerte und sollte die Bedingungsnummer verbessern.

α

$\alpha$

α

$\alpha$

Aron Ahmadia

@ AaronAhmadia, funktioniert hervorragend! Vielen Dank! Welche große Anzahl sollte ich jedoch hinzufügen? Ich habe N selbst ausprobiert und es hat bis 5000x5000 funktioniert (gerade abgeschlossene Simulationen). Wird die Verwendung a+N*eye(N,N)sicherstellen, dass es für alle Werte über 5000 funktioniert? Können Sie Ihren Kommentar in eine Antwort umwandeln?

Untersuchung

10

$c$ $D$ $[1,c]$ $1$ $c$ $u$ $A:=(I-tuu^T)D(I-tuu^T)$ $t=2/u^Tu$

$O(n^2)$ $v:=Du$ $s:=t^2u^Tv/2$ $w:=tv-su$ $O(n)$ $A$ $A=D-uw^T-wu^T$ $u$ $O(n)$

$D$

$\alpha$ $A$ $\alpha$ $\alpha=\|A\|$

Arnold Neumaier
quelle

Dies ist perfekt!

Untersuchung

Wie soll ich den Algorithmus ändern, um mir Matrizen bereitzustellen, wenn ich die Eigenwerte bereitstelle? Zum Beispiel möchte ich eine nicht symmetrische Matrix mit Eigenwerten 1,-1,2,-2...50,-50.

Untersuchung

1

D = D i a g (- 50 : 50)

$D=Diag(-50:50)$ im obigen Rezept gibt Ihnen diese Eigenwerte, aber mit dieser Auswahl ist die Matrix jetzt symmetrisch unbestimmt, und CG würde ein solches Problem nicht lösen. Und in Ihrem Kommentar fragen Sie sogar nach einer unsymmetrischen Matrix, wehre CG gilt auch nicht. Vielleicht ist es am besten, eine neue Frage zu stellen, mit was genau Sie wollen.

Arnold Neumaier

3

Versuchen Sie , den diagonalen Einträgen Ihrer Matrix eine große Zahl (in der Reihenfolge der Norm der Matrix) hinzuzufügen . Dies entspricht dem Hinzufügen von zu jedem Ihrer Eigenwerte und sollte die Bedingungsnummer verbessern, indem die Lücke zwischen dem größten und dem kleinsten Eigenwert verringert wird. $\alpha$ $\alpha$

Aron Ahmadia
quelle

1

Referenz siehe en.wikipedia.org/wiki/Tikhonov_regularization

Emre

2

Ich bin mir nicht sicher, wie Sie es mit nur einem Vektor machen würden, aber mit zwei Zufallsvektoren und der Größe können Sie über eine positive Matrix erzeugen wobei eine Drehung in der Ebene der Achsen und . $x$ $\theta$ $N$

U = \prod_{i} R_{i} (θ_{i}) A = U diag (abs (x)) U^{*}

$U=\prod_i R_i(\theta_i)\\ A=U\mbox{diag}(\mbox{abs}(x)) U^\ast$

R_{i} (\cdot)

$R_i(\cdot)$

i

$i$

i + 1 mod N

$i+1 \mbox{ mod } N$

Wenn Sie die Bedingungsnummer verbessern möchten, können Sie einen festen positiven Wert hinzufügen und gegebenenfalls neu skalieren. $x$

Todesatem
quelle

Es tut mir leid, aber meine Mathematik ist noch nicht so toll. Bedeutet Transponieren? Was bedeutet Rotation in der Ebene? Das Speichern von 2 Vektoren ist zwar etwas teuer, aber dennoch sieht dieser Look sehr interessant aus.

U^{*}

$U^*$

Untersuchung

R_{i} (θ_{i}) = (\begin{matrix} 1 & 0 & \dots \\ 0 & ⋱ \\ \cos θ_{i} & \sin θ_{i} \\ - \sin θ_{i} & \cos θ_{i} \\ 1 \\ ⋱ \end{matrix})

$R_i(\theta_i)=\left(\begin{matrix} 1 & 0 & \cdots \\ 0 & \ddots \\ &&\cos \theta_i & \sin \theta_i \\ & & -\sin \theta_i & \cos \theta_i\\ & & & &1 \\ && & & & \ddots\end{matrix}\right)$ ist die Rotationsmatrix. bezeichnet die komplexe konjugierte transponierte Matrix (vorausgesetzt, alles ist real, es ist nur die Transponierte).

U^{*}

$U^\ast$

Todesatem

2

Ein ganz anderer Weg wäre wie folgt : Betrachten Sie einen Zufallsvektor , dann ist eine Rang-Eins-Matrix mit Eigenwerten gleich Null und einem streng positiven Eigenwert gleich mit Eigenvektor . Es ist auch symmetrisch. $x$ $A=xx^T$ $N-1$ $\|x\|^2$ $x$

Um eine dichte SPD-Matrix zu erstellen, addieren Sie viele solcher Rang-1-Matrizen. Mit anderen Worten, wenn Sie Vektoren (z. B. Zufallsvektoren), dann ist SPD, wenn und wenn die Vektoren linear unabhängig sind (wenn sie nicht linear unabhängig sind, dann ist positiv semidefinit). Mit der sukzessiven Gram-Schmidt-Orthogonalisierung können Sie überprüfen, ob Ihre Vektoren (oder die ersten Vektoren, die Sie aus dem Zufallsprozess zeichnen) linear unabhängig sind. Sie erhalten jedoch wahrscheinlich auch eine SPD-Matrix, wenn Sie einfach wählen Vektoren. $M$ $x_i$

A = \sum_{i = 1}^{M} x_{i} x_{i}^{T}

$A = \sum_{i=1}^M x_i x_i^T$

M \geq N

$M\ge N$

x_{i}

$x_i$

A

$A$

M

$M$

M \geq N

$M\ge N$

M ≫ N

$M \gg N$

Wolfgang Bangerth
quelle

Generieren symmetrischer positiver definitiver Matrizen mithilfe von Indizes

Antworten: