A successful natural-cubic tridiagonal Cholesky solve has a certified residual

Each successful width subtraction has exact positive input difference, so by [F2] its stored result ${\widehat{h}}_i$ is positive. Write $S_k={\widehat{h}}_k+{\widehat{h}}_{k+1}$. The successful rounding of its sum and multiplication by $2$ gives $d_k\ge 2(1-u{)}^2{S}_k\ge (9\mathrm{/}8)S_k>S_k$. Row $k$'s off-diagonal absolute sum is at most $S_k$: it contains only some of the positive entries ${\widehat{h}}_k,{\widehat{h}}_{k+1}$, and for $n=1$ it is zero. For any real nonzero vector $v$, applying $2c_k{v}_k{v}_{k+1}\ge -\mathrm{\mid }{c}_k\mathrm{\mid }(v_k^2+v_{k+1}^2)$ to each adjacent term yields $v^{T}Tv\ge {\sum }_k(d_k-{\sum }_{j\mathrm{\ne }k}\mathrm{\mid }{T}_{kj}\mathrm{\mid })v_k^2>0$. Hence every successfully assembled $T$ is real SPD.

In the dense Cholesky recurrence of [F3], induction over columns shows that ${\widehat{L}}_{ij}=0$ for $i>j+1$: the input matrix is tridiagonal, and in each such row the prior-column products and input entry are zero. At $k=1$ the diagonal square-sum is empty, so its pivot is copied as $p_1=d_1$, exactly as in the local algorithm. For $k>1$, the only possible nonzero term in the dense diagonal square-sum is $e_{k-1}^2$; the remaining zero products, additions and subtractions are exact and cannot fail under [F2]. Thus the dense pivot is exactly the specialized $p_k$, followed by the same square root and positive-normal test. For the first subdiagonal, the dense dot product has only the input $c_k$ after its exact zero terms, so the update is exactly $\mathrm{fl}(c_k\mathrm{/}{\mathrm{\ell }}_k)$. Every lower entry beyond that subdiagonal is exactly zero. This induction proves equality of all stored factor entries and all potentially failing operations. The forward and backward dense triangular recurrences likewise have only the single adjacent product; all other terms are exact zeros. Therefore the specialized solve outputs equal the published substitutions.

Let $r_{\ast }=T\widehat{m}-f$ be the exact residual. The algorithm computes the same sparse sequential products and subtraction as the dense dot product in [F6], with only exact-zero products and additions omitted. By [F2], a zero product is exact and adding zero to a stored normal value or zero is also exact, so the sparse accumulation is identical to the dense one. Thus [F6] gives $\mathrm{\parallel }\widehat{w}-r_{\ast }{\mathrm{\parallel }}_2\le g_n\mathrm{\parallel }T{\mathrm{\parallel }}_F\mathrm{\parallel }\widehat{m}{\mathrm{\parallel }}_2+u(\mathrm{\parallel }\widehat{v}{\mathrm{\parallel }}_2+\mathrm{\parallel }f{\mathrm{\parallel }}_2)$. By [F9] and [F10], the Euclidean norm is the square root of the sum of squared coordinates, so each coordinate magnitude is at most that norm and $\mathrm{\parallel }v{\mathrm{\parallel }}_2\le {\sum }_k\mathrm{\mid }{v}_k\mathrm{\mid }$; the latter follows by squaring, since all cross terms are nonnegative. By [F8], the same argument on the finite entry list gives $\mathrm{\parallel }T{\mathrm{\parallel }}_F\le {\sum }_{i,j}\mathrm{\mid }{T}_{ij}\mathrm{\mid }=F_1$. The definitions in [F1] therefore imply $\mathrm{\parallel }\widehat{w}{\mathrm{\parallel }}_2\le W_1$, $\mathrm{\parallel }\widehat{m}{\mathrm{\parallel }}_2\le X_1$, $\mathrm{\parallel }\widehat{v}{\mathrm{\parallel }}_2\le V_1$, and $\mathrm{\parallel }f{\mathrm{\parallel }}_2\le Y_1$. The coordinate bound also gives $\mathrm{\parallel }{r}_{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}\le \mathrm{\parallel }{r}_{\ast }{\mathrm{\parallel }}_2$, whence $\mathrm{\parallel }{r}_{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}\le \mathrm{\parallel }{r}_{\ast }-\widehat{w}{\mathrm{\parallel }}_2+\mathrm{\parallel }\widehat{w}{\mathrm{\parallel }}_2\le C$. Setting $e=r_{\ast }$ gives the stated exact right-hand-side perturbation without division by a solution or residual norm.

If $(n+3)u<1$, apply [F4] to each successful triangular substitution from step 1.2. It gives $D_1,D_2$ with $(\widehat{L}+D_1)z=f$ and $({\widehat{L}}^T+D_2)\widehat{m}=z$ and the stated entrywise bounds; since $\widehat{L}$ is bidiagonal, those bounds force $D_1,D_2$ to be bidiagonal as well. Under the distinct condition $(20n+20)u<1\mathrm{/}5$, step 1.1 and [F5] give $E=\widehat{L}{\widehat{L}}^T-T$ and the stated factor bound. Substituting the second triangular equation into the first gives $(\widehat{L}+D_1)({\widehat{L}}^T+D_2)\widehat{m}=f$. Expanding the product and using $\widehat{L}{\widehat{L}}^T=T+E$ yields $(T+J)\widehat{m}=f$. Entrywise submultiplicativity and the bounds on $D_1,D_2,E$ give the displayed bound for $J$. The conditional Frobenius estimate is exactly the further norm consequence in [F5], with the norm convention in [F8].

Put $n=r-2$. Assembly makes a fixed number of floating-point operations per each of the $r-1$ intervals and $n$ rows. Factorization, each substitution and residual evaluation visit $n$ rows, with at most a fixed number of operations per row because a tridiagonal row has at most three nonzero entries. The exact-certificate scan likewise visits $r-1$ intervals and $n$ rows; each contributes a fixed number of rational operations and comparisons to the sums, row discrepancies, and extrema, followed by a fixed number to form $B$. Thus the floating-point and exact rational operation counts are $O(r)$. The algorithm stores only input and output vectors, the bidiagonal factor, the three diagonals of $T$ and $A$, and a fixed number of rational accumulators; row discrepancies can be computed as they are scanned, so storage is $O(r)$ scalars and $O(r)$ rationals. Every loop has a finite index range and every floating-point instruction returns or its first failure. The certificate denominators $h_i$, $\delta$, and $1-(n-1)u$ are positive, so each exact rational operation has finite inputs and is defined. [F7] therefore gives termination; if a resource limit prevents completion of the exact certificate, the algorithm returns its separate failure status and no $B$. No rational bit-complexity bound follows.