A posteriori parameter choice strategies for some Newton type methods for the regularization of nonlinearill-posed problems

This paper treats a class of Newton type methods for the approximate solution of nonlinear ill-posed operator equations, that use so-called filter functions for regularizing the linearized equation in each Newton step. For noisy data we derive an aposteriori stopping rule that yields convergence of the iterates to asolution, as the noise level goes to zero, under certain smoothness conditions on the nonlinear operator. Appropriate closeness and smoothness assumptions on the starting value and the solution are shown to lead to optimal convergence rates. Moreover we present an application of the Newton type methods under consideration to a parameter identification problem, together with some numerical results. Received November 29, 1996 / Revised version received April 25, 1997     

A convergence analysis of the Landweber iteration for nonlinear ill-posed problems

Summary. In this paper we prove that the Landweber iteration is a stable method for solving nonlinear ill-posed problems. For perturbed data with noise level we propose a stopping rule that yields the convergence rate ) under appropriate conditions. We illustrate these conditions for a few examples. Received February 15, 1993 / Revised version received August 2, 1994     

On an a posteriori parameter choice strategy for Tikhonov regularization of nonlinear ill-posed problems

Summary. In the study of the choice of the regularization parameter for Tikhonov regularization of nonlinear ill-posed problems, Scherzer, Engl and Kunisch proposed an a posteriori strategy in 1993. To prove the optimality of the strategy, they imposed many very restrictive conditions on the problem under consideration. Their results are difficult to apply to concrete problems since one can not make sure whether their assumptions are valid. In this paper we give a further study on this strategy, and show that Tikhonov regularization is order optimal for each with the regularization parameter chosen according to this strategy under some simple and easy-checking assumptions. This paper weakens the conditions needed in the existing results, and provides a theoretical guidance to numerical experiments. Received August 8, 1997 / Revised version received January 26, 1998     

Superlinear convergence rates for the Lanczos method applied to elliptic operators

Summary. This paper investigates the convergence of the Lanczos method for computing the smallest eigenpair of a selfadjoint elliptic differential operator via inverse iteration (without shifts). Superlinear convergence rates are established, and their sharpness is investigated for a simple model problem. These results are illustrated numerically for a more difficult problem. Received March 8, 1996     

On the convergence of multipoint iterations

Summary. This note gives a new convergence proof for iterations based on multipoint formulas. It rests on the very general assumption that if the desired fixed point appears as an argument in the formula then the formula returns the fixed point. Received March 24, 1993 / Revised version received January 1994     

The approximation of generalized turning points\newline by Krylov subspace methods

Summary. Certain types of singular solutions of nonlinear parameter-dependent operator equations were characterized by Griewank and Reddien [5, 6] as regular solutions of suitable augmented systems. For their numerical approximation an approach based on the use of Krylov subspaces is here presented. The application to boundary value problems is illustrated by numerical examples. Received March 8, 1993 / Revised version received December 13, 1993     

On Landweber iteration for nonlinear ill-posed problems in Hilbert scales

Summary. In this paper we derive convergence rates results for Landweber iteration in Hilbert scales in terms of the iteration index for exact data and in terms of the noise level for perturbed data. These results improve the one obtained recently for Landweber iteration for nonlinear ill-posed problems in Hilbert spaces. For numerical computations we have to approximate the nonlinear operator and the infinite-dimensional spaces by finite-dimensional ones. We also give a convergence analysis for this finite-dimensional approximation. The conditions needed to obtain the rates are illustrated for a nonlinear Hammerstein integral equation. Numerical results are presented confirming the theoretical ones. Received May 15, 1998 / Revised version received January 29, 1999 / Published online December 6, 1999     

On the convergence of a dual-primal substructuring method

Summary.   In the Dual-Primal FETI method, introduced by Farhat et al. [5], the domain is decomposed into non-overlapping subdomains, but the degrees of freedom on crosspoints remain common to all subdomains adjacent to the crosspoint. The continuity of the remaining degrees of freedom on subdomain interfaces is enforced by Lagrange multipliers and all degrees of freedom are eliminated. The resulting dual problem is solved by preconditioned conjugate gradients. We give an algebraic bound on the condition number, assuming only a single inequality in discrete norms, and use the algebraic bound to show that the condition number is bounded by for both second and fourth order elliptic selfadjoint problems discretized by conforming finite elements, as well as for a wide class of finite elements for the Reissner-Mindlin plate model. Received January 20, 2000 / Revised version received April 25, 2000 / Published online December 19, 2000     

Using the L--curve for determining optimal regularization parameters

Summary. The ``L--curve' is a plot (in ordinary or doubly--logarithmic scale) of the norm of (Tikhonov--) regularized solutions of an ill--posed problem versus the norm of the residuals. We show that the popular criterion of choosing the parameter corresponding to the point with maximal curvature of the L--curve does not yield a convergent regularization strategy to solve the ill--posed problem. Nevertheless, the L--curve can be used to compute the regularization parameters produced by Morozov's discrepancy principle and by an order--optimal variant of the discrepancy principle proposed by Engl and Gfrerer in an alternate way. Received June 29, 1993 / Revised version received February 2, 1994     

On the convergence of the Newton/log-barrier method

In the Newton/log-barrier method, Newton steps are taken for the log-barrier function for a fixed value of the barrier parameter until a certain convergence criterion is satisfied. The barrier parameter is then decreased and the Newton process is repeated. A naive analysis indicates that Newton’s method does not exhibit superlinear convergence to the minimizer of each instance of the log-barrier function until it reaches a very small neighborhood, namely within O(μ²) of the minimizer, where μ is the barrier parameter. By analyzing the structure of the barrier Hessian and gradient in terms of the subspace of active constraint gradients and the associated null space, we show that this neighborhood is in fact much larger –O(μ^σ) for any σ∈(1,2] – thus explaining why reasonably fast local convergence can be attained in practice. Moreover, we show that the overall convergence rate of the Newton/log-barrier algorithm is superlinear in the number of function/derivative evaluations, provided that the nonlinear program is formulated with a linear objective and that the schedule for decreasing the barrier parameter is related in a certain way to the step length and convergence criteria for each Newton process. Received: October 10, 1997 / Accepted: September 10, 2000?Published online February 22, 2001     

On the discrepancy principle for iterative and parametric methods to solve linear ill-posed equations

Summary. For the numerical solution of (non-necessarily well-posed) linear equations in Banach spaces we consider a class of iterative methods which contains well-known methods like the Richardson iteration, if the associated resolvent operator fulfils a condition with respect to a sector. It is the purpose of this paper to show that for given noisy right-hand side the discrepancy principle (being a stopping rule for the iteration methods belonging to the mentioned class) defines a regularization method, and convergence rates are proved under additional smoothness conditions on the initial error. This extends similar results obtained for positive semidefinite problems in Hilbert spaces. Then we consider a class of parametric methods which under the same resolvent condition contains the method of the abstract Cauchy problem, and (under a weaker resolvent condition) the iterated method of Lavrentiev. A modified discrepancy principle is formulated for them, and finally numerical illustrations are presented. Received August 29, 1994 / Revised version received September 19, 1995     

Quadratic convergence of scaled matrices in Jacobi method

Summary. A quadratic convergence bound for scaled Jacobi iterates is proved provided the initial symmetric positive definite matrix has simple eigenvalues. The bound is expressed in terms of the off-norm of the scaled initial matrix and the minimum relative gap in the spectrum. The obtained result can be used to predict the stopping moment in the two-sided and especially in the one-sided Jacobi method. Received October 31, 1997 / Revised version received March 8, 1999 / Published online July 12, 2000     

On constrained Newton linearization and multigrid for variational inequalities

Summary. We consider the fast solution of a class of large, piecewise smooth minimization problems. For lack of smoothness, usual Newton multigrid methods cannot be applied. We propose a new approach based on a combination of convex minization with constrained Newton linearization. No regularization is involved. We show global convergence of the resulting monotone multigrid methods and give polylogarithmic upper bounds for the asymptotic convergence rates. Efficiency is illustrated by numerical experiments. Received March 22, 1999 / Revised version received February 24, 2001 / Published online October 17, 2001     

On the convergence of line iterative methods for cyclically reduced non-symmetrizable linear systems

Summary. We derive analytic bounds on the convergence factors associated with block relaxation methods for solving the discrete two-dimensional convection-diffusion equation. The analysis applies to the reduced systems derived when one step of block Gaussian elimination is performed on red-black ordered two-cyclic discretizations. We consider the case where centered finite difference discretization is used and one cell Reynolds number is less than one in absolute value and the other is greater than one. It is shown that line ordered relaxation exhibits very fast rates of convergence. Received March 3, 1992/Revised version received July 2, 1993     

On worst-case condition numbers of a nondefective multiple eigenvalue

Summary. This paper is a continuation of the author [6] in Numerische Mathematik. Let be a nondefective multiple eigenvalue of multiplicity of an complex matrix , and let be the secants of the canonical angles between the left and right invariant subspaces of corresponding to the multiple eigenvalue . The analysis of this paper shows that the quantities are the worst-case condition numbers of the multiple eigenvalue . Received September 28, 1992 / Revised version received January 18, 1994     

Stability and error estimates for the $\theta$-method for strongly monotone and infinitely stiff evolution equations

Summary.   For evolution equations with a strongly monotone operator we derive unconditional stability and discretization error estimates valid for all . For the -method, with , we prove an error estimate , if , where is the maximal integration step for an arbitrary choice of sequence of steps and with no assumptions about the existence of the Jacobian as well as other derivatives of the operator , and an optimal estimate under some additional relation between neighboring steps. The first result is an improvement over the implicit midpoint method , for which an order reduction to sometimes may occur for infinitely stiff problems. Numerical tests illustrate the results. Received March 10, 1999 / Revised version received April 3, 2000 / Published online February 5, 2001     

On the asymptotic stability properties of Runge-Kutta methods for delay differential equations

Summary. In this paper asymptotic stability properties of Runge-Kutta (R-K) methods for delay differential equations (DDEs) are considered with respect to the following test equation: where and is a continuous real-valued function. In the last few years, stability properties of R-K methods applied to DDEs have been studied by numerous authors who have considered regions of asymptotic stability for “any positive delay” (and thus independent of the specific value of ). In this work we direct attention at the dependence of stability regions on a fixed delay . In particular, natural Runge-Kutta methods for DDEs are extensively examined. Received April 15, 1996 / Revised version received August 8, 1996     

The convergence rate of the minimal residual method for the Stokes problem

Summary. Discretisation of the classical Stokes problem gives rise to symmetric indefinite matrices with eigenvalues which, in a precise way, are not symmetric about the origin, but which do depend on a mesh size parameter. Convergence estimates for the Conjugate Residual or Minimum Residual iterative solution of such systems are given by best minimax polynomial approximations on an inclusion set for the eigenvalues. In this paper, an analytic convergence estimate for such problems is given in terms of an asymptotically small mesh size parameter. Received November 16, 1993 / Revised version received August 2, 1994     

An iterative multi level algorithm for solving nonlinear ill–posed problems

Summary. The convergence analysis of Landweber's iteration for the solution of nonlinear ill–posed problem has been developed recently by Hanke, Neubauer and Scherzer. In concrete applications, sufficient conditions for convergence of the Landweber iterates developed there (although quite natural) turned out to be complicated to verify analytically. However, in numerical realizations, when discretizations are considered, sufficient conditions for local convergence can usually easily be stated. This paper is motivated by these observations: Initially a discretization is fixed and a discrete Landweber iteration is implemented until an appropriate stopping criterion becomes active. The output is used as an initial guess for a finer discretization. An advantage of this method is that the convergence analysis can be considered in a family of finite dimensional spaces. The numerical performance of this multi level algorithm is compared with Landweber's iteration. Received October 21, 1996 / Revised version received July 28, 1997     

On the convergence of finite difference schemes for the heat equation with concentrated capacity

Summary. We investigate the convergence of difference schemes for the one-dimensional heat equation when the coefficient at the time derivative (heat capacity) is represents the magnitude of the heat capacity concentrated at the point . An abstract operator method is developed for analyzing this equation. Estimates for the rate of convergence in special discrete energetic Sobolev's norms, compatible with the smoothness of the solution are obtained. Received November 2, 1999 / Revised version received July 24, 2000 / Published online May 4, 2001