Variable-step BDF2 with an explicit local implicit-branch rule

Input a vector field $f(t,y)$, a finite grid $t_0,\dots ,t_N$, starting states $Y_0,Y_1\in {\mathbb{R}}^d$ (so $N\ge 1$), and for each later step a prescribed closed ball $B_{n+1}\subset {\mathbb{R}}^d$ that specifies the admissible implicit branch. Before any evaluation, if either starting state has dimension different from $d$, return invalid-input; otherwise, if any time increment is nonpositive, return invalid-grid. Set $h_n=t_{n+1}-t_n$ and $r_n=h_n\mathrm{/}{h}_{n-1}$ for $1\le n<N$.

Also supply an exact branch oracle $\mathcal{O}$ for the step equations below. On input $(f,t_{n+1},h_n,r_n,Y_{n-1},Y_n,B_{n+1})$, it returns evaluation-failure if $f(t_{n+1},\cdot )$ is not defined throughout $B_{n+1}$. Otherwise it returns no-root if the equation has no root in that ball, ambiguous-branch if it has more than one, or $(\mathtt{\text{unique-root}},Z)$ with the exact root if it has exactly one. Oracle calls are returning primitives; a realization of this procedure must supply an oracle meeting this contract for every call it reaches. This is an algorithm relative to that oracle; the vector field and ball alone do not provide a general exact root-counting or root-solving procedure.

For $n=1,\dots ,N-1$, form the equation and call $\mathcal{O}$ with the current history and prescribed ball:

$\frac{(1+2r_n)Z-(1+r_n{)}^2{Y}_n+r_n^2{Y}_{n-1}}{h_n(1+r_n)}=f(t_{n+1},Z)\mathrm{.}$

On $(\mathtt{\text{unique-root}},Z)$, set $Y_{n+1}=Z$ and continue. On any of the three failure statuses, return that status with the computed prefix. On reaching $N$, return completed and $(Y_0,\dots ,Y_N)$. The procedure admits arbitrary positive adjacent step ratios; no convergence or accuracy property is part of this algorithm.

The coefficients are those obtained from the quadratic interpolation derivative in Quadratic interpolation gives the variable-step BDF2 formula and cubic residual. A separate theorem gives the uniform ratio hypotheses needed for second-order convergence; they are not part of this algorithm.