In the adaptive finite element method, the solution of a p.d.e. is approximated from finer and finer meshes, which are controlled by error estimators. So, starting from a given coarse mesh, some elements are subdivided a couple of times. We investigate the question of avoiding instabilities which limit this process from the fact that nodal coordinates of one element coincide in more and more leading digits. In a previous paper the stable calculation of the Jacobian matrices of the element mapping was given for straight line triangles, quadrilaterals and hexahedrons. Here, we generalize this ideas to linear and quadratic triangles on curved boundaries.

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.

An der TU Chemnitz haben sich seit über zwei Jahrzehnten die Gebiete der rechnergestützten Wissenschaften (Computational Science) sowie des parallelen und verteilten Hochleistungsrechnens mit zunehmender Verzahnung entwickelt. Die Koordinierung und Bündelung entsprechender Forschungsarbeiten in der Profillinie 6 “Modellierung, Simulation, Hochleistungsrechnen” wird es ermöglichen, im internationalen Wettbewerb des Wissens mitzuhalten.

No description available.

No description available.

Matrix Lyapunov and Riccati equations are an important tool in mathematical systems theory. They are the key ingredients in balancing based model order reduction techniques and linear quadratic regulator problems. For small and moderately sized problems these equations are solved by techniques with at least cubic complexity which prohibits their usage in large scale applications. Around the year 2000 solvers for large scale problems have been introduced. The basic idea there is to compute a low rank decomposition of the quadratic and dense solution matrix and in turn reduce the memory and computational complexity of the algorithms. In this thesis efficiency enhancing techniques for the low rank alternating directions implicit iteration based solution of large scale matrix equations are introduced and discussed. Also the applicability in the context of real world systems is demonstrated. The thesis is structured in seven central chapters. After the introduction chapter 2 introduces the basic concepts and notations needed as fundamental tools for the remainder of the thesis. The next chapter then introduces a collection of test examples spanning from easily scalable academic test systems to badly conditioned technical applications which are used to demonstrate the features of the solvers. Chapter four and five describe the basic solvers and the modifications taken to make them applicable to an even larger class of problems. The following two chapters treat the application of the solvers in the context of model order reduction and linear quadratic optimal control of PDEs. The final chapter then presents the extensive numerical testing undertaken with the solvers proposed in the prior chapters. Some conclusions and an appendix complete the thesis.

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.

We study the approximation of functions defined on different domains by trigonometric and transformed trigonometric functions. We investigate which of the many results known from the approximation theory on the d-dimensional torus can be transfered to other domains. We define invertible parameterized transformations and prove conditions under which functions from a weighted Sobolev space can be transformed into functions defined on the torus, that still have a certain degree of Sobolev smoothness and for which we know worst-case upper error bounds. By reverting the initial change of variables we transfer the fast algorithms based on rank-1 lattices used to approximate functions on the torus efficiently over to other domains and obtain adapted FFT algorithms.:1 Introduction 2 Preliminaries and notations 3 Fourier approximation on the torus 4 Torus-to-R d transformation mappings 5 Torus-to-cube transformation mappings 6 Conclusion Alphabetical Index / Wir betrachten die Approximation von Funktionen, die auf verschiedenen Gebieten definiert sind, mittels trigonometrischer und transformierter trigonometrischer Funktionen. Wir untersuchen, welche bisherigen Ergebnisse für die Approximation von Funktionen, die auf einem d-dimensionalen Torus definiert wurden, auf andere Definitionsgebiete übertragen werden können. Dazu definieren wir parametrisierte Transformationsabbildungen und beweisen Bedingungen, bei denen Funktionen aus einem gewichteten Sobolevraum in Funktionen, die auf dem Torus definiert sind, transformiert werden können, die dabei einen gewissen Grad an Sobolevglattheit behalten und für die obere Schranken der Approximationsfehler bewiesen wurden. Durch Umkehrung der ursprünglichen Koordinatentransformation übertragen wir die schnellen Algorithmen, die Rang-1 Gitter Methoden verwenden um Funktionen auf dem Torus effizient zu approximieren, auf andere Definitionsgebiete und erhalten adaptierte FFT Algorithmen.:1 Introduction 2 Preliminaries and notations 3 Fourier approximation on the torus 4 Torus-to-R d transformation mappings 5 Torus-to-cube transformation mappings 6 Conclusion Alphabetical Index

Data gathering is a constant in human history with ever increasing amounts in quantity and dimensionality. To get a feel for the data, make it interpretable, or find underlying laws it is necessary to fit a function to the finite and possibly noisy data. In this thesis we focus on a method achieving this, namely least squares approximation. Its discovery dates back to around 1800 and it has since then proven to be an indispensable tool which is efficient and has the capability to achieve optimal error when used right. Crucial for the least squares method are the ansatz functions and the sampling points. To discuss them, we gather tools from probability theory, frame subsampling, and $L_2$-Marcinkiewicz-Zygmund inequalities. With that we give results in the worst-case or minmax setting, when a set of points is sought for approximating a class of functions, which we model as a generic reproducing kernel Hilbert space. Further, we give error bounds in the statistical learning setting for approximating individual functions from possibly noisy samples. Here, we include the covariate-shift setting as a subfield of transfer learning. In a natural way a parameter choice question arises for balancing over- and underfitting effect. We tackle this by using the cross-validation score, for which we show a fast way of computing as well as prove the goodness thereof.:1 Introduction 2 Least squares approximation 3 Reproducing kernel Hilbert spaces (RKHS) 4 Concentration inequalities 5 Subsampling of finite frames 6 L2 -Marcinkiewicz-Zygmund (MZ) inequalities 7 Least squares in the worst-case setting 8 Least squares in statistical learning 9 Cross-validation 10 Outlook

It is well-known that the solution of a so-called singularly perturbed differential equation exhibits layers. These are small regions in the domain where the solution changes drastically. These layers deteriorate the convergence of standard numerical algorithms, such as the finite element method on a uniform mesh. In the past many approaches were developed to overcome this difficulty. In this context it was very helpful to understand the structure of the solution - especially to know where the layers can occur. Therefore, we have a lot of analysis in the literature concerning the properties of solutions of such problems. Nevertheless, this field is far from being understood conclusively. More recently, there is an increasing interest in the numerics of optimal control problems subject to a singularly perturbed convection-diffusion equation and box constraints for the control. However, it is not much known about the solutions of such optimal control problems. The proposed solution methods are based on the experience one has from scalar singularly perturbed differential equations, but so far, the analysis presented does not use the structure of the solution and in fact, the provided bounds are rather meaningless for solutions which exhibit boundary layers, since these bounds scale like epsilon^(-1.5) as epsilon converges to 0. In this thesis we strive to prove bounds for the solution and its derivatives of the optimal control problem. These bounds show that there is an additional layer that is weaker than the layers one expects knowing the results for scalar differential equation problems, but that weak layer deteriorates the convergence of the proposed methods. In Chapter 1 and 2 we discuss the optimal control problem for the one-dimensional case. We consider the case without control constraints and the case with control constraints separately. For the case without control constraints we develop a method to prove bounds for arbitrary derivatives of the solution, given the data is smooth enough. For the latter case we prove bounds for the derivatives up to the second order. Subsequently, we discuss several discretization methods. In this context we use special Shishkin meshes. These meshes are piecewise equidistant, but have a very fine subdivision in the region of the layers. Additionally, we consider different ways of discretizing the control constraints. The first one enforces the compliance of the constraints everywhere and the other one enforces it only in the mesh nodes. For each proposed algorithm we prove convergence estimates that are independent of the parameter epsilon. Hence, they are meaningful even for small values of epsilon. As a next step we turn to the two-dimensional case. To be able to adapt the proofs of Chapter 2 to this case we require bounds for the solution of the scalar differential equation problem for a right hand side f only in W^(1,infty). Although, a lot of results for this problem can be found in the literature but we can not apply any of them, because they require a smooth right hand side f in C^(2,alpha) for some alpha in (0,1). Therefore, we dedicate Chapter 3 to the analysis of the scalar differential equations problem only using a right hand side f that is not very smooth. In Chapter 4 we strive to prove bounds for the solution of the optimal control problem in the two dimensional case. The analysis for this problem is not complete. Especially, the characteristic layers induce subproblems that are not understood completely. Hence, we can not prove sharp bounds for all terms in the solution decomposition we construct. Nevertheless, we propose a solution method. Numerical results indicate an epsilon-independent convergence for the considered examples - although we are not able to prove this.