This issuePrevious ArticlePartitioned second order method for magnetohydrodynamics in Elsässer variablesNext ArticleUnderlying one-step methods and nonautonomous stability of general linear methods
Polynomial interpolation and a priori bootstrap for computer-assisted proofs in nonlinear ODEs
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.
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
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
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
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
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
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/BredenM.LessardJ.-P.Mireles JamesJ. D.
Computation of maximal local (un)stable manifold patches by the parameterization method
Indag. Math. (N.S.)
20162734036710.1016/j.indag.2015.11.001MR3437754CastelliR.LessardJ.-P.Mireles JamesJ. D.
Parameterization of invariant manifolds for periodic orbits (Ⅱ): a-posteriori analysis and computer assisted error bounds
J. Dynam. Differential Equations
201710.1007/s10884-017-9609-zCasLesMir16BredenM.LessardJ.-P.VanicatM.
Global bifurcation diagrams of steady states of systems of pdes via rigorous numerics: A 3-component reaction-diffusion system
Acta Appl. Math.
201312811315210.1007/s10440-013-9823-6MR3125637
E. W. Cheney, Introduction to Approximation Theory, AMS Chelsea Publishing, Providence, RI, 1998. Reprint of the second (1982) edition.
MR1656150
ChowS.-N.Van VleckE. S.
A shadowing lemma approach to global error analysis for initial value ODEs
SIAM J. Sci. Comput.
19941595997610.1137/0915058MR1278010CoomesB. A.KoçcakH.PalmerK. J.
Transversal connecting orbits from shadowing
Numer. Math.
200710642746910.1007/s00211-007-0065-2MR2302059CoomesB. A.KoçcakH.PalmerK. J.
Homoclinic shadowing
J. Dynam. Differential Equations
20051717521510.1007/s10884-005-3146-xMR2157844DayS.KaliesW. D.
Rigorous computation of the global dynamics of integrodifference equations with smooth nonlinearities
SIAM J. Numer. Anal.
2013512957298310.1137/120903129MR3124898DayS.LessardJ.-P.MischaikowK.
Validated continuation for equilibria of PDEs
SIAM J. Numer. Anal.
20074513981424 (electronic)10.1137/050645968MR2338393DombreT.FrischU.GreeneJ. M.HénonM.MehrA.SowardA. M.
Chaotic streamlines in the ABC flows
J. Fluid Mech.
198616735339110.1017/S0022112086002859MR851673EhlichH.ZellerK.
Auswertung der Normen von Interpolationsoperatoren
Math. Ann.
196616410511210.1007/BF01429047MR0194799FiguerasJ.-L.HaroA.LuqueA.
Rigorous computer assisted application of KAM theory: A modern approach
Foundations of Computational Mathematics
2017171123119310.1007/s10208-016-9339-3MR3709329GameiroM.LessardJ.-P.
A Posteriori Verification of Invariant Objects of Evolution Equations: Periodic Orbits in the Kuramoto-Sivashinsky PDE
SIAM J. Appl. Dyn. Syst.
20171668772810.1137/16M1073789MR3623202GameiroM.LessardJ.-P.PuglieseA.
Computation of smooth manifolds via rigorous multi-parameter continuation in infinite dimensions
Found. Comput. Math.
20161653157510.1007/s10208-015-9259-7MR3464215GideaM.ZgliczyńskiP.
Covering relations for multidimensional dynamical systems
J. Differential Equations
2004202598010.1016/j.jde.2004.03.013MR2060531Gilbert Friedlander SusanA. D.VishikM.
Hydrodynamic instability for certain abc flows
Geophysical and Astrophysical Fluid Dynamics
1993739710710.1080/03091929308203622MR1289022
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.
10.1007/978-3-319-29662-3
MR3467671
HiraokaY.
Rigorous numerics for symmetric homoclinic orbits in reversible dynamical systems
Kybernetika (Prague)
200743797806MR2388394JorbaÀ.ZouM.
A software package for the numerical integration of ODEs by means of high-order Taylor methods
Experiment. Math.
2005149911710.1080/10586458.2005.10128904MR2146523
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çcakH.PalmerK.CoomesB.
Shadowing in ordinary differential equations
Rend. Semin. Mat. Univ. Politec. Torino
20076589113MR2339601KochH.SchenkelA.WittwerP.
Computer-assisted proofs in analysis and programming in logic: A case study
SIAM Rev.
19963856560410.1137/S0036144595284180MR1420838LessardJ.-P.
Recent advances about the uniqueness of the slowly oscillating periodic solutions of Wright's equation
J. Differential Equations
2010248992101610.1016/j.jde.2009.11.008MR2592879LessardJ.-P.Mireles JamesJ. D.ReinhardtC.
Computer assisted proof of transverse saddle-to-saddle connecting orbits for first order vector fields
J. Dynam. Differential Equations
20142626731310.1007/s10884-014-9367-0MR3207723LessardJ.-P.Mireles JamesJ. D.RansfordJ.
Automatic differentiation for Fourier series and the radii polynomial approach
Phys. D
201633417418610.1016/j.physd.2016.02.007MR3545977MakinoK.BerzM.
Taylor models and other validated functional inclusion methods
Int. J. Pure Appl. Math.
20034379456MR1962787McMillenT.XinJ.YuY.ZlatosA.
Ballistic orbits and front speed enhancement for ABC flows
SIAM J. Appl. Dyn. Syst.
2016151753178210.1137/16M1059059MR3549020
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.
MischaikowK.MrozekM.
Chaos in the Lorenz equations: A computer-assisted proof
Bull. Amer. Math. Soc. (N.S.)
199532667210.1090/S0273-0979-1995-00558-6MR1276767NakaoM. T.
Numerical verification methods for solutions of ordinary and partial differential equations
Numer. Funct. Anal. Optim.
20012232135610.1081/NFA-100105107MR1849323NeumaierA.RageT.
Rigorous chaos verification in discrete dynamical systems
Phys. D
19936732734610.1016/0167-2789(93)90169-2MR1236201
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
RumpS. M.
Verification methods: Rigorous results using floating-point arithmetic
Acta Numer.
20101928744910.1017/S096249291000005XMR2652784
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.
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.
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.
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/.
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$