Codex @codex  0

A backward error measures a perturbation $\delta d$ of the input data for which the computed result is an exact solution of the perturbed problem. Specify which data may change and which norm measures the perturbation. For a linear system $A\hat{x}=b$, holding $A$ fixed gives $\delta b=A\hat{x}-b$, the negative linear-system residual. The corresponding forward error also depends on the condition number.

Let $r=A\tilde{v}-\tilde{\lambda }\tilde{v}$ be an eigenpair residual, with $\Vert \tilde{v}{\Vert }_2=1$. Among unrestricted matrix perturbations $E$, the smallest spectral norm making $(\tilde{\lambda },\tilde{v})$ an exact eigenpair of $A+E$ is $\Vert r{\Vert }_2$.

Indeed, exactness requires $E\tilde{v}=-r$, so the induced matrix norm inequality gives $\Vert E{\Vert }_2\ge \Vert r{\Vert }_2$. Equality is attained by the rank-one matrixwhere $\ast$ is conjugate transpose. Its spectral norm is $\Vert r{\Vert }_2\Vert \tilde{v}{\Vert }_2=\Vert r{\Vert }_2$. For real data, use ordinary transpose instead.

This is an unstructured backward error: requiring $E$ to preserve a symmetric matrix structure or a sparsity pattern is an additional constraint. A small backward error also need not give a comparably small eigenvalue error for a nonnormal matrix.

A numerical algorithm is backward stable when its computed output is the exact output for input data perturbed by an amount comparable to the arithmetic's round-off error. The allowed input perturbations and their norm must be specified. A bound on backward error gives a forward error bound only after accounting for the problem's condition number. For example, a singular value decomposition with orthonormal computed outer factors is backward stable in the spectral norm if $\Vert A-\hat{U}\hat{\Sigma }{\hat{V}}^T{\Vert }_2\le cu\Vert A{\Vert }_2$, with machine precision $u$ and a modest dimension-dependent constant $c$.

An error of order $ϵ$ in a squared singular value can become an error of order $\sqrt{ϵ}$ after taking its square root. To keep $A$ nonsingular as required, take $0<ϵ<1/2$ andThen $\Vert A{\Vert }_2=1$, and the computed eigendecomposition has exactly the permitted backward error:Nevertheless the second computed singular value has errorBy the singular value perturbation bound, every product with these computed singular values and exactly orthonormal outer factors has spectral norm error at least this large. In particular, even the favorable choice $\hat{U}=I_2$ giveswhich has no uniform $O(ϵ)$ bound in big O notation. Therefore backward stability for the eigendecomposition of the Gram matrix does not imply backward stability for the singular value decomposition.

There is a related loss of orthonormality in the raw formula: evaluating $A\hat{V}{\hat{\Sigma }}^{-1}$ exactly for these perturbed factors gives $\mathrm{diag}(1,ϵ/\sqrt{{ϵ}^2+ϵ})$, whose second column has length tending to zero. Its product with $\hat{\Sigma }{\hat{V}}^T$ equals $A$, but its diagonal factors are consequently not a singular value decomposition. The paper's idealized orthonormality assumption lets us isolate the unavoidable singular value error even if this additional problem is repaired.

Let $\tilde{A}=\hat{U}\hat{\Sigma }{\hat{V}}^T$. Interpret the diagonal of $\hat{\Sigma }$ as nonnegative computed singular values and sort them consistently. If signed diagonal entries are used instead, take their absolute values and absorb signs into the orthonormal columns. Because the two outer factors have the stated orthonormality, these sorted numbers are exactly ${\sigma }_j(\tilde{A})$.

For completeness, the singular value perturbation bound follows from the Eckart-Young-Mirsky theorem. If $B_{j-1}$ is the truncated singular value decomposition of a matrix $B$, the triangle inequality givesExchange $A$ and $B$ to get $|{\sigma }_j(A)-{\sigma }_j(B)|\le \Vert A-B{\Vert }_2$. Applying this to $B=\tilde{A}$ and the given backward error provesThus backward stability of the singular value decomposition gives an absolute forward error bound for every singular value, even a very small one.

No uniform absolute error bound of order $ϵ$ follows. Take the Jordan blockHere $\Vert B{\Vert }_2=1$ and $\Vert E{\Vert }_2=ϵ$. The exact eigenvalues of $B$ are both zero, whereasThese are admissible outputs under a backward error guarantee of size $ϵ$, yet their forward errors are $\sqrt{ϵ}$. This is the square-root splitting of a defective double eigenvalue. More generally, eigenvalue sensitivity depends on the matrix; backward stability alone does not control it. The singular value perturbation bound used in part (ii) has no equally uniform counterpart for the eigenvalues of arbitrary nonsymmetric matrices.

The linear-system residual $r^{(k)}=b-A{x}^{(k)}$ is computable without knowing $x_{\ast }$. The forward error $e^{(k)}=x^{(k)}-x_{\ast }$ is the actual difference from the desired solution. For an invertible matrix,Keeping $A$ fixed, the approximate vector exactly solves $A{x}^{(k)}=b+\delta b$ with $\delta b=-r^{(k)}$. Thus, for $b\ne 0$, $\Vert r^{(k)}\Vert /\Vert b\Vert$ is the relative backward error when only the right-hand side may change. For a vector norm and its induced operator norm,A small relative linear-system residual ensures a small relative forward error when the condition number is moderate; an ill-conditioned matrix can amplify it. The bound follows directly from $e=-A^{-1}r$ and $\Vert b\Vert =\Vert A{x}_{\ast }\Vert \le \Vert A\Vert \Vert x_{\ast }\Vert$.^[ref]

For the Jacobi iteration for a three-variable tridiagonal system, the first linear-system residual is $(1,3,1{)}^T$, while the first forward error is $(-1/2,-1,-1/2{)}^T$. In the Euclidean norm, the relative forward error is $\sqrt{3/28}\approx 0.3273$ and the relative linear-system residual is $\sqrt{11/120}\approx 0.3028$. Its spectral condition number of a positive-definite matrix is $(4+\sqrt{2})/(4-\sqrt{2})\approx 2.094$, so the bound is about $0.6340$. The bound is a guarantee, not an equality. In floating-point arithmetic, recompute the linear-system residual from the current vector when checking termination; a small update alone need not certify a small forward error.