Namespaces
Variants
Actions

Difference between revisions of "Bordering method"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
A method for solving a system of linear algebraic equations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b0170101.png" /> with a non-degenerate matrix by inverting a matrix and calculating a determinant, based on passing recursively from the solution of the problem with matrix
+
<!--
 +
b0170101.png
 +
$#A+1 = 61 n = 0
 +
$#C+1 = 61 : ~/encyclopedia/old_files/data/B017/B.0107010 Bordering method
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b0170102.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
to the solution of the problem with the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b0170103.png" />, which can be considered as the result of bordering <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b0170104.png" />.
+
A method for solving a system of linear algebraic equations  $  Ax = b $
 +
with a non-degenerate matrix by inverting a matrix and calculating a determinant, based on passing recursively from the solution of the problem with matrix
  
The calculating scheme of the bordering method for the inversion of a matrix is as follows: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b0170105.png" /> be a non-degenerate matrix. In the inversion of the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b0170106.png" />, the representation
+
$$
 +
A _ {k-1}  = \left \|
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b0170107.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
\begin{array}{lcl}
 +
a _ {1,1}  &\dots  &a _ {1, k - 1 }  \\
 +
\dots  &\dots  &\dots  \\
 +
a _ {k-1,1}  &\dots  &a _ {k-1,k-1}  \\
 +
\end{array}
  
is used, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b0170108.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b0170109.png" />. Then
+
\right \| ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701010.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
to the solution of the problem with the matrix  $  A _ {k} $,
 +
which can be considered as the result of bordering  $  A _ {k-1} $.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701011.png" /></td> </tr></table>
+
The calculating scheme of the bordering method for the inversion of a matrix is as follows: Let  $  A _ {k-1} $
 +
be a non-degenerate matrix. In the inversion of the matrix  $  A _ {k} $,
 +
the representation
  
Subsequent inversion of the matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701012.png" /> by this scheme gives the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701013.png" />.
+
$$ \tag{1 }
 +
A _ {k}  = \left \|
  
The above scheme of the bordering method is only applicable to matrices with principal minors unequal to zero. Generally, a choice of the principal element is adopted. In this scheme, the bordering rows and columns used are those for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701014.png" /> has the maximum absolute value. The calculated matrix will then differ from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701015.png" /> only in the rearrangement of the rows and columns [[#References|[1]]].
+
\begin{array}{cc}
 +
A _ {k-1}  &u _ {k}  \\
 +
v _ {k}  &a _ {kk}  \\
 +
\end{array}
 +
 
 +
\right \|
 +
$$
 +
 
 +
is used, where  $  u _ {k} = (a _ {1,k} \dots a _ {k+1,k} )  ^ {T} $
 +
and  $  v _ {k} = (a _ {k,1} \dots a _ {k,k-1} ) $.
 +
Then
 +
 
 +
$$ \tag{2 }
 +
A _ {k}  ^ {-1}  =  \left \|
 +
 
 +
\begin{array}{cc}
 +
A _ {k-1}  ^ {-1} +
 +
 
 +
\frac{A _ {k-1}  ^ {-1} u _ {k} v _ {k} A _ {k-1}  ^ {-1} }{\alpha _ {k} }
 +
  & -
 +
\frac{A _ {k-1}  ^ {-1} u _ {k} }{\alpha _ {k} }
 +
  \\
 +
-
 +
\frac{v _ {k} A _ {k-1}  ^ {-1} }{\alpha _ {k} }
 +
  &
 +
\frac{1}{\alpha _ {k} }
 +
  \\
 +
\end{array}
 +
 
 +
\right \| ,
 +
$$
 +
 
 +
$$
 +
\alpha _ {k}  =  a _ {kk} - v _ {k} A _ {k-1}  ^ {-1} u _ {k} .
 +
$$
 +
 
 +
Subsequent inversion of the matrices  $  A _ {1} \dots A _ {n} $
 +
by this scheme gives the matrix  $  A  ^ {-1} $.
 +
 
 +
The above scheme of the bordering method is only applicable to matrices with principal minors unequal to zero. Generally, a choice of the principal element is adopted. In this scheme, the bordering rows and columns used are those for which $  \alpha _ {k} = a _ {kk} -v _ {k} A _ {k-1}  ^ {-1} u _ {k} $
 +
has the maximum absolute value. The calculated matrix will then differ from $  A  ^ {-1} $
 +
only in the rearrangement of the rows and columns [[#References|[1]]].
  
 
The bordering method is not the fastest of the direct methods of [[Inversion of a matrix|inversion of a matrix]].
 
The bordering method is not the fastest of the direct methods of [[Inversion of a matrix|inversion of a matrix]].
  
The bordering method permits an effective inversion of a triangular matrix. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701016.png" /> is a right (upper-) triangular matrix, then in (1)
+
The bordering method permits an effective inversion of a triangular matrix. If $  A _ {k} $
 +
is a right (upper-) triangular matrix, then in (1)
 +
 
 +
$$
 +
v _ {k}  =  0 \  \textrm{ and } \  A _ {k}  ^ {-1}  =  \left \|
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701017.png" /></td> </tr></table>
+
\begin{array}{cc}
 +
A _ {k-1}  ^ {-1}  &-
 +
\frac{A _ {k-1}  ^ {-1} u _ {k} }{a _ {kk} }
 +
  \\
 +
0 &
 +
\frac{1}{a _ {kk} }
 +
  \\
 +
\end{array}
 +
\
 +
\right \| .
 +
$$
  
 
The amount of calculation in this instance is reduced six-fold.
 
The amount of calculation in this instance is reduced six-fold.
Line 29: Line 103:
 
The bordering method is particularly effective when inverting Hermitian positive-definite matrices. For these matrices it is not necessary to use a scheme with a choice of a principal element. Moreover, they are determined by only half of their elements. The calculating scheme in this instance is simplified thus:
 
The bordering method is particularly effective when inverting Hermitian positive-definite matrices. For these matrices it is not necessary to use a scheme with a choice of a principal element. Moreover, they are determined by only half of their elements. The calculating scheme in this instance is simplified thus:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701018.png" /></td> </tr></table>
+
$$
 +
A _ {k}  ^ {-1}  =  \left \|
 +
 
 +
\begin{array}{cc}
 +
A _ {k-1}  ^ {-1} +
 +
\frac{P _ {k} P _ {k}  ^  \star  }{\alpha _ {k} }
 +
  & -
 +
\frac{P _ {k} }{\alpha _ {k} }
 +
  \\
 +
-
 +
\frac{P _ {k}  ^  \star  }{\alpha _ {k} }
 +
  &
 +
\frac{1}{\alpha _ {k} }
 +
  \\
 +
\end{array}
 +
 
 +
\right \| ,
 +
$$
 +
 
 +
$$
 +
P _ {k}  = A _ {k-1}  ^ {-1} u _ {k} ,\  \alpha _ {k}  = a _ {kk} - u _ {k}  ^  \star  P _ {k} .
 +
$$
 +
 
 +
The calculating scheme of the bordering method for the solution of a system is as follows. Let  $  b  ^ {(kp)} = (a _ {1p} \dots a _ {kp} )  ^ {T} $,
 +
$  k = 1 \dots n $;  
 +
$  b  ^ {(n,n+1)} = -b $.
 +
If  $  A _ {k-1} $
 +
is a non-degenerate matrix and  $  x  ^ {(k-1,p)} $
 +
is the solution of the system  $  A _ {k-1} x  ^ {(k-1,p)} + b  ^ {(k-1,p)} = 0 $,
 +
then the solution  $  x  ^ {(k,p)} $
 +
of the system  $  A _ {k} x  ^ {(k,p)} + b  ^ {(k,p)} = 0 $
 +
is obtained from the representation
 +
 
 +
$$ \tag{3 }
 +
A _ {k}  = \left \|
 +
 
 +
\begin{array}{cc}
 +
A _ {k-1}  &b ^ {(k-1,k)}  \\
 +
v _ {k}  &a _ {kk}  \\
 +
\end{array}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701019.png" /></td> </tr></table>
+
\right \| ,\ \
 +
b  ^ {(k,p)}  = \left \|
  
The calculating scheme of the bordering method for the solution of a system is as follows. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701021.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701022.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701023.png" /> is a non-degenerate matrix and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701024.png" /> is the solution of the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701025.png" />, then the solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701026.png" /> of the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701027.png" /> is obtained from the representation
+
\begin{array}{c}
 +
b ^ {(k-1,p)}  \\
 +
a _ {kp}  \\
 +
\end{array}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701028.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
\right \| ,
 +
$$
  
 
and from (2) as follows
 
and from (2) as follows
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701029.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
$$ \tag{4 }
 +
x  ^ {(k,p)}  = - \left \|
 +
 
 +
\begin{array}{cc}
 +
A _ {k-1}  ^ {-1}  & 0  \\
 +
0  & 0 \\
 +
\end{array}
 +
 
 +
\right \|  \left \|
 +
 
 +
\begin{array}{c}
 +
b ^ {(k-1,p)}  \\
 +
a _ {kp}  \\
 +
\end{array}
 +
\right \| +
 +
$$
 +
 
 +
$$
 +
+
 +
 
 +
\frac{1}{\alpha _ {k} }
 +
\left \|
 +
\begin{array}{c}
 +
-x
 +
^ {(k-1,k)} v _ {k} x  ^ {(k-1,p)} -x  ^ {(k-1,k)} a _ {kp}  \\
 +
-v _ {k} x  ^ {(k-1,p)} - a _ {kp}  \\
 +
\end{array}
 +
\right \| =
 +
$$
 +
 
 +
$$
 +
= \
 +
\left \|
 +
\begin{array}{c}
 +
x  ^ {(k-1,p)}  \\
 +
0  \\
 +
\end{array}
 +
\
 +
\right \| -
 +
\frac{v _ {k} x  ^ {(k-1,p)} + a _ {kp} }{a _ {kk} + v _ {k} x  ^ {(k-1,k)} }
 +
\left \|
 +
 +
\begin{array}{c}
 +
x  ^ {(k-1,k)}  \\
 +
1  \\
 +
\end{array}
 +
\right \| .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701030.png" /></td> </tr></table>
+
In this way, through the solutions  $  x  ^ {(k-1,p)} $
 +
and  $  x  ^ {(k-1,k)} $
 +
of the systems with the same matrix  $  A _ {k-1} $
 +
and with various right-hand sides, it is easy to obtain the solution of the system with the bordered matrix  $  A _ {k} $.  
 +
The solution of the initial system is  $  x  ^ {(n,n+1)} $.  
 +
This can be obtained by the recurrent use of relation (4). This leads to the subsequent calculation of the set of vectors  $  x  ^ {(k,p)} $,
 +
$  k = 1 \dots n $,
 +
$  p > k $,
 +
that is
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701031.png" /></td> </tr></table>
+
$$
  
In this way, through the solutions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701032.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701033.png" /> of the systems with the same matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701034.png" /> and with various right-hand sides, it is easy to obtain the solution of the system with the bordered matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701035.png" />. The solution of the initial system is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701036.png" />. This can be obtained by the recurrent use of relation (4). This leads to the subsequent calculation of the set of vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701037.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701038.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701039.png" />, that is
+
\begin{array}{llll}
 +
x  ^ {(12)} ,  &x  ^ {(13)} ,  &\dots,  &x  ^ {(1,n+1)} ,  \\
 +
{}  &x  ^ {(23)} ,  &\dots,  &x  ^ {(2,n+1)} ,  \\
 +
{}  &{}  &\dots,  &\dots,  \\
 +
{}  &{}  &{}  &x  ^ {(n-1,n+1)} , \\
 +
{}  &{}  &{}  &x  ^ {(n,n+1)} . \\
 +
\end{array}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701040.png" /></td> </tr></table>
+
$$
  
 
In the amount of calculation necessary, this bordering method is equivalent to the [[Gauss method|Gauss method]], one of the fastest direct methods of solving systems.
 
In the amount of calculation necessary, this bordering method is equivalent to the [[Gauss method|Gauss method]], one of the fastest direct methods of solving systems.
  
The bordering method allows one to solve higher-order systems owing to the effective use of computer memory. This is caused by the fact that for the calculation of the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701041.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701042.png" />, only the storage of the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701043.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701044.png" />, and the coefficients of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701045.png" />-th order system of equations is necessary, that is, a series of numbers of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701046.png" />. It is therefore sufficient to have a working capacity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701047.png" /> to solve a system of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701048.png" />. Moreover, the elements of the matrix and of the right-hand side do not have to be put into the computer memory immediately but successively, row by row.
+
The bordering method allows one to solve higher-order systems owing to the effective use of computer memory. This is caused by the fact that for the calculation of the vectors $  x  ^ {(k,p)} $,  
 +
$  p > k $,  
 +
only the storage of the vectors $  x  ^ {(k-1,p)} $,  
 +
$  p > k-1 $,  
 +
and the coefficients of a $  k $-
 +
th order system of equations is necessary, that is, a series of numbers of length $  f(k) = k(n-k+1) + (n+1) $.  
 +
It is therefore sufficient to have a working capacity $  (n+1)(n+5)/4 \approx (n/2)  ^ {2} $
 +
to solve a system of order $  n $.  
 +
Moreover, the elements of the matrix and of the right-hand side do not have to be put into the computer memory immediately but successively, row by row.
  
 
It is advisable to use the bordering method when solving systems for which a truncated system has already been solved. Relation (4) then immediately gives the required solution.
 
It is advisable to use the bordering method when solving systems for which a truncated system has already been solved. Relation (4) then immediately gives the required solution.
Line 57: Line 244:
 
The scheme of the bordering method described can be used to calculate the determinant. It follows from (1) that
 
The scheme of the bordering method described can be used to calculate the determinant. It follows from (1) that
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701049.png" /></td> </tr></table>
+
$$
 +
| A _ {k} |  = \
 +
( a _ {kk} -v _ {k} A _ {k-1}  ^ {-1} u _ {k} ) \
 +
| A _ {k-1} | .
 +
$$
  
Recurrent use of this relation gives <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701050.png" />.
+
Recurrent use of this relation gives $  | A | $.
  
 
As with the inversion of a matrix, the solution of a system and the calculation of the determinant by means of the bordering method is possible only for matrices with non-zero principal minors. It is generally also necessary here to use a scheme with a choice of a principal element.
 
As with the inversion of a matrix, the solution of a system and the calculation of the determinant by means of the bordering method is possible only for matrices with non-zero principal minors. It is generally also necessary here to use a scheme with a choice of a principal element.
Line 65: Line 256:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.V. Voevodin,  "Numerical methods of algebra. Theory and algorithms" , Moscow  (1966)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  D.K. Faddeev,  V.N. Faddeeva,  "Computational methods of linear algebra" , Freeman  (1963)  (Translated from Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.V. Voevodin,  "Numerical methods of algebra. Theory and algorithms" , Moscow  (1966)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  D.K. Faddeev,  V.N. Faddeeva,  "Computational methods of linear algebra" , Freeman  (1963)  (Translated from Russian)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
 
The bordering method is a special case of more general partitioning procedures [[#References|[a1]]].
 
The bordering method is a special case of more general partitioning procedures [[#References|[a1]]].
  
The bordering method defined above is related to the Sherman–Morrison formula and its generalization the Sherman–Morrison–Woodbury formula. The Sherman–Morrison formula states that a non-singular <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701051.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701052.png" /> and vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701053.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701054.png" /> are related by
+
The bordering method defined above is related to the Sherman–Morrison formula and its generalization the Sherman–Morrison–Woodbury formula. The Sherman–Morrison formula states that a non-singular $  (m \times m ) $-
 +
matrix $  M $
 +
and vectors $  x $
 +
and $  y $
 +
are related by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701055.png" /></td> </tr></table>
+
$$
 +
[ M + xy  ^ {H} ]  ^ {-1}  = \
 +
M  ^ {-1} - M  ^ {-1} xc  ^ {-1} y  ^ {H} M  ^ {-1} ,\  c=1+y  ^ {H} M  ^ {-1} x ,
 +
$$
  
provided that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701056.png" />. The Sherman–Morrison–Woodbury formula replaces the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701057.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701058.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701059.png" />-matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701060.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b017/b017010/b01701061.png" />. These formulas were developed in [[#References|[a2]]]–[[#References|[a5]]] (see also [[#References|[a6]]]), and used for the construction of matrix inversion schemes resembling that of the bordering method. An excellent discussion of these schemes is given in [[#References|[a7]]].
+
provided that $  c \neq 0 $.  
 +
The Sherman–Morrison–Woodbury formula replaces the vectors $  x $
 +
and $  y $
 +
by $  (m \times n ) $-
 +
matrices $  X $
 +
and $  Y $.  
 +
These formulas were developed in [[#References|[a2]]]–[[#References|[a5]]] (see also [[#References|[a6]]]), and used for the construction of matrix inversion schemes resembling that of the bordering method. An excellent discussion of these schemes is given in [[#References|[a7]]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.R. Westlake,  "A handbook of numerical matrix inversion and solution of linear equations" , Wiley  (1968)  pp. Sect. 2.6</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M.S. Bartlett,  "An inverse matrix adjustment arising in discriminant analysis"  ''Ann. Math. Stat.'' , '''22'''  (1951)  pp. 107–111</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J. Sherman,  "Computations relating to inverse matrices" , ''Appl. Math. Ser.'' , '''29''' , Nat. Bur. Standards  (1953)  pp. 123–124</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  J. Sherman,  W.J. Morrison,  "Adjustments of an inverse matrix corresponding to changes in the elements of a given column or a given row of the original matrix"  ''Ann. Math. Stat.'' , '''20'''  (1949)  pp. 621</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  M. Woodbury,  "Inverting modified matrices"  ''Memorandum Report Stat. Res. Group Princeton'' , '''42'''  (1950)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  G.H. Golub,  C.F. van Loan,  "Matrix computations" , North Oxford Acad.  (1983)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A.S. Householder,  "Principles of numerical analysis" , McGraw-Hill  (1953)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.R. Westlake,  "A handbook of numerical matrix inversion and solution of linear equations" , Wiley  (1968)  pp. Sect. 2.6</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M.S. Bartlett,  "An inverse matrix adjustment arising in discriminant analysis"  ''Ann. Math. Stat.'' , '''22'''  (1951)  pp. 107–111</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J. Sherman,  "Computations relating to inverse matrices" , ''Appl. Math. Ser.'' , '''29''' , Nat. Bur. Standards  (1953)  pp. 123–124</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  J. Sherman,  W.J. Morrison,  "Adjustments of an inverse matrix corresponding to changes in the elements of a given column or a given row of the original matrix"  ''Ann. Math. Stat.'' , '''20'''  (1949)  pp. 621</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  M. Woodbury,  "Inverting modified matrices"  ''Memorandum Report Stat. Res. Group Princeton'' , '''42'''  (1950)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  G.H. Golub,  C.F. van Loan,  "Matrix computations" , North Oxford Acad.  (1983)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A.S. Householder,  "Principles of numerical analysis" , McGraw-Hill  (1953)</TD></TR></table>

Revision as of 06:28, 30 May 2020


A method for solving a system of linear algebraic equations $ Ax = b $ with a non-degenerate matrix by inverting a matrix and calculating a determinant, based on passing recursively from the solution of the problem with matrix

$$ A _ {k-1} = \left \| \begin{array}{lcl} a _ {1,1} &\dots &a _ {1, k - 1 } \\ \dots &\dots &\dots \\ a _ {k-1,1} &\dots &a _ {k-1,k-1} \\ \end{array} \right \| , $$

to the solution of the problem with the matrix $ A _ {k} $, which can be considered as the result of bordering $ A _ {k-1} $.

The calculating scheme of the bordering method for the inversion of a matrix is as follows: Let $ A _ {k-1} $ be a non-degenerate matrix. In the inversion of the matrix $ A _ {k} $, the representation

$$ \tag{1 } A _ {k} = \left \| \begin{array}{cc} A _ {k-1} &u _ {k} \\ v _ {k} &a _ {kk} \\ \end{array} \right \| $$

is used, where $ u _ {k} = (a _ {1,k} \dots a _ {k+1,k} ) ^ {T} $ and $ v _ {k} = (a _ {k,1} \dots a _ {k,k-1} ) $. Then

$$ \tag{2 } A _ {k} ^ {-1} = \left \| \begin{array}{cc} A _ {k-1} ^ {-1} + \frac{A _ {k-1} ^ {-1} u _ {k} v _ {k} A _ {k-1} ^ {-1} }{\alpha _ {k} } & - \frac{A _ {k-1} ^ {-1} u _ {k} }{\alpha _ {k} } \\ - \frac{v _ {k} A _ {k-1} ^ {-1} }{\alpha _ {k} } & \frac{1}{\alpha _ {k} } \\ \end{array} \right \| , $$

$$ \alpha _ {k} = a _ {kk} - v _ {k} A _ {k-1} ^ {-1} u _ {k} . $$

Subsequent inversion of the matrices $ A _ {1} \dots A _ {n} $ by this scheme gives the matrix $ A ^ {-1} $.

The above scheme of the bordering method is only applicable to matrices with principal minors unequal to zero. Generally, a choice of the principal element is adopted. In this scheme, the bordering rows and columns used are those for which $ \alpha _ {k} = a _ {kk} -v _ {k} A _ {k-1} ^ {-1} u _ {k} $ has the maximum absolute value. The calculated matrix will then differ from $ A ^ {-1} $ only in the rearrangement of the rows and columns [1].

The bordering method is not the fastest of the direct methods of inversion of a matrix.

The bordering method permits an effective inversion of a triangular matrix. If $ A _ {k} $ is a right (upper-) triangular matrix, then in (1)

$$ v _ {k} = 0 \ \textrm{ and } \ A _ {k} ^ {-1} = \left \| \begin{array}{cc} A _ {k-1} ^ {-1} &- \frac{A _ {k-1} ^ {-1} u _ {k} }{a _ {kk} } \\ 0 & \frac{1}{a _ {kk} } \\ \end{array} \ \right \| . $$

The amount of calculation in this instance is reduced six-fold.

The bordering method is particularly effective when inverting Hermitian positive-definite matrices. For these matrices it is not necessary to use a scheme with a choice of a principal element. Moreover, they are determined by only half of their elements. The calculating scheme in this instance is simplified thus:

$$ A _ {k} ^ {-1} = \left \| \begin{array}{cc} A _ {k-1} ^ {-1} + \frac{P _ {k} P _ {k} ^ \star }{\alpha _ {k} } & - \frac{P _ {k} }{\alpha _ {k} } \\ - \frac{P _ {k} ^ \star }{\alpha _ {k} } & \frac{1}{\alpha _ {k} } \\ \end{array} \right \| , $$

$$ P _ {k} = A _ {k-1} ^ {-1} u _ {k} ,\ \alpha _ {k} = a _ {kk} - u _ {k} ^ \star P _ {k} . $$

The calculating scheme of the bordering method for the solution of a system is as follows. Let $ b ^ {(kp)} = (a _ {1p} \dots a _ {kp} ) ^ {T} $, $ k = 1 \dots n $; $ b ^ {(n,n+1)} = -b $. If $ A _ {k-1} $ is a non-degenerate matrix and $ x ^ {(k-1,p)} $ is the solution of the system $ A _ {k-1} x ^ {(k-1,p)} + b ^ {(k-1,p)} = 0 $, then the solution $ x ^ {(k,p)} $ of the system $ A _ {k} x ^ {(k,p)} + b ^ {(k,p)} = 0 $ is obtained from the representation

$$ \tag{3 } A _ {k} = \left \| \begin{array}{cc} A _ {k-1} &b ^ {(k-1,k)} \\ v _ {k} &a _ {kk} \\ \end{array} \right \| ,\ \ b ^ {(k,p)} = \left \| \begin{array}{c} b ^ {(k-1,p)} \\ a _ {kp} \\ \end{array} \right \| , $$

and from (2) as follows

$$ \tag{4 } x ^ {(k,p)} = - \left \| \begin{array}{cc} A _ {k-1} ^ {-1} & 0 \\ 0 & 0 \\ \end{array} \right \| \left \| \begin{array}{c} b ^ {(k-1,p)} \\ a _ {kp} \\ \end{array} \right \| + $$

$$ + \frac{1}{\alpha _ {k} } \left \| \begin{array}{c} -x ^ {(k-1,k)} v _ {k} x ^ {(k-1,p)} -x ^ {(k-1,k)} a _ {kp} \\ -v _ {k} x ^ {(k-1,p)} - a _ {kp} \\ \end{array} \right \| = $$

$$ = \ \left \| \begin{array}{c} x ^ {(k-1,p)} \\ 0 \\ \end{array} \ \right \| - \frac{v _ {k} x ^ {(k-1,p)} + a _ {kp} }{a _ {kk} + v _ {k} x ^ {(k-1,k)} } \left \| \begin{array}{c} x ^ {(k-1,k)} \\ 1 \\ \end{array} \right \| . $$

In this way, through the solutions $ x ^ {(k-1,p)} $ and $ x ^ {(k-1,k)} $ of the systems with the same matrix $ A _ {k-1} $ and with various right-hand sides, it is easy to obtain the solution of the system with the bordered matrix $ A _ {k} $. The solution of the initial system is $ x ^ {(n,n+1)} $. This can be obtained by the recurrent use of relation (4). This leads to the subsequent calculation of the set of vectors $ x ^ {(k,p)} $, $ k = 1 \dots n $, $ p > k $, that is

$$ \begin{array}{llll} x ^ {(12)} , &x ^ {(13)} , &\dots, &x ^ {(1,n+1)} , \\ {} &x ^ {(23)} , &\dots, &x ^ {(2,n+1)} , \\ {} &{} &\dots, &\dots, \\ {} &{} &{} &x ^ {(n-1,n+1)} , \\ {} &{} &{} &x ^ {(n,n+1)} . \\ \end{array} $$

In the amount of calculation necessary, this bordering method is equivalent to the Gauss method, one of the fastest direct methods of solving systems.

The bordering method allows one to solve higher-order systems owing to the effective use of computer memory. This is caused by the fact that for the calculation of the vectors $ x ^ {(k,p)} $, $ p > k $, only the storage of the vectors $ x ^ {(k-1,p)} $, $ p > k-1 $, and the coefficients of a $ k $- th order system of equations is necessary, that is, a series of numbers of length $ f(k) = k(n-k+1) + (n+1) $. It is therefore sufficient to have a working capacity $ (n+1)(n+5)/4 \approx (n/2) ^ {2} $ to solve a system of order $ n $. Moreover, the elements of the matrix and of the right-hand side do not have to be put into the computer memory immediately but successively, row by row.

It is advisable to use the bordering method when solving systems for which a truncated system has already been solved. Relation (4) then immediately gives the required solution.

The scheme of the bordering method described can be used to calculate the determinant. It follows from (1) that

$$ | A _ {k} | = \ ( a _ {kk} -v _ {k} A _ {k-1} ^ {-1} u _ {k} ) \ | A _ {k-1} | . $$

Recurrent use of this relation gives $ | A | $.

As with the inversion of a matrix, the solution of a system and the calculation of the determinant by means of the bordering method is possible only for matrices with non-zero principal minors. It is generally also necessary here to use a scheme with a choice of a principal element.

References

[1] V.V. Voevodin, "Numerical methods of algebra. Theory and algorithms" , Moscow (1966) (In Russian)
[2] D.K. Faddeev, V.N. Faddeeva, "Computational methods of linear algebra" , Freeman (1963) (Translated from Russian)

Comments

The bordering method is a special case of more general partitioning procedures [a1].

The bordering method defined above is related to the Sherman–Morrison formula and its generalization the Sherman–Morrison–Woodbury formula. The Sherman–Morrison formula states that a non-singular $ (m \times m ) $- matrix $ M $ and vectors $ x $ and $ y $ are related by

$$ [ M + xy ^ {H} ] ^ {-1} = \ M ^ {-1} - M ^ {-1} xc ^ {-1} y ^ {H} M ^ {-1} ,\ c=1+y ^ {H} M ^ {-1} x , $$

provided that $ c \neq 0 $. The Sherman–Morrison–Woodbury formula replaces the vectors $ x $ and $ y $ by $ (m \times n ) $- matrices $ X $ and $ Y $. These formulas were developed in [a2][a5] (see also [a6]), and used for the construction of matrix inversion schemes resembling that of the bordering method. An excellent discussion of these schemes is given in [a7].

References

[a1] J.R. Westlake, "A handbook of numerical matrix inversion and solution of linear equations" , Wiley (1968) pp. Sect. 2.6
[a2] M.S. Bartlett, "An inverse matrix adjustment arising in discriminant analysis" Ann. Math. Stat. , 22 (1951) pp. 107–111
[a3] J. Sherman, "Computations relating to inverse matrices" , Appl. Math. Ser. , 29 , Nat. Bur. Standards (1953) pp. 123–124
[a4] J. Sherman, W.J. Morrison, "Adjustments of an inverse matrix corresponding to changes in the elements of a given column or a given row of the original matrix" Ann. Math. Stat. , 20 (1949) pp. 621
[a5] M. Woodbury, "Inverting modified matrices" Memorandum Report Stat. Res. Group Princeton , 42 (1950)
[a6] G.H. Golub, C.F. van Loan, "Matrix computations" , North Oxford Acad. (1983)
[a7] A.S. Householder, "Principles of numerical analysis" , McGraw-Hill (1953)
How to Cite This Entry:
Bordering method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Bordering_method&oldid=46119
This article was adapted from an original article by G.D. Kim (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article