This page is based on reviews done by [Ong22, Skeel82] with additional elements from other contributions.
In the 1940's, using an inspiration from "relaxation methods" used for simultaneous algebraic equations, Fox introduced a "difference correction method" [Fox47] intending to solve ordinary and partial differential equations. Noting that derivatives are infinite series of differences, such that truncated version of those series are simply finite-difference approximations, Fox uses approximations of different orders to estimate a correction term allowing to improve the accuracy of a first approximate solution. Its method is later called "Deferred Correction" (DC), and its correction term turns out to be an estimate of the locale discretization error [Skeel82]. The main advantage of this method is to "allow an improvement of the accuracy of finite-difference solutions without increasing the complexity of the algebraic systems required for the solution" [Ong22]. But its main default lays on the use of high-order finite differences to compute the correction term, which requires solution values outside of the domain of integration and is prone to non-negligible round-off errors with equi-spaced grids.
While [Fox47] uses DC for Boundary Value Problem (BVP) and eigenvalue problems linked to ODE, the approach was applied for Initial Value Problem (IVP) in [Fox49]. Additionnaly, Pereyra generalized DC to functionnal equations in [Pereyra66] and applied it to specific types of BVPs in [Pereyra68]. A decade after, Skeel credited Pereyra for a renewed perspective on DC methods, as he was "the first to put the deferred correction procedure into a general and mathematically rigorous setting" and his "theoretical and practical contributions did much to revive interest in the idea" [Skeel82]. Even if DC methods where usually referred to "Fox and Pereyra" method at that time, we can also mention a similar contribution of [Hausman47] who introduced a DC-like method with a different approach to estimate the correction term. Finally, a proper definition of DC was given by Mayers in the book of Fox [Fox62] :
"An alternative method, of deferred correction, uses approximate formulae to find a first approximation to the required solution in the complete range of integration. The local truncation errors are assessed from this approximation and included in a correcting run, which again is repeated as often as necessary."
With the main theoretical basis brought by Pereyra, many contributions were added to the field of DC methods. Zadunaisky considered in [Zadunaisky66] an alternative DC method mentionned as "defect correction", where the correction term does not include the computation of local truncation error, but requires an interpolation of the numerical solution. Those interpolations are prone to numerical problem for large equi-spaced grids and solved using a decomposition into several interpolation intervals [Zadunaisky76]. This idea was generalized by [Stetter74] who consider adding error approximation to the numerical solution to form a new one. Its algorithm was referred later as "Classical Deferred Correction" [Ong22], and motivated extended analysis from [Lindberg76, Frank77a] as long as new variation of DC methods, e.g with [Frank76, Frank77b]. Skeel also brought its contributions, along with a thorough review of the different DC approaches at that time [Skeel82]. All those developments were mostly focused on proving the convergence of each DC flavours, as well as searching for more efficient technics to compute the error correction term, or "defect".
DC methods have been since then applied to many types of problem, among them :
- Ordinary Differential Equations
- Initial Value Problems : [Fox49, Dutt00, Hansen11, Christlieb09, Christlieb10a, Christlieb10b]
- Boundary Value Problems : [Fox47, Pereyra66, Pereyra68]
- Partial Differential Equations : [Fox47, Kress02, Rangan03]
- Differential-Algebraic Equations : [Huang06, Rangan03]
- Eigenvalue problems : [Fox49, Chu81]
They have also be used in conjunction with :
- linear multistep methods : [Geng85]
- Krylov subspace methods : [Huang06, Bu12]
- splitting methods : [Hansen11]
Usually, interpolation is done in DC methods using Lagrange polynomials, which appears to be the most classical approach. The use of rational functions for interpolant were also considered by [Güttel13], as well as continuous extensions and splines in [Ong22].
🛠️ In construction ...
🛠️ In construction ...
[Ong22] Ong, B. W., & Spiteri, R. J. (2020). Deferred correction methods for ordinary differential equations. Journal of Scientific Computing, 83(3), 1-29.
[Fox47] Fox, L. (1947). Some improvements in the use of relaxation methods for the solution of ordinary and partial differential equations. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 190(1020), 31-59.
[Skeel82] Skeel, R. D. (1982). A theoretical framework for proving accuracy results for deferred corrections. SIAM Journal on Numerical Analysis, 19(1), 171-196
[Fox49] Fox, L., & Goodwin, E. T. (1949, July). Some new methods for the numerical integration of ordinary differential equations. In Mathematical Proceedings of the Cambridge Philosophical Society (Vol. 45, No. 3, pp. 373-388). Cambridge University Press.
[Fox62] Fox, L. (1962). Numerical solution of ordinary and partial differential equations: based on a summer school held in Oxford, August-September 1961. Pergamon Press, Oxford.
[Pereyra66] Pereyra, V. (1966). On improving an approximate solution of a functional equation by deferred corrections. Numerische Mathematik, 8(4), 376-391.
[Pereyra68] Pereyna, V. (1968). Iterated deferred corrections for nonlinear boundary value problems. Numerische Mathematik, 11(2), 111-125.
[Hausman47] Hausman, L. F., & Schwarzschild, M. (1947). Automatic Integration of Linear Sixth‐Order Differential Equations by Means of Punched‐Card Machines. Review of Scientific Instruments, 18(12), 877-883.
[Zadunaisky66] Zadunaisky, P. E. (1966). A method for the estimation of errors propagated in the numerical solution of a system of ordinary differential equations. In The Theory of Orbits in the Solar System and in Stellar Systems (Vol. 25, p. 281).
[Zadunaisky76] Zadunaisky, P. E. (1976). On the estimation of errors propagated in the numerical integration of ordinary differential equations. Numerische Mathematik, 27(1), 21-39.
[Stetter74] Stetter, H. J. (1974). Economical global error estimation. In Stiff differential systems (pp. 245-258). Springer, Boston, MA.
[Lindberg76] Lindberg, B. (1976). Error Estimation and Iterative Improvement for the Numerical Solution of Operator Equations. ILLINOIS UNIV AT URBANA-CHAMPAIGN DEPT OF COMPUTER SCIENCE.
[Frank76] Frank, R., Hertling, J., & Ueberhuber, C. W. Iterated Defect Correction based on Estimates of the Local Discretization Error Report Nr. 18/76, Inst. f. Num. Math. Technical University of Vienna.
[Frank77a] Frank, R., Hertling, J., & Ueberhuber, C. W. (1977). An extension of the applicability of iterated deffered corrections. Mathematics of Computation, 31(140), 907-915.
[Frank77b] Frank, R., & Ueberhuber, C. W. (1977). Iterated defect correction for the efficient solution of stiff systems of ordinary differential equations. BIT Numerical Mathematics, 17(2), 146-159.
[Güttel13] Güttel, S., & Klein, G. (2013). Efficient high-order rational integration and deferred correction with equispaced data.
[Christlieb09] Christlieb, A., Ong, B., & Qiu, J. M. (2009). Comments on high-order integrators embedded within integral deferred correction methods. Communications in Applied Mathematics and Computational Science, 4(1), 27-56.
[Christlieb10a] Christlieb, A., Ong, B., & Qiu, J. M. (2010). Integral deferred correction methods constructed with high order Runge–Kutta integrators. Mathematics of Computation, 79(270), 761-783.
[Christlieb10b] Christlieb, A. J., Macdonald, C. B., & Ong, B. W. (2010). Parallel high-order integrators. SIAM Journal on Scientific Computing, 32(2), 818-835.
[Dutt00] Dutt, A., Greengard, L., & Rokhlin, V. (2000). Spectral deferred correction methods for ordinary differential equations. BIT Numerical Mathematics, 40(2), 241-266.
[Hansen11] Hansen, A. C., & Strain, J. (2011). On the order of deferred correction. Applied numerical mathematics, 61(8), 961-973.
[Kress02] Kress, W., & Gustafsson, B. (2002). Deferred correction methods for initial boundary value problems. Journal of scientific computing, 17(1), 241-251.
[Rangan03] Rangan, A. V. (2003). Adaptive solvers for partial differential and differential-algebraic equations. University of California, Berkeley (PhD Thesis).
[Huang06] Huang, J., Jia, J., & Minion, M. (2006). Accelerating the convergence of spectral deferred correction methods. Journal of Computational Physics, 214(2), 633-656.
[Chu81] Chu, K. W., & Spence, A. (1981). Deferred correction for the integral equation eigenvalue problem. The ANZIAM Journal, 22(4), 474-487.
[Geng85] Geng, S. (1985). The deferred correction procedure for linear multistep formulas. Journal of Computational Mathematics, 41-49.
[Bu12] Bu, S., Huang, J., & Minion, M. (2012). Semi-implicit Krylov deferred correction methods for differential algebraic equations. Mathematics of Computation, 81(280), 2127-2157.