# Order of predictor-corrector method.

Consider the following initial value problem $$\begin{cases} x'(t) = f(t,x(t)), \; t \in [t_0, T]\\ x(t_0) = \mu_0 \end{cases}$$ where $f \in \mathcal{C}\left([t_0, T] \times \mathbb{R}^n;\mathbb{R}^n \right)$ and is lipschitz on the second variable with Lipschitz's constant $L >0$. Given $n \in \mathbb{N}$, consider the net of nodes $t_i = t_0 + ih$ for $i = 0,1,\dots , N$ where $h = \frac{T-t_0}{N}$

Now consider the predictor-corrects method $P(EC)E$ where the predictor is the modified Euler Method $$x_{i+1} = x_i + hf\left( t_i + \frac{h}{2}, x_i + \frac{h}{2}f(t_i,x_i)\right)$$ and the corrector is the two step Adams- Moulton Method given by $$x_{i+2} = x_{i+1} + \frac{h}{12}\left( 5f_{i+2} + 8f_{i+1} - f_i \right)$$ where $f_{i+k} = f(t_{i+k}, x_{i+k})$

Show that the order of the resultant predictor-corrector method is $3$.

Now, I've already shown that the Adam-Mouton's Method has order $3$, and that Euler's modifies method has order two. Now there's a Theorem which barely says that

If I have two methods, both linear multistep methods of orders $p$ and $p^*$, the resultant predictor-corrector method taking as the predictor the method of order $p$ and the corrector the method of order $p^+$ has order $$\overline{p}=\min \{p,p^*\}$$

However, Euler's modified method is a Runge-Kutta method and therefore I don't think this theorem applies. My question is

How do I find the order of the method?

• You could consider the method as a semi-implicit one-step method for $\Delta t=2h$ with tableau $$\begin{array}{c|ccc}0&&&\\\frac12&\frac12&&\\1&-\frac1{24}&\frac56&\frac{5}{24}\\\hline&-\frac1{24}&\frac56&\frac{5}{24}\end{array}$$ and check its order conditions. – Dr. Lutz Lehmann Jun 12 '17 at 14:05
• I'm sorry but I don't know how did you get that tableau. For the Euler method I know how to get it, but I don't know much about semi-implicit methods... – user313212 Jun 12 '17 at 16:49
• It just means in this case that the equation for $k_3=Δt·f(t+Δt, x+...+\frac5{24}k3)$ depends non-linearly or implicitly on $k_3$ itself, which is natural since that is the part of the implicit corrector in the scheme. -- In this interpretation, your method is 2-periodic, $x_{2k+1}$ is always determined by the improved Euler method, $x_{2k+2}$ by the Adams- Moulton method. Is that correct? – Dr. Lutz Lehmann Jun 12 '17 at 16:55
• I may have mixed up the halves and quarters. More explicitly, the interpretation as one-step method computes $k_1=Δt⋅f(t,x)$, $k_2=Δt⋅f(t+\frac14Δt, x+\frac14k_1)$, $x_{+1}=x+\frac12k_2$, $k_3= Δt⋅f(t+\frac12Δt, x+\frac12k_2)$, $x_{+2}=x_{+1}+\frac1{24}(5k_4+8k_3-k_1)$ where $k_4=Δt⋅f(t+Δt,x_{+2})$. Thus one gets a 4-stage method with tableau \begin{array}{c|cccc}0&&&&\\\frac14&\frac14&&&\\\frac12&&\frac12&\\1&-\frac1{24}&\frac12&\frac13&\frac{5}{24}\\\hline&-\frac1{24}&\frac12&\frac13&\frac{5}{24}\end{array} – Dr. Lutz Lehmann Jun 12 '17 at 17:10
• Thank you. I'm trying to understand but I still don't see why is that. Maybe I'm not familiar with the notation you are using or something. Are you saying that my step $h$ should now be $2h$? Maybe I should review this whole predictor-corrector methods again and come back to this later. – user313212 Jun 12 '17 at 17:30

Compare to the exact solution $x(t)$ of the ODE going through the initial point $(t_i,x_i)$.
The improved Euler step then relates to the exact ODE solution as $$x_{i+1}=x(t_{i+1})+O(h^3)$$ and thus also $$f_{i+1}=f(t_{i+1},x_{i+1})=x'(t_{i+1})+O(h^3).$$
The error of the Adams-Moulton step is $$x(t_{i+2})=x(t_{i+1})+\frac{h}{12}(5x'(t_{i+2})+8x'(t_{i+1})-x'(t_i))+O(h^4)$$ Replacing $x'(t_{i+1})$ with $f_{i+1}$ only adds another $h·O(h^3)=O(h^4)$ error term. As we know that $x(t_{i+2})$ nearly solves the fixed-point equation for $x_{i+2}=X$, $$X=C+\frac{5h}{12}f(t_{i+2},X),\qquad C=x_{i+1}+\frac{h}{12}(8f_{i+1}-f_i)$$ with an error $O(h^4)$, by the implicit function theorem or more basically the Banach fixed point theorem, the exact solution of the Adams-Moulton step also only has distance of $O(h^4)$ to $x(t_{i+2})$.
This local $O(h^4)$ error translates into a global $O(h^3)$ error, thus giving the order of the method as $3$.