Convergence of inexact inverse iteration with application to preconditioned iterative solves

MA Freitag, A Spence

Research output: Contribution to journalArticle

25 Citations (Scopus)
56 Downloads (Pure)

Abstract

In this paper we study inexact inverse iteration for solving the generalised eigenvalue problem A x=λM x. We show that inexact inverse iteration is a modified Newton method and hence obtain convergence rates for various versions of inexact inverse iteration for the calculation of an algebraically simple eigenvalue. In particular, if the inexact solves are carried out with a tolerance chosen proportional to the eigenvalue residual then quadratic convergence is achieved. We also show how modifying the right hand side in inverse iteration still provides a convergent method, but the rate of convergence will be quadratic only under certain conditions on the right hand side. We discuss the implications of this for the preconditioned iterative solution of the linear systems. Finally we introduce a new ILU preconditioner which is a simple modification to the usual preconditioner, but which has advantages both for the standard form of inverse iteration and for the version with a modified right hand side. Numerical examples are given to illustrate the theoretical results.
Original languageEnglish
Pages (from-to)27-44
Number of pages18
JournalBIT Numerical Mathematics
Volume47
Issue number1
DOIs
Publication statusPublished - Mar 2007

Fingerprint

Inverse Iteration
Newton-Raphson method
Linear systems
Preconditioner
Modified Newton Method
Eigenvalue
Generalized Eigenvalue Problem
Quadratic Convergence
Scientific notation
Iterative Solution
Tolerance
Convergence Rate
Rate of Convergence
Directly proportional
Linear Systems
Numerical Examples

Keywords

  • Preconditioned iterative methods
  • Newton’s method
  • Inverse iteration

Cite this

Convergence of inexact inverse iteration with application to preconditioned iterative solves. / Freitag, MA; Spence, A.

In: BIT Numerical Mathematics, Vol. 47, No. 1, 03.2007, p. 27-44.

Research output: Contribution to journalArticle

@article{11c17ba9111e40afb24b0f336470bafd,
title = "Convergence of inexact inverse iteration with application to preconditioned iterative solves",
abstract = "In this paper we study inexact inverse iteration for solving the generalised eigenvalue problem A x=λM x. We show that inexact inverse iteration is a modified Newton method and hence obtain convergence rates for various versions of inexact inverse iteration for the calculation of an algebraically simple eigenvalue. In particular, if the inexact solves are carried out with a tolerance chosen proportional to the eigenvalue residual then quadratic convergence is achieved. We also show how modifying the right hand side in inverse iteration still provides a convergent method, but the rate of convergence will be quadratic only under certain conditions on the right hand side. We discuss the implications of this for the preconditioned iterative solution of the linear systems. Finally we introduce a new ILU preconditioner which is a simple modification to the usual preconditioner, but which has advantages both for the standard form of inverse iteration and for the version with a modified right hand side. Numerical examples are given to illustrate the theoretical results.",
keywords = "Preconditioned iterative methods, Newton’s method, Inverse iteration",
author = "MA Freitag and A Spence",
year = "2007",
month = "3",
doi = "10.1007/s10543-006-0100-1",
language = "English",
volume = "47",
pages = "27--44",
journal = "BIT Numerical Mathematics",
issn = "0006-3835",
publisher = "Springer Netherlands",
number = "1",

}

TY - JOUR

T1 - Convergence of inexact inverse iteration with application to preconditioned iterative solves

AU - Freitag, MA

AU - Spence, A

PY - 2007/3

Y1 - 2007/3

N2 - In this paper we study inexact inverse iteration for solving the generalised eigenvalue problem A x=λM x. We show that inexact inverse iteration is a modified Newton method and hence obtain convergence rates for various versions of inexact inverse iteration for the calculation of an algebraically simple eigenvalue. In particular, if the inexact solves are carried out with a tolerance chosen proportional to the eigenvalue residual then quadratic convergence is achieved. We also show how modifying the right hand side in inverse iteration still provides a convergent method, but the rate of convergence will be quadratic only under certain conditions on the right hand side. We discuss the implications of this for the preconditioned iterative solution of the linear systems. Finally we introduce a new ILU preconditioner which is a simple modification to the usual preconditioner, but which has advantages both for the standard form of inverse iteration and for the version with a modified right hand side. Numerical examples are given to illustrate the theoretical results.

AB - In this paper we study inexact inverse iteration for solving the generalised eigenvalue problem A x=λM x. We show that inexact inverse iteration is a modified Newton method and hence obtain convergence rates for various versions of inexact inverse iteration for the calculation of an algebraically simple eigenvalue. In particular, if the inexact solves are carried out with a tolerance chosen proportional to the eigenvalue residual then quadratic convergence is achieved. We also show how modifying the right hand side in inverse iteration still provides a convergent method, but the rate of convergence will be quadratic only under certain conditions on the right hand side. We discuss the implications of this for the preconditioned iterative solution of the linear systems. Finally we introduce a new ILU preconditioner which is a simple modification to the usual preconditioner, but which has advantages both for the standard form of inverse iteration and for the version with a modified right hand side. Numerical examples are given to illustrate the theoretical results.

KW - Preconditioned iterative methods

KW - Newton’s method

KW - Inverse iteration

UR - http://www.springerlink.com/content/eg27mk213gr75061/

U2 - 10.1007/s10543-006-0100-1

DO - 10.1007/s10543-006-0100-1

M3 - Article

VL - 47

SP - 27

EP - 44

JO - BIT Numerical Mathematics

JF - BIT Numerical Mathematics

SN - 0006-3835

IS - 1

ER -