Nonlinear Boundary-Value Solvers

Fix $a<b$, an integer $d\ge 1$, an open set $\mathrm{\Omega }\subseteq \mathbb{R}\times {\mathbb{R}}^d$ containing $[a,b]\times$ the states under consideration, and a vector field $f:\mathrm{\Omega }\to {\mathbb{R}}^d$. Let $D_B\subseteq {\mathbb{R}}^d\times {\mathbb{R}}^d$ be open and let $B:D_B\to {\mathbb{R}}^d$. A square nonlinear two-point boundary-value problem (BVP) is

$y^{\mathrm{\prime }}(t)=f(t,y(t))(a\le t\le b),B(y(a),y(b))=0,$

where $y$ is a continuously differentiable curve whose graph lies in $\mathrm{\Omega }$, whose endpoint pair lies in $D_B$, and where the $d$ scalar components of $B$ give exactly $d$ boundary equations. A BVP solution is such a curve satisfying both the differential equation and endpoint equation. No existence or uniqueness is part of this definition.

If the IVP from initial state $s\in {\mathbb{R}}^d$ has a unique solution $\varphi (\cdot ;s)$ on $[a,b]$, the exact shooting residual is $R(s):=B(s,\varphi (b;s))$ whenever $(s,\varphi (b;s))\in D_B$. For a mesh $a=t_0<\cdots <t_N=b$ and segment initial states $s_0,\dots ,s_N$, the exact multiple-shooting residual has rows ${\varphi }_i(t_{i+1};s_i)-s_{i+1}$ for $0\le i<N$ and final row $B(s_0,s_N)$, where ${\varphi }_i$ denotes the unique segment IVP solution when it exists. These residuals are defined only on their admissible IVP and boundary domains.

Let $a<b$, let $\mathrm{\Omega }\subseteq \mathbb{R}\times {\mathbb{R}}^d$ be open, and let $f:\mathrm{\Omega }\to {\mathbb{R}}^d$ be $C^1$. Let $K\subseteq \mathrm{\Omega }$ be compact and convex, and let $U\subseteq {\mathbb{R}}^d$ be open. Assume that for every $s\in U$ the unique IVP solution $\varphi (\cdot ;s)$ from $\varphi (a;s)=s$ exists on $[a,b]$ and $(t,\varphi (t;s))\in K$ for every $t$. Then $s\mapsto \varphi (t;s)$ is $C^1$ on $U$ for each $t\in [a,b]$. Its derivative matrix $S(t;s):=D_s\varphi (t;s)$ is the unique solution of

$S(t;s)=I_d+{\int }_a^t{D}_{y}f(r,\varphi (r;s))S(r;s)dr,$

and hence satisfies ${\mathrm{\partial }}_{t}S=D_{y}f(t,\varphi (t;s))S$, $S(a;s)=I_d$. The claim is local to the stated common compact tube; it does not assert differentiability beyond it.

Fix an interval $[a,b]$ and an open set $U\subseteq {\mathbb{R}}^d$ on which each exact IVP flow $\varphi (t;s)$ exists for all $t\in [a,b]$. A certified differentiable IVP evaluator on $U$ declares a $C^1$ approximate endpoint map (here $C^1$ means total differentiability with continuous derivative entries) $\tilde{\mathrm{\Phi }}:U\to {\mathbb{R}}^d$ and a stated number ${\delta }_{\mathrm{I}\mathrm{V}\mathrm{P}}\ge 0$. A call at $s\in U$ either returns failure or supplies a continuous approximate trajectory $\tilde{\varphi }(\cdot ;s)$, the endpoint $\tilde{\mathrm{\Phi }}(s)$ and the exact derivative $D\tilde{\mathrm{\Phi }}(s)$ for that numerical map, satisfying

${\sup }_{t\in [a,b]}\mathrm{\parallel }\tilde{\varphi }(t;s)-\varphi (t;s){\mathrm{\parallel }}_2\le {\delta }_{\mathrm{I}\mathrm{V}\mathrm{P}},\tilde{\mathrm{\Phi }}(s)=\tilde{\varphi }(b;s)\mathrm{.}$

The same ${\delta }_{\mathrm{I}\mathrm{V}\mathrm{P}}$ bounds every successful call, uniformly in its initial state; no approximate trajectory or error bound is required at a failed call. The declared endpoint map remains $C^1$ on $U$ even when some calls fail. The returned derivative is not asserted to equal the derivative of the exact flow. This is an interface contract for a supplied method; it does not assert that any particular integrator satisfies the contract.

Let $y^{\ast }\in C^1([a,b],{\mathbb{R}}^d)$ solve a square BVP, with $f$ and $B$ continuously differentiable on open neighborhoods of the trajectory and endpoint pair. Put $A(t)=D_{y}f(t,y^{\ast }(t))$, $B_1=D_{1}B(y^{\ast }(a),y^{\ast }(b))$, and $B_2=D_{2}B(y^{\ast }(a),y^{\ast }(b))$. Let

$X=C^1([a,b],{\mathbb{R}}^d),\mathrm{\parallel }v{\mathrm{\parallel }}_X=\mathrm{\parallel }v{\mathrm{\parallel }}_{\mathrm{\infty }}+\mathrm{\parallel }{v}^{\mathrm{\prime }}{\mathrm{\parallel }}_{\mathrm{\infty }},$

and

$Z=C([a,b],{\mathbb{R}}^d)\times {\mathbb{R}}^d,\mathrm{\parallel }(g,q){\mathrm{\parallel }}_Z=\max \{\mathrm{\parallel }g{\mathrm{\parallel }}_{\mathrm{\infty }},\mathrm{\parallel }q{\mathrm{\parallel }}_2\}\mathrm{.}$

The continuous linearized BVP operator is the bounded linear map $\mathcal{L}:X\to Z$ given by

$\mathcal{L}v=(v^{\mathrm{\prime }}-Av,B_{1}v(a)+B_{2}v(b))\mathrm{.}$

It is boundedly invertible when it is bijective and its inverse ${\mathcal{L}}^{-1}:Z\to X$ has finite operator norm. That norm is the conditioning constant for the linearized BVP used in the local discretization theorem.

For a $d$-dimensional BVP on $[a,b]$, an integer $N\ge 1$, uniform mesh width $h=(b-a)\mathrm{/}N$, mesh nodes $t_i=a+ih$, and node vector $Y=(Y_0,\dots ,Y_N)\in ({\mathbb{R}}^d{)}^{N+1}$, let $D_h$ be the open set of node vectors for which every midpoint pair $(t_i+h\mathrm{/}2,(Y_i+Y_{i+1})\mathrm{/}2)$ lies in the vector-field domain and $(Y_0,Y_N)$ lies in the boundary-map domain. Define $G_h:D_h\to ({\mathbb{R}}^d{)}^{N+1}$ by

$G_{h,i}(Y)=\frac{Y_{i+1}-Y_i}{h}-f\text{\hspace{0.17em}⁣}(t_i+\frac{h}{2},\frac{Y_i+Y_{i+1}}{2})(0\le i<N),G_{h,N}(Y)=B(Y_0,Y_N)\mathrm{.}$

Use the maximum of the Euclidean block norms for both node and residual vectors. The interior rows are normalized by $h$; consequently an unscaled increment row has size $h$ times its normalized row.

Fix a mesh $a=t_0<\cdots <t_N=b$ and states $s_0,\dots ,s_N$. Suppose the unique IVP solution from each segment start $s_i$ exists as a $C^1$ curve on $[t_i,t_{i+1}]$ for $0\le i<N$, and $(s_0,s_N)\in D_B$. The exact multiple-shooting residual has rows ${\varphi }_i(t_{i+1};s_i)-s_{i+1}$ and $B(s_0,s_N)$. For this fixed tuple, it vanishes exactly when there is a BVP solution $y$ with $y(t_i)=s_i$ for every $0\le i\le N$; that solution restricts to the given segment solutions on all mesh intervals.

On an open set $U$ of initial states, suppose each IVP has a unique solution $\varphi (\cdot ;s)$ on $[a,b]$ that is a $C^1$ curve, and $(s,\varphi (b;s))\in D_B$ for every $s\in U$. Define the exact shooting residual by $R(s)=B(s,\varphi (b;s))$. Then $R(s)=0$ if and only if $\varphi (\cdot ;s)$ is a BVP solution. Any BVP solution with initial state $s$ equals this shot.

Fix a uniform mesh and the open nodal domain $D_h$ and normalized residual $G_h$ from Normalized implicit-midpoint collocation residual for a two-point BVP. If $f$ and $B$ are $C^1$ on the required domains (total differentiability with continuous derivative entries), then $G_h$ is a $C^1$ square map from the open subset $D_h\subseteq {\mathbb{R}}^{d(N+1)}$ into ${\mathbb{R}}^{d(N+1)}$. Given an initial node vector $Y_0\in D_h$, tolerance $\tau \ge 0$, and correction budget $M\in {\mathbb{N}}_0$, apply Finite-budget Newton for a square vector residual to $G_h$ using its exact Jacobian. Return the last node vector and its root, singular-jacobian, invalid-trial, or iteration-budget-exhausted status as defined by that procedure. A root status means only that $\mathrm{\parallel }{G}_h(Y)\mathrm{\parallel }\le \tau$; it is not a branch, convergence, or error certificate.

Here $C^k$ means each coordinate has continuous total derivatives through order $k$. Let $f,B$ be $C^2$ near an exact solution $y^{\ast }\in C^3([a,b],{\mathbb{R}}^d)$ of a square BVP, and suppose the continuous linearized operator $\mathcal{L}$ in Continuous linearized BVP operator and its conditioning is boundedly invertible. For uniform meshes with $h=(b-a)\mathrm{/}N$, let $Y_i^{\ast }=y^{\ast }(t_i)$ and let $J_h=D{G}_h(Y^{\ast })$ be the Jacobian of the normalized midpoint residual. There are $h_0>0$ and $C<\mathrm{\infty }$ such that for every mesh width $0<h\le h_0$, $J_h$ is invertible and

$\mathrm{\parallel }{J}_h^{-1}{\mathrm{\parallel }}_{\mathrm{\infty }\to \mathrm{\infty }}\le C,$

where both finite-dimensional norms are the maximum of the Euclidean block norms. The bound is independent of $h$; this is a local linear inverse result, not a nonlinear convergence theorem.

For any $Y\in D_h$, $G_h(Y)=0$ if and only if

$Y_{i+1}-Y_i=hf\text{\hspace{0.17em}⁣}(t_i+\frac{h}{2},\frac{Y_i+Y_{i+1}}{2})(0\le i<N),B(Y_0,Y_N)=0.$

Equivalently, the piecewise-linear interpolant has on each segment a constant slope equal to the vector field at the segment midpoint state and satisfies the endpoint residual.

Fix a mesh $a=t_0<\cdots <t_N=b$, $N\ge 1$, and an open product domain of segment starts $(s_0,\dots ,s_N)$ on which $B$ and each exact or certified approximate segment endpoint map ${\mathrm{\Psi }}_i:U_i\to {\mathbb{R}}^d$ are $C^1$. Here $C^1$ means total differentiability with continuous derivative matrix entries. Define $F$ by rows $F_i={\mathrm{\Psi }}_i(s_i)-s_{i+1}$ for $0\le i<N$ and $F_N=B(s_0,s_N)$. Its Jacobian block row $i<N$ has $D{\mathrm{\Psi }}_i(s_i)$ in column $i$, $-I_d$ in column $i+1$, and zero in every other column. Its boundary row has $D_{1}B$ and $D_{2}B$ in columns $0$ and $N$ and zero elsewhere. When $N=1$, columns $0$ and $N$ are distinct.

Let $\mathrm{\Psi }:U\to {\mathbb{R}}^d$ be a $C^1$ endpoint map (total differentiability with continuous derivative entries) on an open set $U\subseteq {\mathbb{R}}^d$, and let $B$ be $C^1$ on an open neighborhood of $\{(s,\mathrm{\Psi }(s)):s\in U\}$. Define $R_{\mathrm{\Psi }}(s)=B(s,\mathrm{\Psi }(s))$. Then $R_{\mathrm{\Psi }}$ is $C^1$ and

$D{R}_{\mathrm{\Psi }}(s)=D_{1}B(s,\mathrm{\Psi }(s))+D_{2}B(s,\mathrm{\Psi }(s))D\mathrm{\Psi }(s)\mathrm{.}$

This applies to the exact flow endpoint map under Initial-data sensitivity of an ODE flow on a common compact tube and to the approximate endpoint map in Certified differentiable IVP approximation interface for shooting; in the latter case the derivative is exact for the numerical map, not the exact flow.

Fix a mesh $a=t_0<\cdots <t_N=b$, $N\ge 1$, and an open product domain of segment starts $(s_0,\dots ,s_N)$ on which $B$ and every certified segment endpoint map are $C^1$, meaning they are totally differentiable with continuous derivative entries. Inputs are an initial tuple in this domain, a residual tolerance $\tau \ge 0$, and a correction budget $M\in {\mathbb{N}}_0$. Each evaluator supplies an approximate endpoint map ${\tilde{\mathrm{\Phi }}}_i$ and its derivative. Form the computed square residual with rows ${\tilde{\mathrm{\Phi }}}_i(s_i)-s_{i+1}$ for $0\le i<N$ and $B(s_0,s_N)$; its block Jacobian is the matrix in The multiple-shooting Jacobian is bordered block-bidiagonal. For $k=0,1,\dots ,M$, in this order:

1. Evaluate the residual, its Jacobian, and the approximate segment trajectories. If any evaluator fails, return the last valid tuple with status evaluator-failure and no residual certificate.
2. If the Euclidean norm of the residual is at most $\tau$, return the tuple and trajectories with status root-tolerance-met.
3. If $k=M$, return status iteration-budget-exhausted.
4. Solve the Newton correction equation with the displayed square Jacobian using Newton correction for a square vector residual. A singular Jacobian returns status singular-jacobian.
5. If the proposed tuple is outside the open product domain, return the last tuple with status invalid-trial; otherwise accept it as the next iterate.

The procedure applies the finite-budget Newton checks to the $(N+1)d$ variables. Its residual-tolerance status concerns the approximate map that was evaluated. It does not certify that the segment approximations join, that an exact BVP solution exists, or that the procedure converges from arbitrary starts.

Let $U\subseteq {\mathbb{R}}^d$ be the open trial-initial-state set. Let $D_B\subseteq {\mathbb{R}}^d\times {\mathbb{R}}^d$ be the open domain of the $C^1$ boundary map $B$, where $C^1$ means total differentiability with continuous derivative entries. Inputs are a certified evaluator from Certified differentiable IVP approximation interface for shooting, an initial trial $s_0\in U$, residual tolerance $\tau \ge 0$, and a correction budget $M\in {\mathbb{N}}_0$. The evaluator may return failure on a queried trial. Every successful response must supply the approximate trajectory, the endpoint $\tilde{\mathrm{\Phi }}(s)$ and the exact derivative $D\tilde{\mathrm{\Phi }}(s)$ of the declared $C^1$ numerical endpoint map, with the interface's stated uniform trajectory-error bound. Success on every queried trial is not an input assumption.

For $k=0,1,\dots ,M$, in this order:

1. Query the evaluator at $s_k$. If it fails, return the last accepted trial with status evaluator-failure and no residual certificate. Before evaluating $B$, check $(s_k,\tilde{\mathrm{\Phi }}(s_k))\in D_B$; if this fails or cannot be established, return the last accepted trial with status invalid-endpoint-pair and no residual certificate. On success form $\tilde{R}(s_k)=B(s_k,\tilde{\mathrm{\Phi }}(s_k))$ and $D\tilde{R}(s_k)=D_{1}B(s_k,\tilde{\mathrm{\Phi }}(s_k))+D_{2}B(s_k,\tilde{\mathrm{\Phi }}(s_k))D\tilde{\mathrm{\Phi }}(s_k)$ using Derivative of the nonlinear shooting residual. A failure to evaluate these quantities returns evaluator-failure without a residual certificate.
2. If $\mathrm{\parallel }\tilde{R}(s_k){\mathrm{\parallel }}_2\le \tau$, return $s_k$, its approximate trajectory, and status root-tolerance-met. This status asserts only the displayed residual tolerance.
3. If $k=M$, return the last trial and status iteration-budget-exhausted.
4. Call Newton correction for a square vector residual with $A=D\tilde{R}(s_k)$ and $r=\tilde{R}(s_k)$. If it reports singular-jacobian, stop with that status. Otherwise let $u_k$ be its returned correction.
5. If the proposed trial $s_k+u_k$ is outside $U$ or its membership cannot be established, return the last accepted trial with status invalid-trial; otherwise accept $s_{k+1}=s_k+u_k$. Initially the last accepted trial is $s_0$; accepting a trial supplies no boundary residual certificate until step 1 succeeds there.

On a sequence of successful evaluations with endpoint pairs in $D_B$, this has the same residual, singularity, trial-domain and budget checks as Finite-budget Newton for a square vector residual. It makes no global-start, exact-root, or discretization-error claim. The numerical residual is $C^1$ on the open subset of $U$ where $(s,\tilde{\mathrm{\Phi }}(s))\in D_B$; no boundary value is evaluated outside that subset.

Here $C^2$ means continuously differentiable with continuous second total derivatives, and $C^3$ means the same through third derivatives. Let $f,B$ be $C^2$ on open neighborhoods of an exact solution $y^{\ast }\in C^3([a,b],{\mathbb{R}}^d)$ of the square BVP, and suppose its continuous linearized BVP operator is boundedly invertible. For all sufficiently fine uniform meshes, the normalized midpoint residual $G_h$ has a unique zero $Y_h$ in a fixed-radius maximum-norm ball about the sampled vector $Y^{\ast }=(y^{\ast }(t_i))$. Its Jacobian at $Y_h$ is invertible with an inverse bound independent of $h$. For every candidate $Y$ in that ball with $\mathrm{\parallel }{G}_h(Y){\mathrm{\parallel }}_{\mathrm{\infty }}\le {\epsilon }_{\mathrm{a}\mathrm{l}\mathrm{g}}$, its piecewise-linear interpolant $P_{h}Y$ satisfies