Jacobi method

A method for reducing a quadratic form (cf. also 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 [1]).

Let

be a given bilinear form (not necessarily symmetric) over a field . Suppose that its matrix satisfies the condition

(1)

where is the minor of order in the upper left-hand corner. Then can be written in the form

(2)

where , , and for ,

(3a)

(3b)

In particular, if is a symmetric matrix satisfying (1) and is the quadratic form with matrix , then can be reduced to the canonical form

(4)

by using the following transformation of the unknowns:

(5)

for , and

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

(6)

where is the minor of that stands in the rows , and in the columns .

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

When the matrix of satisfies only the conditions

where is the rank of the form, can be reduced to the canonical form

(7)

(here ) by a triangular transformation of the unknowns. This reduction can be realized by using the Gauss method (see [1]). If, in particular, , then the positive index of inertia of 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

See also Law of inertia.

References

[1]	F.R. [F.R. Gantmakher] Gantmacher, "The theory of matrices" , 1 , Chelsea, reprint (1977) (Translated from Russian) MR1657129 MR0107649 MR0107648 Zbl 0927.15002 Zbl 0927.15001 Zbl 0085.01001

I.V. Proskuryakov

Jacobi's method is a one-step iteration method (cf. Simple-iteration method) for solving a system of linear algebraic equations for which a preliminary transformation to the form is realized by the rule:

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 [a3]). If the matrix is irreducibly diagonally dominant, then the method converges for any starting vector (cf. [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 [a2], [a4], [a5], and [a6].

References

[a1]	L. Collatz, "Ueber die Konvergentzkriterien bei Iterationsverfahren für lineare Gleichungssysteme" Math. Z. , 53 (1950) pp. 149–161
[a2]	L.A. Hageman, D.M. Young, "Applied iterative methods" , Acad. Press (1981) MR0630192 Zbl 0459.65014
[a3]	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
[a4]	J.M. Ortéga, "Numerical analysis" , Acad. Press (1972) MR0403154 Zbl 0248.65001
[a5]	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
[a6]	D.M. Young, "Iterative solution of large linear systems" , Acad. Press (1971) MR0305568 Zbl 0231.65034

Jacobi's method is a rotation method for solving the 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 [a1]). Related rotation (or: transformation) methods are Householder's method and Francis' QR method (cf. [a2]).

References

[a1]	C.E. Fröberg, "Introduction to numerical analysis, theory and applications" , Benjamin/Cummings (1985)
[a2]	G.H. Golub, C.F. van Loan, "Matrix computations" , North Oxford Acad. (1983) MR0733103 Zbl 0559.65011