Stability of Toeplitz matrix inversion formulas (Q2784759)

Let \(T_n=[a_{i-j}]_{i,j=0}^{n-1}\) be a Toeplitz matrix and \(T^{-1}_n\) its inverse. The objective of the paper is the investigation of stability of algorithms emerging under the calculation of the matrix-vector product \(T^{-1}_n b\) rather than under the calculation of the inverse matrix. The author is looking for estimations of the kind NEWLINE\[NEWLINE\frac{\|\xi-\widehat{\xi}]\|}{\|\xi\|}\leq c n k(T_n)({\mathbf u}+O(\mathbf{u}^2))NEWLINE\]NEWLINE where \(\xi=T^{-1}_n b\), \(\widehat{\xi}\) is the computed vector, \(k(\cdot)\) is the condition number and \(\mathbf{u} \) is the machine precision. The inversion formulas for \(T_n\) usually having the form \(T_n^{-1}=B_1-B_2\), the author's main task is to estimate the magnitude of the matrices \(B_1\) and \(B_2\), so the main accent is given to the stability of the formula rather than the algorithms. The author gives a survey of inversion formulas, presents some bounds for the forward error and reduces the stability problem to that of estimation of the norms of fundamental systems. He also discusses the problem of choosing the parameters in families of the inversion formulas to minimize the norms of the fundamental systems, that is, norms of \(B_1\) and \(B_2\). Then he estimates the norms of the fundamental system by norms of matrices and finally shows that the well-conditioned extension of well-conditioned Toeplitz matrix exists in order to prove the existence of stable inversion formulas.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00035].