Exact error estimates and optimal randomized algorithms for integration

Exact error estimates for evaluating multi-dimensional integrals are considered. An estimate is called exact if the rates of convergence for the low- and upper-bound estimate coincide. The algorithm with such an exact rate is called optimal. Such an algorithm has an unimprovable rate of convergence. The problem of existing exact estimates and optimal algorithms is discussed for some functional spaces that define the regularity of the integrand. Important for practical computations data classes are considered: classes of functions with bounded derivatives and Holder type conditions. The aim of the paper is to analyze the performance of two optimal classes of algorithms: deterministic and randomized for computing multidimensional integrals. It is also shown how the smoothness of the integrand can be exploited to construct better randomized algorithms.

What Monte Carlo models can do and cannot do efficiently?

The question "what Monte Carlo models can do and cannot do efficiently" is discussed for some functional spaces that define the regularity of the input data. Data classes important for practical computations are considered: classes of functions with bounded derivatives and Holder type conditions, as well as Korobov-like spaces. Theoretical performance analysis of some algorithms with unimprovable rate of convergence is given. Estimates of computational complexity of two classes of algorithms - deterministic and randomized for both problems - numerical multidimensional integration and calculation of linear functionals of the solution of a class of integral equations are presented. (c) 2007 Elsevier Inc. All rights reserved.

An Exponentially Convergent Nonpolynomial Finite Element Method for Time-Harmonic Scattering from Polygons

In recent years nonpolynomial finite element methods have received increasing attention for the efficient solution of wave problems. As with their close cousin the method of particular solutions, high efficiency comes from using solutions to the Helmholtz equation as basis functions. We present and analyze such a method for the scattering of two-dimensional scalar waves from a polygonal domain that achieves exponential convergence purely by increasing the number of basis functions in each element. Key ingredients are the use of basis functions that capture the singularities at corners and the representation of the scattered field towards infinity by a combination of fundamental solutions. The solution is obtained by minimizing a least-squares functional, which we discretize in such a way that a matrix least-squares problem is obtained. We give computable exponential bounds on the rate of convergence of the least-squares functional that are in very good agreement with the observed numerical convergence. Challenging numerical examples, including a nonconvex polygon with several corner singularities, and a cavity domain, are solved to around 10 digits of accuracy with a few seconds of CPU time. The examples are implemented concisely with MPSpack, a MATLAB toolbox for wave computations with nonpolynomial basis functions, developed by the authors. A code example is included.

An unstructured CVFEM and moving interface algorithm for non-Newtonian Hele-Shaw flows in injection molding

Purpose - The purpose of this paper is to develop a novel unstructured simulation approach for injection molding processes described by the Hele-Shaw model. Design/methodology/approach - The scheme involves dual dynamic meshes with active and inactive cells determined from an initial background pointset. The quasi-static pressure solution in each timestep for this evolving unstructured mesh system is approximated using a control volume finite element method formulation coupled to a corresponding modified volume of fluid method. The flow is considered to be isothermal and non-Newtonian. Findings - Supporting numerical tests and performance studies for polystyrene described by Carreau, Cross, Ellis and Power-law fluid models are conducted. Results for the present method are shown to be comparable to those from other methods for both Newtonian fluid and polystyrene fluid injected in different mold geometries. Research limitations/implications - With respect to the methodology, the background pointset infers a mesh that is dynamically reconstructed here, and there are a number of efficiency issues and improvements that would be relevant to industrial applications. For instance, one can use the pointset to construct special bases and invoke a so-called ""meshless"" scheme using the basis. This would require some interesting strategies to deal with the dynamic point enrichment of the moving front that could benefit from the present front treatment strategy. There are also issues related to mass conservation and fill-time errors that might be addressed by introducing suitable projections. The general question of ""rate of convergence"" of these schemes requires analysis. Numerical results here suggest first-order accuracy and are consistent with the approximations made, but theoretical results are not available yet for these methods. Originality/value - This novel unstructured simulation approach involves dual meshes with active and inactive cells determined from an initial background pointset: local active dual patches are constructed ""on-the-fly"" for each ""active point"" to form a dynamic virtual mesh of active elements that evolves with the moving interface.

Wavelet regression with correlated errors on a piecewise Holder class

This paper generalizes the methodology of Cat and Brown [Cai, T., Brown, L.D., 1998. Wavelet shrinkage for nonequispaced samples. The Annals of Statistics 26, 1783-1799] for wavelet shrinkage for nonequispaced samples, but in the presence of correlated stationary Gaussian errors. If the true function is a member of a piecewise Holder class, it is shown that, even for long memory errors, the rate of convergence of the procedure is almost-minimax relative to the independent and identically distributed errors case. (c) 2008 Elsevier B.V. All rights reserved.

Continuidade de atratores para a discretização de problemas parabólicos usando o método de elementos finitos

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Parameterschätzung in Verzweigungsprozessen mit Immigration

Im Verzweigungsprozess mit Immigration werden Schätzer für die erwartete Nachkommenzahl m eines Individuums und die erwartete Immigration λ pro Generation konstruiert. Sie sind nur aufgrund der beobachteten Populationsgröße einer jeden Generation konsistent, ohne Vorkenntnis darüber, ob der Prozess subkritisch (m<1), kritisch (m=1) oder superkritisch (m>1) ist. Im superkritischen Fall ist der Schätzer für λ jedoch nicht konsistent. Dies ist aber keine Einschränkung, denn es wird gezeigt, dass in diesem Fall kein konsistenter Schätzer für λ existiert. Des Weiteren werden Konvergenzgeschwindigkeit der Schätzer und asymptotische Verteilungen der Schätzfehler untersucht. Dabei werden die Fälle (m<1), (m>1) und (m=1) unterschieden, was gänzlich verschiedene Vorgehensweisen erfordert (Ergodizität, Martingalmethoden, Diffusionsapproximationen). Diese hier vorliegende Diplomarbeit orientiert sich an den Ideen und Ergebnissen von Wei und Winnicki (1989/90).

Dichteschätzung mit Wavelets

Es soll eine Dichtefunktion geschätzt werden unter der Modellannahme, dass diese in einer geeigneten Besovklasse liegt und kompakten Träger hat. Hierzu wird ein Waveletschätzer TW näher untersucht, der Thresholding-Methoden verwendet. Es wird die asymptotische Konvergenzgeschwindigkeit von TW für eine große Zahl von Beobachtungen angegeben und bewiesen. Schließlich werden in einem Überblick weitere Waveletschätzer diskutiert und mit TW verglichen. Es zeigt sich, dass TW in vielen Modellannahmen die optimale Konvergenzrate erreicht.

Wavelet estimation in diffusions with periodicity

Wir betrachten einen zeitlich inhomogenen Diffusionsprozess, der durch eine stochastische Differentialgleichung gegeben wird, deren Driftterm ein deterministisches T-periodisches Signal beinhaltet, dessen Periodizität bekannt ist. Dieses Signal sei in einem Besovraum enthalten. Wir schätzen es mit Hilfe eines nichtparametrischen Waveletschätzers. Unser Schätzer ist von einem Wavelet-Dichteschätzer mit Thresholding inspiriert, der 1996 in einem klassischen iid-Modell von Donoho, Johnstone, Kerkyacharian und Picard konstruiert wurde. Unter gewissen Ergodizitätsvoraussetzungen an den Prozess können wir nichtparametrische Konvergenzraten angegeben, die bis auf einen logarithmischen Term den Raten im klassischen iid-Fall entsprechen. Diese Raten werden mit Hilfe von Orakel-Ungleichungen gezeigt, die auf Ergebnissen über Markovketten in diskreter Zeit von Clémencon, 2001, beruhen. Außerdem betrachten wir einen technisch einfacheren Spezialfall und zeigen einige Computersimulationen dieses Schätzers.

Berry-Esseen bounds for nonlinear statistics, and asymptotic relative efficiency between correlation statistics

Four papers, written in collaboration with the author’s graduate school advisor, are presented. In the first paper, uniform and non-uniform Berry-Esseen (BE) bounds on the convergence to normality of a general class of nonlinear statistics are provided; novel applications to specific statistics, including the non-central Student’s, Pearson’s, and the non-central Hotelling’s, are also stated. In the second paper, a BE bound on the rate of convergence of the F-statistic used in testing hypotheses from a general linear model is given. The third paper considers the asymptotic relative efficiency (ARE) between the Pearson, Spearman, and Kendall correlation statistics; conditions sufficient to ensure that the Spearman and Kendall statistics are equally (asymptotically) efficient are provided, and several models are considered which illustrate the use of such conditions. Lastly, the fourth paper proves that, in the bivariate normal model, the ARE between any of these correlation statistics possesses certain monotonicity properties; quadratic lower and upper bounds on the ARE are stated as direct applications of such monotonicity patterns.

WYPIWYG Hyperelasticity

In this paper we describe a new promising procedure to model hyperelastic materials from given stress-strain data. The main advantage of the proposed method is that the user does not need to have a relevant knowledge of hyperelasticity, large strains or hyperelastic constitutive modelling. The engineer simply has to prescribe some stress strain experimental data (whether isotropic or anisotropic) in also user prescribed stress and strain measures and the model almost exactly replicates the experimental data. The procedure is based on the piece-wise splines model by Sussman and Bathe and may be easily generalized to transversely isotropic and orthotropic materials. The model is also amenable of efficient finite element implementation. In this paper we briefly describe the general procedure, addressing the advantages and limitations. We give predictions for arbitrary ?experimental data? and also give predictions for actual experiments of the behaviour of living soft tissues. The model may be also implemented in a general purpose finite element program. Since the obtained strain energy functions are analytic piece-wise functions, the constitutive tangent may be readily derived in order to be used for implicit static problems, where the equilibrium iterations must be performed and the material tangent is needed in order to preserve the quadratic rate of convergence of Newton procedures.

Truncation error estimation in the Discontinuous Galerkin Spectral Element Method

En esta tesis, el método de estimación de error de truncación conocido como restimation ha sido extendido de esquemas de bajo orden a esquemas de alto orden. La mayoría de los trabajos en la bibliografía utilizan soluciones convergidas en mallas de distinto refinamiento para realizar la estimación. En este trabajo se utiliza una solución en una única malla con distintos órdenes polinómicos. Además, no se requiere que esta solución esté completamente convergida, resultando en el método conocido como quasi-a priori T-estimation. La aproximación quasi-a priori estima el error mientras el residuo del método iterativo no es despreciable. En este trabajo se demuestra que algunas de las hipótesis fundamentales sobre el comportamiento del error, establecidas para métodos de bajo orden, dejan de ser válidas en esquemas de alto orden, haciendo necesaria una revisión completa del comportamiento del error antes de redefinir el algoritmo. Para facilitar esta tarea, en una primera etapa se considera el método conocido como Chebyshev Collocation, limitando la aplicación a geometrías simples. La extensión al método Discontinuouos Galerkin Spectral Element Method presenta dificultades adicionales para la definición precisa y la estimación del error, debidos a la formulación débil, la discretización multidominio y la formulación discontinua. En primer lugar, el análisis se enfoca en leyes de conservación escalares para examinar la precisión de la estimación del error de truncación. Después, la validez del análisis se demuestra para las ecuaciones incompresibles y compresibles de Euler y Navier Stokes. El método de aproximación quasi-a priori r-estimation permite desacoplar las contribuciones superficiales y volumétricas del error de truncación, proveyendo información sobre la anisotropía de las soluciones así como su ratio de convergencia con el orden polinómico. Se demuestra que esta aproximación quasi-a priori produce estimaciones del error de truncación con precisión espectral. ABSTRACT In this thesis, the τ-estimation method to estimate the truncation error is extended from low order to spectral methods. While most works in the literature rely on fully time-converged solutions on grids with different spacing to perform the estimation, only one grid with different polynomial orders is used in this work. Furthermore, a non timeconverged solution is used resulting in the quasi-a priori τ-estimation method. The quasi-a priori approach estimates the error when the residual of the time-iterative method is not negligible. It is shown in this work that some of the fundamental assumptions about error tendency, well established for low order methods, are no longer valid in high order schemes, making necessary a complete revision of the error behavior before redefining the algorithm. To facilitate this task, the Chebyshev Collocation Method is considered as a first step, limiting their application to simple geometries. The extension to the Discontinuous Galerkin Spectral Element Method introduces additional features to the accurate definition and estimation of the error due to the weak formulation, multidomain discretization and the discontinuous formulation. First, the analysis focuses on scalar conservation laws to examine the accuracy of the estimation of the truncation error. Then, the validity of the analysis is shown for the incompressible and compressible Euler and Navier Stokes equations. The developed quasi-a priori τ-estimation method permits one to decouple the interfacial and the interior contributions of the truncation error in the Discontinuous Galerkin Spectral Element Method, and provides information about the anisotropy of the solution, as well as its rate of convergence in polynomial order. It is demonstrated here that this quasi-a priori approach yields a spectrally accurate estimate of the truncation error.

Approximation Classes for Adaptive Methods

* This work has been supported by the Office of Naval Research Contract Nr. N0014-91-J1343, the Army Research Office Contract Nr. DAAD 19-02-1-0028, the National Science Foundation grants DMS-0221642 and DMS-0200665, the Deutsche Forschungsgemeinschaft grant SFB 401, the IHP Network “Breaking Complexity” funded by the European Commission and the Alexan- der von Humboldt Foundation.

Nonlinear Normalization in Limit Theorems for Extremes

2000 Mathematics Subject Classification: 60G70, 60F05.

Some Bounds for Almost Absorbing Birth and Death Processes with Catastrophes

2000 Mathematics Subject Classification: 60J27.