Inexact inverse iteration for generalized eigenvalue problems

Gene H. Golub; Qiang Ye

doi:10.1023/A:1022388317839

Inexact inverse iteration for generalized eigenvalue problems

Gene H. Golub, Qiang Ye

Research output: Contribution to journal › Article › peer-review

58 Scopus citations

Abstract

In this paper, we study an inexact inverse iteration with inner-outer iterations for solving the generalized eigenvalue problem Ax = λBx, and analyze how the accuracy in the inner iterations affects the convergence of the outer iterations. By considering a special stopping criterion depending on a threshold parameter, we show that the outer iteration converges linearly with the inner threshold parameter as the convergence rate. We also discuss the total amount of work and asymptotic equivalence between this stopping criterion and a more standard one. Numerical examples are given to illustrate the theoretical results.

Original language	English
Pages (from-to)	671-684
Number of pages	14
Journal	BIT Numerical Mathematics
Volume	40
Issue number	4
DOIs	https://doi.org/10.1023/A:1022388317839
State	Published - Dec 2000

Bibliographical note

Funding Information:
∗Received March 1999. Communicated by Lars Eldén. †Research supported in part by National Science Foundation Grant DMS-9403899. ‡Research supported by Natural Sciences and Engineering Research Council of Canada while this author was with University of Manitoba, Winnipeg, Canada.

Keywords

Inner-outer iterations
Inverse iteration
Shift-and-invert

ASJC Scopus subject areas

Software
Computer Networks and Communications
Computational Mathematics
Applied Mathematics

Access to Document

10.1023/A:1022388317839

Cite this

@article{d002b090b1af445580c63948fb776d58,

title = "Inexact inverse iteration for generalized eigenvalue problems",

abstract = "In this paper, we study an inexact inverse iteration with inner-outer iterations for solving the generalized eigenvalue problem Ax = λBx, and analyze how the accuracy in the inner iterations affects the convergence of the outer iterations. By considering a special stopping criterion depending on a threshold parameter, we show that the outer iteration converges linearly with the inner threshold parameter as the convergence rate. We also discuss the total amount of work and asymptotic equivalence between this stopping criterion and a more standard one. Numerical examples are given to illustrate the theoretical results.",

keywords = "Inner-outer iterations, Inverse iteration, Shift-and-invert",

author = "Golub, {Gene H.} and Qiang Ye",

note = "Funding Information: ∗Received March 1999. Communicated by Lars Eld{\'e}n. †Research supported in part by National Science Foundation Grant DMS-9403899. ‡Research supported by Natural Sciences and Engineering Research Council of Canada while this author was with University of Manitoba, Winnipeg, Canada.",

year = "2000",

month = dec,

doi = "10.1023/A:1022388317839",

language = "English",

volume = "40",

pages = "671--684",

number = "4",

}

TY - JOUR

T1 - Inexact inverse iteration for generalized eigenvalue problems

AU - Golub, Gene H.

AU - Ye, Qiang

N1 - Funding Information: ∗Received March 1999. Communicated by Lars Eldén. †Research supported in part by National Science Foundation Grant DMS-9403899. ‡Research supported by Natural Sciences and Engineering Research Council of Canada while this author was with University of Manitoba, Winnipeg, Canada.

PY - 2000/12

Y1 - 2000/12

N2 - In this paper, we study an inexact inverse iteration with inner-outer iterations for solving the generalized eigenvalue problem Ax = λBx, and analyze how the accuracy in the inner iterations affects the convergence of the outer iterations. By considering a special stopping criterion depending on a threshold parameter, we show that the outer iteration converges linearly with the inner threshold parameter as the convergence rate. We also discuss the total amount of work and asymptotic equivalence between this stopping criterion and a more standard one. Numerical examples are given to illustrate the theoretical results.

AB - In this paper, we study an inexact inverse iteration with inner-outer iterations for solving the generalized eigenvalue problem Ax = λBx, and analyze how the accuracy in the inner iterations affects the convergence of the outer iterations. By considering a special stopping criterion depending on a threshold parameter, we show that the outer iteration converges linearly with the inner threshold parameter as the convergence rate. We also discuss the total amount of work and asymptotic equivalence between this stopping criterion and a more standard one. Numerical examples are given to illustrate the theoretical results.

KW - Inner-outer iterations

KW - Inverse iteration

KW - Shift-and-invert

UR - http://www.scopus.com/inward/record.url?scp=0041730764&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0041730764&partnerID=8YFLogxK

U2 - 10.1023/A:1022388317839

DO - 10.1023/A:1022388317839

M3 - Article

AN - SCOPUS:0041730764

SN - 0006-3835

VL - 40

SP - 671

EP - 684

JO - BIT Numerical Mathematics

JF - BIT Numerical Mathematics

IS - 4

ER -

Inexact inverse iteration for generalized eigenvalue problems

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this