Parareal

Remarks

The proof is an induction on $k$. For $k = 0$ only $n = 0$ is concerned, and $U_0^0 = y_0 = Y_0$. If the claim holds for $k$, then $U_0^{k+1} = Y_0$, and if $U_n^{k+1} = Y_n$ with $n \le k$, then also $U_n^k = Y_n$, so the iteration gives $U_{n+1}^{k+1} = \mathcal{G}_n(Y_n) + \mathcal{F}_n(Y_n) - \mathcal{G}_n(Y_n) = Y_{n+1}$. The result needs no property of $\mathcal{F}_n$ and $\mathcal{G}_n$; it guarantees termination but no speed-up. In practice the iteration is stopped after $K$ iterations with $K$ much smaller than $N$, when $\mathcal{G}_n$ is accurate and stable enough for the iterates to converge fast.

Going deeper

For a student

The expensive fine solves $\mathcal{F}_n(U_n^k)$ for all $n$ are independent, so they run in parallel; only the coarse sweep is sequential. The parallel speed-up is bounded by about $N/K$, so the method pays off only when it converges in few iterations. It works well for diffusive problems and less well for hyperbolic or highly oscillatory ones. Parareal can be seen as a multiple shooting method in which a Newton step is approximated with the coarse propagator.