View source for Jacobi method

A method for reducing a [[quadratic form]] (cf. also [[Quadratic forms, reduction of|Quadratic forms, reduction of]]) to canonical form by using a triangular transformation of the unknowns; it was suggested by C.G.J. Jacobi (1834) (see [[#References|[1]]]).

Let

<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/j/j054/j054090/j0540901.png" /></td> </tr></table>

be a given [[Bilinear form|bilinear form]] (not necessarily symmetric) over a field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j0540902.png" />. Suppose that its matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j0540903.png" /> satisfies the condition

<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/j/j054/j054090/j0540904.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j0540905.png" /> is the [[Minor|minor]] of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j0540906.png" /> in the upper left-hand corner. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j0540907.png" /> can be written in the form

<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/j/j054/j054090/j0540908.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j0540909.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409010.png" />, and for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409011.png" />,

<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/j/j054/j054090/j05409012.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3a)</td></tr></table>

<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/j/j054/j054090/j05409013.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3b)</td></tr></table>

In particular, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409014.png" /> is a symmetric matrix satisfying (1) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409015.png" /> is the quadratic form with matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409016.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409017.png" /> can be reduced to the canonical form

<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/j/j054/j054090/j05409018.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>

by using the following transformation of the unknowns:

<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/j/j054/j054090/j05409019.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>

for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409020.png" />, and

<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/j/j054/j054090/j05409021.png" /></td> </tr></table>

This transformation has a triangular matrix, and can be written as

<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/j/j054/j054090/j05409022.png" /></td> <td valign="top" style="width:5%;text-align:right;">(6)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409023.png" /> is the minor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409024.png" /> that stands in the rows <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409025.png" />, and in the columns <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409026.png" />.

The formulas (2)–(7) are called Jacobi's formulas.

When the matrix of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409027.png" /> satisfies only the conditions

<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/j/j054/j054090/j05409028.png" /></td> </tr></table>

<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/j/j054/j054090/j05409029.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409030.png" /> is the rank of the form, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409031.png" /> can be reduced to the canonical form

<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/j/j054/j054090/j05409032.png" /></td> <td valign="top" style="width:5%;text-align:right;">(7)</td></tr></table>

(here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409033.png" />) by a triangular transformation of the unknowns. This reduction can be realized by using the [[Gauss method]] (see [[#References|[1]]]). If, in particular, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409034.png" />, then the positive index of inertia of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409035.png" /> is equal to the number of preservations of sign, and the negative index of inertia is equal to the number of changes of sign in the series of numbers

<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/j/j054/j054090/j05409036.png" /></td> </tr></table>

See also [[Law of inertia]].

====References====
<table>
<TR><TD valign="top">[1]</TD> <TD valign="top"> F.R. [F.R. Gantmakher] Gantmacher, "The theory of matrices" , '''1''' , Chelsea, reprint (1977) (Translated from Russian) {{MR|1657129}} {{MR|0107649}} {{MR|0107648}} {{ZBL|0927.15002}} {{ZBL|0927.15001}} {{ZBL|0085.01001}} </TD></TR>
</table>

''I.V. Proskuryakov''

Jacobi's method is a one-step iteration method (cf. [[Simple-iteration method]]) for solving a system of linear algebraic equations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409037.png" /> for which a preliminary transformation to the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409038.png" /> is realized by the rule:

<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/j/j054/j054090/j05409039.png" /></td> </tr></table>

<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/j/j054/j054090/j05409040.png" /></td> </tr></table>

''G.D. Kim''

====Comments====
Alternative names occurring in Western literature for this iteration method are: Gauss–Jacobi iteration, point Jacobi iteration, method of successive substitutions, and method of simultaneous displacements. It was already used by C.G.J. Jacobi (1845) (see [[#References|[a3]]]). If the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j054/j054090/j05409041.png" /> is irreducibly diagonally dominant, then the method converges for any starting vector (cf. [[#References|[a1]]]). With the introduction of new computer architectures such as vector and parallel computers, Jacobi's method has regained interest because it vectorizes and parallelizes extremely well. Comprehensive surveys of related iterative methods for sparse matrix equations can be found in [[#References|[a2]]], [[#References|[a4]]], [[#References|[a5]]], and [[#References|[a6]]].

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top"> L. Collatz, "Ueber die Konvergentzkriterien bei Iterationsverfahren für lineare Gleichungssysteme" ''Math. Z.'' , '''53''' (1950) pp. 149–161</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top"> L.A. Hageman, D.M. Young, "Applied iterative methods" , Acad. Press (1981) {{MR|0630192}} {{ZBL|0459.65014}} </TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top"> C.G.J. Jacobi, "Ueber eine neue Auflösungsart der bei der Methode der kleinsten Quadraten vorkommenden lineare Gleichungen" ''Astr. Nachr.'' , '''22''' : 523 (1845) pp. 297–306</TD></TR>
<TR><TD valign="top">[a4]</TD> <TD valign="top"> J.M. Ortéga, "Numerical analysis" , Acad. Press (1972) {{MR|0403154}} {{ZBL|0248.65001}} </TD></TR>
<TR><TD valign="top">[a5]</TD> <TD valign="top"> R.S. Varga, "A comparison of the successive over-relaxation method and semi-iterative methods using Chebyshev polynomials" ''Siam J. Appl. Math.'' , '''5''' (1962) pp. 39–47</TD></TR>
<TR><TD valign="top">[a6]</TD> <TD valign="top"> D.M. Young, "Iterative solution of large linear systems" , Acad. Press (1971) {{MR|0305568}} {{ZBL|0231.65034}} </TD></TR>
</table>

Jacobi's method is a [[rotation method]] for solving the [[Complete problem of eigen values|complete problem of eigen values]] and eigen vectors for a [[Hermitian matrix]].

''G.D. Kim''

====Comments====
The convergence of Jacobi's method has been examined by J. von Neumann and H. Goldstine (see [[#References|[a1]]]). Related rotation (or: transformation) methods are Householder's method and Francis' QR method (cf. [[#References|[a2]]]).

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top"> C.E. Fröberg, "Introduction to numerical analysis, theory and applications" , Benjamin/Cummings (1985)</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top"> G.H. Golub, C.F. van Loan, "Matrix computations" , North Oxford Acad. (1983) {{MR|0733103}} {{ZBL|0559.65011}} </TD></TR>
</table>

[[Category:Numerical analysis and scientific computing]]