Vl. 8, Fixpunktiteration

Benutzeravatar
igor.a
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 143
Registriert: 28. Sep 2009 16:05

Vl. 8, Fixpunktiteration

Beitrag von igor.a » 8. Dez 2010 18:50

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.

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: Vl. 8, Fixpunktiteration

Beitrag von dschneid » 9. Dez 2010 15:38

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:

Benutzeravatar
igor.a
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 143
Registriert: 28. Sep 2009 16:05

Re: Vl. 8, Fixpunktiteration

Beitrag von igor.a » 9. Dez 2010 23:20

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.

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: Vl. 8, Fixpunktiteration

Beitrag von dschneid » 10. Dez 2010 00:31

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...

Stumpf.Alex
Nerd
Nerd
Beiträge: 643
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Re: Vl. 8, Fixpunktiteration

Beitrag von Stumpf.Alex » 12. Dez 2010 14:44

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.
Dateianhänge
fixpunkt_konvergenz.pdf
Erklärung Banach
(79.63 KiB) 135-mal heruntergeladen

Benutzeravatar
igor.a
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 143
Registriert: 28. Sep 2009 16:05

Re: Vl. 8, Fixpunktiteration

Beitrag von igor.a » 13. Dez 2010 10:14

Im Anhang befindet sich eine ausführliche Erläuterung, welche von den Assistenten extra angefertigt wurde.
Klasse! Danke :)

Antworten

Zurück zu „Archiv“