Stability Analysis of Algorithms for Solving Confluent Vandermonde-Like Systems

A confluent Vandermonde-like matrix P(α ₀ ,α ₁ , ⋯ ,α ₙ ) is a generalisation of the confluent Vandermonde matrix in which the monomials are replaced by arbitrary polynomials. For the case where the polynomials satisfy a three-term recurrence relation algorithms for solving the systems $Px = b$ and PT a = f in O(n² ) operations are derived. Forward and backward error analyses that provide bounds for the relative error and the residual of the computed solution are given. The bounds reveal a rich variety of problem-dependent phenomena, including both good and bad stability properties and the possibility of Xextremely accurate solutions. To combat potential instability, a method is derived for computing a “stable” ordering of the points α ᵢ; it mimics the interchanges performed by Gaussian elimination with partial pivoting, using only O(n²) operations. The results of extensive numerical tests are summarised, and recommendations are given for how to use the fast algorithms to solve Vandermonde-like systems in a stable manner.