Deferred correction and collocation iterations

Assume Countable Choice. Let $g:[0,1]\to \mathbb{R}$ be continuous. Its Riemann integral and its Lebesgue integral with respect to Lebesgue measure on $[0,1]$ both exist and are equal.

The proof uses explicit uniform partitions and avoids the stronger general Riemann-to-Lebesgue equality theorem. Its dependency on Countable Choice is stated: the interval-measure formula comes from A box in ${\mathbb{R}}^n$ with parameters $a_i\le b_i$ is Lebesgue measurable of measure ${\prod }_{i<n}(b_i-a_i)$, whichever of its faces are included.

Assume Countable Choice. For every integer $M\ge 1$, Lebesgue measure on the relative Borel space $[0,1]$ is Gaussian quadrature moment data of order $2M$ in the sense of Positive-measure Gaussian quadrature moment data.

Let $M,d\ge 1$, let $0\le c_1<\cdots <c_M\le 1$ be distinct collocation nodes, and let ${\mathrm{\ell }}_1,\dots ,{\mathrm{\ell }}_M$ be their cardinal polynomials from Cardinal-polynomial interpolation. Define $Q_{ij}:={\int }_0^{c_i}{\mathrm{\ell }}_j(s)ds,b_j:={\int }_0^1{\mathrm{\ell }}_j(s)ds\mathrm{.}$ The matrix $Q\in {\mathbb{R}}^{M\times M}$ and vector $b\in {\mathbb{R}}^M$ are the collocation tableau coefficients. For an IVP $y^{\mathrm{\prime }}=f(t,y)$ with $f:D\to {\mathbb{R}}^d$ on the open time-state domain $D$ of First-order systems, initial value problems, and solutions on intervals, fix $(t,u)\in D$ and a step $h>0$. A stage vector $U\in ({\mathbb{R}}^d{)}^M$ is admissible only when $(t+c_{j}h,U_j)\in D$ for every $j$. On this admissible set write $F_j(U):=f(t+c_{j}h,U_j),QF(U):={({\sum }_{j=1}^M{Q}_{ij}{F}_j(U))}_{i=1}^M\mathrm{.}$ All displayed integrals use the oriented Riemann convention of The integral with oriented limits: ${\int }_a^{a}f:=0$ and ${\int }_b^{a}f:=-{\int }_a^{b}f$. In particular $Q_{ij}=0$ when $c_i=0$, and the integral in $u_h$ vanishes at $\tau =0$. The collocation stages and endpoint are the implicit Runge–Kutta equations of Implicit Runge–Kutta stage equations and update with $A=Q$, nodes $c$, and weights $b$: $U=\mathbf{1}u+hQF(U),{\mathrm{\Psi }}_h(t,u)=u+h{\sum }_{j=1}^M{b}_j{F}_j(U)\mathrm{.}$ The associated collocation polynomial on normalized time $\tau \in [0,1]$ is $u_h(\tau ):=u+h{\int }_0^{\tau }{\sum }_{j=1}^M{\mathrm{\ell }}_j(s)F_j(U)ds\mathrm{.}$ Thus $u_h(c_i)=U_i$, $u_h^{\mathrm{\prime }}(c_i)=h{F}_i(U)$, and $u_h(1)={\mathrm{\Psi }}_h(t,u)$ whenever $U$ is an admissible solution. This definition alone asserts no branch existence or uniqueness.

For interpolation estimates define the Lebesgue constant of this fixed node set by ${\mathrm{\Lambda }}_M:={\max }_{0\le s\le 1}{\sum }_{j=1}^M\mathrm{\mid }{\mathrm{\ell }}_j(s)\mathrm{\mid }\mathrm{.}$ For a real matrix $A$, write $\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{\infty }}:={\max }_i{\sum }_j\mathrm{\mid }{a}_{ij}\mathrm{\mid }$. These constants depend on the nodes and on $M$; no uniform-in-$M$ bound is part of the definition.

For the distinct nodes and cardinal polynomials in Collocation tableau from distinct quadrature nodes, every entry of $Q$, every component of $b$, and the Lebesgue constant ${\mathrm{\Lambda }}_M$ is a finite real number.

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.

Consider the procedure of Finite explicit-left-Euler spectral deferred-correction sweep with $M,d\ge 1$ and budget $K\ge 0$. Count one stage call for each instructed evaluation of $F_j(U)=f(t+c_{j}h,U_j)$, even when different calls happen to have equal arguments. Generating the supplied predictor and constructing or checking external admissibility, set-membership or invariance certificates are outside this call count. Assume each invoked evaluation and check returns. The following counts apply to any supplied predictor, including the default constant predictor.

• An exit at the node, contraction, invariance or predictor-admissibility checks before step 4 uses zero instructed stage calls. A run completing step 4 uses $M$ predictor calls. If $K=0$, it then returns iteration-budget-exhausted, with no residual test and no accepted endpoint.
• If predictor evaluation and exactly $s$ full sweeps complete, with no incomplete sweep, the run uses exactly $M(s+1)$ stage calls, where $0\le s\le K$. If the next sweep instead exits at an inadmissible stage after evaluating a prefix of $p$ new stages, where $0\le p<M$ and $s<K$, the count is exactly $M(s+1)+p$.
• Hence every execution uses at most $M(K+1)$ instructed stage calls. Equality holds for a run completing predictor evaluation and all $K$ sweeps, including the $K=0$ case after predictor evaluation. Acceptance after $s\ge 1$ completed sweeps returns $U^{s-1}$; forming its endpoint uses the cached $F(U^{s-1})$ and adds no stage call. No $F_0=f(t,u)$ call is required.

For direct dense evaluation of the prescribed finite sums, the stored tableau and preconditioner use $O(M^2)$ real coefficients, and old/current stage and derivative buffers use $O(Md)$ real scalars. A complete sweep uses $O(M^{2}d)$ scalar arithmetic in addition to its $M$ stage calls. Its residual requires $O(Md)$ scalar arithmetic, at most $M$ square roots and $O(M)$ comparisons; the accepted endpoint requires $O(Md)$ further arithmetic and no stage calls. These bounds also bound any evaluated prefix of a failed sweep. After the quadrature data are supplied, forming the preconditioner, coefficient differences and contraction row norms uses $O(M^2)$ scalar arithmetic and absolute-value operations. Including default constant-predictor initialization, all direct algebraic work through any exit is bounded by $O(M^2+(K+1)M^{2}d)$, with at most $KM$ square roots for residuals; scalar absolute values and loop/comparison work obey the same asymptotic bound. The storage bound is independent of $K$ when buffers are reused as instructed.

These bounds exclude the work and internal storage of evaluating $f$, constructing the polynomial quadrature data, generating a supplied nondefault predictor, and performing the external domain/set/certificate checks. They do not bound those unspecified tasks or assert that a failed execution completed $K$ sweeps. All counts concern exact real arithmetic and give no floating-point roundoff guarantee.

For an admissible stage vector $U$, the fixed-point equation for one sweep of Finite explicit-left-Euler spectral deferred-correction sweep holds if and only if $U=\mathbf{1}u+hQF(U)$, the collocation stage equation of Collocation tableau from distinct quadrature nodes.

Assume Countable Choice for the Lebesgue interval-measure formula. For Lebesgue measure on $[0,1]$, the one-node Gaussian quadrature rule has node $c_1=1\mathrm{/}2$ and weight $b_1=1$. Its one-stage collocation tableau therefore has $Q_{11}=1\mathrm{/}2$ and endpoint weight $b_1=1$.

For the scalar test equation $y^{\mathrm{\prime }}=\lambda y$ and $z=h\lambda$, let $U^{\ast }$ be a collocation stage vector and $U^k$ the SDC iterates using the explicit-left-Euler stage block $Q_{\mathrm{\Delta }}$ from Finite explicit-left-Euler spectral deferred-correction sweep. Then $E^{k+1}=B(z)E^k,B(z):=(I-z{Q}_{\mathrm{\Delta }}{)}^{-1}z(Q-Q_{\mathrm{\Delta }}),E^k:=U^k-U^{\ast }\mathrm{.}$ The inverse exists for every real $z$ because $Q_{\mathrm{\Delta }}$ is strictly lower triangular. In the induced infinity norm from Collocation tableau from distinct quadrature nodes, $\mathrm{\parallel }{E}^k{\mathrm{\parallel }}_{\mathrm{\infty },2}\le \mathrm{\parallel }B(z){\mathrm{\parallel }}_{\mathrm{\infty }}^k\mathrm{\parallel }{E}^0{\mathrm{\parallel }}_{\mathrm{\infty },2}$. This identity makes no convergence claim when the powers of $B(z)$ do not tend to zero; stability of the fully solved collocation step alone is not an SDC iteration guarantee.

Let $\mathcal{C}$ be a nonempty closed product ball of admissible stage vectors in $({\mathbb{R}}^d{)}^M$, with metric $\mathrm{\parallel }U-V{\mathrm{\parallel }}_{\mathrm{\infty },2}={\max }_i\mathrm{\parallel }{U}_i-V_i{\mathrm{\parallel }}_2$. For each $V\in \mathcal{C}$, assume the inner stage map $Z⟼\mathbf{1}u+h{Q}_{\mathrm{\Delta }}F(Z)+h(Q-Q_{\mathrm{\Delta }})F(V)$ maps $\mathcal{C}$ into itself, and assume the stage field $F(U)=(f(t+c_{i}h,U_i){)}_{i=1}^M$ is $L$-Lipschitz there for some $L\ge 0$. Put $a=hL\mathrm{\parallel }{Q}_{\mathrm{\Delta }}{\mathrm{\parallel }}_{\mathrm{\infty }},q=\frac{hL\mathrm{\parallel }Q-Q_{\mathrm{\Delta }}{\mathrm{\parallel }}_{\mathrm{\infty }}}{1-a}\mathrm{.}$ If $a<1$ and $q<1$, then every sweep is uniquely defined in $\mathcal{C}$, the sweep map $S:U^k\mapsto U^{k+1}$ is a contraction with constant $q$, and its unique fixed point $U^{\ast }$ is the unique collocation stage vector in $\mathcal{C}$. For every $V\in \mathcal{C}$, $\mathrm{\parallel }V-U^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty },2}\le \frac{\mathrm{\parallel }S(V)-V{\mathrm{\parallel }}_{\mathrm{\infty },2}}{1-q}\mathrm{.}$ If the initial iterate satisfies $U^0\in \mathcal{C}$, then the iterates $U^{k+1}=S(U^k)$ obey $\mathrm{\parallel }{U}^k-U^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty },2}\le q^k\mathrm{\parallel }{U}^0-U^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty },2}$. In particular, a residual-certified predictor used with Finite explicit-left-Euler spectral deferred-correction sweep must lie in $\mathcal{C}$. These are local stage-iteration claims; they assert no convergence when either contraction inequality fails.

Fix $M$ distinct nodes in $[0,1]$, a time $t$, and an exact IVP solution $y$ on an interval $[t,t+h_0]$ for some $h_0>0$, with initial state $u=y(t)$. Let $D\subseteq \mathbb{R}\times {\mathbb{R}}^d$ be open and let $f:D\to {\mathbb{R}}^d$ be defined on a neighborhood of a compact tube containing this exact trajectory and the collocation stages. Assume each scalar coordinate of $f$ has continuous partial derivatives through total order $2M+1$, all bounded on the tube. Smoothness of vector-valued functions and their derivative bounds here and below are componentwise; the scalar Taylor supplier is applied to each coordinate, and finite-dimensional coordinate bounds give the stated Euclidean norm bounds. Assume the collocation stage branch exists and is locally unique in this tube for all sufficiently small $h\le h_0$. Let $u_h$ be the collocation polynomial from Collocation tableau from distinct quadrature nodes, and set $g_h(\tau )=f(t+h\tau ,u_h(\tau )),r_h(\tau )=u_h^{\mathrm{\prime }}(\tau )-h{g}_h(\tau )\mathrm{.}$ For $1\le j\le M$, $\mathrm{\parallel }{u}_h^{(j)}{\mathrm{\parallel }}_{\mathrm{\infty }}\le C_j{h}^j$; for $j>M$, $u_h^{(j)}=0$. For $0\le j\le 2M$, $\mathrm{\parallel }{g}_h^{(j)}{\mathrm{\parallel }}_{\mathrm{\infty }}\le C_j{h}^j$ (with $h^0=1$), and $\mathrm{\parallel }{r}_h^{(j)}{\mathrm{\parallel }}_{\mathrm{\infty }}\le C_j{h}^{j+1}\mathrm{.}$ The constants depend on the fixed node set and its cardinal-basis derivative bounds; no uniformity in $M$ is asserted.