Summary
In this paper, the potentials of so-calledlinear semiiterative methods are considered for the approximate solution of linear ill-posed problems and ill conditioned matrix equations. Several efficient two-step methods are presented, most of which have been introduced earlier in the literature. Stipulating certain conditions concerning the smoothness of the solution, a notion of optimal speed of convergence may be formulated. Various direct and converse results are derived to illustrate the properties of this concept.
If the problem's right hand side data are contaminated by noise, semiiterative methods may be used asregularization methods. Assuming optimal rate of convergence of the iteration for the unperturbed problem, the regularized approximations will be of order optimal accuracy.
To derive these results, specific properties of polynomials are used in connection with the basic theory of solving ill-posed problems. Rather recent results onfast decreasing polynomials are applied to answer an open question of Brakhage.
Numerical examples are given including a comparison to the method of conjugate gradients.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Achieser, N.I. (1967): Vorlesungen über Approximationstheorie. Akademie-Verlag, Berlin
Bakushinskii, A.B. (1967): A general method of constructing regularizing algorithms for a linear ill-posed equation in Hilbert space. USSR Comput. Math. Phys.7, 3, 279–287
Björck, Å., Eldén, L. (1979): Methods in numerical algebra for ill-posed problems. Tech. Report LiTH-MAT-R-33-1979, Linköping University, Linköping
Brakhage, H. (1987) On ill-posed problems and the method of conjugate gradients. In: H.W. Engl, C. W. Groetsch, eds., Inverse and Ill-Posed Problems. Academic Press, Boston, New York, London, pp. 165–175
Ditzian, Z., Totik, V. (1987): Moduli of Smoothness. Springer, New York Berlin Heidelberg.
Eicke, B., Louis, A.K., Plato, R. (1990): The instability of some gradient methods for ill-posed problems, Numer. Math.58, 129–134
Eiermann, M., Varga, R.S., Niethammer, W. (1987): Iterationsverfahren für nichtsymmetrische Gleichungssysteme und Approximationsmethoden im Komplexen. Jahresber. Deutsch. Math.-Verein.89, 1–32
Faddeev, D.K., Faddeeva, V.N. (1963): Computational Methods of Linear Algebra. Freeman, San Francisco London
Fridman, V.M. (1956): Method of successive approximations for a Fredholm integral equation of the 1st kind. Uspekhi Mat. Nauk11, 1, 233–234 [in Russian]
Gavurin, M.K., Ryabov, V.M. (1973): Application of Chebyshev polynomials to the regularization of ill-posed and ill-conditioned equations in Hilbert space. USSR Comput. Math. Math. Phys.13, 6, 283–287
Gradshteyn, I.S., Ryzhik, I.M. (1965): Table of Integrals, Series, and Products. Academic Press, New York San Francisco London
Groetsch, C.W. (1975): On existence criteria and approximation procedures for integral equations of the first kind. Math. Comput.29, 1105–1108
Groetsch, C.W. (1977): Generalized Inverses of Linear Operators. Dekker, New York Basel
Groetsch, C.W. (1984): The Theory of Tikhonov Regularization for Fredholm Equations of the First Kind. Pitman, Boston London Melbourne
Hanke, M., Niethammer, W. (1990): On the acceleration of Kaczmarz's method for inconsistent linear systems. Linear Algebra Appl.130, 83–98
Hansen, P.C. (1990): The discrete Picard condition for discrete ill-posed problems. BIT30, 658–672
Ivanov, K.G., Totik, V. (1990): Fast decreasing polynomials, Constr. Approx.6, 1–20
Kress, R. (1989): Linear Integral Equations. Springer, Berlin Heidelberg New York
Landweber, L. (1951): An iteration, formula for Fredholm integral equations of the first kind. Amer. J. Math.73, 615–624
Lorentz, G.G. (1966): Approximation of Functions. Holt, Rinehart and Winston, New York Chicago San Francisco
Louis, A. K. (1987): Convergence of the conjugate gradient method for compact operators. In: H. W. Engl, C. W. Groetsch, eds., Inverse and Ill-Posed Problems. Academic Press, Boston New York London, pp. 177–183
Louis, A.K. (1989). Inverse und schlecht gestellte Probleme. Teubner, Stuttgart
Lubinsky, D.S., Saff, E.B. (1989): Szegö asymptotics for non-Szegö weights on [−1,1]. In: C.K. Chui, L.L. Schumaker, J.D. Wards, eds., Approximation Theory VI, Vol. 2. Academic Press, Boston New York London, pp. 409–412
Morozov, V.A. (1966): On the solution of functional equations by the method of regularization. Soviet Math. Dokl.7, 414–417
Natterer, F. (1986): The Mathematics of Computerized Tomography. Wiley, Chichester New York Brisbane
Nemirovskii, A.S. (1986): The regularizing properties of the adjoint gradient method in ill-posed problems. USSR Comput. Math. Math. Phys.,26, 2, 7–16
Nemirovskii, A.S., Polyak, B.T. (1984): Iterative methods for solving linear ill-posed problems under precise information, I. Engrg. Cybernetics22, 3, 1–11
Nemirovskii, A.S., Polyak, B.T. (1984): Iterative methods for solving linear ill-posed problems under precise information. II, Engrg. Cybernetics22, 4, 50–56
Nevai, P.G. (1979): Orthogonal Polynomials. Mem. Amer. Math. Soc., Vol. 213. Amer. Math. Soc., Providence, Rhode Island
Nevai, P.G., Totik, V. (1986): Weighted polynomial inequalities, Constr. Approx.2, 113–127
Plato, R. (1990): Optimal algorithms for linear ill-posed problems yield regularization methods. Numer. Funct. Anal. Optim.11, 111–118
Potapov, M.K. (1983): Approximation by algebraic polynomials in an integral metric with Jacobi weight. Moscow Univ. Math. Bull.38, 4, 48–57
Richardson, L.F. (1910): The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam. Philos. Trans. Roy. Soc. London Ser. A,210, 307–357
Schock, E. (1985): Approximate solution of ill-posed equations: Arbitrarily slow convergence vs. superconvergence. In: G. Hämmerlin, K.-H. Hoffmann, eds., Constructive Methods for the Practical Treatment of Integral Equations. Birkhäuser, Basel Boston Stuttgart, pp. 234–243
Schock, E. (1987): Semi-iterative methods for the approximate solution of ill-posed problems. Numer. Math.50, 263–271
Schock, E. (1988): Pointwise rational approximation and iterative methods for ill-posed problems. Numer. Math.54, 91–103
Stiefel, E. (1955): Relaxationsmethoden bester Strategie zur Lösung linearer Gleichungssysteme. Comment. Math. Helv.29, 157–179
Strand, O.N. (1974): Theory and methods related to the singular-function expansion and Landweber's iteration for integral equations of the first kind. SIAM J. Numer. Anal.11, 798–825
Szegö, G. (1967): Orthogonal Polynomials. Amer. Math. Soc. Colloq. Publ., Vol. 23. Amer. Math. Soc., Providence, Rhode Island
Tikhonov, A.N., Arsenin, V.Y. (1977): Solutions of Ill-Posed Problems. Wiley, New York Toronto London
Vainikko, G.M. (1980): Error estimates of the successive approximation method for ill-posed problems. Automat. Remote Control,40, 356–363
Vainikko, G.M. (1982): The discrepancy principle for a class of regularization methods. USSR Comput. Math. Math. Phys.22, 3, 1–19
Vainikko, G.M. (1983): The critical level of discrepancy, in regularization methods. USSR Comput. Math. Math. Phys.22, 6, 1–9
Vainikko, G.M., Veretennikov, A.Y. (1986): Iteration Procedures in Ill-Posed Problems. Nauka, Moscow [in Russian]
Van Der Sluis, A., Van Der Vorst, H.A. (1990): SIRT- and CG-type methods for the iterative solution of sparse linear least squares problems. Linear Algebra Appl.130, 257–303
Varah, J.M. (1979): A practical examination of some numerical methods for linear discrete ill-posed problems. SIAM Rev.21, 100–111
Varga, R.S. (1962): Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, NJ
Author information
Authors and Affiliations
Additional information
This research was sponsored by the Deutsche Forschungsgemeinschaft (DFG).