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.
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$.