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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
B. C. Cook,Least Structure Solution of Photonuclear Yield Functions, Nuclear Instruments and Methods 24 (1963), pp. 256–268.
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.
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.
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.
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.
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.
G. H. Golub,Some Modified Eigenvalue Problems, SIAM Review 15 (1973), pp. 318–334.
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.
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.
V. K. Ivanov,On Linear Problems which are not Well-Posed, Dokl. Akad. Nauk SSSR 145 (1962), pp. 270–272.
L. S. Jennings,Orthogonal Transformations and Improperly Posed Problems, Thesis, Australian National University, 1973.
N. Köckler,Parameterwahl und Fehlerabschätzung bei der regularisierten Lösung von inkorrekt gestellten Problemen, Dissertation, Johannes Gutenberg-Universität, Mainz, 1974.
C. L. Lawson and R. J. Hanson,Solving Least Squares Problems, Prentice-Hall, Englewood Cliffs, 1974.
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.
D. L. Phillips,A Technique for the Numerical Solution of Certain Integral Equations of the First Kind, J. ACM 9 (1962), pp. 84–97.
C. H. Reinsch,Smoothing by Spline Functions, Numer. Math. 16 (1971), pp. 451–454.
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.
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.
C. F. Van Loan,Generalizing the Singular Value Decomposition, SIAM J. Numer. Anal. 13 (1976), pp. 76–83.
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.
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.
G. Wahba,Convergence Rates of Certain Approximate Solutions to Fredholm Integral Equations of the First Kind, J. Appr. Theory 8 (1973), pp. 167–185.
G. Wahba,Practical Approximate Solutions to Linear Operator Equations when the Data are Noisy, SIAM J. Numer. Anal., to appear.
J. H. Wilkinson and C. H. Reinsch,Handbook for Automatic Computation, Vol. II,Linear Algebra, Springer-Verlag, Berlin, 1971.
Author information
Authors and Affiliations
Rights 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
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01932285