Backward error and condition of structured linear systems

Desmond J. Higham, Nicholas J. Higham

Research output: Contribution to journalArticle

Abstract

Existing definitions of backward error and condition number for linear systems do not cater to structure in the coefficient matrix, except possibly for sparsity. The definitions are extended so that when the coefficient matrix has structure the perturbed matrix has this structure too. It is shown that when the structure comprises linear dependence on a set of parameters, the structured componentwise backward error is given by the solution of minimal $infty $ -norm to an underdetermined linear system; an explicit expression for the condition number in this linear case is also obtained. Applications to symmetric matrices, Toeplitz matrices and the least squares problem are discussed and illustrated through numerical examples.
Original languageEnglish
Pages (from-to)162-175
Number of pages13
JournalSIAM Journal on Matrix Analysis and Applications
Volume13
Issue number1
DOIs
Publication statusPublished - 1992

Fingerprint

Backward Error
Linear Systems
Condition number
Linear dependence
Toeplitz matrix
Least Squares Problem
Coefficient
Sparsity
Symmetric matrix
Norm
Numerical Examples

Keywords

  • componentwise backward error
  • condition number
  • underdetermined system
  • symmetric matrix
  • Toeplitz matrix
  • least squares problem
  • augmented system
  • numerical mathematics

Cite this

Higham, Desmond J. ; Higham, Nicholas J. / Backward error and condition of structured linear systems. In: SIAM Journal on Matrix Analysis and Applications. 1992 ; Vol. 13, No. 1. pp. 162-175.
@article{6d4b7cdde21c4f31949731445dd2b22c,
title = "Backward error and condition of structured linear systems",
abstract = "Existing definitions of backward error and condition number for linear systems do not cater to structure in the coefficient matrix, except possibly for sparsity. The definitions are extended so that when the coefficient matrix has structure the perturbed matrix has this structure too. It is shown that when the structure comprises linear dependence on a set of parameters, the structured componentwise backward error is given by the solution of minimal $infty $ -norm to an underdetermined linear system; an explicit expression for the condition number in this linear case is also obtained. Applications to symmetric matrices, Toeplitz matrices and the least squares problem are discussed and illustrated through numerical examples.",
keywords = "componentwise backward error, condition number, underdetermined system, symmetric matrix, Toeplitz matrix, least squares problem, augmented system, numerical mathematics",
author = "Higham, {Desmond J.} and Higham, {Nicholas J.}",
year = "1992",
doi = "10.1137/0613014",
language = "English",
volume = "13",
pages = "162--175",
journal = "SIAM Journal on Matrix Analysis and Applications",
issn = "0895-4798",
number = "1",

}

Backward error and condition of structured linear systems. / Higham, Desmond J.; Higham, Nicholas J.

In: SIAM Journal on Matrix Analysis and Applications, Vol. 13, No. 1, 1992, p. 162-175.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Backward error and condition of structured linear systems

AU - Higham, Desmond J.

AU - Higham, Nicholas J.

PY - 1992

Y1 - 1992

N2 - Existing definitions of backward error and condition number for linear systems do not cater to structure in the coefficient matrix, except possibly for sparsity. The definitions are extended so that when the coefficient matrix has structure the perturbed matrix has this structure too. It is shown that when the structure comprises linear dependence on a set of parameters, the structured componentwise backward error is given by the solution of minimal $infty $ -norm to an underdetermined linear system; an explicit expression for the condition number in this linear case is also obtained. Applications to symmetric matrices, Toeplitz matrices and the least squares problem are discussed and illustrated through numerical examples.

AB - Existing definitions of backward error and condition number for linear systems do not cater to structure in the coefficient matrix, except possibly for sparsity. The definitions are extended so that when the coefficient matrix has structure the perturbed matrix has this structure too. It is shown that when the structure comprises linear dependence on a set of parameters, the structured componentwise backward error is given by the solution of minimal $infty $ -norm to an underdetermined linear system; an explicit expression for the condition number in this linear case is also obtained. Applications to symmetric matrices, Toeplitz matrices and the least squares problem are discussed and illustrated through numerical examples.

KW - componentwise backward error

KW - condition number

KW - underdetermined system

KW - symmetric matrix

KW - Toeplitz matrix

KW - least squares problem

KW - augmented system

KW - numerical mathematics

U2 - 10.1137/0613014

DO - 10.1137/0613014

M3 - Article

VL - 13

SP - 162

EP - 175

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

SN - 0895-4798

IS - 1

ER -