Conjugate Gradients and Conjugate Residuals type methods for solving Least Squares problems from Tomography

This research investigates iterative methods for solving large and sparse least squares problems, as those encountered in tomography. A widely used method for such systems is the Conjugate Gradients method for Least Squares problems (CGLS), which is derived from the popular Conjugate Gradient method. The Conjugate Residuals method can also be adapted for Least Squares problems, which would lead to the Conjugate Residual Least Square method (CRLS). Such a method seems to be unknown. In this thesis we derive the method of Conjugate Residuals for the Least Square problem and compare it to other iterative methods like Conjugate Gradients, Conjugate Gradients for the Least Square problem, Conjugate Residuals, Least Square Minimal Residual (LSMR) and Least Square QR-factorization (LSQR). Also a non-iterative method, the Singular Value Decomposition (SVD) is tested and compared to this iterative methods. A test problem that provides ill conditioned problems is used to test the accuracy of the methods. It can be concluded that CRLS behaves significantly worse with this test problem than the methods SVD, CGLS, LSQR and LSMR, if it is implemented in its most time efficient way. Its accuracy is comparable to the methods CG and CR. If the implementation is altered the accuracy improves up to the level of the other algorithms, but this implementation requires an extra matrix multiplication. This means the investigated method can achieve high accuracy, but may require more time and memory while computing a solution. In the application of the discussed algorithms on a representative geophysical test problem the accuracy problem of CRLS cannot be detected. Even the time-efficient implementation does not result in loss of accuracy in comparison with CGLS in this test problem. After adding perturbation to the measured data of this problem, it is clear that CRLS is also in this area comparable to CGLS.

Subject

conjugate gradients
conjugate residuals
tomography

To reference this document use:

http://resolver.tudelft.nl/uuid:05a0181b-dd14-4915-b2b4-a6344aea03af

Part of collection

Student theses

Document type

bachelor thesis

Rights

Files

PDF

report_Tamara_Kloek_final.pdf

1.1 MB

Close viewer