CGLS a LSQR jsou matematicky ekvivalentní algoritmy pro řešení systému normálních rovnic. Na CGLS lze nahlížet jako na vhodně upravenou verzi metody sdružených gradientů aplikovanou na systém normálních rovnic. Algoritmus LSQR je založen na Golub-Kahanově bidiagonalizaci a na následné konstrukci aproximace řešení pomocí řešení problému nejmenších čtverců s bidiagonální maticí. Cílem práce je nejprve ukázat vztahy mezi vektory a koeficienty obou algoritmů a následně provést srovnání jejich numerického chování. Numerické experimenty se zaměří například na porovnání ztráty ortogonality, zpoždění konvergence, či hladiny limitní přesnosti.
Seznam odborné literatury
Å. Björck, T. Elfving, and Z. Strakoš, Stability of conjugate gradient and Lanczos methods for linear least squares problems, SIAM J. Matrix Anal. Appl. 19, 720-736, 1998.
J. Duintjer Tebbens, I. Hnětynková, M. Plešinger, Z. Strakoš, and P. Tichý, Analýza metod pro maticové výpočty - Základnı́ metody, matfyzpress, Praha, 2012.
C.C. Paige and M. A. Saunders, LSQR: an algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software 8, 43-71, 1982.
Y. Saad, Iterative methods for sparse linear systems, Society for Industrial and Applied Mathematics, xviii+528, 2003.
Předběžná náplň práce
CGLS a LSQR jsou matematicky ekvivalentní algoritmy pro řešení systému normálních rovnic. Na CGLS lze nahlížet jako na vhodně upravenou verzi metody sdružených gradientů aplikovanou na systém normálních rovnic. Algoritmus LSQR je založen na Golub-Kahanově bidiagonalizaci a na následné konstrukci aproximace řešení pomocí řešení problému nejmenších čtverců s bidiagonální maticí. Cílem práce je nejprve ukázat vztahy mezi vektory a koeficienty obou algoritmů a následně provést srovnání jejich numerického chování. Numerické experimenty se zaměří například na porovnání ztráty ortogonality, zpoždění konvergence, či hladiny limitní přesnosti.
Předběžná náplň práce v anglickém jazyce
CGLS and LSQR are mathematically equivalent algorithms for solving a system of normal equations. CGLS can be viewed as a suitably modified version of the conjugate gradient method applied to a system of normal equations. The LSQR algorithm is based on Golub-Kahan bidiagonalisation and the subsequent construction of an approximate solution by solving a least squares problem with a bidiagonal matrix. The goal of the thesis is first to show the relationships between the vectors and coefficients of the two algorithms and then to compare their numerical behavior. The numerical experiments will focus, for example, on comparing the loss of orthogonality, the delay of convergence, or the level of maximum attainable accuracy.
- zadáno a potvrzeno stud. odd.