| Title:
|
Computing discrete convolutions with verified accuracy via Banach algebras and the FFT (English) |
| Author:
|
Lessard, Jean-Philippe |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
63 |
| Issue:
|
3 |
| Year:
|
2018 |
| Pages:
|
219-235 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
We introduce a method to compute rigorous component-wise enclosures of discrete convolutions using the fast Fourier transform, the properties of Banach algebras, and interval arithmetic. The purpose of this new approach is to improve the implementation and the applicability of computer-assisted proofs performed in weighed $\ell ^1$ Banach algebras of Fourier/Chebyshev sequences, whose norms are known to be numerically unstable. We introduce some application examples, in particular a rigorous aposteriori error analysis for a steady state in the quintic Swift-Hohenberg PDE. (English) |
| Keyword:
|
discrete convolutions |
| Keyword:
|
Banach algebras |
| Keyword:
|
fast Fourier transform |
| Keyword:
|
interval arithmetic |
| Keyword:
|
rigorously verified numerics |
| Keyword:
|
quintic Swift-Hohenberg PDE |
| MSC:
|
42B05 |
| MSC:
|
46B45 |
| MSC:
|
46J15 |
| MSC:
|
65G40 |
| MSC:
|
65R10 |
| MSC:
|
65T50 |
| idZBL:
|
Zbl 06945730 |
| idMR:
|
MR3833658 |
| DOI:
|
10.21136/AM.2018.0082-18 |
| . |
| Date available:
|
2018-07-16T08:46:53Z |
| Last updated:
|
2020-07-06 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147308 |
| . |
| Reference:
|
[1] Boyd, J. P.: Chebyshev and Fourier Spectral Methods.Dover Publications, Mineola (2001). Zbl 0994.65128, MR 1874071 |
| Reference:
|
[2] Brigham, E.: Fast Fourier Transform and Its Applications.Prentice Hall, Upper Saddle River (1988). |
| Reference:
|
[3] Cyranka, J.: Efficient and generic algorithm for rigorous integration forward in time of dPDEs. I.J. Sci. Comput. 59 (2014), 28-52. Zbl 1296.65138, MR 3167726, 10.1007/s10915-013-9749-1 |
| Reference:
|
[4] Day, S., Hiraoka, Y., Mischaikow, K., Ogawa, T.: Rigorous numerics for global dynamics: a study of the Swift-Hohenberg equation.SIAM J. Appl. Dyn. Syst. 4 (2005), 1-31. Zbl 1058.35050, MR 2136516, 10.1137/040604479 |
| Reference:
|
[5] Day, S., Junge, O., Mischaikow, K.: A rigorous numerical method for the global analysis of infinite-dimensional discrete dynamical systems.SIAM J. Appl. Dyn. Syst. 3 (2004), 117-160. Zbl 1059.37068, MR 2067140, 10.1137/030600210 |
| Reference:
|
[6] Day, S., Kalies, W. D.: Rigorous computation of the global dynamics of integrodifference equations with smooth nonlinearities.SIAM J. Numer. Anal. 51 (2013), 2957-2983. Zbl 1288.37030, MR 3124898, 10.1137/120903129 |
| Reference:
|
[7] Day, S., Lessard, J.-P., Mischaikow, K.: Validated continuation for equilibria of PDEs.SIAM J. Numer. Anal. 45 (2007), 1398-1424. Zbl 1151.65074, MR 2338393, 10.1137/050645968 |
| Reference:
|
[8] Figueras, J.-L., Llave, R. de la: Numerical computations and computer assisted proofs of periodic orbits of the Kuramoto-Sivashinsky equation.SIAM J. Appl. Dyn. Syst. 16 (2017), 834-852. Zbl 1370.65047, MR 3633778, 10.1137/16M1073790 |
| Reference:
|
[9] Figueras, J.-L., Haro, A., Luque, A.: Rigorous computer-assisted application of KAM theory: a modern approach.Found. Comput. Math. 17 (2017), 1123-1193. Zbl 06814851, MR 3709329, 10.1007/s10208-016-9339-3 |
| Reference:
|
[10] Gameiro, M., Lessard, J.-P.: Analytic estimates and rigorous continuation for equilibria of higher-dimensional PDEs.J. Differ. Equations 249 (2010), 2237-2268. Zbl 1256.35196, MR 2718657, 10.1016/j.jde.2010.07.002 |
| Reference:
|
[11] Gameiro, M., Lessard, J.-P., Mischaikow, K.: Validated continuation over large parameter ranges for equilibria of PDEs.Math. Comput. Simul. 79 (2008), 1368-1382. Zbl 1166.65379, MR 2487806, 10.1016/j.matcom.2008.03.014 |
| Reference:
|
[12] Gameiro, M., Lessard, J.-P., Ricaud, Y.: Rigorous numerics for piecewise-smooth systems: a functional analytic approach based on Chebyshev series.J. Comput. Appl. Math. 292 (2016), 654-673. Zbl 1323.65123, MR 3392421, 10.1016/j.cam.2015.05.016 |
| Reference:
|
[13] Hiraoka, Y., Ogawa, T.: Rigorous numerics for localized patterns to the quintic Swift-Hohenberg equation.Japan J. Ind. Appl. Math. 22 (2005), 57-75. Zbl 1067.65146, MR 2126387, 10.1007/BF03167476 |
| Reference:
|
[14] Hiraoka, Y., Ogawa, T.: An efficient estimate based on FFT in topological verification method.J. Comput. Appl. Math. 199 (2007), 238-244. Zbl 1109.65110, MR 2269503, 10.1016/j.cam.2005.08.036 |
| Reference:
|
[15] Hungria, A., Lessard, J.-P., James, J. D. Mireles: Rigorous numerics for analytic solutions of differential equations: the radii polynomial approach.Math. Comput. 85 (2016), 1427-1459. Zbl 1332.65114, MR 3454370, 10.1090/mcom/3046 |
| Reference:
|
[16] Koch, H., Schenkel, A., Wittwer, P.: Computer-assisted proofs in analysis and programming in logic: A case study.SIAM Rev. 38 (1996), 565-604. Zbl 0865.68111, MR 1420838, 10.1137/S0036144595284180 |
| Reference:
|
[17] Lessard, J.-P., James, J. D. Mireles, Ransford, J.: Automatic differentiation for Fourier series and the radii polynomial approach.Physica D 334 (2016), 174-186. MR 3545977, 10.1016/j.physd.2016.02.007 |
| Reference:
|
[18] Lessard, J.-P., Reinhardt, C.: Rigorous numerics for nonlinear differential equations using Chebyshev series.SIAM J. Numer. Anal. 52 (2014), 1-22. Zbl 1290.65060, MR 3148084, 10.1137/13090883X |
| Reference:
|
[19] James, J. D. Mireles, Mischaikow, K.: Computational proofs in dynamics.Encyclopedia of Applied and Computational Mathematics B. Engquist Springer, Berlin (2015). MR 3470172, 10.1007/978-3-540-70529-1_322 |
| Reference:
|
[20] Moore, R. E.: Interval Analysis.Prentice-Hall, Englewood Cliffs (1966). Zbl 0176.13301, MR 0231516 |
| Reference:
|
[21] Nakao, M. T.: Numerical verification methods for solutions of ordinary and partial differential equations.Numer. Funct. Anal. Optimization 22 (2001), 321-356. Zbl 1106.65315, MR 1849323, 10.1081/NFA-100105107 |
| Reference:
|
[22] Rump, S. M.: INTLAB - INTerval LABoratory.T. Csendes Developments in Reliable Computing Kluwer Academic Publishers, Dordrecht (1999), 77-104. Available at http://www.ti3.tu-harburg.de/rump/intlab/. Zbl 0949.65046 |
| Reference:
|
[23] Rump, S. M.: Verification methods: rigorous results using floating-point arithmetic.Acta Numerica 19 (2010), 287-449. Zbl 1323.65046, MR 2652784, 10.1017/S096249291000005X |
| Reference:
|
[24] Sakaguchi, H., Brand, H. R.: Stable localized solutions of arbitrary length for the quintic Swift-Hohenberg equation.Physica D 97 (1996), 274-285. 10.1016/0167-2789(96)00077-2 |
| Reference:
|
[25] Tucker, W.: Validated Numerics. A Short Introduction to Rigorous Computations.Princeton University Press, Princeton (2011). Zbl 1231.65077, MR 2807595 |
| Reference:
|
[26] Berg, J. B. van den, Groothedde, C. M., Lessard, J.-P.: A general method for computer-assisted proofs of periodic solutions in delay differential problems.Preprint (2018). MR 3896998 |
| Reference:
|
[27] Berg, J. B. van den, Lessard, J.-P.: Rigorous numerics in dynamics.Notices Am. Math. Soc. 62 (2015), 1057-1061. Zbl 1338.68301, MR 3444942, 10.1090/noti1276 |
| Reference:
|
[28] Berg, J. B. van den, Williams, J. F.: Validation of the bifurcation diagram in the 2D Ohta-Kawasaki problem.Nonlinearity 30 (2017), 1584-1638. Zbl 1366.65068, MR 3636312, 10.1088/1361-6544/aa60e8 |
| Reference:
|
[29] Loan, C. F. Van: Computational Frameworks for the Fast Fourier Transform.Frontiers in Applied Mathematics 10, SIAM, Philadelphia (1992). Zbl 0757.65154, MR 1153025, 10.1137/1.9781611970999 |
| Reference:
|
[30] Wilczak, D., Zgliczynski, P.: Heteroclinic connections between periodic orbits in planar restricted circular three-body problem---a computer-assisted proof.Commun. Math. Phys. 234 (2003), 37-75. Zbl 1055.70005, MR 1961956, 10.1007/s00220-002-0709-0 |
| Reference:
|
[31] Zgliczyński, P.: Rigorous numerics for dissipative PDEs. III: An effective algorithm for rigorous integration of dissipative PDEs.Topol. Methods Nonlinear Anal. 36 (2010), 197-262. Zbl 1230.65113, MR 2788972 |
| Reference:
|
[32] Zgliczyński, P., Mischaikow, K.: Rigorous numerics for partial differential equations: The Kuramoto-Sivashinsky equation.Found. Comput. Math. 1 (2001), 255-288. Zbl 0984.65101, MR 1838755, 10.1007/s102080010010 |
| . |
