On the Forward Instability of the QR Transformation,

Abstract

This study is in the area of matrix eigenvalue computations The Householder-QR algorithm has become the standard method for diagonalizing a symmetric matrix. First the matrix is reduced to tridiagonal form T by a technique introduced by A. Householder in 1958. Next the tridiagonal matrix T is diagonalized by successive applications of the QR transformation with shifts Moreover it is well known that the QR transformation is backward stable. That means that the computed transform is exactly orthogonally similar to a matrix close to the old one. It is also known to the experts that the QR transformation sometimes exhibits forward instability. That means the the computed output is far from the result obtained with exact arithmetic. For the purpose of computing eigenvalues and eigenvectors the property of backward stability is all that one requires. However the QR transformation has other uses and in some cases forward stability is desirable. This report analyzes the forward instability of QR and shows that it occurs only when the shift is very close to eigenvalues with a special property. (kr)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1988
Accession Number
ADA206865

Entities

People

  • Beresford N. Parlett
  • Jia‐Liang Le

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Arithmetic
  • Computations
  • Eigenvalues
  • Eigenvectors
  • Equations
  • Errors
  • Inequalities
  • Mathematics
  • Notation
  • Perturbations
  • Precision
  • Rotation
  • Sequences
  • Standards
  • Theorems

Readers

  • Linear Algebra