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)

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)
[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)
[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)

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)