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

Chan, Tony F.; Foulser, David E.

SIAM J. Sci. Stat. Comput. 9, No. 6, 963-969 (1988).

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

MSC:

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

Keywords:

error analysis; well-conditioning; condition number; sensitivity; Vandermonde matrices; fast Poisson solver; fast sine transforms

Citations:

Zbl 0595.65029; Zbl 0221.65054