Other Triangular Factorizations

We have so far always chosen the diagonal elements of L to be 1, following Gaussian Elimination. We now remove this restriction and write the factorization equations for $k=1,2,\ldots ,n,$ in symmetric form as

      

u₁₁m₁₁ = a₁₁ (2.4)

$$a_{kk}-\sum _{t=1}^{k-1}m_{kt}u_{tk}, \quad k=2,3,\ldots ,n$$ u_kkm_kk = (2.5)

$$\frac{a_{1j}}{m_{11}},~ j=2,3,\ldots ,n$$ u_1j = (2.6)

$$\frac{1}{m_{kk}}( a_{kj}-\sum _{t=1}^{k-1}m_{kt}u_{tj}) \quad k=2,3,\ldots ,n;~ j=k+1,k+2,\ldots ,n$$ u_kj = (2.7)

$$\frac{a_{i1}}{u_{11}}, ~ i=2,3,\ldots ,n$$ m_i1 = (2.8)

$$\frac{1}{u_{kk}}( a_{ik}-\sum _{t=1}^{k-1}m_{it}u_{tk}) \quad k=2,3,\ldots ,n;~ i=k+1,k+2,\ldots ,n.$$ m_ik = (2.9)

At each stage we have a free choice of u_kk or m_kk. The only choice which might seem to offer an advantage is

$$u_{kk}=m_{kk}=\sqrt{a_{kk}-\sum _{t=1}^{k-1}m_{kt}u_{tk}}. \\$$ (2.10)

In practice, this choice is only used for real symmetric matrices, when it is known as Choleski's Method. The following theorem shows the potential advantage of the method.

Theorem 2.3.1   If $A\in \hbox{{\sf I}\kern-.15em\hbox{\sf R}}^{n\times n}$ is symmetric and can be factorized into LU, where L,U are lower and upper triangular factors respectively, and if their diagonals are chosen to be identical, then U=L^T and A=LL^T.

Proof.  (By induction on k).
Using (5.6) and (5.8), we find for $j=1,2,\ldots ,n$

$$u_{1j}=\frac{a_{1j}}{m_{11}}=\frac{a_{j1}}{u_{11}}=m_{j1}.$$

Now assume $u_{tj}=m_{jt},~ t=1,2,\ldots ,k-1;~ j=t+1,t+2,\ldots ,n$.
With the help of (5.7) and (5.9) we obtain for $j=k+1,k+2,\ldots ,n$

$$\begin{eqnarray*}u_{kj} & = & \frac{1}{m_{kk}}(a_{kj}-\sum _{t=1}^{k-1}m_{kt}u_{... ...}{u_{kk}}(a_{jk}-\sum _{t=1}^{k-1}u_{tk}m_{jt})\\ & = & m_{jk}. \end{eqnarray*}$$

Thus, for a real symmetric matrix we only need to calculate the elements of L or U, but we do have to compute square roots for the diagonal elements. The operational count for one right hand side is $\frac{n^3}{6}+\frac{3n^2}{2}+\frac{n}{3}+n$ square roots.

Example.  Factorize the matrix $\left[ \begin{array}{rrr}1 & 1 & 2\\ 1 & 0 & -1\\ 2 & -1 & -1\end{array} \right]$.

The factorization is

$$\left[ \begin{array}{rrr}1 & 0 & 0\\ 1 & i & 0\\ 2 & 3i & 2\e... ...ay}{rrr}1 & 1 & 2\\ 0 & i & 3i\\ 0 & 0 & 2\end{array} \right].$$

Note that the diagonal element and hence the other elements in the corresponding row of U can only be real or purely imaginary. Later elements are then formed from the products of real or imaginary elements, so that no complex numbers arise. We can even eliminate imaginary elements from A=LL^T by writing L=MD, where M is real and D is diagonal with entries 1 or i (since the columns of L are either real or pure imaginary). Then A=(MD)(MD)^T=(MD²)M^T=NM^T say, where N=MD² has the same columns as M apart possibly from the signs.Example.  We return to the previous example where

$$L=\left[ \begin{array}{rrr}1 & 0 & 0\\ 1 & i & 0\\ 2 & 3i & 2... ...}{rrr}1 & 0 & 0\\ 0 & i & 0\\ 0 & 0 & 1\end{array} \right]=MD.$$

Now

$$N=MD^2=\left[ \begin{array}{rrr}1 & 0 & 0\\ 1 & 1 & 0\\ 2 & 3... ...y}{rrr}1 & 0 & 0\\ 1 & -1 & 0\\ 2 & -3 & 2\end{array} \right].$$

There are two connected snags; we cannot use interchanges without destroying the symmetry, and because of this we may at some stage obtain a zero pivot, so that we cannot proceed at all. These snags are avoided if A is positive definite, and so the method is only usually used for such matrices.

Definition 2.3.2   A symmetric matrix $A\in \hbox{{\sf I}\kern-.15em\hbox{\sf R}}^{n\times n}$ is positive definite if $\mbox{\boldmath$\space x $ } ^TA\mbox{\boldmath$\space x $ } >0$ for all nonzero vectors $\mbox{\boldmath$\space x $ } \in \hbox{{\sf I}\kern-.15em\hbox{\sf R}}^n$.

Lemma 2.3.3   Let A_k be the matrix formed from the first k rows and columns of $A\in \hbox{{\sf I}\kern-.15em\hbox{\sf R}}^{n\times n}$. If A is positive definite then so is A_k for $k=1,2,\ldots ,n$.

Proof.  For arbitrary $\mbox{\boldmath$\space x $ } ^k=[x_1,x_2,\ldots ,x_k]^T\in \hbox{{\sf I}\kern-.15em\hbox{\sf R}}^k$ let $\mbox{\boldmath$\space x $ } =[x_1,x_2,\ldots ,x_k,0,\ldots ,0]^T\in \hbox{{\sf I}\kern-.15em\hbox{\sf R}}^n$. Then $(\mbox{\boldmath$\space x $ } ^k)^TA_k\mbox{\boldmath$\space x $ } ^k=\mbox{\boldmath$\space x $ } ^TA\mbox{\boldmath$\space x $ } >0$.

Theorem 2.3.4   If $A\in \hbox{{\sf I}\kern-.15em\hbox{\sf R}}^{n\times n}$ is symmetric and positive definite then the Choleski factorization exists and the factors are real.

Proof.  With L=[m_ij], we use induction, in which the kth inductive step consists of proving that m_kk²>0, so that the kth column of L is real.
By the lemma, A₁=[a₁₁] is positive definite, so that a₁₁x₁²>0 for all non zero x₁, which implies that m₁₁²=a₁₁>0, and so column 1 of L is real.
Suppose the Choleski decomposition exists and m_ii²>0 for $i=1,2,\ldots ,k-1$, so that the first k-1 columns of L are real. The equation A_k=L_kL_k^T displayed is

$$\left[ \begin{array}{lll}a_{11} & \cdots & a_{1k}\\ \vdots & ... ...ots \\ & & \cdot & \cdot \\ & & & m_{kk}\end{array} \right].$$

All elements of L_k are real, except possibly m_kk. Now choose $\mbox{\boldmath$\space x $ } ^k\in \hbox{{\sf I}\kern-.4em\hbox{\sf C}}^k$ so that $L_k^T\mbox{\boldmath$\space x $ } ^k=m_{kk}\mbox{\boldmath$\space e $ } _k$, or in displayed form

$$\left[ \begin{array}{llll}m_{11} & \ldots & \ldots & m_{k1}\\... ...[ \begin{array}{l}0\\ \vdots \\ 0\\ m_{kk}\end{array} \right].$$

If m_kk=0 we can choose $\mbox{\boldmath$\space x $ } ^k$ real and nonzero. Otherwise x_k=1 and other components of $\mbox{\boldmath$\space x $ } ^k$ are real by back-substitution. Hence $\mbox{\bf0}\not= \mbox{\boldmath$\space x $ } ^k\in \hbox{{\sf I}\kern-.15em\hbox{\sf R}}^k$.
Now

$$\begin{eqnarray*}0 & < & (\mbox{\boldmath$ x $ } ^k)^TA_k\mbox{\boldmath$ x $ } ... ...h$ x $ } ^k)^T(L_k^T\mbox{\boldmath$ x $ } ^k)\\ & = & m_{kk}^2. \end{eqnarray*}$$