Tikhonov error separates bias, data noise, discretization and solve residual

Assume Countable Choice. Let $X,Y$ be real or complex Hilbert spaces, let $A:X\to Y$ be compact (hence bounded), and let $A_h:X\to Y$ be a bounded discrete operator whose range is a finite-dimensional subspace of $Y$. For $\lambda >0$, define

$R_{\lambda }=(A^{\ast }A+\lambda I_X{)}^{-1}{A}^{\ast },R_{\lambda ,h}=(A_h^{\ast }{A}_h+\lambda I_X{)}^{-1}{A}_h^{\ast }\mathrm{.}$

These maps are well-defined by The shifted Hilbert-space normal operator is invertible with inverse norm at most $1\mathrm{/}\lambda$. Let $x^{†}\in X$, $y=A{x}^{†}$, $y_{\delta }=y+e$ with $\mathrm{\parallel }e\mathrm{\parallel }\le \delta$ and $\delta \ge 0$, and let $\tilde{x}\in X$. Define the exact discrete normal-equation residual

$r_h=(A_h^{\ast }{A}_h+\lambda I_X)\tilde{x}-A_h^{\ast }{y}_{\delta }\mathrm{.}$

Then the following chain is exact:

$x^{†}-\tilde{x}=(x^{†}-R_{\lambda }y)+(R_{\lambda }y-R_{\lambda }{y}_{\delta })+(R_{\lambda }{y}_{\delta }-R_{\lambda ,h}{y}_{\delta })+(R_{\lambda ,h}{y}_{\delta }-\tilde{x})\mathrm{.}$

Its norm satisfies

$\mathrm{\parallel }{x}^{†}-\tilde{x}\mathrm{\parallel }\le \mathrm{\parallel }{x}^{†}-R_{\lambda }y\mathrm{\parallel }+\frac{\delta }{2\sqrt{\lambda }}+\mathrm{\parallel }(R_{\lambda }-R_{\lambda ,h})y_{\delta }\mathrm{\parallel }+\frac{\mathrm{\parallel }{r}_h\mathrm{\parallel }}{\lambda }\mathrm{.}$

The first term is regularization bias, the second is data noise, the third is the regularized-operator discretization difference, and the fourth is the solve residual. The third term receives a numerical bound only when an operator-perturbation bound is supplied: if $\mathrm{\parallel }{R}_{\lambda }-R_{\lambda ,h}\mathrm{\parallel }\le {\eta }_{\lambda ,h}$, it is at most ${\eta }_{\lambda ,h}\mathrm{\parallel }{y}_{\delta }\mathrm{\parallel }$. If residual evaluation returns ${\widehat{r}}_h$ with a certified $\mathrm{\parallel }{r}_h-{\widehat{r}}_h\mathrm{\parallel }\le {\rho }_h$, the last term is at most $(\mathrm{\parallel }{\widehat{r}}_h\mathrm{\parallel }+{\rho }_h)\mathrm{/}\lambda$. If an algorithm has a specified exact-arithmetic stopping output $x_{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}$ and returns a computed output $\tilde{x}$, the last difference can further split as

$R_{\lambda ,h}{y}_{\delta }-\tilde{x}=(R_{\lambda ,h}{y}_{\delta }-x_{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}})+(x_{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}-\tilde{x})\mathrm{.}$

Writing $r_{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}=(A_h^{\ast }{A}_h+\lambda I_X)x_{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}-A_h^{\ast }{y}_{\delta }$, the first term is at most $\mathrm{\parallel }{r}_{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}\mathrm{\parallel }\mathrm{/}\lambda$; the second is the separate returned-output roundoff term. Any bound on that roundoff or on residual-evaluation error requires its own arithmetic hypotheses. For a discretized datum $y_{h,\delta }=A_h{x}^{†}+e$ formed before inversion, put $d_h=(A-A_h)x^{†}=y_{\delta }-y_{h,\delta }$. Let ${\tilde{x}}_h\in X$ be a computed discrete output. The corresponding exact refinement is

$x^{†}-{\tilde{x}}_h=(x^{†}-R_{\lambda }y)+(R_{\lambda }y-R_{\lambda }{y}_{\delta })+R_{\lambda }{d}_h+(R_{\lambda }-R_{\lambda ,h})y_{h,\delta }+(R_{\lambda ,h}{y}_{h,\delta }-{\tilde{x}}_h),$

so the forward residual discarded by quadrature or collocation is counted before inversion as $R_{\lambda }{d}_h$, with $\mathrm{\parallel }{R}_{\lambda }{d}_h\mathrm{\parallel }\le \mathrm{\parallel }{d}_h\mathrm{\parallel }\mathrm{/}(2\sqrt{\lambda })$. The separate operator discretization and solve terms remain. For this refined chain, define $r_{h,h}=(A_h^{\ast }{A}_h+\lambda I_X){\tilde{x}}_h-A_h^{\ast }{y}_{h,\delta }$; then $\mathrm{\parallel }{R}_{\lambda ,h}{y}_{h,\delta }-{\tilde{x}}_h\mathrm{\parallel }\le \mathrm{\parallel }{r}_{h,h}\mathrm{\parallel }\mathrm{/}\lambda$. If its evaluation returns ${\widehat{r}}_{h,h}$ with a certified $\mathrm{\parallel }{r}_{h,h}-{\widehat{r}}_{h,h}\mathrm{\parallel }\le {\rho }_{h,h}$, the last term is at most $(\mathrm{\parallel }{\widehat{r}}_{h,h}\mathrm{\parallel }+{\rho }_{h,h})\mathrm{/}\lambda$. No rate for $d_h$, no operator perturbation estimate, and no floating-point residual bound is implicit. When $X,Y$ are finite-dimensional and $b=A{x}^{†}+e$, the same identity is the canonical Tikhonov bias/noise formula

$x^{†}-A_{\lambda }^{\mathrm{\#}}b=(I-A_{\lambda }^{\mathrm{\#}}A)x^{†}-A_{\lambda }^{\mathrm{\#}}e,A_{\lambda }^{\mathrm{\#}}=(A^{\ast }A+\lambda I{)}^{-1}{A}^{\ast }\mathrm{.}$

Here $\lambda$ is the coefficient of $\mathrm{\parallel }x{\mathrm{\parallel }}^2$ in $\mathrm{\parallel }Ax-b{\mathrm{\parallel }}^2+\lambda \mathrm{\parallel }x{\mathrm{\parallel }}^2$.

For stored finite matrices, Computed augmented Tikhonov solves have certified residual and output-error bounds supplies the concrete augmented-QR or independently certified-residual application: take its $\rho$ as ${\rho }_h$ with datum $y_{\delta }$, or as ${\rho }_{h,h}$ with datum $y_{h,\delta }$. It bounds returned-output roundoff for the exact direct-solve target and retains explicit real/complex realization, square-root representation, successful-operation and nonsingularity conditions.

Hansen's slides write the penalty as $\mathrm{\parallel }Ax-b{\mathrm{\parallel }}^2+{\lambda }_H^2\mathrm{\parallel }x{\mathrm{\parallel }}^2$; there $\lambda ={\lambda }_H^2$. Clason's coefficient $\alpha$ in front of the squared penalty maps directly to this item's $\lambda$. The concrete finite-matrix allowance is supplied by Computed augmented Tikhonov solves have certified residual and output-error bounds; for general Hilbert-space computations any residual certificate still needs its own stated arithmetic realization.