Richardson method and totally nonnegative linear systems (Q603132)

Totally nonnegative stochastic matrices arise as collocation matrices in computer-aided design interpolating curves in a shape preserving manner [see e. g. \textit{J. M. Peña}. Shape preserving representations in computer aided geometric design. Huntington, NY: Nova Science. (1999; Zbl 1005.68163)] by polynomial and spline functions. The corresponding linear systems \(A x = b\) for the computation of the control points can be solved by the Richardson iterative method which converges if and only if the spectral radius of \(\rho(I-A)\), \(I\) identity matrix, is less than \(1\). In order to accelerate the convergence the authors use a relaxation of the method. They prove the convergence of this modified Richardson method for nonsingular totally nonnegative stochastic matrices and derive the parameter for the optimal convergence speed. Additionally, a modified Richardson method is presented, that converges for any nonsingular totally nonnegative matrix, including a procedure for the estimation of the optimal convergence parameter. The results are verified by numerical examples arising in the interpolation by spline and polynomial functions. Discussed are Vandermonde matrices, Bernstein-Vandermonde matrices, and quadratic and cubic B-spline collocation matrices. The choice of the optimal parameter reduces the number of iterations to a factor greater than a half. The convergence is low in the case of bad conditioning using higher degrees in the polynomial interpolation but, the convergence is ensured for any dimension.