Cílem práce je shrnutí poznatků o chování metody sdružených gradientů v konečné aritmetice počítače a provedení řady numerických experimentů. Budou zkoumány problémy spojené s matematickým modelem výpočtů CG v konečné aritmetice.
Annotation in English
The goal is to summarize knowledge about the behavior of the conjugate gradient method in finite precision arithmetic, performing numerical experiments, and investigation of some problems connected with the mathematical model of finite precision CG computations.
Keywords
metoda sdružených gradientů, Gaussova kvadratura, Lanczosův algoritmus, konečná aritmetika počítače, ztráta ortogonality, zpoždění konvergence, maximální dosažitelná přesnost
Keywords in English
Conjugate Gradient method, Gauss-quadrature, Lanczos algorithm, finite precision arithmetic, loss of orthogonality, delay of convergence, ultimate attainable accuracy
Length of the covering note
vii s., 53 s.
Language
CZ
Annotation
Cílem práce je shrnutí poznatků o chování metody sdružených gradientů v konečné aritmetice počítače a provedení řady numerických experimentů. Budou zkoumány problémy spojené s matematickým modelem výpočtů CG v konečné aritmetice.
Annotation in English
The goal is to summarize knowledge about the behavior of the conjugate gradient method in finite precision arithmetic, performing numerical experiments, and investigation of some problems connected with the mathematical model of finite precision CG computations.
Keywords
metoda sdružených gradientů, Gaussova kvadratura, Lanczosův algoritmus, konečná aritmetika počítače, ztráta ortogonality, zpoždění konvergence, maximální dosažitelná přesnost
Keywords in English
Conjugate Gradient method, Gauss-quadrature, Lanczos algorithm, finite precision arithmetic, loss of orthogonality, delay of convergence, ultimate attainable accuracy
Research Plan
Pro proniknutí do problematiky tématu nastudovat uvedenou literaturu a aktuální články.
Formulovat matematické vlastnosti metody sdružených gradientů.
Popsat a numericky demonstrovat základní jevy k nimž dochází u metody sdružených gradientů (CG) vlivem konečné aritmetiky počítače.
Seznámit se s teorií A. Greenbauma a Z. Strakoše, podle níž je možné hledět na výpočty CG v konečné aritmetice jako na výpočty přesné CG aplikované na jiný systém lineárních algebraických rovnic.
V systému MATLAB vypracovat program na sestavení tohoto systému, pomocí něhož lze matematicky simulovat běh CG v konečné aritmetice.
Provést numerické experimenty zaměřené na zjišťování vlastností systému.
Research Plan
Pro proniknutí do problematiky tématu nastudovat uvedenou literaturu a aktuální články.
Formulovat matematické vlastnosti metody sdružených gradientů.
Popsat a numericky demonstrovat základní jevy k nimž dochází u metody sdružených gradientů (CG) vlivem konečné aritmetiky počítače.
Seznámit se s teorií A. Greenbauma a Z. Strakoše, podle níž je možné hledět na výpočty CG v konečné aritmetice jako na výpočty přesné CG aplikované na jiný systém lineárních algebraických rovnic.
V systému MATLAB vypracovat program na sestavení tohoto systému, pomocí něhož lze matematicky simulovat běh CG v konečné aritmetice.
Provést numerické experimenty zaměřené na zjišťování vlastností systému.
Recommended resources
J. Duintjer Tebbens, I. Hnětynková, M. Plešinger, Z. Strakoš, P. Tichý, Analýza metod pro maticové výpočty: Základni metody, Mafyzpress, to appear in 2012.
M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards, 49 (1952), pp. 409--436 (1953).
G. Meurant, The Lanczos and conjugate gradient algorithms, vol. 19 of Software, Environments, and Tools, Society for Industrial andApplied Mathematics (SIAM), Philadelphia, PA, 2006.
G. Meurant and Z. Strakoš, The Lanczos and conjugate gradient algorithms in finite precision arithmetic, Acta Numer., 15 (2006), pp. 471--542.
A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl., 113 (1989), pp. 7--63.
A. Greenbaum and Z. Strakoš, Predicting the behavior of finite precision Lanczos and conjugate gradient computations, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 121--137.
J. K. Reid, On the method of conjugate gradients for the solution of large sparse systems of linear equations, in Large sparse sets of linear equations (Proc. Conf., St. Catherine´s Coll., Oxford, 1970), Academic Press, London, 1971, pp. 231--254.
Z. Strakoš, On the real convergence rate of the conjugate gradient method, linear Algebra Appl., 154/156 (1991), pp. 535--549.
Z. Strakoš and P. Tichý, On error estimation in the conjugate gradient method and why it works in finite precision computations, Electron. Trans. Numer. Anal., 13 (2002), pp. 56--80.
Recommended resources
J. Duintjer Tebbens, I. Hnětynková, M. Plešinger, Z. Strakoš, P. Tichý, Analýza metod pro maticové výpočty: Základni metody, Mafyzpress, to appear in 2012.
M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards, 49 (1952), pp. 409--436 (1953).
G. Meurant, The Lanczos and conjugate gradient algorithms, vol. 19 of Software, Environments, and Tools, Society for Industrial andApplied Mathematics (SIAM), Philadelphia, PA, 2006.
G. Meurant and Z. Strakoš, The Lanczos and conjugate gradient algorithms in finite precision arithmetic, Acta Numer., 15 (2006), pp. 471--542.
A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl., 113 (1989), pp. 7--63.
A. Greenbaum and Z. Strakoš, Predicting the behavior of finite precision Lanczos and conjugate gradient computations, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 121--137.
J. K. Reid, On the method of conjugate gradients for the solution of large sparse systems of linear equations, in Large sparse sets of linear equations (Proc. Conf., St. Catherine´s Coll., Oxford, 1970), Academic Press, London, 1971, pp. 231--254.
Z. Strakoš, On the real convergence rate of the conjugate gradient method, linear Algebra Appl., 154/156 (1991), pp. 535--549.
Z. Strakoš and P. Tichý, On error estimation in the conjugate gradient method and why it works in finite precision computations, Electron. Trans. Numer. Anal., 13 (2002), pp. 56--80.