Autor |
Funktion η gesucht mit O(f(η(n)))=O(g(η(n))) |
|
maellj
Junior  Dabei seit: 27.08.2019 Mitteilungen: 10
 |
Hallo zusammen,
ich schreibe gerade an meiner Masterarbeit im Bereich Algebra/Analytische Zahlentheorie. In meinem Forschungsteil geht es darum, dass ich eine Funktion $\eta(n)$ finden soll. Ich habe zwei Ausdrücke, die von $n$ bzw $\eta(n)$ abhängen und diese sollen größenordnungsmäßig gleich groß sein. Daher O(f(eta(n)))=O(g(eta(n))).
Ich habe schon mehrere Dinge ausprobiert, zB habe ich f/g für viele $n$ berechnet und plotten lassen, um zu sehen, ob das gegen eine Konstante konvergiert. Allerdings gibt es bisher (mit den Beispielfunktionen, die ich testete) keinen Kandidaten. Und ich kann mir natürlich tausend Funktionen ausdenken (ich weiß, dass es Logarithmen sind, mehr oder weniger geschachtelt und multipliziert etc), aber das ist nicht sehr zielführend.
Daher meine Frage: Gibt es ein Vorgehen für solch ein Problem? Ich habe auch schon Lösungen gefunden, die klappen würden, das Problem ist aber auch, dass $\lim_{n \to \infty} \eta (n) =0$ gelten muss.
Liebe Grüße
maellj
|
Notiz Profil
Quote
Link |
Nuramon
Senior  Dabei seit: 23.01.2008 Mitteilungen: 2519
 |     Beitrag No.1, eingetragen 2019-08-27
|
Hallo,
2019-08-27 10:19 - maellj im Themenstart schreibt:
Und ich kann mir natürlich tausend Funktionen ausdenken (ich weiß, dass es Logarithmen sind, mehr oder weniger geschachtelt und multipliziert etc), aber das ist nicht sehr zielführend.
aus diesem Grund wird man dir wohl kaum weiterhelfen können, ohne mehr über das konkrete Problem zu kennen.
|
Notiz Profil
Quote
Link |
maellj
Junior  Dabei seit: 27.08.2019 Mitteilungen: 10
 |     Beitrag No.2, vom Themenstarter, eingetragen 2019-08-27
|
Ich weiß nicht, wie viel ich sagen darf. Es ist immerhin etwas, das ich mir selbst erarbeiten soll und auch will. Daher meine vage Formulierung.
Es geht mir darum neuen Input zu bekommen. Ich möchte keine Lösung, nur einen Weg zu dieser.
Wenn nötig, werde ich auch das Problem posten, aber ich dachte, dass es vllt dazu einen Weg gibt, den ich nicht kenne.
|
Notiz Profil
Quote
Link |
Nuramon
Senior  Dabei seit: 23.01.2008 Mitteilungen: 2519
 |     Beitrag No.3, eingetragen 2019-08-27
|
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}\)
Kannst du irgendwelche Eigenschaften der Funktionen $f$ und $g$ angeben? Ich nehme mal an, deren Definitionsbereich soll $\IR\setminus\{0\}$ sein und dass $\eta:\IN \to \IR$ eine Folge sein soll.
Kannst du z.B. Aussagen über das Konvergenzverhalten von $f(x)$ oder $g(x)$ für $x\to 0$ treffen?
Geht vermutlich nicht in die Richtung, die für dich hilfreich ist, aber z.B. für $f(x)=\sin(\frac 1x)$ und $g(x)=\cos(x)$ könnte man $\eta(n)=\frac 1{\frac \pi 2 + 2\pi n}$ wählen.
\(\endgroup\)
|
Notiz Profil
Quote
Link |
maellj
Junior  Dabei seit: 27.08.2019 Mitteilungen: 10
 |     Beitrag No.4, vom Themenstarter, eingetragen 2019-08-27
|
Okay, das hätte ich noch schreiben können. $\eta$ ist eine Funktion, mit $\eta : \mathbb{N} \to \mathbb{R}$. Ich habe schon so Sachen wie $\frac{1}{logloglog(n)}$ probiert. Aber wie gesagt, durch Rumprobieren wurde ich nicht viel schlauer.
Ich nahm verschiedene $\eta$s und setzte sie ein und berechnete die Kurven. Das Problem, das ich habe, ist, dass in $\mathcal{O}$ viel verschwinden kann und ich eben nur genau rechnen kann.
|
Notiz Profil
Quote
Link |
Nuramon
Senior  Dabei seit: 23.01.2008 Mitteilungen: 2519
 |     Beitrag No.5, eingetragen 2019-08-27
|
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}\)
Wenn du nicht die konkreten Funktionen $f,g$ aus deiner Arbeit angeben willst, vielleicht kannst du andere angeben, für die das Problem etwas einfacher sein könnte. Ich fürchte ein ganz allgemeines Rezept zum Auffinden für ein mögliches $\eta$ wird es nicht geben.\(\endgroup\)
|
Notiz Profil
Quote
Link |
maellj
Junior  Dabei seit: 27.08.2019 Mitteilungen: 10
 |     Beitrag No.6, vom Themenstarter, eingetragen 2019-08-27
|
Das dürfte gehen.
Okay, nehmen wir für $f(\eta(n))=\exp(log(n)^{\eta(n)})$ und für $g(\eta(n))=\eta(n)$.
|
Notiz Profil
Quote
Link |
Nuramon
Senior  Dabei seit: 23.01.2008 Mitteilungen: 2519
 |     Beitrag No.7, eingetragen 2019-08-27
|
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}\)
Ich dachte $f$ und $g$ sollen gegeben sein und $\eta$ ist gesucht.
Dann sollte in der Definition von $f,g$ aber kein $\eta$ vorkommen. Meintest du $g(x)=x$? Welche Funktion soll $f$ sein?\(\endgroup\)
|
Notiz Profil
Quote
Link |
maellj
Junior  Dabei seit: 27.08.2019 Mitteilungen: 10
 |     Beitrag No.8, vom Themenstarter, eingetragen 2019-08-27
|
$f$ und $g$ hängen von $n$ und $\eta$ ab, ich kann auch nicht irgendwie auflösen, um eine Richtung zu kriegen.
|
Notiz Profil
Quote
Link |
Nuramon
Senior  Dabei seit: 23.01.2008 Mitteilungen: 2519
 |     Beitrag No.9, eingetragen 2019-08-27
|
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}\)
Also ist es so gemeint?
Gegeben sind zwei Funktionenscharen $f_\eta(n)=\exp(\log(n)^{\eta(n)})$ und $g_\eta(n) = \eta(n)$. Gesucht ist ein $\eta$ mit $\lim_{n \to \infty} \eta (n) =0$ und $\mathcal O(f_\eta) = \mathcal O(g_\eta)$.\(\endgroup\)
|
Notiz Profil
Quote
Link |
maellj
Junior  Dabei seit: 27.08.2019 Mitteilungen: 10
 |     Beitrag No.10, vom Themenstarter, eingetragen 2019-08-27
|
Könnte man so sagen. Ein solches $\eta$ soll ich finden
|
Notiz Profil
Quote
Link |
Nuramon
Senior  Dabei seit: 23.01.2008 Mitteilungen: 2519
 |     Beitrag No.11, eingetragen 2019-08-27
|
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}\)
2019-08-27 11:55 - Nuramon in Beitrag No. 9 schreibt:
Gegeben sind zwei Funktionenscharen $f_\eta(n)=\exp(\log(n)^{\eta(n)})$ und $g_\eta(n) = \eta(n)$. Gesucht ist ein $\eta$ mit $\lim_{n \to \infty} \eta (n) =0$ und $\mathcal O(f_\eta) = \mathcal O(g_\eta)$. Also in diesem Fall gibt es einfach kein geeignetes $\eta$:
Gäbe es nämlich eines, dann müsste insbesondere $\lim_{n \to \infty} f_\eta (n) =0$ sein, weil $\lim_{n \to \infty} g_\eta (n) =0$ ist.
Dann müsste aber $\lim_{n \to \infty} \log(n)^{\eta(n)} =-\infty $ sein, was im Widerspruch zu $\log(n)^{\eta(n)} >0$ steht.\(\endgroup\)
|
Notiz Profil
Quote
Link |
Kitaktus
Senior  Dabei seit: 11.09.2008 Mitteilungen: 6653
Herkunft: Niedersachsen
 |     Beitrag No.12, eingetragen 2019-08-27
|
Ich habe ziemlich lange gebraucht, um das Problem zu verstehen, weil Du im Themenstart die explizite Abhängigkeit von $n$ bei den Funktionen nicht aufgeführt hast.
Eine denkbare Variante:
Betrachte die Gleichung $f(n,x)=c(n)\cdot g(n,x)$. Das $c(n)$ darfst Du selbst wählen, die Funktion sollte aber beschränkt sein, nur nichtnegative Werte annehmen und 0 nicht als Häufungspunkt haben. Der einfachste Fall wäre $c(n)=1$. Jetzt löst Du die Gleichung in Abhängigkeit von $n$ nach $x$ auf.
Wenn Du es (durch die Wahl von $c$) schaffst, dass $x(n)$ gegen 0 geht, dann hast Du eine Funktion mit den gewünschten Eigenschaften gefunden.
|
Notiz Profil
Quote
Link |
Ehemaliges_Mitglied  |     Beitrag No.13, eingetragen 2019-08-28
|
Bilde die Funktion \(\eta^{-1}.\) SP
|
Notiz Profil
Quote
Link |
maellj
Junior  Dabei seit: 27.08.2019 Mitteilungen: 10
 |     Beitrag No.14, vom Themenstarter, eingetragen 2019-08-28
|
Danke schön, das werde ich mal testen. So einfach auflösen kann ich nicht, aber vllt komme ich so mit den Testfunktionen weiter.
Nur um das noch klarzustellen. Ich habe keinerlei $x$ in meinen Gleichungen. Es hängt alles entweder von $n$ und $\eta(n)$ ab oder nur von $\eta(n)$. Die Abhängigkeit von $n$ habe ich unterschlagen, da habt ihr Recht.
|
Notiz Profil
Quote
Link |
Kitaktus
Senior  Dabei seit: 11.09.2008 Mitteilungen: 6653
Herkunft: Niedersachsen
 |     Beitrag No.15, eingetragen 2019-08-28
|
2019-08-28 16:33 - maellj in Beitrag No. 14 schreibt:
Nur um das noch klarzustellen. Ich habe keinerlei $x$ in meinen Gleichungen. Es hängt alles entweder von $n$ und $\eta(n)$ ab oder nur von $\eta(n)$. Ja, das habe ich auch so verstanden. Das $x$ ist hier ein Platzhalter für die zu bestimmende Funktion $\eta(n)$.
|
Notiz Profil
Quote
Link |
maellj
Junior  Dabei seit: 27.08.2019 Mitteilungen: 10
 |     Beitrag No.16, vom Themenstarter, eingetragen 2019-09-02
|
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}\)
2019-08-27 12:32 - Nuramon in Beitrag No. 11 schreibt:
2019-08-27 11:55 - Nuramon in Beitrag No. 9 schreibt:
Gegeben sind zwei Funktionenscharen $f_\eta(n)=\exp(\log(n)^{\eta(n)})$ und $g_\eta(n) = \eta(n)$. Gesucht ist ein $\eta$ mit $\lim_{n \to \infty} \eta (n) =0$ und $\mathcal O(f_\eta) = \mathcal O(g_\eta)$. Also in diesem Fall gibt es einfach kein geeignetes $\eta$:
Gäbe es nämlich eines, dann müsste insbesondere $\lim_{n \to \infty} f_\eta (n) =0$ sein, weil $\lim_{n \to \infty} g_\eta (n) =0$ ist.
Dann müsste aber $\lim_{n \to \infty} \log(n)^{\eta(n)} =-\infty $ sein, was im Widerspruch zu $\log(n)^{\eta(n)} >0$ steht.
Entschuldige, da habe ich ein Minus vergessen (Ex-Physiker 😉 ). Es ist eher $f_\eta(n)=\exp(- \log(n)^{\eta(n)})$.
Die Methode mit $f(\eta(n),n)=c(n)\cdot g(\eta(n),n)$ habe ich für verschiedene $\eta$'s durchlaufen lassen. Leider gab es keine aussagekräftigen Ergebnisse.\(\endgroup\)
|
Notiz Profil
Quote
Link |
Kitaktus
Senior  Dabei seit: 11.09.2008 Mitteilungen: 6653
Herkunft: Niedersachsen
 |     Beitrag No.17, eingetragen 2019-09-02
|
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}\)
2019-09-02 14:59 - maellj in Beitrag No. 16 schreibt:
Die Methode mit $f(\eta(n),n)=c(n)\cdot g(\eta(n),n)$ habe ich für verschiedene $\eta$'s durchlaufen lassen. Leider gab es keine aussagekräftigen Ergebnisse. Hhm, in der Methode kann man $\eta(n)$ doch gar nicht variieren?!
Ich mache es mal an einem Beispiel vor:
Wir wählen $c(n)=1$ und ersetzen $\eta(n)$ durch $x$.
Ziel ist die Gleichheit:
$f(n,x)=\exp(-\log(n)^{x}) = c(n)\cdot\eta(n) = 1\cdot\eta(n)= x$.
Das führt zu $-\log(n)^x = \log(x)$. Zur besseren Übersicht (weniger negative Vorzeichen) substituieren wir $y:=1/x$. $-log(n)^{1/y} = -log(y)$, also $\log(n) = \log(y)^y$ bzw. $\log(\log(n))=y\cdot \log(\log(y))$.
$y$ wächst also ein wenig langsamer als $\log(\log(n))$.
Wir machen den Ansatz $y=\log(\log(n)) / r(n)$ und erhalten
$\log(\log(n))=\log(\log(n))/ r(n) \cdot \log(\log(\log(\log(n))/ r(n)))$ und vereinfacht:
$r(n)= \log(\log(\frac{\log(\log(n))}{r(n)}))$.
Ohne das komplett durchdacht zu haben, würde ich jetzt $r(n)= O(\log(\log(\log(\log(n)))))$ behaupten.
Insgesamt führt das dann zu einem $\eta(n)\approx \frac{\log(\log(\log(\log(n))))}{\log(\log(n))}$.
\(\endgroup\)
|
Notiz Profil
Quote
Link |
maellj
Junior  Dabei seit: 27.08.2019 Mitteilungen: 10
 |     Beitrag No.18, vom Themenstarter, eingetragen 2019-09-03
|
Wow, danke, das war hilfreich!
Ich habe nun ein Ergebnis, das ich mit meinem Prof abkläre 😁
|
Notiz Profil
Quote
Link |
maellj
Junior  Dabei seit: 27.08.2019 Mitteilungen: 10
 |     Beitrag No.19, vom Themenstarter, eingetragen 2019-09-04
|
Okay, ich habe das nun geklärt und habe ein "sehr gutes" Ergebnis erhalten. Vielen Dank euch allen!
|
Notiz Profil
Quote
Link |