Cílem této práce je popsat a vysvětlit vztahy mezi metodou sdružených gradientů, Lanczosovým algoritmem, ortogonálnímy polynomy, obecným kvadraturním pravidlem a Jacobiho maticí. Ukážeme jak můžeme získat Gaussovu kvadraturu aproximací Riemann-Stieltjesa itnegrálu. Uzly a váhy tohoto pravidla můžeme počítat pomocí vlastních čísel a vlastních vektorů Jacobiho matice, která je popsána tříčlennou rekurencí. Potom představíme algoritmy pro počítání dolních a horních odhadů A-normy chyby založené na Gaussově, Gauss-Radau a Gauss-Lobatto kvadratuře. V numerických experimentech se převážně soustředíme na horní odhad A-normy chyby. Položíme otázky na stabilitu a přesnost horního Gauss-Radau odhadu. Na závěr představíme heuristiku pro zlepšení dolního odhadu.
Anotace v angličtině
The aim of this work is to describe and explain the relationships
between Conjugate gradient, Lanczos algorithm, orthogonal polynomials, quadrature rules and Jacobi matrix.
We show how can to obtain Gauss quadrature rules by approximation of Riemann?Stieltjes integral and the nodes and weights of these rules can be
computed using the eigenvalues and eigenvectors of the Jacobi matrix describing
the three-term recurrence. Then we present algorithms for compute of the lower and upper bound for the A-norm of the error based on Gauss, Gauss- Radau, Gauss-Lobatto quadrature .
In numerical experiments we concentrate mostly on the upper bound for the
A-norm of the error. Pose the questions about accuracy and stability of the Gauss-Radau
estimate. In conclusion we present a heuristic for the adaptive refinement of
the estimate.
Conjugate gradient, Lanczos algorithm, orthogonal polynomial,Gauss quadrature, Jacobi matrix, A-norm of the error
Rozsah průvodní práce
67 s.
Jazyk
CZ
Anotace
Cílem této práce je popsat a vysvětlit vztahy mezi metodou sdružených gradientů, Lanczosovým algoritmem, ortogonálnímy polynomy, obecným kvadraturním pravidlem a Jacobiho maticí. Ukážeme jak můžeme získat Gaussovu kvadraturu aproximací Riemann-Stieltjesa itnegrálu. Uzly a váhy tohoto pravidla můžeme počítat pomocí vlastních čísel a vlastních vektorů Jacobiho matice, která je popsána tříčlennou rekurencí. Potom představíme algoritmy pro počítání dolních a horních odhadů A-normy chyby založené na Gaussově, Gauss-Radau a Gauss-Lobatto kvadratuře. V numerických experimentech se převážně soustředíme na horní odhad A-normy chyby. Položíme otázky na stabilitu a přesnost horního Gauss-Radau odhadu. Na závěr představíme heuristiku pro zlepšení dolního odhadu.
Anotace v angličtině
The aim of this work is to describe and explain the relationships
between Conjugate gradient, Lanczos algorithm, orthogonal polynomials, quadrature rules and Jacobi matrix.
We show how can to obtain Gauss quadrature rules by approximation of Riemann?Stieltjes integral and the nodes and weights of these rules can be
computed using the eigenvalues and eigenvectors of the Jacobi matrix describing
the three-term recurrence. Then we present algorithms for compute of the lower and upper bound for the A-norm of the error based on Gauss, Gauss- Radau, Gauss-Lobatto quadrature .
In numerical experiments we concentrate mostly on the upper bound for the
A-norm of the error. Pose the questions about accuracy and stability of the Gauss-Radau
estimate. In conclusion we present a heuristic for the adaptive refinement of
the estimate.
Conjugate gradient, Lanczos algorithm, orthogonal polynomial,Gauss quadrature, Jacobi matrix, A-norm of the error
Zásady pro vypracování
Pro proniknutí do problematiky tématu nastudovat uvedenou literaturu.
Odvodit metodu sdružených gradientů pomocí Lanczosova algoritmu.
Popsat souvislosti metody sdružených gradintů s ortogonálními polynomy, Jacobiho maticemi a Gaussovou kvadraturou
Popsat různé odhady normy chyby (založených na Gaussově, Gauss-Radau či Gauss-Lobatto kvadratuře).
V systému MATLAB testovat uvedené odhady a studovat jejich silné a slabé stránky z teoretického i praktického hlediska.
Provést numerické experimenty týkající se studia některé z otevřených otázek (např. algebraického zjednodušení algoritmů na výpočet odhadů či adaptivní volby parametrů).
Zásady pro vypracování
Pro proniknutí do problematiky tématu nastudovat uvedenou literaturu.
Odvodit metodu sdružených gradientů pomocí Lanczosova algoritmu.
Popsat souvislosti metody sdružených gradintů s ortogonálními polynomy, Jacobiho maticemi a Gaussovou kvadraturou
Popsat různé odhady normy chyby (založených na Gaussově, Gauss-Radau či Gauss-Lobatto kvadratuře).
V systému MATLAB testovat uvedené odhady a studovat jejich silné a slabé stránky z teoretického i praktického hlediska.
Provést numerické experimenty týkající se studia některé z otevřených otázek (např. algebraického zjednodušení algoritmů na výpočet odhadů či adaptivní volby parametrů).
Seznam doporučené literatury
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.H. Golub and G. Meurant, Matrices, Moments and Quadrature With Applications, Princeton University Press, USA, 2010.
G.H. Golub and Z Strakoš, Estimates in quadratic formulas, Numer. Algorithms, 8 (1994), pp. 241--268.
G. Meurant and P. Tichý, Simplification of the CGQL algorithm, in preparation.
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.
Z. Strakoš and P. Tichý, Error estimation in preconditioned conjugate gradients, BIT 45, 789-817 (2005).
Seznam doporučené literatury
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.H. Golub and G. Meurant, Matrices, Moments and Quadrature With Applications, Princeton University Press, USA, 2010.
G.H. Golub and Z Strakoš, Estimates in quadratic formulas, Numer. Algorithms, 8 (1994), pp. 241--268.
G. Meurant and P. Tichý, Simplification of the CGQL algorithm, in preparation.
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.
Z. Strakoš and P. Tichý, Error estimation in preconditioned conjugate gradients, BIT 45, 789-817 (2005).