|
|
Multilevel methods and adaptivity
Vacek, Petr ; Strakoš, Zdeněk (advisor) ; Tichý, Petr (referee)
After introduction of the model problem we derive its weak formulation, show the existence and the uniqueness of the solution, and present the Galerkin finite element method. Then we briefly describe some of the stationary iterative methods and their smoothing property. We present the most common multigrid schemes, i.e. two-grid correction scheme, V-cycle scheme, and the full multigrid algorithm. Then we perform numerical experiment showing the differences between the use of the direct and iterative coarsest grid solver in V-cycle scheme and experiment considering a perturbation of the correction vector simulating a fault of a computational device. Powered by TCPDF (www.tcpdf.org)
|
|
|
Analysis of Krylov subspace methods
Gergelits, Tomáš ; Strakoš, Zdeněk (advisor) ; Hnětynková, Iveta (referee)
Title: Analysis of Krylov subspace methods Author: Tomáš Gergelits Department: Department of Numerical Mathematics Supervisor: prof. Ing. Zdeněk Strakoš, DrSc. Abstract: After the derivation of the Conjugate Gradient method (CG) and the short review of its relationship with other fields of mathematics, this thesis is focused on its convergence behaviour both in exact and finite precision arith- metic. Fundamental difference between the CG and the Chebyshev semi-iterative method is described in detail. Then we investigate the use of the widespread lin- ear convergence bound based on Chebyshev polynomials. Through the example of the composite polynomial convergence bounds it is showed that the effects of rounding errors must be included in any consideration concerning the CG rate of convergence relevant to practical computations. Furthermore, the close corre- spondence between the trajectories of the CG approximations generated in finite precision and exact arithmetic is studied. The thesis is concluded with the discus- sion concerning the sensitivity of the closely related Gauss-Christoffel quadrature. The last two topics may motivate our further research. Keywords: Conjugate Gradient Method, Chebyshev semi-iterative method, fi- nite precision computations, delay of convergence, composite polynomial conver-...
|
|
|
Teorie a aplikace krylovovských metod v souvislostech
Gergelits, Tomáš ; Strakoš, Zdeněk (advisor) ; Hnětynková, Iveta (referee)
Title: Krylov subspace methods: Theory, applications and interconnections Author: Tomáš Gergelits Department: Department of Numerical Mathematics Supervisor: prof. Ing. Zdeněk Strakoš, DrSc. Abstract: After recalling of properties of Chebyshev polynomials and of sta- tionary iterative methods, this thesis is focused on the description of Conjugate Gradient Method (CG), the Krylov method of the choice for symmetric positive definite matrices. Fundamental difference between stationary iterative methods and Krylov subspace methods is emphasized. CG is derived using the minimiza- tion of the quadratic functional and the relationship with several other fields of mathematics (Lanczos method, orthogonal polynomials, quadratic rules, moment problem) is pointed out. Effects of finite precision arithmetic are emphasized. In compliance with the theoretical part, the numerical experiments examine a bound derived assuming exact arithmetic which is often presented in literature. It is shown that this bound inevitably fails in practical computations. The thesis is concluded with description of two open problems which can motivate further research. Keywords: Krylov subspace methods, convergence behaviour, numerical stabil- ity, spectral information, convergence rate bounds
|
|
|
Maticové funkce a jejich numerické aproximace
Suchá, Darja ; Hnětynková, Iveta (advisor) ; Strakoš, Zdeněk (referee)
In the presented work, we study numerical methods for approximation of a function f of a matrix A. First, we give theoretical background - definitions of matrix functions, and their properties. Further, we summarize basic numerical methods for computation of an approximation of matrix functions f(A). In many applications, we need to approximate the matrix function f(A) applied on an apriory given vector b, i.e. f(A)b. Especially, when A is large and sparse, the computation of approximation to f(A) and subsequent multiplication by the vector b can be computationaly expensive. Therefore we study methods, which compute the approximation of f(A)b directly. Main emphasis is placed on the polynomial approximation in the least squares sense, and several modifications of Krylov subspace methods. Numerical experiments compare convergence and computa- tional time required to obtain reasonable approximation to f(A)b. 1
|
|
|
Odhady algebraické chyby a zastavovací kritéria v numerickém řešení parciálních diferenciálních rovnic
Papež, Jan ; Strakoš, Zdeněk (advisor) ; Vlasák, Miloslav (referee)
Title: Estimation of the algebraic error and stopping criteria in numerical solution of partial differential equations Author: Jan Papež Department: Department of Numerical Mathematics Supervisor of the master thesis: Zdeněk Strakoš Abstract: After introduction of the model problem and its properties we describe the Conjugate Gradient Method (CG). We present the estimates of the energy norm of the error and a heuristic for the adaptive refinement of the estimate. The difference in the local behaviour of the discretization and the algebraic error is illustrated by numerical experiments using the given model problem. A posteriori estimates for the discretization and the total error that take into account the inexact solution of the algebraic system are then discussed. In order to get a useful perspective, we briefly recall the multigrid method. Then the Cascadic Conjugate Gradient Method of Deuflhard (CCG) is presented. Using the estimates for the error presented in the preceding parts of the thesis, the new stopping criteria for CCG are proposed. The CCG method with the new stopping criteria is then tested. Keywords: numerical PDE, discretization error, algebraic error, error es- timates, locality of the error, adaptivity
|
|
|
Od problému momentů k moderním iteračním metodám - historické souvislosti a inspirace
Tůma, Martin ; Strakoš, Zdeněk (advisor) ; Zítko, Jan (referee)
In the present work we study the connections between the moment problem and the modern iterative methods. A short historical review of the study of the moment problem is given. Some different definitions of the moment problem are shown. Motivation and results of some mathematicians, who used the moment problem in their work are discussed. Connections between different definitions of the moment problem, Gauss-Christoffel quadrature, orthogonal polynomials, continued fractions, Sturm-Liouville problem, reduction of the model in linear dynamical systems and some of the iterative methods like Lanczos and Conjugate gradients method are explained.
|
|
|
Neinterpolační a zjemněné interpolační kvadratury
Novelinková, Martina ; Kofroň, Josef (advisor) ; Strakoš, Zdeněk (referee)
Most of this work deals with refined interpolatory quadrature formulae. The first part is focused on the general background of the problem of numerical integration and some of the basic properties of interpolatory quadratures are discussed. Further in the work, the systems of orthogonal polynomials are introduced and their most important characteristics are proved. A part of this text is dedicated to detailed description of some refined interpolatory quadratures, such as general and classical Gauss quadrature and their modifications. We summarise also the most imporant properties of Romberg's quadrature formula and show the error estimations. This work also includes numerical experiments which practically show the introduced statememnts and comparison of errors of Romberg formula, Clenshaw-Curtis scheme and trapezoidal rule.
|
|
|
Teoretické otázky popisu chování krylovovských metod
Strnad, Otto ; Strakoš, Zdeněk (advisor) ; Zítko, Jan (referee)
The presented thesis is focused on the GMRES convergence analysis. The basic principles of CG, MINRES and GMRES are briefly explained. The thesis summarizes some known convergence results of these methods. The known characterizations of the matrices and the right hand sides gen- erating the same Krylov residual spaces are summarized. Connections and the differences between the different points of view on GMRES convergence analysis are shown. We expect that if the convergence curve of GMRES applied to the nonnormal matrix and the right hand side seems to be de- termined by the eigenvalues of the matrix then exists a matrix that is close to normal and has the same spectrum as the matrix and for the right hand side has the same GMRES convergence curve (We assume that the initial approximation 0 = 0). Several numerical experiments are done to examine this assumption. This thesis describes an unpublished result of Gérard Meu- rant which is the formula for the norm of the -th error of GMRES applied to the matrix and right hand side and its derivation. The upper estimate of the -th GMRES error is derived. This estimate is minimized via spectrum.
|
|
| |
|
| |
guest ::
