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 I have been interested in two main aspects: - the algorithmic aspect: an iterative algorithm is a mathematical entity which behaves in a dynamic fashion. Even if it is started far from a solution, it will often tend to get closer and closer. - the mathematical aspect: this consists of a coherent and rigorous analy­ sis of convergence, with the aid of mathematical tools (these tools are mainly the use of norms for convergence proofs, the use of matrix algebra and so on). One may for example refer to the algorithmic and mathematical aspects of Newton's method in JRn as well as to the QR algorithm for eigenvalues of matrices. These two algorithms seem to me to be the most fascinating algorithms in numerical analysis, since both show a remarkable practical efficiency even though there exist relatively few global convergence results for them.

1. Discrete Iterations and Automata Networks: Basic Concepts.- 1. Discrete Iterations and Their Graphs.- 2. Examples.- 3. Connectivity Graphs and Incidence Matrices.- 4. Interpretations in Terms of Automata Networks.- 5. Serial Operation and the Gauss-Seidel Operator.- 6. Serial-Parallel Modes of Operation and the Associated Operators.- 2. A Metric Tool.- 1. The Boolean Vector Distance d.- 2. Some Basic Inequalities.- 3. First Applications.- 4. Serial-Parallel Operators. An Outline.- 5. Other Possible Metric Tools.- 3. The Boolean Perron-Frobenius and Stein-Rosenberg Theorems.- 1. Eigenelements of a Boolean Matrix.- 2. The Boolean Perron-Frobenius Theorem.- 3. The Boolean Stein-Rosenberg Theorems.- 4. Conclusion.- 4. Boolean Contraction and Applications.- 1. Boolean Contraction.- 2. A Fixed Point Theorem.- 3. Examples.- 4. Serial Mode: Gauss-Seidel Iteration for a Contracting Operator.- 5. Examples.- 6. Comparison of Operating Modes for a Contracting Operator.- 7. Examples.- 8. Rounding-Off: Successive Gauss- Seidelisations.- 9. Conclusions.- 5.Comparison of Operating Modes.- 1. Comparison of Serial and Parallel Operating Modes.- 2. Examples.- 3. Extension to the Comparison of Two Serial-Parallel Modes of Operation.- 4. Examples.- 5. Conclusions.- 6. The Discrete Derivative and Local Convergence.- 1. The Discrete Derivative.- 2. The Discrete Derivative and the Vector Distance.- 3. Application: Characterization of the Local Convergence in the Immediate Neighbourhood of a Fixed Point.- 4. Interpretation in Terms of Automata Networks.- 5. Application: Local Convergence in a Massive Neighbourhood of a Fixed Point.- 6. Gauss-Seidel.- 7. The Derivative of a Function Composition.- 8. The Study of Cycles: Attractive Cycles.- 9. Conclusions.- 7. A Discrete Newton Method.- 1. Context.- 2. Two Simple Examples.- 3. Interpretation in Terms of Automata.- 4. The Study of Convergence: The Case of the Simplified Newton Method.- 5. The Study of Convergence, The General Case.- 6. The Efficiency of an Iterative Method on a Finite Set.- 7. Numerical Experiments.- 8. Conclusions.- General Conclusion.- Appendix 2. The Number of Regular n x n Matrices with Elements in Z/p (p prime).- Appendix 4. Continuous Iterations-Discrete Iterations.- Inde.