Der Spigot-Ansatz ist eine elegante Vorgehensweise, spezielle numerische Werte zuverlässig, effizient und mit beliebiger Genauigkeit zu berechnen. Die Stärke des Ansatzes ist seine Effizienz, seine totale Korrektheit und seine mathematisch exakt begründete Sicherstellung einer gewünschten absoluten Genauigkeit. Seine Schwäche ist möglicherweise die eingeschränkte Anwendbarkeit. Es gibt in der Literatur Spigot-Berechnung für e und pi. Wurzelberechnung und Logarithmenberechnung gehören zu den Hauptergebnissen der Dissertation. In Kombination mit den Methoden der Reihentransformation von Zeilberger und Wilf bzw. von Gosper ist der Einsatz zur Berechnung von hypergeometrischen Reihen sehr Erfolg versprechend. Eine interessante offene Frage ist die Berechnung der Feigenbaumkonstanten mit dem Ansatz. 'Spigot' bedeutet 'sukzessive Extraktion von Wertanteilen': die Wertanteile werden extrahiert, als ob sie durch einen Hahn (englisch: spigot) gepumpt werden. Es ist dabei besonders interessant, dass in bestimmten Fällen ein Wert-Anteil mit einer Ziffer der Kodierung des Ergebnisses versehen werden kann. Der Spigot-Ansatz steht damit im Gegensatz zu den konventionellen Iterationsverfahren: in einem Schritt des Spigot-Ansatzes wird jeweils ein Wert-Anteil 'extrahiert' und das gesamte Ergebnis ist die Summe der Wert-Anteile; während ein Schritt in einem Iterationsverfahren die Berechnung eines besseren gesamten Ergebnisses aus dem des vorigen Schritt beinhaltet. Das Grundschema der Berechnung mit dem Spigot-Ansatz sieht folgendermaßen aus: zuerst wird für den zu berechnenden numerischen Wert eine gut konvergierende Reihe mit rationalen Gliedern durch symbolisch-algebraische Methoden hergeleitet; dann wird für eine gewünschte Genauigkeit eine Teilsumme ausgewählt; anschließend werden aus der Teilsumme Wert-Anteile iterativ extrahiert. Die Extraktion von Wert-Anteilen aus der Teilsumme geschieht mit dem Spigot-Algorithmus, der auf Sale zurück geht, nur Integer-Arithmetik benötigt und sich als eine verallgemeinerte Form der Basis-Konvertierung dadurch auffassen lässt, dass die Teilsumme als die Kodierung des Wertes in einer inhomogenen Basis interpretiert wird. Die Spigot-Idee findet auch in der Überführung einer Reihe in eine besser konvergierende Reihe auf der Art und Weise Anwendung, dass Wert-Anteile aus der Reihe extrahiert werden, um die originale Reihe werttreu zur Reihe der Wert-Anteile zu transformieren. Dies geschieht mit den Methoden der Reihentransformation von Gosper bzw. Wilf. Die Dissertation umfasst im Wesentlichen die Formalisierung des Spigot-Algorithmus und der Gosperschen Reihentransformation, eine systematische Darstellung der Ansätze, Methoden und Techniken der Reihenentwiclung und Reihentransformation (die Herleitung von Reihen mit Hilfe charakteristischer Funktionalgleichungen; Methoden der Reihentransformation von Euler, Kummer, Markoff, Gosper, Zeilberger und Wilf) sowie die Methoden zur Berechnung von Wurzeln und Logarithmen mit dem Spigot-Ansatz. Es ist interessant zu sehen, wie sich die Grundideen des Spigot-Algorithmus, der Wurzelberechnung und der Logarithmenberechnung jeweils im Wesentlichen durch eine Gleichung ausdrücken lassen. Es ist auch interessant zu sehen, wie sich verschiedene Methoden der Reihentransformation auf einige einfache Grundideen zurückführen lassen. Beispiele für den Beweis von totalen Korrektheit (bei iterativer Berechnung von Wurzeln) könnte auch von starkem Interesse sein. Um die Zuverlässigkeit anderer Methoden zur Berechnung von natürlichen Logarithmen zu überprüfen, scheint der Vergleich der Ergebnisse mit den des Spigot-Ansatzes die beste Methode zu sein. Anders als bei Wurzelberechnung kann hierbei zur Überprüfung die inverse Berechnung nicht angewandt werden. / spigot, total correctness, acceleration of series, computation of roots, computation of logarithms Reliable numerical computations with spigot approach Spigot approach is an elegant way to compute special numerical values reliably, efficiently and with arbitrary accuracy. The advantage of this way are its efficiency and its total correctness including the bounding of the absolute error. The disadvantage is perhaps its restricted applicableness. There are spigot computation for e an pi. The computation of roots and logarithms belongs to the main results of this thesis. In combination with the methods for acceleration of series by Gosper as well as by Zeilberger and Wilf is the use for numerical summation of hypergeometric series very promising. An interesting open question is the computation of the Feigenbaum constant by this way. ‘Spigot’ means ‘successive extraction of portions of value’: the portions of value are ‘extracted’ as if they were pumped through a spigot. It is very interesting in certain case, where these portions can be interpreted as the digits of the result. With respect to that the spigot approach is the opposition to the iterative approach, where in each step the new better result is computed from the result of the previous step. The schema of spigot approach is characterised as follows: first a series for the value to be computed is derived, then a partial sum of the series is chosen with respect to an desired accuracy, afterwards the portions of value are extracted from the sum. The extraction of potions of value is carried by the spigot algorithm which is due to Sale an requires only integer arithmetic. The spigot algorithm can be understood as a generalisation of radix-conversion if the sum is interpreted as an encoding of the result in a mixed-radix (inhomogeneous) system. The spigot idea is also applied in transferring a series into a better convergent series: portions of value are extracted successively from the original series in order to form the series of extracted potions which should have the same value as the original series. This transfer is carried with the methods for acceleration of series by Gosper and Wilf. The thesis incorporates essentially the formalisation of the spigot algorithm and the method of Gosper for acceleration of series, a systematisation of methods and techniques for derivation and acceleration of series (derivation of series for functions by using their characteristic functional equations; methods for acceleration of series by Euler, Kummer, Markov, Gosper Zeilberger and Wilf) as well as the methods for computation of roots and logarithms by spigot approach. It is interesting to see how to express the basic ideas for spigot algorithm, computation of roots and computation of logarithm respectively in some equations. It is also interesting to see how to build various methods for acceleration of series from some simple basic ideas. Examples for proof of total correctness (for iterative computation of roots) can be of value to read. Comparing with the results produced by spigot approach is possibly the best way for verifying the reliability of other methods for computation of natural logarithms, because (as opposed to root computing) the verification by inverse computation is inapplicable.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:24875 |
| Date | 20 September 2005 |
| Creators | Do, Dang-Khoa |
| Contributors | Stoschek, Erwin P., Kerner, Immo O., Hantzschmann, Karl |
| Publisher | Technische Universität Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | German |
| Detected Language | German |
| Type | doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0022 seconds