Advanced Search
Article Contents
Article Contents

Polynomial interpolation and a priori bootstrap for computer-assisted proofs in nonlinear ODEs

  • * Corresponding author

    * Corresponding author

The second author is supported by NSERC

Abstract Full Text(HTML) Figure(6) / Table(5) Related Papers Cited by
  • In this work, we introduce a method based on piecewise polynomial interpolation to enclose rigorously solutions of nonlinear ODEs. Using a technique which we call a priori bootstrap, we transform the problem of solving the ODE into one of looking for a fixed point of a high order smoothing Picard-like operator. We then develop a rigorous computational method based on a Newton-Kantorovich type argument (the radii polynomial approach) to prove existence of a fixed point of the Picard-like operator. We present all necessary estimates in full generality and for any nonlinearities. With our approach, we study two systems of nonlinear equations: the Lorenz system and the ABC flow. For the Lorenz system, we solve Cauchy problems and prove existence of periodic and connecting orbits at the classical parameters, and for ABC flows, we prove existence of ballistic spiral orbits.

    Mathematics Subject Classification: Primary: 65G20, 65P99, 65D30, 37M99, 37C27.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  The longest orbits we are able to validate, with a total number of coefficient of approximately 14000. In blue for $p = 1$, in green for $p = 2$ and in red for $p = 3$. The initial value is given by (22)

    Figure 2.  A validated periodic orbit of the Lorenz system, whose period $\tau$ is approximately $11.9973$. We used two iterations of a priori bootstrap, that is $p = 3$, for the validation. If we want to minimize the total number of coefficients to do the validation, we can take $k = 3$ and $m = 602$ (which makes $7225$ coefficients in total), and we then get a validation radius of $1.5627\times 10^{-4}$. It is possible to get a significantly lower validation radius, at the expense of a slight increase in the total number of coefficients: for instance with $k = 5$ and $m = 495$ (which makes $8911$ coefficients in total), we get a validation radius of $4.7936\times 10^{-9}$

    Figure 3.  Validated connecting orbit for the Lorenz system, with parameters $(\sigma, \beta, \rho) = (10, \frac{8}{3}, 28)$. The local stable manifold of the origin is in blue, the local unstable manifold of $\left(\sqrt{\beta(\rho-1)}, \sqrt{\beta(\rho-1)}, \rho-1\right)$ in yellow, and the green connection between them (of length $\tau\simeq 17.3$) is validated using polynomial interpolation, with a priori bootstrap ($p = 3$). The proof gives a validation radius of $r = 3.1340\times 10^{-5}$

    Figure 4.  These are the orbits that are described in Theorem 7.1. The color varies from blue for $A = 1$ to red for $A = 0.1$. Each proof was done with $p = 2$, $k = 2$ and $m = 50$, and gave a validation radius varying from $r = 4.8313\times 10^{-8}$ to $r = 7.4012\times 10^{-6}$

    Figure 5.  This is the orbit that is described in Theorem 7.2. The proof was done with $p = 2$, $k = 2$ and $m = 300$, and gave a validation radius $r = 4.0458\times 10^{-6}$

    Figure 6.  An example of the situation described just above, with $k = 11$ and $i_0 = 9$. The black squares represent the other Chebyshev points $x_{i}^k$

    Table 1.  Comparisons for $p = 1$. $\tau_{max}$ is the longest integration time for which the proof succeeds, and $r$ is the associated validation radius, that is a bound of the distance (in $\mathcal{C}^0$ norm) between the numerical data used and the true solution

    $k$ $m$ $nm(k+1)$ $\tau_{max}$ $r$
    1 2333 13998 $\color{red} {0.69} $ $2.3233\times 10^{-5}$
    2 1556 14004 0.64 $1.1524\times 10^{-7}$
    3 1167 14004 0.58 $8.6805\times 10^{-9}$
     | Show Table
    DownLoad: CSV

    Table 2.  Comparisons for $p = 2$. $\tau_{max}$ is the longest integration time for which the proof succeeds, and $r$ is the associated validation radius, that is a bound of the distance (in $\mathcal{C}^0$ norm) between the numerical data used and the true solution

    $k$ $m$ $nm(k+1)$ $\tau_{max}$ $r$
    1 2333 13998 0.97 $1.5718\times 10^{-3}$
    2 1556 14004 $\color{red} {5.6} $ $8.4373\times 10^{-5}$
    3 1167 14004 5.5 $8.4184\times 10^{-8}$
    4 933 13995 4.9 $7.9190\times 10^{-9}$
     | Show Table
    DownLoad: CSV

    Table 3.  Comparisons for $p = 3$. $\tau_{max}$ is the longest integration time for which the proof succeeds, and $r$ is the associated validation radius, that is a bound of the distance (in $\mathcal{C}^0$ norm) between the numerical data used and the true solution

    $k$ $m$ $nm(k+1)$ $\tau_{max}$ $r$
    2 1556 14004 5.6 $7.6716\times 10^{-4}$
    3 1167 14004 $\color{red} {8.1} $ $9.3043\times 10^{-6}$
    4 933 13995 $\color{red} {8.1} $ $8.8204\times 10^{-8}$
    5 778 14004 8.0 $1.6175\times 10^{-8}$
    9 467 14010 7.9 $1.3748\times 10^{-8}$
    19 233 13980 6.9 $2.2998\times 10^{-8}$
     | Show Table
    DownLoad: CSV

    Table 4.  Minimal number of coefficients needed to validate the orbit of length $\tau = 2$, starting from $u_0$ given in (22), and the associated validation radius provided by the proof. We repeat that in this example, we put the emphasis on getting an existence result with a minimal amount of computational power, which of course results in less sharp validation radius, especially in situations where the $Y$ bound is the limiting factor

    $k=1$ $k=2$ $k=3$ $k=4$
    $p=2$ no proof $m=416$ $m=415$ $m=377$
    no proof $\color{red} {nm(k+1)=3744} $ $nm(k+1)=4980$ $nm(k+1)=5655$
    no proof $r=2.9\times 10^{-4}$ $r=9.4\times 10^{-7}$ $r=1.4\times 10^{-10}$
    $k=2$ $k=3$ $k=4$ $k=5$
    $p=3$ $m=470$ $m=125$ $m=110$ $m=99$
    $nm(k+1)=4230$ $\color{red} {nm(k+1)=1500} $ $nm(k+1)=1650$ $nm(k+1)=1782$
    $r=1.2\times 10^{-3}$ $r=3.4\times 10^{-4}$ $r=7.2\times 10^{-6}$ $r=1.8\times 10^{-7}$
     | Show Table
    DownLoad: CSV

    Table 5.  The intervals $[\tau^-_A, \tau^+_A]$, for $A = 0.1, 0.2, \ldots, 1$ in which the period $\tau_A$ of the solution described in Theorem 7.1 is proved to be

    $A$ $1$ $0.9$ $0.8$ $0.7$ $0.6$ $0.5$ $0.4$ $0.3$ $0.2$ $0.1$
    $\tau^-_A$ $3.23527736$ $3.41779635$ $3.62512508$ $3.86405419$ $4.14464726$ $4.48269179$ $4.90491344$ $5.46177978$ $6.26680147$ $7.67945129$
    $\tau^+_A$ $3.23527746$ $3.41779647$ $3.62512521$ $3.86405436$ $4.14464749$ $4.48269213$ $4.90491401$ $5.46178092$ $6.26680442$ $7.67946552$
     | Show Table
    DownLoad: CSV
  • [1] V. Arnold, Sur la topologie des écoulements stationaires des fluides parfaits, C. R. Acad. Sci. Paris, 261 (1965), 17-20. 
    [2] M. Berz and K. Makino, Verified integration of ODEs and flows using differential algebraic methods on high-order Taylor models, Reliab. Comput., 4 (1998), 361-369.  doi: 10.1023/A:1024467732637.
    [3] M. Breden and J.-P. Lessard, MATLAB codes to perform the computer-assisted proofs available at http://archimede.mat.ulaval.ca/jplessard/AprioriBootstrap/ Breden M. Lessard J.-P. Mireles James J. D. Computation of maximal local (un)stable manifold patches by the parameterization method Indag. Math. (N.S.) 2016 27 340 367 10.1016/j.indag.2015.11.001 MR3437754 Castelli R. Lessard J.-P. Mireles James J. D. Parameterization of invariant manifolds for periodic orbits (Ⅱ): a-posteriori analysis and computer assisted error bounds J. Dynam. Differential Equations 2017 10.1007/s10884-017-9609-z CasLesMir16 Breden M. Lessard J.-P. Vanicat M. Global bifurcation diagrams of steady states of systems of pdes via rigorous numerics: A 3-component reaction-diffusion system Acta Appl. Math. 2013 128 113 152 10.1007/s10440-013-9823-6 MR3125637 E. W. Cheney, Introduction to Approximation Theory, AMS Chelsea Publishing, Providence, RI, 1998. Reprint of the second (1982) edition.

    MR1656150 Chow S.-N. Van Vleck E. S. A shadowing lemma approach to global error analysis for initial value ODEs SIAM J. Sci. Comput. 1994 15 959 976 10.1137/0915058 MR1278010 Coomes B. A. Koçcak H. Palmer K. J. Transversal connecting orbits from shadowing Numer. Math. 2007 106 427 469 10.1007/s00211-007-0065-2 MR2302059 Coomes B. A. Koçcak H. Palmer K. J. Homoclinic shadowing J. Dynam. Differential Equations 2005 17 175 215 10.1007/s10884-005-3146-x MR2157844 Day S. Kalies W. D. Rigorous computation of the global dynamics of integrodifference equations with smooth nonlinearities SIAM J. Numer. Anal. 2013 51 2957 2983 10.1137/120903129 MR3124898 Day S. Lessard J.-P. Mischaikow K. Validated continuation for equilibria of PDEs SIAM J. Numer. Anal. 2007 45 1398 1424 (electronic) 10.1137/050645968 MR2338393 Dombre T. Frisch U. Greene J. M. Hénon M. Mehr A. Soward A. M. Chaotic streamlines in the ABC flows J. Fluid Mech. 1986 167 353 391 10.1017/S0022112086002859 MR851673 Ehlich H. Zeller K. Auswertung der Normen von Interpolationsoperatoren Math. Ann. 1966 164 105 112 10.1007/BF01429047 MR0194799 Figueras J.-L. Haro A. Luque A. Rigorous computer assisted application of KAM theory: A modern approach Foundations of Computational Mathematics 2017 17 1123 1193 10.1007/s10208-016-9339-3 MR3709329 Gameiro M. Lessard J.-P. A Posteriori Verification of Invariant Objects of Evolution Equations: Periodic Orbits in the Kuramoto-Sivashinsky PDE SIAM J. Appl. Dyn. Syst. 2017 16 687 728 10.1137/16M1073789 MR3623202 Gameiro M. Lessard J.-P. Pugliese A. Computation of smooth manifolds via rigorous multi-parameter continuation in infinite dimensions Found. Comput. Math. 2016 16 531 575 10.1007/s10208-015-9259-7 MR3464215 Gidea M. Zgliczyński P. Covering relations for multidimensional dynamical systems J. Differential Equations 2004 202 59 80 10.1016/j.jde.2004.03.013 MR2060531 Gilbert Friedlander Susan A. D. Vishik M. Hydrodynamic instability for certain abc flows Geophysical and Astrophysical Fluid Dynamics 1993 73 97 107 10.1080/03091929308203622 MR1289022 A. Haro, M. Canadell, J.-L. Figueras, A. Luque and J.-M. Mondelo, The Parameterization Method for Invariant Manifolds: From Rigorous Results to Effective Computations, volume 195 of Applied Mathematical Sciences, Springer, 2016.


    MR3467671 Hiraoka Y. Rigorous numerics for symmetric homoclinic orbits in reversible dynamical systems Kybernetika (Prague) 2007 43 797 806 MR2388394 Jorba À. Zou M. A software package for the numerical integration of ODEs by means of high-order Taylor methods Experiment. Math. 2005 14 99 117 10.1080/10586458.2005.10128904 MR2146523 D. E. Knuth, The Art of Computer Programming, Vol. 2, Addison-Wesley Publishing Co., Reading, Mass., second edition, 1981. Seminumerical algorithms, Addison-Wesley Series in Computer Science and Information Processing.

    MR633878 Koçcak H. Palmer K. Coomes B. Shadowing in ordinary differential equations Rend. Semin. Mat. Univ. Politec. Torino 2007 65 89 113 MR2339601 Koch H. Schenkel A. Wittwer P. Computer-assisted proofs in analysis and programming in logic: A case study SIAM Rev. 1996 38 565 604 10.1137/S0036144595284180 MR1420838 Lessard J.-P. Recent advances about the uniqueness of the slowly oscillating periodic solutions of Wright's equation J. Differential Equations 2010 248 992 1016 10.1016/j.jde.2009.11.008 MR2592879 Lessard J.-P. Mireles James J. D. Reinhardt C. Computer assisted proof of transverse saddle-to-saddle connecting orbits for first order vector fields J. Dynam. Differential Equations 2014 26 267 313 10.1007/s10884-014-9367-0 MR3207723 Lessard J.-P. Mireles James J. D. Ransford J. Automatic differentiation for Fourier series and the radii polynomial approach Phys. D 2016 334 174 186 10.1016/j.physd.2016.02.007 MR3545977 Makino K. Berz M. Taylor models and other validated functional inclusion methods Int. J. Pure Appl. Math. 2003 4 379 456 MR1962787 McMillen T. Xin J. Yu Y. Zlatos A. Ballistic orbits and front speed enhancement for ABC flows SIAM J. Appl. Dyn. Syst. 2016 15 1753 1782 10.1137/16M1059059 MR3549020 J. D. Mireles James and K. Mischaikow, Computational proofs in dynamics, In Bjorn Engquist, editor, Encyclopedia of Applied and Computational Mathematics, pages 288-295. Springer, 2015. Mischaikow K. Mrozek M. Chaos in the Lorenz equations: A computer-assisted proof Bull. Amer. Math. Soc. (N.S.) 1995 32 66 72 10.1090/S0273-0979-1995-00558-6 MR1276767 Nakao M. T. Numerical verification methods for solutions of ordinary and partial differential equations Numer. Funct. Anal. Optim. 2001 22 321 356 10.1081/NFA-100105107 MR1849323 Neumaier A. Rage T. Rigorous chaos verification in discrete dynamical systems Phys. D 1993 67 327 346 10.1016/0167-2789(93)90169-2 MR1236201 S. Oishi, Numerical verification method of existence of connecting orbits for continuous dynamical systems, J. UCS, SCAN-97 (Lyon), 4 (1998), 193{201 (electronic).

    MR1661847 K. J. Palmer, Exponential dichotomies, the shadowing lemma and transversal homoclinic points, In Dynamics Reported, volume 1 of Dynam. Report. Ser. Dynam. Systems Appl., pages 265-306. Wiley, Chichester, 1988.

    MR945967 Rump S. M. Verification methods: Rigorous results using floating-point arithmetic Acta Numer. 2010 19 287 449 10.1017/S096249291000005X MR2652784 S. M. Rump, INTLAB-INTerval LABoratory, In Tibor Csendes, editor, Developments in Reliable Computing, pages 77-104. Kluwer Academic Publishers, Dordrecht, 1999. http://www.ti3.tu-harburg.de/rump/. doi: 10.1007/978-94-017-1247-7_7.

    [4] D. Stoffer and K. J. Palmer, Rigorous verification of chaotic behaviour of maps using validated shadowing, Nonlinearity, 12 (1999), 1683-1698.  doi: 10.1088/0951-7715/12/6/316.
    [5] L. N. Trefethen, Approximation Theory and Approximation Practice, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2013.
    [6] W. Tucker, Validated Numerics, Princeton University Press, Princeton, NJ, 2011. A short introduction to rigorous computations.
    [7] J. B. van den Berg and J.-P. Lessard, Rigorous numerics in dynamics, Notices of the American Mathematical Society, 62 (2015), 1057-1061.  doi: 10.1090/noti1276.
    [8] J. B. van den BergA. DeschênesJ.-P. Lessard and J. D. Mireles James, Stationary Coexistence of Hexagons and Rolls via Rigorous Computations, SIAM J. Appl. Dyn. Syst., 14 (2015), 942-979.  doi: 10.1137/140984506.
    [9] J. B. van den Berg and R. Sheombarsing, Rigorous numerics for odes using chebyshev series and domain decomposition, Submitted, 2016.
    [10] J. B. van den BergC. M. Groothedde and J. F. Williams, Rigorous computation of a radially symmetric localized solution in a Ginzburg-Landau problem, SIAM J. Appl. Dyn. Syst., 14 (2015), 423-447.  doi: 10.1137/140987973.
    [11] J. B. van den BergJ.-P. Lessard and K. Mischaikow, Global smooth solution curves using rigorous branch following, Math. Comp., 79 (2010), 1565-1584.  doi: 10.1090/S0025-5718-10-02325-2.
    [12] J. B. van den BergJ. D. Mireles-JamesJ.-P. Lessard and K. Mischaikow, Rigorous numerics for symmetric connecting orbits: Even homoclinics of the Gray-Scott equation, SIAM J. Math. Anal., 43 (2011), 1557-1594.  doi: 10.1137/100812008.
    [13] J. B. van den BergJ. D. Mireles James and C. Reinhardt, Computing (un)stable manifolds with validated error bounds: Non-resonant and resonant spectra, J. Nonlinear Sci., 26 (2016), 1055-1095.  doi: 10.1007/s00332-016-9298-5.
    [14] D. Wilczak, Abundance of heteroclinic and homoclinic orbits for the hyperchaotic Rössler system, Discrete Contin. Dyn. Syst. Ser. B, 11 (2009), 1039-1055.  doi: 10.3934/dcdsb.2009.11.1039.
    [15] D. Wilczak, Symmetric heteroclinic connections in the Michelson system: A computer assisted proof, SIAM J. Appl. Dyn. Syst., 4 (2005), 489-514(electronic).  doi: 10.1137/040611112.
    [16] D. Wilczak and P. Zgliczynski, Heteroclinic connections between periodic orbits in planar restricted circular three-body problem——a computer assisted proof, Comm. Math. Phys., 234 (2003), 37-75.  doi: 10.1007/s00220-002-0709-0.
    [17] A. WittigM. BerzJ. GroteK. Makino and S. Newhouse, Rigorous and accurate enclosure of invariant manifolds on surfaces, Regul. Chaotic Dyn., 15 (2010), 107-126.  doi: 10.1134/S1560354710020024.
    [18] J. XinY. Yu and A. Zlatos, Periodic orbits of the ABC flow with $A = B = C = 1$, SIAM J. Math. Anal., 48 (2016), 4087-4093.  doi: 10.1137/16M1076241.
    [19] N. Yamamoto, A numerical verification method for solutions of boundary value problems with local uniqueness by Banach's fixed-point theorem, SIAM J. Numer. Anal., 35 (1998), 2004-2013.  doi: 10.1137/S0036142996304498.
    [20] P. Zgliczyński, $C^1$ Lohner algorithm, Found. Comput. Math., 2 (2002), 429-465(electronic).  doi: 10.1007/s102080010025.
    [21] P. Zgliczyński, Rigorous numerics for dissipative partial differential equations. Ⅱ. Periodic orbit for the Kuramoto-Sivashinsky PDE—a computer-assisted proof, Found. Comput. Math., 4 (2004), 157-185.  doi: 10.1007/s10208-002-0080-8.
    [22] P. Zgliczyński and M. Gidea, Covering relations for multidimensional dynamical systems, J. Differential Equations, 202 (2004), 32-58.  doi: 10.1016/j.jde.2004.03.013.
    [23] P. Zgliczyński, Covering relations, cone conditions and the stable manifold theorem, J. Differential Equations, 246 (2009), 1774-1819.  doi: 10.1016/j.jde.2008.12.019.
    [24] CAPD: Computer assisted proofs in dynamics, a package for rigorous numerics, http://capd.ii.uj.edu.pl/.
  • 加载中




Article Metrics

HTML views(1212) PDF downloads(223) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint