Next: Inversion of the Hessian
Up: Least-squares solution of the
Previous: Least-squares solution of the
Let us define the
block matrix M as follows:
| ![\begin{displaymath}
{\bf M}=
\left( \begin{array}
{cc}
{\bf A} & {\bf B} \\ {\bf C} & {\bf D}\end{array}\right),\end{displaymath}](img269.gif) |
(87) |
where A, B, C, and D are matrices.
First, we consider the matrix equation
| ![\begin{displaymath}
\left( \begin{array}
{cc}
{\bf A} & {\bf B} \\ {\bf C} & ...
...eft( \begin{array}
{c}
{\bf G} \\ {\bf H}\end{array}\right).\end{displaymath}](img270.gif) |
(88) |
If we multiply the top row by
and add it to the bottom,
we have
| ![\begin{displaymath}
({\bf D} - {\bf CA^{-1}B}){\bf F} = {\bf H} - {\bf CA^{-1}G}.\end{displaymath}](img272.gif) |
(89) |
Then we can easily find F and E. The quantity
is called the Schur complement of A and,
denoted as
, appears often in linear algebra Demmel (1997).
The derivation of F and E can be written in a matrix form
| ![\begin{displaymath}
\left( \begin{array}
{cc}
{\bf A} & {\bf B} \\ {\bf C} & ...
...\bf I} & {\bf A^{-1}B} \\ {\bf 0} & {\bf I}\end{array}\right),\end{displaymath}](img275.gif) |
(90) |
which resembles an LDU decomposition of M.
Alternatively, we have the UDL decomposition
| ![\begin{displaymath}
\left( \begin{array}
{cc}
{\bf A} & {\bf B} \\ {\bf C} & ...
...\bf I} & {\bf 0} \\ {\bf D^{-1}C} & {\bf I}\end{array}\right),\end{displaymath}](img276.gif) |
(91) |
where
is the Schur complement of
D.
The inversion formulas are then easy to derive as follows:
| ![\begin{displaymath}
\left( \begin{array}
{cc}
{\bf A} & {\bf B} \\ {\bf C} & ...
...\bf I} & {\bf 0} \\ {\bf -CA^{-1}} & {\bf I}\end{array}\right)\end{displaymath}](img278.gif) |
(92) |
and
| ![\begin{displaymath}
\left( \begin{array}
{cc}
{\bf A} & {\bf B} \\ {\bf C} & ...
...bf I} & {\bf -BD^{-1}} \\ {\bf 0} & {\bf I}\end{array}\right).\end{displaymath}](img279.gif) |
(93) |
The decomposition of the matrix M offers opportunities for
fast inversion algorithms. The final expressions for M are
| ![\begin{displaymath}
\left( \begin{array}
{cc}
{\bf A} & {\bf B} \\ {\bf C} & ...
...} \\ -{\bf S_A^{-1}CA^{-1}} & {\bf S_A^{-1}}\end{array}\right)\end{displaymath}](img280.gif) |
(94) |
and
| ![\begin{displaymath}
\left( \begin{array}
{cc}
{\bf A} & {\bf B} \\ {\bf C} & ...
...[{\bf D^{-1}}+{\bf
D^{-1}CS_D^{-1}BD^{-1}}]\end{array}\right).\end{displaymath}](img281.gif) |
(95) |
Equations (
) and (
) yield the matrix inversion lemma
| ![\begin{displaymath}
({\bf A} - {\bf BD^{-1}C})^{-1} =
{\bf A^{-1}}+{\bf A^{-1}B({\bf D} - {\bf CA^{-1}B})^{-1}CA^{-1}}.\end{displaymath}](img282.gif) |
(96) |
Next: Inversion of the Hessian
Up: Least-squares solution of the
Previous: Least-squares solution of the
Stanford Exploration Project
5/5/2005