NATIONAL BUREAU OF STANDARDS REPORT

1977

On Gauss' Speeding Up Device in the Theory of

Single Step Iteration

by

A. M. Ostrowski

American University

and

University of Basle, Switzerland

<JjBS>

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
U. S. DEPARTMENT OF COMMERCE

Charles Sawyer, Secretary

NATIONAL BUREAU OF STANDARDS

A. V. Astin, 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.

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

Optics and Metrology. Photometry and Colorimetry. Optical Instruments. Photographic

Technology. Length. Gage.

Heat and Power. Temperature Measurements. Thermodynamics. Cryogenics. Engines and

Lubrication. Engine Fuels. Cryogenic Engineering.

Atomic and Radiation Physics. Spectroscopy. Radiometry. Mass Spectrometry. Solid State

Physics. Electron Physics. Atomic Physics. Neutron Measurements. Infrared Spectroscopy.

Nuclear Physics. Radioactivity. X-Rays. Betatron. Nucleonic Instrumentation. Radiological Equipment. Atomic Energy Commission Instruments Branch.

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

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

Mechanics. Sound. Mechanical Instruments. Aerodynamics. Engineering Mechanics. Hydraulics. Mass. Capacity, Density, and Fluid Meters. Organic and Fibrous Materials. Rubber. Textiles. Paper. Leather. Testing and Specifications. Polymer Structure. Organic Plastics. Dental Research.

Metallurgy. Thermal Metallurgy. Chemical Metallurgy. Mechanical Metallurgy. Corrosion.

Mineral Products. Porcelain and Pottery. Glass. Refractories. Enameled Metals. Concreting Materials. Constitution and Microstructure. Chemistry of Mineral Products.

Building Technology. Structural Engineering. Fire Protection. Heating and Air Conditioning. Floor, Roof, and Wall Coverings. Codes and Specifications.

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

Development.

Electronics. Engineering Electronics. Electron Tubes. Electronic Computers. Electronic

Instrumentation.

Radio Propagation. Upper Atmosphere Research. Ionospheric Research. Regular Propagation Services. Frequency Utilization Research. Tropospheric Propagation Research. High

Frequency Standards. Microwave Standards.

Ordnance Development. These three divisions are engaged in a broad program of research

Electromechanical Ordnance, and development in advanced ordnance. Activities include

Electronic Ordnance. basic and applied research, engineering, pilot production, field testing, and evaluation of a wide variety of ordnance materiel. Special skills and facilities of other

NBS divisions also contribute to this program. The activity is sponsored by the Department of

Defense.

Missile Development. Missile research and development: engineering, dynamics, intelligence,

instrumentation, evaluation. Combustion in jet engines. These activities are sponsored by the

Department of Defense.

® Office of Basic Instrumentation • Office of Weights and Measures.
NATIONAL BUREAU OF STANDARDS REPORT

NBS PROJECT NBS REPORT

noi-io-5100 1977

October 8, 1952

On Gauss' Speeding Up Device in the Theory of

Single Step Iteration

by

A. M. Ostrowski

American University

and

University of Basle, Switzerland

The publication, reprinting, or reproduction of this report In any form, either in wholelor in part, Is prohibited

unless permission is obtained In writing from theOffice of the Director, National Bureau of Standards, Washington

25, D. C, Such permission Is not needed, however, by a Government agency for which a report has been specifically prepared If that agency wishes to reproduce additional copies of that particular report for Its own use,
'

t
On Gauss' Speeding Up Device in the Theory of Single

Step Iteration

by

A. M. Ostrowski*

1. In solving the linear system

(i) a x - y

Vs | f- V V

— x,,,.,n)

with the matrix A, a ^ 0 ( u. = l,...,n) and non vanishing determinant

r

by the single step iteration, we form.

starting from an arbitrary vector %0 , a sequence of vectors

( 2 ) ^k = ( xl^,...,xn ^) (k = 1,2,...)

obtained in

value Nk of

(3)

the following way: For any integer k (k *.0) choose a

the "leading index" from the indices l,...,n; then if

vP k

~ ( r

l

^

^ ' • • * * rn

^

^ ) (k= 0,1,2,,..)

is the k-th residual vector defined by

*This work was performed under a contract of the NBS with the Am. Un . I gratefully acknowledge discussions with T. 3. Motzkin and 0. Taussky-Tod
‘

V
2

(4)

we put

(5)

r ( k ) = h

la x( k )

( ~ 1 j • • * j k— 0 j 1 >

• •

x( k+1)= x( k )(u^ Nk ), r p

v

(k+D

xNk

00

xKk

H

(k)

k

a,«A

In studying this iteration, we will only consider the case where all

y vanish, since we can always by a convenient change of the origin

P

make all y = 0, without changing the f . p ^ k

2. Me consider in what follows only the case where the matrix of

the system (l) is symmetric and the quadratic form

( 6 ) r r

defined for an arbitrary vector (x^,...,xn ), is positive definite .

In this case it is well known and immediately verified that if the

vector £k+l is obtained from the vector by the transformation (5),

we have

(7) K ($k+l) = K (jk)

r

( k )2 X

In using (7) it was proved by Seidel^l874 ^9j that the single step

iteration is always convergent if Nk

is chosen at each step so that
’ f 

t
This is the " relaxation " procedure ). On the other hand Schmeidler

( 1949)^ proved in using ^

S'] ")

^ (7) that the single step procedure is

convergent in the cyclic case when runs periodically through all

indices 1 , 2 , . . . ,n

.

p. Gauss [0 , CO » DO proposed the following modification of

the above procedure in order to speed up the convergence. Put

(9) ,n)

where z Q can he arbitrarily chosen. Then the system (l) can be

written in the form (assuming 7,. = 0)

do)

V\ a OV SV

a z

0

0 1, • • • ,n) )

where the first equation is, of course, not independent of the last

n equations but is useful for the sake of uniformity and for checking purposes.

In particular ^

0o is positive since by (9) ao0 is the value of

the quadratic form (6) for Xy = 1( h) = l,...,n).

4 . From a solution (z0 , z^,...,zn ) of the system ( 10 ) we obtain

at once by (9) the solution (x]_,...,xn ) of the system (l) . The idea

of Gauss is now to apply the procedure, described in ( 4 ) and ( 5 ), to

the system ( 10 ) . If we obtain then, starting from a vector

-r , (0) (0) (0), = ^ z 0 > Z 1 ’

• • • 3 zn ) a sequence of the vector:

Tk = ( z 0

(k)

. zl

(lc)

i • • • » zn

(k ) ) .

ve consider at the same time the corresponding vectors

5 k = Wi (k) - z

o (k t z 2

< k)

- z

0 W,...,zn

W - z0 «)

If then in the passage from "J k

to J the leading index Nk

is ^ 0

we have

( 11 ) 2i^, (k) zi

k) =±a (z

n>=o v v -tt: ^

v

v v (k+l) (k) 2. aN v

z k

zNk = %k - = z„k _

a

Nk

11 k

- zo^

k t = ^

k t

(k)

(k)

r%

a-®kNk

(k+l) _ z (k)

'f- t 1

z' - = z'~‘ (k £ Nk ) .

Since here z, (k+l) — 2

(k)

, ve see that the corresponding n -dimensional vectors 5k. 5 k+l are connec 't e(i exactly by the formulae (5),

so that in this case there is no essential change compared with the

original method.

5. If however = 0, then only z o (^0 i S changed and therefore all

components X]_( k )

,

. .

,xn

( k ) are changed by the same amount. In this

case we have obviously a new possibility and the question arises

b

whether in this case the convergence is indeed speeded up. Of course

under the convergence in this case is not meant the convergence of

the vectors but the convergence of the corresponding vectors 5k • This question is apparently not as yet settled as widely contradictory opinions are to be found in the literature.

6. In what follows we will prove that in the case of the relaxation

rule (8) the procedure remains convergent , and for n> 2 the convergence is speeded up by Gauss' transformation "in the statistical

sense" ^ i f

< VT~ -Mm VaT“

r r

and is not speeded up in the same sense if

it. a ^ ZL-fT -

' ±77 rr

Kl

r r-r- w rp pu

The probability that the decrease of K(^) is greater for = 0

than for Nk >0 is always positive for some values A of

in the first case and vanishes in the second case.

For n = 2 Gauss ' device has no effect in the second case and

speeds up (this time in the "absolute" sense)" .

It is quite different in the case of the cyclic one step iteration. In this case we will prove that the procedure remains convergent, but for any n^2 there exists matrices for which the modified procedure is slower and others for which the modified procedure

6

is indeed faster than the original one.^)

7. In what follows we will say the two (n+l) -dimensional vectors

J= (z

Q ,z 1 , . . . ,zn ) and

'J' = (

Q

»,

n

1 ) are equivalent

if we have z^ - z Q = z^ 1 - z 0

‘. In the class of vectors equivalent

to

"J there exists a reduced one

~J = (0,x^, . .

,xn ) and the corresponding n dimension%lvector (x-^,...,xn ) is uniquely determined.

We have for the component of the residual vector corresponding to

the index 0

(11°) r0u W= £ ° ^ ^ “ - v= t v

and we see from (ll) and (11°) that the residual vector for the

system (10) does not depend on the component z Q but only on the corresponding vector . It follows from (9) and (6)

^

a zM = SET a (z00-zo 00) = - 2- r( k ) , ViO V V:| OV >>

n a

r r

v ~ tn r

a

r

J~ a, v

-z z. =. >_

jV^-0 1

^ / n \

C

-

* ^ a x

i 0

v V--,

'

- <“

5 B

V: \ r

v r o>,) .)

ja- - T” * > a x % — V

c— yu.v p- J

V-
f
7

( 12 )

n a z z = ^ (i v

cl X. X .

, . z ^ h V

’ 1 hVil

Qo . It is obvious that the algebraic identity corresponding to (7)

remains also true for the system (10), although the corresponding

quadratic form is only semi -definite . Therefore and from (12) it

(k)

follows that the relation (7) is also true for 1% = 0 where r0

is given by (ll) , and the quadratic form K is the positive definite

quadratic form (6)But then it follows

,(k)2

0 (k-j-oo) , (17)

a%Nk

Q . If now the relaxation rule (8) is used, it follows obviously

(k)2

a

0 (k. -oo ’r

= 0,1, ...,n)

->0 h = 0, 1-,..-,*)

and therefore since y^ = 0 and the determinant in (4) does not

vanish x ^)__

0 (k—>c>0; o = l,...,n), and we see that the

t

1 ' modified procedure in the case of the relaxation rule (8) is

always convergent

10. The rate of the convergence in this case can be measured

by the decreases of the quadratic form K(J k ) each step. But

then obviously the convergence is each time speeded up in choosing

% = 0 if we have
/
{ 14 )

8

r (k)2

0 _ Max

cl oo --v-r

a

.002

K

In estimating the probability of (14) we must of course assume

(

) that rQ ^ 0, that is to say, that is not = 0. But then one

of the r W ( |4 = l,2,...n) must vanish. For n = 2 there remains

only one r| k ) ^ 0. If for instance = 1, ipM = 0, we have

= - rQ

( k ) and (14) is true if and only if a00 < a22 . = 0, (14) is true if and only if a 00 ^app. We see that In

the case a 00 ^Max (app, aP2 ), (14) never occurs and Gauss' device

has no effect at all.

If however a

Q0<[Max (ap-j_, a^) * the procedure is indeed speeded

up/' (and becomes cyclic if an additional convention is used for

a ll = a22 ) • Suppose now n^>2. In order to estimate the probability of (14)

put

Max %- = m

2

cltr

and ask for the probability of the inequality

yy. 2 v 2

a.‘oo

if one of the r (u-= l,...,n) is = 0. If we put ^ \

9

(15) ex' = v/a m,

^ = s/a. m , p o

v

oe,

we have to determine the probability of the inequality

r\

(16)

r

-

r

u- >°<o - = 1 V

in assuming that the r^ are independent variables, uniformly

distributed conformally to the condition

(17) Max ' = 1; V>0 (u = l,...,n; U. ^ = 0,

H--," C< t \ I %

r where X= Wk _!.

11. In a previous paper C6 3 we have proved that the probability

F*(o-) of the inequality r^ +,,,+r^<’C“ under the condition

Max = 1, o< . o(u = 1 N) for uniformly distributed r is

r-(-,K ** r v t

4 given by the formula

N

F* (<r) =

+ -A 2 V N-l

0< - o(L

+ +

and is a strictly monotonically increasing function of as long as

we have

(18)

N N

V-l Vi I

The symbolism used in the formula (18) is the following; we denote

by Iq.

10

(19) k+

5

0

k t 0

k < 0

and by S

( 20 )

the displacement operator defined by

f(T-) = f (<J“- ^

)

The probability of (16) under the conditions (17) is therefore

( 21 ) where

(22) F(<T) =

2(1 - FK,) ,

\ 4S ^

for ^3" =o^. In the case n = 3, (22) becomes for ^- = 3, for instance,

i

^

[(' • s*>- s”3hand more generally for any ^

- «r- * *0* )

(23)

12. (21) is positive if and only if ^ . It is easy to

® A

prove that

that is

(24)

m

“<<,< 2_\ =

u-1 r~ n

v/5°° < 2—

p

s i

r n

Indeed (24) follows immediately from

since we have for u £ \)

satisfied even for one X only. Consider indeed the symmetric determinant

1 x x

I X 1 X

X x 1

the condition that the corresponding quadratic form is positive definite is obviously x C 1 and we have here

= (x-1) 2 (2x + 1) ,

)

°<1= °<3= > V 3 + 6 * ; °<

0 = 4 3+ 6X
.

"• ’
12

and we have hereof 4 and °^o > ©<—if . In

the general case (21) is positive for all X if we have

(25, a)

and (21) vanishes for all X if we have

n

(25,b) V ^ ^ - Min °<

"V= 1

v v

14. In the example considered by Gauss the matrix of the equations

(1) is

3 -1 -1 \

and we have with m = 1

“<;= 2, 0^= /3 , o^= 2, O^ - s/5, o< = 2 + 2/3 ,

and we have for every A : cV < o< - ©< and the nrobability (21) becomes

t> A

o< - o( 2 \I~S ~~ °^-x *

13

This is .46410, .42265, .46410 according as A. = 1,2,3. The probability for Ujj. = 0 is therefore in this case > .42265, that is fairly

great, due to the a ^ ( ^ ^ >>> ) being negative.

15. "We consider now the cyclic case. Here it follows from (13)

rM 0 (

k

~ y )

and therefore from (5) and the corresponding formula for 3k arid- Nk = 0.

x

(k+l) _ x(k) 0 (k^ooj u. = l,...,n) , r- r*

r

and therefore by (4)

Pk+i) _ r

(k) 0> (k -*oo; M - 1, ...,n) . ^ r 1

Or more generally for each constant integer

ri

k+if ) ' rik) 0 (k-*<sO; M

=

f* r

h

But for any fixed ^ , among n+1 consecutive values of k there is

one for which Nk = ^

, therefore it follows that

(k -> 00 ; = 1, . . . ,n) ,

and, since the determinant in (4) does not vanish,

(k-.oo

; ^

= 1, . . ,,n) .

hk)-» 0

h

x^—> 0

r

T

r. see that the modified procedure is indee.. 3 *. -overs ant

.

16. In comparing the rate of convergence of the ori inal and.

l le modified cyclic single step iteration it is better to change our

xG nations in the following way. If we start with a vector

^ 0

and apply the complete n -cycle of single steps corresponding to

Nr = l,...,n, the obtained vector will be denoted by and the

P - L vectors obtained in repeating each time the complete n cycle will

be denoted by J 2 * ^ 3 » • • • • In the same way, in the modified cyclic procedure we obtain,

starting from a vector ~^ 0 and applying each time the whole (n-fl) eye

corresponding to II-^ = 0 , 1 ,..., n the sequence of vectors "J .. . .

17. The rate of convergence of the usual cyclic single step

iteration depends on the maximum modulus Ajj of the roots of the

equation

( 26 ) N ( Jp =

3, - • 6 ^ i

• - u

1 > * a

**

1 A a n -

, , -v a

! 7 a V) , A a . H 2. 9 , A 2

1 n 2 > r\

% - 0

t

!

n V- -

1

We have then, if A >0

( 07 \ \£- ( ! \ - KJ ( X

- a o K J C -

)

15

while the starting vector

4 \ not tend to 0 with k—>oc>. j

can be chosen so that ? tC does

18. We will now characterize in a similar way the rate of convergence of the modified cyclic single step iteration.

We decompose A in the following way

where D is the diagonal matrix with the elements an,..., ann , while

in L all elements to the right and on the main diagonal and in L*

all elements to the left and on the main diagonal vanish. We have

A / X then for the matrix A of the system (10) the corresponding decomposition

( 28) A = L + D + L* ,

Then we have between J0 and Jq_, as in the theory of the usual cyclic

one step iteration, the relations

(L+'b)-5 1 + L*T0 = 0 ,

(30) Jl - - (L + D)-1 i«T 0 •

19. As has been mentioned above the result of this operation

is not changed if To I s replaced by the corresponding reduced vector

To = (°> x:

( 0 )

/ Q

\

,

. . . ,xn

'

* )

. Before we go on from j i_ rep „ce

therefore ~J again by the corresponding reduced vector

'N

7 l « (o,x£1) ,

. . . ,xn

W )

. For this purpose we apply the transformation - zQ ( m # n) which is equivalent to the multiplication by the matrix

¥e have then finally in putting

- -K„ (L + D)"1 L* ,

35)

A

T

Hi

- k A

' - 3 o

( k = 1,2,...)

we use now the following result due to Werner Gautschi

£

5 i If for any matrix c = (c ) we define as its "norm”

and if B is a square matrix of the order n for which the greatest

modulus of the fundamental root Is 2\^ then ire have

17

(34) N(Bk

) = 0 (y^ kP -1

) (k ->oo ) ,

where p is the greatest multiplicity of a fundamental root of B with

the modulus A . 21 o If we apply this to the singular matrix ( 32 ) and denote

the maximal modulus of a fundamental root of Q0 by A

g

, the maximal multiplicity of a root with modulus Ag is 5 n -1 ifAg^ 0 , as will

follow later from (42) . We have therefore

(35) K (Q0

k

) = 0(A?

3

On the other hand it follows from (35) in applying Cauchy-Schwartz inequality

Ipswon.'

and we obtain therefore

(36) !k 0(A„

k kn_1

) (k->oo )

22 <, On the other hand it is easy to show that for a conveniently

A Cl y chosen starting vector 0 the expression j y

^ does not tend to

zero Indeed if is an eigenvector of Q0 corresponding to a fundamental root A with l*|-* g, we have

and iterating

18

But, since the first row in Q0 consists of zeros, the vector^ is a

reduced one and can be taken as . Then we have

Ik

- x

k

T W= ( jt)

k

T

and this does not tend to zero with k—

2J>, We are going now to transform the fundamental equation of Q0

and introduce for this purpose the matrix

which corresponds to the transformation

(38) r0 = fV \ = S- Z

,

( » > °)

and goes for £ 0 into N0

. Since the inverse of ( 58 ) is for

f Os

z

0 = J

y0 > 2

v = \ ~ yQ ( 'O 0 )

we have
n..I

-
19

(39) N

-1

0 . . .0

1 . . .0

0 0 + 9

0 . . .1

Oo . .0

\

0

1

The fundamental equation of Q0 can "^ e written in the form

(40) Lim \ /\.E + N (L + 'b)

1

L* 1 = 0 .

24 „ On the other hand we have identically since ) N | = &

(41) ( | L + D | ^

f | A E + I (L +l>)~ 1

L*f) = &\ (iftD)N^

1

+ L* |

and obtain therefore the fundamental equation of Q in taking the limit

for f-)0 on the right in (4l) . Now we have

1 a

£

00

0 * • 0 0

f(a. +a- 1 £

x lo II1 a•I 0 0 0

e •

» » »

&r

z(b * Mo+.,tl )

n-in-l a

h-i i ^ . . H-l z. a 0

~r (a + . • + a. e v ^ 0 liny) 3-M

a. • * 2. a a / r\ ^ /

20

where a + a + . ,± a

no * i n

n

0 by (9) and we have therefore identically

tkct^M'+LT- a:

cL

0 0 a

0 \ a

o-a.

"*

a + a lo IJ A a11 a

.v

•

a. +• a + a

10 2 1 i-i. A a.m

0 9 * »

a. +. .+ 2 A a. \w-| In— * 1 vv-l E» 0 a_

>> » a

n z.

a 2

oh- 1 no

IV>-| 'h

a 2

Zr\-\ ZY\

2.

*>-1 •'-i n-i ^

2 a

«h-| VI irj

^Q> ^" S ^iere ^01’ e maxi^uKi modulus of the fundamental roots of the

equation

a_

0 o

a

\o \ t

(*2) GOO

O I xa

M

a +..+ a h

. 1 V>-> 0 -I n *l 1 0 cL

Vi |

* a.

0 \n~\

<9 ®

o n

a

u-i » n

A a a

h-m-i n-t n

a.

w h-1 h n

- o

21

25 . In specializing for n = 2 we obtain in particular 3 if we put

a12 = a22 = &2 3 a12 = a21 ” 'o~ anc^- assume q

- / 0 for

G : /*-) 5 2.

ai + a2 + 2 -a^ - CT -a2

- (p

- cr a i

“*

0 0" a2

(45)

- C a

p

+a2 + 2 “) a

2

X- - p ( a2. 'Kr) ( a2 +Cr) >

C a <a (a + a + ^

1 2. I "2-

while the equation for

n

2 U)

A N

reduces

_ A a or* I Aa2

to

= 0

and gives

(44)

a-j a

2

From (45) and (44) we have

It. -

I a-i-t^ri I \ I o-l (a., -v a. z + jt)

( 45)

26. If we square this, subtract 1 and. multiply by the square

of the denominator we obtain

[

( i*r)( 4 ^

q-) - iy w1

] [ ( i,^)( 1 +t) -+ <r(a 1+ a.p+ z<r

J

]

=

^ + 3^ 1

).

Since the first factor is positive, we see that Aq =^jj according

as the second factor is = 0, but this factor is ~( a. 7. ^7 ) (<3. vZt) — <T

and we see that 'X

q

according as

(46) a 1 + 2cr) (a2 + 2 3") =- cj“

9 ^ Here qp ^ 0 is subject only to the condition 0“ < ^-,3*2

In particular for CT > 0 we have always A^. ^A^. ¥e see that for

7y

2 71 can be as well > A as C A

) GrO H N /

27 . To prove the corresponding result for n>2 consider the matrix

A corresponding to the quadratic form

(47) K(^) - a^ Xj_ + 2q'x1x 2 + a2 x

2

2 +

VO

In the corresponding determinant

first column are

(--3 h

for G(/L) the elements in the

^

o + a|M. 1 + 0 • « +a — "(a + . . .+a )

fAin

and vanish therefore for k i 2. The same is true for the elements

to the left of the main diagonal A <3. with i*. > 2 and and th

I** is I

| elements a ( \>< n), while the elements on the diagonal A a

and & n

become respectively A- and 1. we obtain therefore

i i u > /r i

G(7l) »2 (a)

so that A a

is in this case given also by (tyjj) . 28. In the same way it follows from (26) that H in our case A

is equal to A

n_1 m2 (a) and therefore A pj is given by (44) . We

can have therefore in this case according to the chosen values of

CP as well A q >A ^

as well G ^^ N

* It may be finally remarked that the value of A,, is not changed

if the (n+l) equation in (10) and the corresponding new variable

z 0 are not put at the beginning but interpolated between two Indices

|u, 3 U + 1 or even put at the end. Indeed this amounts to the old

process applied to a transformation of T by a finite sequence of

/s J U

single step iterations, but then 0 is carried over in the general

reduced vector and the Invariency of /t qfollows then from the

characterization of A n contained in the development of numbers 21

Footnotes

This special rule goes hack to F. R. Helmert (1872) [ 5

*] . The

relaxation rule indicated previously by Gauss [G and Gerling DO

is different as well as that proposed by Southwell 0-G , but the

rule (8) is apparently the most advantageous one.

The same result was proved, 1949, by E. Reich [ J~\ independently

and with a completely different method .j ^The proof of it is

quite similar as in what follows the proof of the corresponding

results for the modified single step iterations, (see (35))*

If - 0,, then already J n vanishes identically and the

in)

solution is obtained at the most n steps,

5. If q. = 0, then already 3 n+l vani sbes identically. |3.This

agrees with the results mentioned in the paper [ia] of Forsythe

and Motzkin, footnote 24.
.
2

Bibliography

[ 1~J Dedekind, R „ , Festschrift zur Feier des 150 jaehrigen

Bestehens der Koenigl. Gesellsch. d. Wiss. zu Goettingen (1901), 45~59j Werke,2. Bd., p.293~306,

namentlich p. 300-301,

DuQ Forsythe , G. E. and Motzkin, T, S. An extension of Gauss’

Transformation for Improving the condition of

Systems of Linear Equations. Math. Tables and

Other Aids to Computation , v. VI,(1952i p. 9-17

,

footnote 24.

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

[3I Gautschi Werner, On the Asymptotic Behavior of the Powers of

Matrices 9 Duke Math. J.

[*4j Gerling jC . L^Dle Ausgleichsrechnung usw., Hamburg -Gotha

(jdj Helmert, F. R., Die Ausglgichuncrechnung Nach Der Methode

Der Kleins ten (Quadrate Mit Anwendungen Auf Die

Geodasie Und Die Theorie Der Messinstrumente

,

Leipzig (1872), p. 136.

G? ] Ostrowski, A. M., Explicit Formulae for the Distribution

Function of the Sums of n Uniformly Distributed

Variables, UBS Report 1601 (April, 1952)

.

fr] Reich, E„, On the Convergence of the Classical Iterative

Method of Solving Linear Simultaneous Equations,

Ann. Math. Stat. 20(1949), p. 448-451.

C8j Schmeidler, W., Vortrage ueber Determinanten und Matrizen

mit anwendungen in Physik und. Technik, Berlin (1949)

[9] Seidel, L., Uber ein Verfahren usw.. Munch Abhandl. Math. - phys. Kl. 11(1874), p. 81-108.

[10] Southwell, R. V., Proc . R. S. L. A151 (1935) , p. 56-95.

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 listing 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 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 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.
1