Rebecca Sela (rebeccapaul) wrote in computerscience,
Rebecca Sela

  • Mood:

Linear convergence and number of iterations

I think this is actually an easy question, but I'm feeling dumb, so I figured I'd ask here. (My excuse is that I'm really a statistician, trying to figure out an algorithm.)

What does an algorithm having linear convergence apply about the required number of iterations for convergence (within a fixed tolerance)?

In particular, I have an algorithm (the PCG algorithm, in case you're curious) whose convergence rate is linear in the square root of the condition number. If I could prove that the condition number was O(f(n)), would the number of iterations be O(sqrt(f(n)))? (My advisor thinks so; I can't get my head around it.)

Thanks in advance!
  • Post a new comment


    default userpic