Certified inverse defects and primal residuals bound linear-solve Jacobian and pullback errors

For every $z$, $\mathrm{\parallel }ABz\mathrm{\parallel }\ge (1-d)\mathrm{\parallel }z\mathrm{\parallel }$ by [F9]. Applying [F3] to the square map $AB$, a zero singular value would give a nonzero right singular vector in its kernel, contradicting this lower bound; thus $AB$ is invertible. Then $B$ is injective and $A$ is surjective. The square SVDs of $B$ and $A$ therefore also have no zero singular values, so [F3] makes both invertible. Applying the lower bound to $z=(AB{)}^{-1}y$ gives $\mathrm{\parallel }(AB{)}^{-1}\mathrm{\parallel }\le 1\mathrm{/}(1-d)$. Since $A^{-1}=B(AB{)}^{-1}$, [F8] gives $\mathrm{\parallel }{A}^{-1}\mathrm{\parallel }\le K$. The identity $B-A^{-1}=A^{-1}(AB-I)$ gives $\mathrm{\parallel }B-A^{-1}\mathrm{\parallel }\le Kd$, while $\widehat{x}-x=A^{-1}(A\widehat{x}-b)$ gives $\mathrm{\parallel }\widehat{x}-x\mathrm{\parallel }\le K\rho$. The residuals in these identities are exact; [F2] explains how to certify them from rounded evaluations.

Apply [F1] at the exact point $(A,b)$. For the matrix edge, $BH\widehat{x}-A^{-1}Hx=(B-A^{-1})H\widehat{x}+A^{-1}H(\widehat{x}-x)$. Since $\mathrm{\parallel }H{\mathrm{\parallel }}_2\le \mathrm{\parallel }H{\mathrm{\parallel }}_F$ by [F7], submultiplicativity [F8], the operator action bound [F9], and step 1.1 give ${\eta }_A$; the vector edge gives ${\eta }_b$. For any linear map $J$ between Euclidean spaces, $\mathrm{\parallel }{J}^{T}y\mathrm{\parallel }={\sup }_{\mathrm{\parallel }x\mathrm{\parallel }=1}\mathrm{\mid }⟨J^{T}y,x⟩\mathrm{\mid }={\sup }_{\mathrm{\parallel }x\mathrm{\parallel }=1}\mathrm{\mid }⟨y,Jx⟩\mathrm{\mid }\le \mathrm{\parallel }y\mathrm{\parallel }\mathrm{\parallel }J\mathrm{\parallel }$ by [F7], so $\mathrm{\parallel }{J}^T\mathrm{\parallel }\le \mathrm{\parallel }J\mathrm{\parallel }$; applying this to $J^T$ gives equality. Thus the adjoint discrepancies have the same norm bounds. This explicitly accounts for the perturbed primal evaluation point through $\rho$.

Fix an output coordinate $j$ of $\widehat{\lambda }$ and put $q_i=B_{ij}{c}_i$. By success in [F4] and the relative bound in [F5], $p_i=q_i(1+{\alpha }_i)$ with $\mathrm{\mid }{\alpha }_i\mathrm{\mid }\le u$; exact-zero products have ${\alpha }_i=0$. For each addition $i=2,\dots ,n$, write $s_i=(s_{i-1}+p_i)(1+{\beta }_i)$ with $\mathrm{\mid }{\beta }_i\mathrm{\mid }\le u$, taking ${\beta }_i=0$ when the exact sum is zero. Expanding gives ${\widehat{\lambda }}_j=s_n={\sum }_{i=1}^n{q}_i(1+{\alpha }_i){\prod }_{k=\max (2,i)}^n(1+{\beta }_k)$, with an empty product interpreted as $1$. Each coefficient has at most $n$ factors: for $i=1$ it has one product factor and $n-1$ addition factors, while for $i\ge 2$ it has one product factor and $n-i+1$ addition factors. Thus [F6], $nu<1$, and monotonicity of $ku\mathrm{/}(1-ku)$ imply that each coefficient differs from $1$ by at most ${\gamma }_n$. Hence $\mathrm{\mid }{\widehat{\lambda }}_j-(B^{T}c{)}_j\mathrm{\mid }\le {\gamma }_n{\sum }_i\mathrm{\mid }{B}_{ij}\mathrm{\mid }\mathrm{\mid }{c}_i\mathrm{\mid }$. Stacking these bounds and applying [F7] to $\mathrm{\mid }B{\mathrm{\mid }}^T\mathrm{\mid }c\mathrm{\mid }$ gives $\mathrm{\parallel }\widehat{\lambda }-B^{T}c{\mathrm{\parallel }}_2\le t\mathrm{\parallel }c{\mathrm{\parallel }}_2$. By the adjoint norm equality in step 2.1 and the action bound [F9], $\mathrm{\parallel }{B}^{T}c{\mathrm{\parallel }}_2\le M\mathrm{\parallel }c{\mathrm{\parallel }}_2$, so $\mathrm{\parallel }\widehat{\lambda }{\mathrm{\parallel }}_2\le (M+t)\mathrm{\parallel }c{\mathrm{\parallel }}_2$. Each rounded outer-product entry has error at most $u\mathrm{\mid }{\widehat{\lambda }}_i{\widehat{x}}_j\mathrm{\mid }$, so its Frobenius error is at most $u(M+t)\mathrm{\parallel }\widehat{x}{\mathrm{\parallel }}_2\mathrm{\parallel }c{\mathrm{\parallel }}_2$. Combining these bounds with step 2.1 gives the stated vector and matrix cotangent estimates.

For each realized nonzero $c$, any cotangent error vector $z$ is the action on $c$ of the linear map $z{c}^T\mathrm{/}\mathrm{\parallel }c{\mathrm{\parallel }}^2$, whose induced norm is $\mathrm{\parallel }z\mathrm{\parallel }\mathrm{/}\mathrm{\parallel }c\mathrm{\parallel }$ by Cauchy--Schwarz [F7] and equality on $c\mathrm{/}\mathrm{\parallel }c\mathrm{\parallel }$ [F9]; vectorize the matrix cotangent for the matrix edge. When $c=0$, successful operations return exact zero. Thus the realized rounded pullbacks admit local linear-map perturbations with the displayed bounds, without asserting global linearity of rounding. The graph perturbation theorem may propagate these realized maps with exact accumulation.