Backward Error Estimates for Toeplitz and Vandermonde Systems

Given a computed approximate solution x to Ax= b, it is of interest to find nearby systems with x as exact solution, and which have the same structure as A. In this paper, we show that the distance to these nearby structured systems can be much larger than for the corresponding general perturbation for Toeplitz and Vandennonde systems. In fact, even the correctly rounded solution x may require a structured penurbation of O(nllxll), not O(n) as might be expected.