Obere Schranke < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:13 Di 19.11.2013 | | Autor: | papilio |
Hallo,
ich habe hier einen Beweis, über eine Schranke, an der letzten Umformung komme ich nicht weiter.
Ich überspringe den Anfang.....
.... j [mm] \le \wurzel{2 \pi} \Delta^{2} n^{2,5} ln(2^{n} [/mm] n! [mm] n^{ \bruch{n}{2} } \Delta^{n} [/mm] )
Meine obere Schranke ist nun O( [mm] \Delta^{2} n^{3,5} [/mm] log(n [mm] \Delta))
[/mm]
Zur Erklärung noch, [mm] \Delta [/mm] ist der Betrag von einer Unterdeterminante von A [mm] \in \IZ^{mxn}
[/mm]
Mein Ansatz bisher, damit ich [mm] n^{3,5} [/mm] erreiche, werde ich ein ^{n} aus dem ln herrausziehen. Das [mm] \wurzel{2\pi} [/mm] kommt "weg", da als Konstante nicht interessant.
Und der Rest? Wie kann ich den geschickt umformen?
Ich danke für jede Hilfreiche Antwort.
|
|
| |
|
Hallo papilio,
> Hallo,
>
> ich habe hier einen Beweis, über eine Schranke, an der
> letzten Umformung komme ich nicht weiter.
>
> Ich überspringe den Anfang.....
>
> .... j [mm]\le \wurzel{2 \pi} \Delta^{2} n^{2,5} ln(2^{n}[/mm] n!
> [mm]n^{ \bruch{n}{2} } \Delta^{n}[/mm] )
>
> Meine obere Schranke ist nun O( [mm]\Delta^{2} n^{3,5}[/mm] log(n
> [mm]\Delta))[/mm]
>
> Zur Erklärung noch, [mm]\Delta[/mm] ist der Betrag von einer
> Unterdeterminante von A [mm]\in \IZ^{mxn}[/mm]
>
> Mein Ansatz bisher, damit ich [mm]n^{3,5}[/mm] erreiche, werde ich
> ein ^{n} aus dem ln herrausziehen. Das [mm]\wurzel{2\pi}[/mm] kommt
> "weg", da als Konstante nicht interessant.
> Und der Rest? Wie kann ich den geschickt umformen?
Das ist etwas Rechnerei; ich habe das vllt. etwas umständlich gemacht, komme aber auf die Lösung.
Du musst die Logarithmusklammer "kaputt" kriegen:
[mm]\log\left(2^n\cdot{}n!\cdot{}n^{n/2}\cdot{}\Delta^n\right)=\log(n!)+n\cdot{}\log\left(2\cdot{}\Delta\cdot{}n^{1/2}\right)[/mm]
Und das [mm]\log(n!)[/mm] kannst du mit der Stirlingformel klein kriegen ...
Versuch's mal weiter ...
>
> Ich danke für jede Hilfreiche Antwort.
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:59 Di 19.11.2013 | | Autor: | papilio |
Hallo schachuzipus,
vielen Dank ersteinmal für deine Hilfe.
Die Stirlingformel war mir nicht bewusst.
Ich habe mich deswegen erst informieren müssen und diese Abschätzung gefunden und benutzt:
log(n!) < (n+1) log(n+1)-n
Die Abschätzung habe ich nun benutzt und bin nach einigen Umformungen auf dies gekommen
[mm] \wurzel{2 \pi} \Delta^{2}n^{3,5}log(n^{ \bruch{3}{2}} [/mm] 2 [mm] \Delta [/mm] + [mm] n^{\bruch{1}{2}} [/mm] 2 [mm] \Delta) [/mm] - [mm] \wurzel{2 \pi} \Delta^{2}n^{3,5} [/mm] + [mm] \wurzel{2 \pi} \Delta^{2}n^{2,5} [/mm] log(n+1)
Ist das so richtig, weil ich das Ende immer noch nicht sehe...
Viele Grüße
papilio
|
|
|
| |
|
Hallo nochmal,
> Hallo schachuzipus,
>
> vielen Dank ersteinmal für deine Hilfe.
>
> Die Stirlingformel war mir nicht bewusst.
> Ich habe mich deswegen erst informieren müssen und diese
> Abschätzung gefunden und benutzt:
>
> log(n!) < (n+1) log(n+1)-n
Ich hatte eher im Sinn: [mm]n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n[/mm]
Damit dann [mm]\log(n!)\approx 1/2\log(2\pi n)+n\log\left(n/e\right)[/mm]
Das zusammen mit dem anderen [mm]log[/mm]-Term, also mit [mm]n\log(2\Delta n^{1/2})[/mm] betrachten, dann kannst du n ausklammern und kommst auf [mm]n\log(2/e \Delta n^{3/2})[/mm]
Insgesamt ergibt das für den urprünglichen [mm]\log[/mm]-Term:
[mm]1/2\log(2\pi n)+n\log(2/e \Delta n^{3/2})[/mm]
Das kannst du mit dem Faktor, der vor dem log stand verwurschteln zu
[mm]\mathcal O\left(\Delta^2n^{2,5}\cdot{}\left[\log(n)+n\log(\Delta n^{3/2})\right]\right)[/mm]
(Wenn ich das richtig hier auf dem Schmierblatt sehe  )
Rechne das mal nach; von da aus ist es nämlich nicht mehr weit ...
>
> Die Abschätzung habe ich nun benutzt und bin nach einigen
> Umformungen auf dies gekommen
>
> [mm]\wurzel{2 \pi} \Delta^{2}n^{3,5}log(n^{ \bruch{3}{2}}[/mm] 2 [mm]\Delta[/mm] + [mm]n^{\bruch{1}{2}}[/mm] 2 [mm]\Delta)[/mm] - [mm]\wurzel{2 \pi} \Delta^{2}n^{3,5}[/mm] + [mm]\wurzel{2 \pi} \Delta^{2}n^{2,5}[/mm] log(n+1)
>
> Ist das so richtig, weil ich das Ende immer noch nicht
> sehe...
Ich sehe nicht mal, wie du darauf kommst
Du solltest den ein oder anderen Rechenschritt oder zumindest Kommentar spendieren ...
>
>
> Viele Grüße
> papilio
>
Gruß zurück!
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:24 Di 19.11.2013 | | Autor: | papilio |
> Hallo nochmal,
>
>
> > Hallo schachuzipus,
> >
> > vielen Dank ersteinmal für deine Hilfe.
> >
> > Die Stirlingformel war mir nicht bewusst.
> > Ich habe mich deswegen erst informieren müssen und
> diese
> > Abschätzung gefunden und benutzt:
> >
> > log(n!) < (n+1) log(n+1)-n
>
> Ich hatte eher im Sinn: [mm]n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n[/mm]
>
> Damit dann [mm]\log(n!)\approx 1/2\log(2\pi n)+n\log\left(n/e\right)[/mm]
>
> Das zusammen mit dem anderen [mm]log[/mm]-Term, also mit
> [mm]n\log(2\Delta n^{1/2})[/mm] betrachten, dann kannst du n
> ausklammern und kommst auf [mm]n\log(2/e \Delta n^{3/2})[/mm]
>
> Insgesamt ergibt das für den urprünglichen [mm]\log[/mm]-Term:
>
> [mm]1/2\log(2\pi n)+n\log(2/e \Delta n^{3/2})[/mm]
>
> Das kannst du mit dem Faktor, der vor dem log stand
> verwurschteln zu
>
> [mm]\mathcal O\left(\Delta^2n^{2,5}\cdot{}\left[\log(n)+n\log(\Delta n^{3/2})\right]\right)[/mm]
>
> (Wenn ich das richtig hier auf dem Schmierblatt sehe )
>
> Rechne das mal nach; von da aus ist es nämlich nicht mehr
> weit ...
Ahhh... Dein Schmierzettel stimmt mit meinem überein ;)
Nun habe ich [mm] [\bruch{1}{2}\log(2\pi n)+n\log(\bruch{2}{e}\Delta n^{3/2})] [/mm] mit + und - n [mm] \log (n^{\bruch{1}{2}}) [/mm] erweitert.
Das - n [mm] \log (n^{\bruch{1}{2}}) [/mm] mit [mm] n\log(\bruch{2}{e}\Delta n^{3/2}) [/mm] zusammengerechnet und die anderen beiden logarithmen ebenso.
Und komme auf [mm] \wurzel{2\pi} \Delta^{2}n^{3,5} \log (\Delta [/mm] n [mm] \bruch{2}{e}) [/mm] + [mm] \wurzel{2\pi} \Delta^{2}n^{2,5} \bruch{1}{2} \log [/mm] (2 [mm] \pi n^{1-n})
[/mm]
Da der zweite Term einen geringeren Grad hat, fällt der in meiner Abschätzung weg. Die Konstanten ebenso und ich bekomme die Behauptung
[mm]\mathcal O\left(\Delta^2n^{3,5}\cdot{}\left[\log(\Delta n)\right]\right)[/mm]
Ist das so richtig Argumentiert?
>
>
> >
> > Die Abschätzung habe ich nun benutzt und bin nach
> einigen
> > Umformungen auf dies gekommen
> >
> > [mm]\wurzel{2 \pi} \Delta^{2}n^{3,5}log(n^{ \bruch{3}{2}}[/mm] 2
> [mm]\Delta[/mm] + [mm]n^{\bruch{1}{2}}[/mm] 2 [mm]\Delta)[/mm] - [mm]\wurzel{2 \pi} \Delta^{2}n^{3,5}[/mm]
> + [mm]\wurzel{2 \pi} \Delta^{2}n^{2,5}[/mm] log(n+1)
> >
> > Ist das so richtig, weil ich das Ende immer noch nicht
> > sehe...
>
> Ich sehe nicht mal, wie du darauf kommst
>
> Du solltest den ein oder anderen Rechenschritt oder
> zumindest Kommentar spendieren ...
>
> >
Das vergessen wir jetzt einmal....
> >
> > Viele Grüße
> > papilio
> >
>
> Gruß zurück!
>
> schachuzipus
Noch einem Gruß meinerseits =)
|
|
|
| |
|
Hi nochmal,
muss gerade schnell los, gucke mir das aber später noch mal an, falls sich in der Zwischenzeit kein anderer findet ...
Gruß
schachuzipus
|
|
|
| |
|
Hallo nochmal,
> Ahhh... Dein Schmierzettel stimmt mit meinem überein ;)
> Nun habe ich [mm][\bruch{1}{2}\log(2\pi n)+n\log(\bruch{2}{e}\Delta n^{3/2})][/mm]
> mit + und - n [mm]\log (n^{\bruch{1}{2}})[/mm] erweitert.
> Das - n [mm]\log (n^{\bruch{1}{2}})[/mm] mit
> [mm]n\log(\bruch{2}{e}\Delta n^{3/2})[/mm] zusammengerechnet und die
> anderen beiden logarithmen ebenso.
>
> Und komme auf [mm]\wurzel{2\pi} \Delta^{2}n^{3,5} \log (\Delta[/mm]n [mm]\bruch{2}{e})[/mm] + [mm]\wurzel{2\pi} \Delta^{2}n^{2,5} \bruch{1}{2} \log[/mm](2 [mm]\pi n^{1-n})[/mm]
Muss es ganz hinten nicht [mm]1/2\log\left(2\pi n^{1\red +n}\right)[/mm] sein?
Du addierst ja 2 Logarithmen, womit sich die Argumente multiplizieren ...
> Da der zweite Term einen geringeren Grad
> hat, fällt der in meiner Abschätzung weg. Die Konstanten
> ebenso und ich bekomme die Behauptung
> [mm]\mathcal O\left(\Delta^2n^{3,5}\cdot{}\left[\log(\Delta n)\right]\right)[/mm]
>
> Ist das so richtig Argumentiert?
>
Hmm, das würde ich gerne etwas genauer begründet haben
(ich hab's auch etwas schluderig aufgeschrieben auf meinem Schmierzettel )
> Noch einem Gruß meinerseits =)
Zurück!
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 20:12 Di 19.11.2013 | | Autor: | papilio |
Hallo,
danke, dass du dich meiner Frage nocheinmal angenommen hast.
> Muss es ganz hinten nicht [mm]1/2\log\left(2\pi n^{1\red +n}\right)[/mm]
> sein?
>
> Du addierst ja 2 Logarithmen, womit sich die Argumente
> multiplizieren ...
Ja, da hast du vollkommen recht. Habe mir da ein zweites Minus hingezaubert.
> Hmm, das würde ich gerne etwas genauer begründet haben
>
> (ich hab's auch etwas schluderig aufgeschrieben auf meinem
> Schmierzettel )
So, mit dem Plus sieht alles gleich viel besser aus. (Hoffe ich)
[mm] \bruch{1}{2}\log\left(2\pi n^{1 +n}\right)[/mm]
Schreibe ich als
[mm] \bruch{1}{2} \log(2\pi) + \bruch{1}{2} \log(n) + \bruch{1}{2} n \log(n))[/mm]
Dann habe ich insgesamt
[mm] \wurzel{2 \pi} \Delta^{2}n^{2,5} ( n \log(\bruch{2}{e} \Delta n) + \bruch{1}{2} \log(2\pi n) + n \bruch{1}{2} \log(n))[/mm]
Ist das soweit der richtige Weg?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Do 21.11.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 12:35 Mi 20.11.2013 | | Autor: | papilio |
Hallo,
> > Da der zweite Term einen geringeren Grad
> > hat, fällt der in meiner Abschätzung weg. Die
> Konstanten
> > ebenso und ich bekomme die Behauptung
> > [mm]\mathcal O\left(\Delta^2n^{3,5}\cdot{}\left[\log(\Delta n)\right]\right)[/mm]
>
> >
> > Ist das so richtig Argumentiert?
> >
>
> Hmm, das würde ich gerne etwas genauer begründet haben
>
> (ich hab's auch etwas schluderig aufgeschrieben auf meinem
> Schmierzettel )
Wie kann ich das genauer und formal richtig begründen?
Wähle ich mir einfach mein "c" durch Umformungen, oder gibt es noch einen schöneren Weg für das c?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:20 Fr 22.11.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
