Rigorous bounds for polynomial Julia sets

Previous Article
Towards tensor-based methods for the numerical approximation of the Perron--Frobenius and Koopman operator
JCD Home
This Issue
Next Article

June 2016, 3(2): 113-137. doi: 10.3934/jcd.2016006

Rigorous bounds for polynomial Julia sets

Luiz Henrique de Figueiredo ^1, , Diego Nehab ^1, , Jorge Stolfi ^2, and João Batista S. de Oliveira ^3,

1.	IMPA, Rio de Janeiro, Brazil, Brazil
2.	Instituto de Computacão, UNICAMP, Campinas, Brazil
3.	Faculdade de Informática, PUC-RS, Porto Alegre, Brazil

Received March 2016 Revised August 2016 Published November 2016

Abstract
Related Papers

We present an algorithm for computing images of polynomial Julia sets that are reliable in the sense that they carry mathematical guarantees against sampling artifacts and rounding errors in floating-point arithmetic. We combine cell mapping based on interval arithmetic with label propagation in graphs to avoid function iteration and rounding errors. As a result, our algorithm avoids point sampling and can reliably classify entire rectangles in the complex plane as being on either side of the Julia set. The union of the rectangles that cannot be so classified is guaranteed to contain the Julia set. Our algorithm computes a refinable quadtree decomposition of the complex plane adapted to the Julia set which can be used for rendering and for approximating geometric properties such as the area of the filled Julia set and the fractal dimension of the Julia set.

Keywords: cell mapping, computer-assisted proofs., robust rendering, Julia sets, fractals, adaptive refinement.

Mathematics Subject Classification: 37-04, 37F50, 37F10, 37M99, 65P9.

Citation: Luiz Henrique de Figueiredo, Diego Nehab, Jorge Stolfi, João Batista S. de Oliveira. Rigorous bounds for polynomial Julia sets. Journal of Computational Dynamics, 2016, 3 (2) : 113-137. doi: 10.3934/jcd.2016006

References:

[1]	Z. Arai, On hyperbolic plateaus of the Hénon map, Experimental Mathematics, 16 (2007), 181-188. doi: 10.1080/10586458.2007.10128992.
[2]	P. Blanchard, Complex analytic dynamics on the Riemann sphere, Bulletin of the American Mathematical Society, 11 (1984), 85-141. doi: 10.1090/S0273-0979-1984-15240-6.
[3]	B. Branner, The Mandelbrot set, in Amer. Math. Soc., 39 (1989), 75-105. doi: 10.1090/psapm/039/1010237.
[4]	M. Braverman, Hyperbolic Julia sets are poly-time computable, Electronic Notes in Theoretical Computer Science, 120 (2005), 17-30. doi: 10.1016/j.entcs.2004.06.031.
[5]	M. Braverman and M. Yampolsky, Computability of Julia Sets, Springer-Verlag, 2009.
[6]	R. Carniel, A quasi-cell mapping approach to the global dynamical analysis of Newton's root-finding algorithm, Applied Numerical Mathematics, 15 (1994), 133-152. doi: 10.1016/0168-9274(94)00016-6.
[7]	L. H. de Figueiredo and J. Stolfi, Affine arithmetic: concepts and applications, Numerical Algorithms, 37 (2004), 147-158. doi: 10.1023/B:NUMA.0000049462.70970.b6.
[8]	M. Dellnitz and A. Hohmann, A subdivision algorithm for the computation of unstable manifolds and global attractors, Numerische Mathematik, 75 (1997), 293-317. doi: 10.1007/s002110050240.
[9]	M. Dellnitz and O. Junge, Set oriented numerical methods for dynamical systems, in Handbook of dynamical systems, North-Holland, 2 (2002), 221-264. doi: 10.1016/S1874-575X(02)80026-1.
[10]	R. L. Devaney and L. Keen (eds.), Chaos and Fractals: The Mathematics behind the Computer Graphics, Proceedings of Symposia in Applied Mathematics 39, AMS, 1989.
[11]	A. Douady, Does a Julia set depend continuously on the polynomial?, in Complex Dynamical Systems: The Mathematics Behind the Mandelbrot and Julia Sets (ed. R. L. Devaney), Proceedings of Symposia in Applied Mathematics, AMS, 49 (1994), 91-138. doi: 10.1090/psapm/049/1315535.
[12]	M. B. Durkin, The accuracy of computer algorithms in dynamical systems, International Journal of Bifurcation and Chaos in Applied Sciences and Engineering, 1 (1991), 625-639. doi: 10.1142/S0218127491000452.
[13]	Z. Galias, Rigorous investigation of the Ikeda map by means of interval arithmetic, Nonlinearity, 15 (2002), 1759-1779. doi: 10.1088/0951-7715/15/6/304.
[14]	E. Grassmann and J. Rokne, The range of values of a circular complex polynomial over a circular complex interval, Computing, 23 (1979), 139-169. doi: 10.1007/BF02252094.
[15]	T. H. Gronwall, Some remarks on conformal representation,, Annals of Mathematics, 16 (): 72. doi: 10.2307/1968044.
[16]	S. L. Hruska, Constructing an expanding metric for dynamical systems in one complex variable, Nonlinearity, 18 (2005), 81-100. doi: 10.1088/0951-7715/18/1/005.
[17]	S. L. Hruska, Rigorous numerical studies of the dynamics of polynomial skew products of $C^2$, in Complex dynamics, vol. 396 of Contemp. Math., AMS, 2006, 85-100. doi: 10.1090/conm/396/07395.
[18]	C. S. Hsu, Cell-to-cell Mapping: A Method of Global Analysis for Nonlinear Systems, Springer-Verlag, 1987. doi: 10.1007/978-1-4757-3892-6.
[19]	C. S. Hsu, Global analysis by cell mapping, International Journal of Bifurcations and Chaos, 2 (1992), 727-771. doi: 10.1142/S0218127492000422.
[20]	O. Junge, Rigorous discretization of subdivision techniques, in International Conference on Differential Equations, Vol. 1, 2 (Berlin, 1999), World Sci. Publ., 2000, 916-918.
[21]	W. D. Kalies, K. Mischaikow and R. C. A. M. VanderVorst, An algorithmic approach to chain recurrence, Foundations of Computational Mathematics, 5 (2005), 409-449. doi: 10.1007/s10208-004-0163-9.
[22]	L. Keen, Julia sets, in Proc. Sympos. Appl. Math., 39 (1989), 57-74. doi: 10.1090/psapm/039/1010236.
[23]	V. Kreinovich, Interval software,, , ().
[24]	D. Michelucci and S. Foufou, Interval-based tracing of strange attractors, International Journal of Computational Geometry & Applications, 16 (2006), 27-39. doi: 10.1142/S0218195906001914.
[25]	J. Milnor, Remarks on iterated cubic maps, Experimental Mathematics, 1 (1992), 5-24.
[26]	J. Milnor, Dynamics in One Complex Variable, vol. 160 of Annals of Mathematics Studies, 3rd edition, Princeton University Press, 2006.
[27]	R. E. Moore, Interval Analysis, Prentice-Hall, 1966.
[28]	R. E. Moore, R. B. Kearfott and M. J. Cloud, Introduction to Interval Analysis, SIAM, 2009. doi: 10.1137/1.9780898717716.
[29]	R. P. Munafo, Roundoff error, http://mrob.com/pub/muency/roundofferror.html, 1996, Accessed: 2015-12-09.
[30]	D. Nehab and H. Hoppe, A fresh look at generalized sampling, Foundations and Trends in Computer Graphics and Vision, 8 (2014), 1-84. doi: 10.1561/0600000053.
[31]	G. Osipenko, Dynamical Systems, Graphs, and Algorithms, vol. 1889 of Lecture Notes in Mathematics, Springer-Verlag, 2007.
[32]	A. Paiva, L. H. de Figueiredo and J. Stolfi, Robust visualization of strange attractors using affine arithmetic, Computers & Graphics, 30 (2006), 1020-1026. doi: 10.1016/j.cag.2006.08.016.
[33]	H.-O. Peitgen and P. H. Richter, The Beauty of Fractals: Images of Complex Dynamical Systems, Springer-Verlag, 1986. doi: 10.1007/978-3-642-61717-1.
[34]	H.-O. Peitgen and D. Saupe (eds.), The Science of Fractal Images, Springer-Verlag, 1988. doi: 10.1007/978-1-4612-3784-6.
[35]	M. S. Petković and L. D. Petković, Complex Interval Arithmetic and Its Applications, Wiley-VCH Verlag, 1998.
[36]	R. Rettinger, A fast algorithm for {Julia} sets of hyperbolic rational functions, Electronic Notes in Theoretical Computer Science, 120 (2005), 145-157. doi: 10.1016/j.entcs.2004.06.041.
[37]	R. Rettinger and K. Weihrauch, The computational complexity of some Julia sets, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003), ACM, 2003, 177-185. doi: 10.1145/780542.780570.
[38]	J. Rokne, The range of values of a complex polynomial over a complex interval, Computing, 22 (1979), 153-169. doi: 10.1007/BF02253127.
[39]	D. Ruelle, Repellers for real analytic maps, Ergodic Theory and Dynamical Systems, 2 (1982), 99-107. doi: 10.1017/S0143385700009603.
[40]	S. M. Rump and M. Kashiwagi, Implementation and improvements of affine arithmetic, Nonlinear Theory and Its Applications, IEICE, 6 (2015), 341-359.
[41]	H. Samet, The quadtree and related hierarchical data structures, Computing Surveys, 16 (1984), 187-260. doi: 10.1145/356924.356930.
[42]	D. Saupe, Efficient computation of Julia sets and their fractal dimension, Physica D, 28 (1987), 358-370. doi: 10.1016/0167-2789(87)90024-8.
[43]	N. Steinmetz, Rational Iteration: Complex Analytic Dynamical Systems, Walter de Gruyter & Co., 1993. doi: 10.1515/9783110889314.
[44]	C. M. Stroh, Julia Sets of Complex Polynomials and Their Implementation on the Computer, Master's thesis, University of Linz, 1997.
[45]	R. Tarjan, Depth-first search and linear graph algorithms, SIAM Journal on Computing, 1 (1972), 146-160. doi: 10.1137/0201010.
[46]	W. Tucker, The Lorenz attractor exists, C. R. Acad. Sci. Paris Sér. I Math., 328 (1999), 1197-1202. doi: 10.1016/S0764-4442(99)80439-X.
[47]	J. Tupper, Reliable two-dimensional graphing methods for mathematical formulae with two free variables, in Proceedings of SIGGRAPH '01, ACM, 2001, 77-86. doi: 10.1145/383259.383267.

show all references

References:

[1]	Z. Arai, On hyperbolic plateaus of the Hénon map, Experimental Mathematics, 16 (2007), 181-188. doi: 10.1080/10586458.2007.10128992.
[2]	P. Blanchard, Complex analytic dynamics on the Riemann sphere, Bulletin of the American Mathematical Society, 11 (1984), 85-141. doi: 10.1090/S0273-0979-1984-15240-6.
[3]	B. Branner, The Mandelbrot set, in Amer. Math. Soc., 39 (1989), 75-105. doi: 10.1090/psapm/039/1010237.
[4]	M. Braverman, Hyperbolic Julia sets are poly-time computable, Electronic Notes in Theoretical Computer Science, 120 (2005), 17-30. doi: 10.1016/j.entcs.2004.06.031.
[5]	M. Braverman and M. Yampolsky, Computability of Julia Sets, Springer-Verlag, 2009.
[6]	R. Carniel, A quasi-cell mapping approach to the global dynamical analysis of Newton's root-finding algorithm, Applied Numerical Mathematics, 15 (1994), 133-152. doi: 10.1016/0168-9274(94)00016-6.
[7]	L. H. de Figueiredo and J. Stolfi, Affine arithmetic: concepts and applications, Numerical Algorithms, 37 (2004), 147-158. doi: 10.1023/B:NUMA.0000049462.70970.b6.
[8]	M. Dellnitz and A. Hohmann, A subdivision algorithm for the computation of unstable manifolds and global attractors, Numerische Mathematik, 75 (1997), 293-317. doi: 10.1007/s002110050240.
[9]	M. Dellnitz and O. Junge, Set oriented numerical methods for dynamical systems, in Handbook of dynamical systems, North-Holland, 2 (2002), 221-264. doi: 10.1016/S1874-575X(02)80026-1.
[10]	R. L. Devaney and L. Keen (eds.), Chaos and Fractals: The Mathematics behind the Computer Graphics, Proceedings of Symposia in Applied Mathematics 39, AMS, 1989.
[11]	A. Douady, Does a Julia set depend continuously on the polynomial?, in Complex Dynamical Systems: The Mathematics Behind the Mandelbrot and Julia Sets (ed. R. L. Devaney), Proceedings of Symposia in Applied Mathematics, AMS, 49 (1994), 91-138. doi: 10.1090/psapm/049/1315535.
[12]	M. B. Durkin, The accuracy of computer algorithms in dynamical systems, International Journal of Bifurcation and Chaos in Applied Sciences and Engineering, 1 (1991), 625-639. doi: 10.1142/S0218127491000452.
[13]	Z. Galias, Rigorous investigation of the Ikeda map by means of interval arithmetic, Nonlinearity, 15 (2002), 1759-1779. doi: 10.1088/0951-7715/15/6/304.
[14]	E. Grassmann and J. Rokne, The range of values of a circular complex polynomial over a circular complex interval, Computing, 23 (1979), 139-169. doi: 10.1007/BF02252094.
[15]	T. H. Gronwall, Some remarks on conformal representation,, Annals of Mathematics, 16 (): 72. doi: 10.2307/1968044.
[16]	S. L. Hruska, Constructing an expanding metric for dynamical systems in one complex variable, Nonlinearity, 18 (2005), 81-100. doi: 10.1088/0951-7715/18/1/005.
[17]	S. L. Hruska, Rigorous numerical studies of the dynamics of polynomial skew products of $C^2$, in Complex dynamics, vol. 396 of Contemp. Math., AMS, 2006, 85-100. doi: 10.1090/conm/396/07395.
[18]	C. S. Hsu, Cell-to-cell Mapping: A Method of Global Analysis for Nonlinear Systems, Springer-Verlag, 1987. doi: 10.1007/978-1-4757-3892-6.
[19]	C. S. Hsu, Global analysis by cell mapping, International Journal of Bifurcations and Chaos, 2 (1992), 727-771. doi: 10.1142/S0218127492000422.
[20]	O. Junge, Rigorous discretization of subdivision techniques, in International Conference on Differential Equations, Vol. 1, 2 (Berlin, 1999), World Sci. Publ., 2000, 916-918.
[21]	W. D. Kalies, K. Mischaikow and R. C. A. M. VanderVorst, An algorithmic approach to chain recurrence, Foundations of Computational Mathematics, 5 (2005), 409-449. doi: 10.1007/s10208-004-0163-9.
[22]	L. Keen, Julia sets, in Proc. Sympos. Appl. Math., 39 (1989), 57-74. doi: 10.1090/psapm/039/1010236.
[23]	V. Kreinovich, Interval software,, , ().
[24]	D. Michelucci and S. Foufou, Interval-based tracing of strange attractors, International Journal of Computational Geometry & Applications, 16 (2006), 27-39. doi: 10.1142/S0218195906001914.
[25]	J. Milnor, Remarks on iterated cubic maps, Experimental Mathematics, 1 (1992), 5-24.
[26]	J. Milnor, Dynamics in One Complex Variable, vol. 160 of Annals of Mathematics Studies, 3rd edition, Princeton University Press, 2006.
[27]	R. E. Moore, Interval Analysis, Prentice-Hall, 1966.
[28]	R. E. Moore, R. B. Kearfott and M. J. Cloud, Introduction to Interval Analysis, SIAM, 2009. doi: 10.1137/1.9780898717716.
[29]	R. P. Munafo, Roundoff error, http://mrob.com/pub/muency/roundofferror.html, 1996, Accessed: 2015-12-09.
[30]	D. Nehab and H. Hoppe, A fresh look at generalized sampling, Foundations and Trends in Computer Graphics and Vision, 8 (2014), 1-84. doi: 10.1561/0600000053.
[31]	G. Osipenko, Dynamical Systems, Graphs, and Algorithms, vol. 1889 of Lecture Notes in Mathematics, Springer-Verlag, 2007.
[32]	A. Paiva, L. H. de Figueiredo and J. Stolfi, Robust visualization of strange attractors using affine arithmetic, Computers & Graphics, 30 (2006), 1020-1026. doi: 10.1016/j.cag.2006.08.016.
[33]	H.-O. Peitgen and P. H. Richter, The Beauty of Fractals: Images of Complex Dynamical Systems, Springer-Verlag, 1986. doi: 10.1007/978-3-642-61717-1.
[34]	H.-O. Peitgen and D. Saupe (eds.), The Science of Fractal Images, Springer-Verlag, 1988. doi: 10.1007/978-1-4612-3784-6.
[35]	M. S. Petković and L. D. Petković, Complex Interval Arithmetic and Its Applications, Wiley-VCH Verlag, 1998.
[36]	R. Rettinger, A fast algorithm for {Julia} sets of hyperbolic rational functions, Electronic Notes in Theoretical Computer Science, 120 (2005), 145-157. doi: 10.1016/j.entcs.2004.06.041.
[37]	R. Rettinger and K. Weihrauch, The computational complexity of some Julia sets, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003), ACM, 2003, 177-185. doi: 10.1145/780542.780570.
[38]	J. Rokne, The range of values of a complex polynomial over a complex interval, Computing, 22 (1979), 153-169. doi: 10.1007/BF02253127.
[39]	D. Ruelle, Repellers for real analytic maps, Ergodic Theory and Dynamical Systems, 2 (1982), 99-107. doi: 10.1017/S0143385700009603.
[40]	S. M. Rump and M. Kashiwagi, Implementation and improvements of affine arithmetic, Nonlinear Theory and Its Applications, IEICE, 6 (2015), 341-359.
[41]	H. Samet, The quadtree and related hierarchical data structures, Computing Surveys, 16 (1984), 187-260. doi: 10.1145/356924.356930.
[42]	D. Saupe, Efficient computation of Julia sets and their fractal dimension, Physica D, 28 (1987), 358-370. doi: 10.1016/0167-2789(87)90024-8.
[43]	N. Steinmetz, Rational Iteration: Complex Analytic Dynamical Systems, Walter de Gruyter & Co., 1993. doi: 10.1515/9783110889314.
[44]	C. M. Stroh, Julia Sets of Complex Polynomials and Their Implementation on the Computer, Master's thesis, University of Linz, 1997.
[45]	R. Tarjan, Depth-first search and linear graph algorithms, SIAM Journal on Computing, 1 (1972), 146-160. doi: 10.1137/0201010.
[46]	W. Tucker, The Lorenz attractor exists, C. R. Acad. Sci. Paris Sér. I Math., 328 (1999), 1197-1202. doi: 10.1016/S0764-4442(99)80439-X.
[47]	J. Tupper, Reliable two-dimensional graphing methods for mathematical formulae with two free variables, in Proceedings of SIGGRAPH '01, ACM, 2001, 77-86. doi: 10.1145/383259.383267.

[1]	Maxime Breden, Jean-Philippe Lessard. Polynomial interpolation and a priori bootstrap for computer-assisted proofs in nonlinear ODEs. Discrete and Continuous Dynamical Systems - B, 2018, 23 (7) : 2825-2858. doi: 10.3934/dcdsb.2018164
[2]	István Balázs, Jan Bouwe van den Berg, Julien Courtois, János Dudás, Jean-Philippe Lessard, Anett Vörös-Kiss, JF Williams, Xi Yuan Yin. Computer-assisted proofs for radially symmetric solutions of PDEs. Journal of Computational Dynamics, 2018, 5 (1&2) : 61-80. doi: 10.3934/jcd.2018003
[3]	Chiara Caracciolo, Ugo Locatelli. Computer-assisted estimates for Birkhoff normal forms. Journal of Computational Dynamics, 2020, 7 (2) : 425-460. doi: 10.3934/jcd.2020017
[4]	Maciej J. Capiński, Emmanuel Fleurantin, J. D. Mireles James. Computer assisted proofs of two-dimensional attracting invariant tori for ODEs. Discrete and Continuous Dynamical Systems, 2020, 40 (12) : 6681-6707. doi: 10.3934/dcds.2020162
[5]	Thomas Wanner. Computer-assisted equilibrium validation for the diblock copolymer model. Discrete and Continuous Dynamical Systems, 2017, 37 (2) : 1075-1107. doi: 10.3934/dcds.2017045
[6]	A. Aschwanden, A. Schulze-Halberg, D. Stoffer. Stable periodic solutions for delay equations with positive feedback - a computer-assisted proof. Discrete and Continuous Dynamical Systems, 2006, 14 (4) : 721-736. doi: 10.3934/dcds.2006.14.721
[7]	Nahid Banihashemi, C. Yalçın Kaya. Inexact restoration and adaptive mesh refinement for optimal control. Journal of Industrial and Management Optimization, 2014, 10 (2) : 521-542. doi: 10.3934/jimo.2014.10.521
[8]	Piotr Zgliczyński. Steady state bifurcations for the Kuramoto-Sivashinsky equation: A computer assisted proof. Journal of Computational Dynamics, 2015, 2 (1) : 95-142. doi: 10.3934/jcd.2015.2.95
[9]	Koh Katagata. Quartic Julia sets including any two copies of quadratic Julia sets. Discrete and Continuous Dynamical Systems, 2016, 36 (4) : 2103-2112. doi: 10.3934/dcds.2016.36.2103
[10]	Robert L. Devaney, Daniel M. Look. Buried Sierpinski curve Julia sets. Discrete and Continuous Dynamical Systems, 2005, 13 (4) : 1035-1046. doi: 10.3934/dcds.2005.13.1035
[11]	Danilo Antonio Caprio. A class of adding machines and Julia sets. Discrete and Continuous Dynamical Systems, 2016, 36 (11) : 5951-5970. doi: 10.3934/dcds.2016061
[12]	Nathaniel D. Emerson. Dynamics of polynomials with disconnected Julia sets. Discrete and Continuous Dynamical Systems, 2003, 9 (4) : 801-834. doi: 10.3934/dcds.2003.9.801
[13]	Luís Tiago Paiva, Fernando A. C. C. Fontes. Adaptive time--mesh refinement in optimal control problems with state constraints. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4553-4572. doi: 10.3934/dcds.2015.35.4553
[14]	Xuemei Li, Rafael de la Llave. Convergence of differentiable functions on closed sets and remarks on the proofs of the "Converse Approximation Lemmas''. Discrete and Continuous Dynamical Systems - S, 2010, 3 (4) : 623-641. doi: 10.3934/dcdss.2010.3.623
[15]	Lorenzo Valvo, Ugo Locatelli. Hamiltonian control of magnetic field lines: Computer assisted results proving the existence of KAM barriers. Journal of Computational Dynamics, 2022 doi: 10.3934/jcd.2022002
[16]	Tien-Cuong Dinh, Nessim Sibony. Rigidity of Julia sets for Hénon type maps. Journal of Modern Dynamics, 2014, 8 (3&4) : 499-548. doi: 10.3934/jmd.2014.8.499
[17]	Tarik Aougab, Stella Chuyue Dong, Robert S. Strichartz. Laplacians on a family of quadratic Julia sets II. Communications on Pure and Applied Analysis, 2013, 12 (1) : 1-58. doi: 10.3934/cpaa.2013.12.1
[18]	Krzysztof Barański, Michał Wardal. On the Hausdorff dimension of the Sierpiński Julia sets. Discrete and Continuous Dynamical Systems, 2015, 35 (8) : 3293-3313. doi: 10.3934/dcds.2015.35.3293
[19]	Ali Messaoudi, Rafael Asmat Uceda. Stochastic adding machine and $2$-dimensional Julia sets. Discrete and Continuous Dynamical Systems, 2014, 34 (12) : 5247-5269. doi: 10.3934/dcds.2014.34.5247
[20]	Ranjit Bhattacharjee, Robert L. Devaney, R.E. Lee Deville, Krešimir Josić, Monica Moreno-Rocha. Accessible points in the Julia sets of stable exponentials. Discrete and Continuous Dynamical Systems - B, 2001, 1 (3) : 299-318. doi: 10.3934/dcdsb.2001.1.299

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Luiz Henrique de Figueiredo Diego Nehab Jorge Stolfi João Batista S. de Oliveira
on Google Scholar
Luiz Henrique de Figueiredo Diego Nehab Jorge Stolfi João Batista S. de Oliveira

[Back to Top]