This paper extends Higham's results on the remarkable
numerical stability of the
Bjorck-Pereyra algorithm for Vandermonde linear systems
to other classes of structured matrices.
In
another recent paper of the authors
several fast algorithms were developed for
solving linear systems with Cauchy coefficient matrices, and it
was observed
that they give much higher accuracy than standard numerically stable
methods. In this paper an a-priori forward error analysis
is presented for one of these algorithms, referred to as the BKO
algorithm, suggesting an explanation for
its high relative accuracy. This analysis
identifies a particular class of Cauchy systems for which
the relative error in the components of the computed solution
is about as small as could possibly be expected,
The bounds obtained in the
present paper, do not depend on
the condition number of the coefficient matrix, and they show that
the BKO algorithm introduces no more uncertainty into numerical solutions
than is caused by simply storing the right-hand side vector
on a finite precision computer.
In particular, this indicates that Hilbert linear systems,
which traditionally has been considered to be too ill-conditioned to be
attacked, with special
right hand sides actually can be solved with
a remarkably high accuracy. The obtained results are used to illustrate the
concepts of total positivity and effective
well-conditioning.
Related papers:
The BKO algorithm, analyzed in the present paper was suggested in
[BKO94a]. The algorithms with partial
and diagonal pivoting for the more general Cauchy-like
matrices appeared in
[GO94a]
( see also the short version [GO94e] ) and
in [GKO95].
Keywords:
Displacement structure,
Cauchy matrix,
Hilbert matrix,
Vandermonde matrix,
Bjorck-Pereyra algorithm,
Numerical stability,
Forward error analysis,
Ordering of interpolation points,
Leja ordering,
Predictive partial pivoting,
Total positivity,
Effective well-conditioning.
AMS subject classification: 65F05, 65H10, 15A06, 15A09, 15A57.
Vadim Olshevsky's Home page
