Minimum energy paths string neb and saddle certificates

Let $d\ge 2$, let $C_{\mathrm{b}\mathrm{a}\mathrm{d}}\subseteq {\mathbb{R}}^d$ be the model's prescribed set of forbidden configurations, and let $U\subseteq {\mathbb{R}}^d\setminus C_{\mathrm{b}\mathrm{a}\mathrm{d}}$ be open. Call $U$ a declared collision-free tube when it is the supplied open domain on which the potential is defined; no physical interpretation of the choice of $U$ is implied. Let $V\in C^4(U,\mathbb{R})$, using the $C^k$ convention of $C^k$ maps and multi-index derivative notation in Euclidean space, and let $a,b\in U$. A regular path with fixed endpoints is $R\in C^1([0,1],U;{\mathbb{R}}^d)$ such that $R(0)=a$, $R(1)=b$, and $R^{\mathrm{\prime }}(s)\mathrm{\ne }0$ for every $s\in [0,1]$ (with one-sided derivatives at the endpoints). Its unit tangent and normal projector are

$t(s):=\frac{R^{\mathrm{\prime }}(s)}{\mathrm{\parallel }{R}^{\mathrm{\prime }}(s){\mathrm{\parallel }}_2},P_{t(s)}^{\perp }:=I-t(s)t(s{)}^T\mathrm{.}$

The path is a regular minimum-energy path (MEP) when

$P_{t(s)}^{\perp }\mathrm{\nabla }V(R(s))=0(0\le s\le 1),$

where $\mathrm{\nabla }V$ is the gradient in The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case. Thus the gradient is tangent to the path; at points where it vanishes the equation still holds. The endpoints are fixed data and need not be local minima unless that is added as a hypothesis. This is a conditional mathematical definition and makes no claim about reaction rates, physical mechanisms, or uniqueness.

Let $V\in C^4(U,\mathbb{R})$ on an open set $U\subseteq {\mathbb{R}}^d$, let $x\in U$, and let $v\in {\mathbb{R}}^d$ satisfy $\mathrm{\parallel }v{\mathrm{\parallel }}_2=1$ and $x\pm ϵv\in U$ for $ϵ>0$. Assume the segments $x+[-ϵ,ϵ]v$ lie in $U$. Define

$D_{ϵ}(x,v):=\frac{\mathrm{\nabla }V(x+ϵv)-\mathrm{\nabla }V(x-ϵv)}{2ϵ}\mathrm{.}$

If approximate gradient evaluations ${\widehat{g}}_{\pm }$ satisfy $\mathrm{\parallel }{\widehat{g}}_{\pm }-\mathrm{\nabla }V(x\pm ϵv){\mathrm{\parallel }}_2\le \eta$, and $M_4$ bounds the third derivatives of each gradient coordinate in the Taylor remainders on these segments, then

${\parallel \frac{{\widehat{g}}_{+}-{\widehat{g}}_{-}}{2ϵ}-{\mathrm{\nabla }}^{2}V(x)v\parallel }_2\le \frac{\sqrt{d}{M}_4}{6}{ϵ}^2+\frac{\eta }{ϵ}\mathrm{.}$

Thus the deterministic truncation error is $O({ϵ}^2)$ and the force-evaluation error contributes $O(\eta \mathrm{/}ϵ)$. This is an error bound for the Hessian action on the supplied direction; it is not an operator-norm bound for a full Hessian approximation.

Let $n\ge 1$, let $U\subseteq {\mathbb{R}}^n$ be open, and let $F:U\to {\mathbb{R}}^n$ be $C^1$ with Jacobian $J=DF$. Take $x_0\in U$ such that $A:=J(x_0)$ is invertible, and let $\beta >0$ be any bound with $\mathrm{\parallel }{A}^{-1}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \beta$. Suppose $ϵ:=\mathrm{\parallel }F(x_0){\mathrm{\parallel }}_2>0$, set $r:=2\beta ϵ$, and assume the open ball $B_2(x_0,2r)$ lies in $U$ and

$\mathrm{\parallel }J(x)-J(y){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le L\mathrm{\parallel }x-y{\mathrm{\parallel }}_2(x,y\in B_2(x_0,2r))$

for some $L\ge 0$ with $\beta Lr\le \frac{1}{2}$. Then $F$ has exactly one zero $x_{\ast }$ in the closed ball ${\bar{B}}_2(x_0,r)$, and

$\mathrm{\parallel }{x}_{\ast }-x_0{\mathrm{\parallel }}_2\le 2\beta \mathrm{\parallel }F(x_0){\mathrm{\parallel }}_2\mathrm{.}$

If $F(x_0)=0$, then $x_0$ itself is a zero; this separate case makes no local uniqueness assertion.

Let $n\ge 1$, let $U\subseteq {\mathbb{R}}^n$ be open, and let $F:U\to {\mathbb{R}}^n$ be $C^1$. For $x\in {\mathbb{R}}^n$ define $\mathrm{\parallel }x{\mathrm{\parallel }}_{\mathrm{\infty }}:={\max }_{j<n}\mathrm{\mid }{x}_j\mathrm{\mid }$, and for a linear map $B:{\mathbb{R}}^n\to {\mathbb{R}}^n$ define its induced norm by $\mathrm{\parallel }B{\mathrm{\parallel }}_{\mathrm{\infty }}:={\sup }_{z\mathrm{\ne }0}\mathrm{\parallel }Bz{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{/}\mathrm{\parallel }z{\mathrm{\parallel }}_{\mathrm{\infty }}$. This supremum is a finite real: if $B=(b_{ij})$ in the standard basis, then for $\mathrm{\parallel }z{\mathrm{\parallel }}_{\mathrm{\infty }}=1$,

$\mathrm{\parallel }Bz{\mathrm{\parallel }}_{\mathrm{\infty }}={\max }_{i<n}\mid {\sum }_{j<n}{b}_{ij}{z}_j\mid \le {\sum }_{i<n}{\sum }_{j<n}\mathrm{\mid }{b}_{ij}\mathrm{\mid },$

and scaling reduces every nonzero $z$ to this case; the set is nonempty because $n\ge 1$. Its supremum therefore exists by the least-upper-bound property of $\mathbb{R}$. Let $x_0\in U$, $A:=DF(x_0)$ be invertible, and suppose $\mathrm{\parallel }{A}^{-1}{\mathrm{\parallel }}_{\mathrm{\infty }}\le \beta$ for some $\beta >0$. Put $ϵ:=\mathrm{\parallel }F(x_0){\mathrm{\parallel }}_{\mathrm{\infty }}\ge 0$, and choose $r>0$ with $\beta ϵ\le r\mathrm{/}2$. Assume $B_{\mathrm{\infty }}(x_0,2r)\subset U$ and

$\mathrm{\parallel }DF(x)-DF(y){\mathrm{\parallel }}_{\mathrm{\infty }}\le L\mathrm{\parallel }x-y{\mathrm{\parallel }}_{\mathrm{\infty }}(x,y\in B_{\mathrm{\infty }}(x_0,2r))$

for some $L\ge 0$ with $\beta Lr\le \frac{1}{2}$. Then $F$ has exactly one zero $x_{\ast }$ in ${\bar{B}}_{\mathrm{\infty }}(x_0,r)$, and

$\mathrm{\parallel }{x}_{\ast }-x_0{\mathrm{\parallel }}_{\mathrm{\infty }}\le 2\beta \mathrm{\parallel }F(x_0){\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{.}$

In particular, when $F(x_0)=0$ the unique zero in this ball is $x_0$.

Let $U,V$ be as in Regular minimum-energy paths on a declared collision-free tube. Inputs: $x_0\in U$, a unit vector $v_0$, finite-difference distance $ϵ>0$, force-evaluation error bound $\eta \ge 0$, rotation step $\alpha >0$, rotation tolerance ${\tau }_{\mathrm{r}\mathrm{o}\mathrm{t}}\ge 0$, force tolerance ${\tau }_F\ge 0$, rotation cap $J\in {\mathbb{N}}_0$, translation step $\sigma >0$, and translation cap $K\in {\mathbb{N}}_0$. Return the last point, direction, reported residuals, a termination status from force-tolerance, rotation-cap, translation-cap, geometry-failure, rotation-failure, or nonfinite-evaluation, and mode_status=mode-unverified.

Initialize the translation-update counter $k=0$, the current point $x=x_0$, and the current unit direction $v=v_0$. At each translation iteration, start with the current $v$, set the rotation-update counter $j=0$, and repeat the following residual test and possible update:

1. If $x\pm ϵv\mathrm{\notin }U$, return geometry-failure. Evaluate approximate gradients ${\widehat{g}}_{\pm }$ at $x\pm ϵv$ with the declared error bound, and form $D_{ϵ}=({\widehat{g}}_{+}-{\widehat{g}}_{-})\mathrm{/}(2ϵ)$. Nonfinite data return nonfinite-evaluation.
2. Set $r_{\mathrm{r}\mathrm{o}\mathrm{t}}=\mathrm{\parallel }(I-v{v}^T)D_{ϵ}{\mathrm{\parallel }}_2$. If $r_{\mathrm{r}\mathrm{o}\mathrm{t}}\le {\tau }_{\mathrm{r}\mathrm{o}\mathrm{t}}$, end this rotation loop. If the test fails and $j=J$, return rotation-cap with the last direction. Otherwise set $w=v-\alpha (I-v{v}^T)D_{ϵ}$. If $w=0$, return rotation-failure; else replace $v$ by $w\mathrm{/}\mathrm{\parallel }w{\mathrm{\parallel }}_2$, set $j\leftarrow j+1$, and repeat the rotation test.

Thus $J$ counts direction updates, and the current direction is tested before the cap is returned, including when $J=0$. A small rotational residual by itself does not certify that the direction is the lowest eigenmode. This procedure does not take or validate a spectral-gap or mode-tracking certificate, so it always returns mode_status=mode-unverified.

After a rotation residual passes, evaluate $\widehat{g}(x)$ with error at most $\eta$. If it is nonfinite, return nonfinite-evaluation. If $\mathrm{\parallel }\widehat{g}(x){\mathrm{\parallel }}_2\le {\tau }_F$, return force-tolerance together with the mode status. If $k=K$, return translation-cap together with the mode status; perform an update only when $k<K$.

$x^{+}=x+\sigma [-\widehat{g}(x)+2(\widehat{g}(x{)}^{T}v)v]\mathrm{.}$

If $x^{+}\mathrm{\notin }U$, return geometry-failure; otherwise set $x\leftarrow x^{+}$, set $k\leftarrow k+1$, and begin the next translation iteration. Thus $K$ counts translation updates; the force-tolerance test is made before the cap test, including when $K=0$. mode_status=mode-unverified is metadata about the direction, not a termination status. This finite procedure makes no arbitrary-start, termination, saddle-convergence, or global-transition claim.

Let $U,V,a,b$ satisfy Regular minimum-energy paths on a declared collision-free tube. Inputs: an integer $M\ge 2$, images $R_0=a,R_1,\dots ,R_{M-1},R_M=b$ in $U$, a step size $\eta >0$, force and spacing tolerances ${\tau }_F,{\tau }_s\ge 0$, and a finite update budget $N\in {\mathbb{N}}_0$. Output: the last image chain and one of tolerances-met, geometry-failure, nonfinite-evaluation, or budget-exhausted. A stop status is an algorithmic report, not a continuum-error certificate.

At iteration $k=0,\dots ,N$, perform the following in order. After every arithmetic operation or norm evaluation below, return nonfinite-evaluation if its scalar or vector result is nonfinite, before using that result in a comparison, normalization, segment lookup, or subsequent operation. In particular, this check applies to chords, lengths, cumulative lengths, target lengths, and interpolated images.

1. For each interior $i=1,\dots ,M-1$, form the centered chord $c_i=R_{i+1}-R_{i-1}$. If $c_i=0$, return geometry-failure. Otherwise put $t_i=c_i\mathrm{/}\mathrm{\parallel }{c}_i{\mathrm{\parallel }}_2$ and $F_i^{\perp }=-(I-t_i{t}_i^T)\mathrm{\nabla }V(R_i)$. If any force is nonfinite, return nonfinite-evaluation.
2. For the current chain set ${\mathrm{\ell }}_i=\mathrm{\parallel }{R}_i-R_{i-1}{\mathrm{\parallel }}_2$ for $1\le i\le M$, $\bar{\mathrm{\ell }}=M^{-1}{\sum }_{i=1}^M{\mathrm{\ell }}_i$, $r_F={\max }_{1\le i<M}\mathrm{\parallel }{F}_i^{\perp }{\mathrm{\parallel }}_2$, and $r_s={\max }_{1\le i\le M}\mathrm{\mid }{\mathrm{\ell }}_i-\bar{\mathrm{\ell }}\mathrm{\mid }$. If $r_F\le {\tau }_F$ and $r_s\le {\tau }_s$, return tolerances-met.
3. If $k=N$, return budget-exhausted. Otherwise set $Y_0=a$, $Y_M=b$, and $Y_i=R_i+\eta F_i^{\perp }$ for interior images. Reject any nonfinite $Y_i$ with nonfinite-evaluation; if any $Y_i\mathrm{\notin }U$, return geometry-failure.
4. Compute cumulative lengths $s_0=0$, $s_j={\sum }_{i=1}^j\mathrm{\parallel }{Y}_i-Y_{i-1}{\mathrm{\parallel }}_2$, and total length $S=s_M$. If $S=0$ or the computed cumulative lengths are not strictly increasing, return geometry-failure. For $j=1,\dots ,M-1$, place the new image at the unique point of the piecewise-linear polygon $Y_0,\dots ,Y_M$ whose cumulative length is $jS\mathrm{/}M$; if that target is a vertex, use that vertex, and otherwise use linear interpolation on its unique containing segment. If any redistributed image lies outside $U$, return geometry-failure. Set $R_0^{k+1}=a,R_M^{k+1}=b$ and use the checked redistributed points as the new interior images.

This is the specified projected-force string variant. No convergence from arbitrary initial images, no automatic endpoint minimization, and no error estimate follow from the procedure alone.

Let $U,V,a,b$ satisfy Regular minimum-energy paths on a declared collision-free tube. Inputs: an integer $M\ge 2$, images $R_0=a,R_1,\dots ,R_M=b$ in $U$, spring constant $\kappa \ge 0$, fixed step $\eta >0$, force and spacing tolerances ${\tau }_F,{\tau }_s\ge 0$, an ordinary-step count $n_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{b}}\in {\mathbb{N}}_0$, and a finite update budget $N\in {\mathbb{N}}_0$. Require $n_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{b}}\le N$. Output: the last chain and one of tolerances-met, tangent-failure, geometry-failure, nonfinite-evaluation, or budget-exhausted.

At each iteration, endpoints are fixed and only interior images are updated. First evaluate $V_i=V(R_i)$ for every image; if any energy is nonfinite, return nonfinite-evaluation before making energy comparisons. For $i=1,\dots ,M-1$, write ${\mathrm{\Delta }}_i^{+}=R_{i+1}-R_i$ and ${\mathrm{\Delta }}_i^{-}=R_i-R_{i-1}$. Select an unnormalized tangent by

${\tau }_i=\{\begin{array}{ll}{\mathrm{\Delta }}_i^{+},& V_{i+1}>V_i>V_{i-1},\\ {\mathrm{\Delta }}_i^{-},& V_{i+1}<V_i<V_{i-1},\\ w_{\max }{\mathrm{\Delta }}_i^{+}+w_{\min }{\mathrm{\Delta }}_i^{-},& \text{otherwise and }{V}_{i+1}>V_{i-1},\\ w_{\min }{\mathrm{\Delta }}_i^{+}+w_{\max }{\mathrm{\Delta }}_i^{-},& \text{otherwise and }{V}_{i+1}<V_{i-1},\\ {\mathrm{\Delta }}_i^{+}+{\mathrm{\Delta }}_i^{-},& V_{i+1}=V_{i-1},\end{array}$

where $w_{\max }=\max (\mathrm{\mid }{V}_{i+1}-V_i\mathrm{\mid },\mathrm{\mid }{V}_{i-1}-V_i\mathrm{\mid })$ and $w_{\min }=\min (\mathrm{\mid }{V}_{i+1}-V_i\mathrm{\mid },\mathrm{\mid }{V}_{i-1}-V_i\mathrm{\mid })$. When $V_{i+1}=V_{i-1}$, the displayed centered-chord branch is the algorithm's explicit tie convention; it is a local completion of the strict-comparison rule in the cited improved-tangent formula. If ${\tau }_i=0$, return tangent-failure; otherwise set $t_i={\tau }_i\mathrm{/}\mathrm{\parallel }{\tau }_i{\mathrm{\parallel }}_2$. Next evaluate $\mathrm{\nabla }V(R_i)$ for every interior image; if any gradient is nonfinite, return nonfinite-evaluation before forming forces.

Initialize the update counter $k=0$. At iteration $k$, use the ordinary force

$F_i=-(I-t_i{t}_i^T)\mathrm{\nabla }V(R_i)+\kappa (\mathrm{\parallel }{\mathrm{\Delta }}_i^{+}{\mathrm{\parallel }}_2-\mathrm{\parallel }{\mathrm{\Delta }}_i^{-}{\mathrm{\parallel }}_2)t_i\mathrm{.}$

When $k\ge n_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{b}}$, choose the least index $i_{\ast }$ attaining the largest interior energy and replace that image's force by

$F_{i_{\ast }}^{\mathrm{C}\mathrm{I}}=-\mathrm{\nabla }V(R_{i_{\ast }})+2(\mathrm{\nabla }V(R_{i_{\ast }}{)}^T{t}_{i_{\ast }})t_{i_{\ast }};$

the climbing image has no spring force. The remaining interior images retain the ordinary force. If any resulting force is nonfinite, return nonfinite-evaluation. Thus iterations $k=0,\dots ,n_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{b}}-1$ use ordinary forces and the first climbing force is evaluated at iteration $k=n_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{b}}$. At each iteration report the maximum force norm and spacing residual ${\max }_i\mathrm{\mid }\mathrm{\parallel }{\mathrm{\Delta }}_i^{+}{\mathrm{\parallel }}_2-\mathrm{\parallel }{\mathrm{\Delta }}_i^{-}{\mathrm{\parallel }}_2\mathrm{\mid }$. Stop with tolerances-met only if both are within their declared tolerances. If a tolerance fails and $k=N$, return budget-exhausted; only when $k<N$ update every interior image by $R_i^{k+1}=R_i^k+\eta F_i^k$. Leaving $U$ returns geometry-failure. After a valid update set $k\leftarrow k+1$ and repeat. The tolerance check precedes the budget check, so $N=0$ still checks the initial chain and $n_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{b}}=N$ uses a climbing force at the final residual check (without an update if the budget is then exhausted).

The finite stopping status does not assert convergence to a MEP, a saddle, or a continuum path.

Let $V$ and $U$ be as in Regular minimum-energy paths on a declared collision-free tube, let $x\in U$, and let $H={\mathrm{\nabla }}^{2}V(x)$ use the convention of The Hessian matrix and critical points of a scalar field. Since $V\in C^4(U)$, it is $C^2$; The Hessian of a $C^2$ scalar field is symmetric gives $H^T=H$. In the standard Euclidean inner product this makes the endomorphism represented by $H$ self-adjoint. Therefore the real spectral theorem Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis applies, and $H$ has ordered eigenvalues ${\lambda }_1(H)\le \cdots \le {\lambda }_d(H)$.

A validated ordered eigenvalue enclosure is a list of intervals $I_j=[{\mathrm{\ell }}_j,u_j]$ together with an independently checked certificate proving ${\lambda }_j(H)\in I_j$ for every $j$ and preserving the stated ordering. The exact Hessian $H$, interval arithmetic or another validated spectral method, and all rounding assumptions used by the certificate are part of that external certificate; a Ritz value or residual alone is not, by definition, such a certificate.

For $d\ge 2$ and $\gamma >0$, the enclosure certifies index one with gap $\gamma$ when $u_1\le -\gamma$ and ${\mathrm{\ell }}_j\ge \gamma$ for every $j\ge 2$. For $d=1$, the condition is $u_1\le -\gamma$, with no positive-eigenvalue clauses. A validated enclosure records the input evidence; this definition does not assert that any particular eigensolver produces it.

Let $R:J\to {\mathbb{R}}^d$ be a unit-speed $C^3$ curve on an open interval $J$ containing $[0,1]$. Let $J_0\subseteq J$ be an interval on which ${\max }_j{\sup }_{u\in J_0}\mathrm{\mid }{R}_j^{\mathrm{\prime }\mathrm{\prime }\mathrm{\prime }}(u)\mathrm{\mid }\le M_3\mathrm{/}\sqrt{d}$. For the centered estimate, take $s$ and $h>0$ with $[s-h,s+h]\subseteq J_0$ and define

$d_h:=\frac{R(s+h)-R(s-h)}{2h},{\widehat{t}}_h:=\frac{d_h}{\mathrm{\parallel }{d}_h{\mathrm{\parallel }}_2}\mathrm{.}$

If ${\delta }_h:=M_3{h}^2\mathrm{/}6\le 1\mathrm{/}2$, then $d_h\mathrm{\ne }0$ and

$\mathrm{\parallel }{d}_h-R^{\mathrm{\prime }}(s){\mathrm{\parallel }}_2\le {\delta }_h,\mathrm{\parallel }{\widehat{t}}_h-R^{\mathrm{\prime }}(s){\mathrm{\parallel }}_2\le 4{\delta }_h\mathrm{.}$

For the unequal-step estimate, take positive $h_{-},h_{+}$ with $[s-h_{-},s+h_{+}]\subseteq J_0$ and define

$d_{h_{-},h_{+}}:=\frac{h_{+}}{h_{-}(h_{-}+h_{+})}(R(s)-R(s-h_{-}))+\frac{h_{-}}{h_{+}(h_{-}+h_{+})}(R(s+h_{+})-R(s))\mathrm{.}$

If ${\delta }_{h_{-},h_{+}}:=M_3{h}_{-}{h}_{+}\mathrm{/}6\le 1\mathrm{/}2$, then it is nonzero and its unit normalization differs from $R^{\mathrm{\prime }}(s)$ by at most $4{\delta }_{h_{-},h_{+}}$. In particular, equal steps give an $O(h^2)$ unit-tangent error; quasiuniform unequal steps give an $O(h_{-}{h}_{+})$ error. No second-order claim is made for a one-sided tangent branch.

Let $L>0$, let $M\ge 1$ be an integer, and let $R:[0,L]\to {\mathbb{R}}^d$ be a unit-speed $C^3$ curve with $M$ equal arc-length intervals of length $h=L\mathrm{/}M$. Suppose $\mathrm{\parallel }{R}^{\mathrm{\prime }\mathrm{\prime }}{\mathrm{\parallel }}_2\le K_2$ and the coordinate third derivatives satisfy the bound in Second-order centered and unequal-step tangent estimates with constant $M_3$. For sufficiently small $h$, each chord length ${\mathrm{\ell }}_i=\mathrm{\parallel }R(ih)-R((i-1)h){\mathrm{\parallel }}_2$ satisfies $\mathrm{\mid }{\mathrm{\ell }}_i-h\mathrm{\mid }\le C_1{h}^3$, where $C_1$ depends only on $K_2,M_3$. The piecewise-linear interpolant through the samples differs from $R$ in supremum norm by at most $C_2{h}^2$. If this polygon is redistributed by linear interpolation at equally spaced cumulative-length targets, the $j$th redistributed image is within $C_3{h}^2$ of $R(jh)$, for every $j=0,\dots ,M$.

Here $C^3$ on $[0,L]$ means that $R$ is the restriction of a $C^3$ curve on an open interval containing $[0,L]$; derivatives at the endpoints are the continuous one-sided values, and the unit-speed and derivative bounds are required on $[0,L]$.