Affine Iterations and Wrapping Effect: Various Approaches

Keywords: interval analysis, affine iterations, matrix powers, Lohner's QR algorithm, QR factorization, SVD factorization

Abstract

Affine iterations of the form x(n+1)=Ax(n)+b converge, using real arithmetic, if the spectral radius of the matrix A is less than 1. However, substituting interval arithmetic to real arithmetic may lead to divergence of these iterations, in particular if the spectral radius of the absolute value of A is greater than 1. We will review  different approaches to limit the overestimation of the iterates, when the components of the initial vector x(0) and b are intervals. We will compare, both theoretically and experimentally, the widths of the iterates computed by these different methods: the naive iteration, methods based on the QR- and SVD-factorization of A, and Lohner's QR-factorization method. The method  based on the SVD-factorization is computationally less demanding and gives good results when the matrix is poorly scaled, it is superseded either by the naive iteration or by Lohner's method otherwise.

Downloads

Download data is not yet available.
Published
2023-06-02
How to Cite
Revol, N. (2023). Affine Iterations and Wrapping Effect: Various Approaches. Acta Cybernetica, 26(1), 129-147. https://doi.org/10.14232/actacyb.295251
Section
Special Issue of SCAN 2020