0 Daumen
133 Aufrufe

Aufgabe:

Ich versuche ein Programm zu schreiben, dass mir die n-te Bernoulli-Zahl berechnet.

Ich habe bereits etwas dazu recherchiert und diesen Ansatz hier gefunden:

https://math.stackexchange.com/questions/2844290/what-is-the-simplest-way-to-get-bernoulli-numbers


$$B_{n}=1− \sum \limits_{k = 0}^{n-1} \begin{pmatrix} n\\k \end{pmatrix}\cdot \frac{B_{k}}{n - k + 1}$$


Problem/Ansatz:

Ich habe das ganze schon Programmatisch umgesetzt und es liefert auch die korrekten Ergebnisse, ABER.....


1. ABER: Das ganze funktioniert nur, wenn für $$B_{0} = 1$$ und für $$B_{1} = \frac{1}{2}$$ angenommen wird. Mir ist allerdings aufgefallen, dass das anscheinend nicht korrekt ist.

Laut https://mathworld.wolfram.com/BernoulliNumber.html ist $$B_{1} = - \frac{1}{2}$$. Damit errechnet mir mein Programm für $$B_{2} = \frac{7}{6}$$ statt $$- \frac{1}{6}$$. Ich habe das dann mal händisch nachgerechnet und bin auch auf  $$\frac{7}{6}$$ gekommen.

Ich frage mich natürlich nun, warum man auf korrekte Ergebnisse kommt, wenn man für $$B_{1}$$ das (wohl falsche) $$ \frac{1}{2} $$  annimmt, aber mit dem korrekten Wert von $$- \frac{1}{2}$$ dann falsche Folgewerte entstehen???


2. ABER (Bonus bzw. Randfrage in Richtung Programmierung):

Mein Programm errechnet die ersten ca. 400 Bernoulli-Zahlen sehr flott in wenigen Sekunden. Bei Zahlen über 1000 dauert es aber extrem lange.
Ohne jetzt im Detail auf das Programm eingehen zu wollen und damit mehr im mathematischen Rahmen zu bleiben: Ich denke der Grund dafür ist, dass ich zum Errechnen z.B. der 1000sten Bernoulli-Zahl ja offensichtlich aller vorhergehenden 999 Bernoulli Zahlen berechnen muss. Das ginge vielleicht auch noch ganz flott, aber jede dieser vorhergehenden 999 Zahlen ist ja wiederum eine individuelle Summe aller vorangegangenen Zahlen. Individuell soll in diesem Kontext bedeuten, dass sich die Funktion innerhalb der Summe:

$$\sum \limits_{k = 0}^{n-1} \begin{pmatrix} n\\k \end{pmatrix}\cdot \frac{B_{k}}{n - k + 1}$$ nicht nur durch die Laufvariable K beeinflusst wird, sondern auch der Endwert n in die Funktion mit einfließt. Wäre das nicht so, könnte man die Summe wohl einfach um ein weiteres Element (Summand?) erweitern und hätte daraus direkt die folgende Bernoulli Zahl errechnet.


Da das aber wohl nicht geht, muss für jedes $$B_{n}$$ erst mal eine Liste aus n-1 Elementen individuell berechnet und summiert werden In etwa entspricht das wohl einer Komplexität von $$\frac{n^{2}}{2} $$Rechenoperationen, was ja leider nicht gerade effizient ist. Aus den eben genannten Gründen, sehe ich aber keine Möglichkeit, die Bernoulli Zahlen effizienter zu berechnen.

von

1 Antwort

+1 Daumen
 
Beste Antwort

Hallo :-)

es kommt drauf an, welche Rekursionsformel du für die Bernoulli-Zahlen nimmst:

https://en.wikipedia.org/wiki/Bernoulli_number#Recursive_definition

Deine Formel ist mit der Version \(B_n^+\) gleichzusetzen, während die von wolframalpha die andere, also \(B_n^-\) verwendet. Die Besonderheit liegt hier eben bei der zweiten Bernoulli-Zahl, wo nämlich \(B_1=\pm \frac{1}{2}\) gilt und sich das Vorzeichen entsprechend ergibt. Also \(B_1^+=+\frac{1}{2}\) und \(B_1^-=-\frac{1}{2}\).

Ferner bekommst du für die dritte Zahl den Wert \(B_2=\frac{1}{6}=B_2^+=B_2^-\). Damit rechnet also dein Programm nicht korrekt.

Zum Rechenaufwand. Willst du die \(n\)-te Bernoullizahl haben, so musst du erstmal die \(n\) vorherigen \(B_0,...,B_{n-1}\) berechnet haben. Du hast also grob zwei Schleifen, die abgelaufen werden müssen:

for i <- 1 to n do

______for k <- 0 to i-1 do

Aufpassen: Die Indizes sind hier Indexpositionen. \(i=1\) bedeutet also, dass die erste Indexposition \(0\) ignoriert wird, da ja \(B_0=1\) schon bekannt ist. Die zweite Schleife beinhaltet die Summation der einzelnen \(B_k\), ohne jetzt auf die Codierung einzugehen. Das macht also

\(\sum\limits_{i=1}^n\left (\sum\limits_{k=1}^{i-1} 1 \right)=\sum\limits_{i=1}^n (i-1)=\frac{n(n+1)}{2}-n=\frac{n^2}{2}-\frac{n}{2}\in \Theta(n^2)\) Durchläufe.

Und wie du erkannt hast, wird das nicht besser von der Laufzeit. Du kannst dein Programm aber etwas beschleunigen, indem du für alle \(i \geq 3\) mit \(i\) ungerade \(B_i=0\) setzt.

Außerdem musst du noch bedenken, dass für jeden Summanden der Binomialkoeffizient besonders ins Gewicht fällt, vorallem bei sehr großen Eingabegrößen, sodass dein Programm eine höhere Laufzeit als nur quadratische hat.

von

Erst mal Danke für die schnelle, ausführliche und verständliche Antwort!

An Hand von deinen Ausführungen hat sich für mich aber jetzt noch eine Frage ergeben. So wie du die Formel oben ausgeschrieben hast, ist mir beim nochmaligen Stöbern in Wikipedia gleich die Formel hier ins Auge gesprungen:


$$B_m^{+} = \sum \limits_{k=0}^{m}\sum \limits_{v=0}^{k}(-1)^{v}\begin{pmatrix} k\\v \end{pmatrix}\frac{(v+1)^{m}}{k+1}$$

https://en.wikipedia.org/wiki/Bernoulli_number#Explicit_definition


Statt es rekursiv zu programmieren, habe ich es also einfach mal genau so umgesetzt, wie die explizite Formel es vorgesehen hat. Im Kern entspricht das auch genau deiner Erläuterung mit der Doppelschleife. Ich habe das auch darum gemacht, weil das System, in dem ich die Funktion verwenden will, leider eine maximale Rekursionstiefe hat, die bei großen Bernoulli-Zahlen leider überschritten wird.


Nun rechnet mein Programm mit der expliziten Formel aber leider falsche Zahlen aus.


$$B_0^{+} = \frac{-1}{1}$$

$$B_1^{+} = \frac{-5}{2}$$

$$B_2^{+} = \frac{-19}{2}$$


Ich habe das mal händisch nachgeprüft und komme auf die gleichen Ergebnisse und wundere mich darum, wo der Fehler liegt...


$$B_0^{+} = \sum \limits_{k=0}^{0}\sum \limits_{v=0}^{k}(-1)^{v}\begin{pmatrix} k\\v \end{pmatrix}\frac{(v+1)^{m}}{k+1}\\ = (-1)^{0}\begin{pmatrix} 0\\0 \end{pmatrix}\frac{(0+1)^{0}}{0+1}\\ = (-1)^{0} \cdot \frac{0!}{0!\cdot(0 - 0)!}\cdot\frac{(0+1)^{0}}{0+1}\\ = -1 \cdot \frac{1}{1} \cdot \frac{1}{1}\\ = -1 \cdot 1 \cdot 1\\ B_0^{+} = -1$$


Und für


$$B_1^{+} = \sum \limits_{k=0}^{1}\sum \limits_{v=0}^{k}(-1)^{v}\begin{pmatrix} k\\v \end{pmatrix}\frac{(v+1)^{m}}{k+1}\\ \text{ Ist letztlich die Summe aus drei Elementen:}\\ 0.0 \rightarrow(-1)^{0} \cdot \begin{pmatrix} 0\\0 \end{pmatrix} \cdot \frac{(0+1)^{0}}{0+1} = -1 \cdot \frac{1}{1} \cdot \frac{1}{1} = -1\\ 1.0 \rightarrow(-1)^{0} \cdot \begin{pmatrix} 1\\0 \end{pmatrix} \cdot \frac{(0+1)^{1}}{1+1} = -1 \cdot \frac{1}{1} \cdot \frac{1}{2} = -\frac{1}{2}\\ 1.1 \rightarrow(-1)^{1} \cdot \begin{pmatrix} 1\\1 \end{pmatrix} \cdot \frac{(1+1)^{1}}{1+1} = -1 \cdot \frac{1}{1} \cdot \frac{2}{2} = -1\\ \text{ Aus den zwei "inneren" Schleifen ergeben sich:}\\ \sum -1 = -1\\ \sum -\frac{1}{2}, -1 = -\frac{3}{2}\\ \text{ Beide Summen werden in der "äußeren" Schleife wiederum summiert:}\\ \sum -1, -\frac{3}{2} =  -\frac{5}{2}\\ B_1^{+} = -\frac{5}{2}$$

Genau das gibt mein Programm auch für die ersten beiden Zahlen aus und wenn ich mich nicht zweimal gleichmäßig händisch verrechnet habe, scheint das ja auch zu stimmen.


Aber wie gesagt sind das natürlich nicht die ersten beiden Bernoulli Zahlen und ich frage mich was da falsch läuft.


Im Gegensatz zu den rekursiven Definitionen, bei denen $$B_0^{+}$$ und $$B_1^{+}$$ ja vordefiniert sind, müsste sich über die explizite Formel ja jede Bernoulli Zahl entsprechend errechnen lassen.

Ich weiß ja nicht, wie du dein Programm geschrieben hast, aber in deinem händischem Rechenweg passiert dir folgender grober Fehler: Es gilt stets \(x^0=1\) für jede Zahl \(x\in \mathbb{K}\), also auch \((-1)^0=1\) und nicht \((-1)^0=-1\). Ansonsten sehen auf dem ersten Blick alle Zwischensummationen richtig aus.

Danke nochmal für deinen Input!

Du hast natürlich absolut Recht. Ich war mir bei $$x^0$$ nicht mehr so sicher und hatte es schnell bei wolframalpha eingegeben. Seltsamerweise sagt wolframalpha -1^0 = -1. Auch Python sagt -1**0 = -1, weshalb mein Programm das zufälliger Weise genau so falsch gerechnet hat, wie ich.

Ich nehme aber an, das liegt an der Order of Execution, dass also erst die Potenz berechnet wird und dann das Ergebnis negativiert wird.

(-1)^0 bzw (-1)**0 funktionieren in Wolfram Alpha, respektive Python korrekt.


Entsprechend liefert auch mein Programm jetzt die korrekten Ergebnisse.

Also abschließend nochmal Danke!

Freut mich! :-)

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community