Polynomial Root-finding and Polynomiography

✍ Scribed by Bahman Kalantari

• Publisher: World Scientific
• Year: 2009
• Tongue: English
• Leaves: 492
• Edition: Illustrated
• Category: Library

✦ Synopsis

This book offers fascinating and modern perspectives into the theory and practice of the historical subject of polynomial root-finding, rejuvenating the field via polynomiography, a creative and novel computer visualization that renders spectacular images of a polynomial equation. Polynomiography will not only pave the way for new applications of polynomials in science and mathematics, but also in art and education. The book presents a thorough development of the basic family, arguably the most fundamental family of iteration functions, deriving many surprising and novel theoretical and practical applications such as: algorithms for approximation of roots of polynomials and analytic functions, polynomiography, bounds on zeros of polynomials, formulas for the approximation of Pi, and characterizations or visualizations associated with a homogeneous linear recurrence relation. These discoveries and a set of beautiful images that provide new visions, even of the well-known polynomials and recurrences, are the makeup of a very desirable book. This book is a must for mathematicians, scientists, advanced undergraduates and graduates, but is also for anyone with an appreciation for the connections between a fantastically creative art form and its ancient mathematical foundations.

✦ Table of Contents

Contents
Preface
Introduction
1. Approximation of Square-Roots and Their Visualizations
1.1 Introduction
1.2 A Simple Algebraic Method for Approximation of Square- Roots
1.3 High-Order Algebraic Methods for Approximation of Square-Roots
1.4 Convergence Analysis
1.5 Approximation of Square-Roots from Complex Inputs
1.6 The Basic Sequence and Fixed Point Iterations
1.7 Determinantal Representation of High-Order Iteration Functions and Basic Sequence
1.8 Visualizations in Approximation of Square-Roots
1.9 High-Order Methods for Approximation of Cube-Roots
1.10 Complexity of Sequential Versus Parallel Algorithms
1.11 Extensions
2. The Fundamental Theorem of Algebra and a Special Case of Taylor's Theorem
2.1 Introduction
2.2 Algebraic Derivation of Newton's Method
2.3 A Recurrence Relation and the Basic Family
2.4 Conclusions
3. Introduction to the Basic Family and Polynomiography
3.1 Introduction
3.2 The Basic Family and its Properties
3.3 Polynomiography and Its Applications
4. Equivalent Formulations of the Basic Family
4.1 Determinantal Formulation of the Basic Family
4.2 Properties of a Determinant
4.3 Gerlach's Method
4.4 Equivalence to the Basic Family
4.5 KÄonig's Family and Equivalence to the Basic Family
4.6 Notes and Remarks
5. Basic Family as Dynamical System
5.1 Introduction
5.2 Iterations of a Rational Function
5.3 Newton's Method and Connections to Mandelbrot Set
5.4 Analysis of Infinity as Fixed Point
5.5 MÄobius Transformations and Conjugacy
5.6 Periodic Points and Cycles of a Rational Function
5.7 Critical Points and Their Cardinality
5.8 Cardinality of Periodic Points of Different Types
5.9 Local Behavior of Iterations Near Fixed Points
5.10 Local Behavior of Iterations Near General Points: Equicon- tinuity and Normality
5.11 Fatou and Julia Sets and Their Basic Properties
5.12 Montel Theorem and Characterization of Fatou and Julia Sets
5.13 Fatou and Julia Sets as: The Good, The Bad, and The Undesirable
5.14 Fatou Components and Their Dynamical Properties
5.15 Critical Points and Connection with Periodic Fatou Components
5.16 Fatou-Julia and Topological Fatou-Julia Graphs: Analo- gies for Visualization and Conceptualization of Dynamics
5.17 Lakes and Waterfalls: Analogy for Dynamics of Rational Maps
5.18 General Convergence: Algorithmic Limitation of Iterations
5.19 A Summary for the Behavior of Iteration Functions
5.20 Undecidability Issues in Rational Functions
6. Fixed Points of the Basic Family
6.1 Introduction .
6.2 Properties of the Fixed Points of the Basic Family
6.3 Proof of Main Theorem
7. Algebraic Derivation of the Basic Family and Characterizations
7.1 Introduction
7.2 Algebraic Proof of Existence of the Basic Family
7.3 Derivation of Closed Form of the Basic Family
7.4 Two Formulas for Generation of Iteration Functions
7.5 Deriving the Euler-SchrÄoder Family
7.6 Extension to Non-Polynomial Root Finding
7.7 Conclusions
8. The Truncated Basic Family and the Case of Halley Family
8.1 The Halley Family
8.2 The Order and Asymptotic Error of Halley Family
8.3 The Truncated Basic Family
8.4 Applications
8.5 Polynomiography with the Truncated Basic Family
8.6 Conclusions
9. Characterizations of Solutions of Homogeneous Linear Recurrence Relations
9.1 Introduction
9.2 Homogeneous Linear Recurrence Relations
9.3 Explicit Representation of the Fundamental Solution
9.4 Explicit Representation Via Characteristic Polynomial
9.5 Approximation of Polynomial Roots Using HLRR
9.6 Basic Sequence and Connection to the Basic Family
9.7 The Basic Sequence and the Bernoulli Method
9.8 Determinantal Representation of Fundamental Solution
9.9 Application to Fibonacci Sequence and Generalizations
9.10 Experimental Results Via Polynomiography
9.11 A Representation Theorems for Arbitrary Solutions
9.12 Applications to Fibonacci and Lucas Numbers
9.13 Concluding Remarks
10. Generalization of Taylor's Theorem and Newton's Method
10.1 Introduction
10.2 Taylor's Theorem with Conuent Divided Differences
10.2.1 Basic Applications .
10.3 The Determinantal Taylor Theorem
10.3.1 Determinantal Interpolation Formulas
10.4 Proof of Determinantal Taylor Theorem and Equivalent Form
10.5 Applications of Determinantal Formulas
10.5.1 Infinite Spectrum of Rational Approximation Formulas
10.5.2 Infinite Spectrum of Rational Inverse Approximation Formulas
10.5.3 Infinite Families of Single and Multipoint Iteration Functions
10.5.4 Determinantal Approximation of Roots of Polynomials
10.5.5 A Rational Expansion Formula and Connection to Pad e Approximant
10.5.6 Algebraic Approximation Formulas
10.6 Concluding Remarks
11. The Multipoint Basic Family and its Order of Convergence
11.1 Introduction
11.2 The Multipoint Basic Family
11.3 Description of the Order of Convergence
11.4 Proof of the Order of Convergence
12. A Computational Study of the Multipoint Basic Family
12.1 Introduction
12.2 The Iteration Functions
12.3 The Iteration Complexity
12.4 The Experiment
12.5 Conclusions
13. A General Determinantal Lower Bound
13.1 Introduction
13.2 An Application in Approximation of Polynomial Root
13.3 Conclusions
14. Formulas for Approximation of Pi Based on Root-Finding Algorithms
14.1 Introduction
14.2 Main Results
14.3 Auxiliary Results
14.4 Proof of Main Theorems
14.5 Applications in Approximation of
14.6 Special Formulas for Approximation of
14.7 Approximation of Via the Basic Family
14.8 A Formula for Approximation of e
14.9 Concluding Remarks
15. Bounds on Roots of Polynomials and Analytic Functions
15.1 Introduction
15.2 Estimate to Zeros of Analytic Functions
15.3 The Basic Family for General Analytic Functions
15.4 Application of Basic Family in Separation Theorems
15.5 Estimate to Nearest Zero and Bounds on Zeros
15.6 Applications, Asymptotic Analysis, Computational E - ciency and Comparisons
15.7 Concluding Remarks
16. A Geometric Optimization and its Algebraic O springs
16.1 Introduction
16.2 Elementary Proof of the Gauss-Lucas Theorem and the Maximum Modulus Principle
16.3 The Gauss Lucas Iteration Function and Extensions of the Maximum Modulus Principle
16.4 Conclusions
17. Polynomiography: Algorithms for Visualization of Polynomial Equations
17.1 A Basic Coloring Algorithm
17.2 Basic Family and Variants: The Basis of Polynomiography
17.3 Many Polynomiographs of Cubic Roots of Unity
18. Visualization of Homogeneous Linear Recurrence Relations
18.1 Introduction
18.2 The Generalized Fibonacci, the Hyper Fibonacci, and their Polynomiography
18.3 The Induced Basic Family and Induced Basic Sequence
18.4 The Fibonacci and Lucas Families of Iteration Functions
18.5 Visualization of HLRR with Arbitrary Initial Conditions
19. Applications of Polynomiography in Art, Education, Science and Mathematics
19.1 Polynomiography in Art
19.1.1 Polynomiography as a Tool of Art and Design
19.1.2 Polynomiography Based on Voronoi Coloring
19.1.3 Polynomiography Based on Levels of Convergence
19.1.4 Symmetric Designs from Polynomiography
19.1.5 Polynomiography of Numbers
19.1.6 Some Extensions of Polynomiography
19.1.7 Glossary of Terms
19.2 Polynomiography in Education
19.2.1 Polynomiography for Encouraging Creativity in Education
19.2.2 Teacher Survey
19.2.3 Student Survey
19.2.4 Developing Seminars and Courses Based on Polynomiography
19.3 Polynomiography in Mathematics and Science
19.3.1 Polynomiography for Measuring the Average Performance of Root- nding Algorithms
19.4 Conclusions
20. Approximation of Square-Roots Revisited
20.1 Regular Continued Fractions and the Basic Family
20.2 Regular Continued Fraction Convergents Versus Basic Sequence Convergents
20.3 Applications of Continued Fractions and Basic Sequence in Factorization
20.4 Basic Sequence for Approximation of Higher Roots of a Number and its Factorization
21. Further Applications and Extensions of the Basic Family and Polynomiography
21.0.1 Extensions to Analytic Functions
21.0.2 Extensions to Other Dimensions or Domains
21.0.3 Polynomiography for Designing Shapes
21.1 Toward a Digital Media Based on Polynomiography
Bibliography
Index