Extrapolation methods and their applications in numerical analysis and applied mathematics

This Ph.D. thesis discusses some applications of extrapolation methods. In numerical analysis and in applied mathematics one has often to deal with sequences which converge slowly to their limit. Extrapolation methods can be used to accelerate the convergence of a slow converging sequence or even to sum up divergent series. The first two chapters of this thesis are devoted to scalar sequence transformations. We revisit Aitken's Δ2 process and we propose three new transformations which generalize it. The convergence and acceleration properties of one of our transformations are discussed theoretically and verified experimentally using diverging and converging sequences. Shanks transformation and Wynn's ε-algorithm are studied extensively; we remind the particular rules due to Wynn for treating isolated singularities, i.e. when two consecutive elements are equal or almost equal, and the more general particular rules proposed by Cordellier for treating non-isolated singularities, i.e. when more than two elements are equal. A new implementation of the generalized particular rule is given covering all the cases, namely singularities caused by two or more elements that are equal or almost equal. In the remaining part of the thesis we focus on vector extrapolation. First we briefly describe the vector ε-algorithm, the topological ε-algorithm and the simplified topological ε-algorithm, which was recently introduced by Brezinski and Redivo-Zaglia. In the sequel, we present under a unified notation the Algebraic Reconstruction Techniques, the Simultaneous Iterative Reconstruction Techniques, and other iterative regularization methods, which are commonly used for solving linear inverse problems. Last, we study the gain of applying extrapolation on these methods in imaging problems. In particular, we use the simplified topological ε-algorithm in order to extrapolate a sequence generated by methods such as Landweber's and Cimmino's when solving image reconstruction and restoration problems. The numerical results illustrate the good performance of the accelerated methods compared to their unaccelerated versions and other methods.

Questa tesi di dottorato tratta alcune applicazioni dei metodi di estrapolazione. Spesso in analisi numerica e nella matematica applicata si devono trattare successioni che convergono lentamente al loro limite. I metodi di estrapolazione possono essere utilizzati per accelerare la convergenza di una successione che converge lentamente o anche per sommare serie divergenti. I primi due capitoli della tesi sono dedicati alle trasformazioni di successioni scalari. Viene ripreso il Δ2 di Aitken e vengono proposte tre nuove trasformazioni che lo generalizzano. Le proprietà di convergenza e di accelerazione di una delle trasformazioni sono discusse teoricamente e verificate sperimentalmente usando delle successioni divergenti e convergenti. La trasformazione di Shanks e l'ε-algorithm di Wynn sono accuratamente studiati; vengono richiamate le regole particolari proposte da Wynn per il trattamento delle singolarità isolate, ovvero quando due elementi consecutivi sono uguali o quasi uguali, ed anche le regole particolari, più generali, proposte da Cordellier, per il trattamento delle singolarità non isolate, ovvero quando più di due elementi sono uguali. Viene proposta una nuova generale implementazione delle regole particolari in modo da poter trattare tutti i casi possibili, ossia la presenza di singolarità causata da due o più elementi che sono uguali o quasi uguali. Nella parte rimanente della tesi ci si concentra sull'estrapolazione vettoriale. Prima vengono brevemente descritti l'ε-algorithm vettoriale, l'ε-algorithm topologico e la sua versione semplificata, recentemente introdotta da Brezinski e Redivo-Zaglia. Successivamente, vengono presentate, con una notazione unificata le Algebraic Reconstruction Techniques (ART), le Simultaneous Iterative Reconstruction Techniques (SIRT) e altri metodi iterativi di regolarizzazione, che sono comunemente utilizzati per risolvere problemi inversi lineari. Infine, vengono illustrati i vantaggi ottenuti applicando l'estrapolazione ai precedenti metodi iterativi, utilizzati su problemi relativi alle immagini. In particolare, viene utilizzato il simplified topological ε-algorithm al fine di estrapolare una successione generata da metodi di tipo Landweber e Cimmino quando si risolvono problemi di ricostruzione e di restauro di immagini. I risultati numerici mostrano un buon comportamento dei metodi accelerati rispetto alle loro versioni non accelerate ed anche rispetto ad altri metodi.