Componentwise perturbation theory for linear systems with multiple right-hand sides

D.J. Higham, N.J. Higham

Research output: Contribution to journalArticle

18 Citations (Scopus)

Abstract

Existing definitions of componentwise backward error and componentwise condition number for linear systems are extended to systems with multiple right-hand sides and to a general class of componentwise measure of perturbations involving Hölder p-norms. It is shown that for a system of order n with r right-hand sides, the componentwise backward error can be computed by finding the minimum p-norm solutions to n underdetermined linear systems, and an explicit expression is obtained in the case r = 1. A perturbation bound is derived, and from this the componentwise condition number is obtained to within a multiplicative constant. Applications of the results are discussed to invariant subspace computations, quasi-Newton methods based on multiple secant equations, and an inverse ODE problem.
Original languageEnglish
Pages (from-to)111-130
Number of pages19
JournalLinear Algebra and its Applications
Volume174
DOIs
Publication statusPublished - Sep 1992

Fingerprint

Backward Error
Condition number
Perturbation Theory
Linear systems
Linear Systems
Norm
Perturbation Bound
Quasi-Newton Method
Newton-Raphson method
Invariant Subspace
Chord or secant line
Inverse problems
Multiplicative
Perturbation
Class

Keywords

  • componentwise backward error
  • numerical mathematics
  • linear systems
  • Hölder p-norms

Cite this

@article{cee75774aa804ca191c9b5352de48251,
title = "Componentwise perturbation theory for linear systems with multiple right-hand sides",
abstract = "Existing definitions of componentwise backward error and componentwise condition number for linear systems are extended to systems with multiple right-hand sides and to a general class of componentwise measure of perturbations involving H{\"o}lder p-norms. It is shown that for a system of order n with r right-hand sides, the componentwise backward error can be computed by finding the minimum p-norm solutions to n underdetermined linear systems, and an explicit expression is obtained in the case r = 1. A perturbation bound is derived, and from this the componentwise condition number is obtained to within a multiplicative constant. Applications of the results are discussed to invariant subspace computations, quasi-Newton methods based on multiple secant equations, and an inverse ODE problem.",
keywords = "componentwise backward error, numerical mathematics, linear systems, H{\"o}lder p-norms",
author = "D.J. Higham and N.J. Higham",
year = "1992",
month = "9",
doi = "10.1016/0024-3795(92)90046-D",
language = "English",
volume = "174",
pages = "111--130",
journal = "Linear Algebra and its Applications",
issn = "0024-3795",

}

Componentwise perturbation theory for linear systems with multiple right-hand sides. / Higham, D.J.; Higham, N.J.

In: Linear Algebra and its Applications, Vol. 174, 09.1992, p. 111-130.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Componentwise perturbation theory for linear systems with multiple right-hand sides

AU - Higham, D.J.

AU - Higham, N.J.

PY - 1992/9

Y1 - 1992/9

N2 - Existing definitions of componentwise backward error and componentwise condition number for linear systems are extended to systems with multiple right-hand sides and to a general class of componentwise measure of perturbations involving Hölder p-norms. It is shown that for a system of order n with r right-hand sides, the componentwise backward error can be computed by finding the minimum p-norm solutions to n underdetermined linear systems, and an explicit expression is obtained in the case r = 1. A perturbation bound is derived, and from this the componentwise condition number is obtained to within a multiplicative constant. Applications of the results are discussed to invariant subspace computations, quasi-Newton methods based on multiple secant equations, and an inverse ODE problem.

AB - Existing definitions of componentwise backward error and componentwise condition number for linear systems are extended to systems with multiple right-hand sides and to a general class of componentwise measure of perturbations involving Hölder p-norms. It is shown that for a system of order n with r right-hand sides, the componentwise backward error can be computed by finding the minimum p-norm solutions to n underdetermined linear systems, and an explicit expression is obtained in the case r = 1. A perturbation bound is derived, and from this the componentwise condition number is obtained to within a multiplicative constant. Applications of the results are discussed to invariant subspace computations, quasi-Newton methods based on multiple secant equations, and an inverse ODE problem.

KW - componentwise backward error

KW - numerical mathematics

KW - linear systems

KW - Hölder p-norms

UR - http://dx.doi.org/10.1016/0024-3795(92)90046-D

U2 - 10.1016/0024-3795(92)90046-D

DO - 10.1016/0024-3795(92)90046-D

M3 - Article

VL - 174

SP - 111

EP - 130

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

SN - 0024-3795

ER -