Namespaces
Variants
Actions

Difference between revisions of "Completion method"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(Tex done)
 
Line 1: Line 1:
A method for calculating the inverse of a matrix, based on a recurrent transition which involves the calculation of a matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c0240801.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c0240802.png" /> is a column vector, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c0240803.png" /> is a row vector, by the formula
+
{{TEX|done}}{{MSC|65F05}}
  
<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/c/c024/c024080/c0240804.png" /></td> </tr></table>
+
A method for calculating the inverse of a matrix, based on a recurrent transition which involves the calculation of a matrix $(C+uv)^{-1}$, where $u$ is a column vector, $v$ is a row vector, by the formula
 +
$$
 +
(C + uv)^{-1} = C^{-1} - \frac{1}{\gamma} C^{-1} u v C^{-1} \ ,\ \ \ \gamma = 1 + v C^{-1} u \ .
 +
$$
  
The computational scheme of the method is as follows. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c0240805.png" /> be a given matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c0240806.png" />. Consider a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c0240807.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c0240808.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c0240809.png" /> is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c02408010.png" />-th column of the identity matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c02408011.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c02408012.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c02408013.png" /> and the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c02408014.png" /> is obtained by applying the above-described procedure <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c02408015.png" /> times. The computational formulas in this case are the following: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c02408016.png" /> is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c02408017.png" />-th column of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c02408018.png" />, then for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c02408019.png" />,
+
The computational scheme of the method is as follows. Let $A = (A_{ij})$ be a given matrix of order $n$. Consider a sequence $A_0 = I, A_1, \ldots, A_n$, where $A_k = A_{k-1} + e_k a_k $ and $e_k$ is the $k$-th column of the identity matrix $I$, $a_k = (a_{k1},\ldots,a_{k,k-1},a_{kk}-1,a_{k,k+1},\ldots,a_{kn})$. Then $A_n = A$ and the matrix $A^{-1}$ is obtained by applying the above-described procedure $n$ times. The computational formulas in this case are the following: If $a_j^{(k)}$ is the $j$-th column of $A_k$, then for $k=1,\ldots,n$,
 +
$$
 +
a_j^{(k)} = a_j^{(k-1)} - \frac{ a_ka_j^{(k-1)} }{ 1+a_ka_k^{(k-1)} } a_k^{(k-1)} \ ,\ \ j=1,\ldots,n\,.
 +
$$
  
<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/c/c024/c024080/c02408020.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
It is sufficient to compute the elements of the first $k$ rows of the matrix $A_k^{-1}$, since all subsequent rows coincide with the rows of the identity matrix.
 
 
It is sufficient to compute the elements of the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c02408021.png" /> rows of the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024080/c02408022.png" />, since all subsequent rows coincide with the rows of the identity matrix.
 
  
 
Other possibilities of arranging the computations in the completion method based on certain modifications of (*) are known, e.g. the so-called Ershov method (see [[#References|[1]]]).
 
Other possibilities of arranging the computations in the completion method based on certain modifications of (*) are known, e.g. the so-called Ershov method (see [[#References|[1]]]).
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</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">  D.K. Faddeev,  V.N. Faddeeva,  "Computational methods of linear algebra" , Freeman  (1963)  (Translated from Russian)</TD></TR>
 +
</table>
  
  
  
 
====Comments====
 
====Comments====
This method is also called the bordering method (cf. [[#References|[1]]]). See, however, also [[Bordering method|Bordering method]].
+
This method is also called the bordering method (cf. [[#References|[1]]]). See, however, also [[Bordering method]].

Latest revision as of 22:01, 19 November 2016

2020 Mathematics Subject Classification: Primary: 65F05 [MSN][ZBL]

A method for calculating the inverse of a matrix, based on a recurrent transition which involves the calculation of a matrix $(C+uv)^{-1}$, where $u$ is a column vector, $v$ is a row vector, by the formula $$ (C + uv)^{-1} = C^{-1} - \frac{1}{\gamma} C^{-1} u v C^{-1} \ ,\ \ \ \gamma = 1 + v C^{-1} u \ . $$

The computational scheme of the method is as follows. Let $A = (A_{ij})$ be a given matrix of order $n$. Consider a sequence $A_0 = I, A_1, \ldots, A_n$, where $A_k = A_{k-1} + e_k a_k $ and $e_k$ is the $k$-th column of the identity matrix $I$, $a_k = (a_{k1},\ldots,a_{k,k-1},a_{kk}-1,a_{k,k+1},\ldots,a_{kn})$. Then $A_n = A$ and the matrix $A^{-1}$ is obtained by applying the above-described procedure $n$ times. The computational formulas in this case are the following: If $a_j^{(k)}$ is the $j$-th column of $A_k$, then for $k=1,\ldots,n$, $$ a_j^{(k)} = a_j^{(k-1)} - \frac{ a_ka_j^{(k-1)} }{ 1+a_ka_k^{(k-1)} } a_k^{(k-1)} \ ,\ \ j=1,\ldots,n\,. $$

It is sufficient to compute the elements of the first $k$ rows of the matrix $A_k^{-1}$, since all subsequent rows coincide with the rows of the identity matrix.

Other possibilities of arranging the computations in the completion method based on certain modifications of (*) are known, e.g. the so-called Ershov method (see [1]).

References

[1] D.K. Faddeev, V.N. Faddeeva, "Computational methods of linear algebra" , Freeman (1963) (Translated from Russian)


Comments

This method is also called the bordering method (cf. [1]). See, however, also Bordering method.

How to Cite This Entry:
Completion method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Completion_method&oldid=15211
This article was adapted from an original article by G.D. Kim (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article