Date: 08/25/07 (Algorithms)    Keywords: no keywords

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!

Source: http://community.livejournal.com/algorithms/92024.html