NATIONAL BUREAU OF STANDARDS REPORT

2007

FOUR ARTICLES ON NUMERICAL MATRIX METHODS

Translated from the Russian by Curtis D. Benster

Editor: G. E. Forsythe

National Bureau of Standards

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
U. S. DEPARTMENT OF COMMERCE

Charles Sawyer, Secretary

NATIONAL BUREAU OF STANDARDS

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

1101-10-^100 August lh3 19^2 2007

FOUR ARTICLES ON NUMERICAL MATRIX METHODS

Translated from the Russian by Curtis D 0 Benster

Editors G. E. Forsythe

National Bureau of Standards

PREPRINT

** These translations were sponsored in part by the

Office of Naval Research

<NBS>

The publication, reprint

unless permission is obta

25. D, C. Such permi:

prepared If that agen<

Approved for public release by the

Director of the National Institute of

rt, Is prohibited

rds, Washington

)een specifically

or its own use.

Standards and Technology (NIST) on October 9, 2015
'
CONTENTS

Page

I. A Numerical Method for Determining the Characteristic Values and Characteristic Planes

s \ of a Linear Operator, by A. M. Lopshits 1

II. The Application of Polynomials of Best Approximation to the Improvement of Iterative Processes, by M. K. Gavurin . LiU

III. Some Estimates for the Method of Steepest Descent, by M. SH. Birman $1

IV. A Process of Successive Approximations for

finding Characteristic Values and Characteristic Vectors, by N. Azbelev and

R. Vinograd £7
...

'! .

1 /;' , -x/'U \7i x..x

:

.

, :v

• ••

.

• .7- :
I.

A NUMERICAL METHOD FOR DETERMINING THE CHARACTERISTIC VALUES AND

CHARACTERISTIC PLANES OE A LINEAR OPERATOR

/"> 1 A. M„ Lopshits

The numerical method of determining the coefficients of the

characteristic equation of a linear operator (the characteristic

equation of a matrix) that was suggested in 1931 by Academician

A. No Krylov [1] required a considerably smaller quantity of computations than the methods that had been developed earlier. Nevertheless neither this method nor that published in 1937 by

A. Danilevsky [2] (which reduces the numerical work to approximately two-thirds of that required by the Krylov method) effected

simplifications in the solution of the problem of determining the

characteristic vectors of a linear operator. A geometrical method

that I have suggested [ 3 ], [

I4]

, which leads to the construction of

^"Translated from Moscow, universitet, fiziko-mekhanicheskii

U

fakul'tet, nauchno-issledovatel'skii institut matematiki i mekhaniki, seminar po vektornomu i tenzornomu analizu . .., Trudy , vol.

7 (19)i9), PPo 233-259.

Translator's acknowledgement: In construing two passages by

which he was balked, the translator has enjoyed the assistance of

Prof. Dimitry M„ Krassovsky, Slavic Consultant, UCLA, to whom his

thanks are extended.
1
2

the characteristic equation in the form in which it is suggested by

Academician A, N c Krylov9 offers the possibility, with a suitable continuation that is expounded in the present article, of constructing a

new algorithm for the solution of the problems indcated in the title.

This algorithm provides a new geometrical scheme for reduction of the

matrix to Jordan normal form.

§1„ If in the sequence of vectors

2 1

a, Aa, A a, » •

only the first m are linearly independent, we then have the equation

(1) A

m

a + oc 1A

m=°1

a + °^ 2A

m"2 a + ® • ° + ex. ^Aa + 04 m

a = 0 ,

where the numerical coefficients °

• are uniquely defined in

terms of the initial vector a (for a given operator A| a discussion of

a computational scheme making possible the determination of the coefficients in terms of the coordinates of the vectors a, Aa,

A

2

a, 09 °, A

m

"*'a, A

m

a is given in §9) .

The planec <X ? defined by the vectors a, Aa,

A

m

^a

1

The Roman-type minuscule a designates a vector of an n-dimensional

vector spacer the Roman majuscule A designates a linear vector function

of a vector argument (a linear operator) relating to the vector a_ the

vector Aa, The product of the operators A and B, i 0 e„, the operator C,

is defined by the equation Cx = A(Bx), and we shall write C = AB . Let

2 2 3 us agree also on the conventions AA 3 A j AA" s A , etc.

2

That is, the manifold of all vectors that are linear combinations of the vectors A

1

a (i = 1, 2, ° °

° , m-l) c
•

'

• : .

:

' " "" :

.fi

.

4
“3"

("belonging" to the vector a) is obviously an invariant plane of

the operator A (i.e„ s contains the vector Ap if the vector p is

taken from this same plane). If we introduce into the discussion

the "characteristic polynomial 0(x) belonging to the vector a":

(1 T ) 0(A) = A

m +cyAm” 1

+ •••

v r +c* x + a

1 m-1 m 5

it is easily seen that, for any vector x lying in the plane Ot,

the equation

(2) 0(A)x - 0 ,

holds, where

0(A) - A

m

+ cx_ A

m 1

+ »

•

r

• + ot -A + oc 1 m-1 m

Indeed, multiplying (l) by A

1

, we obtain

A

10(A)x = 0

or, on the strength of the commutativity of polynomials in the

operator A, we obtain

0(A)A1 a = 0 , i = 0, 1, 2, •••, m-1

i„e„, equation (2) holds for the m linearly independent vectors

A a defining the plane OL

§2o Let us employ the designation

oo(A) - w(A ) (3) ~ A

1

'~1~ ' D“M •

cu(a) being an arbitrary polynomial in A, and A^ a given number;

let us also use the designations

(3 ? ) D

1

co(A) = DD

1_1

60(A) ; D°^(A) = co(x)
••
If A^ is a root of multiplicity k of the characteristic polynomial 0(A) , we obviously have

(3") d^x) = -!Lx-L.

t d = i j 2< k ) . (A-AP

Let us introduce into the discussion the "structural vectors"

a

l

s a2’

’ °

° > defined by the equations

(U) a

±

= D

10(A)a (i - 1, 2, k)

and which "belong to the root A^»» e

It is easily shown that the structural vectors a^ are linearly

independent and satisfy the system of equations

( 5 ) (A - A

1

)a

i - ai

_ 1

? i = 1, g, k; a

Q

= 0

Indeed the vector a^ is, on the strength of formula (h), a

linear combination of the linearly independent vectors a, Aa, •••,

A

m 1

a, in which the coefficient of the vector A

m 1

is equal to unity,

whence it then follows that the vector a,, is linearly independent

of the vectors a^, a^, •*», Equations (£) are, moreover, a

consequence of the identity

(A - A^D^A) = D

1_1

0(A)

If A^ is a root of multiplicity one, we obtain a unique structural

vector belonging to the root and satisfying (on the strength of

(£)) the equation

Aa

l

= A

l

a

l

i„e 0

, we obtain the so-called characteristic vector a of the operator A and the characteristic number (characteristic value), A^, that

corresponds to it 8 The computation of the coordinates of this

characteristic vector reduces , therefore , in accordance with formula (3"), to the computation of the coordinates of the vector

®1

iiAL a = A'

'A. A

m-1

+ ptm-2

a + m-2Aa +

i.e., to the computation of the coordinates of a linear combination

of the given vectors «, (A calculation of the number of computational operations required for this, and a comparison with the number

of operations required for the solution of this problem by existing methods 9 will be given below.)

If the multiplicity of the root be greater than 1 (k > 1),

formulas (£) show that the structural vectors a^ s a^, ° °

• , a^ define an invariant plane belonging to the vector a^ to which the

characteristic polynomial (A-A^) 1

belongs,, We shall call such a

plane a characteristic plane of the operator A (an axial manifold

[ £] s [6])„ (Thus the characteristic vector is a "characteristic

plane of one dimension. 1 ') Formulas (U) give us the possibility of

computing the coordinates of the structural vectors a^ s a

2

s

’ 00jak

that define the characteristic plane Ol belonging to the characteristic number A^„

Let us note that for any vector x lying in this plane, the

equality

(A - X ) kx = 0

holds.

§3o If the degree of the constructed characteristic polynomial 0 (a) belonging to the vector a is equal to the number of
.

I

-
- 6

'

dimensions of the vector space (m = n), then, having constructed

in the manner indicated the system of structural vectors for each

root K . of multiplicity (which vectors define a k^-dimensional

characteristic plane ou), we arrive at a complete decomposition

of the vector space into characteristic planes, since two characteristic planes belonging to different roots will not have a common part.^ In this case (to which, strictly speaking, A„ N. Krylov

[1] limited himself), for the determination of the characteristic

numbers and characteristic planes the following operations must

be effected:

1, The computation of the coordinates of n vectors: Aa,

A

2

a.

. n-1 . n A a, A a. n

2» The resolution of the vector A' a in terms of the linearly independent vectors a, Aa s A

n ^a (the computation of

the coefficients of the characteristic equation consists of just

1

See [ U

.

2 The determination of these coefficients can be effected, on

the strength of (l) (if we consider that m = n) by means of the

formulas

=

( a , Aa ; .n-i-1 .n-i+1

, A a, A a. Ana) ° ^ 4 1

(is= l,2, * *

* ,n)

,

where

6

±

• ( - l)

i

(a» Aa, .... A”"

1

*, A

n

a)

(the symbol '(p » ••

,

pn

) here denotes the determinant whose s-th

row is the aggregate of the n successive coordinates of the vector

p ). Substituting these expressions for oC. in formula (l 1 ), we

S 1

/
'
“7~

this), i.eoj the solution of a system of n linear equations in n

unknowns „ ^

3° The computation of the roots of the characteristic equation*

ho The computation for each root of multiplicity of

the coefficients of the polynomials —

? j = 1 2, • • • k.,

(,. - A. )i

i 0 e O g the computation of the coordinates of the structural vectors

of the characteristic plane (belonging to the root ) with re- n-1

spect to the coordinatal systems a, Aa s

°

*

s A a.

5° The computation of the coordinates of the structural

vectors in the initial coordinate system (in accordance with formula (U))»

If all roots of the polynomial are of multiplicity one, for

computing the n characteristic numbers and the coordinates of the

n corresponding characteristic vectors there will be required (if

the operations required for the determination of the roots of the

3 characteristic equation be disregarded) about hn^ additions and

multiplications

«

To solve this same problem using Danilevsky’s method [2] for

obtain the characteristic polynomial of the affinor A in the form

in which it was proposed in 1931 by Acad» Aa Nc Krylov* The method given above for obtaining this polynomial was given in 1933

by me [3l» See also [ U] s P° 1?6°

1

See below a §9=

- 8“

the computation of the coefficients of the characteristic equation,

if for each root we compute by the familiar method [6] the coordinates of the corresponding characteristic vector (i 0 e 0s solve the

corresponding homogeneous system of n linear equations in n unknowns) 9 about 2(n- l)"n additions and subtractions will be re3 2 quired 9 i.e„ s approximately (n- l) p/2n as many operations as does

the method referred to above.

§ ho If the characteristic equation has the complex root

A^ - ot + of multiplicity k^ s -the effectuation of the operations

indicated above is complicated computationally 0 In order to reduce the number of operations a preliminary construction of a system of polynomials with real coefficients

fs M —5 2hL-2 T-5 U - 2Aa + or + (3 d

)

( s — 1 s 2 9

°

• 0 , k)

is called for 9 as is also the construction of a system of linearly

independent real vectors

b

g

- fg (A)a (s »1, 2, •••, k)

which will obviously satisfy the structural equations

(A

2

- 2aA + + (3 2

) b = b , (s = 1, •»», k,; b = 0)

S S“± X s

One has no difficulty in showing that the characteristic

plane belonging to the complex characteristic number a + i(3 is determined by the (complex) structural vectors

» (A - (a - i(3))V (i = 1, 2, a. •••, k^

i
'
9-

§5° If m < ns the characteristic planes constructed in §1 do

not exhaust the vector space; for the determination of the new characteristic planes the process indicated above may be repeated,

choosing for the initial vector an arbitrary vector a* not lying

in the plane CJt. If the characteristic polynomial 0

® (a) belonging

to this vector is of degree n, the decompositon of the space into

characteristic planes may be conducted as has been indicated above.

The computational labor spent in determining the coefficients of

the polynomial 0 (a) proves not to be utterly superfluous here?

the polynomial 0(A) is a divisor of the polynomial 0

f (\) and this

fact of course facilitates the computation of the roots of the

polynomial 0 ' (A) 0

If s however a the degree n® of the polynomial 0 ®(a) is less

than n0 we will obtains for each root of it that is different

from the roots of the polynomial 0 (a) a a new characteristic plane

that does not have a part in common with the plane Ob If on the

other hand a root equal to a root A^ of the polynomial 0 (a) is to

be found among the roots of the polynomial 0®(A) s let the characteristic plane at5 , defined by the structural vectors

a^ = D

10»(A)a l (i - 1, 2 S

• • •

,

k)

belong to it.

The relative situation of these two characteristic planes belonging to the same root a^ is determined in accordance with the

following

Theorems Let the characteristic
|

e I h mk- - > at t. I

.

.

.

i
-10-

a

2

. ••• ak

) and 01* ( a^. a

2> '*’> a^

) k *

belong to the same root , !•£» s let

(I) (A ~h)a

i

~~ ai"l 5 a = 0

o

(i " 1» 2, \ k)

(ii) (A - xpa! i — a „ - : a-1 ’ a* = 0

o

(3 - 1. 2, ••• X)

and , furthermore , let the following equalities hold :

= hA

a

2

= °ia

2 + °<2 al

-

a

3

= °ia

3

+ V2

+ “S

8

!

' (III)

a = <* a + c* a . + m 1 m 2 m~l

* + 'J

If s along with this „ the vector

C-. = a* - (o£ a + oC 0 a + ••• + oi a0 ) 1 m+1 1 m+1 2m m2 7

is not collinear with the vector a^ s the vectors

C

l

fl C 2*

c '°

5 C^-m

defined by the formulas

°i

= am+i '

<*:

(IV) (i

, a . + c*0 a . n +

* 1 m+i 2 m+i-1

+ oc a. , ) m l+l

1, 2, X*m)

determine a characteristic plane *C belonging to the root and

having no part in common with the characteristic plane Gi

.

Proof. Applying the operator (A- A) to both parts of equation (IV), we obtain, using (I) and (II):

(A - \ )c. = a ' , - (cx a + o(0 a . ~ +

• 0 ° + a a.

)

l i m+i-1 1 m+i-1 2 m+i-2 Hn l

and, accordingly (on the strength' of (IV) and (III)),

(V) (A - \

1

)c

i

= cn>1 | c q

* 0 ; i = 1, 2, %-m .

It thus remains to be shown that the vectors a, . c0 •». c v 1’ 2

s 3 %-m

are linearly independent and form a region^ oC having no common

part with region Oi 0

Let us first satisfy ourselves that the vector c^ does not lie

in region <X Indeed, in the contrary case the equality

(VI) cx

- CT1

a1

+ a

2 a

2

+

••• + cr^

would holdo

Applying the operator (A = \) to both sides, we obtain, on

the strength of (V) and ( I)

g

0 = 0^ + a

3a

2

••• ^akVl

and consequently

Substituting these values for c\ in (VI), we would have

C

1 ^i3! »

i.e„, we are led to a contradiction with the condition of the Theorem.

We shall now show that the vectors c^ and c

2 are linearly

Editor's notes Here and below the author uses 'region 1

(oblast') for * sub" space.

independent „ Indeed s if the equality

Cp ~ crc1

held, we would have the equation

(A - ?v1

)c

2

= cr(A - X

1

)c1

or, in accordance with (5>)

c^ = 0

which contradicts the condition. We shall now show that the plane

formed by the vectors and does not have a part in common with

the plane Ol„ Indeed, if the equality

a

l°l

+ a

2

c2

= ^l3

!

* °2a

2

+ ' ’

' + a, f 0 ,

held, then on applying the operator (A - ?v^) to both parts of it

we would obtain (on the strength of (V)):

“

2

=1

- ‘ °2a

l

••• -cr^.

i.e 0

, we would be led to a contradiction with the already proven

thesis that the vector does not lie in the region Ot.

Continuing analogously, we become convinced that the vector

c^ does not lie in the region formed by the vectors c^ and C 2

(for

from equality

C

3

=CX

L C1

+CX

2

C

2

it would follow that

(A - X

1

)c

3

= oc^A - X

1

)c1

+ o^

2

(a - \)c2

LBy this it is also proved that c~ f 0.

13-

i 0 e 0s that = ov^c^), and we show that the region formed by the

vectors does not have a part in common with the region

Of, since, applying to both parts of the equation

a

l

c

l

+ct

2 c

2

+a3°3 ’*1*1 + c

2 a2

+ + °kak

; “3 ^

°

the operator (A - Tv), we would arrive at the equation

a

2 ci

+ a

3 c

3

= + * * 0 + ^Vl , oc3

f 0 ,

which contradicts the already proven thesis that the plane c^ s c^

has no common part with the plane OL The proof can now be completed in the obvious fashion.

Let us remark in conclusion that if m - 0 (i„e 0£, if the vectors a^ and a^ are not collinear), the regions Ol and Ol* have no

part in common and Ol? - JZ * If, however, m ~ , region Ol1 then

lies in region Of and accordingly JZ “0,

Thus for each root X of the polynomial 0

’(a) that is also a

root of the polynomial 0 ( x) we shall either find a new characteristic plane «C. belonging to this root and not having a part in

x common with the characteristic plane Ot^, found earlier (and belonging to this same characteristic number and lying in the plane

of the vectors a, Aa, ° °

° , Am

^a)

,

or we shall find a characteristic plane X?. containing as a part (proper or improper) of itself the plane Ot_ found earlier.

If the aggregate of the new characteristic planes that can be

constructed as indicated by means of the polynomial 0 *(x) and of

the vectors A^* (i - 0, 1, 0 ° 0 , rtp fills out the aggregate of

characteristic planes constructed earlier to an n-dimensional

-Illvector space,, the solution of the problem has then been completed.

If, however, the n-dimensional space is not exhausted with all the

characteristic planes that have been constructed, the aggregate of

all the characteristic planes constructed will nonetheless be of

* greater dimension than the dimension of the plane Ot, since the

vector a' was chosen outside the plane Ot, (This dimension may

nevertheless be less than the sum of the dimensions of the planes

0( and Ot! ; this circumstance may be awkwardly reflected in the

number of computations necessary to arrive at a complete solution

of the problem,) Continuing, therefore, the construction by means

of a new initial vector a" that does not lie in the region Ot+ ol',

we shall arrive either at an exhaustion of the space or at a further increase of the dimension of the region made up of the constructed characteristic planes. Thus a finite number of steps will

lead us to the complete exhaustion of the space by the characteristic planes.

The algorithm proposed above also solves the problem of the

reduction of the matrix corresponding to the operator A to Jordan

canonical forms one need only write the matrix corresponding to

the operator A in the coordinatal system determined by the aggregate of the structural vectors of all the characteristic planes,

suitably renumbering them,

§6. It was stated above (§£) that in case the degree of the

characteristic polynomial 0(?v) is less than n, it may happen that

the subsequent stages of the computations utilize quite incompletely

-15-

the computational work carried out on the preceding stages . We

will now give a new scheme that fully utilizes at each new step of

the computations the results obtained in the preceding stages.

Assuming that m < n and selecting an arbitrary vector a' that

does not lie in the plane let us construct a sequence of vectors A

1

a' such that the vectors

(6) a, Aa, A

2 a 5 •••, ATM

1

a s a’, Aa\ •••, A

m 1

a'

are linearly independent and such that the following equality holds

(Am

a’ +0(|Am 1

a* + ••• + ot

1 [l

, -l

Aaf + <X^a')

(6*

)

+ V1

A

mTM 1a + ^2

Am" 2 a + ** + = 0

The plane defined by the vectors (6) we shall denote by Gl + Ot'

.

Let us introduce into the discussion the polynomials

0*(x) = X

m ' +a|xm“ 1

+ ••• + 0^ j fM -t3^

1 - + * Pm

and rewrite equation (6’) in the form

(6”) 0(A)a» + f(A)a = 0

Let be a root of the polynomial 0' (x) of multiplicity k* and at

the same time a root of the polynomial 0(x) of multiplicity k. We

shall now show a method of constructing the system of vectors

a

l» a

2

s

’ *k

a-Q, cr13

•••,

and the system of numbers
.

'
-16-

satisfying the equations

(7) (A - X

1 )a^ = a^_ 1

+ o-i

_ 1

a^ ,

- i = 1, 2 S•

•

• , k ' ; a^ = 0 ,

where is the last structural vector of the characteristic plane;

it lies in the plane Ot (defined in §2) and belongs to the characteristic number A. If k = 0, i.e„ s if is not a root of the polynomial 0(A)

,

then = 0.

With the aforementioned objective in view # let us rewrite equation (6”) in the form

(8) (A -A ) (D0 ? (A)a' + D)^(A)a) + ^(A-^a = 0

where the operator D is defined by formula (3).

Taking into account that s in accordance with ( U) 3 \ -j - a = D

k0(A)a ^

(A-A1

) k

we obtain

ak

= (A - A1

)D

k+10(A)a + Dk

0(A 1

)a

and accordingly

(9) a 1_ ( A - X ) ^A)

D

k

0(A n ) k 1

D

k

0(\, )

(since D

K

0 (a^) / 0). Substituting the expression thus obtained

for a in equation (8) we obtain:

(A - A

1 )

(

/

D0'(A)a' + vf(k)a - f^)

D

r‘0(A 1

) J D^0(A

1

)

a = 0

k

LHere Dk

0(A

1

) E (D

k

0) (A^ E (D

k0(A))

x=>

-17-

Let us introduce into the discussion the operator P, defined by

the equation

pmW = u(a) - co(x, ) BI-&L . 1

D

k

0(Xl )

introducing also the designations:

(10) a^ D0»(A)a* + DP^(A)a

and

' ^

=

’

we arrive at the result:

(A - A)^ = 0^ ,

i.e., at the first of the equations of system (7).

Furthermore, rewriting equation (10) in the form:

= (A - A

1

)(D

2

0‘(A)a» + D

2

Pj^(A)a) + DPjKA^a

and substituting for a in the second summand of the right member

of (10) its expression (9), we obtain the second equation of system (7):

(A - X-Ja'z = a^ + , where

a'

2

= D

20 * (A)a' + (DP)

2

)^(A)a ,

dp)^(a 1

) ^

D

k

0(A x

)

Continuing in analogous fashion, we will also obtain the subsequent equations of system (7), but for the vectors a^ and the scalars o\ we have the following expressions:
-
- 18-

a'±

= D

10'(A)a I + (DPf^a (i = 1, 2 ,

• •

• , k ’

)

( 10 ’)

- cr. =

i

(DP)

i

1f(\1

)

If the vector = 0 (i„e.,

0(A)) all the numbers cr^, «

vectors

(i = 0, 1, ••*, k’-l) .

if A-^ is not a root of the polynomial

° are equal to zero, and the

i V

are (in accordance with (7)) structural vectors of the characteristic plane 0?^ having no part in common with the characteristic

plane 0(^ constructed earlier.

If, however,

x * 0

and

<r0

«

* * * = cr^_ 1

= 0; (r^ f 0 , 0 = 0 < k’

then we construct the system of vectors defined by the recurrence relations:

(11) Vl = (A ' A

l

)bi

(i - k'-l, k'-2, •••) ;

•

Utilising (7 ) and ( $)

,

we obtain

b

i

= a

i

+ ffA + °id\-l + + crk'-l

ak-(k'-i+l)

and, in particular,

b

i

= a

i + °iak

+ °2Vi + •••

(here and henceforth it is assumed that a = 0 if s < 0). Theres fore

b

o

= (A - Vh = °o\ + °iVi + a2\-2 * •••
'

'
-19-

and accordingly

b

o

= (A - X1

)b1

= cr^

%

+

* .

If k - % - 0,

b

i

= * °'A-x+1

•

(A - A

1

)b

]_ = 0

and consequently the constructed (linearly independent) vectors

b^, b

2

, •••, b^, are structural vectors of the characteristic plane

Oi.

* which has no part in common with the plane Ot^ constructed earlier (since the vector b^ is not collinear with the vector a^).

If k - X > 0, however , then b

Q f 0 and, continuing the construction prescribed by the recurrence formula (11), we construct

the vectors

b

-l> b_2

;

• b

( k.^) +1 5

the (linearly independent) vectors

b

(k-^)+l ; b

(k-X)+2 5 5 b

o

; b

l

5 b

2

; » b

k

! are structural vectors of the characteristic plane C which, however, has a part (of k - X dimensions) in common with the plane O?^

constructed earlier

„

Let us now take into account the fact that

(A - X)a| = a[_

x

(i = 1, 2, •••, %)

(since cr^ = • • > = cr

, ^

= 0) and that the vectors

a

i

5 a

2

1 s

are consequently structural vectors of the characteristic plane

having no part in common with the characteristic plane C7t| ,

20-

just constructed.

Thus in case % < k one can also construct, by utilizing the

i i vectors A a and A^a', two characteristic planes belonging to the

one root A^ and together filling out a plane of dimension

(k - X) + k

! + X

= k + k', i.e„ s equal to the multiplicity with

which the root A^ enters the polynomial 0 (a)0"(a) o By carrying

through the indicated construction for each root of the polynomial

0’(x), we shall have decomposed the entire plane 0( + Ol ” into

characteristic planes, and with this we shall have solved the problem before us in the case when CX + Ot' is the whole n-dimensional space 0 The characteristic polynomial will in this case

equal the polynomial^ 0(x)0’(A).

The computation of the coefficients of the polynomial 0’ (A)

reduces, obviously, to the determination of the coefficients of the

in ^ resolution of the vector A a in terms of the linearly independent

vectors (6). One may easily satisfy oneself that in case m+ m’ = n,

the computation of the coefficients of the polynomial 0 ’(a) may be

carried out by means of the formulas

? / a .m-1 ,

. , .m'-i-l , .m'-i+l , A m' .sc-1

= (a, Aa,-^ A a, a', Aa',-»*, A a

s , A a',.-.,A a

, )6 i

(i = 1, 2, •••, m')

where

h

±

= (- 1

)

1

(a, Aa, A m-1 , A a,9 a’ 9, A

1”'-1

.') .

These may thus be considered to be a , generalization of the

formulas given in the footnote to page 236 for the case that was

omitted from consideration in the article by Acad„ A„ N. Krylov, [1].
I
- 21 -

§7° In conclusion we dwell on the case when the plane

0( + Ol* does not exhaust the entire space 0 Having selected the

arbitrary vector a" , not lying in the plane 0( + CX'

j we construct

the system of vectors

Aa». A a" A

m"-l

such that the vectors

(12) a, Aa5

•

• •

, A

m” 1 a a a\ Aa*.-»-.AJ 9 9*9 5 m’-l . |i H ii .m"-! „ a', a

M

, Aa" , « «

• ,A a"

are linearly independent, but the equation

(A

m

"a" +oc"A

m

"” 1a

n + ... + „ n Aa" +oi"a") + (/3>A

m, " 1

a' 1 m"-l m" > 1

+ +

/3

m'-l

Aa ' +

I3m

,al) + ( iClA,"' la +

tm-l

Aa *

!Tma) = 0

holds. The plane defined by the vectors (12 ) we shall denote by

Gl + 01* + 01" •

Let us introduce into the discussion the polynomials

0"(A) = A

m'' H-ap?"'1

+ ... + a«

m„_£ + ,

0>(A) +

•••

* |3V-1X + P'm<

X(A) = Y^

m 1

+ ”• * + Ym

(Subsequent reasoning will show that if the region (X + Ol* + 00’

is the entire n-dimensional space, the characteristic equation of

the affinor A has the following form:

0(7'O0 , (*)0"(*) = 0

The extension of this method of constructing the characteristic

equation to the case when the region Ot + Ot* + Ot" does not fill

out the entire space is thus made quite obvious.)
' .

.
- 22-

Let X be a root of multiplicity k" (/ 0) of the polynomial

0"(x) and simultaneously a root of multiplicity kg of the polynomial 0

? (A) and of multiplicity k_^ of the polynomial 0(A).

By means of the operators D and defined by formulas (3)

and (7), and also of operator F

? a defined by the formula

tUK)

P'U(A) = U(\) - W(A

1

) , k

2 1

let us construct the system of vectors a” s aJj’, ag, • • ° , determined

by the formula

(i = X, 2, • •• , k") ,

where the polynomials 0V, are defined by the following recurrence relation:

Let us construct also the two systems of numbers

= ^(Xl) ' 0

' (A,

)

k2 V 1

;

(i - 0, !,•••, k''-l)

It can be shown that the following system of equations holds:

(lh) (A - - a"„

x

+ (i-l.V.k-, a" = 0)
.

'

.

'

,

,
-23-

Now let us construct the system of vectors c^, defined by the

recurrence relation

( 15) (A - A.) Ci c i

_ 1 ; ck

„ - ak

„

. 1 Employing (lh.), (11) and (£), we obtain :

c. = a'.' + o\b_ + <r! ,b^ +

• * 0 + cr, _ a^

i l i k

i i“l k *-l k 1 k

, -(k"-i-l)

+ + ViVi + • • • + T

k', -lak-(k,, -i-l)

and in particular t

°1

= *1 +<r

l

b

k.

+<T

2

b

k.-i

+ ••• + Vk +T2Vl + "•

(here and henceforth it is assumed that \

= ak

= 0 if k = 0).

Therefore

(16) c = (c/b^ + cr'bj +•••) + (T a_ + T a_ + •••)

0 0

k* 1 1<-1 0 k

1 k-1

or

or

or

a) If

b~, = ak

, =0 and ak

= 0

b^ = 0 ; t; o =T

1

=

... = rtn = o , k"

*k

= 0 > °0 °1 ” °kn 0 »

__i t cr = cr. = o 1

= cr. „ =0 and X - T, k" o 1

= V = 0 -

"'’Here k* is equal either to k' or to k' + (k-^); in the latter

case b^ denotes the vector that we have previously denoted by b^_

k_^/

~2lr

then c = 0 and the vectors

o

C1 5 c

2 5 "’5 c^n ( c

j_ a

j_)

are structural vectors of the characteristic plane 01 ", which belongs to the characteristic number and has no common part with

the characteristic planes constructed earlier.

b) If, furthermore, b^ = 0 (or cr^ = • “->• = = 0), but

ak / 0 and r

Q

= ^

=0; t

g f 0 ; 0 » s < k" ,

we then obtain (in conformity with (l6))

c = t a. + r .-.a, +...

o s k-s s+1 k-s-1

If k - s = 0, then c q

= 0, and accordingly the vectors

C l

s c 2*

'*•. ck»

(cl

= *1 + rsVs+l^

are structural vectors of the characteristic plane ot" which has

no common part with the planes previously constructed.

If k - s > 0," however, then b^ / 0 and, continuing the construction prescribed by the recurrence formula (l£), we construct

the vectors

C-l*

C~2’ °°°’ c-(k-s)+l

= ^s3!

5

the (linearly independent) vectors

C-(k-s)+l 3 c-(k-s)+2*”°» C o

s cl*

Ck"

are structural vectors of the characteristic plane having

k" + (k - s) dimensions, which has, however, a common part (of

k-s dimensions) with the previously constructed plane

Let us now take into account the fact that in conformity with

(iU),

I
'
-25-

(A - A)a" =0 (i = 1, 2 S •••, s)

and accordingly the vectors

» ti n a

2 » a

s

n

are structural vectors of the characteristic plane which does

not have a common part with the characteristic planes constructed

earlier 0 Thus in the case under consideration it is likewise poscharacteristic planes belonging to the same characteristic number

and together filling out a plane of dimension [k" + (k’ - s)]

+ s + k* = k + k* + k

n

s i,e. s of the multiplicity with which the

root figures in the polynomial 0(A)0' (A)0U (A).

c) We shall not tarry over a consideration of the case when

\

- 0 or t

0

= T

1

- = r.k"-l

= 0

but

Let us pass on to the case when

\ + 0 ; T0

- ^

- • • • - t

s_1

- 0 ; T

g + 0 ; 0

- s < k» ,

o- 0 ; o-y,/ 0 ; 0 S l'< k" .

In accordance with (16) we obtains

If

k - 0 ' = 0 and k - s = 0

then c q

= 0 and accordingly the vectors

- 26-

cl>C

2

5 c3’

'

J ck»

" ak

n

are structural vectors of the characteristic plane.

Omitting consideration of the case when either k - X' - 0 or

k - s = 0, let us turn to the case when

k - X

x > 0 and k - s > 0

Here let

k - p = k - s

Continuing the construction prescribed by the recurrence formula ( 15 ), let us construct the linearly independent vectors

C

-l*

C-2 5 ’*'» C -(k-X') +l

= °^ ,a

l

5

the vectors

C-(k-X')+l s C

-(k-X') + 2’ V C l>

**’» C

k"

are structural vectors of the characteristic plane 01 ” (which has

k

n + (k - X* ) dimensions) which has s however s a common part of

k - X' dimensions with the characteristic plane constructed earlier s whose structural vectors are headed by the vector a^.

c^) If with this we have X

’ = s, then in accordance with

0-h),

(A - 7s) a” = a?_

x

(i = 1, 2, %') ,

and accordingly the vectors

^s a2»

* *

a^

are structural vectors of a characteristic plane that has no common part with the characteristic planes constructed previously.

Thus in the case in hand one can construct three characteristic
.
-27-

planes belonging to the same characteristic number and together

filling out the plane whose dimensions are equal to

k" + Ok' - X') + V + k = k" + k« + k = k" + k> + k

c^) If, however 9 ^* > s, then in accordance with (lb) the

equations

(A - A)aV = aV_

x (i = 1, 2, • • •

,

s) ,

(A - X)a'! = + Vlak

= s + U *’>

hold. In this case let us construct a system of vectors a^, de

fined by the recurrence formula

(17) (A - A)d

t

= d._

1 ; Aj,, - .

Then

d

i

= a

l

+ Vk + TwVi + • • •

and, in particular,

h ‘ b

+ Vk + r

2 ak-i

+

Therefore

and accordingly

d

o t a^s k-s

+ x a^

s+1 k-s+1

+

• • •

Since k-s>0, d / 0, and we construct, by means of the recurrence formula (17 ) , the linearly independent vectors

d . -(k-s)+l

= °X

,al

d . , -(k-s)+l

The vectors

- 28-

are structural vectors of the characteristic plane (having a com- mon part of k - s dimensions with the plane constructed previously

that is headed by the vector a^).

Let us now take into consideration the fact that

(A - A.) a'.' = a?

1 l-l (i = 1, 2, s)

Therefore the vectors

1

1

*1

n ti2

n

, a

* s

are structural vectors of the characteristic plane. Thus in the

case indicated one can construct three characteristic planes,

which together fill out a plane of dimension

[k» + (k ? - 0')] + [V - (k - s)] + s = k" + k* + k = k" + k

? + k ,

i.e. s of the multiplicity with which the root A^ figures in the

polynomial 0(A)0 5 (A)0u (7v)

,

Having carried through the indicated constructions for each

root of the polynomial 0

" (a), we shall have decomposed the whole

plane ot + ot' + ct" into characteristic planes and shall with this

have solved the problem in hand in the case where ol + OC* + Ct"

constitutes the whole n-dimensional space. The characteristic polynomial will in this case obviously be equal to the polynomial

0(A) 0'(7O0"(X).

We shall not dwell on a discussion of that case for which the

plane CX + Ot* + (X" is only part of the n-dimensional space; the

reasoning set forth above indicates the course that would have to

be followed for a complete separation of the n-dimensional space

into structural planes.
.

,

'

-
=29=

^8 e a) The case m < n9 discussed in £l, is^ theoretically speaking,

exceptional,. It can occur either with an exceptional structure of the

affinor A (where to some characteristic number of A there correspond different characteristic planes) , or with an exceptional choice of the

initial vector a (when it is taken from some characteristic plane of the

affinor A) 0 One must suppose this to be the explanation of the negligent

attitude toward consideration of this case that characterizes the

literature of the problem

„

It is therefore essential to show that "in practice", i 0 e„, in computations conducted to a limited degree of accuracy, this case will be

general when n is sufficiently large 0 In order to elucidate this, let us denote by A the

group of characteristic numbers of the operator A that are largest in

modulus 9 and assume that the remaining characteristic numbers

,i , L .0 9 00 °, A „ "have the order of smallness k with respect

n-jj+l* n_+2* 5 n.+n~

to the number A , i e e 0 , for the adopted degree of computational accuracy, the fractionl

^n^+i\k

1

J

) may be disregarded in comparison with unity.

Assuming for simplicity of exposition that the characteristic numbers A^ are simple and distinct, and denoting by p^ the characteristic

vectors corresponding to them, we obtain

ASa=

!i

aPA ^ *

if

a = J aPp .

(The coordinates ©c of the vector a are generally speaking numbers

of the same order.)

On the strength of the assumption that was made,
’
-30-

1 + r* 1

we arrive at the conclusion that the vector

b 5 A^a -a* x .

i.e., "in practice" it lies in the plane formed by the "first" characteristic vectors p-^, p •••

, pn , and that the vectors

2 n —1 ^

Ab, A b, ••• , A ^ b lie in this same plane, and consequently the

vectors

b, Ab, A A

are "in practice" connected by a relation of linear dependences

\

n_-l

+ oc tA b + ° ° ° + ** Ab + ©d b = 0 . ± n—l n

Thus in the case when

k + n^ < n

(and this is just what will be true, generally speaking, when n is sufficiently large), the vectors

k-1 k k+n^

a, Aa, •«. , A a, A

K

a, •••

, A a

are linearly dependent and accordingly the method indicated in §1

will lead to the determination only of the "first" characteristic numbers and the characteristic vectors corresponding to them.

It is easily realized that in case n^ » 1, we arrive at the wellknown "method of iteration" for the determination of the largest characteristic number and the characteristic vector corresponding to it.

^Editor1 s note: The author uses the word for "oldest"-
1

'

.

'

.

.

. ••
-31-

It is essential to note that the recommended practice for this

method,'*' under which one verifies at each succeeding stage only the

* collinearity of the two successive vectors A

1a and A^" artificially reduces the general method proposed by us to the case = 1.

A more expeditious method in practice is thus the following

computational scheme, which derives from the reasoning set forth

above, and offers the possibility of discovering the whole plane

of n^ dimensions formed by the first characteristic vectors. Having

constructed the critical vector A

1 a, let us determine the possibility of resolving it in terms of the vectors constructed earlier .

. i-1 .i-2 .2 .1

A a, A a, ••», A a, A a, a

Taking into consideration along with this the practical likelihood that the vector A

1a will turn out to be a linear combination

of just some of the vectors immediately preceding it in this sequence, we should employ with this aim in view the "second scheme

2

of linear analysis" «,

b) We shall now indicate a possible course of the determination of the rest of the characteristic vectors and characteristic

numbers.

We note to begin with that the course suggested in §3 will

not lead to the goal in the case in hand, since -- in conformity

with what has been stated in §3 — having again begun the process

^See [6]

.

2 c See below, 99.
'

.
-32-

of iterations , proceeding from a vector a' which does not lie in

the plane pn , p9 , p already^ constructed, we in practice ar1 C. rive again at the plane p^, p^, Prj^,

since the vector A a'

will "practically" lie in this very plane.

The process suggested in §6 will also not give the possibility of finding the new characteristic vectors. Indeed, with the

construction of the n^+k vectors

n-i -1 V-l

b, Ab, °°°

3 A

1 b, a', Aa ! ,

• ° ° , A a'

we will not yet have obtained a basis, since n^ + k < n; at the

same time the next vector constructed will "practically" lie in

the plane of the vectors already constructed, p^, p^.

The position would, however, have been altered had the vector

a’ been taken from the plane of the "last "^characteristic vectors

P , . p

•••, p , . In this case the scheme indicated above

mi-^+1’ *n-^+2» 5 ^n^+r^

would have led us ("theoretically") to the determination of a cer2

tain plane (the "second" ) s formed by the vectors

Pr^+1* Pr^+2’ Pr^+k' ^ k ' <

“l^

The vector co(A)a may be taken as such a vector a'. Indeed,

having taken into consideration that

w(A)p

i

= 0 (i = 1, 2, r^)

we obtain the result

w(A)a = otn

l

' W(A )p + • • • + ocn

(b(A )p . I l

^'Editor's note: The author uses the word for "youngest".

"Editor’s notes The author uses the word for "second oldest".
.
"33”

It should, however, be borne in mind that "practically" the

vector A a’ will also contain components with respect to the vectors p^, p^ } ••*, pn ; however, they will be small in comparison

with its components with respect to the vectors pn +q,

* ' ° ,P n +n •

One should therefore expect that despite the fact that the vector

k

A a* will have a component in the plane p^,

** e

, it will not

be so large that one can neglect, in comparison with it, the component of the vector A a* in the plane P^ +]_, Pn^+2’

8

8

° * Pn

»

Continuing the computation of the vectors

.k+1 . . k+2 , .k+3 . A a®, A a', A ...

we will of course obtain vectors in which the component in the

plane p., , p0f •••, p increases in comparison with the component

l ^ n

l

in the plane p +1 , that in some cases the vector

n“ nl , _ k+(n-n]_-k)

, Pn^+n^" (-lne ma7 anticipate, however.

A

will no longer lie in the plane p p „ and therefore the

vectors

9 i

n-i ”1 . ,

, A b

1

, a1, Aa

1

,

I

s * ^

n*

n-n-i -1

, A^a’ , A

1V ' "a * , » •

« , A

x

a' .k+1 ,

n-m

will form a basis of the space . .Resolving the vector A a' in

terms of the vectors of this basis, we arrive at the equation

0«(A)a ! + f(A)b = 0

by means of which we will find the characteristic vectors

p

••• p as has been shown in §6. * rn
.

.

'

.

• .

mw-ntt.:
S9o The method given above for the determination of characteristic

numbers and characteristic vectors leads to the need for a practical

solution of the folio-wing problem (the problem of "linear analysis").

In the sequence of vectors

&2 s a

3?

* * ° ?

each of which is given in some coordinate system ° ° °

» by its n1/ coordinates , a^ s ^ to find the vector of least index that is

linearly expressible in terms of the preceding vectors , and to compute

the coefficients of this resolution „

¥e shall indicate two schemes for solving this problem. The first

of them is convenient for the case when n (the number of dimensions of

the space) is small. The second -- somewhat inferior in point of computational convenience — substantially reduces the number of operations

1

in cases for which n is large.

First scheme

Given the vectors

^Editor s s note? Let M denote the matrix whose rows are the vectors a^, a^, °°° ° Then the author's first scheme is ordinary Gaussian

elimination on the rows of M to triangularize M, The second scheme is

a modified Gaussian elimination on the columns of A, In both schemes

the author deals carefully with zeros. He fails, however, to note the

practical efficiency achieved in the compact arrangements of elimination introduced by many computers and described, for example, in

P,S, Dwyer's Linear Computations (John Wiley, 19!? l) .
;
- 35”

3-

j^ , a2

s a

^

> (a

lc 5

which we shall call the vectors of the first series „ let us construct the vectors

^2, * a

2

9 a

3

3 2 2uv i. -oiJj.

l l A- P

of a second series by the formulas

1 1

m Vi • Vm,

here

Ik. Ik.

X = °C " : OL

m m+1 1

lk]_

where OL 1 is the first (i.e., with the least index) non-vanishing coordinate of thevector a^ c The vectors of the second series obviously

lie in an (n- 1) -dimensional coordinate plane defined by the coordinate vectors

t1$ %2

. s He,-!* A ^k-, +1 ; V1

, tn

If the first vector of the second series, a_^, is not equal to

zero,, then construct the vectors of a third series;

by the formulas

here

2k,

ap

3 a

2

9 a

^

3

3 2 a = a _ m m+1

2 2

Vm

.2 2k2 2k2 X = Ca. : oi

m m+1 1

whereof is the first non-vanishing coordinate of the vector a^.

If a^ / 0, then construct analogously the vectors aj

4

, a!>

4

s ••• of

a fourth series, etc., thus obtaining successively the elements of

a triangular vector table
• . .
=36-

111

^2 a

3

(i)

2 2

2

a^ a

s *1

1 1

a . a P-1 P

2 2 a 0

a. , P-2 P-1

3 3 a -> a o p-3 P“2

s s a a n p-s p-s+1

and also the triangular table of numbers

1 A 1 A 1 A 1

A

1

X

2

X

3

(I')

1 2

A

3

A

P-1

2

‘P-2

A

P"3

p-s

defined by the recurrence formulas

i+1

m

1 L i am+l

~

i

ik. iki A = oC ? :0( 1 1

m m+1 1

ik^

J

la.-; 1 where is the first non-vanishing coordinate of the vector a^

,

S "^"1 ' If the first vector of the (s + l)-th series a^ turns out

to be equal to zero, then, as one may easily verify.

s+1

*- J- ym C = £ a

x

+ \ a~ +

V S + X ac

where the coefficients ^ of the resolution are determined from the

triangular system of linear equations

- 37 “

?

P * 5P+M * ^+ — + ' s-p *£/x s-p+l

(p - 1, 2, •••, s) 5 xj - 1 ,

which is written in extenso thus:

.s-1 1 -s. 1

(id

+ ?

3

\g * VVj * '" +?° ^s-2 + ^As-X

=A

, v 3.2 h 2 .s-1 2 v

s..2 .2 *^1*^2*"^ As-3 t

As-2- A

s-l

*

3 M + -+r\u ^.3

- a

3

_s-l yS S-1 _

+ t Ai - Ag

= a;

s-2

s-1

It is useful to carry through the indicated computations in

such a sequence that the triangular table (I) of the vectors a^

develops in sequential column construction; speaking more exactly,

2

after constructing the vector a^ (which completes the second col2 3 umn) the vectors a^ s a£ are constructed in succession (completing

2

o

) the third column), and then the vectors a^, a^, a^L , etc.

If not one vector equal to zero appears in the first s columns,

this will imply that the vectors a^, a^, a •••, a

g are linearly

independent.

If, furthermore, the vector a

g_ k+2> in the (s+l)-th column,

turns out to be zero (and the vectors standing above it are different from zero), this will then imply that

a

s+l

' *

+ •" +

* a

k

(since in this case all vectors of the (s+l)-th column standing
.

•

‘
3 «-

beneath the vector a „ will equal zero, and conseauentlv so will S”K+d 9 S+l

a

1

- 0).

o i The coefficients X of the resolution are in tlr s case solutions of a for^hortened system of equations that is obtained from

the system (II) of equations, if we put in it

.k+1 _ -vk+2

Ns-k s-k-1

=°

Observation, The suggested scheme obviously offers the possibility of investigating and solving the system o** n equations in p

unknowns

X

1^ + x2

°£> + vp k k

+ bux q = a ,, p p+1 fk - 1, 2, n)

since it is equivalent to one vector equation

^a. + £

2a0 +

••• + Spa = a _ • a. - apt

i 2

s p p+1 ’ i r )i

If p

= n3 and if it is known beforehand that the vectors

a^, a

2»

° °

* t an

are linearly independent, it is then convenient

(from a computational point of view) to conduct the construction

of the triangular vector table so that the rows develop successively in it (i.e„ s first compute the vectors of the second series,

then of the third, and so forth).

It is readily calculated that for the construction of tables

(I) and (I’), one must carry out

|(n-l)p(p-l)

additions

subtractions

and irp(p-l)

multiplications

divisi ons

"For computing the coefficients of the t riangular system of

equations (IT) one must still carry out
,

iS. hi 'V
- 39'

additions

is(s-i)

subtractions

multiplications

and \ s (s-l)

divisi ons

Thus for the solution of the system oP n independent linear equations in n unknowns by the scheme suggested here, one must carry

through (n = p

- s) in all

1

* y(n-l)n2

additions

subtractions

and yfn-lWn+l)

multiplicati ons

divisions

The execution of the operations according to the indicated

scheme is much facilitated if specially constructed cut-out templates be utilized.

Second scheme.

Given the vectors a^,

Illa?J a^, 000 of the "first series n

, let

2 2 2 us construct the vectors su^, a^, a^, ••• o^ a second series by the

formulas

_ 01_L X JL a — a _ — a A 2 m m+1 m m ’

here

1

-L x A s & % a m m+1 m

The vectors of the second series obviously lie in the plane defined

by the vectors , *’°

s Xn

° Construct, further, the vectors of

^C. Runge's scheme (Praxis der Gleichungen") requires the same

number of operations; it consists of the successive elimination of

the unknown ^ from all the equations commencing with the second,

2 then from all equations commencing with the third, etc. We note,

however, that Runge's scheme does not lead to results in the case

where there are linearly dependent or incompatible equations in the

system.
4

.

'
- JjOa third, series:

here

= 1, 2, 3, • •

•

)

by the formulas:

3 2 a = a n m m+1

2 2 a X

m m

~ 2 22 ^22 A = cl . : d.

m m+1 m

These vectors obviously lie in the plane spanned by the

vectors X^, Xj , ***, Xn

» We construct the vectors a^ of a fourth

series, those of a fifth series, and so on, obtaining the elements

of a triangular vector table

1111

^

a

2 a

3 %

'*

(III)

2 2 2

a^ Bp a^

3 3 a

l

a

2

and also the triangular table of numbers

. 1 .1 .1 .1 \ a

2

a

3 a

)( ...

(Ill*)

2 2 2

A^ A

2

X

3

Tv 3 A

3 h 2

defined by the recurrence formulas

k+1 k k k

3. ** 3 ““ 3 A

m m+1 m m

. k . kk ^ kk

A = Oi _ : <X m m+1 m

(here obviously a^ = a^X^)

The indicated construction may conveniently be carried through

-Lain such an order that the triangular table of vectors (Til) develops by a sequential column construction (lust as was suggested

for the first scheme).

If a vector equal to zero does not appear in the ^irst s columns, this will imply that the vectors a^, a^, •••', a

g (of the

first series) are linearly independent

„

Furthermore if the vector ak+?" . of the (s + l)-th column turns s-k+1

out to be equal to zero (but the vectors standing above it are different from zero)

,

this will imply that

i_s , >_s-l , , vs-k+l

a ,. = £ a + k a .+<>+ t a s+1 s s-1 Q s-k+1

(if, in particular, only a

a+^ = 0, then ag+^

= £

sa

g + ^ag_^

+

• • • + ^a^)

.

For the determination of the coefficients of the resolution

k+1 it must be borne in mind that the equation for a . _ has for its

s-k+1

consequence, in view of the law of construction of the vector table

(III), the sequence of equations

k _k ts-K+i . ps-k+1 ps-k+1 _ k

as-k+2

as-k+l ’ ^s-k+1 *

k-1 _ k-1

k

p

T

s-k+2 ^ k-1 k

p

1 s-k+l

a s-k+3

as-k+2 as-k+l

m , m m m ps-m+1 , m ts-m

a ~ — a +a b

s-m+2 s-m+1 s-m

s.

m

m

+ a“ i ±1 £

s-k+1

s-k+1

in which the coefficients ^ are to be determined by means of the

following recurrence formulas:

t t m = k-1, k-2 ••• 2 1

m. m+1. n m+1. * * 5 * ^ = 5

1-1

- l UTM

i = s-k+1 . s-k+2 *

. s-m+1
,

.

.
in which we have put

m+1s-k m+1

^ s-m+k _ _ -j_

Computationally, the determination of the coefficients

1 . (= £ ) from this system is less convenient than the solution of

the triangular system of equation (TI) (which appears in the first

scheme) | however the use of specially constructed templates will

reduce this discrepancy to a minimum.

The superiority of the second scheme will manifest itself,

however, in cases where in resolving the vector as+-j_ in terms of

the vectors a-p •••, a

g several of the first vectors a^ , a 2»*’*» a

k

do not appear. This circumstance, which will obtain, as a rule,

with the determination of the characteristic numbers and vectors of

a matrix of high order (for the case of a large n$ see §8), will be

revealed automatically, in a sense, during the utilization of the

second scheme (by the vanishing of the vectors a^^+^) — more exactly speaking, where one does not need to compute the coefficients

of the vectors a^, a^, ° •

°

,

a^ in the resolution.

The second scheme also offers the possibility of beginning the

construction of the triangular vector table (ITT) — in cases when

it is possible to anticipate the absence, in the resolution of a

g+^,

of components of the vectors a^, « • «

,

a^. — not with the vector a^

but with the vector a^: if the process of the computation suggests

the wisdom of using the vectors a^_^, \-2

’ ’*°s as we"^> a

n^evelopment leftwards” of table (TTI) is possible only with the use of

the* second scheme.
m

'

'

‘

'

'
BIBLIOGRAPHY

(All in Russian)

A. No Krylov, "The numerical solution of an equation with

which the frequency of the vibrations of material systems is

determined in technological problems", Akad . Nauk . SSSR , Izvestiia , Physico-mathematical series (1931), pp. U91“539.

A. M. Danilevsky, "The numerical solution of the characteristic equation", Matem . Sbornik , vol. 2 (UU), (1937), pp. 169-171.

A. M. Lopshits, "The characteristic equation of lowest degree for an affinor, and its application to the integration

of differential equations". Same Trudy f vol. 2-3 (1935), p. 11.

P. A. Shirokov, Tensor analysis . Part 1. The algebra of tensors , GTTI (193 b).

No No Luzin, "Concerning the method of A. N„ Krylov for composing the characteristic equation", Akad „ Nauk . SSSR , Izvestiia ,

Physico-mathematical series (1931), PP* 903 “958.

K. A. Semendiaev, "The determination of the latent roots and

the invariant manifolds of a matrix by means of iterations "

,

Priklad . matem . i mekh, vol. 3 (I9h3), pp. 193“221. [Available in English: National Bureau of Standards Report No. 1^02,

1952.]

"Cited on page 1 above.
.

.
-I4r

11

THE APPLICATION OF POLYNOMIALS OF BEST APPROXIMATION TO THE

IMPROVEMENT OF THE CONVERGENCE OF ITERATIVE PROCESSES

by

M. K„ Gavurin

The purpose of this note is to propose some methods that will

permit the acceleration of iterative processes in solving systems

of linear algebraic equations and determining the proper numbers

and vectors. We have s it should be said a limited ourselves to the

algebraic case only for simplicity of exposition; it is perfectly

evident that the methods proposed are applicable to analogous problems in the case of linear operators in an arbitrary Hilbert space.

1„ Finding the proper numbers and vectors .

Let us consider a matrix of the n-th order s

„ A = (a. and

10 *

assume that all its elementary divisors are linear and its proper

numbers real.

Numbering the proper numbers of the matrix A in order of diminishing absolute value g 2 ••• 4 |x • Ki * l2

i n'

let us in addition assume (which is no longer very essential) that

hjJ > l*. 2

l > l*

3

l •

The ordinary iterative methods for finding the dominant proper

“Hjspekhi Matematicheskhikh Nauk , vol. 5, n°» 3 (1950) ,pp. 156-160

number consist of two stages:

1) The construction of a -finite sequence f

Qj f^,

of numbers of the form

( 1 ) n

f. = y cx.X. k 1 i i=l

f f

p® p+1

where are certain constants „ The sequence of traces of the matrices A can serve as such a sequence, or -- for an arbitrary vector Y

q

, Y^ = AY^_^ = A^Y

q

(k = 1, 2, p+1) -- the sequence of

the i-th components of the vectors Y^ (i arbitrary), or lastly, in

the case of a symmetric A, the sequence f^

k

= (Y^, Y^),

f

2k+l

* ^ Y

k

5 Y

k+1^°

2) The approximate determination of based on the fact that

for ^ 0 and k sufficiently large the first term will predominate

in sum (l). Ordinarily one adopts

As is easily seen, the error of this equality is estimable by the

quantity

where

M

P

M^p (l + y)

1 - MyP

M

A. C 0 Aitken has proposed the more exact equality

Y

A. C. Aitken, "Studies in practical mathematics. The evolution of the latent roots and the latent vectors of a matrix," Proc .

Roy. Soc . of Edinburgh , vol. 37 (1937), pp. 269_ 30h.
'
the error of which is of the order

y

2P ,

Knowing A-j and taking into consideration that in the difference

f^

+^

“ A^f^ the termct^A^CA^ - A^) predominates, for example,

may be found from the relation

Vi - A A

2 ~ f

k

" A

l

f

k-1

Here, in practice, one should not take k too large lest the inexactitude in the determination of A^ distort the result.

We have set ourselves the task of finding a linear combination

e

P £ c

k

f

k ai 1 °kxi

= .1 ai

p

P

(V * ^ k=o i=l k=o i=l ^

such that the predominance of the first term in the right member will

be as great as possible. We shall consider that A^ is known to us,

and that nothing more of the distribution of • • • A is known.

3 n We therefore arrive at the problem of minimizing the ratio

( 2 ) FIaTT

• p 1

Max

-|\

2

|S\S|x

2

l r

p

Ml

It is easily seen that this ratio will attain its least value if

F

P

O)

P

Z

k=o

Ak

9

where d^. are the coefficients of the Chebyshev polynomial

In this case the quantity (2) equals

-U7-

P | It ( i /i , p

p V v

A If' _ Ar J

<

2f

T, + Fk - 1 1 + /TA7

If.J therefore, we choose P (A) in the manner indicated, and ’ p

w 5 put

n

9 = Vc.fi, = Vcx.A.P (A.) , p+1 k k+1 . l-l i l p l

’ r k=o -,=1 ^ i=l

w

+

, the approximate equality A-^ ^ — will hold, with an error estimable by the quantity

2M

r

N = P

+ A -

1

2 (1 + P

2M

1 + /1

-

N

For p sufficiently large, ^ 2 and the ratio

i + I:

A— is significantly closer to than the ration 211 —

£— . If

]f > 0. 5h37 *

•

• , then f

< ^ , and the method proposed by us

i + A - f

thus gives, generally speaking, better results than the method of

Aitken.

The application of the method indicated requires an approximate determination of A^, then of A^, making it possible after this

to refine the value of A^.

The proper vector corresponding to the first proper number

may be refined by the same method. As the approximation to it

one usually adopts the vector Y (considering the vectors

P
.
-U8-

Y I-., *

' ' , I to have been found), A better approximation would

be the vector F^(A)Y^ - Zp-0

' cp"^p° The approximation will in this case

have the order

2. The solution of a system of linear algebraic equations .

Holding to the assumption of the linearity of the elementary

divisors and the reality of the proper numbers of the matrix A,

let us consider the system of equations

(3) X - AX = Y , where Y is the given and X the sought vector. The method of iteration will be applicable to this equation if |X^| < 1 (i = 1,2,-.. ,n).

The essence of this method consists in the replacement of the exact

solution

00 00 x - (I - A)” I - f,A

kY = f, I

k=o k=o

by a segment of the series standing on the right. Thus one adopts

X IX = x

(p)

k=o

Let us set ourselves the task of finding such a linear combination of the vectors Y , Y..

* *

*

. Y : Z = Y? c. Y. as will best

o' 1* * p p Mc=o k k

approximate the vector X.

Introducing the linearly independent proper vectors of the matrix A: X^, • •

• 5 X^ corresponding to the proper numbers x

i

j ‘**

,7V

let us resolve the vector Y in terms of these vectors:

n Y Z

i=l

a.X.

i i

Then

-ii9-

n k„ , £ _ 1 IT = Va.x X. , X = Y oc. k 1 1 i ’ .K i i“l

“ ' i=l * 1 " A

i

1

Therefore

n Qy. n P . n

x - z = f x. - y ya c .A

k

x. = foe

p 1 - A. i ^ i k i l .“i i=l i i=l k=o i=l'

- W x

i

where

P

£

k=o

S

p

(X) = Z_OkX

k

If we know nothing more about the distribution of the proper numbers than the modulus of the dominant one, A^, it will be best to

choose as S (A.) the polynomial of best approximation to the funcP

tion in the interval [-|A.J a |\-J ] .

It was P. L. Chebyshev who found the polynomial of best ap1 1 proximation for the functions — (a>l) in the interval [-1, 1]

.

S. ” X

It permits us to write the expression for S^(A) 0 Let

P

+1

V?) • r[W£) - 2“T

P

(E) +a2Vi(5)]

- FS1 £ yC

. JC

k=o

where a = —-r . Oi = a - J&

Ai

1 , T

p

(£) = cos P( arc cos ^) is the p-th

Chebyshev polynomial,

Then

s (a)

P

P d

, ^ ] k+1 k=o \\ |

k xk

Here for A6[-|X^| , |A^| ]

Io Akhiezer, Lectures on the theory of approximation .

Gostekhizdat (19U7), p. 69.
7

.
-£0

-

< 2ao<P

+1

(l-.cx 2

) 2

2(1 - x

2 )d + A - x

2

) p

~ 1

i£

where we have put X = |X, | = — <, -L 3. Therefore

||X - Zj 2 N . X

2(1 - X

2

)

p-1

P

where by N is denoted the sum |ot

| , while for the difference

/ \ X - X^ p one obtains the estimate

|| x - x^|| = n *

p+1

We remark that the method indicated may also be applied in

case the Seidel form of the method of iterations is applied to the

solution of system (3)0 Indeed,, the Seidel method of iterations

is equivalent to the ordinary method of iterations applied to

another system

AY * A-j^AY _ vJL-^ 0

Lastly we point out that the method here proposed may be applied even when the ordinary method of iterations diverges. It is

sufficient to know one or two intervals containing all the proper

numbers of the matrix A and not containing the point 1 , and to be

able to construct the polynomials of best approximation for the

1

1 - A

function in these intervals.

-SlIII

SOME ESTIMATES FOR THE METHOD OF STEEPEST DESCENT

by

Mo SH. Birman'*'

The present note is devoted to the improvement of certain estimates obtained by L. Vo Kantorovich [2] for, the generalized method of steepest descent proposed by him.

Let A be a symmetric, bounded, positive definite operator in

real Hilbert space; let ex be its spectral function; and let the

numbers M and m be its upper and lower bounds.

Let us consider the equation

(1) Ax - 0

= 0

The problem of solving this equation is equivalent to the problem

of finding the minimum of the functional

(2) H(x) = (Ax, x) - 2(xs 0)

The generalized method of steepest descent consists in the construction of a sequence [xn } in which the element x

q

is arbitrary,

and the subsequent elements are defined by the formula

P-1

( 3 )

Here z = Ax , n n-1

x = x + y’oL^A^z

n n' 1 iAt*

/ \ 0, and the numbers oo ' are determined from the

^Uspekhi Matematicheskikh Nauk , vol. 5, no. 3 (1950), pp. 152-155*

^See L. V„ Kantorovich [1], [2].

-52-

condition for a minimum of the quantity H(x ). This condition

f n) leads to a system of equations linear in theCXl

K

Xn) Xn) _ (A z z ) + (A z Az )oC '+-->+ (A z . A

pz )ocv

' 7 = 0

n> n

v n

J n

7 o n

J n

7 p-1

(k - 0, 1, .... p-1) .

Let us denote the solution of equation (1) by x* and put

* V = x - X . <n n

L. V. Kantorovich has shown that the sequence |xn j is minimizing

for the functional (2) and converges strongly to the solution of

equation (l); moreover

(U) 7n

) = H(x

n

) - H(x*) = [H(x

q

) - H(x*)]

2np

m

and accordingly

(5) ll?n» o>

-

It was L„ V. Kantorovich's surmise [2] that for p > 1 these estimates could be improved.

Indeed, as it has turned out, estimates (Li) and (5) can be replaced by the following:

(Ua)

and

(5a)

H(x

n

) - H(x*) - L^n[H(x

o

) - H(x*)]

n

\\\\\ “ * t H(x

0

) ~ H(x*)] 2

. Vm

Here L is a quantity expressible simply in terms of the deviation

P

from zero of the p-th Chebyshev polynomial, viz.:

2

M + m

M- m mm\2

m

p r

M + m

M- m

M_+m\2

M- m

- 1
.

'

.

m
-63-

In particular,,

T M-in T L

i

" m+S > L

:

(M-rn)

I L^ ~ (M-m)‘

I , etc

(M+m) +ljmM ' (M+m) [ (M+m)^+ 12mM]

The idea of the proof consists in constructing a majorant sequence of

definite form as close as possible to the sequence ^ x

n |

Let us replace equation (l) by the equivalent equation

(6)

P-1 v x 38 x + ^ LyA

K

[Ax - 0)

k-o

We shall try to choose the numbers 6^ so that the norm of the operator

B

P

-

1 -

» J

1

w

k

^ k=o

2 will be less than unity for any symmetric operator A with bounds M and m.

Let A be a spectral point of the operator A3 and

p

a spectral

point of the operator . Then

(7)

P“1

p

s

p( A)^i+A ^

^ k®o

"1 consider it fitting to note that in the proof I have utilized

the idea of the application of polynomials of best approximation in

the operator variable^ which idea has been applied by M eK, Gavurin in

hastening the convergence of iterative processes (see the note by

M, K« Gavurin appearing in the present issue [the preceding translation]) . 2

I. P. Natanson [3] has proposed such a transformation for the case

p

= 1 5 with a view to making the method of successive approximations

applicable

e
'
and

( 8 ) <

= max

m=A=M

!/*l

We shall choose the numbers by, so that the function (7) will be a

polynomial in X of degree p deviating least from zero in the interval [m, M] on condition that ju(0) = 1. The ordinary Chebyshev

polynomial T (A) for the interval [m, M] , normalized by the condition Tp(0) = 1, is such a polynomial . The maximum of its modulus

in [m, M] is IL . Obviously 1 > > ° * °

, and therefore from

(8) it follows that

|bt = L < 1

P

and for equation (6) the usual successive approximations, computed

by the formula

(9)

converge.

lr X = X _ + y t. A

k

(AX _ - 0) n n-1 k n-1 r k=o

Now put

It follows from (9) that

Hence

0 = X - x

n n

) = B 0 n p n-1

(A0 0 ) = (AB 9 _ , B 0 _ ) = (AB 0 _ , 0 . ) = n 5 n' v p n-1 5 p n-1' v p n-1 5 n-1'

(10) = f Au (x)d(e 0 -,,0 ) = max u

2 (a) f Ad(e^0 _ 0 _) ' Jm r x n-1 5 n-1' ^ r 'Jm

v A n-1 5 n-1'

A0[m,MJ

= l

2

(a© . , e _ ) . p n-1 5 n-1'

Inequality (10) will remain time if the quantities ^ and 7n_-^ be

substituted for the quantities 0^ and ©n , since the quantities

(n)

o^. ' are determined at each step from the condition for a minimum
*

' mm '

.
of the expression^

From the inequality

( AV7n> = H(x

n

) ' H(x*)

^ A,

?n> ’In^ " L

p^ A

Vn-l- 7n-P

there follows directly the inequality

(Ua)

Estimate ( Ua) is exact; to wit: for each p one can find a positive

H(x

n

) - H(x* ) S Lp

n[H(x

o

) - H(x*)]

definite symmetric operator A with bounds M and m and an initial

element x such that for each n we will have

o

( 11 ) 2nr (A V ??n) = H(x

n

} ” H(x } = L

p

L H(x

o

) “ H(x )] *

For example, with p=l equation (11) will be satisfied for an operator with two proper numbers = m and = M, if we put

x

0

= x

* + Yoyo

+ -

Here yQ

and y^ are proper elements of the operator concerned, and

the numbers ^

and ^are connected by the relation

.2 ->2 ,2 2 h ' \

= to • Ao

•

Proceeding from (Ua), ||xn

- x*|| may be easily estimated, to wit

2n

<V V = m

(AV V = "S"

(Al

/o- V

whence (Pa) also follows, as well as the inequality

l*n- x*» Vi - Lp-

‘The functionals H(x) and H(x)-K(x*) attain a minimum simultaneously.
'

.

.

.
-£6

-

The method of steepest descent is also extended by L„ V. Kantorovich

to a series of problems in which A is an unbounded operator. It can

be shown that in this case as well estimates analogous to (l|a) and

(£a) hold.

CITED LITERATURE

(all in Russian)

[1] L. V. Kantorovich, "The method of steepest descent," Akad. Nauk

SSSR, Doklady, vol. £6 (19h7), p. 233.

[2] L. V. Kantorovich, "Functional analysis and applied mathematics," Uspekhi mat , nauk , vol. 3, no. 6 (I9b8), p. 89. [An

English translation is in preparation ;at the National Bureau of

Standards, Los Angeles.]

[33 I. p. Natanson, Leningad , Leningradskii pedagogicheskii institut imenj A. I. Gertsena , Uchenye zapiski , vol. 6k (19l|8).

t
. . , ' '
-51-

IV

A PROCESS OE SUCCESSIVE APPROXIMATIONS FOR FINDING

CHARACTERISTIC VALUES AND CHARACTERISTIC VECTORS

by

N. Azbelev and R. Vinograd^

(Submitted by Academician I. G. Petrovsky, June 27, 1951)

Let there be given a linear operator A in n-dimensional space

(real or complex). The operator is not required to be symmetric.

The process of successive approximations described below

leads to any characteristic vector of the operator A, provided

a suitable zero-th approximation be chosen. The character of the

convergence is specified by Theorem 2.

The process is defined as follows:

An arbitrary vector x

q f 0 is adopted as the zero-th approxi-

(Ax , x ) mation. We then put = and construct the operator

x.

B - A - A E and the vector y - B B x , afterwards taking as the

o o o o o o’

next approximation x_

| = x

q

- ^0J0 , \

a numerical coeffi-

(yo’ x

o

) IVoll

2

cient equalling —-—

—

^—• = —— . We thereby consider to be

l|y. lly. O" "''O 1 '

the zero-th approximation to the characteristic value. Carrying

the same operations through on x^ we obtain A^ and x^. In general

supposing and x^ to have been already determined, we put

l Akademiia Nauk SSSR , Doklady . vol. 83 (1952), pp. 173- 17U.
,

m
A

(Axk , Ki2

s and then = A = A.^ES after which we determine

B

*

( 7k" V k^H'

yk

^

and \

= T"^ = T“«2"

and lastly A+1 ’ VVkl|yk !1 l!yk

l!

The process of the approximations is definite.

Theorem 1 gives a rough estimate of the convergence.

Theorem 1. Depending on the choice of x one of two cases

obtains: either x^ 0 S or all the limiting vectors for the sequence {

x

k } belong to the same characteristic subspace and have the

identical norm d > 0.

This result is refined by Theorems 2 and 3*

Theorem 2. In the J ordan normal form of the matrix (A) of the

operator A let there correspond to the characteristic value X’ only

£

diagonal box „ i„e „

9 the invariant sub space L

1 belonging to consists of characteristic vectors only. The process then converges

with the rapidity of a geometrical progression to a non- zero vector

x® of L® (i°£« 9 j|x^_ = x® || = where q < 1) if for x^ an arbitrary

vector be chosen that forms with L® an angle less than a certain cx^.

Observation : Examples show that if the condition that the box

be diagonal be violated, convergence with a rapidity of only l/k is

observed.

Theorem 3 * In conditions of Theorem 2 s as regards L ® , the

" region of attraction" G(L’) of the subspace L\ i, e. 9 the set of

zero-th approximations such as will lead to non- zero vectors from

L * is an open set

.

Observation 1: Theorem 2 established only that G(L ! ) contains
;

.

.

'

.

,
- 59“

a certain sufficiently narrow "cone i! around L',

Observation 2? In case operator A is symmetric,, the number

q figuring in the estimate of the convergence (Theorem 2) is simply expressible in terms of the characteristic values of the operator A, Let the latter be arrayed in ascending order, A^< A^<

<A

r

(r = n) 0 If we are located in the "region of attraction" of

the subspace L belonging to X ,

•

q

= M - m_E B

M + m

P P

$

2 2 where M is the larger of the two numbers (A, - X ) and (X - A ) p

v 1

p' v r p' ’ 2 2 and m is the lesser of the two numbers (X - X ) and (A A ) p p-1 P P+1 P

(in case p

- 1 or p ^ ^= r we adopt A , = A or A

^ p-1 p

ly).

= A^_ respectiveobservation 3: Let the Jordan normal form of the matrix A be

diagonal. The sum of the "regions of attraction" of all the characteristic subspaces is, by Theorem 3, an open set, and consequently

the complementary set F — which is then, on the strength of Theorem

1, a "region of attraction" of zero — is closed.

The validity of the following hypothesis appears to be very

probable: "The 'region of attraction' of zero, at least in case A

is reducible to diagonal form, is a nowhere dense set."

Were it proved, this proposition would imply that the case of

the convergence of the process to zero is practically impossible.

The hypothesis is easily proved for all operators in two-dimensional

space (even without assuming A to be reducible to diagonal form) and

for some operators in three-dimensional space. We have not succeeded