A unified approach to some strategies for the treatment of breakdown in Lanczos-type algorithms

• Autorzy: A. El Guennouni
• Języki publikacji: EN

Abstrakty

EN

The Lanczos method for solving systems of linear equations is implemented by using some recurrence relationships between polynomials of a family of formal orthogonal polynomials or between those of two adjacent families of formal orthogonal polynomials. A division by zero can occur in these relations, thus producing a breakdown in the algorithm which has to be stopped. In this paper, three strategies to avoid this drawback are discussed: the MRZ and its variants, the normalized and unnormalized BIORES algorithm and the composite step biconjugate algorithm. We prove that all these algorithms can be derived from a unified framework; in fact, we give a formalism for finding all the recurrence relationships used in these algorithms, which shows that the three strategies use the same techniques.

Słowa kluczowe

EN

deficient polynomials; orthogonal polynomials; Lanczos method

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Applicationes Mathematicae
• Rocznik: 1999
• Tom: 26
• Numer: 4
• Strony: 477-488

Daty

wydano

1999

otrzymano

1999-05-11

poprawiono

1999-08-03

Twórcy

autor

A. El Guennouni

• Laboratoire d'Analyse Numérique et d'Optimisation, UFR IEEA-M3, Université des Sciences et Technologies, de Lille, F-59655 Villeneuve d'Ascq Cedex, France

Bibliografia

• [1] C. Brezinski and M. Redivo Zaglia, Breakdown in the computation of orthogonal polynomial, in: Nonlinear Numerical Methods and Rational Approximation, II, A. Cuyt (ed.), Kluwer, Dordrecht, 1994, 49-59.
• [2] C. Brezinski, M. Redivo Zaglia and H. Sadok, Avoiding breakdown and near-breakdown in Lanczos type algorithms, Numer. Algorithms 1 (1991), 261-284.
• [3] C. Brezinski, M. Redivo Zaglia and H. Sadok, Breakdown in the implementation of the Lanczos method for solving linear systems, Comput. Math. Appl. 33 (1997), 31-44.
• [4] C. Brezinski and H. Sadok, Lanczos-type algorithm for solving systems of linear equations, Appl. Numer. Math. 11 (1993), 443-473.
• [5] T. F. Chan and R. E. Bank, A composite step bi-conjugate gradient algorithm for solving nonsymmetric systems, Numer. Algorithms 7 (1994), 1-16.
• [6] T. F. Chan and R. E. Bank, An analysis of the composite step bi-conjugate gradient method, Numer. Math. 66 (1993), 295-319.
• [7] A. Draux, Polynômes orthogonaux formels, Lecture Notes in Math. 974, Springer, Berlin, 1983.
• [8] A. Draux, Formal orthogonal polynomials revisited. Applications, Numer. Algorithms 11 (1996), 143-158.
• [9] R. Fletcher, Conjugate gradient methods for indefinite systems, in: Numerical Analysis (Dundee, 1975), G. A. Watson (ed.), Lecture Notes in Math. 506, Springer, Berlin, 1976, 73-89.
• [10] M. H. Gutknecht, A completed theory of the unsymmetric Lanczos process and related algorithms. I, SIAM J. Matrix Anal. 13 (1992), 594-639.
• [11] C. Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bur. Standards 45 (1950), 255-282.
• [12] C. Lanczos, Solution of systems of linear equations by minimized iterations, ibid. 49 (1952), 33-53.