Iterative Verfahren < Nichtlineare Gleich. < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 20:50 So 06.02.2005 | | Autor: | Maison2000 |
Ich habe diese Frage auf keiner anderen Internetseiten gestellt!
Hallo zusammen
Welche Bedingungen müssen für das Fixpunktverfahren erfüllt sein um es anzuwenden?
Bis jetzt habe ich das sich die Fkt f in einem Intervall I=[c,d] abbildet. und
|f'(x)|<=q<1 für alle x [mm] \in [/mm] I
Dann besitzt das Intervall I genau einen Fixpunkt x* und jeder Startwert der iterierten Folge konvergiert gegen x*.
Gibt es noch mehr Bedingungen???
Und gibt es als Iterative Verfahren nur das Fixpunkt und das Newton-Verfahren? oder zählen auch das Gauß-Newton Verfahren, Sherman-Morrison-Verfahren, usw dazu?
Welche Probleme bei der Anwendung von Newton und Fixpunkt gibt es???
Vielen Dank für Eure Hilfe
|
|
| |
|
Hallo Maison2000,
> Welche Bedingungen müssen für das Fixpunktverfahren erfüllt
> sein um es anzuwenden?
> Bis jetzt habe ich das sich die Fkt f in einem Intervall
> I=[c,d] abbildet. und
> |f'(x)|<=q<1 für alle x [mm]\in[/mm] I
>
> Dann besitzt das Intervall I genau einen Fixpunkt x* und
> jeder Startwert der iterierten Folge konvergiert gegen
> x*.
>
> Gibt es noch mehr Bedingungen???
Nein das reicht. Edit: Man kann es zwar hineininterpretieren aber f bildet das Intervall auf sich selbst ab also f(I) [mm] \subseteq [/mm] I müsste dastehen
> Und gibt es als Iterative Verfahren nur das Fixpunkt und
> das Newton-Verfahren? oder zählen auch das Gauß-Newton
> Verfahren, Sherman-Morrison-Verfahren, usw dazu?
Was macht denn das Gauß Newtonverfahren/sherman-Morrison-Verfahren?
> Welche Probleme bei der Anwendung von Newton und Fixpunkt
> gibt es???
Als Beispiel [mm] f(x)=x^2 [/mm] Fixpunkte dieser Funktion sind 0 und 1.
Was passiert wenn du als Startwert 2 wählst?
gruß
mathemaduenn
|
|
|
| |
|
Hallo mathemaduenn,
> > Welche Bedingungen müssen für das Fixpunktverfahren
> erfüllt
> > sein um es anzuwenden?
> > Bis jetzt habe ich das sich die Fkt f in einem Intervall
>
> > I=[c,d] abbildet. und
> > |f'(x)|<=q<1 für alle x [mm]\in[/mm] I
> >
> > Dann besitzt das Intervall I genau einen Fixpunkt x* und
>
> > jeder Startwert der iterierten Folge konvergiert gegen
>
> > x*.
> >
> > Gibt es noch mehr Bedingungen???
> Nein das reicht.
Ist diese Bedingung, die da oben angegeben ist, quasi der "Kern" des Banachschen Fixpunktsatzes? Was ist z.B. mit diesen a posteriori und a priori-Abschätzungen? Ich versuche mal ein Beispiel:
[m]\begin{gathered}
x^2 = \left( {\left( {x + 1} \right) - 1} \right)^2 = \left( {x + 1} \right)^2 - 2\left( {x + 1} \right) + 1 = 0 \Leftrightarrow \left( {x + 1} \right)^2 = 2\left( {x + 1} \right) - 1 \hfill \\
\Rightarrow x_{i + 1} : = \frac{{\left( {x_i + 1} \right)^2 - 1}}
{2} \hfill \\
\end{gathered}[/m]
Jetzt benutze ich die obere Bedingung und bilde die erste Ableitung meiner Iterationsfunktion, welche x+1 ist. Und weil es daher immer ein x gibt, welches größer oder gleich 0 ist, konvergiert das Verfahren nicht gegen die Nullstelle 0 für alle Werte außer 0 selbst.
War das jetzt so richtig? Und wenn ja: Ist die obere Bedingung eine Art "Kurzfassung" des Banach-Satzes?
Vielen Dank!
Grüße
Karl
|
|
|
| |
|
Hallo Karl,
[Dateianhang nicht öffentlich]
Da müsste natürlich noch stehen f bildet I auf sich ab. Also durch anwenden der Funktion verläßt man das Intervall nicht. Diese Bedingung muß gelten und:
[mm]||f(x)-f(y)||\le L||x-y||[/mm] mit L<1
Warum erhält man aus "Ableitung kleiner eins" solch ein L?
[mm]f(b)-f(a)=f'(\lambda)(b-a) \lambda \in [a,b][/mm]
[mm] \Rightarrow
[/mm]
[mm]|f(b)-f(a)|=|f'(\lambda)||(b-a)|[/mm]
[mm] \Rightarrow
[/mm]
[mm]|f(b)-f(a)|\le \max_{x\in I}|f'(x)| |(b-a)|[/mm]
Also ist [mm] \max_{x\in I}|f'(x)| [/mm] solch ein L.
> War das jetzt so richtig? Und wenn ja: Ist die obere
> Bedingung eine Art "Kurzfassung" des Banach-Satzes?
Die Abschätzungen sind ja Resultat des Banachschen Fixpunktsatzes keine Bedingungen. Der Schluß das das Verfahren bei nicht Gültigkeit der Voraussetzungen des Satzes nicht konvergiert ist allerdings nicht richtig. Meintest Du das?
gruß
mathemaduenn
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
|
|
|
| |
|
Hallo mathemaduenn,
Annahme:
Das Verfahren [m]x_{i + 1} : = \frac{{\left( {x_i + 1} \right)^2 - 1}}
{2}[/m] konvergiert nicht gegen eine Nullstelle von [m]f\left( x \right): = x^2[/m]. Es sei den wir setzen im ersten Approximationsschritt die Nullstelle von [mm] $f\left(x\right)$ [/mm] ein.
Wir beweisen die Aussage mit ... ja mit was eigentlich? Heißt das nun Lipschitz-Stetigkeit oder Banachscher Fixpunktsatz?
Beweis:
Angenommen das Verfahren konvergiert doch für einen beliebigen Startwert [mm] $x_{\texttt{Start}} \not= x_{\texttt{Nullstelle von }f\left(x\right)}$ [/mm] gegen die Nullstelle von [mm] $f\left(x\right)$. [/mm] Dann gilt nach der Lipschitz-Bedingung(?):
[m]\begin{gathered}
\left| {\frac{{\left( {a + 1} \right)^2 - 1}}
{2} - \frac{{\left( {b + 1} \right)^2 - 1}}
{2}} \right| \leqslant L\left| {a - b} \right| \Rightarrow \left| {\frac{{\left( {a + 1} \right)^2 - 1 - \left( {b + 1} \right)^2 + 1}}
{2}} \right| \leqslant L\left| {a - b} \right| \hfill \\
\Rightarrow \left| {\frac{{\left( {a + 1} \right)^2 - \left( {b + 1} \right)^2 }}
{2}} \right| \leqslant L\left| {a - b} \right| \Rightarrow \left| {\frac{{\left( {\left( {a + 1} \right) - \left( {b + 1} \right)} \right)\left( {\left( {a + 1} \right) + \left( {b + 1} \right)} \right)}}
{2}} \right| \leqslant L\left| {a - b} \right| \hfill \\
\Rightarrow \left| {\frac{{\left( {a - b} \right)\left( {a + b + 2} \right)}}
{2}} \right| \leqslant L\left| {a - b} \right| \Rightarrow \left| {\frac{{\left( {a - b} \right)\left( {a + b + 2} \right)}}
{{2\left( {a - b} \right)}}} \right| \leqslant L \Rightarrow \left| {\frac{{a + b + 2}}
{2}} \right| \leqslant L \hfill \\
\end{gathered}[/m]
[mm] $L\!$ [/mm] ist eine Konstante. Deshalb kann ich immer ein solches [mm] $a\!$ [/mm] und [mm] $b\!$ [/mm] finden, daß dieser Bruch größer als [mm] $L\!$ [/mm] ist. Damit ist die Lipschitz-Bedingung verletzt. Widerspruch zur Annahme!
Damit konvergiert das Verfahren nicht. [mm] $\square$
[/mm]
Ist das so richtig?
Vielen Dank!
Viele Grüße
Karl
|
|
|
| |
|
Hallo Karl,
Da sieht man wieder das Smileys interpretierbar sind. Ich war eigentlich ärgerlich über mich das ich die Selbstabbildung (f bildet das Intervall I auf sich selbst ab) nicht nochmal hervorgehoben habe sondern geschrieben habe "das reicht". Man konnte das zwar hineininterpretieren aber so richtig klar schiens nicht.
Banachscher Fixpunktsatz:
Wenn die Bedingungen erfüllt sind(Lipschitzstetigkeit mit L<1 und Selbstabbildung) dann erhält man daraus das es einen eindeutigen Fixpunkt gibt und die Fixpunktiteration konvergiert für alle Startwerte aus dem Intervall.
Wenn die Bedingungen nicht erfüllt.
![[keineahnung]](/images/smileys/keineahnung.gif "[keineahnung]")
Konvergenz - keine Konvergenz
Das gibt der Satz eben nicht her.
Du hast bewiesen das deine Funktion nicht global L-stetig ist. Das heißt nur das der Ban. Fixp. Satz nicht global anwendbar wäre.
gruß
mathemaduenn
|
|
|
| |
|
Hallo mathemaduenn,
> Banachscher Fixpunktsatz:
> Wenn die Bedingungen erfüllt sind(Lipschitzstetigkeit mit
> L<1 und Selbstabbildung) dann erhält man daraus das es
> einen eindeutigen Fixpunkt gibt und die Fixpunktiteration
> konvergiert für alle Startwerte aus dem Intervall.
> Wenn die Bedingungen nicht erfüllt.
>
> Konvergenz - keine Konvergenz
> Das gibt der Satz eben nicht her.
> Du hast bewiesen das deine Funktion nicht global L-stetig
> ist. Das heißt nur das der Ban. Fixp. Satz nicht global
> anwendbar wäre.
Mir ist leider nicht ganz klar, was ich davon habe. Ich dachte der Banach-Fixpunktsatz wäre dazu da, um zu bestimmen, ob es mit einem Iterationsverfahren klappt oder nicht. Aber im Grunde ist man nach der Anwendung des Satzes genauso weit gekommen wie zuvor, oder? Er scheint einem nur zu nützen, wenn sich durch die Anwendung kein Widerspruch ergibt. Denn dann weiß man, daß das Verfahren konvergiert. Stimmt das?
Viele Grüße
Karl
|
|
|
| |
|
Hallo Karl,
Beginnen möchte ich mit einem Beispiel:
[mm] f(x)=\begin{cases} 1, & \mbox{für } x<0 \\ 0 & \mbox{sonst} \end{cases}[/mm]
Da die Funktion in 0 unstetig ist gibt es keine Umgebung von 0 in der die Lipschitz - Bedingung des Banachschen Fixpunktsatzes erfüllt wäre. Trotzdem braucht eine Fixpunktiteration nur 2 Schritte bis zur Lösung.
2. Beispiel: Das Newtonverfahren
[mm] x_{k+1}=x_k-\bruch{f(x_k)}{f'(x_k)}
[/mm]
Nun kann man sich fragen: Bringt das was?
Also betrachte ich das als Fixpunktiteration:
[mm] x_{k+1}=T(x_k) [/mm] mit [mm] T(x)=x-\bruch{f(x)}{f'(x)}
[/mm]
[mm] T'(x)=1-\bruch{f'(x)^2-f(x)*f''(x)}{f'(x)^2}
[/mm]
Wenn f(x^*)=0 dann ist x^* offensichtlich ein Fixpunkt von T(x). Was macht die Ableitung von T(x^*)?
[mm] T'(x)=1-\bruch{f'(x^*)^2-f(x^*)*f''(x^*)}{f'(x^*)^2}=0
[/mm]
Sind die beteiligten Funktionen stetig und [mm] f'(x^*)\not=0 [/mm] ergibt sich die Anwendbarkeit des Banachschen Fixpunktsatzes (also Eindeutigkeit des Fixpunktes und Konvergenz) in einer Umgebung von x^* Das ist doch schonmal was.
Ein anderes Beispiel wäre beim Gesamtschrittverfahren die strenge Diagonaldominanz der Matrix A. Ist sie gegeben ist die Zeilensummennorm der Iterationsmatrix kleiner 1. Das gibt mir solch ein L.
Alles klar?
gruß
mathemaduenn
|
|
|
| |
|
Hallo mathemaduenn,
Also ich habe hier einige Aufgaben, wo man wohl das, was Du sagst, anwenden sollte:
Es geht um die Funktion [m]f\left( x \right): = x + \ln x[/m].
Dazu sind 3 iterative Verfahren gegeben, durch die man eine Nullstelle von [mm] $f\left(x\right)$ [/mm] bestimmen soll. Die Fragen sind:
"Welche Formel oder welche Formeln können benutzt werden?"
und
"Welche Formel sollte benutzt werden?"
Es geht also darum, welche Verfahren konvergieren und welches von den folgenden am schnellsten konvergiert:
[m]\begin{array}{*{20}c}
{1.\quad x_{i + 1} : = - \ln x_i } & {2.\quad x_{i + 1} : = e^{ - x_i } } & {3.\quad } \\
\end{array} x_{i + 1} : = \frac{{x_i + e^{ - x_i } }}
{2}[/m]
Also Du sprachst ja jetzt etwas von Ableitung gleich 0, richtig? Jedenfalls gibt es nur bei Ableitung Nr. 3 in diesem Beispiel eine Nullstelle:
[m]\frac{1}
{2} - \frac{{e^{ - 0} }}
{2} = 0[/m]
Und das sagt mir jetzt also, daß ich dieses Verfahren verwenden soll, richtig?
Viele Grüße
Karl
|
|
|
| |
|
Hallo Karl,
Die Frage ist welche dieser Funktionen ein möglichst kleines L erlaubt. Das mit der Ableitung im Fixpunkt war nur besonders schön. Das heißt aber nicht das man die Ableitung null setzen muß. Denn wo die Ableitung null ist muß ja kein Fixpunkt sein.
gruß
mathemaduenn
|
|
|
|
