matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

For pupils, students, teachers.
Hello Guest!Log In | Register ]
Home · Forum · Knowledge · Courses · Members · Team · Contact
Navigation
 Home...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Tools...
 Agency for private tuition beta...
 Online Games beta
 Search
 Registered Society...
 Contact
Forenbaum
^ Tree of Forums
Status Maths
  Status School
    Status Grades 1-4
    Status Grades 5-7
    Status Grades 8-10
    Status Grades 11-12
    Status Mathematical Contest
    Status School maths - Miscellaneous
  Status University
    Status Uni-Calculus
    Status Uni-LinA u. Algebra
    Status Algebra and Number Theoriy
    Status Discrete Mathematics
    Status Teaching Methodology
    Status Financial Maths and Actuarial Theory
    Status Logic and Set Theory
    Status 
    Status Stochastic Theory
    Status Topology and Geometry
    Status Uni Maths - Miscellaneous
  Status Courses on maths
    Status 
    Status 
    Status Universität
  Status Software for maths
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Calculators

Only forums with an interest level bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
The project is organised by our team of coordinators.
Hundreds of members help out in our moderated forums.
Service provider for this webpage is the Registered Society "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
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.mathspace.org
[ Home | Forum | Knowledge | Courses | Members | Team | Contact ]