NATIONAL BUREAU OF STANDARDS REPORT

1728

ON ABSOLUTE CONVERGENCE OF LINEAR

ITERATION PROCESSES

by

A. . M. Ostrowski

<NBS>

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
U. S. DEPARTMENT OF COMMERCE

Charles Sawyer, Secretary

NATIONAL BUREAU OF STANDARDS

A. V. A81in, Director THE NATIONAL BUREAU OF STANDARDS

The scope of activities of the National Bureau of Standards is suggested in the following

listing of the divisions and sections engaged in technical work. In general, each section is engaged in specialized research, development, and engineering in the field indicated by its

title. A brief description of the activities, and of the resultant reports and publications, appears on the inside of the back cover of this report.

1. Electricity. Resistance Measurements. Inductance and Capacitance. Electrical Instruments. Magnetic Measurements. Electrochemistry.

2. Optics and Metrology. Photometry and Colorimetry. Optical Instruments. Photographic Technology. Length. Gage.

3. Heat and Power. Temperature Measurements. Thermodynamics. Cryogenics. Engines and Lubrication. Engine Fuels.

4. Atomic and Radiation Physics. Spectroscopy. Radiometry. Mass Spectrometry.

Physical Electronics. Electron Physics. Atomic Physics. Neutron Measurements.

Nuclear Physics. Radioactivity. X-Rays. Betatron. Nucleonic Instrumentation.

Radiological Equipment. Atomic Energy Commission Instruments Branch.

5. Chemistry. Organic Coatings. Surface Chemistry. Organic Chemistry. Analytical

Chemistry. Inorganic Chemistry. Electrodeposition. Gas Chemistry. Physical Chemistry. Thermochemistry. Spectrochemistry. Pure Substances.

6. Mechanics. Sound. Mechanical Instruments. Aerodynamics. Engineering Mechanics. Hydraulics. Mass. Capacity, Density, and Fluid Meters.

7. Organic and Fibrous Materials. Rubber. Textiles. Paper. Leather. Testing

and Specifications. Organic Plastics. Dental Research.

8. Metallurgy. Thermal Metallurgy. Chemical Metallurgy. Mechanical Metallurgy.

Corrosion.

9. Mineral Products. Porcelain and Pottery. Glass. Refractories. Enameled Metals.

Building Stone. Concreting Materials. Constitution and Microstructure. Chemistry

of Mineral Products.

10. Building Technology. Structural Engineering. Fire Protection. Heating and Air

Conditioning. Exterior and Interior Coverings. Codes and Specifications.

11. Applied Mathematics. Numerical Analysis. Computation. Statistical Engineering.

Machine Development.

12. Electronics. Engineering Electronics. Electron Tubes. Electronic Computers. Electronic Instrumentation.

13. Ordnance Development. Mechanical Research and Development. Electromechanical Fuzes. Technical Services. Missile Fuzing Research. Missile Fuzing Development.

Projectile Fuzes. Ordnance Components. Ordnance Tests. Ordnance Research.

14. Radio Propagation. Upper Atmosphere Research. Ionospheric Research. Regular

Propagation Services. Frequency Utilization Research. Tropospheric Propagation

Research. High Frequency Standards. Microwave Standards.

15. Missile Development. Missile Engineering. Missile Dynamics. Missile Intelligence.

Missile Instrumentation. Technical Services. Combustion.
NATIONAL BUREAU OF STANDARDS REPORT

NBS PROJECT NBS REPORT

1102-21-1104 June 15, 1952 1728

ON ABSOLUTE CONVERGENCE OF LINEAR

ITERATION PROCESSES

by

A. M. Ostrovski

American University

University of Basel

The publication, reprinti Approved for public release by the rti , s pro hibited

unless permission is obta Director of the National Institute of rds, Washington 25.D.C. Such permis Sta nda rds a nd Technology ( N 1ST) ieen specifically prepared if that agenr on October 9, 2015 or its own use.

ON absolute convergence of linear

ITERATION PROCESSES I

By a. M. QstrowskI

1. In solving the linear system A £ * rf by iteration (where

i = (a ) is a quadratic matrix of order n as are all matrices

considered later, save, of course, vectors) we establish a sequence of

vectors d , approximating vectors to the solution vector .. ; H

the corresponding residual vectors p are given by

A

£

‘ • k

"7 1c

elements a

A*/*

We assume in what follows that the diagonal

are = 1.

In the single step iteration at each step only one component

O<) of L is changed; if the components of are X

K

K V

to each k corresponds a leading index N^ such that

then

(1) x

(k+1)

If .00 (V+ N. ) , x

(k+1)

N. - x

(k)

N. $

k

Usually J is so chosen that the corresponding components

(k) of 0 becomes 0; if the components of 0^ are r.

‘

. we have

then 8 lr =-hk)

, V

L

In the case the so-called incomplete relaxation is allowed

we take

(2) S \ r

N

(k>

(0 < qk < 2) ;

for < 1 we have under relaxation and for qk > 1 we have over

relaxation.
-2

2, A generalization of the single step iteration is the

group iteration ; here at each step the indices 1, n are

decomposed into two groups, active indices ( 4 or Y ) a.nd

pass i ve indices ( ) and in passing from

4^ 4 the

components with passive indices are not changed, while for

the change of the components with active Indices the following

rule is used. Define for the active indices the constants

£

CK)

0 from the set of equations

(3) %

a «r

~ <

k)

where and Y run over all active indices, and take

.(*> , q

<*> &°° (k) (4) x

(k+1) = x

(k) x

(k+1 > - x

(k

[ 1 X

B :< X

B

> X

(K p -p * "a ~a ~a ,(0<q a

< 2) *

An essentially different type of linear iteration is the

Jacobian iteration described by the formulae ( ?! s j Yn )

)

, (k+1) _ v £ k

(4a) x' = ~ll~ & a . x,.

• Y=1 fAl/ V

(See Argelander [1] ancl^Jacobi [4]).

3* While in the iteration (4) no freedom is left save

the choice of the starting vector , in using the single

step of the group iteration the choice of the leading index

or more generally of the active indices at each step -

we call this the steering of the process - becomes the essential

problem. If this choice depends on the values of the components

P we call it the relaxation processes (introduced by Gauss [2], K

see also references to Gauss in Gerllng [3] and later discussed
-3-

by Seidel C 17 3 and rediscovered by Southwell [lSfy^If the

sequence of the leading indices or more generally of the groups

of active indices is periodic* then, if no index is missing

(while some of them may occur several times in a period) we

speak of the periodic steering ; if in particular, in a

complete period each index occurs exactly once we speak of

the cyclic steering,, The cyclic steering appears to have

been considered for the first time by Nekrassoff [8] although

2

it was mentioned by Seidel [17] who did not recommend it.

The cyclic group iteration was first considered by Pizzetti

[15] while the group relaxation was recommended by Gauss

(see the r ef erence in Gerling C 3 U )

- Finally we speak of

the free steering if the sequence of the leading indices

and active indices is chosen in an arbitrary way provided

q \ each index occurs an infinite number of times. The

incomplete relaxation is used in the practical computing

but it has not been as yet theoretically discussed.

These iteration schemes arose from the method of

the least squares. For a symmetric definite matrix the

convergence of the single step iteration in the case of the

steering by relaxation was first proved by Seidel [17]

Pizzetti [ 15 ] proved the convergence of the cyclic single

step and group iteration, while Reich [16] showed that
-4-

for a symmetric matrix the cyclic single step iteration

always diverges if the corresponding form is not a definite

one.

1 5. In the case of non-symmetric matrices the first sufficient

conditions for the convergence of the cyclic one "step iteration"

were given in 1892;

(5) £

|aA ^

|< 1 (Mehmke) [ 5 ] , (Nekrassof f ) [6]

,

Other sufficient conditions were given by Nekrassoff [9] and

later other writers (see the references in [20]). These conditions

contain usually not the elements a ^themselves but only their

moduli and it was then in any case noticed that the same conditions

are" also sufficient for the convergence of the Jacobian Iteration

(4a). In what follows we will say that an iteration process as

described above for a fixed choice of the active Indices is

absolutely* convergent if it is convergent for any choice of the

starting vector ^

and if it remains so when the elements

of the matrix are multiplied by arbitrary numbers of modulus

one. The conditions (-5 ) and analogous conditions are then

obviously sufficient conditions for the absolute convergence

of the cyclic one step Iteration.

In this note we will characterize completely all matrices

A for which the cyclic one step iteration is absolutely

convergent.
-5-

6. To a general matrix A = ) corresponds in a unique

way the matrix ,

(6) Ap (t a^^ jo y^+V '

the adjoint matrix to A [11]. The matrix A is called of H type

or an H matrix if |A^| >0 while all coaxial minors of Ap of

all orders are not negative.

Then we obtain as the necessary and sufficient condition

for the absolute convergence of the single step cyclic

Iteration, that the matrix A is an H matrix . More precisely

we have the two more general theorems:

I. If the cyclic one step Iteration converges for the

matrix for any choice of starting value 4/

> A is an H

matrix.

II. If A is an H matrix then the cyclic one step

iteration and even the one step iteration and the group

iteration with free steering are convergent for the matrix A

for any choice of the starting vector. Further, the incomplete

relaxation is allowed to the following extent: let t^ and

t

2 be positive numbers where t^ < 1 and t

2 is sufficiently

smallj, then the one step iteration remains convergent if the

vectors satisfy the condition

(7) sc qk $ 1 + t

2

k = (1,2, )

.
-6-

cr)

In the case of the group Iteration the factors q must

satisfy the condition

, (r)

(8) |qk

- 1| $ t

2

A corresponding result holds also for the Jacobian iteration

(4a),

III, A necessary and sufficient condition for the absolute

convergence of the Jacobian iteration for any choice of the starting

value ^ is that the matrix A is an H matrix.
-7-

ON ABSOLUTE CONVERGENCE OF LINEAR

ITERATION PROCESSES II

By A. M. Ostrowski

7* There are many sufficient conditions for the H type matrices

which, without being necessary, are often very easy to apply.

We use the following notations:

n n

(9)

no)

i£l l a

/(V I ' n

= C V=l

|a

'u '*/

SM

=

p-jVp

(11) m . = Max Ja 1, m = Max 1 ^ ^

n>v

M = Max , >M<V a/U/U

Then each of the following conditions (12) - (16) is sufficient

for the matrix A being of the H type:

(12) Z < I a | (A » 1, n);

yv

1 tL

' (13

<| | (yU«l, ..., n)

for a convenient <% , 0 4 OC ^ 1 [12];

n

(i^) ^

A=1 l+A aAA

< 1, A + i - 1; [13]

P q

n

(15) £

/<=1

I V< 1 + V

, v .. m M

(16) m < M, -—”n <7 "n < ( 1+m) ( 1+M

cp]

ci4]

In interchanging the rows with the columns we obtain a further

4) set of sufficient conditions. '
-8-

8® A single step or group Iteration scheme with a periodic

steering is equivalent to a matrix iteration of the type

c

' ' / * At £ + A0 7} * if the result of all steps contained 1 % 2 7 in a period is interpreted as the passage from a vector L

K

to a vector / . In the case of the cyclic single step

K+!

iteration such a representation can be obtained in writing the

matrix A as the sum L + D + R of the matrix L containing zeros

on the diagonal and to the right of it, the matrix D containing

zeros off the diagonal and the matrix R containing zeros on

the diagonal and to the left of it. Then the matrix

interpretation of the cyclic single step Iterations

corresponds to the formula

L = - (L+D)"

1

R i' + (L+D)

-1

•»'

; and from that the necessary and sufficient condition for the

convergence of this iteration can be obtained in the form that

the maximum modulus of the roots of the equation

|A,L + XrD +R|~0 remains < 1 [8,9] • We will denote this

maximum modulus as the Nekrassoff number of A.

9. On the other hand a corresponding condition has been

derived for the convergence of the Jabobian iteration; in this

case it is necessary and sufficient for the convergence that

the maximum modulus of the roots of the equation | A D + L + R| = 0

is < 1 [7].
-9 -

¥e will consider in particular the maximum modulus of

the roots of this equation formed for the adjoint matrix

of A; this number will be denoted by <r ^

and called the

Jacobian constant of the matrix A. Then we can write the

necessary and sufficient condition for the absolute convergence

of the Jacobian iteration of the matrix A in the form

CT , < 1. This is equivalent to the theorem that

or a < 1 is necessary and sufficient for the matrix A to be

of the H type.

On the other hand it can be proved that if cr^ 1, the

Nekrassoff number of A remains ^ or

10. These results can be generalized in the following

way. We call a matrix S a truncated part

^

^ of the matrix A if

the elements of S are obtained in multiplying the corresponding

elements of A by arbitrary factors from the interval <0, l? , Let now the matrix A be decomposed into the sum of two

truncated parts U, V: A - U + V, and suppose that all diagonal

elements of V vanish; let A_ = Urj + V_ be the corresponding

P P P

decomposition of the adjoint matrix Ag. Assume now that

Up is not singular and write H = -U “ V ; then for

r f P

the convergence of the stationary linear iteration

£

/ r*J t -i 4

= H 4 + (E - H ) A

JV

KH H

' for an arbitrary starting vector 4 it is necessary that A

is an H matrix
-10-

On the other hand, if A is an H matrix and if we consider

for each k a particular decomposition of the above type

A = Uk + V*., the diagonal elements of being zero, we

obtain in putting =-Uy

1

a generally non- stationary

linear iteration process £ - ^

which is convergent in such a way that “4k ” ® ( ( <r^ +

for any positive c

,

. s

11. The one step iteration as defined in the section 1

can be also considered as an iteration of the residual

vector. Thus we obtain from (1) and (2) easily

(17)

/ ^k P

K

where

( 0 0 a 0

I

i V

(18) A rV o -

0 -

t 0 -

- 0 a/-/y 0

-01

- 0 avWv

0

0

0

:

° i

0 i

0 - - 0 a 0 - - 0

n, v

is the matrix obtained from A in keeping the V**1 column

and replacing all other elements by zeros. From our theorem

II it follows that for an H-matrix A and q satisfying

k *

the condition (7) the product ^(E - qk ) tends with

k

k o© to zero, if the sequence of the leading indices N.
-11- contains each index 1, . .., n an infinite number of times.

By this result we have in particular proven that the

Hardy Cross Balancing process for a continuous beam is

always convergent if each support is used in balancing

an infinite number of times. If in particular the supports

are treated in a certain order periodically, the convergence

Is linear, that is, of the type described at the end of

6 ) section 10.

Indeed, in the Hardy Cross process as described by

Oldenburger [10], the matrix A is defined by

V

= % ' &

1/-v = 1 > aVH V

= T-v = 0 (/<>V+1, /U<1/-1)

where

= S L-X

{1_t i

) > 7

i “ r i

t

i

o ^ t

1 ^ 1, 0 ^ r

i < 1, 0^.si <l.

Here we have certainly < (1-t ) + t =1 and our

matrix A is certainly then an H matrix.

11. The proofs for the necessity of our conditions make

use of properties of the H matrices given in an earlier

paper by the author[ 11 ]; howevei’ these properties have to

be developed further in different directions.

As to the proofs for the sufficiency of our criteria

they use in particular the following lemma:
-12-

To any matrix A with the Jacobian constant <x and. to any

A

positive g, correspond two positive diagonal matrices

(i.e, matrices with zeros off the diagonal and positive

numbers in the diagonal) P, such that we have

p"i - E -n

B - <Vv>

Vu= 0, £ <rA

+ £ , (// =l,...,n).

Instead of this lemma also the following one could be used

for the same purpose: I*et A be a matrix and n the maximum

modulus of the fundamental roots of A, then to any positive t

corresponds a non- singular matrix S such that we have

SAS"1 = B = (b^)

where

n

l>vl* p + e ( /« = 1, ... , n).

The details of our proofs will be developed in another

7 ) paper.
-13-

Footnotes

1)

As a matter of fact, the rules given by Gauss, Seidel and

Southwell for the choice of N are different; but they

coincide if the diagonal elements of A are all 1.

2) Hovrever, already Nekrasoff [8]had already referred to this

iteration

/as to the "Seideliteration" and this is the name usually

if wrongly used.

3) To this type belongs a class of iterations considered

occasionally by H. Gelringer [3a].

k) Cf. [19] for another connection in which these conditions

play an important role.

5) This name was proposed to me by Dr. F. Alt.

6) The convergence of the Hardy Crosses Process was proved

by Oldenburger [10] in the special case that the balancing

process is applied alternatively to all supports with odd

numbers and to all supports with even numbers.

7) A. Ostrowski, Die Determinant en mit ueberwiegender Hauptdiagonale und absolute Konvergenz linearer Iteratlonsprozesse. To appear in the Commentarii mathematlci helvetici.

o-
[1] Argelander. Ueber die Anwendung der Methode der Kleinsten

Quadrate auf einen besonderen Fall. Astronomlsche Nachrlchten

No. 491 (1844), p. 163.

[2] Gauss C.F . , Werke, Bd. IX, p. 278-281.

C3l Gerling G.L . . Die Ausglei chung ere chnung usw., HamburgGotha, 1843.

[3a] Gelrlnger H. . On the Solution of Systems of Linear Equations

by Certain Iterative Methods. Reissner Anniversary Volume

(1949), p. 365-393.

[4] Jacobi C.G.F. . Ueber elne neue Aufloesungsart der bei der

Methode der ki'elnsten Quadrate vorkommenden linearen

Gleichungen, Astronomlsche Nachrlchten. No. 523 (1845),

p. 297.

[ 5 ] Mehmke R, . Ueber das Seldelsche Verfahren, urn lineare

leichungen bei einer sehr grossen Anzahl der Unbekannten

durch successive Annaeherung aufzuloesen. Mat. Sbornik,

XVI (1892), p. 342-345.

[6] Mehmke R. und Nekrassof P.A. . Solution of a linear system

of equations by successive approximations (two letters by

Mehmke in German, two letters by Nekrassof in Russian).

Mat. Sbornik, XVI (1892), p. 437-459.

[ 7 ] von Mlses R, und Gelrlnger H. . Praktische Verfahren der

Glei chung saufloe sung. Zusammenfassender Bericht. ZAMM,9,

(1929), p. 58-77 and 152-164.
-15-

C8] Nekrassof P»A . , The determination of the unknowns by the

method of the least squares for a very large number of

unknowns. Mat. Sbornik, XII (1884), p. 189-204.

[9] Nekrassof P.A. . Concerning the solution of linear systems

of equations with a large number of unknowns. Bulletin of

the Petersbourg Academy of Sciences, LXIX (1892) No. 5, P*

1 -18 .

Nkra 3 af and ,

ehmke see Mehmke and Nekrassof.

[10] Oldenburg er R . . Convergence of Hardy-Crosse 1 s Balancing Process.

Journal of Applied Mechanics, 7 (1940), p. 166-170,

[11] Qstrowskl, A. . Ueber die Determinaten mit ueberwlegender

Hauptdiagonale, Comm. Math. Helv. , 10 (1937), p. 69-98 .

[12] Qstrowskl A, « Ueber das Nichtverschwinden einer Klasse von

Determinanten und die Lokallsierung der charakteristischen

Wurzeln von Matrizen. Comp. Math., 9(1951), p* 209-226.

[13] Q strowskl. A. . Sur les conditions generales pour la

regularite des matrices. Rendiconti di mat. e.d.s. applic.,

(V) 10 (1951), Pa 156-168.

[14] Qstrowskl .A,

Bur les matrices peu differentes d‘une matrice

triangulaire . C.R. 233 (1951), p» 1558-1560.

[15] Plzzettl P, . Rendiconti d.R. A. d.Lincei, (4) B^ (1887),

p. 230-235, 288-293

[16] Reich E.

On the convergence of the classical iterative

method of solving linear simultaneous equations. Ann. Math.

Stat., 20 (1949), p, 448-451,
£l7] Seidel L, . Ueber ein Verfahren usw. # Muench. Abhandl.

Math. -phys . Klassse 11 ( 1874 ), p. 81-108 .

[18] Southwell R.V. . Proc. R.S. London, A. 151 (1935), p .56

[19] Taussky-Todd 0. . A recurring theorem on determinants.

Am. M. Monthly, 56 (1949), p. 672-676 .

[20] Vfillers F.A. . Methoden der praktischen Analysis . V.W.V. Berlin, 2nd ed. , 1951.
THE NATIONAL BUREAU OF STANDARDS

Functions and Activities

The functions of the National Bureau of Standards are set forth in the Act

of Congress, March 3, 1901, as amended by Congress in Public Law 619, 1950.

These include the development and maintenance of the national standards of

measurement and the provision of means and methods for making measurements

consistent with these standards; the determination of physical constants and

properties of materials; the development of methods and instruments for testing

materials, devices, and structures; advisory services to Government Agencies on

scientific and technical problems; invention and development of devices to serve

special needs of the Government; and the development of standard practices,

codes, and specifications. The work includes basic and applied research, development, engineering, instrumentation, testing, evaluation, calibration services

and various consultation and information services. A major portion of the

Bureau’s work is performed for other Government Agencies, particularly the

Department of Defense and the Atomic Energy Commission. The scope of activities is suggested by the fisting of divisions and sections on the inside of the

front cover. Reports and Publications

The results of the Bureau’s work take the form of either actual equipment and

devices or published papers and reports. Reports are issued to the sponsoring

agency of a particular project or program. Published papers appear either in the

Bureau’s own series of publications or in the journals of professional and scientific

societies. The Bureau itself publishes three monthly periodicals, available from

the Government Printing Office: The Journal of Research, which presents complete papers reporting technical investigations; the Technical News Bulletin, which

presents summary and preliminary reports on work in progress; and Basic Radio

Propagation Predictions, which provides data for determining the best frequencies

to use for radio communications throughout the world. There are also five series

of nonperiodical publications: The Applied Mathematics Series, Circulars, Handbooks, Building Materials and Structures Reports, and Miscellaneous Publications.

Information on the Bureau’s publications can be found in NBS Circular 460,

Publications of the National Bureau of Standards ($1.00). Information on cali- bration services and fees can be found in NBS Circular 483, Testing by the National

Bureau of Standards (25 cents). Both are available from the Government Printing Office. Inquiries regarding the Bureau’s reports and publications should be

addressed to the Office of Scientific Publications, National Bureau of Standards,

Washington 25, D. C.
r