Optimization of Schwarz waveform relaxation over short time windows

Schwarz waveform relaxation algorithms (SWR) are naturally parallel solvers for evolution partial differential equations. They are based on a decomposition of the spatial domain into subdomains, and a partition of the time interval of interest into time windows. On each time window, an iteration, during which subproblems are solved in space-time subdomains, is then used to obtain better and better approximations of the overall solution. The information exchange between subdomains in space-time is performed through classical or optimized transmission conditions (TCs). We analyze in this paper the optimization problem when the time windows are short. We use as our model problem the optimized SWR algorithm with Robin TCs applied to the heat equation. After a general convergence analysis using energy estimates, we prove that in one spatial dimension, the optimized Robin parameter scales like the inverse of the length of the time window, which is fundamentally different from the known scaling on general bounded time windows, which is like the inverse of the square root of the time window length. We illustrate our analysis with a numerical experiment.     

A procedure for determining a spacewise dependent heat source and the initial temperature

The inverse problem of determining a spacewise dependent heat source, together with the initial temperature for the parabolic heat equation, using the usual conditions of the direct problem and information from two supplementary temperature measurements at different instants of time is studied. These spacewise dependent temperature measurements ensure that this inverse problem has a unique solution, despite the solution being unstable, hence the problem is ill-posed. We propose an iterative algorithm for the stable reconstruction of both the initial data and the source based on a sequence of well-posed direct problems for the parabolic heat equation, which are solved at each iteration step using the boundary element method. The instability is overcome by stopping the iterations at the first iteration for which the discrepancy principle is satisfied. Numerical results are presented for a typical benchmark test example, which has the input measured data perturbed by increasing amounts of random noise. The numerical results show that the proposed procedure gives accurate numerical approximations in relatively few iterations.     

A variational method for identifying a spacewise-dependent heat source

The inverse problem of determining a spacewise-dependent heatsource for the parabolic heat equation using the usual conditionsof the direct problem and information from one supplementarytemperature measurement at a given instant of time is studied.This spacewise-dependent temperature measurement ensures thatthis inverse problem has a unique solution, but the solutionis unstable and hence the problem is ill-posed. We propose avariational conjugate gradient-type iterative algorithm forthe stable reconstruction of the heat source based on a sequenceof well-posed direct problems for the parabolic heat equationwhich are solved at each iteration step using the boundary elementmethod. The instability is overcome by stopping the iterativeprocedure at the first iteration for which the discrepancy principleis satisfied. Numerical results are presented which have theinput measured data perturbed by increasing amounts of randomnoise. The numerical results show that the proposed procedureyields stable and accurate numerical approximations after onlya few iterations.     

Numerical methods for some inverse problems of heart electrophysiology

We consider numerical methods for solving inverse problems that arise in heart electrophysiology. The first inverse problem is the Cauchy problem for the Laplace equation. Its solution algorithm is based on the Tikhonov regularization method and the method of boundary integral equations. The second inverse problem is the problem of finding the discontinuity surface of the coefficient of conductivity of a medium on the basis of the potential and its normal derivative given on the exterior surface. For its numerical solution, we suggest a method based on the method of boundary integral equations and the assumption on a special representation of the unknown surface.     

The Sinc‐Galerkin method for solving an inverse parabolic problem with unknown source term

The inverse problem of determining an unknown source term depending on space variable in a parabolic equation is considered. A numerical algorithm is presented for recovering the unknown function and obtaining a solution of the problem. As this inverse problem is ill‐posed, Tikhonov regularization is used for finding a stable solution. For solving the direct problem, a Galerkin method with the Sinc basis functions in both the space and time domains is presented. This approximate solution displays an exponential convergence rate and is valid on the infinite time interval. Finally, some examples are presented to illustrate the ability and efficiency of this numerical method. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013     

范数下无容量限制设施选址逆问题的求解方法

一个优化问题的逆问题是这样一类问题,在给定该优化问题的一个可行解时,通过最小化目标函数中参数的改变量(在某个范数下)使得该可行解成为改变参数后的该优化问题的最优解。对于本是NP-难问题的无容量限制设施选址问题,证明了其逆问题仍是NP-难的。研究了使用经典的行生成算法对无容量限制设施选址的逆问题进行计算,并给出了求得逆问题上下界的启发式方法。两种方法分别基于对子问题的线性松弛求解给出上界和利用邻域搜索以及设置迭代循环次数的方式给出下界。数值结果表明线性松弛法得到的上界与最优值差距较小,但求解效率提升不大;而启发式方法得到的下界与最优值差距极小,极大地提高了求解该逆问题的效率。     

A new algorithm based on factorization for heterogeneous domain decomposition

Often computational models are too expensive to be solved in the entire domain of simulation, and a cheaper model would suffice away from the main zone of interest. We present for the concrete example of an evolution problem of advection reaction diffusion type a heterogeneous domain decomposition algorithm which allows us to recover a solution that is very close to the solution of the fully viscous problem, but solves only an inviscid problem in parts of the domain. Our new algorithm is based on the factorization of the underlying differential operator, and we therefore call it factorization algorithm. We give a detailed error analysis in one spatial dimension, and show that we can obtain approximations in the viscous region which are much closer to the viscous solution in the entire domain of simulation than approximations obtained by other heterogeneous domain decomposition algorithms from the literature. We illustrate our results with numerical experiments in one and two spatial dimensions.     

Range reduction techniques for improving computational efficiency in global optimization of signomial geometric programming problems

Many global optimization approaches for solving signomial geometric programming problems are based on transformation techniques and piecewise linear approximations of the inverse transformations. Since using numerous break points in the linearization process leads to a significant increase in the computational burden for solving the reformulated problem, this study integrates the range reduction techniques in a global optimization algorithm for signomial geometric programming to improve computational efficiency. In the proposed algorithm, the non-convex geometric programming problem is first converted into a convex mixed-integer nonlinear programming problem by convexification and piecewise linearization techniques. Then, an optimization-based approach is used to reduce the range of each variable. Tightening variable bounds iteratively allows the proposed method to reach an approximate solution within an acceptable error by using fewer break points in the linearization process, therefore decreasing the required CPU time. Several numerical experiments are presented to demonstrate the advantages of the proposed method in terms of both computational efficiency and solution quality.     

Inverse source problem for a diffusion equation involving the fractional spectral Laplacian

In this paper, we consider an inverse problem related to a fractional diffusion equation. The model problem is governed by a nonlinear partial differential equation involving the fractional spectral Laplacian. This study is focused on the reconstruction of an unknown source term from a partial internal measured data. The considered ill‐posed inverse problem is formulated as a minimization one. The existence, uniqueness, and stability of the solution are discussed. Some theoretical results are established. The numerical reconstruction of the unknown source term is investigated using an iterative process. The proposed method involves a denoising procedure at each iteration step and provides a sequence of source term approximations converging in norm to the actual solution of the minimization problem. Some numerical results are presented to show the efficiency and the accuracy of the proposed approach.     

Convergence properties of a class of boundary element approximations to linear diffusion problems with localized nonlinear reactions

We consider a boundary element (BE) Algorithm for solving linear diffusion desorption problems with localized nonlinear reactions. The proposed BE algorithm provides an elegant representation of the effect of localized nonlinear reactions, which enables the effects of arbitrarily oriented defect structures to be incorporated into BE models without having to perform severe mesh deformations. We propose a one-step recursion procedure to advance the BE solution of linear diffusion localized nonlinear reaction problems and investigate its convergence properties. The separation of the linear and nonlinear effects by the boundary integral formulation enables us to consider the convergence properties of approximations to the linear terms and nonlinear terms of the boundary integral equation separately. For the linear terms we investigate how the degree of piecewise polynomial collocation in space and the size of the spatial mesh relative to the time step affects the accumulation of errors in the one-step recursion scheme. We develop a novel convergence analysis that combines asymptotic methods with Lax's Equivalence Theorem. We identify a dimensionless meshing parameter θ whose magnitudé governs the performance of the one-step BE schemes. In particular, we show that piecewise constant (PWC) and piecewise linear (PWL) BE schemes are conditionally convergent, have lower asymptotic bounds placed on the size of time steps, and which display excess numerical diffusion when small time steps are used. There is no asymptotic bound on how large the tie steps can be–this allows the solution to be advanced in fewer, larger time steps. The piecewise quadratic (PWQ) BE scheme is shown to be unconditionally convergent; there is no asymptotic restriction on the relative sizes of the time and spatial meshing and no numerical diffusion. We verify the theoretical convergence properties in numerical examples. This analysis provides useful information about the appropriate degree of spatial piecewise polynomial and the meshing strategy for a given problem. For the nonlinear terms we investigate the convergence of an explicit algorithm to advance the solution at an active site forward in time by means of Caratheodory iteration combined with piecewise linear interpolation. We consider a model problem comprising a singular nonlinear Volterra equation that represents the effect of the term in the BE formulation that is due to a single defect. We prove the convergence of the piecewise linear Caratheodory iteration algorithm to a solution of the model problem for as long as such a solution can be shown to exist. This analysis provides a theoretical justification for the use of piecewise linear Caratheodory iterates for advancing the effects of localized reactions.     

Determination of a spacewise dependent heat source

This paper investigates the inverse problem of determining a spacewise dependent heat source in the parabolic heat equation using the usual conditions of the direct problem and information from a supplementary temperature measurement at a given single instant of time. The spacewise dependent temperature measurement ensures that the inverse problem has a unique solution, but this solution is unstable, hence the problem is ill-posed. For this inverse problem, we propose an iterative algorithm based on a sequence of well-posed direct problems which are solved at each iteration step using the boundary element method (BEM). The instability is overcome by stopping the iterations at the first iteration for which the discrepancy principle is satisfied. Numerical results are presented for various typical benchmark test examples which have the input measured data perturbed by increasing amounts of random noise.     

Low-Cost Numerical Method for Solving a Coefficient Inverse Problem for the Wave Equation in Three-Dimensional Space

For the acoustic-sensing problem of determining the characteristics of a local inhomogeneity scattering a wave field in three-dimensional space, a numerical algorithm is proposed and justified that is efficient in terms of computational resources and CPU time. The algorithm is based on the fast Fourier transform, which is used under certain a priori assumptions on the character of the inhomogeneity and the observation domain of the scattered field. Typical numerical results obtained by solving this inverse problem with simulated data on a personal computer are presented, which demonstrate the capabilities of the algorithm.     

A Newton iteration process for inverse eigenvalue problems

Summary We suppose an inverse eigenvalue problem which includes the classical additive and multiplicative inverse eigenvalue problems as special cases. For the numerical solution of this problem we propose a Newton iteration process and compare it with a known method. Finally we apply it to a numerical example.     

Uniqueness in inverse obstacle scattering with conductive boundary conditions

We consider the uniqueness of the inverse obstacle scattering with conductive boundary conditions. This work is based on the original idea of Isakov for transmission boundary conditions, which utilize the solvability of the direct problem, orthogonality relations, approximations to solution of the direct problem and singular solutions. The methodology used is constructive and allows an extension to more general conditions and numerical methods.     

Computational identification of the lowest space-wise dependent coefficient of a parabolic equation

In the present work, we consider a nonlinear inverse problem of identifying the lowest coefficient of a parabolic equation. The desired coefficient depends on spatial variables only. Additional information about the solution is given at the final time moment, i.e., we consider the final redefinition. An iterative process is used to evaluate the lowest coefficient, where at each iteration we solve the standard initial-boundary value problem for the parabolic equation. On the basis of the maximum principle for the solution of the differential problem, the monotonicity of the iterative process is established along with the fact that the coefficient is approached from above. The possibilities of the proposed computational algorithm are illustrated by numerical examples for a model two-dimensional problem.     

On some issues related to the moment problem for the band matrices with operator elements

The connection between the classical moment problem and the spectral theory of second order difference operators (or Jacobi matrices) is a thoroughly studied topic. Here we examine a similar connection in the case of the second order operator replaced by an operator generated by an infinite band matrix with operator elements. For such operators, we obtain an analog of the Stone theorem and consider the inverse spectral problem which amounts to restoring the operator from the moment sequence of its Weyl matrix. We establish the solvability criterion for such problems, find the conditions ensuring that the elements of the moment sequence admit an integral representation with respect to an operator valued measure and discuss an algorithm for the recovery of the operator. We also indicate a connection between the inverse problem method and the Hermite-Padé approximations.     

On regularization methods based on dynamic programming techniques

In this article, we investigate the connection between regularization theory for inverse problems and dynamic programming theory. This is done by developing two new regularization methods, based on dynamic programming techniques. The aim of these methods is to obtain stable approximations to the solution of linear inverse ill-posed problems. We follow two different approaches and derive a continuous and a discrete regularization method. Regularization properties for both methods are proved as well as rates of convergence. A numerical benchmark problem concerning integral operators with convolution kernels is used to illustrate the theoretical results.     

On a Steffensen-Hermite method of order three

In this paper we study a third order Steffensen type method obtained by controlling the interpolation nodes in the Hermite inverse interpolation polynomial of degree 2. We study the convergence of the iterative method and we provide new convergence conditions which lead to bilateral approximations for the solution; it is known that the bilateral approximations have the advantage of offering a posteriori bounds of the errors. The numerical examples confirm the advantage of considering these error bounds.     

Asymptotic solution method for a quasilinear minimum force control problem

For a transient process in a quasilinear system, we consider an optimization problem of finding a (multi-dimensional) control with minimum intensity. We suggest an algorithm for constructing asymptotic approximations to the solution of this problem. The main advantage of the algorithm is that an optimal control problem for a linear system is solved instead of the original essentially nonlinear problem.