Numerik-Oberseminar WS 2002/2003

Eigenvalue-Day (Workshop zu nichtlinearen Eigenwertproblemen),
Montag, 20. Januar 2003, ab 13:00 Uhr in MA 464

Interessenten sind herzlich eingeladen!

Rückblick:

• Numerik-Oberseminar SS 2002
• Numerik-Oberseminar WS 2001/02
• Numerik-Oberseminar SS 2001

• Diplomanden- und Doktorandenseminar des Fachgebiets Numerische Mathematik

Abstracts zu den Vorträgen:

Karsten Eppler, TU Berlin
First and second order shape optimization algorithms using wavelet-based BEM
Di 15.10.2002, 16:15 Uhr in MA 750

Abstract:
First and second order shape optimization algorithms using wavelet-based BEM
(K. E. and H. Harbrecht, Tu Chemnitz)

The talk deals with the numerical solution of 2D-elliptic shape optimization problems. Additional equality and inequality constraints are assumed to be given in terms of shape-differentiable domain or boundary integrals. First, the realibility of the Gradient and Quasi-Newton algorithm for a boundary variational approach is discussed. To compute the objective and the shape gradient, a wavelet-Galerkin BEM is used for solving the state equation.
To proceed in a similar way for second order optimization methods, a complete boundary integral representation of the shape Hessian is required.The related second spatial derivatives of the solution and other quantities can be obtained by BIE-methods as well. Numerical results are presented for the problem of minimizing the volume of an elastic cylindrical bar under given inequality constraints on the bending and torsional rigidity. Furthermore, related ``dual" problems (maximize torsional rigidity subject to constraints on the volume and the bending stiffness, maximize bending rigidity ..) can be treated as well.

Abstract:
The subject of geometric numerical integration deals with numerical integrators that preserve geometric properties of the flow of a differential equation, and it explains how structure preservation leads to an improved long-time behaviour. This talk illustrates concepts and results of geometric numerical integration on the important example of the Störmer/Verlet method, the integrator of choice especially in molecular dynamics.
After an introduction to the Newton-Störmer-Verlet-leapfrog method and its various interpretations, there follows a discussion of geometric properties: reversibility, symplecticity, volume preservation, and the conservation of first integrals. The theoretical foundation relies on a backward error analysis, which translates the geometric properties of the method into the structure of a modified differential equation, whose flow is nearly identical to the numerical method. Combined with results from perturbation theory, this explains the excellent long-time behaviour of the method: long-time energy conservation, linear error growth and preservation of invariant tori in near-integrable systems, and a discrete virial theorem.

Lit.: E. Hairer, Ch. Lubich, G. Wanner, Geometric Numerical Integration. Structure-Preserving Algorithms for Ordinary Differential Equations. Springer, Berlin, 2003.

Abstract:
Die Large Eddy Simulation (LES) ist gegenwärtig eine der vielversprechensten Herangehensweisen zur Simulation turbulenter Strömungen. Bei der LES versucht man, nur die großen Strukturen einer turbulenten Strömung möglichst genau zu berechnen. Die großen Stömungsstrukturen werden oft durch Faltung mit einer geeigneten Filterfunktion definiert.
Die raumgemittelten Navier-Stokes-Gleichungen sind die Grundgleichungen der LES. Zunächst werden analytische Untersuchungen zum sogenannten Vertauschungsfehler, der bei der Herleitung der raumgemittelten Navier-Stokes-Gleichungen auf einem beschränkten Gebiet entsteht, vorgestellt. Um Gleichungen für die großen Strömungsstrukturen aus den raumgemittelten Navier-Stokes-Gleichungen zu erhalten, ist eine Modellierung des sogenannten Reynolds-Spannungstensors nötig. Es werden Modelle präsentiert, die auf einer Approximation der Filterfunktion im Fourier-Raum beruhen. Die Diskretisierung der so erhaltenen Modelle mittels impliziter Zeitverfahren und Finiter Elemente im Raum wird beschrieben. Für das Smagorinsky-Modell wird eine Finite Element-Fehlerabschätzung angegeben. Abschließend werden numerische Tests präsentiert. Bei diesen Tests wurden die besten Ergebnisse mit dem rationalen LES-Modell von GalDi und Layton (2000) erzielt.

Abstract:
A classical theorem by Zubov asserts that for an asymptotically stable fixed point of an ordinary differential equation the domain of attraction can be characterized by a maximal Lyapunov function. This Lyapunov function can be obtained as the solution of a certain first order PDE.
In this talk it will be discussed how this result can be extended to perturbed and controlled systems. In the perturbed case we obtain a PDE the solution of which is a maximal robust Lyapunov function. Conversely, in the controlled case a control Lyapunov function defined on the domain of asymptotic nullcontrollability can be constructed via this method.
The approach is based on a reformulation of the problems as optimal control problems and on the consideration of the associated value functions. These are solutions in the viscosity sense of equations which can be obtained from Zubov's original equation by straightforward generalization. From the numerical point of view, however, some regularization of the generalized equation is necessary. A few examples will be discussed.

Abstract:
Stopping criteria for (linear algebraic) iterative solvers were thoroughly studied by many authors. During the last decade many well justified theoretical conclusions were published on this issue (with most of them based on much older work). It seems therefore rather surprising that these conclusions are rarely used in practical scientific computations, and the leading position among the measures of convergence is still undeservely held by the relative residual norm.
Our contribution will recall in an elementary way some basic points concerning stopping criteria for iterative methods. We will then discusse several sources of possible confusion which can be found in the literature. We will finally present two recent results about estimating the energy norm (A-norm) of the error in the conjugate gradient method and about the normwise backward error in GMRES.

Abstract:
The main idea of using iterative methods consists in constructing a sequence of approximate solutions and in stopping the process when the desired accuracy is reached. For decision when to stop the process, it is very important to understand the theoretical iterative method but also its behaviour in finite precision arithmetic.

In their paper published in 1952, Hestenes and Stiefel [1] considered the conjugate gradient (CG) method as an iterative method which terminates in at most n steps if no rounding errors are encountered. Though they did not give any particular stopping procedure, they presented several relations as possible justifications for such procedures. They emphasized that while the A-norm of the error and the Euclidean norm of the error had to decrease monotonically in each step, the residual norm is not a reliable criterion of convergence because it can oscillate and may even increase in each but the last step.

In our talk we deal with numerical estimation of the A-norm of the error in the Hestenes and Stiefel implementation of the CG method. Estimating error norms in the conjugate gradient method was promoted and developed into practical procedures by Golub and his collaborators. The estimates were related to moments and Gauss-type quadrature. More recently, several authors published estimates developed by simple algebraic manipulations.

We prove that the lower bound for the A-norm of the error based on Gauss quadrature is mathematically equivalent to the simple lower bound based on an original formula present in the paper by Hestenes and Stiefel [1]. We show that this simplest estimate is numerically stable. In our opinion, this estimate should be a part of any conjugate gradient computation.

References:

[1] M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bureau Standarts, 49 (1952), pp. 409-435.

[2] Z. Strakos and P. Tichy, On Error Estimation in the Conjugate Gradient Method and Why It Works In Finite Precision Computations, Electronic Transactions on Numerical Analysis (ETNA), Volume 13, pp. 56-80, published online, 2002. The original publication is available on LINK at http://etna.mcs.kent.edu/ (c) ETNA.

Abstract:
In many applications one is faced with the task of simulating or controlling complex dynamical systems. Such applications include for instance, weather prediction, air quality management, VLSI chip design, molecular dynamics, active noise reduction, chemical reactors, etc. In all these cases complexity manifests itself as the number of first order differential equations which arise. For the above examples, depending on the level of modeling detail required, complexity may range anywhere from a few thousand to a few million first order equations, and above. Simulating (controlling) systems of such complexity becomes a challenging problem, irrespective of the computational resources available. In this talk we will first briefly describe some motivating examples, we will then define the problem in mathematical terms and sketch a methodology for its solution. The talk will conclude with open problems and directions for future research.

Abstract:
This paper is concerned with transparent boundary conditions (TBCs) for the time-dependent Schroedinger equation in one and two dimensions. Discrete TBCs are introduced in the numerical simulations of whole space problems in order to reduce the computational domain to a finite region. Since the discrete TBC for the Schroedinger equation includes a convolution w.r.t. time with a weakly decaying kernel, its numerical evaluation becomes very costly for large-time simulations. As a remedy we construct approximate TBCs with a kernel having the form of a finite sum-of-exponentials, which can be evaluated in a very efficient recursion. We prove stability of the resulting initial-boundary value scheme, give error estimates for the considered approximation of the boundary condition, and illustrate the efficiency of the proposed method on several examples.

Abstract:
This paper is about the art of modularization. We focus on modularization as a method of Integrated Assessment modelling. Integrated Assessment models are applied in order to support climate policy decision-making which, however, is limited due to deficits of traditional Integrated Assessment models. There is a lack of expansibility, transparency, applicability, and credibility. We present a modular approach that should help to overcome these deficits. This approach is distinguished by the way of module coupling which is based on an interplay of a job control module, a numerical coupling module, and a couple of stand-alone functional modules. The numerical coupling module - the core component - serves to catch the feedbacks between the functional modules by means of a two-phase meta-optimization. A first implemented example that couples an economic and a climate module is presented. The algorithm and mathematical structure behind will be discussed as well as important features like convergence behaviour and reliability.

Abstract:
We present the convergence properties of a fully discrete linear finite element solution for a one-dimensional elliptic problem subject to general boundary conditions. The method is equivalent to a finite difference scheme on a nonuniform mesh and the obtained convergence is then a so-called supraconvergence result for solution and gradient. Numerical results illustrate the performance of the method and support the convergence result.