Accuracy and stability of inversion of power series
Raymundo Navarrete, Divakar Viswanath · IMA Journal of Numerical Analysis · 2015
This article considers the numerical inversion of the power series |$p(x)=1+b_{1}x+b_{2}x^{2}+ \cdots$| to compute the inverse series |$q(x)$| satisfying |$p(x)q(x)=1$| . Numerical inversion is a special case of triangular back-substitution, which has been known for its beguiling numerical stability since the classic work of Wilkinson (1961, Error analysis of direct methods of matrix inversion. J. Assoc. Comput. Mach. , 8 , 281–330). We prove the numerical stability of inversion of power series and obtain bounds on numerical error. A range of examples show that these bounds overestimate the error by only a few digits. When |$p(x)$| is a polynomial and |$x=a$| is a root with |$p(a)=0$| , we show that root deflation via the simple division |$p(x)/(x-a)$| can trigger instabilities relevant to polynomial root finding and computation of finite-difference weights. When |$p(x)$| is a polynomial, the accuracy of the computed inverse |$q(x)$| is connected to the pseudozeros of |$p(x)$| .