4
$\begingroup$

Given $A \in \mathbb{R}^{n \times n}$, a SPD matrix, and a vector $b \in \mathbb{R}^n$, it is possible to solve the problem $$\min_x \| Ax - b\|$$
with the conjugate gradient method. Its algorithm basically is

$r_0 = b - Ax_0\\ p_0 = r_0\\ k = 0\\ \text{while } r_k \text{ is not small enough}\\ \ \ \ \ \ \ \alpha_k = \displaystyle \frac{ \|r_k\|^2 }{\langle p_k, Ap_k \rangle}\\ \ \ \ \ \ \ x_{k+1} = x_k + \alpha_k p_k\\ \ \ \ \ \ \ r_{k+1} = r_k - \alpha_k Ap_k\\ \ \ \ \ \ \ \beta_k = \frac{ \| r_{k+1} \|^2}{ \| r_k \|^2 }\\ \ \ \ \ \ \ p_{k+1} = r_{k+1} + \beta_k p_k\\ \ \ \ \ \ \ k = k+1\\ \text{end while}\\ \text{return } x_{k+1}$

I wonder what happens if I used the same algorithm for a function like $f(x) = Ax + r(x)$, where $r(x)$ usually is much smaller then $f(x)$ (in the norm sense). To be more precise, I use the same algorithm but changing the formulas for $\alpha_k$ and $r_{k+1}$ by

$\alpha_k = \displaystyle \frac{ \|r_k\|^2 }{\langle p_k, f(p_k) \rangle},\\ r_{k+1} = r_k - \alpha_k f(p_k).$

Is the conjugate gradient method flexible at the point I can do this? What condition I need on $r$ to make it work? One possibility is $r$ being a SPD matrix, but this is an obvious one.

$\endgroup$
1
$\begingroup$

Unlikely without special assumptions placed on $f$. The CG algorithm requires $x^T A x \not = 0$ to avoid division by zero. If $A$ is symmetric positive definite and if $v$ is an unit eigenvector of $A$ corresponding to the eigenvalue $\lambda$, then $B = A - \lambda vv^T$ is a symmetric positive semi-definite matrix. In particular, $v^T B v = 0$. If $\lambda$ is the smallest eigenvalue of $A$, then many would consider $f(x) = Bx$ to be only a small perturbation of the original map, especially if the largest eigenvalue of $A$ is much larger than $\lambda$.

$\endgroup$
  • $\begingroup$ Ok, $B$ is a small perturbation o the original map and has the problem of $v^T B v$ vanishing, where $v$ is the eigenvector associated to the smallest eigenvalue of $A$. It means that the algorithm crashes in a certain subspace. Since this subspace has null measure, I think you would agree that there is zero probability of observe crashing. Regardless, what happens when the algorithm doesn't touch this subspace? Is it going to converge? $\endgroup$ – Integral Aug 22 at 16:38
  • 1
    $\begingroup$ In practice, it is not division by zero which should concern you, but the near occurrence of the problem. Tiny numbers are frequently the result of subtractions which had significant loss of accuracy (subtractive cancellation) and zeros are result of products of tiny numbers being flushed to zero. When writing robust numerical software this is a serious issue. If your investigation assumes exact arithmetic, then you are hunting statements which are true for all right hand sides and you should think twice before disregarding a set simply because it has measure zero. $\endgroup$ – Carl Christian Aug 22 at 21:17
  • 1
    $\begingroup$ On a strictly theoretical level, the convergence analysis of the CG algorithm draws heavily on the fact that the matrix is both symmetric and positive definite. There is no reason to expect it to work if either one of these properties is sacrificed in even the slightest degree. $\endgroup$ – Carl Christian Aug 22 at 21:19
  • 1
    $\begingroup$ @Integral I forgot to add your username to trigger the automatic notification for my replies to your comment. $\endgroup$ – Carl Christian Aug 23 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.