Convergence properties of algebraic reconstruction methods

Abstract

Při hledání vektoru řešení soustavy lineárních algebraických rovnic se osvědčily iter- ační metody, a to zejména pro velké a řídké matice. V této práci se zaměříme speciálně na ill-posed inverzní problémy, kde matice systému je špatně podmíněná a přibližná řešení jsou citlivá i na malé změny ve vstupu (pozorování). Tyto problémy řešíme iterativně pomocí Standardní Kaczmarzovy metody a jejích modifikací, které nejprve studujeme a uvádíme některé známé konvergenční věty. Nakonec metody numericky porovnáme, abychom zjistili, zda různé změny iteračního procesu mohou vést ke zlepšení rychlosti konvergence. Naše experimenty zahrnují problémy s různými vlastnostmi, od mírně až po velmi ill-posed. V práci ilustrujeme semikonvergenční chování, jev typický pro inverzní ill-posed problémy. Budeme experimentálně studovat reziduum a skutečnou chybu, stejně jako výpočetní čas, který jednotlivé metody potřebují k dosažení určité přesnosti. 1

In dealing with the problem of finding the solution vector for a system of linear alge- braic equations, iterative methods have proven effective, especially for large and sparse matrices. Here we focus on ill-posed inverse problems, where the system matrices are ill- conditioned and the approximate solutions are sensitive to even small changes in the input (observation). We solve these problems iteratively using the Standard Kaczmarz method and its modifications, which we first study and state some well-known convergence the- orems. Finally, we compare these methods numerically, to see if various alterations of the iterative process can result in an improved convergence rate. Our experiments in- volve testing problems with varying levels of ill-posedness, ranging from mildly to very ill-posed. We illustrate semiconvergence behavior, a phenomenon typical for inverse ill- posed problems. Residual and true error are studied experimentally, as well as the time it takes for each method to reach a certain level of accuracy. 1