Beziehung der Funktion zeigen < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:32 Mi 28.10.2015 | | Autor: | Joseph95 |
| Aufgabe | f(n) [mm] \in [/mm] O(g(n)) ⇔ [mm] (\exists [/mm] c>0 [mm] \exists n_{0} \in\IN\forall [/mm] n [mm] \ge n_{0})[f(n) \le [/mm] c·g(n)]
f(n) [mm] \in [/mm] Ω(g(n)) ⇔ [mm] (\exists [/mm] c>0 [mm] \exists n_{0} \in\IN\forall [/mm] n [mm] \ge n_{0})[f(n) \ge [/mm] c·g(n)]
f(n) [mm] \in [/mm] Θ(g(n)) ⇔ f(n) [mm] \in [/mm] O(g(n)) und f(n) [mm] \in [/mm] Ω(g(n))
Zeigen Sie, dass für die Funktion f(n) := [mm] \summe_{i=1}^{n} \bruch{1}{i} [/mm] die Beziehung f(n) [mm] \in [/mm] θ(log(n)) gilt. Beweisen Sie dazu zunächst die Beziehung f(n) - 1 [mm] \le \integral_{1}^{n+1}{\bruch{1}{x}dx} \le [/mm] f(n), indem Sie das Integral der Funktion 1/x betrachten (=Fläche unterhalb des Funktionsgraphen. Werten Sie anschliessend das Integral aus und folgern Sie das Gewünschte. |
Hey Leute,
ich studiere seit einigen Wochen nun Mathematik und ich muss sagen, ohne euch wäre das schon längst schief gelaufen, deshalb vorab nochmals vielen Dank bisher. Leider verzweifle ich noch an einer Aufgabe, und erbitte deshalb eure Hilfe.
Nachdem ich mir nun die Aufgabe genau durchgelesen habe, würde ich wie folgt beginnen: Ich zeige zunächst,
1) f(n) - 1 [mm] \le \integral_{1}^{n+1}{\bruch{1}{x}dx}
[/mm]
2) [mm] \integral_{1}^{n+1}{\bruch{1}{x}dx} \le [/mm] f(n)
1) [mm] \summe_{i=1}^{n} \bruch{1}{i} [/mm] - 1 [mm] \le \integral_{1}^{n+1}{\bruch{1}{x}dx}
[/mm]
=> [mm] \summe_{i=1}^{n} \bruch{1}{i} [/mm] - 1 [mm] \le [/mm] ln(n+1) - ln(1)
=> [mm] \summe_{i=1}^{n} \bruch{1}{i} [/mm] - 1 [mm] \le [/mm] ln(n+1)
Ab hier komme ich nicht mehr weiter. Habt ihr vielleicht Ideen wie ich vorgehen kann?
Vielen Dank,
Joseph95
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:09 Mi 28.10.2015 | | Autor: | hippias |
Da wird wohl kein ganz strenger Beweis erwartet, da ihr Rieman-Integrale sicher noch nicht behandelt habt.
Daher erinnere Dich wie ihr Integrale in der Schule eingefuehrt habt. Zuerst skizziere den Graphen der Funktion [mm] $f(x)=\frac{1}{x}$ [/mm] im Interval $[1,n+1]$. Sodann zerlege das Interval in $n+1$ Teilintervalle der Länge $1$. Man kann den Inhalt der von der $x$-Achse und dem Graphen von $f$ eingeschlossenen Fläche durch eine Summe von Rechteckflaechen approximieren.
Diese Approximation kann auf zwei Arten durchgefuehrt werden:
1. Du zeichnest die Rechtecke jeweils vom linken Startpunkt der Teilintervalle bis vom Graphen von $f$ hoch; diese Rechtecke ragen alle ein wenige ueber $f$ hinaus.
2. Du zeichnest die Rechtecke jeweils vom rechten Endpunkt der Teilintervalle bis vom Graphen von $f$ hoch; diese Rechtecke liegen alle unterhalb von $f$.
Fuer die Rechteckflaechen gilt [mm] Länge$\times$ [/mm] Breite, also für das $i$-te Rechteck der 1. Sorte [mm] $f(i)\cdot [/mm] 1= [mm] \frac{1}{i}$. [/mm] Dies Summe all dieser ist damit [mm] $\sum_{i=1}^{n} \frac{1}{i}$.
[/mm]
Nun fuehre dies auch für die Rechtecke der zweiten Sorte durch und vergleiche mit dem Integral.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:39 Mi 28.10.2015 | | Autor: | Joseph95 |
Okey, soweit habe ich es jetzt dank dir verstanden. Der rechte Teil der Ungleichung, sprich:
[mm] \summe_{i=1}^{n}\bruch{1}{i}
[/mm]
entspricht damit der Obersumme. Dann gehe ich mal stark davon aus, dass
[mm] \summe_{i=1}^{n}\bruch{1}{i}-1
[/mm]
der Untersumme entsprechen soll.
Hier habe ich ein Problem, ich kenne die Untersumme definiert als:
[mm] \summe_{i=2}^{n+1}\bruch{1}{i}
[/mm]
Jedoch weiß ich nicht was die Bedeutung von -1 sein soll, beziehungsweise wie ich aus
[mm] \summe_{i=2}^{n+1}\bruch{1}{i}
[/mm]
schließen kann, dass [mm] \summe_{i=1}^{n}\bruch{1}{i}-1 \le [/mm] dem Integral ist?
Vg,
Joseph95
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:20 Do 29.10.2015 | | Autor: | hippias |
Dann vergleiche die beiden Terme: wodurch unterscheiden sie sich? was wurde gekürzt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:49 Do 29.10.2015 | | Autor: | fred97 |
> Okey, soweit habe ich es jetzt dank dir verstanden. Der
> rechte Teil der Ungleichung, sprich:
> [mm]\summe_{i=1}^{n}\bruch{1}{i}[/mm]
> entspricht damit der Obersumme.
Das stimmt. Die Obersumme [mm] O_n [/mm] ist also =f(n)
> Dann gehe ich mal stark
> davon aus, dass
> [mm]\summe_{i=1}^{n}\bruch{1}{i}-1[/mm]
> der Untersumme entsprechen soll.
Nein.
> Hier habe ich ein Problem, ich kenne die Untersumme
> definiert als:
> [mm]\summe_{i=2}^{n+1}\bruch{1}{i}[/mm]
Das stimmt. Die Untersumme [mm] U_n [/mm] ist also [mm] =\summe_{i=2}^{n+1}\bruch{1}{i}
[/mm]
Überlege Dir:
[mm] U_n=f(n)+\bruch{1}{n+1}-1
[/mm]
> Jedoch weiß ich nicht was die Bedeutung von -1 sein soll,
> beziehungsweise wie ich aus
> [mm]\summe_{i=2}^{n+1}\bruch{1}{i}[/mm]
> schließen kann, dass [mm]\summe_{i=1}^{n}\bruch{1}{i}-1 \le[/mm]
> dem Integral ist?
Wir haben dann
$f(n)-1 [mm] \le U_n \le \integral_{1}^{n+1}{1/x dx} \le f(n)=O_n$
[/mm]
FRED
>
>
> Vg,
> Joseph95
|
|
|
|
