Seite 1 von 1

Vl. 8, Fixpunktiteration

Verfasst: 8. Dez 2010 18:50
von igor.a
Hallo,
in der Vorlesung wurde als Konvergenzkriterium für die FPI genannt, dass die Eigenwerte der Jacobimatrix >=0 und <1 sind (Folie 11).
Nun habe ich das Thema gegoogelt und fast überall ist vom Banachschen Fixpunktsatz die Rede, wenn es um die Konvergenz geht. Der besagt im Wesentlichen, dass wenn
für alle x, y ||f(x)-f(y)|| < || x - y||,
dann \(x_{i+1} = f(x_i)\) konvergiert.

Ist das Kriterium aus der Vorlesung eine Abwandlung davon? Wenn ja, würde mich interessieren, wie es aus diesem Satz hergeleitet werden kann.

Re: Vl. 8, Fixpunktiteration

Verfasst: 9. Dez 2010 15:38
von dschneid
Das habe ich mich auch gefragt, und mal ein bisschen recherchiert.

Der Banachsche Fixpunktsatz, der die Fixpunktiteration ermöglicht, setzt voraus, dass die iterierte Funktion eine Kontraktion ist, also \(\| \, f(x) - f(y) \| \leq L \| x - y \|\) mit \(0 \leq L < 1\). Das Kriterium von den Folien ist eine Formulierung eines Spezialfalls dieser Voraussetzung, in dem man die Kontraktionseigenschaft über die Beschränktheit der Norm der Jacobi-Matrix herleitet:

Sei \(U \subset \mathbb{R}^n\) und \(f: U \to U\) stetig differenzierbar. Die Jacobi-Matrix von \(f\) heiße \(f'\). Für \(x, y \in U\) gilt bezüglich einer beliebigen Norm \(\| \cdot \|\): \(\| \, f(x) - f(y) \| = \| \int_0^1 \! f'(x + t(y - x)) \, \mathrm{d}t \cdot (x - y) \| \leq \int_0^1 \! \| \, f'(x + t(y - x)) \| \, \mathrm{d}t \cdot \| x - y \|\) wegen dem Mittelwertsatz der Differentialrechnung für vektorwertige Funktionen. Da \(\forall t \in [0, 1]: x + t(y - x) \in U\), gilt außerdem, dass \(\forall t \in [0, 1]: \| \, f'(x + t(y - x)) \| \leq \max_{c \in U} \| \, f'(c) \| =: m\). Man erhält also \(\| \, f(x) - f(y) \| \leq \int_0^1 \! m \, \mathrm{d}t \cdot \| x - y \| = m \cdot \| x - y \|\).

Nimmt man nun an, dass \(m < 1\), dann erhält man mit \(L := m\) sofort wie gewünscht ein L mit \(0 \leq L < 1\), sodass \(\| \, f(x) - f(y) \| \leq L \cdot \| x - y \|\), womit f eine Kontraktion ist, weshalb eine Fixpunktiteration (nach dem Banachschen Fixpunktsatz) funktioniert.

Wählt man nun als \(U\) eine Umgebung um den Fixpunkt \(x_s\), dann erhält man schon fast das Kriterium aus den Folien: Man braucht dann nur zu überprüfen, ob \(\| \, f'(x_s) \| < 1\). Wenn dies der Fall ist, dann ist dies auch überall in einer passend gewählten Umgebung der Fall. Dass auf den Folien steht, der Startwert muss "nahe genug" an \(x_s\) liegen, bedeutet, dass er in der Umgebung \(U\) liegen muss.

In diesem Argument kommen keine Eigenwerte von \(f'\) vor, stattdessen aber Matrixnormen, zum Beispiel \(\| \, f'(x_s) \|\). Für beliebige Matrixnormen gilt allerdings, dass die Norm einer Matrix immer größer oder gleich dem betragsmäßig größten Eigenwert der Matrix ist. Wenn also \(\| \, f'(x_s) \| < 1\) ist, dann bedeutet dies, dass auch alle Eigenwerte von \(f'\) kleiner als 1 sein müssen, also im Einheitskreis liegen. Es gibt zudem Matrixnormen, die von oben beliebig nahe an den betragsmäßig größten Eigenwert herankommen. Das bedeutet, dass man das Kriterium \(| \lambda_{max} | < 1\) als "Ersatz" für die Kriterien \(\| \, f'(x_s) \| < 1\) bezüglich allen beliebigen Normen nehmen kann.

Somit erhält man auch das zweite Kriterium von den Folien, dass alle Eigenwerte der Jacobi-Matrix im Fixpunkt im Einheitskreis liegen müssen.

Ich hoffe, das stimmt soweit. Ich bin ja kein Mathematiker... :wink:

Re: Vl. 8, Fixpunktiteration

Verfasst: 9. Dez 2010 23:20
von igor.a
Danke für die ausführliche Antwort :)
Wo ich nicht ganz überzeugt bin, ist aber der Zusammenhang zwischen der Matrixnorm von f' und dem betragsgrößten Eigenwert von f'. Dieser ist immer kleiner gleich der Norm. Ist er kleiner 1, folgt daraus noch nicht, dass auch die Norm kleiner 1 ist (was nötig wäre).
Die Gleichheit vom betragsmäßig größten EW und der Norm hat man (so meine Recherche) nur bei symmetrischen Matrizen.

Re: Vl. 8, Fixpunktiteration

Verfasst: 10. Dez 2010 00:31
von dschneid
Mich hat das auch eine Weile lang stutzig gemacht. Der Punkt scheint aber folgender zu sein: Es geht wohl nur darum, dass eine beliebige Matrixnorm der Jacobi-Matrix kleiner als 1 ist. Da es anscheinend immer Normen gibt, deren Fehler der Abschätzung des betragsgrößten Eigenwertes beliebig klein wird, kann man den Eigenwert quasi als "Grenzwert" dieser Normen nehmen: Wenn der Eigenwert kleiner als 1 ist, gibt es eine unmittelbar darüberliegende Matrixnorm, die ebenfalls kleiner als 1 ist, womit das Kriterium schon erfüllt ist. Das kommt mir allerdings auch ziemlich wackelig vor. Ich habe bei meiner Suche tatsächlich auch keine Formulierungen gefunden, die von Eigenwerten sprachen, sondern immer nur von Normen.

Es drängt sich also tatsächlich der Gedanke auf, dass das Kriterium von den Folien nicht alle Fälle erfasst, beziehungsweise allenfalls ein Ausschlusskriterium ist (denn diese Richtung funktioniert ja einwandfrei).

Nachtrag: Wenn man nach "Fixpunktiteration Spektralradius" sucht, findet man einige brauchbare Ergebnisse, welche die obige Argumentation stützen (natürlich mit etwas Epsilontik). Es scheint also doch was dran zu sein...

Re: Vl. 8, Fixpunktiteration

Verfasst: 12. Dez 2010 14:44
von Stumpf.Alex
Eure Ansätze sind bereits gut und führen auf den richtigen Weg. Allerdings braucht man tatsächlich die Implikation:

Spektralradius (betragsmäßig größter EW) < 1 => Matrixnorm < 1

um von dem Kriterium der Vorlesung nach Banach schließen zu können. Im Anhang befindet sich eine ausführliche Erläuterung, welche von den Assistenten extra angefertigt wurde.

Re: Vl. 8, Fixpunktiteration

Verfasst: 13. Dez 2010 10:14
von igor.a
Im Anhang befindet sich eine ausführliche Erläuterung, welche von den Assistenten extra angefertigt wurde.
Klasse! Danke :)