solveVandermonde {pnd} | R Documentation |
Numerically stable non-confluent Vandermonde system solver
Description
Numerically stable non-confluent Vandermonde system solver
Usage
solveVandermonde(s, b)
Arguments
s |
Numeric vector of stencil points defining the Vandermonde matrix on
the left-hand side, where each element |
b |
Numeric vector of the right-hand side of the equation.
This vector must be the same length as |
Details
This function utilises the (Björck and Pereyra 1970) algorithm for an accurate solution to non-confluent Vandermonde systems, which are known for their numerical instability. Unlike Gaussian elimination, which suffers from ill conditioning, this algorithm achieves numerical stability through exploiting the ordering of the stencil. An unsorted stencils will trigger a warning. Additionally, the stencil must contain unique points, as repeated values make the Vandermonde matrix confluent and therefore non-invertible.
This implementation is a verbatim translation of Algorithm 4.6.2 from (Golub and Van Loan 2013), which is robust against the issues typically associated with Vandermonde systems.
See (Higham 1987) for an in-depth error analysis of this algorithm.
Value
A numeric vector of coefficients solving the Vandermonde system,
matching the length of s
.
References
Björck Å, Pereyra V (1970).
“Solution of Vandermonde systems of equations.”
Mathematics of computation, 24(112), 893–903.
Golub GH, Van Loan CF (2013).
Matrix computations, 4 edition.
Johns Hopkins University Press.
Higham NJ (1987).
“Error analysis of the Björck-Pereyra algorithms for solving Vandermonde systems.”
Numerische Mathematik, 50(5), 613–632.
Examples
# Approximate the 4th derivatives on a non-negative stencil
solveVandermonde(s = 0:5, b = c(0, 0, 0, 0, 24, 0))
# Small numerical inaccuracies: note the 6.66e-15 in the 4th position --
# it should be rounded towards zero:
solveVandermonde(s = -3:3, b = c(0, 1, rep(0, 5))) * 60