Deferred correction and collocation iterations — Examples

With $K=0$, the algorithm evaluates and stores the $M$ predictor derivatives, then returns iteration-budget-exhausted without an accepted endpoint. If the run stops after $s>0$ completed sweeps with no incomplete sweep, each adds exactly $M$ evaluations because its $M$ new stage states are evaluated once and the previous $F(U^j)$ values are reused. Thus the total is $M+sM=M(s+1)$, and for $s\le K$ this is at most $M(K+1)$, attained if all $K$ sweeps complete. A failed run with a partially evaluated sweep is counted by its actual prefix as in [F2], and still obeys that bound. Acceptance after $s\ge 1$ sweeps returns $U^{s-1}$ and uses its cached endpoint derivatives with no additional calls.

The stored dense matrices $Q,Q_{\mathrm{\Delta }}$ each have $M^2$ real entries, so their storage is $O(M^2)$; retaining old/current stage vectors and their derivative values takes $O(Md)$ additional scalar storage. Each forward-recursion stage has two sums with at most $2M$ vector terms in total, for at most $O(M^{2}d)$ scalar arithmetic per sweep. Residual formation adds $O(Md)$ scalar arithmetic and at most $M$ square roots; an accepted endpoint adds $O(Md)$ arithmetic and no new field evaluations. These are the proved counts in [F2]. They omit the cost of evaluating $f$, constructing the polynomial quadrature data (which depends on their representation), supplied predictor generation, and external admissibility/invariance certification and their internal storage. The model uses exact real arithmetic and gives no floating-point roundoff guarantee.

Here $z=h\lambda =-6$, so [F3] and [F1] under [A1] give $B(-6)=(-6)(1\mathrm{/}2)=-3$. The collocation stage is $U^{\ast }=1-3U^{\ast }$, hence $U^{\ast }=1\mathrm{/}4$. The constant predictor is $U^0=1$, so $E^0=3\mathrm{/}4\mathrm{\ne }0$ and $E^k=(-3{)}^k(3\mathrm{/}4)$ by induction; its magnitude grows by a factor $3$ at every sweep.

The exactly solved endpoint is $1-6(1\mathrm{/}4)=-1\mathrm{/}2$, which is also the midpoint stability factor $(1+z\mathrm{/}2)\mathrm{/}(1-z\mathrm{/}2)=-1\mathrm{/}2$ multiplying the initial value. Its magnitude is below one, while the SDC contraction ratio from the scalar matrix is $\mathrm{\mid }z\mathrm{\mid }\mathrm{/}2=3>1$. Thus stability of the fully solved midpoint step does not imply convergence of the explicit SDC iteration, and the contraction theorem correctly makes no claim here.

The integrand $s^3$ has degree three, so [F1] gives ${\sum }_{j=1}^2{w}_j{c}_j^3={\int }_0^1{s}^{3}d\lambda$. The matching of weights in [F5] and agreement with the Riemann integral in [F3] give ${\sum }_{j=1}^2{b}_j{c}_j^3={\int }_0^1{s}^{3}ds$. The stages solve $U_i={\sum }_j{Q}_{ij}{c}_j^3$ and are well-defined finite real numbers because $f$ does not depend on $U$. The rule data are valid by [F4] and the axiom premise in the Example.

The IVP identity [F6] and the scalar FTC [F3] give $y(s)=s^4\mathrm{/}4$, hence $y(1)=1\mathrm{/}4$. Step 1.1 gives the same collocation endpoint, so the one-step endpoint is exact despite the fact that the collocation polynomial need not equal the exact path at interior points.

Let the common state tube be $[0,2e]$ and take the time-fiber start sets ${\mathcal{U}}_n=[1,e]$; the field $f(t,y)=y$ is bounded there by $B=2e$ and is $1$-Lipschitz. For every start $u\in {\mathcal{U}}_n$, use the one-stage closed product ball ${\mathcal{C}}_u=[0,2u]$, which contains the constant predictor $U^0=u$. By [F12], for $V\in {\mathcal{C}}_u$ the inner/outer sweep map is $S_u(V)=u+(h\mathrm{/}2)V$, whose values lie in $[u,u+hu]\subseteq [u,2u]\subseteq {\mathcal{C}}_u$ when $0<h\le 1$. The contraction constants are $a=0$ and $q=h\mathrm{/}2\le 1\mathrm{/}2$, with $q=(1\mathrm{/}2)h$. Thus [F13] supplies the unique local collocation branch in ${\mathcal{C}}_u$, uniformly for the start states used in the stability comparison. Now induct on the mesh index. If all earlier checks passed, then $y_n=(1+h{)}^n>0$; for $nh\le 1$, [F6] gives $(1+h{)}^n\le \exp (nh)$ and [F11] gives $\exp (nh)\le e$, so $y_n\in {\mathcal{U}}_n$ and the stage set hypotheses just verified apply. The first sweep value is $U^1=y_n+(h\mathrm{/}2)y_n$, with update residual $r_0=h\mathrm{\mid }{y}_n\mathrm{\mid }\mathrm{/}2\le eh\mathrm{/}2$. For sufficiently small $h$, $eh\mathrm{/}2\le 1-h\mathrm{/}2=(1-q)\mathrm{t}\mathrm{o}\mathrm{l}$, so [F1] returns $U^0$ after the first check and the endpoint is $y_{n+1}=(1+h)y_n$. This closes the induction for every step.

Let $y$ be any exact IVP solution. By [F8]–[F9], $z(t)=\exp (-t)y(t)$ has derivative $z^{\mathrm{\prime }}(t)=-\exp (-t)y(t)+\exp (-t)y^{\mathrm{\prime }}(t)=0$. [F10] on each interval $[0,t]$ gives $z(t)=z(0)=1$; the addition formula [F9] then gives $y(t)=\exp (t)$ and in particular $y(1)=e$. Thus the exact grid states also lie in ${\mathcal{U}}_n=[1,e]$. On a step starting at $t_n$, the exact-path integrand is $g_h(s)=e^{t_n+hs}$, so $g_h^{\mathrm{\prime }}(s)=h{e}^{t_n+hs}$ and $\mathrm{\parallel }{g}_h^{\mathrm{\prime }}{\mathrm{\parallel }}_{\mathrm{\infty }}\le eh$ for $0\le t_n+hs\le 1$. This verifies the $M=1$ exact-path derivative premise in [F14].

The computed final value is $(1+1\mathrm{/}N{)}^N$. For $N\ge 2$, [F7] gives its $j$th coefficient as $\left(\genfrac{}{}{0px}{}{N}{j}\right)N^{-j}=\frac{1}{j!}{\prod }_{r=0}^{j-1}(1-r\mathrm{/}N)$ for $j\le N$, which is at most $1\mathrm{/}j!$; omitted terms for $j>N$ are positive in [F5]. The $j=2$ coefficient alone differs from $1\mathrm{/}2!$ by $1\mathrm{/}(2N)$, so $e-(1+1\mathrm{/}N{)}^N\ge 1\mathrm{/}(2N)=h\mathrm{/}2$. Therefore this accepted finite-tolerance method is not order two; [F3] supplies an $O(h)$ global-error bound for the uncorrected stage, while [F2] gives order two for the fully solved collocation method. More explicitly, step 1.1 gives $y_n=(1+h{)}^n\ge 1$, hence the accepted first residual obeys $r_0=h{y}_n\mathrm{/}2\ge h\mathrm{/}2$. The ratio $r_0\mathrm{/}{h}^3\ge 1\mathrm{/}(2h^2)\to \mathrm{\infty }$, so the accepted residual is not $O(h^3)$. This diagnoses failure of that residual target; the independent endpoint lower bound above proves that the accepted method is not order two.

Here $Q_{11}=1\mathrm{/}2$, $b_1=1$, and by [F4] the exact stage equation is $U^{\ast }=1-(h\mathrm{/}2)U^{\ast }$, so $U^{\ast }=20\mathrm{/}21\in [0,2]$. For [F3], the ball is $[0,2]$, and its map is $\mathrm{\Phi }(Y)=1-(h\mathrm{/}2)Y=1-0.05Y$. It maps $[0,2]$ into $[0.9,1]\subset [0,2]$; its contraction factor is $q=h\mathrm{\mid }A\mathrm{\mid }{L}_F=0.1(1\mathrm{/}2)(1)=0.05$, and the invariant-ball bound is $h\mathrm{\mid }A\mathrm{\mid }{M}_F=0.1(1\mathrm{/}2)(2)=0.1\le R=1$. Thus the closed-ball and contraction hypotheses of [F3] hold. The stage update residual map is $G(V)=V-1+(h\mathrm{/}2)V=(1+h\mathrm{/}2)(V-U^{\ast })$; at $V-U^{\ast }=1\mathrm{/}2000$ it has magnitude $21\mathrm{/}40000=0.000525$. For the explicit-left-Euler sweep in [F5], $Q_{\mathrm{\Delta }}=0$, so $\mathrm{\mid }S(V)-V\mathrm{\mid }=\mathrm{\mid }G(V)\mathrm{\mid }$ and the SDC contraction factor is also $h\mathrm{/}2=1\mathrm{/}20$.

The specified $V=20\mathrm{/}21+1\mathrm{/}2000$ lies in $[0,2]$, so [F3] applies. With $q=1\mathrm{/}20$, the numerical residual threshold $(1-q)h^3=19\mathrm{/}20000=0.00095$ exceeds $\mathrm{\mid }G(V)\mathrm{\mid }=21\mathrm{/}40000$ from step 1.1. Directly, [F3] gives $\mathrm{\mid }V-U^{\ast }\mathrm{\mid }\le \mathrm{\mid }G(V)\mathrm{\mid }\mathrm{/}(1-q)=21\mathrm{/}38000<1\mathrm{/}1000=h^3$.

For this field $f(t,Y)=-Y$ and endpoint weight $b_1=1$, the approximate endpoint differs from the exact collocation endpoint by $h\mathrm{\mid }V-U^{\ast }\mathrm{\mid }=0.1\mathrm{/}2000=1\mathrm{/}20000=0.00005$. The stage bound in step 2.1 also gives the upper bound $h{h}^3=h^4=0.0001$. The example verifies a single stage solve; a global order-two conclusion would additionally require uniform per-step defect, stability, and stage-error estimates on the common tube.