Square Root Method

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

$${\hbox{\sf A}}{\bf u}={\bf g}$$ (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

$${\hbox{\sf T}}^{\rm T}{\hbox{\sf T}}={\hbox{\sf A}},$$ (2)

where ${\hbox{\sf T}}^{\rm T}$ is the Matrix Transpose. Then

$${\hbox{\sf T}}^{\rm T}{\bf k} = {\bf g}$$ (3)

$${\hbox{\sf T}}{\bf u} = {\bf k},$$ (4)

so

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

giving the equations

$${s_{11}}^2 = a_{11}$$

$$s_{11}s_{12} = a_{12}$$

$${s_{12}}^2+{s_{22}}^2 = a_{22}$$

$${s_{1j}}^2+{s_{2j}}^2+\ldots+{s_{jj}}^2 = a_{jj}$$

$$s_{1j}+s_{2j}s_{2k}+\ldots+s_{jj}s_{jk} = a_{jk}.$$ (6)

These give

$$s_{11} = \sqrt{a_{11}}$$

$$s_{12} = {a_{12}\over s_{11}}$$

$$s_{22} = \sqrt{a_{22}-{s_{12}}^2}$$

$$s_{jj} = \sqrt{a_{jj}-{s_{ij}}^2-{s_{2j}}^2-\ldots-{s_{j-1,j}}^2}$$

$$s_{jk} = {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,

$$s_{11}k_1 = g_1$$

$$s_{12}k_1+s_{22}k_2 = g_2$$

$$s_{1j}k_1+s_{2j}k_2+\ldots+s_{jj}k_j = g_j,$$ (8)

which gives

$$k_1 = {g_1\over s_{11}}$$

$$k_2 = {g_2-s_{12}k_1\over s_{22}}$$

$$k_j = {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,

$$s_{11}u_1+s_{12}u_2\ldots+s_{1p}u_p = k_1$$

$$s_{22}u_2+\ldots+s_{2p}u_p = k_2$$

$$s_{pp}u_p = k_p,$$ (10)

giving the desired solution,

$$u_p = {k_p\over s_{pp}}$$

$$u_{p-1} = {k_{p-1}-s_{p-1,p}u_p\over s_{p-1,p-1}}$$

$$u_j = {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.