Newton - Verfahren (Beweis) < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | 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
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:38 Sa 11.01.2020 | | Autor: | leduart |
Hallo
natürlich muss der Betrag des Fehlers <10^(-8) sein.
Gruß ledum
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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!
|
|
|
| |
|
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]](/images/smileys/ok.gif "[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
|
|
|
|
