Satz von Kantorovich bestimmung der Konstante

03.11.2009, 15:40

murxtilt

Satz von Kantorovich bestimmung der Konstante

Ich steh gerade auf dem Holzweg. Habe Funktion $\begin{eqnarray*} F(X)=2cos(x) -x^{2} \end{eqnarray*}$ auf dem das Newton Verfahren angewandt werden sollte. So weit so gut. Doch dann wollen sie, dass ich folgendes Problem löse:
Bestimmen Sie explizit eine Konstante C, so dass für die Nullstelle $\begin{eqnarray*} \lambda \end{eqnarray*}$ und für alle natürlichen
Zahlen n gilt: $\begin{eqnarray*} |x_{n}- \lambda| \leq C|x_{n-1} - \lambda^{2} | \end{eqnarray*}$ .

Ich habe überhaupt keinen Ansatz wie ich das lösen soll. Weder in der Vorlesung wurde das Thema groß behandelt noch in der Übung. In meiner Fachliteratur steht nichts dazu, sowie im Internet finde ich nichts brauchbares. Kann mir jemand hier einen Ansatz geben, wie ich das Problem lösen kann.
Mir würde ja schon evtl. helfen, wie ich denn zum Beispiel an das $\begin{eqnarray*} \lambda \end{eqnarray*}$ ran kommen würde.

Gruß murx

03.11.2009, 16:05

tigerbine

Auf diesen Beitrag antworten »

RE: Satz von Kantorovich bestimmung der Konstante
Kannst du ggf. die ganze Aufgabe einstellen? Link?

Wie lautet bei euch der Satz von Kantorovich?

04.11.2009, 01:34

murxtilt2

Auf diesen Beitrag antworten »

Wir betrachten die Funktion F : [pi/4,pi/3]->R, F(x) = 2 cos(x) - $\begin{eqnarray*} x^{2} \end{eqnarray*}$
a) Zeigen Sie, dass das Newton-Verfahren in diesem Fall konvergiert.
b) Berechnen Sie mit einem geeigneten Startwert x0 die Iterationswerte x1; ...; x5 aus dem Newton-Verfahren.
c) Bestimmen Sie explizit eine Konstante C, so dass für die Nullstelle $\begin{eqnarray*} \lambda \end{eqnarray*}$ und für alle natürlichen Zahlen n gilt: $\begin{eqnarray*} | x_n - \lambda | \leq C | X_{n-1} - \lambda | ^2 \end{eqnarray*}$
d) Geben Sie eine Abschätzung von $\begin{eqnarray*} | x_5 - \lambda | \end{eqnarray*}$ an.

a.) und b.) sind gelöst.d.) erhoffe ich mir zu lösen, wenn ich c verstanden habe.

Satz von Kantorovich:
Sei die Vektorfunktion $\begin{eqnarray*} F: R^n \Rightarrow R^n \end{eqnarray*}$ einmal differenzierbar
und besitze ihre Jacobimatrix $\begin{eqnarray*} F'(X)\in : R^{nxn} \end{eqnarray*}$ die Lipschitzkonstante $\begin{eqnarray*} \gamma \end{eqnarray*}$ .
Weiterhin sei $\begin{eqnarray*} x^{(0)} \end{eqnarray*}$ ein Punkt an dem $\begin{eqnarray*} F'(x^{(0)}) \end{eqnarray*}$ regulär ist und somit eine Inverse $\begin{eqnarray*} F'(x^{(0)})^{-1} \end{eqnarray*}$ existiert.
Mit $\begin{eqnarray*} || . | | \end{eqnarray*}$ als induzierte Matrix-Norm folgt dann aus

$\begin{eqnarray*} || F'(x^{(0)})^{-1} | |^2 | | F(x^{(0)}) | | \leq \frac{2}{2\gamma } \end{eqnarray*}$

dass Newton's Methode zu einer Lösung $\begin{eqnarray*} x^{(*)} \end{eqnarray*}$ mit $\begin{eqnarray*} F(x^{(*)})=0 \end{eqnarray*}$ konvergiert.
Die Konvergenzgeschwindigkeit ist quadratisch in dem Sinne dass für eine Konstante c und alle k
gilt
$\begin{eqnarray*} | | x^{(k+1)}-x^{(*)} | |\leq C | | x^{(k)}-x^{(*)} | |^2 \end{eqnarray*}$

In meinem Fall da ich im eindimensionalen Raum bin lässt sich der Satz natürlich vereinfachen. Aber wir haben nur den allgemeinen.

Vielen Dank im vorraus.

Gruß murxtilt

04.11.2009, 10:39

tigerbine

Auf diesen Beitrag antworten »

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

Es wird eine Nullstelle mittels Newton approximiert
Funktion in bisektionf.m anlegen
Ableitung in newtondf.m anlegen
 
Intervall [a,b] eingeben:
a= pi/4
b= pi/3
 
Gewünschte Genauigkeit: eps= 10^(-6)
 
Hat die Funktion auf [a_0,b_0] mehrere Nullstellen? (0-ja, 1-nein) 1
Startwert eingeben: x0= pi/3

  x_n+1            x_n           Delta
============================================
  1.021946        1.047198       0.024113 
  1.021690        1.021946       0.000251 
  1.021690        1.021690       0.000000

[attach]11788[/attach]

$\begin{eqnarray*} f(x)=2\cos(x) -x^{2} \end{eqnarray*}$

$\begin{eqnarray*} f'(x)=-2\sin(x)-2x \end{eqnarray*}$

$\begin{eqnarray*} f''(x)=-2\cos(x)-2 \end{eqnarray*}$

Ich erinnere mich, mal so eine Aufgabe diskutiert zu haben:
[Aufgabensammlung] Fragen & Antworten 3
Bestimmen einer Lipschitz-Konstanten

Was ist nun bei c eigentlich gefragt? Dort soll man zeigen, dass das Verfahren mit quadratischer Geschwindigkeit konvergiert.

$\begin{eqnarray*} \|x_{k+1}-x^*\| \leq C \cdot \|x_k-x^*\|^2 \end{eqnarray*}$

Unsere Funktion ist sehr schön, beliebig oft stetig Differenzierbar und es liegt eine einfache Nullstelle vor. Daher würde ich hiermit ansetzen:
[WS] Eindimensionale Nullstellenprobleme 2 - Das Newton Verfahren

$\begin{eqnarray*} m:=\min_{x \in [a,b]}~|f'(x)|>0 \end{eqnarray*}$
$\begin{eqnarray*} M:=\max_{x \in [a,b]}~|f''(x)|< \infty \end{eqnarray*}$
$\begin{eqnarray*} C:=\frac{M}{2m} \end{eqnarray*}$

Aus der Skizze sieht man ja, wo man die Ableitungen auswerten muss. Imho bracht man dann Kantorovich doch gar nicht... verwirrt

In der Aufgabe steht auch nichts davon, dass man den Satz benutzen soll. Bei der ersten Verlinkten Aufgabe steht ja auch rechtes nur die Norm, nicht das Quadrat.

Gruß Wink

04.11.2009, 12:09

murxtilt2

Auf diesen Beitrag antworten »

Ich danke dir, für deine Hilfe. Jetzt ist es für mich verständlich. Bin auch an die Sache etwas falsch ran gegangen, wie ich anhand deiner Lösung sehe.

Den Satz von Kantorovich habe ich benutzt für a.) Denn wenn es quadratsich konvergiert, konvergiert es ja auch smile

Aber wahrscheinlich auch der Umständlichere Weg.
Da es bei a wunderbar funktioniert hatte, habe ich gedacht, es wäre auch bei c.) benötigt.

04.11.2009, 17:08

tigerbine

Auf diesen Beitrag antworten »

Gern geschehen. Melde dich doch nach der Übung, ob es dem Wunsch deines Korrektors entsprochen hat. Wink

Neue Frage »

Antworten »

Satz von Kantorovich bestimmung der Konstante

Verwandte Themen