Adaptive discretization for signal detection in statistical inverse problems

We discuss statistical tests in inverse problems when the original equation is replaced by a discretized one, i.e. a linear system of equations. Previous studies revealed that using the discretization level as regularizing procedure is possible, but its application is limited unless discretization is restricted to the singular value decomposition, see C. Marteau and P. Mathé, General regularization schemes for signal detection in inverse problems, 2013. General linear regularization may circumvent this, and we propose a regularization of the discretized equations. The discretization level may be chosen adaptively, which may save computational budget. This results in tests which are known to yield the optimal separation rate up to some constant in many cases.     

Regularized collocation method for Fredholm integral equations of the first kind

In this paper we consider a collocation method for solving Fredholm integral equations of the first kind, which is known to be an ill-posed problem. An “unregularized” use of this method can give reliable results in the case when the rate at which smallest singular values of the collocation matrices decrease is known a priori. In this case the number of collocation points plays the role of a regularization parameter. If the a priori information mentioned above is not available, then a combination of collocation with Tikhonov regularization can be the method of choice. We analyze such regularized collocation in a rather general setting, when a solution smoothness is given as a source condition with an operator monotone index function. This setting covers all types of smoothness studied so far in the theory of Tikhonov regularization. One more issue discussed in this paper is an a posteriori choice of the regularization parameter, which allows us to reach an optimal order of accuracy for deterministic noise model without any knowledge of solution smoothness.     

Error estimates for the discretization of elliptic control problems with pointwise control and state constraints

A family of elliptic optimal control problems with pointwise constraints on control and state is considered. We are interested in approximation of the optimal solution by a finite element discretization of the involved partial differential equations. The discretization error for a problem with mixed state constraints is estimated in the semidiscrete case and in the fully discrete scheme with the convergence of order h|ln h| and h ^1/2, respectively. However, considering the unregularized continuous problem and the discrete regularized version, and choosing suitable relation between the regularization parameter and the mesh size, i.e., ε∼h ², a convergence order arbitrary close to 1, i.e., h ^1−β is obtained. Therefore, we benefit from tuning the involved parameters.     

Direct Implementation of Tikhonov Regularization for the First Kind Integral Equation

A common way to handle the Tikhonov regularization method for the first kind Fredholm integral equations, is first to discretize and then to work with the final linear system. This unavoidably inflicts discretization errors which may lead to disastrous results, especially when a quadrature rule is used. We propose to regularize directly the integral equation resulting in a continuous Tikhonov problem. The Tikhonov problem is reduced to a simple least squares problem by applying the Golub-Kahan bidiagonalization (GKB) directly to the integral operator. The regularization parameter and the iteration index are determined by the discrepancy principle approach. Moreover, we study the discrete version of the proposed method resulted from numerical evaluating the needed integrals. Focusing on the nodal values of the solution results in a weighted version of GKB-Tikhonov method for linear systems arisen from the Nyström discretization. Finally, we use numerical experiments on a few test problems to illustrate the performance of our algorithms.     

A well-posed shooting method for transferable DAE's

Summary Consider a TPBVP for transferable nonlinear DAE's. In general the shooting equation has a singular Jacobian. A multiple shooting method which has a nonsingular Jacobian and also produces consistent initial values for the integration is presented. The estimation of the condition of the Jacobian shows the well-posedness of the method. Some illustrative examples are given     

Regularization of Discrete Ill-Posed Problems

The paper concerns conditioning aspects of finite-dimensional problems arising when the Tikhonov regularization is applied to discrete ill-posed problems. A relation between the regularization parameter and the sensitivity of the regularized solution is investigated. The main conclusion is that the condition number can be decreased only to the square root of that for the nonregularized problem. The convergence of solutions of regularized discrete problems to the exact generalized solution is analyzed just in the case when the regularization corresponds to the minimal condition number. The convergence theorem is proved under the assumption of the suitable relation between the discretization level and the data error. As an example the method of truncated singular value decomposition with regularization is considered. This revised version was published online in July 2006 with corrections to the Cover Date.     

Error analysis of finite element approximations of the inverse mean curvature flow arising from the general relativity

This paper proposes and analyzes a finite element method for a nonlinear singular elliptic equation arising from the black hole theory in the general relativity. The nonlinear equation, which was derived and analyzed by Huisken and Ilmanen in (J Diff Geom 59:353–437), represents a level set formulation for the inverse mean curvature flow describing the evolution of a hypersurface whose normal velocity equals the reciprocal of its mean curvature. We first propose a finite element method for a regularized flow which involves a small parameter ɛ; a rigorous analysis is presented to study well-posedness and convergence of the scheme under certain mesh-constraints, and optimal rates of convergence are verified. We then prove uniform convergence of the finite element solution to the unique weak solution of the nonlinear singular elliptic equation as the mesh size h and the regularization parameter ɛ both tend to zero. Computational results are provided to show the efficiency of the proposed finite element method and to numerically validate the “jumping out” phenomenon of the weak solution of the inverse mean curvature flow. Numerical studies are presented to evidence the existence of a polynomial scaling law between the mesh size h and the regularization parameter ɛ for optimal convergence of the proposed scheme. Finally, a numerical convergence study for another approach recently proposed by R. Moser (The inverse mean curvature flow and p-harmonic functions. preprint U Bath, 2005) for approximating the inverse mean curvature flow via p-harmonic functions is also included.     

A second-order accurate numerical method for a fractional wave equation

We study a generalized Crank–Nicolson scheme for the time discretization of a fractional wave equation, in combination with a space discretization by linear finite elements. The scheme uses a non-uniform grid in time to compensate for the singular behaviour of the exact solution at t = 0. With appropriate assumptions on the data and assuming that the spatial domain is convex or smooth, we show that the error is of order k ² + h ², where k and h are the parameters for the time and space meshes, respectively.     

Self–regularization by projection for noisy pseudodifferential equations of negative order

It is well known, that pseudodifferential equations of negative order considered in Sobolev spaces with small smoothness indices are ill–posed. On the other hand, it is known that efficient discretization schemes with properly chosen discretization parameters allow to obtain a regularization effect for such equations. The main accomplishment of the present paper is the principle for the adaptive choice of the discretization parameters directly from noisy discrete data. We argue that the combination of this principle with wavelet–based matrix compression techniques leads to algorithms which are order–optimal in the sense of complexity.     

Numerical analysis of a Stokes interface problem based on formulation using the characteristic function

Numerical analysis of a model Stokes interface problem with the homogeneous Dirichlet boundary condition is considered. The interface condition is interpreted as an additional singular force field to the Stokes equations using the characteristic function. The finite element method is applied after introducing a regularization of the singular source term. Consequently, the error is divided into the regularization and discretization parts which are studied separately. As a result, error estimates of order h^1/2 in H¹ × L² norm for the velocity and pressure, and of order h in L² norm for the velocity are derived. Those theoretical results are also verified by numerical examples.     

A C0 interior penalty discontinuous Galerkin method for fourth‐order total variation flow. I: Derivation of the method and numerical results

We consider the numerical solution of a fourth‐order total variation flow problem representing surface relaxation below the roughening temperature. Based on a regularization and scaling of the nonlinear fourth‐order parabolic equation, we perform an implicit discretization in time and a C⁰ Interior Penalty Discontinuous Galerkin (C⁰IPDG) discretization in space. The C⁰IPDG approximation can be derived from a mixed formulation involving numerical flux functions where an appropriate choice of the flux functions allows to eliminate the discrete dual variable. The fully discrete problem can be interpreted as a parameter dependent nonlinear system with the discrete time as a parameter. It is solved by a predictor corrector continuation strategy featuring an adaptive choice of the time step sizes. A documentation of numerical results is provided illustrating the performance of the C⁰IPDG method and the predictor corrector continuation strategy. The existence and uniqueness of a solution of the C⁰IPDG method will be shown in the second part of this paper.     

A parameter-uniform numerical method for a Sobolev problem with initial layer

The present study is concerned with the numerical solution, using finite difference method of a one-dimensional initial-boundary value problem for a linear Sobolev or pseudo-parabolic equation with initial jump. In order to obtain an efficient method, to provide good approximations with independence of the perturbation parameter, we have developed a numerical method which combines a finite difference spatial discretization on uniform mesh and the implicit rule on Shishkin mesh(S-mesh) for the time variable. The fully discrete scheme is shown to be convergent of order two in space and of order one expect for a logarithmic factor in time, uniformly in the singular perturbation parameter. Some numerical results confirming the expected behavior of the method are shown.      

Discretization of the Poisson equation with non‐smooth data and emphasis on non‐convex domains

Several approaches are discussed how to understand the solution of the Dirichlet problem for the Poisson equation when the Dirichlet data are non‐smooth such as if they are in only. For the method of transposition (sometimes called very weak formulation) three spaces for the test functions are considered, and a regularity result is proved. An approach of Berggren is recovered as the method of transposition with the second variant of test functions. A further concept is the regularization of the boundary data combined with the weak solution of the regularized problem. The effect of the regularization error is studied. The regularization approach is the simplest to discretize. The discretization error is estimated for a sequence of quasi‐uniform meshes. Since this approach turns out to be equivalent to Berggren's discretization his error estimates are rendered more precisely. Numerical tests show that the error estimates are sharp, in particular that the order becomes arbitrarily small when the maximal interior angle of the domain tends to .© 2016 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 1433–1454, 2016     

Preconditioners Based on Fundamental Solutions

We consider a new preconditioning technique for the iterative solution of linear systems of equations that arise when discretizing partial differential equations. The method is applied to finite difference discretizations, but the ideas apply to other discretizations too. If E is a fundamental solution of a differential operator P, we have E*(Pu) = u. Inspired by this, we choose the preconditioner to be a discretization of an approximate inverse K, given by a convolution-like operator with E as a kernel. We present analysis showing that if P is a first order differential operator, KP is bounded, and numerical results show grid independent convergence for first order partial differential equations, using fixed point iterations. For the second order convection-diffusion equation convergence is no longer grid independent when using fixed point iterations, a result that is consistent with our theory. However, if the grid is chosen to give a fixed number of grid points within boundary layers, the number of iterations is independent of the physical viscosity parameter. AMS subject classification (2000) 65F10, 65N22     

Exponential Finite Elements for a Phase Field Fracture Model

Sharp interface material models can be related to phase field models by introducing an order parameter, whose value is assigned to the different phases of a material. The elastic material law is coupled to the evolution equation of the order parameter and cracking is addressed as a phase transition problem instead of a moving boundary value problem. A regularization parameter ϵ controls the width of the diffuse cracks represented by the order parameter and the underlying sharp interface model can be recovered from the phase field model by the limit ϵ → 0. However, in numerical simulations using standard finite elements with linear shape functions, the minimum value of ϵ is restricted by the grid size and therefore the discretization of the crack field requires extensive mesh refinement for small values of ϵ. In this work, we construct special 2d shape functions which take into account the exponential character of the crack field and its dependence on the parameter ϵ. Especially in simulations with small values of ϵ and a rather coarse mesh, the elements with exponential shape functions perform significantly better than standard linear elements. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A geometric view of Krylov subspace methods on singular systems

We give a geometric framework for analysing iterative methods on singular linear systems A x = b and apply them to Krylov subspace methods. The idea is to decompose the method into the ?(A) component and its orthogonal complement ?(A)^?, where ?(A) is the range of A. We apply the framework to GMRES, GMRES(k) and GCR(k), and derive conditions for convergence without breakdown for inconsistent and consistent singular systems. The approach also gives a geometric interpretation and different proofs of the conditions obtained by Brown and Walker for GMRES. We also give examples arising in the finite difference discretization of two‐point boundary value problems of an ordinary differential equation. Copyright © 2010 John Wiley & Sons, Ltd.     

An inverse problem for space‐fractional backward diffusion problem

In this paper, an inverse problem for space‐fractional backward diffusion equation, which is highly ill‐posed, is considered. This problem is obtained from the classical diffusion equation by replacing the second‐order space derivative with a Riesz–Feller derivative of order α ∈ (0,2]. We show that such a problem is severely ill‐posed, and further present a simplified Tikhonov regularization method to deal with this problem. Convergence estimate is presented under a priori choice of regularization parameter. Numerical experiments are given to illustrate the accuracy and efficiency of the proposed method. Copyright © 2013 John Wiley & Sons, Ltd.     

Discretized Lavrent’ev regularization for the autoconvolution equation

Lavrent’ev regularization for the autoconvolution equation was considered by Janno J. in Lavrent’ev regularization of ill-posed problems containing nonlinear near-to-monotone operators with application to autoconvolution equation, Inverse Prob. 2000;16:333–348. Here this study is extended by considering discretization of the Lavrent’ev scheme by splines. It is shown how to maintain the known convergence rate by an appropriate choice of spline spaces and a proper choice of the discretization level. For piece-wise constant splines the discretized equation allows for an explicit solver, in contrast to using higher order splines. This is used to design a fast implementation by means of post-smoothing, which provides results, which are indistinguishable from results obtained by direct discretization using cubic splines.     

Discretized Tikhonov–Phillips regularization for a naturally linearized parameter identification problem

The problem of identification of the diffusion coefficient in the partial differential equation is considered. We discuss a natural linearization of this problem and application of discretized Tikhonov–Phillips regularization to its linear version. Using recent results of regularization theory, we propose a strategy for the choice of regularization and discretization parameters which automatically adapts to unknown smoothness of the coefficient. The estimation of the accuracy will be given and various numerical test supporting theoretical results will be presented.     

SharpL ∞-error estimates for semilinear elliptic problems with free boundaries

Summary A numerical scheme to approximate a semilinear PDE involving a (singular) maximal monotone graph is analyzed inL . A preliminary regularization is combined with piecewise linear finite elements defined on a triangulation which is not assumed to be acute; the discrete maximum principle is thus avoided. Sharp pointwise error estimates are derived for both the smoothing and the discretization procedures. An optimal choice of the regularization parameter as a function of the mesh size leads to a sharp global rate of convergence. These error estimates for solutions, in conjunction with nondegeneracy properties of continuous problems, provide sharp interface error estimates. Two model examples are discussed: the obstacle problem and a combustion equation.This work was partially supported by Consiglio Nazionale delle Ricerche of Italy while the author was in residence at the Istituto di Analisi Numerica del C.N.R. di Pavia