Polynomial Root-Finding and Polynomiography Book

Preface vii

Introduction 1

1 Approximation of Square-Roots and Their Visualizations 13

1.1 Introduction 13

1.2 A Simple Algebraic Method for Approximation of Square-Roots 17

1.3 High-Order Algebraic Methods for Approximation of Square-Roots 18

1.4 Convergence Analysis 19

1.5 Approximation of Square-Roots from Complex Inputs 21

1.6 The Basic Sequence and Fixed Point Iterations 24

1.7 Determinantal Representation of High-Order Iteration Functions and Basic Sequence 25

1.8 Visualizations in Approximation of Square-Roots 27

1.9 High-Order Methods for Approximation of Cube-Roots 30

1.10 Complexity of Sequential Versus Parallel Algorithms 35

1.11 Extensions 38

2 The Fundamental Theorem of Algebra and a Special Case of Taylor's Theorem 39

2.1 Introduction 39

2.2 Algebraic Derivation of Newton's Method 40

2.3 A Recurrence Relation and the Basic Family 45

2.4 Conclusions 46

3 Introduction to the Basic Family and Polynomiography 49

3.1 Introduction 49

3.2 The Basic Family and its Properties 51

3.3 Polynomiography and Its Applications 60

4 Equivalent Formulations of the Basic Family 71

4.1 Determinantal Formulation of the Basic Family 71

4.2 Properties of a Determinant 72

4.3 Gerlach's Method 74

4.4 Equivalence to the Basic Family 75

4.5 Konig's Family and Equivalence to the Basic Family 78

4.6 Notes and Remarks 79

5 Basic Family as Dynamical System 81

5.1 Introduction 82

5.2 Iterations of a Rational Function 86

5.3 Newton's Method and Connections to Mandelbrot Set 92

5.4 Analysis of Infinity as Fixed Point 100

5.5 Mobius Transformations and Conjugacy 101

5.6 Periodic Points and Cycles of a Rational Function 104

5.7 CriticalPoints and Their Cardinality 107

5.8 Cardinality of Periodic Points of Different Types 111

5.9 Local Behavior of Iterations Near Fixed Points 113

5.10 Local Behavior of Iterations Near General Points: Equicontinuity and Normality 119

5.11 Fatou and Julia Sets and Their Basic Properties 123

5.12 Montel Theorem and Characterization of Fatou and Julia Sets 126

5.13 Fatou and Julia Sets as: The Good, The Bad, and The Undesirable 132

5.14 Fatou Components and Their Dynamical Properties 135

5.15 Critical Points and Connection with Periodic Fatou Components 139

5.16 Fatou-Julia and Topological Fatou-Julia Graphs: Analogies for Visualization and Conceptualization of Dynamics 145

5.17 Lakes and Waterfalls: Analogy for Dynamics of Rational Maps 150

5.18 General Convergence: Algorithmic Limitation of Iterations 152

5.19 A Summary for the Behavior of Iteration Functions 163

5.20 Undecidability Issues in Rational Functions 164

6 Fixed Points of the Basic Family 171

6.1 Introduction 171

6.2 Properties of the Fixed Points of the Basic Family 172

6.3 Proof of Main Theorem 173

7 Algebraic Derivation of the Basic Family and Characterizations 175

7.1 Introduction 175

7.2 Algebraic Proof of Existence of the Basic Family 179

7.3 Derivation of Closed Form of the Basic Family 183

7.4 Two Formulas for Generation of Iteration Functions 187

7.5 Deriving the Euler-Schroder Family 190

7.6 Extension to Non-Polynomial Root Finding 192

7.7 Conclusions 193

8 The Truncated Basic Family and the Case of Halley Family 195

8.1 The Halley Family 195

8.2 The Order and Asymptotic Error of Halley Family 198

8.3 The Truncated Basic Family 202

8.4 Applications 203

8.5 Polynomiography with the Truncated Basic Family 206

8.6 Conclusions 206

9 Characterizations of Solutions of Homogeneous Linear Recurrence Relations 207

9.1 Introduction 208

9.2 Homogeneous Linear Recurrence Relations 209

9.3 Explicit Representation of the Fundamental Solution 212

9.4 Explicit Representation Via Characteristic Polynomial 213

9.5 Approximation of Polynomial Roots Using HLRR 217

9.6 Basic Sequence and Connection to the Basic Family 220

9.7 The Basic Sequence and the Bernoulli Method 226

9.8 Determinantal Representation of Fundamental Solution 229

9.9 Application to Fibonacci Sequence and Generalizations 230

9.10 Experimental Results Via Polynomiography 233

9.11 A Representation Theorems for Arbitrary Solutions 233

9.12 Applications to Fibonacci and Lucas Numbers 238

9.13 Concluding Remarks 239

10 Generalization of Taylor's Theorem and Newton's Method 243

10.1 Introduction 243

10.2 Taylor's Theorem with Confluent Divided Differences 246

10.2.1 Basic Applications 249

10.3 The Determinantal Taylor Theorem 251

10.3.1 Determinantal Interpolation Formulas 254

10.4 Proof of Determinantal Taylor Theorem and Equivalent Form 258

10.5 Applications of Determinantal Formulas 269

10.5.1 Infinite Spectrum of Rational Approximation Formulas 270

10.5.2 Infinite Spectrum of Rational Inverse Approximation Formulas 273

10.5.3 Infinite Families of Single and Multipoint Iteration Functions 275

10.5.4 Determinantal Approximation of Roots of Polynomials 276

10.5.5 A Rational Expansion Formula and Connection to Pade Approximant 277

10.5.6 Algebraic Approximation Formulas 280

10.6 Concluding Remarks 281

11 The Multipoint Basic Family and its Order of Convergence 283

11.1 Introduction 283

11.2 The Multipoint Basic Family 284

11.3 Description of the Order of Convergence 286

11.4 Proof of the Order of Convergence 290

12 A Computational Study of the Multipoint Basic Family 295

12.1 Introduction 295

12.2 The Iteration Functions 296

12.3 The Iteration Complexity 297

12.4 The Experiment 299

12.5 Conclusions 304

13 A General Determinantal Lower Bound 305

13.1 Introduction 305

13.2 An Application in Approximation of Polynomial Root 313

13.3 Conclusions 315

14 Formulas for Approximation of Pi Based on Root-Finding Algorithms 317

14.1 Introduction 317

14.2 Main Results 319

14.3 Auxiliary Results 322

14.4 Proof of Main Theorems 324

14.5 Applications in Approximation of π 326

14.6 Special Formulas for Approximation of π 328

14.7 Approximation of π Via the Basic Family 332

14.8 A Formula for Approximation of e 334

14.9 Concluding Remarks 335

15 Bounds on Roots of Polynomials and Analytic Functions 337

15.1 Introduction 337

15.2 Estimate to Zeros of Analytic Functions 338

15.3 The Basic Family for General Analytic Functions 339

15.4 Application of Basic Family in Separation Theorems 342

15.5 Estimate to Nearest Zero and Bounds on Zeros 345

15.6 Applications, Asymptotic Analysis, Computational Efficiency and Comparisons 349

15.7 Concluding Remarks 350

16 A Geometric Optimization and its Algebraic Offsprings 353

16.1 Introduction 353

16.2 Elementary Proof of the Gauss-Lucas Theorem and the Maximum Modulus Principle 355

16.3 The Gauss Lucas Iteration Function and Extensions of the Maximum Modulus Principle 367

16.4 Conclusions 371

17 Polynomiography: Algorithms for Visualization of Polynomial Equations 373

17.1 A Basic Coloring Algorithm 374

17.2 Basic Family and Variants: The Basis of Polynomiography 375

17.3 Many Polynomiographs of Cubic Roots of Unity 376

18 Visualization of Homogeneous Linear Recurrence Relations 381

18.1 Introduction 381

18.2 The Generalized Fibonacci, the Hyper Fibonacci, and their Polynomiography 383

18.3 The Induced Basic Family and Induced Basic Sequence 384

18.4 The Fibonacci and Lucas Families of Iteration Functions 389

18.5 Visualization of HLRR with Arbitrary Initial Conditions 390

19 Applications of Polynomiography in Art, Education, Science and Mathematics 393

19.1 Polynomiography in Art 394

19.1.1 Polynomiography as a Tool of Art and Design 398

19.1.2 Polynomiography Based on Voronoi Coloring 401

19.1.3 Polynomiography Based on Levels of Convergence 407

19.1.4 Symmetric Designs from Polynomiography 412

19.1.5 Polynomiography of Numbers 413

19.1.6 Some Extensions of Polynomiography 414

19.1.7 Glossary of Terms 415

19.2 Polynomiography in Education 416

19.2.1 Polynomiography for Encouraging Creativity in Education 417

19.2.2 Teacher Survey 419

19.2.3 Student Survey 419

19.2.4 Developing Seminars and Courses Based on Polynomiography 421

19.3 Polynomiography in Mathematics and Science 423

19.3.1 Polynomiography for Measuring the Average Performance of Root-finding Algorithms 425

19.4 Conclusions 428

20 Approximation of Square-Roots Revisited 429

20.1 Regular Continued Fractions and the Basic Family 429

20.2 Regular Continued Fraction Convergents Versus Basic Sequence Convergents 432

20.3 Applications of Continued Fractions and Basic Sequence in Factorization 434

20.4 Basic Sequence for Approximation of Higher Roots of a Number and its Factorization 439

21 Further Applications and Extensions of the Basic Family and Polynomiography 443

21.0.1 Extensions to Analytic Functions 443

21.0.2 Extensions to Other Dimensions or Domains 446

21.0.3 Polynomiography for Designing Shapes 446

21.1 Toward a Digital Media Based on Polynomiography 447

Bibliography 449

Index 459