Effectively well-conditioned linear systems. (English) Zbl 0664.65041

The authors discuss effective well-conditioning of the linear system \(Ax=b\). The condition number \(K(A)=\| A\| \| A^{-1}\|\) is often an overly conservative measure of the sensitivity of x under perturbations of \(\Delta\) A and \(\Delta\) b to A and b respectively. Two practical cases in which the sensitivity of x may be significantly less than the worst case predicted by K(A) are presented. The first characterizes a class of Vandermonde matrices and right-hand-sides and the second a FFT-based fast Poisson solver, for each of which accurate solutions may be obtained.
For Vandermonde systems N. J. Higham [Numer. Math. 50, 613-532 (1987; Zbl 0595.65029)] has shown that the algorithm of A. Björck and V. Pereyra [Math. Comput. 24, 893-903 (1971; Zbl 0221.65054)] gives relative errors in the non-zero components of x which are independent of K(A) provided that scalars \(\alpha_ j\) of the Vandermonde matrix are in ascending order and that the elements of the right-hand side b oscillate in sign.
The computation of accurate solutions to the discretized one-dimensional Poisson problem is discussed and the authors’ experiments indicate that a fast Poisson solver composed entirely of fast sine transforms will have better numerical performance than the more common fast transform with tridiagonal solving.
Reviewer: A.Swift


65F35 Numerical computation of matrix norms, conditioning, scaling
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65F05 Direct numerical methods for linear systems and matrix inversion
65G50 Roundoff error
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
Full Text: DOI