Analysis of the finite precision bi-conjugate gradient algorithm for nonsymmetric linear systems |
| |
Authors: | Charles H. Tong Qiang Ye. |
| |
Affiliation: | Sandia National Laboratories, Livermore, CA 94551 ; Department of Mathematics, University of Manitoba, Winnipeg, Manitoba, Canada R3T 2N2 |
| |
Abstract: | In this paper we analyze the bi-conjugate gradient algorithm in finite precision arithmetic, and suggest reasons for its often observed robustness. By using a tridiagonal structure, which is preserved by the finite precision bi-conjugate gradient iteration, we are able to bound its residual norm by a minimum polynomial of a perturbed matrix (i.e. the residual norm of the exact GMRES applied to a perturbed matrix) multiplied by an amplification factor. This shows that occurrence of near-breakdowns or loss of biorthogonality does not necessarily deter convergence of the residuals provided that the amplification factor remains bounded. Numerical examples are given to gain insights into these bounds. |
| |
Keywords: | Bi-conjugate gradient algorithm error analysis convergence analysis nonsymmetric linear systems |
|
| 点击此处可从《Mathematics of Computation》浏览原始摘要信息 |
|
点击此处可从《Mathematics of Computation》下载全文 |