Polynomial Root-finding and Polynomiography

Contents......Page 18
Preface......Page 8
Introduction......Page 26
1.1 Introduction......Page 38
1.2 A Simple Algebraic Method for Approximation of Square- Roots......Page 42
1.3 High-Order Algebraic Methods for Approximation of Square-Roots......Page 43
1.4 Convergence Analysis......Page 44
1.5 Approximation of Square-Roots from Complex Inputs......Page 46
1.6 The Basic Sequence and Fixed Point Iterations......Page 49
1.7 Determinantal Representation of High-Order Iteration Functions and Basic Sequence......Page 50
1.8 Visualizations in Approximation of Square-Roots......Page 52
1.9 High-Order Methods for Approximation of Cube-Roots......Page 55
1.10 Complexity of Sequential Versus Parallel Algorithms......Page 60
1.11 Extensions......Page 63
2.1 Introduction......Page 64
2.2 Algebraic Derivation of Newton\'s Method......Page 65
2.3 A Recurrence Relation and the Basic Family......Page 70
2.4 Conclusions......Page 71
3.1 Introduction......Page 74
3.2 The Basic Family and its Properties......Page 76
3.3 Polynomiography and Its Applications......Page 85
4.1 Determinantal Formulation of the Basic Family......Page 96
4.2 Properties of a Determinant......Page 97
4.3 Gerlach\'s Method......Page 99
4.4 Equivalence to the Basic Family......Page 100
4.5 KÄonig\'s Family and Equivalence to the Basic Family......Page 103
4.6 Notes and Remarks......Page 104
5. Basic Family as Dynamical System......Page 106
5.1 Introduction......Page 107
5.2 Iterations of a Rational Function......Page 111
5.3 Newton\'s Method and Connections to Mandelbrot Set......Page 117
5.4 Analysis of Infinity as Fixed Point......Page 125
5.5 MÄobius Transformations and Conjugacy......Page 126
5.6 Periodic Points and Cycles of a Rational Function......Page 129
5.7 Critical Points and Their Cardinality......Page 132
5.8 Cardinality of Periodic Points of Different Types......Page 136
5.9 Local Behavior of Iterations Near Fixed Points......Page 138
5.10 Local Behavior of Iterations Near General Points: Equicon- tinuity and Normality......Page 144
5.11 Fatou and Julia Sets and Their Basic Properties......Page 148
5.12 Montel Theorem and Characterization of Fatou and Julia Sets......Page 151
5.13 Fatou and Julia Sets as: The Good, The Bad, and The Undesirable......Page 157
5.14 Fatou Components and Their Dynamical Properties......Page 160
5.15 Critical Points and Connection with Periodic Fatou Components......Page 164
5.16 Fatou-Julia and Topological Fatou-Julia Graphs: Analo- gies for Visualization and Conceptualization of Dynamics......Page 170
5.17 Lakes and Waterfalls: Analogy for Dynamics of Rational Maps......Page 175
5.18 General Convergence: Algorithmic Limitation of Iterations......Page 177
5.19 A Summary for the Behavior of Iteration Functions......Page 188
5.20 Undecidability Issues in Rational Functions......Page 189
6.1 Introduction .......Page 196
6.2 Properties of the Fixed Points of the Basic Family......Page 197
6.3 Proof of Main Theorem......Page 198
7.1 Introduction......Page 200
7.2 Algebraic Proof of Existence of the Basic Family......Page 204
7.3 Derivation of Closed Form of the Basic Family......Page 208
7.4 Two Formulas for Generation of Iteration Functions......Page 212
7.5 Deriving the Euler-SchrÄoder Family......Page 215
7.6 Extension to Non-Polynomial Root Finding......Page 217
7.7 Conclusions......Page 218
8.1 The Halley Family......Page 220
8.2 The Order and Asymptotic Error of Halley Family......Page 223
8.3 The Truncated Basic Family......Page 227
8.4 Applications......Page 228
8.6 Conclusions......Page 231
9. Characterizations of Solutions of Homogeneous Linear Recurrence Relations......Page 232
9.1 Introduction......Page 233
9.2 Homogeneous Linear Recurrence Relations......Page 234
9.3 Explicit Representation of the Fundamental Solution......Page 237
9.4 Explicit Representation Via Characteristic Polynomial......Page 238
9.5 Approximation of Polynomial Roots Using HLRR......Page 242
9.6 Basic Sequence and Connection to the Basic Family......Page 245
9.7 The Basic Sequence and the Bernoulli Method......Page 251
9.8 Determinantal Representation of Fundamental Solution......Page 254
9.9 Application to Fibonacci Sequence and Generalizations......Page 255
9.11 A Representation Theorems for Arbitrary Solutions......Page 258
9.12 Applications to Fibonacci and Lucas Numbers......Page 263
9.13 Concluding Remarks......Page 264
10.1 Introduction......Page 268
10.2 Taylor\'s Theorem with Conuent Divided Differences......Page 271
10.2.1 Basic Applications .......Page 274
10.3 The Determinantal Taylor Theorem......Page 276
10.3.1 Determinantal Interpolation Formulas......Page 279
10.4 Proof of Determinantal Taylor Theorem and Equivalent Form......Page 283
10.5 Applications of Determinantal Formulas......Page 294
10.5.1 Infinite Spectrum of Rational Approximation Formulas......Page 295
10.5.2 Infinite Spectrum of Rational Inverse Approximation Formulas......Page 298
10.5.3 Infinite Families of Single and Multipoint Iteration Functions......Page 300
10.5.4 Determinantal Approximation of Roots of Polynomials......Page 301
10.5.5 A Rational Expansion Formula and Connection to Pad e Approximant......Page 302
10.5.6 Algebraic Approximation Formulas......Page 305
10.6 Concluding Remarks......Page 306
11.1 Introduction......Page 308
11.2 The Multipoint Basic Family......Page 309
11.3 Description of the Order of Convergence......Page 311
11.4 Proof of the Order of Convergence......Page 315
12.1 Introduction......Page 320
12.2 The Iteration Functions......Page 321
12.3 The Iteration Complexity......Page 322
12.4 The Experiment......Page 324
12.5 Conclusions......Page 329
13.1 Introduction......Page 330
13.2 An Application in Approximation of Polynomial Root......Page 338
13.3 Conclusions......Page 340
14.1 Introduction......Page 342
14.2 Main Results......Page 344
14.3 Auxiliary Results......Page 347
14.4 Proof of Main Theorems......Page 349
14.5 Applications in Approximation of......Page 351
14.6 Special Formulas for Approximation of......Page 353
14.7 Approximation of   Via the Basic Family......Page 357
14.8 A Formula for Approximation of e......Page 359
14.9 Concluding Remarks......Page 360
15.1 Introduction......Page 362
15.2 Estimate to Zeros of Analytic Functions......Page 363
15.3 The Basic Family for General Analytic Functions......Page 364
15.4 Application of Basic Family in Separation Theorems......Page 367
15.5 Estimate to Nearest Zero and Bounds on Zeros......Page 370
15.6 Applications, Asymptotic Analysis, Computational E - ciency and Comparisons......Page 374
15.7 Concluding Remarks......Page 375
16.1 Introduction......Page 378
16.2 Elementary Proof of the Gauss-Lucas Theorem and the Maximum Modulus Principle......Page 380
16.3 The Gauss Lucas Iteration Function and Extensions of the Maximum Modulus Principle......Page 392
16.4 Conclusions......Page 396
17. Polynomiography: Algorithms for Visualization of Polynomial Equations......Page 398
17.1 A Basic Coloring Algorithm......Page 399
17.2 Basic Family and Variants: The Basis of Polynomiography......Page 400
17.3 Many Polynomiographs of Cubic Roots of Unity......Page 401
18.1 Introduction......Page 406
18.2 The Generalized Fibonacci, the Hyper Fibonacci, and their Polynomiography......Page 408
18.3 The Induced Basic Family and Induced Basic Sequence......Page 409
18.4 The Fibonacci and Lucas Families of Iteration Functions......Page 414
18.5 Visualization of HLRR with Arbitrary Initial Conditions......Page 415
19. Applications of Polynomiography in Art, Education, Science and Mathematics......Page 418
19.1 Polynomiography in Art......Page 419
19.1.1 Polynomiography as a Tool of Art and Design......Page 423
19.1.2 Polynomiography Based on Voronoi Coloring......Page 426
19.1.3 Polynomiography Based on Levels of Convergence......Page 432
19.1.4 Symmetric Designs from Polynomiography......Page 437
19.1.5 Polynomiography of Numbers......Page 438
19.1.6 Some Extensions of Polynomiography......Page 439
19.1.7 Glossary of Terms......Page 440
19.2 Polynomiography in Education......Page 441
19.2.1 Polynomiography for Encouraging Creativity in Education......Page 442
19.2.3 Student Survey......Page 444
19.2.4 Developing Seminars and Courses Based on Polynomiography......Page 446
19.3 Polynomiography in Mathematics and Science......Page 448
19.3.1 Polynomiography for Measuring the Average Performance of Root- nding Algorithms......Page 450
19.4 Conclusions......Page 453
20.1 Regular Continued Fractions and the Basic Family......Page 454
20.2 Regular Continued Fraction Convergents Versus Basic Sequence Convergents......Page 457
20.3 Applications of Continued Fractions and Basic Sequence in Factorization......Page 459
20.4 Basic Sequence for Approximation of Higher Roots of a Number and its Factorization......Page 464
21.0.1 Extensions to Analytic Functions......Page 468
21.0.3 Polynomiography for Designing Shapes......Page 471
21.1 Toward a Digital Media Based on Polynomiography......Page 472
Bibliography......Page 474
Index......Page 484