href="#fb3_img_img_851ecd6a-39f5-5579-ae0d-fe5a19c546c5.png" alt="u Subscript n plus 1 Baseline equals u Subscript n Baseline plus StartFraction k Over 2 EndFraction left-bracket f left-parenthesis t Subscript n Baseline comma u Subscript n Baseline right-parenthesis plus f left-parenthesis t Subscript n plus 1 Baseline comma u Subscript n plus 1 Baseline right-parenthesis right-bracket n equals 0 comma ellipsis comma upper N minus 1"/>
where is non-linear. Here see that the unknown term u is on both the left- and right-hand sides of the equation, and hence it is not possible to solve the problem explicitly in the way that we did for the linear case. However, not all is lost, and to this end we introduce the predictor-corrector method that consists of a set consisting of two difference schemes; the first equation uses the explicit Euler method to produce an intermediate solution called a predictor that is then used in what could be called a modified trapezoidal rule:
(2.30)
The predictor-corrector is used in practice; it can be used with non-linear systems and stochastic differential equations (SDE). We discuss this topic in Chapter 13.
2.4.3 Extrapolation
We give an introduction to a technique that allows us to improve the accuracy of finite difference schemes. This is called Richardson extrapolation in general. We take a specific case to show the essence of the method, namely the implicit Euler method (2.11). We know that it is first-order accurate and that it has good stability properties. We now apply the method on meshes of size k and k/2, and we can show that the approximate solutions can represented as follows:
Then:
Thus, is a second-order approximation to the solution of (2.1).
The constant is independent of , and this is why we can eliminate it in the first equations to get a scheme that is second-order accurate. The same trick can be employed with the second-order Crank–Nicolson scheme to get a fourth-order accurate scheme as follows:
Then:
In general, with extrapolation methods we state what accuracy we desire, and the algorithm divides the interval into smaller subintervals until the difference between the solutions on consecutive meshes is less than a given tolerance.
A thorough introduction to extrapolation techniques for ordinary and partial differential equations (including one-factor and multifactor parabolic equations) can be found in Marchuk and Shaidurov (1983).
2.5 FOUNDATIONS OF DISCRETE TIME APPROXIMATIONS
We discuss the following properties of a finite difference approximation to an ODE:
Consistency
Stability
Convergence.
These topics are also relevant when we discuss numerical methods for partial differential equations.
In order to reduce the scope of the problem (for the moment), we examine the simple scalar non-linear initial value problem (IVP) defined by:
We assume that this system has a unique solution in the interval . In general it is impossible to find an exact solution of Equation (2.31), and we resort to some kind of numerical scheme. To this end, we can write a generic -step method in the form (Henrici (1962), Lambert (1991)):
