Remarks on the Unitary Triangularization of a Nonsymmetric MatrixRemarks on the Unitary Triangularization of a Nonsymmetric Matrix

Access Restriction
Subscribed

 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

Source: ACM Digital Library