The Accurate and Efficient Solution of a Totally Positive Generalized Vandermonde Linear System
The Accurate and Efficient Solution of a Totally Positive Generalized Vandermonde Linear System
复制标题
DOI：
10.1137/s0895479804440335
复制
发表时间：
2005-05
期刊：
影响因子：
--
通讯作者：
J. Demmel;P. Koev
中科院分区：
文献类型：
--
作者：
J. Demmel;P. Koev
Vandermonde，Cauchy和Cauchy-Vandermonde全正线性方程组可以用Bjorck-Pereyra型方法在O（n2）时间内非常精确地求解。我们证明了Bjorck-Pereyra型方法不仅对上述线性方程组存在，而且对任何全正线性方程组也存在，只要初始子式（即，包括第一行或第一列的相邻子项）可以被精确地计算。利用这一结果，我们设计了一个新的O（n ~ 2）的Bjorck-Pereyra型方法，通过使用一个新的算法计算Schur函数来求解广义Vandermonde方程组.我们提出了明确的双对角分解，LDU分解，和一个完全积极的广义范德蒙矩阵的逆的条目的公式，以及算法计算这些条目的相对精度高。
Vandermonde, Cauchy, and Cauchy--Vandermonde totally positive linear systems can be solved extremely accurately in O(n2 time using Bjorck--Pereyra-type methods. We prove that Bjorck--Pereyra-type methods exist not only for the above linear systems but also for any totally positive linear system as long as the initial minors (i.e., contiguous minors that include the first row or column) can be computed accurately. Using this result we design a new O(n2 Bjorck--Pereyra-type method for solving generalized Vandermonde systems of equations by using a new algorithm for computing the Schur function. We present explicit formulas for the entries of the bidiagonal decomposition, the LDU decomposition, and the inverse of a totally positive generalized Vandermonde matrix, as well as algorithms for computing these entries to high relative accuracy.