Finite explicit-left-Euler spectral deferred-correction sweep

Let $D\subseteq \mathbb{R}\times {\mathbb{R}}^d$ be the open time-state domain of an IVP $y^{\mathrm{\prime }}=f(t,y)$, with $d\ge 1$. The inputs are a time $t\in \mathbb{R}$, an initial state $u\in {\mathbb{R}}^d$ with $(t,u)\in D$, a step $h>0$, an integer $M\ge 1$, distinct ordered nodes $0\le c_1<\cdots <c_M\le 1$, a predictor (default $U^0=\mathbf{1}u$), a Lipschitz bound $L\ge 0$, a tolerance $\mathrm{t}\mathrm{o}\mathrm{l}>0$, an integer sweep budget $K\ge 0$, a supplied stage set $\mathcal{C}$, and a caller-supplied Boolean flag invariance_certified. A stage vector $U$ is admissible only when $(t+c_{j}h,U_j)\in D$ for every $j$.

After validating the node data, form the collocation tableau $Q,b$ of Collocation tableau from distinct quadrature nodes. Let $c_0=0$, $\mathrm{\Delta }{c}_j=c_j-c_{j-1}$, and define the left-Euler node-subinterval preconditioner by its initial column $a_i=c_1$ and stage block $(Q_{\mathrm{\Delta }}{)}_{ij}=\{\begin{array}{ll}\mathrm{\Delta }{c}_{j+1},& j<i,\\ 0,& j\ge i\mathrm{.}\end{array}$ The stage block is strictly lower triangular. In augmented notation, set $\widehat{Q}=(0\mid Q)$, ${\widehat{Q}}_{\mathrm{\Delta }}=(a\mid Q_{\mathrm{\Delta }})$, and $\widehat{F}(U)=(f(t,u),F(U))$. One sweep is $U^{k+1}=\mathbf{1}u+h{\widehat{Q}}_{\mathrm{\Delta }}\widehat{F}(U^{k+1})+h(\widehat{Q}-{\widehat{Q}}_{\mathrm{\Delta }})\widehat{F}(U^k)\mathrm{.}$ The fixed initial-column contributions cancel, so the procedure below does not evaluate $F_0=f(t,u)$. For a stage vector $U$, write $F_j(U)=f(t+c_{j}h,U_j)$. Since $Q_{\mathrm{\Delta }}$ is strictly lower triangular, for fixed previous stages $U^k$ the unique new stages are computed in increasing $i$ by the forward recursion $U_i^{k+1}=u+h{\sum }_{j<i}(Q_{\mathrm{\Delta }}{)}_{ij}{F}_j(U^{k+1})+h{\sum }_{j=1}^M(Q_{ij}-(Q_{\mathrm{\Delta }}{)}_{ij})F_j(U^k),i=1,\dots ,M\mathrm{.}$

Use $\mathrm{\parallel }V{\mathrm{\parallel }}_{\mathrm{\infty },2}={\max }_i\mathrm{\parallel }{V}_i{\mathrm{\parallel }}_2$ and $\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{\infty }}={\max }_i{\sum }_j\mathrm{\mid }{A}_{ij}\mathrm{\mid }$. The supplied set $\mathcal{C}$ must be a nonempty closed product ball of admissible stage vectors and have an $L$-Lipschitz stage field $F(U)=(F_j(U){)}_{j=1}^M$ in this norm. A flag value true is admissible only with the caller-established guarantee that, for every $V,Z\in \mathcal{C}$, $\mathbf{1}u+h{Q}_{\mathrm{\Delta }}F(Z)+h(Q-Q_{\mathrm{\Delta }})F(V)\in \mathcal{C}$. This is the inner-map invariance assertion; with $a<1$ it also ensures outer-sweep invariance. A flag value false makes no invariance assertion. Establishing the guarantee is external to this procedure; the procedure reads the supplied flag and does not decide a universally quantified property of $f$. After forming $Q_{\mathrm{\Delta }}$, compute $a=hL\mathrm{\parallel }{Q}_{\mathrm{\Delta }}{\mathrm{\parallel }}_{\mathrm{\infty }}$. If $a\ge 1$, return contraction-not-certified with no accepted endpoint. For $a<1$, compute $q=hL\mathrm{\parallel }Q-Q_{\mathrm{\Delta }}{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{/}(1-a)$; if $q\ge 1$ or invariance_certified is false, return contraction-not-certified with no accepted endpoint. The exact procedure is:

1. Reject repeated, unordered, or out-of-range nodes as invalid-node-data before forming the tableau.
2. Form $Q,b,Q_{\mathrm{\Delta }}$ from the valid nodes and apply the contraction inequalities and the supplied Boolean flag test described above.
3. If the predictor is outside $\mathcal{C}$ or any required stage evaluation $(t+c_{j}h,U_j)$ lies outside $D$, return inadmissible-stage and no accepted endpoint.
4. Evaluate and store all $M$ values $F_j(U^0)$ once.
5. If $K=0$, return iteration-budget-exhausted and no accepted endpoint; no residual test has been performed.
6. For $k=0,1,\dots ,K-1$, compute $U^{k+1}$ in increasing stage order using the displayed recursion, reusing the stored $F(U^k)$ and evaluating each new $F_j(U^{k+1})$ once. If a new stage is outside $D$, return inadmissible-stage and no accepted endpoint. Then compute $r_k=\mathrm{\parallel }{U}^{k+1}-U^k{\mathrm{\parallel }}_{\mathrm{\infty },2}$. If $r_k\le (1-q)\mathrm{t}\mathrm{o}\mathrm{l}$, return status residual-tolerance-met, the stage vector $U^k$, and endpoint $u+h{\sum }_{j=1}^M{b}_j{F}_j(U^k)$. If this is the $K$th sweep and the test failed, return iteration-budget-exhausted and no accepted endpoint; otherwise use $U^{k+1}$ and its stored field values as the next iterate.

These statuses report only the stated branch outcome; they do not assert convergence when a check fails.

Form $Q,b,Q_{\mathrm{\Delta }}$ once per invocation and retain their coefficients through the sweep loop. Retain the old and current stage vectors and their field values while computing a sweep and testing its residual. On continuation, reuse these buffers for the next sweep; on acceptance, use the retained $U^k$ and $F(U^k)$ for the returned stage vector and endpoint in step 6. Perform the displayed operations in exact real arithmetic.