Adaptive Step Selection for a Filtered Implicit Method
Stephen M. McGovern) · 2025
Read Adaptive Step Selection for a Filtered Implicit Method by Stephen M. McGovern) (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-00405.txt.
Introduction
Stephen McGovern presents adaptive step selection for a filtered numerical method in a 2025 paper. Filtering steps added before and after a classic method can raise its order and stability. The base method here is implicit Euler, a simple, stable scheme for differential equations. McGovern builds variable step pre-filters and post-filters so the method adapts its step size as it runs. Adaptive stepping spends effort where the solution changes fast and saves it where the solution stays calm.
Catalog record
| CREATOR | Stephen M. McGovern) |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-00405
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Adaptive Step Selection for a Filtered Implicit Method Stephen M. McGovern) Abstract Pre-filtering and post-filtering steps can be added to many of the traditional numerical methods to generate new, higher order methods with strong stability properties. Presented in this paper are a variable step pre-filter and post-filter that allow adaptive time stepping for a filtered method based on Implicit Euler from [ 4 ] . keywords filtered methods, filters, adaptivity, adaptive step, variable step † † runningheads: Adaptive Step Selection for a Filtered Implicit Method / S. M. McGovern AMS 65L05 1 Introduction To address needs in industry and research, enhanced numerical methods can be generated by the use of filters [ 5 ] . They can be applied before and after a “solve step” in many of the traditional numerical methods to create new, higher order methods [ 5 ] . The filtering steps tend to be only a few lines of code each, which is advantageous from an implementation standpoint. Additionally, the new filtered methods have favorable accuracy and stability properties despite the relative simplicity of the code changes. Ideas of this nature are presented in [ 4 ] [ 5 ] [ 6 ] [ 8 ] . Complex codes based on implicit methods in particular are common. They appear frequently in modern and legacy code bases. It has been shown that their accuracy can be increased through the use of filters while maintaining stability [ 4 ] . The focus of this paper is adaptive step selection for two novel filtered methods based on Implicit Euler from [ 4 ] that were presented with a constant step. The two methods are a natural embedded pair which makes them amenable to adaptive stepping. However, no variable step extension of the methods exists prior to this paper. We develop the variable step extension herein. For reference, the first constant step method from [ 4 ] is a second order Implicit Euler-based method with a pre-filter. The other constant step method is a third order Implicit Euler-based method with the same pre-filter, and then a post-filter added after the Implicit Euler solve. The constant step methods read as follows: Step 1) Pre-filter \displaystyle\tilde{y}_{n}=y_{n}-\frac{1}{2}(y_{n}-2y_{n-1}+y_{n-2}), Step 2) IE Solve \displaystyle\frac{y_{n+1}-\tilde{y}_{n}}{k}=f(t_{n+1},y_{n+1}), Step 3) Post-filter \displaystyle y_{n+1}^{3rd}=y_{n+1}-\frac{5}{11}(y_{n+1}-3y_{n}+3y_{n-1}-y_{n-2}). Completing Step 1) and Step 2) above yields the second order method. We will refer to it as IE-Pre-2. It is A-stable and L-stable [ 4 ] . Once Step 3) is added for post-filtering, then completing all three steps above yields the third order method. This third order method will be referred to as IE-Pre-Post-3. A-stability is lost after adding the post-filter step. However, IE-Pre-Post-3 is still A( \alpha ) stable with \alpha\approx 71.51^{\circ} (Section 4.1.3 of [ 4 ] ). The higher order method shares the same first two steps with the lower order method. This fact makes the two methods a natural embedded pair. The variable step extension derived in Section 3 is Step 1) Pre-filter \displaystyle\tilde{y}_{n}=y_{n} \displaystyle-\frac{\alpha_{n}}{2}\left(\frac{2k_{n-2}}{k_{n-1}+k_{n-2}}y_{n}-2y_{n-1}+\frac{2k_{n-1}}{k_{n-1}+k_{n-2}}y_{n-2}\right), Step 2) IE Solve \displaystyle\frac{y_{n+1}-\tilde{y}_{n}}{k_{n}}=f(t_{n+1},y_{n+1}), Step 3) Post-filter \displaystyle y^{3rd}_{n+1}=y_{n+1} \displaystyle-\beta_{n}\left(\frac{2k_{n-1}}{k_{n}+k_{n-1}}y_{n+1}-2y_{n}+\frac{2k_{n}}{k_{n}+k_{n-1}}y_{n-1}\right. \displaystyle-\left.\left(\frac{2k_{n-2}}{k_{n-1}+k_{n-2}}y_{n}-2y_{n-1}+\frac{2k_{n-1}}{k_{n-1}+k_{n-2}}y_{n-2}\right)\right). Above, \alpha_{n} and \beta_{n} are the pre-filter and post-filter coefficients, respectively. It is shown how to choose these filters for the requisite orders in Section 3 . The variables k_{n} , k_{n-1} and k_{n-2} are steps between values of t . Denote the value computed from Step 1) and Step 2) of the method as y^{2nd}_{n+1} and denote the value computed from Step 1), Step 2) and Step 3) of the complete method as y^{3rd}_{n+1} . Then we can use \displaystyle EST=|y^{3rd}_{n+1}-y_{n+1}^{2nd}| as an estimator of the error at Step 2). We use this error estimator, along with techniques to minimize discrete curvature from [ 8 ] , to derive the filters and construct the variable time step method above. The new method we call Filtered-IE23. This adaptive numerical method is implemented with the simplest controller, halving and doubling, since the focus is on the estimator. The paper is organized as follows. Background is presented in Section 2 , the main results concerning the derivation of the new adaptive pre-filter and post-filter are in Section 3 , the algorithm for a halving and doubling scheme is given in Section 4 , numerical results are in Section 5 , and the conclusions follow in Section 6 . 2 Background We follow the definition of discrete curvature presented in [ 8 ] , pages 7-8. Briefly, we find the Lagrange interpolating polynomial for y_{n+1} , y_{n} and y_{n-1} . Call this quadratic interpolant \phi(t) . We have \displaystyle\phi(t) \displaystyle=y_{n+1}\ell_{n+1}(t)+y_{n}\ell_{n}(t)+y_{n-1}\ell_{n-1}(t) \displaystyle=y_{n+1}\frac{(t-t_{n-1})(t-t_{n})}{(t_{n+1}-t_{n-1})(t_{n+1}-t_{n})}+y_{n}\frac{(t-t_{n-1})(t-t_{n+1})}{(t_{n}-t_{n-1})(t_{n}-t_{n+1})} \displaystyle+y_{n-1}\frac{(t-t_{n})(t-t_{n+1})}{(t_{n-1}-t_{n})(t_{n-1}-t_{n+1})}. Differentiate twice with respect to t to find the discrete second difference, which is \displaystyle\phi^{\prime\prime}(t) \displaystyle=\frac{2}{(t_{n+1}-t_{n-1})(t_{n+1}-t_{n})}y_{n+1}+\frac{2}{(t_{n}-t_{n-1})(t_{n}-t_{n+1})}y_{n} \displaystyle+\frac{2}{(t_{n-1}-t_{n})(t_{n-1}-t_{n+1})}y_{n-1}. Denote k_{n} as the time step between t_{n} and t_{n+1} and denote k_{n-1} as the time step from t_{n-1} to t_{n} . Then we have \displaystyle\phi^{\prime\prime}(t) \displaystyle=\frac{2}{(k_{n-1}+k_{n})k_{n}}y_{n+1}+\frac{2}{k_{n-1}(-k_{n})}y_{n}+\frac{2}{(-k_{n-1})(-(k_{n}+k_{n-1}))}y_{n-1}. Curvature \kappa_{n} , as defined in [ 8 ] , is then \phi^{\prime\prime}(t) scaled by k_{n-1}k_{n} . So \displaystyle\kappa_{n} \displaystyle=k_{n-1}k_{n}\phi^{\prime\prime}=\frac{2k_{n-1}}{k_{n}+k_{n-1}}y_{n+1}-2y_{n}+\frac{2k_{n}}{k_{n}+k_{n-1}}y_{n-1}. Similar ideas are presented in [ 9 ] [ 14 ] . The underlying idea for both the constant and variable step method is Step 1) Pre-filter \displaystyle\tilde{y}_{n}=y_{n}-\frac{\alpha_{n}}{2}\kappa_{n-1}, Step 2) IE Solve \displaystyle\frac{y_{n+1}-\tilde{y}_{n}}{k_{n}}=f(t_{n+1},y_{n+1}), Step 3) Post-filter \displaystyle y^{3rd}_{n+1}=y_{n+1}-\beta_{n}(\kappa_{n}-\kappa_{n-1}). In both cases, \alpha_{n} and \beta_{n} are chosen accordingly for 2nd and 3rd order. The pre-filter is the Robert-Asselin filter [ 2 ] [ 13 ] . The post-filter is a higher-order Robert-Asselin-type time filter, presented in [ 11 ] . Note that in the constant step case, we have k_{n}=k_{n-1}=k_{n-2}=k and thus the curvatures at steps n-1 and n simplify to \displaystyle\kappa_{n-1} \displaystyle=y_{n}-2y_{n-1}+y_{n-2}\,\,\,\text{and}\,\,\,\kappa_{n}=y_{n+1}-2y_{n}+y_{n-1}. Then \kappa_{n-1} scaled by the pre-filter coefficient is found in Step 1) of the constant step method in Section 1 . Likewise, \displaystyle\kappa_{n}-\kappa_{n-1}=y_{n+1}-3y_{n}+3y_{n-1}-y_{n-2} is scaled by the post-filter coefficient in Step 3) of the constant step method. 3 Main Results Now that the background is in place, we show how to derive the adaptive pre-filter and post-filter for the desired orders. We use direct Taylor expansions to determine the pre-filter \alpha_{n} for second order and an alternative method to find the post-filter \beta_{n} for third order. 3.1 Adaptive Step Pre-filter Consider the first two steps of adaptive method Filtered-IE23 from Section 1 . We must choose \alpha_{n} so that Step 1) and Step 2) yield a second order method. Proposition 1 . The value for the pre-filter \alpha_{n} which gives a second order adaptive method after completing Step 1) and Step 2) is \displaystyle\alpha_{n}=\frac{k_{n}^{2}}{k_{n-1}k_{n-2}}. Proof. The strategy is to construct the equivalent multistep method, Taylor expand around each of the terms and choose \alpha_{n} accordingly. Consider Step 1) and Step 2): \displaystyle\tilde{y}_{n}=y_{n}-\frac{\alpha_{n}}{2}\left(\frac{2k_{n-2}}{k_{n-1}+k_{n-2}}y_{n}-2y_{n-1}+\frac{2k_{n-1}}{k_{n-1}+k_{n-2}}y_{n-2}\right), \displaystyle\frac{y_{n+1}-\tilde{y}_{n}}{k_{n}}=f(t_{n+1},y_{n+1}). Substitute the pre-filtered value from Step 1) into the Implicit Euler solve in Step 2), gather terms and simplify: \displaystyle y_{n+1}-\left(y_{n}-\frac{\alpha_{n}}{2}\left(\frac{2k_{n-2}}{k_{n-1}+k_{n-2}}y_{n}-2y_{n-1}+\frac{2k_{n-1}}{k_{n-1}+k_{n-2}}y_{n-2}\right)\right) \displaystyle=k_{n}f(t_{n+1},y_{n+1}),\,\,\,\text{or} \displaystyle y_{n+1}+\frac{(\alpha_{n}-1)k_{n-2}-k_{n-1}}{k_{n-1}+k_{n-2}}y_{n}-\alpha_{n}y_{n-1}+\frac{\alpha_{n}k_{n-1}}{k_{n-1}+k_{n-2}}y_{n-2}-k_{n}(y^{\prime})_{n+1} \displaystyle=0. Taylor expand around each of the terms: \displaystyle y_{n+1} \displaystyle=y_{n+1}, \displaystyle\frac{(\alpha_{n}-1)k_{n-2}-k_{n-1}}{k_{n-1}+k_{n-2}}y_{n} \displaystyle=\frac{(\alpha_{n}-1)k_{n-2}-k_{n-1}}{k_{n-1}+k_{n-2}}y_{n+1}-\frac{(\alpha_{n}-1)k_{n-2}-k_{n-1}}{k_{n-1}+k_{n-2}}k_{n}y^{\prime} \displaystyle+\frac{((\alpha_{n}-1)k_{n-2}-k_{n-1})}{k_{n-1}+k_{n-2}}\frac{k_{n}^{2}}{2}y^{\prime\prime}+\mathcal{O}(k_{n}^{3}), \displaystyle-\alpha_{n}y_{n-1} \displaystyle=-\alpha_{n}y_{n+1}+\alpha_{n}(k_{n}+k_{n-1})y^{\prime} \displaystyle-\alpha_{n}\frac{(k_{n}+k_{n-1})^{2}}{2}y^{\prime\prime}+\mathcal{O}((k_{n}+k_{n-1})^{3}), \displaystyle\frac{\alpha_{n}k_{n-1}}{k_{n-1}+k_{n-2}}y_{n-2} \displaystyle=\frac{\alpha_{n}k_{n-1}}{k_{n-1}+k_{n-2}}y_{n+1}-\frac{\alpha_{n}k_{n-1}}{k_{n-1}+k_{n-2}}(k_{n}+k_{n-1}+k_{n-2})y^{\prime} \displaystyle+\frac{\alpha_{n}k_{n-1}}{k_{n-1}+k_{n-2}}\frac{(k_{n}+k_{n-1}+k_{n-2})^{2}}{2}y^{\prime\prime} \displaystyle+\mathcal{O}((k_{n}+k_{n-1}+k_{n-2})^{3}), \displaystyle-k_{n}(y^{\prime})_{n+1} \displaystyle=-k_{n}y^{\prime}. For a second order method, \alpha_{n} must be chosen so that the y_{n+1} , y^{\prime} and y^{\prime\prime} terms sum to zero. Sum the coefficients on the y_{n+1} terms and we have: \displaystyle 1+\frac{(\alpha_{n}-1)k_{n-2}-k_{n-1}}{k_{n-1}+k_{n-2}}+(-\alpha_{n})+\frac{\alpha_{n}k_{n-1}}{k_{n-1}+k_{n-2}}=0. This is zero regardless of the choice of \alpha_{n} . Similarly, sum the coefficients on the y^{\prime} terms: \displaystyle-\frac{(\alpha_{n}-1)k_{n-2}-k_{n-1}}{k_{n-1}+k_{n-2}}k_{n}+\alpha_{n}(k_{n}+k_{n-1}) \displaystyle-\frac{\alpha_{n}k_{n-1}}{k_{n-1}+k_{n-2}}(k_{n}+k_{n-1}+k_{n-2})-k_{n}=0. This is also trivially zero.