Abstract
In this paper we consider the variants of Gram–Schmidt such as Classical Gram–Schmidt and Modified Gram–Schmidt algorithms. It is shown that for problems of dimension more than two the round-off error of operation \({q_1}^Tq_2\) has more propagation in both of algorithms. To cure this difficulty we will present an algorithm, namely Optimized Modified Gram–Schmidt algorithm. Numerical examples indicate the accuracy of this algorithm. We show that this method can improve the loss of orthogonality of the orthogonalization in some ill-conditioned cases.
Similar content being viewed by others
References
Björck A (1996) Numerical methods for least squares problems. SIAM, Philadelphia
Björck A (1967) Solving linear least squares problems by Gram–Schmidt orthogonalization. BIT 7:1–21
Daniel JW, Gragg WB, Kaufman L, Stewart GW (1976) Reorthogonalization and stable algorithms for updating the Gram–Schmidt QR factorization. Math Comput 30:772–795
Giraud L, Langou J, Rozloznik M, van den Eshof J (2005) Rounding error analysis of the classical Gram–Schmidt orthogonalization process. Numerische Mathematik 101:87–100
Golub GH, Charles VL (1996) Matrix computations, 3rd edn. Johns Hopkins, ISBN 978-0-8018-5414-9
Higham N (1996) Accuracy and stability of numerical algorithms. SIAM, Philadelphia
Kahan W (1966) Numerical linear algebra. Can Math Bull 9:757–801
Laüchli P (1961) Jordan-Elimination und ausgleichung nach kleinsten quadraten. Numer Math 3:226–240
Lawson C, Hanson R (1995) Solving Least squares problems. Classics in Applied Mathematics, SIAM, Philadelphia. doi:10.1137/1.9781611971217.fm. ISBN:978-0-89871-356-5
Leon SJ, Björck A, Gander W (2013) GramSchmidt orthogonalization: 100 years and more. Numer Linear Algebra Appl 20:492–532
Meyer CD (2000) Matrix analysis and applied linear algebra. SIAM, Philadelphia, PA. ISBN:978-0-898714-54-8
Nishi T, Rump SM, Oishi S (2011) On the generation of very ill-conditioned integer matrices. IEICE Nonlinear Theory Appl 2(2):226–245
Rice JR (1966) Experiments on Gram–Schmidt orthogonalization. Math Comp 20:325–328
Schmidt E (1908) Über die Auflösung linearer gleichungen mit unendlich vielen unbekannten. Rend Circ Math Palermo Ser 25(1):53–77
Trefethen LN, Bau D III (1997) Numerical linear algebra. SIAM, Philadelphia
Wilkinson JH (1971) Modern error analysis. SIAM Rev 13:548–568
Acknowledgments
The authors are greatly thankful for the corrections and helpful comments of the anonymous referees.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Jinyun Yuan.
Rights and permissions
About this article
Cite this article
Rivaz, A., Moghadam, M.M., Sadeghi, D. et al. An approach of orthogonalization within the Gram–Schmidt algorithm. Comp. Appl. Math. 37, 1250–1262 (2018). https://doi.org/10.1007/s40314-016-0389-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40314-016-0389-6
Keywords
- Gram–Schmidt algorithm
- Loss of orthogonality
- Ill-conditioned matrix
- Optimized Gram–Schmidt algorithm
- Reorthogonalization