# Which preconditioners make Richardson iteration convergent?

Suppose we solve an $$m\times n$$ full-rank system of equations $$Ax=b$$ by iterating the following for a small enough $$\mu>0$$

$$x=x+\mu B(b-Ax)$$

Is there a nice description of kinds of $$B$$ which make this iteration convergent? For instance, for $$n=1$$, $$A,B$$ can be viewed as vectors, and this iteration converges iff their dot product is positive. What about $$n>1$$?

1. $$B=A^\dagger$$ is (trust-region) Newton's method
2. $$B=A^T$$ is gradient descent on least-squares objective
3. $$B=I$$ is modified Richardson iteration, only works for positive-definite $$A$$

Curious if there's a family of methods between 2. and 3. -- converges for any full-rank $$A$$, but without relying too much on $$A^Ty$$ (much more expensive than $$Ax$$ in my application)

Edit

• It seems sufficient that $$(BA)^T+BA\succ 0$$. This means $$\mu$$ can be made small enough to ensure each step is contractive. However, it is not necessary since for not normal $$BA$$, convergence may happen after initial transient "hump".

• it is necessary (but not sufficient) that all eigenvalues of $$BA$$ have a positive real part. Negative eigenvalue means you'll be pushed away from solution in those direction.

• which means it is necessary that $$B=-SA^\dagger$$ for some stable matrix $$S$$ when $$n=m$$

• It is sufficient that $$B=A^T P$$ for some positive definite $$P$$. This ensures update has form to $$I-\mu C$$ with positive definite $$C$$

• Last condition seems too restrictive, since we could use $$B=\text{sign}(A^T)$$

Found the answer in Francesca Rapetti course notes here, preconditioned Richardson can be made convergent iff $$BA$$ is positive stable, which is true iff $$B=SA^\dagger+Z^T$$ for some positive stable $$S$$ and $$Z^TA=0$$.
So for instance for the following matrix $$PA=\left( \begin{array}{cc} 2 & 100 \\ -300 & 100 \\ \end{array} \right)$$
Would set $$\alpha=\frac{51}{15100}$$
Which gives $$\rho(I-\alpha PA)=1$$ (notebook)