\(\text{GL}(E)\)-quasilinear transformations and acceleration (Q1294465)

The paper is concerned with sequences of \( p \) real-dimensional vectors. \(\lambda\) being such a vector, the sequence \( {\mathbf s}(n)\) \((n \geq 0) \) for which a) \( {\mathbf s}(n) \neq\lambda\) \((n \geq N) \) for some integer \( N \) and b) a \( p \times p \) nonsingular real matrix \( {\mathbb{B}} \) for which \( {\mathbf I -\mathbb{B} }\) is also nonsingular and a sequence \( {\mathbb{B}}(n)\) \((n \geq 0) \) of such matrices converging to the null matrix exists for which \( {\mathbf s}(n + 1) - {\mathbf s}(n) = [{\mathbb{B} -\mathbb{B}}(n)] [{\mathbf s}(n) -\lambda] (n \geq 0) \) is said to converge linearly to \(\lambda\). A transformation \( {\mathbf f} \) of \( k \) vectors \( {\mathbf v}(1),\ldots,{\mathbf v}(k) \) producing a single vector and obeying rules of the form \( {\mathbf f}(\mathbb{A}{\mathbf v}(1),\ldots,\mathbb{A}{\mathbf v}(k)) = \mathbb{A} f({\mathbf v})(1),\ldots,{\mathbf v}(k)) \) for all nonsingular real \( p \times p \) matrices \(\mathbb{A} \), and \( {\mathbf f}({\mathbf v}(1) + {\mathbf b},\ldots,{\mathbf v}(k) + {\mathbf b}))= {\mathbf f}({\mathbf v}(1),\ldots,{\mathbf v}(k)) + {\mathbf b} \) is said to be strictly quasilinear. Such transformations may be applied in the form \( {\mathbf f}({\mathbf s}(m),\ldots,{\mathbf s}(m + k - 1)) \) to subsequences of vectors to produce a further sequence of vectors defined for \( m \geq 0 \) which in some cases converges to the limit of \( {\mathbf s}(n) (n \geq 0) \) faster than does this sequence itself. It is shown, however, that the convergence of linearly convergent sequences is not accelerated in this way by strictly quasilinear transformations. P. Henrici proposed the following transformation. Denote by \( \nabla(i|n) \) the matrix whose successive columns are \( \Delta^{i} {\mathbf s}(n + r) (0 \leq r \leq p), \Delta \) being the forward difference operator. The transformation is \( {\mathbf f}({\mathbf s}(m),\ldots,{\mathbf s}(m + s(m + p + 1)) = {\mathbf s}(m) - \nabla(1|m) \nabla(2|m)^{-1} [ {\mathbf s}(m+1) - {\mathbf s}(m) ]. \) It is strictly quasilinear and, as the author remarks in the course of a detailed examination, subject to his disqualification. But matters are a good deal worse. In practice, the vectors \( {\mathbf s}(n) \) are often approximations to values, taken at equidistant points, of functions satisfying differential or integral equations. Such equations are treated by finite difference methods: for each vector, the approximations are roughly values of polynomials each spanning \( t \) consecutive elements, \( t \) being the order of the method used. There is a linear combination, involving binomial coefficients and powers of minus one, of \( t \) successive elements of a vector, whose value is less than a specified truncation error limit and as such very small. Although the approximating polynomial varies from one set of \( t \) values to the next, the same linear combination of successive values remains small. This holds with regard to all vectors of the sequence whose convergence is to be accelerated: there is a linear combination of each set of \( t \) consecutive rows of \( \nabla(2|m) \) whose value is small and for some such sets the value will be very small: \( \nabla(2|m) \) is numerically nearly singular. In many cases the transformation is highly unstable and cannot be implemented effectively.