Skip to main content
SpringerLink
Log in

The structured sensitivity of Vandermonde-like systems

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Summary

We consider a general class of structured matrices that includes (possibly confluent) Vandermonde and Vandermonde-like matrices. Here the entries in the matrix depend nonlinearly upon a vector of parameters. We define, condition numbers that measure the componentwise sensitivity of the associated primal and dual solutions to small componentwise perturbations in the parameters and in the right-hand side. Convenient expressions are derived for the infinity norm based condition numbers, and order-of-magnitude estimates are given for condition numbers defined in terms of a general vector norm. We then discuss the computation of the corresponding backward errors. After linearising the constraints, we derive an exact expression for the infinity norm dual backward error and show that the corresponding primal backward error is given by the minimum infinity-norm solution of an underdetermined linear system. Exact componentwise condition numbers are also derived for matrix inversion and the least squares problem, and the linearised least squares backward error is characterised.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Arioli, M., Demmel, J.W., Duff, I.S. (1989): Solving sparse linear systems with sqarse backward error. SIAM J. Matrix Anal. Appl.10, 165–190

    Article  Google Scholar 

  2. Bartels, S.G. (1991): Two topics in matrix analysis: structured sensitivity for Vandermonde-like systems and a subgradient method for matrix norm estimation. M.Sc. Thesis, University of Dundee

  3. Björck Å. (1991): Component-wise perturbation analysis and error bounds for linear least squares solutions. BIT31, 238–244

    Google Scholar 

  4. Björck Å., Pereyra, V. (1970): Solution of Vandermonde systems of equations. Math. Comput.24, 893–903

    Google Scholar 

  5. Bunch, J.R., Demmel, J.W., Van Loan, C.F. (1989): The strong stability of algorithms for solving symmetric linear systems. SIAM J. Matrix Anal. Appl.10 494–499

    Google Scholar 

  6. Gohberg, I., Koltracht, I. (1990): On the inversion of Cauchy matrices. In: M.A. Kaashoek, J.H. van Schuppen, A.C.M. Ran, eds., Proceedings of Signal Processing, Scattering and Operator Theory, and Numerical Methods. Birkhäuser, Basel, pp. 381–392

    Google Scholar 

  7. Golub, G.H., Van Loan, C.F. (1989): Matrix Computations, 2nd ed. Johns Hopkins University Press, Baltimore, Md.

    Google Scholar 

  8. Hager, W.W. (1984): Condition estimates. SIAM J. Sci. Statist. Comput.5, 311–316

    Google Scholar 

  9. Higham, D.J., Higham, N.J. (1992): Backward error and condition of structured linear systems. SIAM J. Matrix Anal. Appl.13, 162–175

    Google Scholar 

  10. Higham, D.J., Higham, N.J. (1992): Componentwise perturbation theory for linear systems with multiple right-hand sides. Linear Algebra Appl. (to appear)

  11. Higham, N.J. (1987): Error analysis of the Björck-Pereyra algorithms for solving Vandermonde systems. Numer. Math.50, 613–632

    Google Scholar 

  12. Higham, N.J. (1990): Stability analysis of algorithms for solving confluent Vandermonde-like systems. SIAM J. Matrix Anal. Appl.11, 23–41

    Google Scholar 

  13. Higham, N.J. (1988): FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation (Algorithm 674). ACM Trans. Math. Soft.14, 381–396

    Google Scholar 

  14. Higham, N.J. (1990): Computing error bounds for regression problems. In: P.J. Brown, W.A. Fuller, eds., Statistical Analysis of Measurement Error Models and Applications. Contemporary Mathematics 112. Amer. Math. Soc., pp. 195–208

  15. Horn, R.A., Johnson, C.R. (1985): Matrix Analysis. Cambridge University Press, Cambridge

    Google Scholar 

  16. Oettli, W., Prager, W. (1964): Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides. Numer. Math.6, 405–409

    Article  Google Scholar 

  17. Rohn, J. (1989): New condition numbers for matrices and linear systems. Computing41, 167–169

    Google Scholar 

  18. Skeel, R.D. (1979): Scaling for numerical stability in Gaussian elimination. J. Assoc. Comput. Mach.26, 494–526

    Google Scholar 

  19. Pham Ding Tao (1984): Convergence of a subgradient method for computing the bound norm of matrices. Linear Algebra Appl.62, 163–182 [in French]

    Google Scholar 

  20. Traub, J.F. (1966): Associated polynomials and uniform methods for the solution of linear problems. SIAM Review8, 277–301

    Google Scholar 

Download references

Author information

Author notes

  1. Sven G. Bartels

    Present address: Institut für Statistik und Mathematische Wirtschaftstheorie, Universität Karlsruhe, W-7500, Karlsruhe, Germany

Authors and Affiliations

  1. Department of Mathematics and Computer Science, University of Dundee, DD1 4HN, Dundee, Scotland

    Sven G. Bartels & Desmond J. Higham

Authors
  1. Sven G. Bartels
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Desmond J. Higham
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bartels, S.G., Higham, D.J. The structured sensitivity of Vandermonde-like systems. Numer. Math. 62, 17–33 (1992). https://doi.org/10.1007/BF01396218

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01396218

Mathematics Subject Classification (1991)

Search

Navigation