ON A METHOD FOR ESTIMATING THE PARAMETER \(\alpha\) IN A REGULARIZING ALGORITHM FOR SOLVING ILL-CONDITIONED SYSTEMS OF LINEAR ALGEBRAIC EQUATIONS

A. L. DEINEZHENKO, N. I. SABLIN

(Submitted by the scientific seminar of the Research Institute of Nuclear Physics, Electronics, and Automation)

1. Suppose a system of linear algebraic equations is given:

\[ Ax=b, \tag{1} \]

where \(A=\{a_{ij}\}\) is a nonsingular matrix,

\(x=\{x_j\},\ b=\{b_i\},\ i,j=1,2,\ldots,n.\)

If the right-hand side of system (1) is given with some error \(\delta:\|b-\bar b\|\le \delta\), and the matrix \(A\) is ill-conditioned (the condition number of the matrix \(A\), \(k(A)=\|A\|\cdot\|A^{-1}\|\), is large), then the problem of finding the normal solution \(\bar x\) [1] is ill-posed in the sense of Hadamard, since the solution of (1) is unstable.

We shall use the Euclidean norm of a vector \(\|x\|=\left(\sum_{i=1}^{n}x_i\right)^{1/2}\) and the spectral norm of a matrix consistent with it, \(\|A\|=\mu_1=\max \mu_i\), where \(\mu_i\) are the spectral numbers of the matrix \(A\).

1. Consider the functional [1].

\[ M^\alpha[x,A,b]=\|Ax-b\|^2+\alpha\|x\|^2,\quad \alpha>0. \tag{2} \]

According to [1], \(x^{\alpha_i}\), corresponding to the value of the regularization parameter \(\alpha_i,\ i=1,2,\ldots\), and minimizing the functional \(M^\alpha[x,A,b]\), gives a stable approximation to the normal solution of system (1).

To find the minimum of the functional (2), we solve the Euler equation for \(M^\alpha[x,A,b]\) [2].

\[ (A^T A+\alpha E)x^\alpha=A^T b. \tag{3} \]

1. The following theorem is valid.

Theorem 1. Let \(x^\alpha \in R^n,\ x^\alpha\ne 0\), minimize the functional \(M^\alpha[x,A,b]\), and let the regularization parameter \(\alpha \in \{\alpha\},\ i=1,2,\ldots\), be chosen according to the discrepancy principle [3]; then the inequality

\[ \alpha\le \alpha_b=\|A\|^2\frac{\delta}{\|b\|-\delta}. \tag{4} \]

holds.

Proof. From equation (3), \(\alpha E x^\alpha=A^T(b-Ax^\alpha)\),

\[ \alpha \leq \|A\|\,\frac{\|b-Ax^\alpha\|}{\|x^\alpha\|}. \tag{5} \]

We note that

\[ \|x^\alpha\|\geq \frac{\|Ax^\alpha\|}{\|A\|} \geq \frac{\|b\|-\|Ax^\alpha-b\|}{\|A\|}, \]

and \(\|b\|-\|Ax^\alpha-b\|>0\), since otherwise \(M^\alpha[0,A,b]<M^\alpha[x^\alpha,A,b]\), which contradicts the condition of the theorem. Substituting the lower estimate for \(x^\alpha\) into (5), we obtain

\[ \alpha \leq \|A\|^2\, \frac{\|Ax^\alpha-b\|}{\|b\|-\|Ax^\alpha-b\|}. \]

If the regularization parameter is chosen from the discrepancy principle, then \(\|Ax^\alpha-b\|\leq \delta\), and we obtain (4).

Remark: inequality (4) gives an initial approximation in choosing the regularization parameter \(\alpha\) by the discrepancy principle.

1. As was indicated in [4], where inequality (4) was obtained by another method for normalized spaces and a linear bounded operator \(A\), there is no lower estimate for \(\alpha\) in terms of the discrepancy without additional assumptions; therefore an estimate is proposed under the following assumptions.

Theorem 2. If, for some values of the parameter \(\alpha\), the matrix \(A^T A+\alpha E\) is better conditioned than the matrix \(A\) of system (1) with condition number \(k(A)\), then the inequality

\[ \alpha>\alpha_{\mathrm{n}}=\|A\|^2\,\frac{1}{k(A)} \tag{6} \]

is valid.

Proof. Denote by \(\{\gamma_s\}\) and \(\{\nu_s\}\), \(s=1,2,\ldots,n\), the characteristic numbers of the matrices \(A^TA+\alpha E\) and \(A^TA\), respectively, arranged in nondecreasing order. Then \(\gamma_1=\nu_1+\alpha\), \(\gamma_n=\nu_n+\alpha\) ([5], p. 103). Taking into account that \(k(A^TA+\alpha E)<k(A)\) by the condition of the theorem, and that \(\|A\|=\sqrt{\nu_1}\), we obtain (6).

1. In constructing various regularizing algorithms, [6] uses a function employing the spectrum of the operator \(A^*A\) (\(A^*\) is the operator adjoint to \(A\)). The condition number \(k(A^*A)\) is directly related to the spectrum of the operator \(A^*A\). It is of interest to apply a function, defined on \([\alpha_{\mathrm{n}},\alpha_b]\), that characterizes the properties of the operator \(A\), to the study of the behavior of the regularized solutions of system (3).

As such a function we propose

\[ f(\alpha)=\sqrt{k(A^TA+\alpha E)}. \]

Theorem 3. The function \(f(\alpha)\) is defined on \([0,\infty]\), is continuous, decreases monotonically, and its values exhaust the closed interval

\[ [k(A),\,1]. \]

The proof follows from representing \(f(\alpha)\) in the form

\[ f(\alpha)=\sqrt{\,1+\frac{\nu_1-\nu_n}{\nu_n+\alpha}\,} \]

and from the estimates (4) and (6).

References

1. A. N. Tikhonov. On ill-posed problems of linear algebra and a stable method for their solution. Dokl. Akad. Nauk SSSR, 1965, vol. 163, no. 3, 591–594.

2. V. V. Voevodin. Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki, 1969, vol. 9, no. 3, 673–675.

3. V. A. Morozov. On solving functional equations by the regularization method. Dokl. Akad. Nauk SSSR, 1966, vol. 167, no. 3, 510–512.

4. V. A. Vinokurov. Two remarks on the choice of the regularization parameter. Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki, 1972, vol. 12, no. 2, 481–483.

5. J. Wilkinson. The Algebraic Eigenvalue Problem. Moscow, Mir, 1970.

6. A. B. Bakushinskii. A general technique for constructing regularizing algorithms for a linear ill-posed equation in Hilbert space. Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki, 1967, vol. 7, no. 3, 672–677.