Access Restriction

Author Morrison, David D.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1960
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract In [1], A. Householder described a method for the unitary triangularization of a matrix. The formulas given there are valid for the real case. In this note we describe the modifications to handle the complex case and also point out a small modification in the real case which will improve the numerical accuracy of the method.At first we are concerned with a complex vector space. The basic tool is the fact that if ‖ $\textit{u}$ ‖ = √2, then the matrix $\textit{I}$ - $\textit{uu}*$ is unitary, as may be readily verified.The following lemma is a modification of the one give in [1].LEMMA. Let a ≠ 0 be an arbitrary vector and let v be an arbitrary unit vector. Then there exists a vector u with ‖ $\textit{u}$ ‖ = √2 and a scalar &zgr; with | $\textit{&zgr;}$ | = 1 such that $(\textit{I}$ - $\textit{uu}*)\textit{a}$ = $\textit{&zgr;}$ ‖ $\textit{a}$ ‖ $\textit{v}.$ (1) PROOF: Letting $\textit{α}$ = ‖ $\textit{a}$ ‖ and $\textit{μ}$ = $\textit{u}*\textit{a},$ (1) may be written $\textit{a}$ - $\textit{α&zgr;v}$ = $\textit{μu}.$ (2) Multiply by $\textit{a}*$ gives $\textit{α}2$ - $\textit{α&zgr;a}*\textit{v}$ = $\textit{μa}*\textit{u}$ = ‖ $\textit{μ}$ ‖2. (3) It follows that $\textit{&zgr;a}*\textit{v}$ is real. Assuming for the moment that $\textit{a}*\textit{v}$ ≠ 0, we write it in polar form $\textit{a}*\textit{v}$ = $\textit{rw},$ $\textit{r}$ > 0, ‖ $\textit{w}$ ‖ = 1. Then the fact that $\textit{&zgr;rw}$ is real implies that $\textit{&zgr;}$ = ± $\textit{w}.$ (4) Substituting into (3) gives ‖ $\textit{μ}$ ‖2 = $\textit{α}2$ ∓ $\textit{αr}.$ (5) We now set, arbitrarily, arg $(\textit{μ})$ = 0. Then $\textit{μ}$ = $√\textit{α}(\textit{α}$ ∓ $\textit{r}).$ (6) Next, we select the negative sign in (4) in order to avoid the subtraction of two positive quantities in (6), since such a subtraction may give rise to numerical difficulties. Collecting the formulas, we see that the following sequence of computations will produce the required $\textit{u}$ and $\textit{&zgr;}:$ $\textit{α}$ = ‖ $\textit{a}$ ‖ (7) $\textit{r}$ = ‖ $\textit{a}*\textit{v}$ ‖ (8) $\textit{&zgr;}$ = $-\textit{a}*\textit{v}/\textit{r}$ (9) $\textit{μ}$ = √ $\textit{α}(\textit{α}$ + $\textit{r})$ (10) $\textit{u}$ = $1/\textit{μ}(\textit{a}$ - $\textit{&zgr;αv}).$ (11) The case $\textit{a}*\textit{v}$ = 0 may be handled if, instead of using (9), we let $\textit{&zgr;}$ be an arbitrary number with ‖ $\textit{&zgr;}$ ‖ = 1. It is easily verified that the formulas thus modified will still work.The computation requires 3 square roots to compare $\textit{α},$ $\textit{r},$ and $\textit{μ}.$ A slight modification [1] permits one to avoid the root required to compute $\textit{μ}.$ In the real case, no root is required to compute $\textit{r}.Now$ consider the case of a real vector space. The formulas given [1] for this case are essentially the same as ours except that (8) is replaced by $\textit{r}$ = $\textit{a}*\textit{v},$ and (10) by $\textit{μ}$ = $√\textit{α}(\textit{α}$ - $\textit{r}).$ If $\textit{μ}$ is computed this way and if $\textit{r}$ is positive and near $\textit{α}$ (as is the case when $\textit{v}$ is near $\textit{a}/\textit{α}),$ cancellation of significant digits will occur. This difficulty, and the need for making a special case when $\textit{v}$ is exactly $\textit{a}/\textit{α},$ is avoided in the present set of formulas.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1960-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 7
Issue Number 2
Page Count 2
Starting Page 185
Ending Page 186

Open content in new tab

   Open content in new tab
Source: ACM Digital Library