hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox Chapter Introduction

F05 — Orthogonalization

Scope of the Chapter

This chapter is concerned with the orthogonalization of vectors in a finite dimensional space.

Background to the Problems

Let a1,a2,,ana1,a2,,an be a set of nn linearly independent vectors in mm-dimensional space; mnmn.
We wish to construct a set of nn vectors q1,q2,,qnq1,q2,,qn such that:

Gram–Schmidt Orthogonalization

The classical Gram–Schmidt orthogonalization process is described in many textbooks; see for example Chapter 5 of Golub and Van Loan (1996).
It constructs the orthonormal set progressively. Suppose it has computed orthonormal vectors q1,q2,,qkq1,q2,,qk which orthogonalise the first kk vectors a1,a2,,aka1,a2,,ak. It then uses ak + 1ak+1 to compute qk + 1qk+1 as follows:
zk + 1 =
k
ak + 1(qiTak + 1)qi
i = 1
qk + 1 = zk + 1 / zk + 12.
zk+1 = ak+1-i=1k( qiT ak+1)qi qk+1 = zk+1 /zk+12.
In finite precision computation, this process can result in a set of vectors {qi}{qi} which are far from being orthogonal. This is caused by |zk + 1||zk+1| being small compared with |ak + 1||ak+1|. If this situation is detected, it can be remedied by reorthogonalising the computed qk + 1qk+1 against q1,q2,,qkq1,q2,,qk, that is, repeating the process with the computed qk + 1qk+1 instead of ak + 1ak+1. See Danial et al. (1976).

Householder Orthogonalization

An alternative approach to orthogonalising a set of vectors is based on the QRQR factorization (see the F08 Chapter Introduction), which is usually performed by Householder's method. See Chapter 5 of Golub and Van Loan (1996).
Let AA be the mm by nn matrix whose columns are the nn vectors to be orthogonalised. The QRQR factorization gives
A = QR
A=QR
where RR is an nn by nn upper triangular matrix and QQ is an mm by nn matrix, whose columns are the required orthonormal set.
Moreover, for any kk such that 1kn1kn, the first kk columns of QQ are an orthonormal basis for the first kk columns of AA.
Householder's method requires twice as much work as the Gram–Schmidt method, provided that no re-orthogonalization is required in the latter. However, it has satisfactory numerical properties and yields vectors which are close to orthogonality even when the original vectors aiai are close to being linearly dependent.

Recommendations on Choice and Use of Available Functions

The single function in this chapter, nag_orthog_real_gram_schmidt (f05aa), uses the Gram–Schmidt method, with re-orthogonalization to ensure that the computed vectors are close to being exactly orthogonal. This method is only available for real vectors.
To apply Householder's method, you must use functions in Chapter F08:
for real vectors: nag_lapack_dgeqrf (f08ae), followed by nag_lapack_dorgqr (f08af)
for complex vectors: nag_lapack_zgeqrf (f08as), followed by nag_lapack_zungqr (f08at)
The example programs for nag_lapack_dgeqrf (f08ae) or nag_lapack_zgeqrf (f08as) illustrate the necessary calls to these functions.

References

Danial J W, Gragg W B, Kaufman L and Stewart G W (1976) Reorthogonalization and stable algorithms for updating the Gram–Schmidt QRQR factorization Math. Comput. 30 772–795
Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2013