The Computation of Fixed Points and Applications
Fixed-point algorithms have diverse applications in economics, optimization, game theory and the numerical solution of boundary-value problems. Since Scarf's pioneering work [56,57] on obtaining approximate fixed points of continuous mappings, a great dea
- PDF / 7,424,297 Bytes
- 138 Pages / 397 x 612 pts Page_size
- 89 Downloads / 239 Views
Managing Editors: M. Beckmann and H. P. KUnzi
Mathematical Economics
124 Michael J. Todd
The Computation of Fixed Points and Applications
Springer-Verlag Berlin Heidelberg GmbH
Editorial Board H. Albach . A. V. 8alakrishnan . M. 8eckmann (Managing Editor) P. Dhrymes . J. Green . W. Hildenbrand . W. Krelle H. P. Kunzi (Managing Editor) . K. Ritter . R.Sato • H. Schelbert P. Schonfeld Managing Editors Prof. Dr. M. 8eckmann 8rown University Providence, RI 02912/USA
Prof. Dr. H. P. KOnzi Universitat ZOrich 8090 ZOrich/Schweiz
Author Michael J. Todd School of Operations Research and Industrial Engineering Cornell University Ithaca, New York 14~53/USA
Llbrary or eoa,reu Cat.loela, la Publicatieu Data
Todd, Michae1 J 1947The ccmputation of fixe
O}
be continuous. and
-,
C.
~
= C..
f. (x) > x.
then
~
~
Ci ~ Sn, i E I.
J
= NO
=
cj
~
UjEJ Cj
f.
is continuous and
we have
x* E c~, x''; i'
0 Note:
sat-
c~,
i E No'
'
Since for x E
rt
i E NO'
s~,
x ~ C~,
and condition (ii) is verified.
If the K-K-M lemma holds, we can deduce the existence of f
i E NO'
=
Also, by definition, if
x E UjEJ
~ I,
1
T v x
Sn ~ UiEN C: c U. N C.. o ~ - ~E 0 ~
Hence
Ci ,
lies in none of the
Then
condition (i) is verified. Thus for
If
x E Sn
for
a contradiction.
let
i E NO
We now show that the
~
isfy the hypotheses of the K-K-M lemma.
For
x*
f. (x;,)
i E No' and so
~
Now
1
x*
Since
C ••
1 =
is a fixed point of
Scarf [58] has proved a lemma similar to 3.1 in which condition (ii) is
replaced by: (ii) ,
For all
S~ c C ••
i E No'
1
-
1
One can easily verify that this version also implies Brouwer's theorem for
Sn.
Freidenfelds [22] has shown that the two versions are equivalent. 3.3
Simplices and Triangulations.
3.1 by exhibiting, for any
s
>
0,
one another, with one point in each Sn
into many small simplices.
As we discussed in 2.6(c), we shall prove
an (n+l)-tuple of points of C •• ~
Sn
within
of
We produce these (n+l)-tuples by dividing
The concepts of simplex and triangulation will be
B
introduced informally now; we postpone rigorous definitions until Chapter III. A closed j-simplex is the convex hull of finely independent) in
j+l
points in general position (af-
the points are called the vertices of the simplex.
An
open j-simplex is the relative interior of a closed j-simplex.
Closed n-simplex
n
Note:
Sn
o
(point)
1
(line segment)
2
(triangle)
3
(tetrahedron)
is a closed n-simplex.
A face of a simplex Thus
s~
Open n-simplex
a is a simplex all of whose vertices are vertices of a.
is a closed face of
Sn
for each
i E NO'
Two simplices are incident if one is a face of the other.
Two j-simplices are
adjacent if they share a (j-l)-simplex as a face. A triangulation
G of
Sn
is a finite collection of open n-simplices such
that the open n-simplices, together with all their open faces, form a partition of Sn,
i.e.,
Sn
is their disjoint union.
As we shall see in Chapter III, this rather
non-intuitive definition, when couched in
Data Loading...
