Discrete Iterations A Metric Study
a c 9 h In presenting this monograph, I would like to indicate both its orientation as well as my personal reasons for being interested in discrete iterations (that is, iterations on a generally very large,jinite set). While working in numerical analysis
- PDF / 15,919,032 Bytes
- 202 Pages / 439 x 666 pts Page_size
- 55 Downloads / 222 Views
6
Editorial Board Editorial Board R.L. Graham, R.L. Graham, Murray Murray Hill Hill J. Stoer, J. Stoer, WOrzburg WOrzburg R. Varga, R. Varga, Cleveland Cleveland
Fran
L--> => G ~-monotone } Moreover if F(x) = ~ then G(x) = ~ F F
~-monotone
F
~-monotone
~-non-expansive
F and G ~-ordered
(Theorem 1)
} => => F an d G ..,Y;Y; -or d ere d
} => =>
(Theorem 2)
aggregation and implosion of the basin defined by ~ when going from F to G. (Theorem 4)
By assuming conditions on all the fixed points of F we clearly have the following theorem: Theorem 5. If F is ~-monotone and if F and G G are ~-ordered for all the fixed points ~ of F (and G) then the serial iteration is better than the parallel iteration. (Property (P) is assured.) Indeed, in passing from F to G one has the aggregation and implosion of each basin defined by a fixed point to the detriment of the basins without a fixed point. It should moreover be noted that if the iteration graph for F only has It basins with fixed points then under the assumptions for the above theorem, it follows that each basin keeps its own elements and clearly also gains no other elements when passing to the serial iteration defined by G (the basins may, however, implode). The following examples are given to illustrate the above points: F(x)=x F(x)=const.
't/XEX 't/XEX.
1. Comparison of Serial and Parallel Operating Modes
In these two cases F is ~-monotone and points ~ and furthermore G == F.
87
for all fixed
~-non-expansive
Remarks. (1) (1) We might consider the following more restrictive conditions: - monotonicity of F: d(x, z)::; d(y, z) ~ d(F(x), F(z))::; d(F(y), F(z))
which clearly implies that F is - non-expansion of F:
~-monotone
vx, YEX which clearly implies that F is - F and G G are ordered if
vx, YEX
at each fixed point
~
of F.
d(F(x), F(y)) ::;d(x, y)
~-non-expansive
at each fixed point
~
of F.
d(G(x), G(y)) ::;d(F(x), F(y))
which clearly implies that F and G are ~-ordered at each fixed point ~ of F (and G). Then from the preceding it is clear that if F is monotone, with F and G ordered, then the serial-iteration is better than the parallel iteration. It is moreover possible to establish results analogous to the preceding It theorems directly using the above notions. The proofs are quite similar. The notions that we finally retained (~-monotonicity, ~-non-expansion, ~-ordering) are less restrictive since they are more local. (2) Let ~ be a fixed point of F and x and y two elements of X. If If the inequality d(x, ~)::;d(y,~) holds, then we write x ex:: y. The relation ex:: is clearly reflexive and transitive on X: it is a preorder.
Then the notion of
~-monotonicity
for F may be written as
xex::y~F(x)ex::F(y).
This is the mono tonicity of F relative to the preorder ex::. The notion of of F may be written as
~-non-expansion
V xi" ~ V
The notion of
~-ordering
F(x)ex::x.
may be written as V Xi" ~ V
G(x)ex::F(x).
Clearly the relation [xex::y and yex::x] (which is written d(x, ~)=d(y, ~)) is an equivalence relation on X. Therefore ex:: in
Data Loading...
