1
$\begingroup$

This question is not homework it is recommended exercises to prepare for the final exam.

Consider the family of linear one-step methods defined by $$y_n = y_{n-1} + h(\theta f_n + (1 - \theta)f_{n-1})$$ where $0\leq \theta \leq 1$.

2) For what values of $\theta$ in the interval $0\leq \theta \leq 1$ is the associated method convergent?

Attempted proof:

Let's first prove convergence of forward Euler i.e. when $\theta = 0$, the forward Euler method says that $$u_{n+1} = u_n + hf(t_n,u_n)$$ and Taylor expansion with remainders of each component gives $$ y_j(t_{n+1}) = y_j(t_n) + hf_j(t_n,y(t_n)) + \frac{1}{2}h^2y_j''(t_n + \theta_j h)$$ $$= y_j(t_n) + hf_j(t_n,y(t_n)) + h\tau_{nj}$$ for some unknown collection of numbers $\theta_j$ between $0$ and $1$. This defines the local truncation error $\tau_n$, the amount by which the exact solution $y$ fails to satisfy the method after one step. Subtraction gives a difference equation for the error $$e_{n+1} = u_{n+1} - y(t_{n+1}) = e_n + h[f(t_n,u_n) - f(t_n,y(t_n))] + h\tau_n$$ Assume $f$ is Lipschitz constant $L$ and the local truncation error satisfies a bound $$||\tau_n|| \leq \tau$$ for all $n$ (which depends on the exact solution) then $$||e_{n+1}|| \leq ||e_n|| + hL||e_n|| + h\tau = (1 + hL)||e_n||+ h \tau$$
$$\leq (1 + hL)^{2}||e_{n-1}|| + (1 + (1 + hl))h\tau $$ $$\leq \ldots$$ $$\leq (1 + hL)^{n+1}||e_0|| + \frac{(1 + hL)^{n+1} - 1}{(1 + hL) - 1}h\tau$$ since $(1 + hL) \leq e^{hL} = 1 + hL + \frac{1}{2}(hL)^2 + \ldots$, this gives $$||e_n|| \leq e^{nhL}||e_0|| + \frac{1^{nhL} - 1 }{hL}\tau \leq e^{LT}||e_0|| + \frac{e^{LT} - 1}{L}\tau$$ for $0\leq t_n = nh\leq T$. This shows stability. Now the local truncation error satisfies $$h||\tau_n|| = ||\frac{1}{2}h^2y'(t_n + \theta_n h)|| \leq \frac{1}{2}Mh^2$$ assuming $y$ is $C^2$ and $||y''|| \leq u$. Consistency gives a local bound on $\tau$ and stability allows us to conclude convergence $$|u_n - y(t_n)|| \leq e^{LT}||u_0 - y_0|| + \frac{e^{LT} - 1}{LT}\frac{T}{2}Mh \leq O(|u_0 - y_0|) + O(h)$$ Convergence implies that $u_n\rightarrow y_n$ on the whole interval $[0,T]$ as $h\rightarrow 0$ and $u_0\rightarrow y_0$. A similar proof can be done for any one-step method. A little extra work is required for implicit methods such as implicit Euler $$u_{n+1} = u_n + hf(t_{n+1},u_{n+1})$$ because the right hand side depends on the new unknown $u_{n+1}$. Assume you can solve the implicit equation for $u_{n+1}$ at each step so we can estimate the errors as for explicit Euler $$||e_{n+1}|| \leq e_n + hL||e_{n+1}|| + h||\tau_n||$$ collect each terms on the left, and for $hL \leq \frac{1}{2}$ we can then divide by $1 - hL$ to get $$||e_{n+1}|| \leq \frac{1}{1 - hL}(||e_n|| + h||\tau_n||)$$ using the additional inequality $$\frac{1}{1 - hL}\leq 1 + 2hL \ \ \text{for} \ \ hL \leq 1/2$$ gives stability as for Euler's method, and the consistency computation follows.

$\endgroup$
  • 1
    $\begingroup$ Part 2 is not a trivial thing to prove. I'd suggest you start by proving convergence of the forward Euler method ($\theta = 1$); then, following the same argument, you can derive a more general result (error bound) for the general case $\theta \in [0,1]$. Hint: the methods are convergent (and first order accurate) for all $\theta \in [0,1]$. For $\theta = 1/2$, the resulting Trapezoidal rule is second order accurate. $\endgroup$ – GoHokies Nov 26 '15 at 16:35
  • 2
    $\begingroup$ Possible duplicate of Family of linear one-step methods $\endgroup$ – Kirill Nov 26 '15 at 17:30
  • 1
    $\begingroup$ @Kirill: It's not a duplicate, the actual question is #2 below. Morgan, you don't need to copy your solution to your previous question here, it's irrelevant (and, as you can see, confusing). $\endgroup$ – Christian Clason Nov 26 '15 at 18:15
  • $\begingroup$ Ok, I understand. so essentially I need to prove convergence for the three methods i.e. forward Euler, backward Euler, and the Trapezoidal rule and then from there prove convergence for the general case? $\endgroup$ – Wolfy Nov 26 '15 at 19:23
  • $\begingroup$ Prove convergence for $\theta=1$ (forward Euler). Then repeat that same argument for general $\theta$. $\endgroup$ – GoHokies Nov 27 '15 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.