vereinfachtes Newtonverfahren < Numerik < Hochschule < Mathe < Vorhilfe
|
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.
|
|
|
|
Status: |
(Antwort) fertig | 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
|
|
|
|