www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Numerik" - vereinfachtes Newtonverfahren
vereinfachtes Newtonverfahren < Numerik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Numerik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

vereinfachtes Newtonverfahren: Konvergenz
Status: (Frage) beantwortet Status 
Datum: 12:34 Do 14.02.2008
Autor: fragespezi

Aufgabe
Es sei $F : [mm] \IR^{n} \to \IR^{n} [/mm] $ Lipschitz-stetig differenzierbar (mit der Konstanten L), [mm] \bar [/mm] x sei reguläre Nullstelle von F, d.h.
[mm] $F(\bar [/mm] x)=0, [mm] \quad F'(\bar [/mm] x) $ regulär.

Mit gegebenem [mm] $x^0 \in \IR^n$ [/mm] ist das vereinfachte Newton-Verfahren definiert durch

[mm] F(x^k) + F'(x^0) (x^{k+1}- x^k) = 0, \qquad k = 0, 1, . . . . [/mm]

Für dies gilt

[mm] F'(x^0) (x^{k+1}-\bar x) = (F'(x^0)-F'(x^k))(x^k-x*)+F(\bar x)-F(x^k)-F'(x^k)(\bar x-x^k), \qquad k = 0, 1, . . .. [/mm]

Man zeige unter Verwendung von
[mm] F(\bar x) = F(x^k) + \integral_{1}^{0}{F'(x^k + t (\bar x- x^k))(\bar x- x^k) dt} [/mm],

dass hieraus folgt
[mm] \left| \left x^{k+1}- \bar x \right| \right| \le L \left| \left| F'(x^0)^{-1} \right| \right| \left( \left| \left| x^{0}-x^k \right| \right| + \bruch{1}{2} \left| \left| x^k - \bar x \right| \right| \right) * \left| \left| x^k-\bar x \right| \right| [/mm].

und begründe damit die lokale Konvergenz des vereinfachten Newtonverfahrens.

Ich komme leider nicht auf die gewünschte Abschätzung.
ich habe bisher folgendes Resultat:
[mm] (x^{k+1}-\bar x) = F'(x^0)^-1 \left[ (F'(x^0)-F'(x^k))(x^k-x\cdot{})+F(\bar x)-F(x^k)-F'(x^k)(\bar x-x^k) \right] [/mm]
und setze da
[mm] F(\bar x) - F(x^k) = \integral_{1}^{0}{F'(x^k + t (\bar x- x^k))(\bar x- x^k) dt} [/mm] ein, woraus sich schließlich

[mm] (x^{k+1}-\bar x) = F'(x^0)^{-1} \left[ (F'(x^0)-F'(x^k))(x^k-\bar x)+\integral_{1}^{0}{F'(x^k + t (\bar x- x^k))(\bar x- x^k) dt} -F'(x^k)(\bar x-x^k) \right] [/mm]
ergibt.
Durch Ausmultiplizieren ergibt sich damit
[mm] (x^{k+1}-\bar x) = F'(x^0)^{-1} \left[ (F'(x^0)(x^k-\bar x)+\integral_{1}^{0}{F'(x^k + t (\bar x- x^k))(\bar x- x^k) dt} \right] [/mm]

in der Vorlesung hatten wir die Abschätzung (ich habe keine Ahnung wie man zu ihr kommt, erste Zeile ist der hauptsatz der Integralrechnung aber weiter weiß ich nicht):
[mm] F(y)-F(x)=\integral_{1}^{0}{F'(x+ t (y-x))(y- x) dt} [/mm]

[mm] \le \left| \left| F'(x) \right| \right| + \integral_{1}^{0}{L (y- x) tdt} \left| \left| y-x \right| \right| [/mm]
[mm] \le \left( \left| \left| F'(x) \right| \right| + \bruch{1}{2} L \left| \left| y- x \right| \right| \right) \left| \left| y-x \right| \right| [/mm]


Frage:
Hilft mir diese Abschätzung weiter, und wie komme ich auf diese Abschätzung?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.




        
Bezug
vereinfachtes Newtonverfahren: Lipschitz-Bedingung
Status: (Antwort) fertig Status 
Datum: 18:54 Sa 16.02.2008
Autor: rainerS

Hallo!

> Es sei [mm]F : \IR^{n} \to \IR^{n}[/mm] Lipschitz-stetig
> differenzierbar (mit der Konstanten L), [mm]\bar[/mm] x sei reguläre
> Nullstelle von F, d.h.
> [mm]F(\bar x)=0, \quad F'(\bar x)[/mm] regulär.
>  
> Mit gegebenem [mm]x^0 \in \IR^n[/mm] ist das vereinfachte
> Newton-Verfahren definiert durch
>  
> [mm] F(x^k) + F'(x^0) (x^{k+1}- x^k) = 0, \qquad k = 0, 1, . . . . [/mm]
>  
> Für dies gilt
>  
> [mm] F'(x^0) (x^{k+1}-\bar x) = (F'(x^0)-F'(x^k))(x^k-x*)+F(\bar x)-F(x^k)-F'(x^k)(\bar x-x^k), \qquad k = 0, 1, . . .. [/mm]
>  
> Man zeige unter Verwendung von
>  [mm] F(\bar x) = F(x^k) + \integral_{1}^{0}{F'(x^k + t (\bar x- x^k))(\bar x- x^k) dt} [/mm],
>  
> dass hieraus folgt
>  [mm] \left| \left x^{k+1}- \bar x \right| \right| \le L \left| \left| F'(x^0)^{-1} \right| \right| \left( \left| \left| x^{0}-x^k \right| \right| + \bruch{1}{2} \left| \left| x^k - \bar x \right| \right| \right) * \left| \left| x^k-\bar x \right| \right| [/mm].
>  
> und begründe damit die lokale Konvergenz des vereinfachten
> Newtonverfahrens.
>  Ich komme leider nicht auf die gewünschte Abschätzung.
>  ich habe bisher folgendes Resultat:
>  [mm] (x^{k+1}-\bar x) = F'(x^0)^-1 \left[ (F'(x^0)-F'(x^k))(x^k-x\cdot{})+F(\bar x)-F(x^k)-F'(x^k)(\bar x-x^k) \right] [/mm]
>  
> und setze da
> [mm] F(\bar x) - F(x^k) = \integral_{1}^{0}{F'(x^k + t (\bar x- x^k))(\bar x- x^k) dt} [/mm]
> ein, woraus sich schließlich
>  
> [mm] (x^{k+1}-\bar x) = F'(x^0)^{-1} \left[ (F'(x^0)-F'(x^k))(x^k-\bar x)+\integral_{1}^{0}{F'(x^k + t (\bar x- x^k))(\bar x- x^k) dt} -F'(x^k)(\bar x-x^k) \right] [/mm]
> ergibt.
>  Durch Ausmultiplizieren ergibt sich damit
>  [mm] (x^{k+1}-\bar x) = F'(x^0)^{-1} \left[ (F'(x^0)(x^k-\bar x)+\integral_{1}^{0}{F'(x^k + t (\bar x- x^k))(\bar x- x^k) dt} \right] [/mm]

Ausmultiplizieren würde ich hier nicht, damit machst du dir das Leben schwerer, siehe unten.

> in der Vorlesung hatten wir die Abschätzung (ich habe keine
> Ahnung wie man zu ihr kommt, erste Zeile ist der hauptsatz
> der Integralrechnung aber weiter weiß ich nicht):
>  [mm] F(y)-F(x)=\integral_{1}^{0}{F'(x+ t (y-x))(y- x) dt} [/mm]
>  
> [mm] \le \left| \left| F'(x) \right| \right| + \integral_{1}^{0}{L (y- x) tdt} \left| \left| y-x \right| \right| [/mm]
>  
> [mm] \le \left( \left| \left| F'(x) \right| \right| + \bruch{1}{2} L \left| \left| y- x \right| \right| \right) \left| \left| y-x \right| \right| [/mm]
>  
>
> Frage:
>  Hilft mir diese Abschätzung weiter, und wie komme ich auf
> diese Abschätzung?

Du hast doch als Voraussetzung, dass F Lipsschitz-stetig diff'bar ist, dass also

$ [mm] \|F'(x)-F'(y)\| \le [/mm] L [mm] \|x-y\| [/mm] $

ist. Damit kannst du den Betrag des Integrals abschätzen:

[mm] $\left\|\integral_{1}^{0}{F'(x+ t (y-x))(y- x) dt} \right\| \le \integral_{1}^{0} \|F'(x+ [/mm] t [mm] (y-x))\|dt *\|y-x\|$ [/mm]
    $   [mm] \le \integral_{1}^{0} (\|F'(x+ [/mm] t (y-x)) [mm] -F'(x)\|+\|F'(x)\| [/mm] dt [mm] *\|y-x\|$ [/mm]
     $  [mm] \le \left(\integral_{1}^{0} L* \|x+ t (y-x) -x \| dt + \|F'(x)\|\right)*\|y-x\|$. [/mm]

Bei der Herleitung oben solltest du, statt Auszumultiplizieren, [mm] $\|F'(x^0)-F'(x^k)\|\le [/mm] L [mm] \|x^0- x^k\|$ [/mm] und das Integral wie eben abschätzen.

Viele Grüße
   Rainer

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Numerik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]