Skip to main content
SpringerLink
Log in

Algorithms for the regularization of ill-conditioned least squares problems

  • Published:
BIT Numerical Mathematics Aims and scope Submit manuscript

Abstract

Two regularization methods for ill-conditioned least squares problems are studied from the point of view of numerical efficiency. The regularization methods are formulated as quadratically constrained least squares problems, and it is shown that if they are transformed into a certain standard form, very efficient algorithms can be used for their solution. New algorithms are given, both for the transformation and for the regularization methods in standard form. A comparison to previous algorithms is made and it is shown that the overall efficiency (in terms of the number of arithmetic operations) of the new algorithms is better.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. B. C. Cook,Least Structure Solution of Photonuclear Yield Functions, Nuclear Instruments and Methods 24 (1963), pp. 256–268.

    Google Scholar 

  2. L. Eldén,Numerical Methods for the Regularization of Fredholm Integral Equations of the First Kind, Report LiH-MAT-R-1974-7, Dept. of Mathematics, Linköping University, 1974.

  3. L. Eldén,A Note on Weighted Pseudoinverses with Application to the Regularization of Fredholm Integral Equations of the First Kind, Report LiTH-MAT-R-75-11, 1975, Dept. of Mathematics, Linköping University.

  4. L. Eldén,A Program for Interactive Regularization, Part I: Implementation of Numerical Algorithms, to appear as a Linköping University, Dept. of Mathematics report.

  5. L. Eldén,A Program for Interactive Regularization, Part II: Interaction and File Handling, to appear as a Linköping University, Dept. of Mathematics report.

  6. G. H. Golub and V. Pereyra,The Differentiation of Pseudo-Inverses and Nonlinear Least Squares Problems Whose Variables Separate, SIAM J. Numer. Anal. 10 (1973) pp. 413–432.

    Google Scholar 

  7. G. H. Golub,Some Modified Eigenvalue Problems, SIAM Review 15 (1973), pp. 318–334.

    Google Scholar 

  8. V. I. Gordonova and V. A. Morozov,Numerical Algorithms for Parameter Choice in the Regularization Method, Zh. Vychisl. Mat. Mat. Fiz. 13 (1973), pp. 539–545.

    Google Scholar 

  9. R. J. Hanson and J. L. Phillips,An Adaptive Numerical Method for Solving Linear Fredholm Integral Equations of the First Kind, Numer. Math. 24 (1975), pp. 291–307.

    Google Scholar 

  10. V. K. Ivanov,On Linear Problems which are not Well-Posed, Dokl. Akad. Nauk SSSR 145 (1962), pp. 270–272.

    Google Scholar 

  11. L. S. Jennings,Orthogonal Transformations and Improperly Posed Problems, Thesis, Australian National University, 1973.

  12. N. Köckler,Parameterwahl und Fehlerabschätzung bei der regularisierten Lösung von inkorrekt gestellten Problemen, Dissertation, Johannes Gutenberg-Universität, Mainz, 1974.

    Google Scholar 

  13. C. L. Lawson and R. J. Hanson,Solving Least Squares Problems, Prentice-Hall, Englewood Cliffs, 1974.

    Google Scholar 

  14. M. Z. Nashed,On Moment Discretization and Least Squares Solutions of Linear Integral Equations of the First Kind, J. Math. Anal. Appl. 53 (1976), pp. 359–366.

    Google Scholar 

  15. D. L. Phillips,A Technique for the Numerical Solution of Certain Integral Equations of the First Kind, J. ACM 9 (1962), pp. 84–97.

    Google Scholar 

  16. C. H. Reinsch,Smoothing by Spline Functions, Numer. Math. 16 (1971), pp. 451–454.

    Google Scholar 

  17. A. N. Tihonov,Solution of Incorrectly Formulated Problems and the Regularization Method, Dokl. Akad, Nauk SSSR 151 (1963), pp. 501–504 = Soviet Math. Dokl. 4 (1963), pp. 1035–1038.

    Google Scholar 

  18. A. N. Tihonov,Regularization of Incorrectly Posed Problems, Dokl. Akad. Nauk SSSR 153 (1963), pp. 49–52 = Soviet Math. Dokl. 4 (1963), pp. 1624–1627.

    Google Scholar 

  19. C. F. Van Loan,Generalizing the Singular Value Decomposition, SIAM J. Numer. Anal. 13 (1976), pp. 76–83.

    Google Scholar 

  20. J. M. Varah,A Practical Examination of Some Numerical Methods for Linear Discrete Ill-Posed Problems, Technical Report 76-08, Dept. of Computer Science, University of British Columbia, Vancouver, 1976.

    Google Scholar 

  21. V. V. Voevodin,The Method of Regularization, Zh. Vychisl. Mat. Mat. Fiz. 9 (1969), pp. 673–675 = USSR Comp. Math. Math. Phys. 9 (1969), pp. 228–232.

    Google Scholar 

  22. G. Wahba,Convergence Rates of Certain Approximate Solutions to Fredholm Integral Equations of the First Kind, J. Appr. Theory 8 (1973), pp. 167–185.

    Google Scholar 

  23. G. Wahba,Practical Approximate Solutions to Linear Operator Equations when the Data are Noisy, SIAM J. Numer. Anal., to appear.

  24. J. H. Wilkinson and C. H. Reinsch,Handbook for Automatic Computation, Vol. II,Linear Algebra, Springer-Verlag, Berlin, 1971.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Linköping University, S-581 83, Linköping, Sweden

    Lars Eldén

Authors
  1. Lars Eldén
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Eldén, L. Algorithms for the regularization of ill-conditioned least squares problems. BIT 17, 134–145 (1977). https://doi.org/10.1007/BF01932285

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01932285

Keywords

Search

Navigation