| Reihen-Entwicklungen (Iterationen) eignen sich besonders gut zur Programmierung von PC und einfachen MikroProzessoren. | Man kann damit viele mathematische Aufgaben rasch und oft nur mit den 4 Grundrechnungs-Arten lösen. |
Algorithmen
|
Ausgewählte IT-Rezepte |
| Reihen | Allgemeine Überlegungen zur Programmierung |
| Genauigkeit | Abbruch beim Erreichen der maximalen Genauigkeit |
| Zahlenwert | Abbruch beim Erreichen der größten darstellbaren Zahlenwerte |
| Kalkulations-Programm | Programmierung mit LibreOffice, OpenOffice oder MS-Excel |
| Basic (VBA) | Programmierung von Reihen-Algorithmen mit LibreOffice- und Visual Basic |
| Javascript | Programmierung von Reihen-Algorithmen mit Javascript |
| Ausgewählte Algorithmen mit Reihenentwicklung: | |
| Bernoulli-Zahlen B[k] | |
| Das Pascal-Dreieck und die Berechnung der Binomial-Koeffizienten | |
| Umfang, Planetenbahn | |
| Reihen-Entwicklung von exp() mit Live-Beispielen | |
| Fakultät-(Faktorielle)-Funktion n! | |
| Fibonacci-Folge, Goldener Schnitt | |
| Berechnung und Grafik der Julia-Menge | |
| Reihen-Entwicklung mit Demo- und Live-Beispielen | |
| Berechnung von Legendre-Polynomen | |
| Reihen-Entwicklung von ln() und log() mit Live-Beispielen | |
| Berechnung und Grafik der Mandelbrot-Menge | |
| Gauß-Normalverteilung, ihr Integral und die Fehler-Funktion erf() | |
| Reihen-Entwicklung und Live-Beispiel | |
| Sinus, Arcustangens Cosinus, und andere trigonometrische Funktionen | |
| Links |
Ausgewählte
|
Reihen |
|
|
Es gibt mathematische Aufgaben, die sich 'exakt' nur schwer oder gar nicht
lösen lassen. Darunter fällt auch die Berechnung von Wurzeln, Logarithmen und Winkelfunktionen. Für einige dieser Aufgaben und Funktionen wurden Näherungs-Verfahren gefunden, die mit Reihen-Entwicklung arbeiten. |
Der Algorithmus zur Berechnung der Arcustangens-Funktion mit einer Reihe dient als
Beispiel für alle Kapitel dieser Seite:
Quelle:
Wikipedia
Man kann das 'Bildungsgesetz' leicht erkennen und auch ohne Mathematik die nächsten
Elemente der Reihe anschreiben: Im Nenner und im Exponenten tritt die Reihe der ungeraden
Zahlen auf (1, 3, 5, 7, 9, ...), außerdem wechselt bei jedem Element das Vorzeichen.
|
Berechnung• Man berechnet jedes einzelne Element der Reihe.• Die Rechnung wird allgemein formuliert und nur ein einziges Mal in Anweisungen ('Befehle') formuliert. • Die allgemeine Berechnung legt man in eine Schleife, wo sie beliebig oft wiederholt wird. ● Der hier gezeigte Algorithmus ist eine Vereinfachung ! - Praktisch verwendbare Ausführung auf der Seite → Winkelfunktionen. |
ErgebnisJe nach Algorithmus wird das Ergebnis auf unterschiedliche Weise gewonnen:• Summe: So wie im Beispiel der Arcustangens-Funktion (oben) werden die einzelnen Elemente der Reihe summiert. Die laufende Summe ist das Ergebnis. • Produkt: Die einzelnen Elemente der Reihe werden miteinander multipliziert. Das laufende Produkt ist das Ergebnis. • Element: Die Elemente selbst sind das Ergebnis. |
Abbruch• In sinnvollen Reihen-Algorithmen wird das Ergebnis umso genauer, je mehr Elemente man berechnet.• Das Ergebnis nähert sich immer mehr dem theoretischen Wert, erreicht diesen jedoch erst nach Berechnung unendlich vieler Elemente. • Zur praktischen Durchführung muss man daher die Berechnung an einem bestimmten Punkt abbrechen. Die Entscheidung zum Abbruch sollte sinnvoll überlegt und programmiert werden. • Während der Entwicklung setzt man als zusätzliches Abbruch-Kriterium einen Zähler ein, welcher den Algorithmus nach einer maximalen Anzahl von Schleifen-Durchgängen sicher abbricht. Wenn die Funktion unter allen Bedingungen zuverlässig arbeitet, kann man den Zähler später entfernen. |
Beispiel: Berechnung der Arcustangens-Funktion
für x=0.5 mit dem Taschenrechner oder mit einem
Kalkulations-Programm (OpenOffice-Calc, MS-Excel, ...) Die Elemente der Reihe werden immer kleiner:
arctan(x) = x - x^3/3 + x^5/5 - x^7/7 + x^9/9 - ...
arctan(0.5) = 0.5 - 0.04167 + 0.00625 - 1.116E-3 + 2.170E-4 - ... Die laufende Summe = Ergebnis nähert sich dem theoretischen Wert:
arctan(x) = 0.5; 0.4583; 0.4646; 0.4635; 0.4637; 0.4636; ...
arctan(x,theor.) = 0.463647609000806... Genauigkeit
Als Maß für die erreichte Genauigkeit kann man die Zahl der
übereinstimmenden Dezimalstellen bestimmen. Sie beträgt hier
ungefähr: 0; 1; 2; 3; 4; 4; 5; 6; Rechenzeit: Ist am Taschenrechner unmerkbar kurz. Bei genauer Messung findet man, dass sie für die ersten Elemente sehr kurz ist, dann jedoch progessiv (immer schneller) zunimmt. |
Genauigkeit |
|
Genauigkeit gegen GeschwindigkeitDie erreichte Genauigkeit wird normalerweise als Kriterium für den Abbruch einer Reihen-Berechnung verwendet.Wenn nicht anders vereinbart, dann wird bis zur maximalen Genauigkeit gerechnet, die mit der internen Speicher-Form von Gleitkomma-Zahlen erreichbar ist, das sind derzeit ca. 15-16 Dezimalstellen. Die Praxis vieler Programme (z.B. Kalkulations-Programme) zeigt, dass dieser Kompromiss brauchbar ist: Die meisten Rechnungen werden mit ausreichender Genauigkeit und Geschwindigkeit ausgeführt. Viele praktische Aufgaben kommen mit wesentlich geringerer Genauigkeit aus. Vor allem bei der Steuerung realer Geräte (Real Time Prozess-Steuerung) kann man die Rechenzeit mit eigenen Programmen sehr verkürzen, wenn man die Reihen schon früher abbricht. Man kann beliebig viele Elemente berechnen, um eine größere Genauigkeit zu erzielen. Das kostet nicht nur viel Rechenzeit: Man muss zum Rechnen und zum Speichern eine andere interne Speicherform verwenden. Solche Rechnungen sind nur selten notwendig und erfordern spezielle Programme. Die meisten modernen Programmiersprachen bieten eigene Module für solche Rechnungen. |
Double Precision nach IEEE-754Gängige PC, Betriebssysteme und Programme verwenden Zum Rechnen mit Gleitkomma-Zahlen den Variablen-Typ 'Double Precision' (Binary64) nach Standard → IEEE-754.Für diesen Typ werden 8 Byte = 64 Bit Speicher verwendet. Die Gleitkomma-Zahlen werden ähnlich wie im 'wissenschaftlichen' Zahlenformat getrennt: -987.6 = -9.876E+2
Die Zahl wird in Mantisse (hier -9.876) und
Exponent (hier +2) getrennt, allerdings binär codiert und
nicht dezimal wie hier gezeigt. Beide Teile können ein Vorzeichen tragen.Grenze
Für die Mantisse werden 52 Bit verwendet. Das bedeutet: Man kann theoretisch
gerade noch die Zahl 2^52 von 2^52-1
unterscheiden.In einem Kalkulations-Programm: Das Ergebnis der Subtraktion =1E15-1 ist von 1E15 verschieden, das Ergebnis der Addition =1E15+1 ist jedoch (ohne Anzeige eines Fehlers !) identisch mit 1E15 Programmierung
Für die Berechnung von Reihen bedeutet das: Wenn ein Element das Ergebnis um
weniger als Ergebnis*10E-15 ändert, dann wird die Rechnung
zwar ausgeführt, ergibt jedoch für dieses und alle weiteren Elemente stets
das gleiche Ergebnis. Man muss diesen Fall erkennen und die Reihe abbrechen, sonst
wird endlos und sinnlos weiter gerechnet.♦ Details zur Darstellung von Zahlen, Trennung in Mantisse und Exponent, Standard IEEE-754 |
AbbruchEs ist bei der Programmierung von Reihen wichtig, den richtigen Zeitpunkt für den Abbruch zu erkennen.Abbruch bei maximaler Genauigkeit:
Diese Variante ist am einfachsten und wird in der Praxis aller gängigen Programme
verwendet:
Wenn ergebnis=voriges_ergebnis dann Abbruch
Man führt die Schleife so lange aus, bis sich das Ergebnis nicht mehr ändert.
In diesem Fall erreicht man eine Genauigkeit (Auflösung) von
theoretisch 1/2^52 oder -log(2^-52)=15.65
Dezimalstellen. |
Abbruch bei definierter Genauigkeit
Diese Variante wird verwendet, wenn man in Zeit-kritischen Anwendungen besonders
schnell rechnen muss: Man definiert eine relative oder absolute Grenze der Genauigkeit,
z.B. rel_lim=0.01 für eine Genauigkeit von 1%In jeder Schleife wird geprüft:
differenz = abs(ergebnis-voriges_ergebnis)
abs_limit = ergebnis * rel_limit Wenn differenz<=abs_limit dann Abbruch |
Quad PrecisionDieser Standard (Binary128) wird von derzeit gängigen Programmen kaum verwendet. Die Speicher-Verwaltung für 128-Bit Gleitkomma-Zahlen wäre kein Problem. Die Rechenzeiten für die maximale Genauigkeit von 112 Bit @ 34 Dezimalstellen wären selbst für leistungsfähige PC unangenehm hoch, insbesondere weil die Rechenzeit / Element in gängigen Algorithmen rasch zunimmt.Mit der allgemeinen Verfügbarkeit von Quad Precision muss man bei der Programmierung die gleichen Probleme lösen wie mit den heute üblichen Double Prcision Zahlen, lediglich angewendet auf längere Mantissen. |
Sicherheits-Grenze
Mindestens bei unbekannten Algorithmen begrenzt man unabhängig von der Genauigkeit
die Anzahl der berechneten Elemente, z.B. auf einige 1000Wenn das funktioniert, dann kann man die Sicherheits-Grenze erhöhen. Manche Algorithmen (Beispiele: → Berechnung von Pi) erreichen sonst die maximale Genauigkeit erst nach einigen Stunden Rechenzeit... |
Absoluter Zahlenwert |
|
|
Unabhängig von der ↑ Genauigkeit
gibt es eine zweite Grenze für das Rechnen mit Gleitkomma-Zahlen: Für einen Double-Precision Exponenten werden 11 Bit verwendet, das entspricht den Werten -1024...+1023 bzw. Exponenten 2^-1024 bis 2^+1023 Damit sind große Gleitkomma-Zahlen im Bereich von ca. -1.8E+308 ... +1.8E+308 und kleine Zahlen im Bereich von ca. -5E-324 ... +5E-324 darstellbar. Wenn man bei einer Rechnung die absolute Grenze überschreitet, dann wird normalerweise ein Fehler angegeben. |
Diese Grenzen erscheinen weit entfernt von jenen Zahlenwerten, mit denen man
in Reihen normalerweise rechnet. Je nach Algorithmus kann man allerdings bei der Berechnung der einzelnen Elemente an die Grenzen gelangen. Insbesondere die → Fakultät-Funktion, die in vielen Algorithmen eingesetzt wird, wächst sehr rasch und erreicht die Grenze bereits bei 170! = 7.26E+306
|
ProgrammierungKontrolle: Bei unbekannten Algorithmen sollte man nicht nur das Ergebnis untersuchen, sondern insbesondere auch die Teil-Ergebnisse bei Berechnung der einzelnen Elemente. Dabei kann man die Annäherung an absolute Grenzen rechtzeitig erkennen. |
Fehler-Werte
Je nach System erhält man beim Überschreiten der Grenze allgemeine
Fehler oder spezielle Werte nach IEEE-754.Allgemeine Fehler kann man in jeder Programmiersprache erkennen und abfangen: In diesem Fall bricht man die Reihe ab und verwendet das letzte Fehler-freie Ergebnis. |
|
Sonderwerte nach IEEE-754
Dieser Standard definiert einige spezielle Werte, z.B.
'Positive Null' = 0x0000 0000 0000 0000
'Negative Null' = 0x8000 0000 0000 0000 'Positiv unendlich' = 0x7FF0 0000 0000 0000 'Negativ unendlich' = 0xFFF0 0000 0000 0000 In Low-Level Anwendungen werden evtl. keine Fehler ausgelöst sondern die Sonderwerte zurückgegeben. Man muss das Auftreten derartiger Werte erkennen und danach wie bei einem Fehler verfahren: Reihe abbrechen, das letzte brauchbare Ergebnis verwenden. |
Algorithmen umstellen
In manchen Fällen kann man einen Algorithmus umstellen und damit die
Überschreitung der absoluten Werte-Grenze verhindern oder zumindest verzögern.
Beispiel:
element = x*y*z/a*b*c
Wenn die Berechnung des Zählers x*y*z die Grenze
überschreitet, dann kann man abwechselnd multiplizieren und dividieren:
element = x/a
Durch geschickte Aufteilung und Umstellung gelingt es manchmal, die absoluten Werte
aller auftretenden Ergebnisse unter der Grenze zu halten.
element = element * y/b element = element * z/c |
Visual Basic (VBA) |
|
|
Die Programmiersprache →
Visual Basic (VBA) wurde als Beispiel gewählt, weil ein VBA-Interpreter in
jedem gängigen Kalkulations-Programm enthalten ist. Wer kein derartiges Programm hat, kann kostenfrei OpenOffice aus dem Internet laden. |
Hier wird allerdings nicht gezeigt, wie man VBA-Programme herstellt. ♦ Details zu VBA-Modulen |
Name und Argumente:• Man wählt für eigene Funktionen nur Namen, die sicher nicht anderswo verwendet werden.• Die Funktion braucht als obligatorisches Argument die Variable x • Mit dem optionalen Argument nmax kann man die Anzahl der berechneten Elemente begrenzen. • Lange Zeilen wie diese kann man mit _ Underline-Zeichen teilen. Deklaration der Variablen:Alle im Programm verwendeten Variablen werden mit der Dim-Anweisung und dem zu verwendenden Typ (Boolean, Integer, Double) deklariert.AnfangswerteVor der Berechnungs-Schleife werden alle nur 1mal notwendigen Arbeiten ausgeführt:Man weist allen Variablen einen Anfangswert zu (entspricht der ersten Zeile des Kalkulations-Programms). ● Summen erhalten fast immer den Anfangswert sum=0 ● Produkte erhalten fast immer den Anfangswert prod=1 (nur für Produkt-Algorithmen) ● Die Schleifen-Bedingung erhält den Wert doloop=True ● Der Schleifen-Zähler erhält den Wert n=0 • Alle Zeichen einer Zeile nach einem ' SingleQuote gelten als Kommentar und werden vom Programm ignoriert. |
Beispiel: Berechnung der Arcustangens-Funktion mit Visual Basic
(VBA)
Function my_arctan( _
x As Double, _
Dim doloop As BooleanOptional nmax As Integer = -1) _ As Double Dim n, i, vorz As Integer Dim element, sum, sumv As Double ' Anfangs-Werte
If nmax < 0 Then nmax = 1000doloop = True vorz = 1 sum = 0 n = 0 ' Iterations-Schleife
While doloop
sumv = sum
Wend
i = 2 * n + 1 element = vorz * x ^ i / i sum = sum + element n = n + 1 If (sum = sumv Or n>=nmax) Then doloop = False vorz = vorz * -1 ' Ergebnis
my_arctan = sum
|
Iterations-SchleifeVon allen Schleifen-Varianten ist die While-Schleife am besten zur Berechnung von Reihen geeignet. Alle Programm-Teile zwischen While...Wend werden so lange wiederholt, wie eine logische Bedingung erfüllt ist.● In allen hier vorgestellten Beispiel-Programmen wird eine Variable zur Steuerung der Schleife verwendet (hier doloop). Diese Variable wird vor Beginn der Schleife =True gesetzt. Innerhalb der Schleife werden 2 Bedingungen mit logisch ODER (Or) kombiniert: Die Schleife wird mit doloop=False abgebrochen, wenn mindestens eine davon erfüllt ist: • Der Schleifenzähler n darf den gewünschten maximalen Wert nmax nicht überschreiten. • Die erwünschte oder maximale Genauigkeit ist erreicht, d.h. das Ergebnis ändert sich nicht mehr oder um weniger als eine vorgegebene Grenze. |
• In jedem Schleifen-Durchgang wird 1 Element der Reihe berechnet: Berechnung eines Elements: • Die Variable sumv speichert das bisherige Ergebnis sum zum späteren Vergleich. • Die Zahl i wird aus dem Schleifen-Zähler berechnet. • Das Element der Reihe wird berechnet. • Zum bisherigen Ergebnis sum wird das Element addiert. • Der Schleifen-Zähler n wird erhöht. • Wenn sich das Ergebnis nicht geändert hat (sum=sumv), oder wenn der Zähler den maximalen Wert erreicht hat, dann wird die Abbruch-Variable doloop=False gesetzt. • Das Vorzeichen vorz wird für die nächste Schleife umgekehrt. • Nach dem Abbruch der Schleife wird das Ergebnis sum an das aufrufende Programm zurückgegeben. |
AnwendungMan kann das VBA-Programm als 'Benutzerdefinierte Funktion' in jedem gängigen Kalkulations-Programm verwenden.Zur Berechnung bis an die Grenze der Genauigkeit geben sie z.B. diese Formel in die Zelle F1 ein: F1=my_arctan(B1)
(Annahme: Das Argument x befindet sich in
Zelle B1 )
|
Zur Berechnung einer begrenzten Anzahl von Elementen geben sie z.B. diese Formel in Zelle F3 ein: F3=my_arctan($B$1;A3-1)
Diese Formel kann man nach unten ausfüllen. Das Ergebnis sollte gleich oder sehr
ähnlich jenem des Kalkulations-Programms in Spalte E sein.
|
Javascript |
|
| Die Programmiersprache → Javascript (JS) wurde als Beispiel gewählt, weil ein JS-Interpreter in jedem Browser-Programm enthalten ist. | Man kann ohne spezielles Entwicklungs-Werkzeug eine Webseite mit einem eigenen JS-Programm herstellen und testen. |
|
Die Funktion wurde fast genau analog zur
↑ Visual Basic-Version programmiert. Eine Version mit der Möglichkeit zum Live-Test finden sie auf der Seite zur → Reihen-Entwicklung von Winkelfunktionen. Eine Schwäche des Algorithmus ist die Verwendung der Potenz-Funktion (Math.pow). Auf der gleichen Seite wird gezeigt, wie man diese und andere Standard-Funktionen durch eigene ersetzt. Damit ist der gesamte Algorithmus auf die 4 Grundrechnungs-Arten (Addition, Subtraktion, Multiplikation, Division) zurückgeführt. |
Beispiel: Berechnung der Arcustangens-Funktion mit Javascript
function my_arctan(x,nmax) {
if(nmax<0) {nmax=10000;}
}var vorz=1; var sum=0; var sumv=0; var i=0; var n=0; var doloop = true; while(doloop) {
sumv = sum;
}i = 2 * n + 1; sum += vorz * Math.pow(x,i) / i; n++; if(sum==sumv || n>=nmax) {doloop=false;} vorz *= -1; return sum; |
Anwendung:Erstellen sie eine HTML oder XHTML-Webseite.Fügen sie ein <script>-Element in den <head> der Webseite ein, z.B.:
<script type="text/javascript">
// <![CDATA[
function my_arctan(x,nmax) {
... function test_arctan() {
x = prompt("Argument -1...x...1","0.2");
}
y = my_arctan(x,-1); alert("my_arctan("+x+") = "+y); // ]]>
</script>
|
Tragen sie in das <script>-Element die
Funktion my_arctan() (kompletter Text oben) und die
Funktion test_arctan() (links) ein: Sie arbeitet als
einfaches User-Interface zur Ein- und Ausgabe. Fügen sie an einer beliebigen Stelle im <body> der Webseite diesen HTML-Quelltext ein:
<a href="javascript:test_arctan()">
</a>
♣ Geben sie den Wert für x mit Komma-Punkt ein, nicht mit Beistrich (international und von allen Programmiersprachen wird nur der Komma-Punkt verwendet). ♣ Tipp: Der Live-Test oben funktioniert beim Anklicken ! |
|
|
|
● Formelsammlung:
Reihenentwicklungen,
Unendliche Reihen, ▲ OEIS: Online Encyclica of Integer Sequences: Lexikon von Zahlenfolgen |
Wikipedia: Kategorie 'Folgen und Reihen',
Reihenentwicklung,
Reihe
(Arithmetische,
Geometrische,
Binomische),
Folge,
(Arithmetische,
Geometrische,
Fibonacci),
Grenzwert,
Potenzreihe,
Taylor-Reihe,
Fourier-Reihe,
Polynome
(Trigonometrische),
Kettenbruch,
Approximation,
Approx-Algorithmen, ... |
|