Startwertbestimmung

Riemer [ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

Startwertbestimmung

Die Konvergenz eines Iterationsverfahrens hängt immer von dem gewählten Startwert ab. So tritt bei vielen nichtlinearen Gleichungssystemen nur dann ausreichend schnelle Konvergenzgeschwindigkeit auf, wenn der Startwert in einer (kleinen) Teilmenge des Einzugsbereiches liegt. Meist liegt diese Teilmenge in der Nähe der gesuchten Lösung. In der Praxis stellt das Finden eines geeigneten Startwertes eines der schwierigsten Probleme beim Lösen nichtlinearer Gleichungssysteme dar. Diese Schwierigkeit steigt mit zunehmender Dimension des Problems.

Zufallsuche

Zur Bestimmung eines günstigen Startwertes x⁽⁰⁾, der mit möglichst hoher Wahrscheinlichkeit im Einzugsbereich der Lösung x^* liegt, kann man dem Iterationsverfahren eine Zufallssuche voranstellen. Dabei wird meist angenommen, daß die Lösung in einem n-dimensionalem Hyperquader

$D:=\left[ a_1,b_1\right] \times \left[ a_2,b_2\right] \times ...\left[a_n,b_n\right] \subset \BbbR ^n$

liegt. Durch Erzeugen von n unabhängigen Zufallszahlen z₁,..., z_n, die in den Intervallen [aⁱ,bⁱ] entsprechend einer stetigen Gleichverteilung bestimmt werden, erhält man einen Zufallspunkt

$z=(z_{1},...,z_{n})^T\in \overset{n}{\underset{i=1}{\prod }}\left[a_i,b_i\right] =D$

mit der gewünschten Gleichverteilung. Man erzeugt nun eine größere Anzahl von derartigen Zufallspunkten und nimmt jenen Punkt z mit dem kleinsten Residuum als Startwert für ein iteratives Verfahren.

Beispiel Kugelumgebung

Die Auswirkungen der Dimension lassen sich an einer einfachen Modellüberlegung demonstrieren. Falls der praktisch nutzbare Einzugsbereich die Einheitskugelumgebung

$K_{n}:=\left\{ x:\left( x_1-x_i^{*}\right) ^2+...+(x_n-x_n^{*})^2\leq1\right\}$

um die Lösung x^* ist und für die oben beschriebene Zufallssuche der Würfel

$Q_{n}:=\left\{ x:\left| x_i-x^{*}\right| \leq 5,i=1,2,...,n\right\}$

mit der Seitenlänge 10 angenommen wird, so ist die Wahrscheinlichkeit, daß ein n-dimensionaler Vektor x⁽⁰⁾ aus Q_n ein geeigneter Startwert ist, gegeben durch

$P_{n}=\frac{Volumen\,(K_n)}{Volumen\,(Q_n)}$

Für n=1, 50, 100 erhält man folgende Werte:

n Volumen (K_n) Volumen (Q_n) P_n

1 2 10¹ 2.00*10^-1

50 1.73*10^-13 10⁵⁰ 1.73*10^-63

100 2.37*10^-40 10¹⁰⁰ 2.37*10^-140

Unter den getroffenen, für manche Probleme charakteristischen Annahmen geht die Wahrscheinlichkeit, einen brauchbaren Startwert durch Zufallssuche zu erhalten, mit steigender Dimension exponentiell gegen Null. Bereits bei n=7 ist unter den getroffenen Annahmen das Auffinden eines brauchbaren Startwertes ungefähr gleich wahrscheinlich wie ein (österreichischer) Lottosechser, nämlich

$\frac 1{\QOVERD( ) {45}{6}}\approx 1.68\cdot 10^{-7}$

Die Startwertbestimmung bei n=100 entspricht in ihrer Schwierigkeit bereits der Suche nach einem ganz bestimmten Molekül im gesamten Weltall.

Das Beispiel zeigt die Notwendigkeit, bei hochdimensionalen Problemen alle verfügbaren Informationen zur Startbestimmung auszunutzen. Eine reine Zufallssuche ist nahezu aussichtslos.

Beispiel Monte-Carlo-Suche nach Nullstellen

Bei einem System von 20 nichtlinearen Gleichungen wurden mit Hilfe von gleichverteilten Zufallszahlen Punkte

$x\in \left[ a_1,b_1\right] \times \left[ a_2,b_2\right] \times ...\times\left[ a_{20},b_{20}\right] \subset \BbbR ^{20}$

gesucht, die ein möglichst kleinen Residuum

$\left\| F(x)\right\| _2$

besitzen, also die Gleichungen möglichst gut erfüllen. In der untenstehenden Abbildung ist der Verlauf dieser Zufallssuche dargestellt, wobei die treppenförmige Kurve dem jeweils kleinsten bei der Suche gefundenen Residuum entspricht. Man sieht deutlich, wie rasch der Aufwand - die Anzahl der versuchsweise zu berechnenden Funktionswerte - wächst, wenn man eine weitere Verkleinerung des Residuums erreichen will.

Verkleinerung des Residuums einer Funktion

$F:$ R$^{20}\rightarrow R^{20}$

bei Monte-Carlo-Suche. Zufallspunkte, deren Residuum größer war als das bisher kleinste Residuum, wurden in der Darstellung nicht berücksichtigt.

Homotopie

Liegt keine gute Startnäherung vor, so kann man oft mit Homotopie- oder Fortsetzungsverfahren zu einer (Näherungs-) Lösung gelangen. Dabei wird durch einen Problemparameter oder durch einen künstlich eingeführten Parameter

$\lambda \in \BbbR$

aus einem System von n Gleichungen in n Unbekannten eine Familie von Problemen

$H(x,\lambda )=0,$

deren Lösungen

$x^{*}(\lambda )$

unter bestimmten Voraussetzungen stetig von

$\lambda$

abhängen.

Unter derartigen Voraussetzungen hat die obenstehende Gleichung eine (eindimensionale) Lösungskurve als Lösungsmenge.

In vielen praktischen Situationen hängt das Problem in natürlicher Weise von einem Parameter ab. Wenn dies nicht der Fall ist, kann z.B.

$H(x,\lambda ):=F(x)+(\lambda -1)F(x^{(0)})$

zur Definition einer Lösungskurve

$H(x(\lambda ),\lambda )$ = 0, \lambda $\in \left[ 0,1\right]$

verwendet werden, deren Endpunkte x(0)=x⁽⁰⁾ und x(1)=x^* sind. Um von x⁽⁰⁾ zu x^* zu gelangen, kann man das Intervall [0,1] durch

$0=\lambda _{0}<\lambda _1<...<\lambda _K=1$

unterteilen und die Folge von nichtlinearen Gleichungssystemen

$$H(x,\lambda _{k})=0,$ k=1,2,...,K,$

sukzessive lösen, wobei die Nullstelle x^(k) des k-ten Gleichungssystems jeweils als Startwert zur Lösung des (k+1)-ten Gleichungssystems verwendet werden kann. Wenn man die Abstände

$\lambda _{k+1}-\lambda _k$

klein genug wählt, kann man damit rechnen, daß x^(k) eine ausreichend genaue Start-Näherung für die iterative Bestimmung von x^(k+1) darstellt.

Beispiel Transportnetz

Die Flüsse in den Kanten eines nichtlinearen Transportnetzes sind Null, solange keine Transportanforderungen bestehen. Durch sukzessives Erhöhen der Anforderungen (evtl. bis in den Sättigungsbereich) erhält man in natürlicher Weise eine Folge nichtlinearer Probleme.

Minimierung

Eine andere Möglichkeit, von einem schlechten Startpunkt in die Nähe der Lösung zu gelangen, besteht in der Anwendung von Minimierungsverfahren auf die Funktion

$\Phi :=\left\| F\right\| :\BbbR ^{n}\rightarrow \BbbR ^n$

Der Einzugsbereich der langsam konvergierenden Gradientenverfahren ist im allgemeinen größer als jener der rasch konvergenten Nullstellenverfahren.

[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

n	Volumen (K_n)	Volumen (Q_n)	P_n
1	2	10¹	2.00*10^-1
50	1.73*10^-13	10⁵⁰	1.73*10^-63
100	2.37*10^-40	10¹⁰⁰	2.37*10^-140