1

I've been stuck on this problem for few days now. Given a quadratic function of the form $f(x) = \frac{1}{2} \langle x,Qx \rangle + \langle c, x \rangle $, where $ Q = B + \sum_{j=1}^s a_j a_j^T $ is of dimension n and B is positive definite, I need to find how many iterations it will take for the Preconditioned Conjugate Gradient to converge with a preconditioner $ V = B^{-1} $.

My thoughts so far is that if $ Q $ has $ k \leq n $ distinct eigenvalues, then the Conjugate gradient converges in k steps. I tried to apply the preconditioner by changing the variable $ x = V^{\frac{1}{2}}y $ and got the expression for $ V^{\frac{1}{2}}QV^{\frac{1}{2}} = I + (B^{-1})^\frac{1}{2} \sum_{j=1}^s a_j a_j^T (B^{-1})^\frac{1}{2}$ .

If I'm not mistaken, $ V^{\frac{1}{2}}QV^{\frac{1}{2}} $ should be positive definite too, because it's a sum of an identity matrix with a semi-positive definite matrix? So it should converge in less than n steps?

And same question for Newton's method: is it supposed to converge in one iteration for a quadratic function?

Any help would be appreciated!

Fedzchen
  • 21
  • 2
  • As long as $s < n$, your $V^{1/2} Q V^{1/2}$ should still have less than $n$ distinct eigenvalues so conjugate gradients should converge in less than $n$ steps. – VHarisop Feb 17 '21 at 06:16
  • @VHarisop that clarifies everything, thank you so much! – Fedzchen Feb 17 '21 at 14:32
  • @VHarisop out of curiosity, how does the number of eigenvalues depend on s? – Fedzchen Feb 17 '21 at 15:44
  • For any symmetric matrix $A$ with eigenvalues $\lambda_i$, the eigenvalues of $I + A$ are $1 + \lambda_i$. In your case, $A$ has rank at most $s$ so at most $s$ of these eigenvalues ($1 + \lambda_i$) can be distinct (all the other ones will be equal to $1$). – VHarisop Feb 17 '21 at 16:34
  • @VHarisop thank you very much! – Fedzchen Feb 17 '21 at 18:09

0 Answers0