info prev up next book cdrom email home

Square Root Method

The square root method is an algorithm which solves the Matrix Equation

\begin{displaymath}
{\hbox{\sf A}}{\bf u}={\bf g}
\end{displaymath} (1)

for ${\bf u}$, with ${\hbox{\sf A}}$ a $p\times p$ Symmetric Matrix and g a given Vector. Convert ${\hbox{\sf A}}$ to a Triangular Matrix such that
\begin{displaymath}
{\hbox{\sf T}}^{\rm T}{\hbox{\sf T}}={\hbox{\sf A}},
\end{displaymath} (2)

where ${\hbox{\sf T}}^{\rm T}$ is the Matrix Transpose. Then
$\displaystyle {\hbox{\sf T}}^{\rm T}{\bf k}$ $\textstyle =$ $\displaystyle {\bf g}$ (3)
$\displaystyle {\hbox{\sf T}}{\bf u}$ $\textstyle =$ $\displaystyle {\bf k},$ (4)

so
\begin{displaymath}
{\hbox{\sf T}}=\left[{\matrix{
s_{11} & s_{12} & \cdots & \...
...ots & \ddots & \vdots\cr
0 & 0 & \cdots & s_{pp}\cr}}\right],
\end{displaymath} (5)

giving the equations
$\displaystyle {s_{11}}^2$ $\textstyle =$ $\displaystyle a_{11}$  
$\displaystyle s_{11}s_{12}$ $\textstyle =$ $\displaystyle a_{12}$  
$\displaystyle {s_{12}}^2+{s_{22}}^2$ $\textstyle =$ $\displaystyle a_{22}$  
$\displaystyle {s_{1j}}^2+{s_{2j}}^2+\ldots+{s_{jj}}^2$ $\textstyle =$ $\displaystyle a_{jj}$  
$\displaystyle s_{1j}+s_{2j}s_{2k}+\ldots+s_{jj}s_{jk}$ $\textstyle =$ $\displaystyle a_{jk}.$ (6)

These give
$\displaystyle s_{11}$ $\textstyle =$ $\displaystyle \sqrt{a_{11}}$  
$\displaystyle s_{12}$ $\textstyle =$ $\displaystyle {a_{12}\over s_{11}}$  
$\displaystyle s_{22}$ $\textstyle =$ $\displaystyle \sqrt{a_{22}-{s_{12}}^2}$  
$\displaystyle s_{jj}$ $\textstyle =$ $\displaystyle \sqrt{a_{jj}-{s_{ij}}^2-{s_{2j}}^2-\ldots-{s_{j-1,j}}^2}$  
$\displaystyle s_{jk}$ $\textstyle =$ $\displaystyle {a_{jk}-s_{1j}s_{1k}-s_{2j}s_{2k}-\ldots-s_{j-1,j}s_{j-1,k}\over s_{jj}},$ (7)

giving ${\hbox{\sf T}}$ from A. Now solve for k in terms of the $s_{ij}$s and g,
$\displaystyle s_{11}k_1$ $\textstyle =$ $\displaystyle g_1$  
$\displaystyle s_{12}k_1+s_{22}k_2$ $\textstyle =$ $\displaystyle g_2$  
$\displaystyle s_{1j}k_1+s_{2j}k_2+\ldots+s_{jj}k_j$ $\textstyle =$ $\displaystyle g_j,$ (8)

which gives
$\displaystyle k_1$ $\textstyle =$ $\displaystyle {g_1\over s_{11}}$  
$\displaystyle k_2$ $\textstyle =$ $\displaystyle {g_2-s_{12}k_1\over s_{22}}$  
$\displaystyle k_j$ $\textstyle =$ $\displaystyle {g_j-s_{1j}k_1-s_{2j}k_2-\ldots-s_{j-1,j}k_{j-1}\over s_{jj}}.$ (9)

Finally, find ${\bf u}$ from the $s_{ij}$s and k,
$\displaystyle s_{11}u_1+s_{12}u_2\ldots+s_{1p}u_p$ $\textstyle =$ $\displaystyle k_1$  
$\displaystyle s_{22}u_2+\ldots+s_{2p}u_p$ $\textstyle =$ $\displaystyle k_2$  
$\displaystyle s_{pp}u_p$ $\textstyle =$ $\displaystyle k_p,$ (10)

giving the desired solution,
$\displaystyle u_p$ $\textstyle =$ $\displaystyle {k_p\over s_{pp}}$  
$\displaystyle u_{p-1}$ $\textstyle =$ $\displaystyle {k_{p-1}-s_{p-1,p}u_p\over s_{p-1,p-1}}$  
$\displaystyle u_j$ $\textstyle =$ $\displaystyle {k_j-s_{j,j+1}u_{j+1}-s_{j,j+2}u_{j+2}-\ldots-s_{jp}u_p\over s_{jj}}.$  
      (11)

See also LU Decomposition


References

Kenney, J. F. and Keeping, E. S. Mathematics of Statistics, Pt. 2, 2nd ed. Princeton, NJ: Van Nostrand, pp. 298-300, 1951.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26