Suppose matrix $A$ is positive semidefinite and $I\succeq A$. Prove that the iteration

$$Y_0=0,\hspace{3mm} Y_{n+1}=\frac{1}{2}(A+Y_n^2)$$

is nondecreasing (that is, $Y_{n+1}\succeq Y_n$ for all $n$) and converges to the matrix $I-(I-A)^{1/2}$.

My plan is to use induction, i.e., assume $Y_n\succeq Y_{n-1}$ and try to prove $Y_{n+1}\succeq Y_n$.

It is easy to see $Y_{n+1}-Y_n=\frac{1}{2}(A-I)+\frac{1}{2}(I-Y_n)^2$. It turns out to be that given $(I-Y_{n-1})^2\succeq (I-A)$, how to show $(I-Y_n)^2\succeq (I-A)$?

For the second part, I guess we need to show $\lim_{n\rightarrow\infty}(I-Y_n)^2=(I-A)$.

Can anyone give me a hint?


Hint. Orthogonally diagonalise $A$ and the problem reduces to the scalar case.

  • $\begingroup$ Thanks. The second half of your hint helps a lot. $\endgroup$ – mining Sep 8 '13 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.