NATIONAL BUREAU OF STANDARDS REPORT

1759

ON THE CONVERGENCE OF CYCLIC LINEAR ITERATIONS

FOR SYMMETRIC

AND NEARLY SYMMETRIC MATRICES „ II

A# M* Ostrovski

American University

and

University of Basle, Switzerland

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
U. S. DEPARTMENT OF COMMERCE

Charles Sawyer, Secretary

NATIONAL BUREAU OF STANDARDS

A. V. Astia, Acting 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 en- gaged in specialised 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.

8. ELECTRICITY, R«sis tance Measurements. Inductance and Capacitance. Electrical Instruments. Magnetic feSeaaurements. Electrochemistry.

2. OPTICS AHD METROLOGY. Photometry and Colorimetry. Optical Instruments. Photographic

Technology. Length. Gage.

3. HEAT hm POWER. Temperature Measurements. Thermodynamics. Cryogenics. Engines and

Lubrication. Engine Fuels.

ATOMIC A^B RADIATION PHYSICS. Spectroscopy. Radioesetry. Mass Spectrometry. Physical Electroaics. Electron Physics. Atomic Physics. Neutron Measurements. Nuclear Physics. Radioactivity. X-Rays. Betatron. Nucleonic Instrumentation. Radiological Equip-

®asat. Atoeic Energy Commission Instruments Branch.

5. CHEMISTRY. Organic Coatings. Surface Chemistry. Organic Chemistry. Analytical Chemistry. Inorganic Chemistry. Eiectrodepositioc . Gas Chemistry. Physical Chemistry. Theresocheasistry . Spectrochemistry. PAire Substances.

B. MECHANICS. Sound. Mechanical Instruments. Aerodynamics. Engineering Mechanics. Hydraulics. Mass. "Capacity, Density, and Fluid Meters. 7. ORGANIC hm FIBROUS MATERIALS. Rubber. Textiles. Paper. Leather. Testing and

Specifications. Organic Plastics. Dental Research.

8. METALLURGY. Thermal Metallurgy. Chemical Metallurgy. Mechanical Metallurgy . Corrosion.

3. MINERAL PRODUCTS. Porcelain and Pottery. Glass. Refractories. Enameled Metals. Building Stone. Concreting Materials. Constitution and Microstructure. Chemistry of Mineral

Presets.

10. BUILDING TECHNOLOGY. Structural Engineering. Fire Protection. Heating and Air Conditioning. Exterior end Interior Coverings. Codes and Specifications.

H. APPLIED MATHEMATICS. Numerical Analysis. Confutation. Statistical Engineering. Ma- chine Development.

I2« ELECTRONICS. Engineering Electronics. Electron Thbee. Electronic Computers. ElectFeaie Issteraiaisatafciffls

.

93. ©RD&8AMCE DEVELOPMENT. Mechanical Research and Development. Electromechanical

Faxes. Technical Services. Missile Fusing Research. Missile Fusing Development. Pro- jectile Ffeisee. Ordnance Components. Ordnance Tests. Ordnance Research.

m* KADI© PROPAGATION. Upper Atmosphere Research. Ionospheric Research. Regular Propagation Servicee. Frequency Utilisation Research. Tropospheric Propagation Research. High

Frespesacy Standards. Microwave Standards.

15. f^lSSlLE DEVELOPMENT. Missile Engineering. Missile Dynamics. Missile Intelligence.

Missile Imstnaaentation. Technical Services. Combustion.
NBS PROJECT

1102-21-noU

NBS REPORT

June 26* 19^2 1759

ON THE CONVERGENCE OF CYCLIC LINEAR ITERATIONS

FOR SYMMETRIC

AND NEARLY SYMMETRIC MATRICES e II *

by

Ao Me Ostrowski

American University

and

University of Basle* Switzerland

PREPRINT

This paper was prepared under contract of the National

Bureau of Standards with the American University*

Washington* D. C*

This report is issued for

in any form, either in who

from the Office of the Dir

Approved for public release by the

Director of the National Institute of

Standards and Technology (NIST) on October 9, 2015

reprinting, or reproduction

ssion in writing is obtained

ington 25, D. C.
.

'
9. In the following all notations of the first note under

the above title are assumed as known*

In the case of the cyclic single step iteration a converse of

Pizzetti’s theorem has been found recently9

. by E® Reich"*

- ® Reich’s

theorem is that if in a real symmetric matrix A all diagonal elements

are positive and if the cyclic single step iteration converges for A

for ary choice of the starting vector5 then A is a definite positive

matrix* In what follows we give an essentially simpler proof of

Reich’s theorem and generalize it to the case of the general linear

cyclic iteration* We prove

III. Let A be an Hermitian matrix and let in the notations of

(3) each of the matrices P be a positive definite Hermitian matrix*

Then,, if the corresponding cyclic linear iteration defined by (2) is

convergent for ary starting vector the matrix A is a positive

definite matrix.

As a matter of fact our proof of (3) gives an essentially more

general results if a regular matrix A is Hermitian but not positive

definite and has positive diagonal elements,, then open sets of

starting vectors in the n-dimensional space exist for which no

single step procedure^ either periodic or not periodic^ is convergent *

10* We prove first the

Lemma. Let A - (av ) be an Hermitian matrix of order n

jxd' —

s and ^ a s'uk matrix of A to the first s

(s < n) rows and columns of A. Assume that P is a definite positive

*The Annals of Mathematical Statistics^ XX5 (19U9) S pp. 14j.8-lj.5l
* l
2

matrix., Let (up 6 ‘5 ° 3

'un

) be a vector and the vector (v.p •»«

9 v^)

be deduced from the vector (u^)

n

(31)

2 3.^ a Vo s ”

,9-1 * Y-s+1

v

ir u

y

2 a o< y u

y

( s 1, * s)

r s s + lo * • • , n)

Then5 if we form the Hermitian to these vectors

( 32 ) % 2 a „ u u

F

v Y

D $ Q s 2 a ,, v v,, ^V Jl

jl

we have

(33)

To prove this lemma we put

(3U) h *

* s L ooe

5 s

)

Then we have from the first of the equation (31)

(35)

n

2 a

)> si

11 °U? V a ^/^

h

P

(

tfK S 1^ 000 s)

¥e have then obviously for the difference

^|9

n

2

n

(36) Qy - ^

- Z* + 2 h M 2^ a

<*i> u2> + 2 sp u^

r

Here we introduce the value (35) of the second sum in the second

right hand termj as to the second sum in the third right hand tern,

we have in using (35)
I

'

.

'

.
3

n _

n m

n s (37) 2 a a-2a,ue2a / u®“Za,h/a r

i p» f Pi r« r ri «rr pi ^

p

pi

a ^

h

^'"pi

a

< s - h

<*

(36) becomes now

(38) 2 a^ o h by® = 2 h , 2 a , h - TM 2 h , 2 a h ^

«,(3 “P * P * *fi I

3 # * p

ft*

and we obtain finally

(39) a^^h^h^g 6 0

which proves our lemma 0

lie This lemma can be immediately generalized in applying to

the rows and columns of A a cogradient permutationj then we see

that if the indices and /s run independently through a group

of s different indices among (15 °°° s n) and y through the

complementary set of indices and the vector (v^ 000

$ v

n

) is

deduced from the vector (u-p ««« 9 u ) by the equations

( ho ) ^ 9

we have still the inequality (33) if the principal minor P = (a^^)

of A is positive definite,,

u

The proof of the theorem III is now immediate „ In applying

successively the operations Indicated by the equations (2) we pass

obviously from the vector to the vector through some

intermediate vectors obtained one from another by a sequence of

equations analogous to ( UO ) | therefore the numbers

(hi) Z a =00

.» JX

form a monot onic ally decreasing sequence of real numbers <> Take now

all components y^ of the vector as 0 and start with such a vector

jf ® jf for which

Z a

(k)

is negative e> Then the decreasing sequence Q' certainly does not

tend to zero and the sequence of the vectors 3 is not convergent

since it otherwise would have to converge to the null-vector 0 This

proves the theorem III«

Obviously the theorem III remains also true if the constant

vector

yj is given from the beginning* since it can be brought into

the origin by a translation* while the cyclic linear iteration is

a covariant process with respect to the translation,,

12c Suppose now that the regular matrix A is Hermit ian and

\ all its diagonal elements are positive 0 Then* if the Hermitian

form corresponding to A is not positive the argument used in the

proof of III can be applied to any sequence of single step operations as described in our lemma for s ® 1 0 We see that in this

case there always exist open sets of starting vectors for which no

sequence of single step operations is convergent 0
,

.

'

-
5

In this case even the use of ,!under or overrelaxation" cannot

change the situation e The use of incomplete relaxation with a

factor q (0 < q ^ 2) corresponds in the notation of our lemma to

the use of the vector (w^, ° ° 9 $ w ) obtained by the formulae

(U2) - (1- q) u

y + q v^

or, what is the same,,

(U3) - u^ + q h^ 9 w^, - u^ «

In this case the formulae (38) and (39) are replaced by

(Uii) 2 a i wv » Z a u u^ = (q^“ 2q) Z h* h^ 4 0

jm r r jis y r *9 p

f

and our argument remains valid,, even if q is varied from one step

to another remaining of course in the interval (0,2) o

June 30, 1932

THE HAT IONA L BUREAU ©F STANDARDS

Functions and Activities

The National Bureau of Standards is the principal agency of

the Federal Government for fundamental and applied research in physics, mathematics, chemistry, and engineering „ Its activities range

from the determination of physical constants and properties of materials, the development and maintenance of the national standards

of measurement in the physical sciences, and the development of

methods and instruments of measurement, to the development of special

devices for the military and civilian agencies of the Government.

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

and various scientific and technical advisory services. A major

portion of the MBS work is performed for other government agencies,

particularly the Department of Defense and the Atomic Energy Commission. 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. The scope of activities is suggested in

the listing of divisions and sections on the inside of the front

cover.

Reports and Pub Heat i ons

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 re- ports 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

(fl.00). Information on calibration 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 Of fice

.

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.