Morozov discrepancy roots exist and converge for nonzero exact data

Because $y\in \mathrm{Ran}A$, $\mathrm{dist}(y_j,\overline{\mathrm{Ran}A})\le \mathrm{\parallel }{y}_j-y\mathrm{\parallel }\le {\delta }_j<\tau {\delta }_j$. The upper endpoint condition is in the Given data. By [F1], the endpoint limits supply finite $0<a_j<b_j$ with $r_{y_j}(a_j)<\tau {\delta }_j<r_{y_j}(b_j)$. The residual is continuous on $[a_j,b_j]$, so [F11] gives at least one root in that positive interval.

If endpoint validation fails, the algorithm returns incompatible-endpoints immediately. Otherwise it evaluates the initial residual once, performs at most $M$ endpoint-search iterations, and, only after a bracket is found, at most $N$ bisection iterations. Each search or bisection iteration uses one residual evaluation, so every finite-budget execution terminates after at most $M+N$ loop iterations and at most $M+N+1$ residual evaluations.

Put $T=A{A}^{\ast }$ and $L_{\lambda }=\lambda (T+\lambda I{)}^{-1}$. By [F1], $\mathrm{\parallel }{L}_{\lambda }\mathrm{\parallel }\le 1$, so the reverse triangle inequality gives $\mathrm{\mid }{r}_{y_j}(\lambda )-r_y(\lambda )\mathrm{\mid }\le \mathrm{\parallel }{L}_{\lambda }(y_j-y)\mathrm{\parallel }\le {\delta }_j\mathrm{.}$ At any root ${\lambda }_j$, this implies $(\tau -1){\delta }_j\le r_y({\lambda }_j)\le (\tau +1){\delta }_j\mathrm{.}$

The intertwining identity $(A{A}^{\ast }+\lambda I)A=A(A^{\ast }A+\lambda I)$ and [F5] imply $L_{\lambda }A=A\lambda (A^{\ast }A+\lambda I{)}^{-1}$. By [F6], this is the residual multiplier for the exact-data Tikhonov solution, so $r_y(\lambda )=\mathrm{\parallel }{L}_{\lambda }y\mathrm{\parallel }$. For $x^{†}\perp \ker A$, [F3]–[F4] give $x^{†}={\sum }_{t>0}{P}_t{x}^{†}$. The images $A{P}_t{x}^{†}$ for distinct $t$ are orthogonal, since $⟨Au,Av⟩=⟨A^{\ast }Au,v⟩=t⟨u,v⟩$ when $u\in E_t$ and $v$ lies in a different eigenspace. Also $\mathrm{\parallel }A{P}_t{x}^{†}{\mathrm{\parallel }}^2=t\mathrm{\parallel }{P}_t{x}^{†}{\mathrm{\parallel }}^2$. Therefore $\frac{r_y(\lambda {)}^2}{\lambda }={\sum }_{t>0}\frac{\lambda t}{(t+\lambda {)}^2}\mathrm{\parallel }{P}_t{x}^{†}{\mathrm{\parallel }}^2\mathrm{.}$ Each scalar coefficient is at most $1\mathrm{/}4$, because $(t+\lambda {)}^2-4t\lambda =(t-\lambda {)}^2\ge 0$, and for fixed $t>0$ it tends to zero as $\lambda \downarrow 0$. Choose a finite spectral set whose orthogonal tail of $x^{†}$ has squared norm below any prescribed $\epsilon >0$; the tail contribution is at most $\epsilon \mathrm{/}4$, while the finite sum tends to zero. Thus $r_y(\lambda )\mathrm{/}\sqrt{\lambda }\to 0$.

Any bracket returned by [F2] has residual below target at its lower end and at least target at its upper end. Continuity from [F1] and [F11] give a root inside the bracket. Thus the finite procedure retains an exact discrepancy crossing whenever it succeeds.

For every $\epsilon >0$, $L_{\epsilon }$ is injective by [F5], so $r_y(\epsilon )=\mathrm{\parallel }{L}_{\epsilon }y\mathrm{\parallel }>0$ because $y\mathrm{\ne }0$. The residual $r_y$ is nondecreasing by [F1]. If ${\lambda }_j\ge \epsilon$ along an infinite subsequence, then $r_y({\lambda }_j)\ge r_y(\epsilon )>0$ there, contradicting the upper bound in step 1.3 as ${\delta }_j\to 0$. Hence ${\lambda }_j\to 0$.

From step 1.3, ${\delta }_j\mathrm{/}\sqrt{{\lambda }_j}\le r_y({\lambda }_j)\mathrm{/}((\tau -1)\sqrt{{\lambda }_j})\to 0$ by step 1.4. Step 2.2 already gives ${\lambda }_j\to 0$, so [F7] proves convergence of the Tikhonov solutions to $x^{†}$.