Robust registration of point sets using iteratively reweighted least squares

Registration of point sets is done by finding a rotation and translation that produces a best fit between a set of data points and a set of model points. We use robust M-estimation techniques to limit the influence of outliers, more specifically a modified version of the iterative closest point algorithm where we use iteratively re-weighed least squares to incorporate the robustness. We prove convergence with respect to the value of the objective function for this algorithm. A comparison is also done of different criterion functions to figure out their abilities to do appropriate point set fits, when the sets of data points contains outliers. The robust methods prove to be superior to least squares minimization in this setting.     

Block filtering decomposition

This paper introduces a new preconditioning technique that is suitable for matrices arising from the discretization of a system of PDEs on unstructured grids. The preconditioner satisfies a so‐called filtering property, which ensures that the input matrix is identical with the preconditioner on a given filtering vector. This vector is chosen to alleviate the effect of low‐frequency modes on convergence and so decrease or eliminate the plateau that is often observed in the convergence of iterative methods. In particular, the paper presents a general approach that allows to ensure that the filtering condition is satisfied in a matrix decomposition. The input matrix can have an arbitrary sparse structure. Hence, it can be reordered using nested dissection, to allow a parallel computation of the preconditioner and of the iterative process. We show the efficiency of our preconditioner through a set of numerical experiments on symmetric and nonsymmetric matrices. Copyright © 2014 John Wiley & Sons, Ltd.     

The Finite Difference Based Fast Adaptive Composite Grid Method

The fast adaptive composite grid (FAC) method is an iterative method for solving discrete boundary value problems on composite grids. McCormick introduced the method in [8] and considered the convergence behaviour for discrete problems resulting from finite volume element discretization on composite grids. In this paper we consider discrete problems resulting from finite difference discretization on composite grids. We distinguish between two obvious discretization approaches at the grid points on the interfaces between fine and coarse subgrids. The FAC method for solving such discrete problems is described. In the FAC method several intergrid transfer operators appear. We study how the convergence behaviour depends on these intergrid transfer operators. Based on theoretical insights, (quasi-)optimal intergrid transfer operators are derived. Numerical results illustrate the fast convergence of the FAC method using these intergrid transfer operators.     

Numerical convergence properties of option pricing PDEs with uncertain volatility

The pricing equations derived from uncertain volatility modelsin finance are often cast in the form of nonlinear partial differentialequations. Implicit timestepping leads to a set of nonlinearalgebraic equations which must be solved at each timestep. Tosolve these equations, an iterative approach is employed. Inthis paper, we prove the convergence of a particular iterativescheme for one factor uncertain volatility models. We also demonstratehow non-monotone discretization schemes (such as standard Crank–Nicolsontimestepping) can converge to incorrect solutions, or lead toinstability. Numerical examples are provided.     

Inexact Iterative Bregman Method for Optimal Control Problems

In this article, we investigate an inexact iterative regularization method based on generalized Bregman distances of an optimal control problem with control constraints. We show robustness and convergence of the inexact Bregman method under a regularity assumption, which is a combination of a source condition and a regularity assumption on the active sets. We also take the discretization error into account. Numerical results are presented to demonstrate the algorithm.     

A comparison of some efficient numerical methods for a nonlinear elliptic problem

The aim of this paper is to compare and realize three efficient iterative methods, which have mesh independent convergence, and to propose some improvements for them. We look for the numerical solution of a nonlinear model problem using FEM discretization with gradient and Newton type methods.     

Numerical solution of quasi-variational inequalities arising in stochastic game theory

We study the finite-difference approximation for the quasi-variational inequalities for a stochastic game involving discrete actions of the players and continuous and discrete payoff. We prove convergence of iterative schemes for the solution of the discretized quasi-variational inequalities, with estimates of the rate of convergence (via contraction mappings) in two particular cases. Further, we prove stability of the finite-difference schemes, and convergence of the solution of the discrete problems to the solution of the continuous problem as the discretization mesh goes to zero. We provide a direct interpretation of the discrete problems in terms of finite-state, continuous-time Markov processes.     

On the convergence of basic iterative methods for convection–diffusion equations

In this paper we analyze convergence of basic iterative Jacobi and Gauss–Seidel type methods for solving linear systems which result from finite element or finite volume discretization of convection–diffusion equations on unstructured meshes. In general the resulting stiffness matrices are neither M‐matrices nor satisfy a diagonal dominance criterion. We introduce two newmatrix classes and analyse the convergence of the Jacobi and Gauss–Seidel methods for matrices from these classes. A new convergence result for the Jacobi method is proved and negative results for the Gauss–Seidel method are obtained. For a few well‐known discretization methods it is shown that the resulting stiffness matrices fall into the new matrix classes. Copyright © 1999 John Wiley & Sons, Ltd.     

基于对偶混合变分形式的Uzawa型算法

基于弹性接触问题的三变量（应力，位移，接触边界位移）对偶混合变分形式，对混合有限元离散化的单边约束问题，提出了一种Uzawa型算法。首先证明了迭代算法的收敛性，然后用数值例子验证了迭代算法的有效性。     

Contraction behaviour of iteration–discretization based on gradient type projections

There is a wide range of iterative methods in infinite dimensional spaces to treat variational equations or variational inequalities. As a rule, computational handling of problems in infinite dimensional spaces requires some discretization. Any useful discretization of the original problem leads to families of problems over finite dimensional spaces. Thus, two infinite techniques, namely discretization and iteration are embedded into each other. In the present paper, the behaviour of truncated iterative methods is studied, where at each discretization level only a finite number of steps is performed. In our study no accuracy dependent a posteriori stopping criterion is used. From an algorithmic point of view, the considered methods are of iteration–discretization type. The major aim here is to provide the convergence analysis for the introduced abstract iteration–discretization methods. A special emphasis is given on algorithms for the treatment of variational inequalities with strongly monotone operators over fixed point sets of quasi-nonexpansive mappings.     

关于Schwarz交替法的收敛因子

§1.Schwarz交替法的收敛因子 我们就二阶自共轭椭圆型方程的Dirichlet问题来讨论.设Ω?R~2为一多边形区域, a(u,v)=(f,v),v∈H_0~1(Ω),f∈H~(-1)(Ω), u∈H_0~1(Ω)是定义在其上的边值问题的变分形式,双线性型时a(·,·)满足     

A Fast Iterative Method to Compute the Flow Around a Submerged Body

We develop an efficient iterative method for computing the steady linearized potential flow around a submerged body moving in a liquid of finite constant depth. In this paper we restrict the presentation to the two-dimensional problem, but the method is readily generalizable to the three-dimensional case, i.e., the flow in a canal. The problem is indefinite, which makes the convergence of most iterative methods unstable. To circumvent this difficulty, we decompose the problem into two more easily solvable subproblems and form a Schwarz--type iteration to solve the original problem. The first subproblem is definite and can therefore be solved by standard iterative methods. The second subproblem is indefinite but has no body. It is therefore easily and efficiently solvable by separation of variables. We prove that the iteration converges for sufficiently small Froude numbers. In addition, we present numerical results for a second-order accurate discretization of the problem. We demonstrate that the iterative method converges rapidly, and that the convergence rate improves when the Froude number decreases. We also verify numerically that the convergence rate is essentially independent of the grid size.

     

Grid solution of problem with unilateral constraints

The present study deals with the solution of a problem, defined in a three-dimensional domain, arising in fluid mechanics. Such problem is modelled with unilateral constraints on the boundary. Then, the problem to solve consists in minimizing a functional in a closed convex set. The characterization of the solution leads to solve a time-dependent variational inequality. An implicit scheme is used for the discretization of the time-dependent part of the operator and so we have to solve a sequence of stationary elliptic problems. For the solution of each stationary problem, an equivalent form of a minimization problem is formulated as the solution of a multivalued equation, obtained by the perturbation of the previous stationary elliptic operator by a diagonal monotone maximal multivalued operator. The spatial discretization of such problem by appropriate scheme leads to the solution of large scale algebraic systems. According to the size of these systems, parallel iterative asynchronous and synchronous methods are carried out on distributed architectures; in the present study, methods without and with overlapping like Schwarz alternating methods are considered. The convergence of the parallel iterative algorithms is analysed by contraction approaches. Finally, the parallel experiments are presented.     

A numerical method for pricing European options with proportional transaction costs

In the paper, we propose a numerical technique based on a finite difference scheme in space and an implicit time-stepping scheme for solving the Hamilton–Jacobi–Bellman (HJB) equation arising from the penalty formulation of the valuation of European options with proportional transaction costs. We show that the approximate solution from the numerical scheme converges to the viscosity solution of the HJB equation as the mesh sizes in space and time approach zero. We also propose an iterative scheme for solving the nonlinear algebraic system arising from the discretization and establish a convergence theory for the iterative scheme. Numerical experiments are presented to demonstrate the robustness and accuracy of the method.     

An iterative method for pricing American options under jump-diffusion models

We propose an iterative method for pricing American options under jump-diffusion models. A finite difference discretization is performed on the partial integro-differential equation, and the American option pricing problem is formulated as a linear complementarity problem (LCP). Jump-diffusion models include an integral term, which causes the resulting system to be dense. We propose an iteration to solve the LCPs efficiently and prove its convergence. Numerical examples with Kou?s and Merton?s jump-diffusion models show that the resulting iteration converges rapidly.     

An Efficient Policy Iteration Algorithm for Dynamic Programming Equations

We present a scheme for Hamilton-Jacobi-Bellman equations based on a semi-Lagrangian discretization and an iterative method in the policy space. The scheme exploits the idea that a good initialization of the policy iteration procedure yields a faster numerical convergence to the optimal solution. The scheme features a pre-processing step with value iterations on a coarse grid. Numerical tests assess the efficient performance of the method. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A comparison result for multisplittings and waveform relaxation methods

We show that certain multisplitting iterative methods based on overlapping blocks yield faster convergence than corresponding nonoverlapping block iterations, provided the coefficient matrix is an M-matrix. This result can be used to compare variants of the waveform relaxation algorithm for solving initial value problems. The methods under consideration use the same discretization technique, but are based on multisplittings with different overlaps. Numerical experiments on the Intel iPSC/860 hypercube are included.     

Hilbert尺度下求解非线性不适定问题的多水平迭代法

本文吸取了多水平方法的思想，采用多水平方法提供了离散化参数和迭代初值的合理的选择方法，提出了Hilbert尺度下求解非线性不适定问题的多水平Landweber迭代算法，并给出了算法的收敛性分析，证明了算法在整体上提高了Hilbert尺度下的Landweber迭代法的迭代效率。     

Convergence of a substructuring method with Lagrange multipliers

Summary. We analyze the convergence of a substructuring iterative method with Lagrange multipliers, proposed recently by Farhat and Roux. The method decomposes finite element discretization of an elliptic boundary value problem into Neumann problems on the subdomains plus a coarse problem for the subdomain nullspace components. For linear conforming elements and preconditioning by the Dirichlet problems on the subdomains, we prove the asymptotic bound on the condition number , or ,where is the characteristic element size and subdomain size. Received January 3, 1995     

A theory of discretization for nonlinear evolution inequalities applied to parabolic Signorini problems

We present a discretization theory for a class of nonlinear evolution inequalities that encompasses time dependent monotone operator equations and parabolic variational inequalities. This discretization theory combines a backward Euler scheme for time discretization and the Galerkin method for space discretization. We include set convergence of convex subsets in the sense of Glowinski-Mosco-Stummel to allow a nonconforming approximation of unilateral constraints. As an application we treat parabolic Signorini problems involving the p-Laplacian, where we use standard piecewise polynomial finite elements for space discretization. Without imposing any regularity assumption for the solution we establish various norm convergence results for piecewise linear as well piecewise quadratic trial functions, which in the latter case leads to a nonconforming approximation scheme. Entrata in Redazione il 16 marzo 1998, in versione riveduta il 15 febbraio 1999.