NAG Library Chapter Introduction

F05 – Orthogonalization

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

Let $a_1,a_2,\dots ,a_n$ be a set of $n$ linearly independent vectors in $m$-dimensional space; $m\ge n$.

We wish to construct a set of $n$ vectors $q_1,q_2,\dots ,q_n$ such that:

• – the vectors $\left\{q_i\right\}$ form an orthonormal set; that is, $q_i^{\mathrm{T}}{q}_j=0$ for $i\ne j$, and ${‖q_i‖}_2=1$;
• – each $a_i$ is linearly dependent on the set $\left\{q_i\right\}$.

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 $q_1,q_2,\dots ,q_k$ which orthogonalise the first $k$ vectors $a_1,a_2,\dots ,a_k$. It then uses $a_{k+1}$ to compute $q_{k+1}$ as follows: In finite precision computation, this process can result in a set of vectors $\left\{q_i\right\}$ which are far from being orthogonal. This is caused by $\left|z_{k+1}\right|$ being small compared with $\left|a_{k+1}\right|$. If this situation is detected, it can be remedied by reorthogonalising the computed $q_{k+1}$ against $q_1,q_2,\dots ,q_k$, that is, repeating the process with the computed $q_{k+1}$ instead of $a_{k+1}$. See Danial et al. (1976).

An alternative approach to orthogonalising a set of vectors is based on the $QR$ factorization (see the F08 Chapter Introduction), which is usually performed by Householder's method. See Chapter 5 of Golub and Van Loan (1996).

Let $A$ be the $m$ by $n$ matrix whose columns are the $n$ vectors to be orthogonalised. The $QR$ factorization gives where $R$ is an $n$ by $n$ upper triangular matrix and $Q$ is an $m$ by $n$ matrix, whose columns are the required orthonormal set.

Moreover, for any $k$ such that $1\le k\le n$, the first $k$ columns of $Q$ are an orthonormal basis for the first $k$ columns of $A$.

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 $a_i$ are close to being linearly dependent.

The single routine in this chapter, F05AAF, 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 routines in Chapter F08:

for real vectors:	F08AEF (DGEQRF), followed by F08AFF (DORGQR)
for complex vectors:	F08ASF (ZGEQRF), followed by F08ATF (ZUNGQR)

The example programs for F08AEF (DGEQRF) or F08ASF (ZGEQRF) illustrate the necessary calls to these routines.

None.

Danial J W, Gragg W B, Kaufman L and Stewart G W (1976) Reorthogonalization and stable algorithms for updating the Gram–Schmidt $QR$ factorization Math. Comput. 30 772–795

Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore