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     

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     

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     

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     

On convergence rates of inexact Newton regularizations

Summary. REGINN is an algorithm of inexact Newton type for the regularization of nonlinear ill-posed problems [Inverse Problems 15 (1999), pp. 309–327]. In the present article convergence is shown under weak smoothness assumptions (source conditions). Moreover, convergence rates are established. Some computational illustrations support the theoretical results. Received March 12, 1999 / Published online October 16, 2000     

A wavelet multilevel method for ill-posed problems stabilized by Tikhonov regularization

Summary. An additive Schwarz iteration is described for the fast resolution of linear ill-posed problems which are stabilized by Tikhonov regularization. The algorithm and its analysis are presented in a general framework which applies to integral equations of the first kind discretized either by spline functions or Daubechies wavelets. Numerical experiments are reported on to illustrate the theoretical results and to compare both discretization schemes. Received March 6, 1995 / Revised version received December 27, 1995     

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     

A note on the pivoted symmetric LR iteration

Summary. We prove that the diagonally pivoted symmetric LR algorithm on a positive definite matrix is globally convergent. Received December 23, 1997 / Revised version received August 3, 1998 / Published online August 19, 1999     

Iterative exponential filtering for large discrete ill-posed problems

Summary. We describe a new iterative method for the solution of large, very ill-conditioned linear systems of equations that arise when discretizing linear ill-posed problems. The right-hand side vector represents the given data and is assumed to be contaminated by measurement errors. Our method applies a filter function of the form with the purpose of reducing the influence of the errors in the right-hand side vector on the computed approximate solution of the linear system. Here is a regularization parameter. The iterative method is derived by expanding in terms of Chebyshev polynomials. The method requires only little computer memory and is well suited for the solution of large-scale problems. We also show how a value of and an associated approximate solution that satisfies the Morozov discrepancy principle can be computed efficiently. An application to image restoration illustrates the performance of the method. Received January 25, 1997 / Revised version received February 9, 1998 / Published online July 28, 1999     

The rate of convergence of Toeplitz based PCG methods for second order nonlinear boundary value problems

Summary. In previous works [21–23] we proposed the use of [5] and band Toeplitz based preconditioners for the solution of 1D and 2D boundary value problems (BVP) by means of the preconditioned conjugate gradient (PCG) methods. As and band Toeplitz linear systems can be solved [4] by using fast sine transforms [8], these methods become especially attractive in a parallel environment of computation. In this paper we extend this technique to the nonlinear, nonsymmetric case and, in addition, we prove some clustering properties for the spectra of the preconditioned matrices showing why these methods exhibit a convergence speed which results to be more than linear. Therefore these methods work much finer than those based on separable preconditioners [18,45], on incomplete LU factorizations [36,13,27], and on circulant preconditioners [9,30,35] since the latter two techniques do not assure a linear rate of convergence. On the other hand, the proposed technique has a wider range of application since it can be naturally used for nonlinear, nonsymmetric problems and for BVP in which the coefficients of the differential operator are not strictly positive and only piecewise smooth. Finally the several numerical experiments performed here and in [22,23] confirm the effectiveness of the theoretical analysis. Received December 19, 1995 / Revised version received September 15, 1997     

Tangent Graeffe iteration

Summary.   Graeffe iteration was the choice algorithm for solving univariate polynomials in the XIX-th and early XX-th century. In this paper, a new variation of Graeffe iteration is given, suitable to IEEE floating-point arithmetics of modern digital computers. We prove that under a certain generic assumption the proposed algorithm converges. We also estimate the error after N iterations and the running cost. The main ideas from which this algorithm is built are: classical Graeffe iteration and Newton Diagrams, changes of scale (renormalization), and replacement of a difference technique by a differentiation one. The algorithm was implemented successfully and a number of numerical experiments are displayed. Received May 29, 1998 / Revised version received September 13, 1999 / Published online April 5, 2001     

A posteriori error estimation with the finite element method of lines for a nonlinear parabolic equation in one space dimension

Summary. Convergence of a posteriori error estimates to the true error for the semidiscrete finite element method of lines is shown for a nonlinear parabolic initial-boundary value problem. Received June 15, 1997 / Revised version received May 15, 1998 / Published online: June 29, 1999     

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     

Finite dimensional approximation of two-parameter nonlinear problems

Summary. In this paper we study a general theory for the numerical approximation of functional nonlinear two-parameter problems in a neighbourhood of an isola center. The results are also valid for a certain class of perturbed bifurcation points. The abstract theory is applied to the Galerkin approximation of nonlinear variational posed problems. In this case, as a consequence of the error being orthogonal to the approximating space, we prove the superconvergence of the perturbation parameter, whereas for the bifurcation parameter and the solution we obtain the same order as in the linear problem. Numerical results are given for the one-dimensional Brussellator model. Received June 10, 1992 / Revised version received May 16, 1994     

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 Halley iteration

This paper proposes some modified Halley iterations for finding the zeros of polynomials. We investigate the non-overshoot properties of the modified Halley iterations and other important properties that play key roles in solving symmetric eigenproblems. We also extend Halley iteration to systems of polynomial equations in several variables. Received March 20, 1996 / Revised version received December 5, 1997     

A New Third-Order Iterative Processfor Solving Nonlinear Equations

 In this paper, we build up a modification of the Midpoint method, reducing its operational cost without losing its cubical convergence. Then we obtain a semilocal convergence result for this new iterative process and by means of several examples we compare it with other iterative processes. (Received 11 April 2000; in final form 27 March 2001)     

An inexactQP-based method for nonlinear complementarity problems

Summary. We consider a quadratic programming-based method for nonlinear complementarity problems which allows inexact solutions of the quadratic subproblems. The main features of this method are that all iterates stay in the feasible set and that the method has some strong global and local convergence properties. Numerical results for all complementarity problems from the MCPLIB test problem collection are also reported. Received February 24, 1997 / Revised version received September 5, 1997     

A posteriori error estimates for optimal control problems governed by parabolic equations

Summary. In this paper, we derive a posteriori error estimates for the finite element approximation of quadratic optimal control problem governed by linear parabolic equation. We obtain a posteriori error estimates for both the state and the control approximation. Such estimates, which are apparently not available in the literature, are an important step towards developing reliable adaptive finite element approximation schemes for the control problem. Received July 7, 2000 / Revised version received January 22, 2001 / Published online January 30, 2002 RID="*" ID="*" Supported by EPSRC research grant GR/R31980