On the choice of subspace for iterative methods for linear discrete ill-posed problems

Daniela Calvetti; Bryan Lewis; Lothar Reichel

International Journal of Applied Mathematics and Computer Science (2001)

  • Volume: 11, Issue: 5, page 1069-1092
  • ISSN: 1641-876X

Abstract

top
Many iterative methods for the solution of linear discrete ill-posed problems with a large matrix require the computed approximate solutions to be orthogonal to the null space of the matrix. We show that when the desired solution is not smooth, it may be possible to determine meaningful approximate solutions with less computational work by not imposing this orthogonality condition.

How to cite

top

Calvetti, Daniela, Lewis, Bryan, and Reichel, Lothar. "On the choice of subspace for iterative methods for linear discrete ill-posed problems." International Journal of Applied Mathematics and Computer Science 11.5 (2001): 1069-1092. <http://eudml.org/doc/207546>.

@article{Calvetti2001,
abstract = {Many iterative methods for the solution of linear discrete ill-posed problems with a large matrix require the computed approximate solutions to be orthogonal to the null space of the matrix. We show that when the desired solution is not smooth, it may be possible to determine meaningful approximate solutions with less computational work by not imposing this orthogonality condition.},
author = {Calvetti, Daniela, Lewis, Bryan, Reichel, Lothar},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {conjugate gradient method; ill-posed problems; minimal residual method},
language = {eng},
number = {5},
pages = {1069-1092},
title = {On the choice of subspace for iterative methods for linear discrete ill-posed problems},
url = {http://eudml.org/doc/207546},
volume = {11},
year = {2001},
}

TY - JOUR
AU - Calvetti, Daniela
AU - Lewis, Bryan
AU - Reichel, Lothar
TI - On the choice of subspace for iterative methods for linear discrete ill-posed problems
JO - International Journal of Applied Mathematics and Computer Science
PY - 2001
VL - 11
IS - 5
SP - 1069
EP - 1092
AB - Many iterative methods for the solution of linear discrete ill-posed problems with a large matrix require the computed approximate solutions to be orthogonal to the null space of the matrix. We show that when the desired solution is not smooth, it may be possible to determine meaningful approximate solutions with less computational work by not imposing this orthogonality condition.
LA - eng
KW - conjugate gradient method; ill-posed problems; minimal residual method
UR - http://eudml.org/doc/207546
ER -

References

top
  1. Baart M.L. (1982): The use of auto-correlation for pseudo-rank determination in noisy ill-conditioned least-squares problems. - IMA J. Numer. Anal., Vol.2, pp.241-247. Zbl0484.65021
  2. Björck Å. (1996): Numerical Methods for Least Squares Problems. - Philadelphia: SIAM. Zbl0847.65023
  3. Calvetti D., Lewis B. and Reichel L. (2000a): GMRES-type methods for inconsistent systems. - Lin. Alg. Appl., Vol.316, pp.157-169. Zbl0963.65042
  4. Calvetti D., Lewis B. and Reichel L. (2000b): Restoration of images with spatially variant blur by the GMRES method, In: Advanced Signal Processing Algorithms, In: Architectures, and Implementations X (F.T. Luk, Ed.). - Proc. Society of Photo-Optical Instrumentation Engineers (SPIE), Vol.4116, Bellingham, WA: The International Society for Optical Engineering, pp.364-374. 
  5. Calvetti D., Lewis B. and Reichel L. (2000c): An L-curve for the MINRES method, In: Advanced Signal Processing Algorithms, Architectures, and Implementations X (F.T. Luk, Ed.).- Proc. Society of Photo-Optical Instrumentation Engineers (SPIE), Vol.4116, Bellingham, WA: The International Society for Optical Engineering, pp.385-395. 
  6. Calvetti D., Lewis B. and Reichel L. (2002a): GMRES, L-curves,and discrete ill-posed problems. - BIT, Vol.42, pp.44-65. Zbl1003.65040
  7. Calvetti D., Lewis B. and Reichel L. (2002b): On the regularizing properties of the GMRES method. - Numer. Math., (to appear). Zbl1022.65044
  8. Calvetti D., Reichel L. and Zhang Q. (1994a): An adaptive semiiterative method for symmetric semidefinite linear systems, In: Approximation and Computation (R.V.M. Zahar, Ed.). -Basel: Birkhauser, pp.77-96. Zbl0828.65034
  9. Calvetti D., Reichel L. and Zhang Q. (1994b): Conjugate gradient algorithms for symmetric inconsistent linear systems, In: Proceedings of the Cornelius Lanczos International Centenary Conference (J.D. Brown, M.T. Chu, D.C. Ellison and R.J. Plemmons, Eds.).- Philadelphia: SIAM, pp.267-272. 
  10. Calvetti D., Reichel L. and Zhang Q. (1999a): Iterative exponential filtering for large discrete ill-posed problems. - Numer. Math., Vol.83, pp.535-556. Zbl0947.65039
  11. Calvetti D., Reichel L. and Zhang Q. (1999b): Iterative solution methods for large linear discrete ill-posedproblems. - Appl. Comp. Control Signals and Circuits, Vol.1, pp.313-367. Zbl0979.93033
  12. Fischer B. (1996): Polynomial Based Iteration Methods for Symmetric Linear Systems. - New York: Wiley-Teubner. Zbl0852.65031
  13. Hanke M. (1995): Conjugate Gradient Type Methods for Ill-Posed Problems. - Harlow: Longman. Zbl0830.65043
  14. Hanke M. and Hansen P.C. (1993): Regularization methods for large-scale problems. - Surv. Math. Ind., Vol.3, pp.253-315. Zbl0805.65058
  15. Hanke M. and Hochbruck M. (1993): A Chebyshev-like semiiteration for inconsistent linear systems. - Elec. Trans. Numer. Anal., Vol.1, pp.89-103. Zbl0809.65039
  16. Hanke M. and Nagy J.G. (1998): Restoring images degraded by spatially-variant blur. - Inv. Problems, Vol.19, pp.1063-1082. Zbl0919.65091
  17. Hansen P.C. (1994): Regularization tools: A Matlab package for analysis and solution of discrete ill-posed problems. - Numer. Algorithms, Vol.6, pp.1-35. Zbl0789.65029
  18. Hansen P.C. (1998): Rank-Deficient and Discrete Ill-Posed Problems. - Philadelphia: SIAM. 
  19. Nagy J.G. and O'Leary D.P. (1998): Restoring images degraded by spatially-variant blur. - SIAM J. Sci. Comput., Vol.19, pp.1063-1082. Zbl0919.65091
  20. Paige C.C. and Saunders M.A. (1975): Solution of sparse indefinite systems of linear equations. - SIAM J. Numer. Anal., Vol.12, pp.617-629. Zbl0319.65025
  21. Phillips D.L. (1962): A technique for the numerical solution of certain integral equations of the first kind. - J. ACM, Vol.9, pp.84-97. Zbl0108.29902
  22. Saad Y. (1996): Iterative Methods for Sparse Linear Systems. -Boston: PWS. Zbl1031.65047
  23. Saad Y. and Schultz M.H. (1986): GMRES: a generalized minimal residual method for solving nonsymmetric linear systems. - SIAM J. Sci. Stat. Comput., Vol.7, pp.856-869. Zbl0599.65018

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.