www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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
Dt. Schulen im Ausland: Mathe-Seiten:

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

Newton - Verfahren (Beweis): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:37 Do 09.01.2020
Autor: Steve96

Aufgabe
Sei $a > 0$ und [mm] $x_{0} \in \mathbb{R}$. [/mm] Die Nullstelle von $f(x) = [mm] \frac{1}{x} [/mm] - a$ soll mit Hilfe des Newton - Verfahrens berechnet werden.

a) Zeigen Sie, dass die Iterationsvorschrift gegeben ist durch

[mm] $x_{k + 1} [/mm] = [mm] x_{k} [/mm] + [mm] x_{k} [/mm] (1 - a [mm] x_{k})\quad \forall [/mm] k [mm] \in \mathbb{N}_{0}$ [/mm]


b) Zeigen Sie, dass für den Fehler [mm] $e_{k} [/mm] := [mm] x_{k} [/mm] - [mm] \frac{1}{a}$ [/mm] gilt:

[mm] $e_{k + 1} [/mm] = - a [mm] e^{2}{k}\quad \forall [/mm] k [mm] \in \mathbb{N}{0}$ [/mm]


Zeigen Sie mit vollständiger Induktion, dass gilt:


[mm] $e_{k} [/mm] = - [mm] \frac{1}{a} [/mm] p [mm] ^{2^{k}}\quad \forall [/mm] k [mm] \in \mathbb{N}$, [/mm] $p := [mm] \vert [/mm] a [mm] x_{0} [/mm] - [mm] 1\vert$. [/mm]

Welche Bedingung an $p$ und [mm] $x_{0}$ [/mm] ist notwenig und hinreichend für die globale Konvergenz des Iterationsverfahrens.


c) Es sei $a [mm] \in \left [\frac{1}{2}, 1 \right [/mm] ]$ und [mm] $x_{0} [/mm] = [mm] \frac{3}{2}$. [/mm] Bestimmen Sie die maximale Anzahl der erforderlichen elementaren Rechenoperationen zur Berechnung einer Näherung [mm] $x_{k}$ [/mm] für [mm] $\frac{1}{a}$ [/mm] durch das Newton - Verfahren mit einem Fehler kleiner als [mm] $10^{- 8}$. [/mm]

Hallo, ich habe Probleme bei der obigen Aufgabe.Ich komme bei einer Teilaufgabe nicht weiter. Ich hoffe, dass mir jemand helfen kann :-)

Zur Aufgabe habe ich ein paar Ansätze, aber bin mir zum Beispiel bei der b) nicht sicher, ob ich es mir zu einfach gemacht habe.



Mein Ansatz zu 1 a)
________________


Wir haben  $f(x) = [mm] \frac{1}{x} [/mm] - a$.

Dann lautet die Iterationsvorschrift:  


[mm] $x_{ k + 1} [/mm] = [mm] x_{k} [/mm] - [mm] \frac{f(x_{k})}{f'(x_{k})} [/mm] = [mm] x_{k} [/mm] - [mm] \frac{\frac{1}{x_{k}} - a}{- \frac{1}{x_{k}^{2}}} [/mm] = [mm] x_{k} [/mm] + [mm] \frac{\frac{1}{x_{k}} - a}{\frac{1}{x_{k}^{2}}} [/mm] =  [mm] x_{k} [/mm] + [mm] \frac{\frac{1 - x_{k} \cdot a}{x_{k}}}{\frac{1}{x_{k}^{2}}} [/mm] =  [mm] x_{k} [/mm] + [mm] \frac{1 - x_{k} \cdot a}{x_{k}} \cdot x_{k}^{2} [/mm] = [mm] x_{k} [/mm] + [mm] x_{k} \cdot [/mm] (1 - [mm] x_{k} \cdot [/mm] a)$


Damit wäre die Behauptung gezeigt.


Mein Ansatz zu 1 b)
_________________


Wir haben den Fehler [mm] $e_{k} [/mm] := [mm] x_{k} [/mm] - [mm] \frac{1}{a}$. [/mm]



Dann gilt:   [mm] $e_{k + 1} [/mm] = [mm] x_{k + 1} [/mm] - [mm] \frac{1}{a} \overset{\text{a)}}{\underset{\text{}}{=}} x_{k} [/mm] + [mm] x_{k} \cdot [/mm] (1 - [mm] x_{k} \cdot [/mm] a) - [mm] \frac{1}{a} \overset{\text{Def \;} e_{k}}{\underset{\text{}}{=}} \left (e_{k} + \frac{1}{a} \right [/mm] ) + [mm] \left (e_{k} + \frac{1}{a} \right [/mm] ) [mm] \cdot \left (1 - a \cdot \left (e_{k} + \frac{1}{a} \right ) \right [/mm] ) - [mm] \frac{1}{a} [/mm] $

$ = [mm] e_{k} [/mm] + [mm] \left (e_{k} + \frac{1}{a} \right [/mm] ) [mm] \cdot \left ( 1- \left ( ae_{k} + \frac{a}{a} \right ) \right [/mm] ) =  - [mm] ae_{k}^{2}$ [/mm]


Damit wäre der erste Teil schon gezeigt.



Die Induktion habe ich so ausgeführt:


Induktionsanfang
______________

Sei $k = 1$.


Dann ist [mm] $e_{1} [/mm] = [mm] x_{1} [/mm] - [mm] \frac{1}{a} \overset{\text{a)}}{\underset{\text{}}{=}} x_{0} [/mm] + [mm] x_{0} [/mm] (1 - [mm] ax_{0}) [/mm] - [mm] \frac{1}{a} [/mm] = - [mm] \frac{1}{a} (ax_{0} [/mm] - [mm] 1)^{2^{1}}$ [/mm]




Induktionsbehauptung
__________________

[mm] $\exists [/mm] k [mm] \in \mathbb{N}: e_{k} [/mm] = [mm] x_{k} [/mm] - [mm] \frac{1}{a} [/mm] = - [mm] \frac{1}{a} p^{2^{k}}$ [/mm]



Induktionsschritt
______________


Wir müssen zeigen:

[mm] $x_{k} [/mm] - [mm] \frac{1}{a} [/mm] = - [mm] \frac{1}{a} p^{2^{k}} \Rightarrow x_{k + 1} [/mm] - [mm] \frac{1}{a} [/mm] = - [mm] \frac{1}{a} p^{2^{k + 1}} [/mm]



Wir haben:


[mm] $e_{k + 1} [/mm] = - [mm] ae_{k}^{2} \overset{\text{IB}}{\underset{\text{}}{=}} [/mm] - a [mm] \cdot \left ( \frac{1}{a} p^{2^{k}} \right )^{2} [/mm] = - a [mm] \cdot \frac{1}{a^{2}} p^{2^{k + 1}} [/mm] =  - [mm] \frac{1}{a} p^{2^{k + 1}}$ [/mm]



q.e.d


Aber wie oben schon erwähnt: Das sieht mir ein wenig zu leicht aus, daher bin ich mir nicht ganz sicher, ob ich irgend etwas übersehen habe.






Zur c) habe ich noch keinen Ansatz. Ich weiß nicht, wo ich anfangen soll, die Rechenoperationen zu zählen.


Und zur Frage, welche Bedingungen an $p$ und [mm] $x_{0}$ [/mm] notwendig und hinreichend sind für die globale Konvergenz des Iterationsverfahrens, habe ich noch keine Antwort.


Es wäre super, wenn mir jemand einen Tipp gibt!


lg, Steve

        
Bezug
Newton - Verfahren (Beweis): Antwort
Status: (Antwort) fertig Status 
Datum: 22:03 Do 09.01.2020
Autor: Gonozal_IX

Hiho,

> b) Zeigen Sie, dass für den Fehler $ [mm] e_{k} [/mm] := [mm] x_{k} [/mm] - [mm] \frac{1}{a} [/mm] $ gilt:
> $ [mm] e_{k + 1} [/mm] = - a [mm] e^{2}{k}\quad \forall [/mm] k [mm] \in \mathbb{N}_0 [/mm] $

Hier meinst du bestimmt
$ [mm] e_{k + 1} [/mm] = - a [mm] e^{2}_{k}\quad \forall [/mm] k [mm] \in \mathbb{N}{0} [/mm] $

> Aber wie oben schon erwähnt: Das sieht mir ein wenig zu leicht aus, daher bin ich mir nicht ganz sicher, ob ich irgend etwas übersehen habe.

Um dich zu schocken: Ja du hast was übersehen.
Aber: Es ist wirklich so "leicht" wie du es gelöst hast.
Wobei ich eher sagen würde, du hast es "souverän" gelöst, und nicht "leicht" ;-)

Zum Übersehenen:
Du hast per Vollständiger Induktion gezeigt:
$ [mm] e_{k} [/mm] = - [mm] \frac{1}{a} [/mm] p [mm] ^{2^{k}}\quad \forall [/mm] k [mm] \in \mathbb{N}, [/mm] p := a [mm] x_{0} [/mm] - 1$

Verlangt war aber zu zeigen:
$ [mm] e_{k} [/mm] = - [mm] \frac{1}{a} [/mm] p [mm] ^{2^{k}}\quad \forall [/mm] k [mm] \in \mathbb{N}, [/mm] p := |a [mm] x_{0} [/mm] - 1|$

Wenn du das noch behebst, passt alles.

> Und zur Frage, welche Bedingungen an p und $ [mm] x_{0} [/mm] $ notwendig und hinreichend sind für die globale Konvergenz des Iterationsverfahrens, habe ich noch keine Antwort.

Na das Verfahren konvergiert global, wenn der Fehler gegen Null geht.
Du hast nun einen Ausdruck für den Fehler hergeleitet, nun frag dich mal, für welche Bedingungen an $p$ (und damit an [mm] x_0) [/mm] der Fehler gegen Null konvergiert.

> Zur c) habe ich noch keinen Ansatz. Ich weiß nicht, wo ich anfangen soll, die Rechenoperationen zu zählen.

Auch hier: Du hast eine Darstellung für den Fehler, der kleiner werden soll als $ [mm] 10^{- 8} [/mm] $
Stelle diese Darstellung nach k um und schätze ab, wie groß $k$ dann im Worst-Case sein muss.
Nun überlege noch, wie viele elementare Rechenoperationen du pro Schritt in dem Verfahren machst und du hast deine Lösung.

Gruß,
Gono



Bezug
                
Bezug
Newton - Verfahren (Beweis): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:15 Fr 10.01.2020
Autor: Steve96

Vielen Dank für dein Feedback :-)

Mist, ich hätte gehofft, alles wäre richtig gewesen :-D

> Zum Übersehenen:
>  Du hast per Vollständiger Induktion gezeigt:
>  [mm]e_{k} = - \frac{1}{a} p ^{2^{k}}\quad \forall k \in \mathbb{N}, p := a x_{0} - 1[/mm]
>  
> Verlangt war aber zu zeigen:
>  [mm]e_{k} = - \frac{1}{a} p ^{2^{k}}\quad \forall k \in \mathbb{N}, p := |a x_{0} - 1|[/mm]
>  
> Wenn du das noch behebst, passt alles.




Okay, dann versuche ich das erneut:


Induktionsanfang
______________

Sei $k = 1$.


Dann ist [mm] $e_{1} [/mm] = [mm] x_{1} [/mm] - [mm] \frac{1}{a} \overset{\text{a)}}{\underset{\text{}}{=}} x_{0} [/mm] + [mm] x_{0} [/mm] (1 - [mm] ax_{0}) [/mm] - [mm] \frac{1}{a} [/mm] = - [mm] \frac{1}{a} (ax_{0} [/mm] - [mm] 1)^{2^{1}} [/mm] =  - [mm] \frac{1}{a} \vert ax_{0} [/mm] - 1 [mm] \vert^{2^{1}}$ [/mm]




Induktionsbehauptung
__________________

[mm] $\exists [/mm] k [mm] \in \mathbb{N}: e_{k} [/mm] = [mm] x_{k} [/mm] - [mm] \frac{1}{a} [/mm] = - [mm] \frac{1}{a} \vert ax_{0} [/mm] - 1 [mm] \vert^{2^{k}}$ [/mm]



Induktionsschritt
______________


Wir müssen zeigen:

[mm] $x_{k} [/mm] - [mm] \frac{1}{a} [/mm] = - [mm] \frac{1}{a} \vert ax_{0} [/mm] - 1 [mm] \vert^{2^{k}} \Rightarrow x_{k + 1} [/mm] - [mm] \frac{1}{a} [/mm] = - [mm] \frac{1}{a} \vert ax_{0} [/mm] - 1 [mm] \vert^{2^{k + 1}} [/mm]



Wir haben:


[mm] $e_{k + 1} [/mm] = - [mm] ae_{k}^{2} \overset{\text{IB}}{\underset{\text{}}{=}} [/mm] - a [mm] \cdot \left ( \frac{1}{a} \vert ax_{0} - 1 \vert^{2^{k}} \right )^{2} [/mm] = - a [mm] \cdot \frac{1}{a^{2}} \vert ax_{0} [/mm] - 1 [mm] \vert^{2^{k + 1}} [/mm] =  - [mm] \frac{1}{a} p^{2^{k + 1}}$ [/mm]



q.e.d



Aber da ändert sich doch nichts, oder ?



>  Na das Verfahren konvergiert global, wenn der Fehler gegen
> Null geht.
> Du hast nun einen Ausdruck für den Fehler hergeleitet, nun
> frag dich mal, für welche Bedingungen an [mm]p[/mm] (und damit an
> [mm]x_0)[/mm] der Fehler gegen Null konvergiert.

Achso. Ich hatte Probleme mit dem Begriff "globale Konvergenz" im Zusammenhang mit dem Newton - Verfahren. Wusste nicht, was mir das sagen soll.

Damit der Ausdruck [mm] $e_{k} [/mm] = - [mm] \frac{1}{a} \vert [/mm] a [mm] x_{0} [/mm] - 1 [mm] \vert ^{2^{k}}$ [/mm] für immer größer werdende $k$ gegen 0 geht, muss  [mm] $\vert [/mm] a [mm] x_{0} [/mm] - 1 [mm] \vert [/mm]   < a$ gelten.


Daraus folgt, dass [mm] $x_{0} [/mm] < [mm] \frac{a + 1}{a} [/mm] $ gelten  muss. Richtig ?

>  
> > Zur c) habe ich noch keinen Ansatz. Ich weiß nicht, wo ich
> anfangen soll, die Rechenoperationen zu zählen.
>  Auch hier: Du hast eine Darstellung für den Fehler, der
> kleiner werden soll als [mm]10^{- 8}[/mm]
>  Stelle diese Darstellung
> nach k um und schätze ab, wie groß [mm]k[/mm] dann im Worst-Case
> sein muss.
>  Nun überlege noch, wie viele elementare Rechenoperationen
> du pro Schritt in dem Verfahren machst und du hast deine
> Lösung.



Es soll [mm] $e_{k} [/mm] = - [mm] \frac{1}{a} p^{2^{k}} [/mm] < [mm] 10^{- 8}$ [/mm] gelten für ein bestimmtes $k$.

Wir haben dann


$  - [mm] \frac{1}{a} p^{2^{k}} [/mm] < [mm] 10^{- 8 }\quad \vert\; \cdot [/mm] (- 1)$

[mm] $\Leftrightarrow \frac{1}{a} p^{2^{k}} [/mm]  > - [mm] 10^{- 8 } \quad \vert\; \cdot [/mm] a$


[mm] $\Leftrightarrow p^{2^{k}} [/mm] > - [mm] 10^{- 8 }a [/mm] $


Aber wie kann ich hier weiter machen ? Den Logarithmus kann ich noch nicht anwenden, da wir auf der rechten Seite einen negativen Ausdruck haben.




lg, Steve


Bezug
                        
Bezug
Newton - Verfahren (Beweis): Antwort
Status: (Antwort) fertig Status 
Datum: 00:38 Sa 11.01.2020
Autor: leduart

Hallo
natürlich muss der Betrag des Fehlers <10^(-8) sein.
Gruß ledum

Bezug
                                
Bezug
Newton - Verfahren (Beweis): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:53 Sa 11.01.2020
Autor: Steve96

Hi :)

> Hallo
>   natürlich muss der Betrag des Fehlers <10^(-8) sein.
>  Gruß ledum


Stimmt, das macht Sinn.


Wir müssen dann unser $k$ so bestimmen, dass [mm] $\vert e_{k} \vert [/mm] =  [mm] \left \vert - \frac{1}{a} p^{2^{k}} \right \vert [/mm] = [mm] \left \vert - \frac{1}{a} \left \vert ax_{0} - 1 \right \vert ^{2^{k}} \right \vert [/mm] = [mm] \left \vert \frac{1}{a} \right \vert \cdot \left \vert ax_{0} - 1 \right \vert^{2^{k}} [/mm] = [mm] \left \vert \frac{1}{a} \right \vert \cdot \left \vert (ax_{0} - 1)^{2^{k}} \right \vert [/mm] = [mm] \left \vert \frac{1}{a} \right \vert \cdot (ax_{0} [/mm] - [mm] 1)^{2^{k}} [/mm] = [mm] \frac{1}{\vert a \vert} \cdot (ax_{0} [/mm] - [mm] 1)^{2^{k}} [/mm]  < [mm] 10^{-8}$ [/mm] gilt.


Durch Umforme erhalten wir dann:


[mm] $\frac{1}{\vert a \vert} \cdot (ax_{0} [/mm] - [mm] 1)^{2^{k}} [/mm]  < [mm] 10^{-8}\quad\quad\quad \vert\; \cdot \vert [/mm] a [mm] \vert$ [/mm]

[mm] $\Leftrightarrow (ax_{0} [/mm] - [mm] 1)^{2^{k}} [/mm] < [mm] 10^{-8} \cdot \vert [/mm] a [mm] \vert \quad\quad\quad \vert\; log_{a}(\ldots)$ [/mm]

[mm] $\Leftrightarrow 2^{k} \cdot log_{a} (ax_{0} [/mm] - 1) < [mm] log_{a} \left ( 10^{-8} \cdot \vert a \vert \right )\quad\quad\quad \vert\; \cdot\frac{1}{log_{a} (ax_{0} - 1)}$ [/mm]

[mm] $\Leftrightarrow 2^{k} [/mm] < [mm] \frac{ log_{a} \left ( 10^{-8} \cdot \vert a \vert \right )}{log_{a} (ax_{0} - 1)} [/mm] = [mm] log_{ax_{0} - 1} \left ( 10^{-8} \cdot \vert a \vert \right [/mm] )$



Aber spätestens hier wird es problematisch, da [mm] $ax_{0} [/mm] - 1$ nicht unbedingt positiv sein muss. Wenn [mm] $ax_{0} [/mm] - 1$ negativ ist, dann kann ich nicht den Logarithmus zur Basis [mm] $ax_{0} [/mm] - 1$  nehmen, da dieser nicht existiert.


Wie kann man hier weiter verfahren?



Lg, Steve

Bezug
                                        
Bezug
Newton - Verfahren (Beweis): Antwort
Status: (Antwort) fertig Status 
Datum: 13:13 So 12.01.2020
Autor: Gonozal_IX

Hiho,

> Durch Umforme erhalten wir dann:

> [mm]\Leftrightarrow (ax_{0} - 1)^{2^{k}} < 10^{-8} \cdot \vert a \vert \quad\quad\quad \vert\; log_{a}(\ldots)[/mm]

Warum [mm] $\log_a$? [/mm]
Nehmen wir [mm] $\log_{10} [/mm] = [mm] \lg$ [/mm] so bekommen wir:

[mm] $2^k \lg(|ax_0 [/mm] - 1|) [mm] \le -8\lg(|a|)$ [/mm]  
(dein Fehler beginnt eigentlich hier, weil ja [mm] $(ax_0 [/mm] - 1)$ negativ sein kann. D.h. da muss der Betrag rum… darum war das auch in der Aufgabe zum Fehler gegeben.

D.h. [mm] $2^k \le -8\lg_{|ax_0 - 1|}(|a|)$ [/mm]

So würde ich das aber nicht schreiben, sondern es als Bruch belassen… kommst du von hier alleine weiter?

Gruß,
Gono

Bezug
                                                
Bezug
Newton - Verfahren (Beweis): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:28 So 12.01.2020
Autor: Steve96


> Hiho,
>  
> > Durch Umforme erhalten wir dann:
>  
> > [mm]\Leftrightarrow (ax_{0} - 1)^{2^{k}} < 10^{-8} \cdot \vert a \vert \quad\quad\quad \vert\; log_{a}(\ldots)[/mm]
>  
> Warum [mm]\log_a[/mm]?

Hallo!

Ich habe einfach so eine allgemeine Basis gewählt. Hätte dann nach der ganzen Umformung dann eine konkrete Basis gewählt.

>  Nehmen wir [mm]\log_{10} = \lg[/mm] so bekommen wir:
>  
> [mm]2^k \lg(|ax_0 - 1|) \le -8\lg(|a|)[/mm]  
> (dein Fehler beginnt eigentlich hier, weil ja [mm](ax_0 - 1)[/mm]
> negativ sein kann. D.h. da muss der Betrag rum… darum war
> das auch in der Aufgabe zum Fehler gegeben.





Genau, ich wollte ursprünglich auch die Betragsstriche nehmen, aber dann habe ich gedacht:


Es gilt doch [mm] $(ax_{0} [/mm] - [mm] 1)^{2^{k}} [/mm] = [mm] \vert ax_{0} [/mm] - 1 [mm] \vert^{2^{k}} [/mm] $.

Nach diese Logik müsste dann [mm] $log_{a} \left ( (ax_{0} - 1)^{2^{k}} \right [/mm] ) = [mm] log_{a} \left ( \vert ax_{0} - 1 \vert^{2^{k}} \right [/mm] )$ gelten und damit


$ [mm] {2^{k}} \cdot log_{a} \left ( ax_{0} - 1 \right [/mm] ) = [mm] {2^{k}} \cdot log_{a} \left ( \vert ax_{0} - 1 \vert \right [/mm] )$.



Aber jetzt fällt mir auf, das nur die Gleichung [mm] ${2^{k}} \cdot log_{a} \left ( \vert ax_{0} - 1 \vert \right [/mm] ) = [mm] log_{a} \left ( (ax_{0} - 1)^{2^{k}} \right [/mm] )$


Das heißt also, dass ich auf der rechten Seite die Potenz [mm] $2^{k}$ [/mm] nicht herausziehen darf.

> D.h. [mm]2^k \le -8\lg_{|ax_0 - 1|}(|a|)[/mm]
>  
> So würde ich das aber nicht schreiben, sondern es als
> Bruch belassen… kommst du von hier alleine weiter?

Meintest du vielleicht [mm] $lg(\vert [/mm] a [mm] \vert) [/mm] - 8$? Denn es ist: $lg [mm] \left (10^{-8} \cdot \vert a \vert \right [/mm] ) = [mm] lg\left ( 10^{- 8 } \right [/mm] ) + [mm] lg(\vert [/mm] a [mm] \vert [/mm] ) = - 8 [mm] \cdot [/mm] lg(10) + [mm] lg(\vert [/mm] a [mm] \vert [/mm] ) = [mm] lg(\vert [/mm] a [mm] \vert [/mm] ) - 8$.




Dann hätte ich insgesamt:



[mm] $2^{k} [/mm] < [mm] \frac{lg(\vert a \vert ) - 8}{lg(\vert a x_{0} - 1 \vert)}$ [/mm]

[mm] $\Leftrightarrow [/mm] k < [mm] log_{2} \left ( \frac{lg(\vert a \vert ) - 8}{lg(\vert a x_{0} - 1\vert)} \right [/mm] )$


Passt das so?


Wenn wir [mm] $x_{0} [/mm] = [mm] \frac{3}{2}$ [/mm] einsetzen, erhalten wir:

[mm] $\Leftrightarrow [/mm] k < [mm] log_{2} \left ( \frac{lg(\vert a \vert ) - 8}{lg(\vert \frac{3a}{2} - 1\vert)} \right [/mm] )$



Ich frage mich ab hier dann, wie unser $k$ konkret aussieht, wenn $a$ keine konkrete Zahl ist, sondern sich im Intervall [mm] $\left [ \frac{1}{2}, 1 \right [/mm] ]$ befindet.




In deiner ersten Antwort hast du geschrieben:


"Nun überlege noch, wie viele elementare Rechenoperationen du pro Schritt in dem Verfahren machst und du hast deine Lösung."


Nehmen wir an, es ist $ k = 8$.

Unsere Iterationsvorschrift für die $f(x) = [mm] \frac{1}{x} [/mm] - a$ lautet doch: [mm] $x_{k + 1} [/mm] = [mm] x_{k} [/mm] - [mm] x_{k} [/mm] (1 - [mm] ax_{k})$ [/mm]

Wir insgesamt 8 Iterationen vorzunehmen, damit der Fehler kleiner ist als [mm] $10^{-8}$ [/mm] ist, stimmts ?

In unserer Iterationsvorschrift haben wir 4 elementare Rechenoperationen.

Wir haben die Multiplikation [mm] $ax_{k}$, [/mm] die Differenz $1 - [mm] ax_{k}$, [/mm] die Multiplikation [mm] $x_{k} [/mm] (1 - [mm] ax_{k})$ [/mm] und die Differenz [mm] $x_{k} [/mm] - [mm] x_{k} [/mm] (1 - [mm] ax_{k})$. [/mm]

Wir haben also pro Schritt $4$ elementare Rechenoperationen durchzuführen. Da wir insgesamt $8$ Iterationen vornehmen müssen, haben wir insgesamt $4 [mm] \cdot [/mm] 8 = 32$ elementare Rechenoperationen.



Ist die Überlegung richtig, oder habe ich was übersehen ?



lg, Steve


Bezug
                                                        
Bezug
Newton - Verfahren (Beweis): Antwort
Status: (Antwort) fertig Status 
Datum: 18:27 So 12.01.2020
Autor: Gonozal_IX

Hiho,

> Es gilt doch $ [mm] (ax_{0} [/mm] - [mm] 1)^{2^{k}} [/mm] = [mm] \vert ax_{0} [/mm] - 1 [mm] \vert^{2^{k}} [/mm] $.
> Nach diese Logik müsste dann $ [mm] log_{a} \left ( (ax_{0} - 1)^{2^{k}} \right [/mm] ) = [mm] log_{a} \left ( \vert ax_{0} - 1 \vert^{2^{k}} \right [/mm] ) $ gelten und damit
> $ [mm] {2^{k}} \cdot log_{a} \left ( ax_{0} - 1 \right [/mm] ) = [mm] {2^{k}} \cdot log_{a} \left ( \vert ax_{0} - 1 \vert \right [/mm] ) $.
> Aber jetzt fällt mir auf, das nur die Gleichung $ [mm] {2^{k}} \cdot log_{a} \left ( \vert ax_{0} - 1 \vert \right [/mm] ) = [mm] log_{a} \left ( (ax_{0} - 1)^{2^{k}} \right [/mm] ) $

> Das heißt also, dass ich auf der rechten Seite die Potenz $ [mm] 2^{k} [/mm] $ nicht herausziehen darf.

Na darfst du schon, aber für den Fall, dass [mm] $(ax_0 [/mm] - 1)$ negativ ist, steht da eben was undefiniertes. [mm] $(ax_0 [/mm] - [mm] 1)^{2^k}$ [/mm] wird hingegen nie negativ, dem muss man also mit den Betragsstrichen Rechnung tragen.

> Meintest du vielleicht $ [mm] lg(\vert [/mm] a [mm] \vert) [/mm] - 8 $? Denn es ist: $ lg [mm] \left (10^{-8} \cdot \vert a \vert \right [/mm] ) = [mm] lg\left ( 10^{- 8 } \right [/mm] ) + [mm] lg(\vert [/mm] a [mm] \vert [/mm] ) = - 8 [mm] \cdot [/mm] lg(10) + [mm] lg(\vert [/mm] a [mm] \vert [/mm] ) = [mm] lg(\vert [/mm] a [mm] \vert [/mm] ) - 8 $.

Ja meinte ich. Danke für die Korrektur.

Zu deiner Lösung rollen wir das Pferd mal von Hinten auf, damit du auch mal selbst überlegst zukünftig, ob deine Lösungen Sinn machen:

Du hast ja:
$ [mm] \Leftrightarrow [/mm] k < [mm] log_{2} \left ( \frac{lg(\vert a \vert ) - 8}{lg(\vert \frac{3a}{2} - 1\vert)} \right [/mm] ) $

Da fallen mir sofort zwei Dinge auf:

1.) Du erhältst also einen Ausdruck, dass k kleiner sein soll als eine bestimmte positive Schranke. Offensichtlich erfüllt $k=0$ das immer.  Also bin ich immer nach dem ersten Schritt fertig?
Das sieht falsch aus. Finde deinen Fehler, wann du vergessen hast aus dem $<$ ein $>$ zu machen.

2.) Für $a = [mm] \frac{3}{2} \in \left [ \frac{1}{2}, 1 \right [/mm] ] $ steht im Nenner [mm] $\lg(0)$, [/mm] was nicht definiert ist. Finde den Fehler, wann eine Fallunterscheidung notwendig geworden wäre und was gilt in diesem Fall?

> Ich frage mich ab hier dann, wie unser k konkret aussieht, wenn a keine konkrete Zahl ist, sondern sich im Intervall $ [mm] \left [ \frac{1}{2}, 1 \right [/mm] ] $ befindet.

Ich gehe hier jetzt mal vom korrekten Ausdruck $k > [mm] log_{2} \left ( \frac{lg(\vert a \vert ) - 8}{lg(\vert \frac{3a}{2} - 1\vert)} \right [/mm] ) $ aus.
Die Frage ist ja, was sind die maximal notwendigen Schritte, d.h. du musst halt ausrechnen, wie viele Schritte k du im "worst case" berechnen musst. D.h. was ist das "ungünstigste" aller $a [mm] \in \left [ \frac{1}{2}, 1 \right [/mm] ] $… naja, d.h. eben: Maximiere  [mm] $\log_{2} \left ( \frac{lg(\vert a \vert ) - 8}{lg(\vert \frac{3a}{2} - 1\vert)} \right [/mm] )$ über alle möglichen a.

Oder man macht es sich bequem, plottet das ganze und stellt fest: Das Maximum wird am Rand angenommen.

Oder (das ist wohl der eleganteste Weg): Man überlegt sich, wo [mm] $e_k$ [/mm] am größten ist, denn dann brauche ich ja auch die meisten Schritte um den Fehler klein zu bekommen.

Deine Überlegung zu den Rechenoperationen ist mMn korrekt, d.h. die Lösung wäre dann eben 4k mit obigem k.

Gruß,
Gono


Bezug
                                                                
Bezug
Newton - Verfahren (Beweis): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:56 So 12.01.2020
Autor: Steve96


> Du hast ja:
> [mm]\Leftrightarrow k < log_{2} \left ( \frac{lg(\vert a \vert ) - 8}{lg(\vert \frac{3a}{2} - 1\vert)} \right )[/mm]
>  
> Da fallen mir sofort zwei Dinge auf:
>  
> 1.) Du erhältst also einen Ausdruck, dass k kleiner sein
> soll als eine bestimmte positive Schranke. Offensichtlich
> erfüllt [mm]k=0[/mm] das immer.  Also bin ich immer nach dem ersten
> Schritt fertig?
> Das sieht falsch aus. Finde deinen Fehler, wann du
> vergessen hast aus dem [mm]<[/mm] ein [mm]>[/mm] zu machen.



Also, damit der Ausdruck [mm] $log_{2} \left ( \frac{log_{10} (\vert a \vert ) - 8}{log_{10} \left ( \vert \frac{3a}{2} - 1 \vert \right )} \right [/mm] )$ überhaupt existiert kann, muss das Argument $ [mm] \frac{log_{10} (\vert a \vert ) - 8}{log_{10} \left ( \frac{3a}{2} - 1 \right )}$ [/mm] > 0 sein.


Man sieht schnell, dass der Zähler [mm] $log_{10} (\vert [/mm] a [mm] \vert [/mm] ) - 8$ des Arguments für alle $a [mm] \in [/mm] [0.5, 1]$ negativ ist.


Damit [mm] $log_{2} \left ( \frac{log_{10} (\vert a \vert ) - 8}{log_{10} \left ( \vert \frac{3a}{2} - 1 \vert \right )} \right [/mm] )$ existiert, muss nun

[mm] $log_{10} \left ( \vert \frac{3a}{2} - 1 \vert \right [/mm] )$ negativ sein.


Damit  [mm] $log_{10} \left ( \vert \frac{3a}{2} - 1 \vert \right [/mm] )$ negativ ist, muss $ [mm] \vert \frac{3a}{2} [/mm] - 1 [mm] \vert \in [/mm] (0, 1)$ gelten.



Das ist nur der Fall für $a [mm] \in [/mm] [0.5, [mm] 1]\setminus \left \{ \frac{3}{4}, \frac{2}{3} \right \}$ [/mm]



Das heißt also, dass nur für  $a [mm] \in [/mm] [0.5, [mm] 1]\setminus \left \{ \frac{3}{4}, \frac{2}{3} \right \}$ [/mm] die folgende Umformung gültig ist:


[mm] $2^{k} \cdot log_{10} \left ( \vert \frac{3a}{2} - 1 \vert \right [/mm] ) < [mm] log_{10}(\vert [/mm] a [mm] \vert) [/mm] - 8$

[mm] $\Leftrightarrow 2^{k} [/mm] > [mm] \frac{log_{10}(\vert a \vert) - 8}{log_{10} \left ( \vert \frac{3a}{2} - 1 \vert \right )}$ [/mm]


$ [mm] \Leftrightarrow [/mm] k > [mm] log_{2} \left ( \frac{lg(\vert a \vert ) - 8}{lg(\vert \frac{3a}{2} - 1\vert)} \right [/mm] )$




Richtig so?



Und was mache ich dann mit $a [mm] \in \left \{ \frac{3}{4}, \frac{2}{3} \right \}$ [/mm] ?


> Ich gehe hier jetzt mal vom korrekten Ausdruck [mm]k > log_{2} \left ( \frac{lg(\vert a \vert ) - 8}{lg(\vert \frac{3a}{2} - 1\vert)} \right )[/mm]
> aus.
> Die Frage ist ja, was sind die maximal notwendigen
> Schritte, d.h. du musst halt ausrechnen, wie viele Schritte
> k du im "worst case" berechnen musst. D.h. was ist das
> "ungünstigste" aller [mm]a \in \left [ \frac{1}{2}, 1 \right ] [/mm]…
> naja, d.h. eben: Maximiere  [mm]\log_{2} \left ( \frac{lg(\vert a \vert ) - 8}{lg(\vert \frac{3a}{2} - 1\vert)} \right )[/mm]
> über alle möglichen a.
>  
> Oder man macht es sich bequem, plottet das ganze und stellt
> fest: Das Maximum wird am Rand angenommen.


Wenn ich das plotte, dann ist das Maximum bei ca. 4,7...

Das heißt, dass $k = 5$ ist und wir dann insgesamt 20 Iterationsschritte haben.




lg, Steve

Bezug
                                                                        
Bezug
Newton - Verfahren (Beweis): Antwort
Status: (Antwort) fertig Status 
Datum: 07:07 Mo 13.01.2020
Autor: Gonozal_IX

Hiho,

> Damit  [mm]log_{10} \left ( \vert \frac{3a}{2} - 1 \vert \right )[/mm]
> negativ ist, muss [mm]\vert \frac{3a}{2} - 1 \vert \in (0, 1)[/mm]
> gelten.
>
> Das ist nur der Fall für [mm]a \in [0.5, 1]\setminus \left \{ \frac{3}{4}, \frac{2}{3} \right \}[/mm]

Also wieso du [mm] \frac{3}{4} [/mm] ausschließt, ist mir nicht klar…
  

>
>
> Das heißt also, dass nur für  [mm]a \in [0.5, 1]\setminus \left \{ \frac{3}{4}, \frac{2}{3} \right \}[/mm]
> die folgende Umformung gültig ist:

> [mm]\Leftrightarrow k > log_{2} \left ( \frac{lg(\vert a \vert ) - 8}{lg(\vert \frac{3a}{2} - 1\vert)} \right )[/mm]

> Richtig so?

Mit der offenen Frage, wieso das für [mm] \frac{3}{4} [/mm] nicht gehen sollte…  

> Und was mache ich dann mit [mm]a \in \left \{ \frac{3}{4}, \frac{2}{3} \right \}[/mm]

Na die [mm] \frac{3}{4} [/mm] nimmst du oben einfach mit dazu ;-)

Bei der [mm] $\frac{2}{3}$: [/mm] Überlege mal, was das bedeutet, dass $a = [mm] \frac{2}{3}$ [/mm] ist… welche Größe hat dann dein Fehler? Schlussfolgerung?

Gruß,
Gono

Bezug
                                                                                
Bezug
Newton - Verfahren (Beweis): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:31 Mo 13.01.2020
Autor: Steve96



Hey :-D

> Also wieso du [mm]\frac{3}{4}[/mm] ausschließt, ist mir nicht
> klar…


Tut mir Leid, ich meinte [mm] $\frac{4}{3}$. [/mm] Aber da $a [mm] \in [/mm] [0.5, 1]$ ist, kommt  [mm] $\frac{4}{3}$ [/mm] also nicht in Frage.


> Bei der [mm]\frac{2}{3}[/mm]: Überlege mal, was das bedeutet, dass
> [mm]a = \frac{2}{3}[/mm] ist… welche Größe hat dann dein Fehler?
> Schlussfolgerung?



Unser Fehler ist gegeben  durch:


[mm] $e_{k} [/mm] = - [mm] \frac{1}{1} \vert [/mm] a [mm] x_{0} [/mm] - 1 [mm] \vert [/mm] ^{2k}$

Wenn $a = [mm] \frac{2}{3}$ [/mm] ist, haben wir:


[mm] $e_{k} [/mm] = - [mm] \frac{3}{2} \left \vert \frac{2}{3} \cdot \frac{3}{2} - 1\right \vert^{2^{k}} [/mm] = - [mm] \frac{3}{2} \left \vert 1 - 1\right \vert^{2^{k}} [/mm] =  - [mm] \frac{3}{2} \cdot [/mm] 0 = [mm] 0\quad \forall [/mm] k [mm] \in \mathbb{N}$. [/mm]


Wenn ich das interpretieren müsste, würde ich sagen, dass wir bei der Funktion $f(x) = [mm] \frac{1}{x} [/mm] - [mm] \frac{2}{3}$ [/mm] die Nullstelle $x = [mm] \frac{3}{2}$ [/mm] richtig geraten  haben. Und da wir die Nullstelle richtig geraten haben, ist es dann logisch, dass der Fehler für jedes $k$ gleich $0$ ist.

Die Iteration bricht schon bei $k = 0$ ab.


Richtig ?


Und vielleicht kurz noch eine Frage zur $b)$. Da hast du mich bei der Induktion korrigiert und hast geschrieben, dass ich die Induktion nicht für $p = [mm] \vert ax_{0} [/mm] - 1 [mm] \vert$ [/mm] gezeigt habe, sondern für $p =  [mm] ax_{0} [/mm] - 1 $.

Aber als ich das korrigiert habe, hat sich an der Induktion nichts verändert. Ich habe dann immer noch:




Induktionsbehauptung
__________________

[mm] $\exists [/mm] k [mm] \in \mathbb{N}: e_{k} [/mm] = [mm] x_{k} [/mm] - [mm] \frac{1}{a} [/mm] = - [mm] \frac{1}{a} \vert ax_{0} [/mm] - 1 [mm] \vert^{2^{k}}$ [/mm]



Induktionsschritt
______________


Wir müssen zeigen:

[mm] $x_{k} [/mm] - [mm] \frac{1}{a} [/mm] = - [mm] \frac{1}{a} \vert ax_{0} [/mm] - 1 [mm] \vert^{2^{k}} \Rightarrow x_{k + 1} [/mm] - [mm] \frac{1}{a} [/mm] = - [mm] \frac{1}{a} \vert ax_{0} [/mm] - 1 [mm] \vert^{2^{k + 1}} [/mm]



Wir haben:


[mm] $e_{k + 1} [/mm] = - [mm] ae_{k}^{2} \overset{\text{IB}}{\underset{\text{}}{=}} [/mm] - a [mm] \cdot \left ( \frac{1}{a} \vert ax_{0} - 1 \vert^{2^{k}} \right )^{2} [/mm] = - a [mm] \cdot \frac{1}{a^{2}} \vert ax_{0} [/mm] - 1 [mm] \vert^{2^{k + 1}} [/mm] =  - [mm] \frac{1}{a} p^{2^{k + 1}}$ [/mm]



q.e.d





Sonst habe ich keine Fragen mehr und bedanke mich herzlich nochmal bei dir. Bist für mich, wie immer, eine sehr große Hilfe!

Bezug
                                                                                        
Bezug
Newton - Verfahren (Beweis): Antwort
Status: (Antwort) fertig Status 
Datum: 13:48 Mo 13.01.2020
Autor: Gonozal_IX

Hiho,

> Wenn ich das interpretieren müsste, würde ich sagen, dass
> wir bei der Funktion [mm]f(x) = \frac{1}{x} - \frac{2}{3}[/mm] die
> Nullstelle [mm]x = \frac{3}{2}[/mm] richtig geraten  haben. Und da
> wir die Nullstelle richtig geraten haben, ist es dann
> logisch, dass der Fehler für jedes [mm]k[/mm] gleich [mm]0[/mm] ist.
>
> Die Iteration bricht schon bei [mm]k = 0[/mm] ab.

[ok]


> Aber als ich das korrigiert habe, hat sich an der Induktion
> nichts verändert. Ich habe dann immer noch:

Ja. Ich hatte ja schon erwähnt: Durch die gerade Potenz ist es völlig wurscht, ob man (a-b) oder |a-b| schreibt, weil nach der Potenzierung eh alles positiv ist.

Gruß,
Gono

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


^ Seitenanfang ^
www.vorhilfe.de