10
W. Gautschi
OstrowskiReich Theorem. If A is symmetric with positive diagonal ele-
ments, and 0 < < 2, then SOR converges if and only if A is positive
definite.
Reich proved the theorem for
= 1 in 1949. Ostrowski proved it for
general in (0, 2), even when
=
k
depends on k but remains in any
compact subinterval of (0, 2).
Excerpt 1.5. A little mathematical jewel (1979).
Theorem. Let p and q be polynomials of degrees m and n, respectively.
Define
M
f
= max
|z|=1
|f (z)|.
Then
M
p
M
q
M
pq
M
p
M
q
,
= sin
m
8m
sin
n
8n
.
The interest here lies in the lower bound, the upper one being trivial. It
is true that this lower bound may be quite small, especially if m and/or n
are large. But jewels need not be useful as long as they shine!
2.2. Volume 2
Key words: Algebra of finite fields (1913); theory of valuation on a field
(191317); necessary and sufficient conditions for the existence of a finite
basis for a system of polynomials in several variables (191820); various
questions of irreducibility (1922, 197577); theory of invariants of binary
forms (1924); arithmetic theory of fields (1934); structure of polynomial
rings (1936); convergence of block iterative methods (1961); Kronecker's
elimination theory for polynomial rings (1977).
The fact, proved by Ostrowski in 1917, that the fields of real and com-
plex numbers are the only fields, up to isomorphisms, which are complete
(Ostrowski used the older term "perfect" for "complete") with respect to
an Archimedean valuation is known today as "Ostrowski's Theorem" in
valuation theory (P. Roquette [31]).
Excerpt 2.1. Evaluation of polynomials (1954). If
p(x)
= a
0
x
n
+ a
1
x
n
-1
+ · · · + a
n
-1
x
+ a
n
,
then, by Horner's rule, p(x)
= p
n
, where
p
0
= a
0
, p
= xp
-1
+ a
,
= 1, 2, . . . , n.
Complexity: n additions, n multiplications.