Maximumsnorm der Lösung eines unterbestimmten LGS

13.01.2016, 13:59	Sobey	Auf diesen Beitrag antworten »
Maximumsnorm der Lösung eines unterbestimmten LGS Meine Frage: Hallo Menschen, ich habe eine Frage, bei der ich ohne weiteres nicht weiter komme. Meine Aufgabe ist es, eine Ansteuerung für einen Kran zu finden und eh man es sich versieht, habe ich ein Lineares Gleichungssystem mit 4 Zeilen und beliebig vielen Spalten (praktisch gesehen reicht 100 oft schon aus). $\begin{eqnarray} A \in \mathbb{R}^{4x100} \end{eqnarray}$ und $\begin{eqnarray} b\in \mathbb{R}^4 \end{eqnarray}$ Meine Aufgabe ist es nun, die Lösung $\begin{eqnarray} x \end{eqnarray}$ zu finden, deren Maximumsnorm $\begin{eqnarray} \vert x \vert_{\infty} \end{eqnarray}$ minimal wird. Meine Ideen: 1. Derzeit löse ich das Gleichungssystem mit der Moore Penrose-Inversen der Matrix und erhalte so eine Lösung mit minimaler 2-Norm. Von dieser nehme ich die extremalen Werte (positiv und negativ) und setze diese auf einen klein wenig geringeren Wert (Faktor ca. 0.999). Ich bringe die fixierten Werte auf die rechte Seite und löse das entstehende (kleinere) Gleichungssystem ebenfalls mit der Moore-Penrose-Inversen. Gibt es jetzt Werte im neuen Lösungsvektor die die vorher gesetzte Grenze überschreiten, werden sie wieder auf diese Grenze gesetzt. (Klingt grade komplizierter, als es ist... ) Erst wenn ich eine gesicherte Lösung gefunden habe, die innerhalb forcierter Norm-Grenzen liegt, verringere ich die Grenzen weiter nach innen. Wenn ich eine Lösung $\begin{eqnarray} x \end{eqnarray}$ mit $\begin{eqnarray} \vert x \vert_{\infty} = k \end{eqnarray}$ gefunden habe, ist dies sicher eine Lösung und die Minimale Norm ist nach oben durch $\begin{eqnarray} k \end{eqnarray}$ beschränkt. Ich kann aber nicht beweisen, dass es keine Lösung mit kleinerer Norm gibt oder wie ich sie finden kann, wenn sie existiert. Die gegen Ende entstehenden Probleme sind teilweise sehr schlecht konditioniert und wenn ich beliebige Lösungen des LGS nehme, bekomme ich meist schlechtere Werte für die Max-Norm. 2. Ein anderer Ansatz ist Minimierung mit linearen Nebenbedingungen. Allerdings ist die Maximums-Norm nicht gewöhnlich differenzierbar und p-Normen mit $\begin{eqnarray} p \mapsto \infty \end{eqnarray}$ bringt wieder enorm schlechte Numerische Kondition in der Ableitung.
14.01.2016, 23:34	Sobey	Auf diesen Beitrag antworten »
Ich habe tatsächlich eine eigene Lösung gefunden! Falls jemand sich dafür interessiert oder das sucht, gebe ich hier die Antwort: Wenn $\begin{eqnarray} x \end{eqnarray}$ ein Vorschlag für eine Lösung mit minimaler Norm ist (aber auf jeden Fall das LGS löst), so gibt es eine/mehrere Indices mit extremalem Wert (die also für die Norm ausschlaggebend sind). $\begin{eqnarray} \hat I = \{ i : x_i = \|x\|_\infty\} \end{eqnarray}$ und $\begin{eqnarray} \tilde I = \{ i : x_i = -\|x\|_\infty\} \end{eqnarray}$ Sei nun $\begin{eqnarray} K \end{eqnarray}$ der Kern der Matrix ( $\begin{eqnarray} AK=0 \end{eqnarray}$ ) und $\begin{eqnarray} k_i \end{eqnarray}$ die ite Zeile der Matrix. Die Lösung ist genau dann optimal, wenn das Problem $\begin{eqnarray} <br /> k_{\hat I} \cdot q < 0, \quad k_{\tilde I} \cdot q>0<br /> \end{eqnarray*}$ (Elementweise Relation) keinen zulässigen Punkt hat. Idee dahinter ist: - Erzeuge eine Linear-Kombination der Spalten von K, die dann noch das LGS löst (weil sie ja im Kern von A liegt) - Forciere für diese Linearkombination, dass sie für die Einträge in u, die "am Rand" liegen, nach innen geschoben werden. Dies muss für alle außen liegenden Punkte gelten. Das Verfahren lässt sich auch konstruktiv anwenden (ist allerdings ineffizient). Dient also eher der Verifikation.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »