1
$\begingroup$

I am working on a iteration method to compute the generalized inverse of a matrix $A$ of rank $r$

Iteration method is

$X_{k+1} = X_{k} + \beta X_{k} (I - A X_{k}) $

where notations are as follows

$A$ is given $n\times n$ matrix

$\beta$ is any non zero scalar such that $ 0< \beta\leq 1 $

and my initial approximation is $X_{0} = \beta A ^t$ and my condition for convergent is as follows

$X_{k}$ are sequence of approximations to compute generalized inverse say $X$of a matrix $A$. Though my method is convergent but number of iterations it is taking is higher than usual one. My condition of convergence if $\max_{1\leq i\leq r} | 1 - \lambda_i (\beta AA^t) |<1$. $\lambda$ denotes eigenvalue of matrix.

Can anybody suggest me any other value of $X_{0}$ and $\beta $? Any kind of help or hint will be helpful to me. Please pardon me if my question is inappropriate for this community.

I have edited my question Thanks

$\endgroup$
6
  • $\begingroup$ It would help if you gave some idea of what problem you are solving? Clearly you can choose $X_{k+1} = X_k$, and this will minimize the norm, but I am sure there are other conditions involved which you haven't stated. $\endgroup$
    – copper.hat
    May 25, 2012 at 5:22
  • $\begingroup$ @copper.hat i have edited sir $\endgroup$
    – Srijan
    May 25, 2012 at 6:07
  • $\begingroup$ What is the question? How to choose $\beta$? $\endgroup$
    – copper.hat
    May 25, 2012 at 6:12
  • $\begingroup$ Sorry, what is the question? Are you asking how to analyze the sequence $X_k$? $\endgroup$
    – copper.hat
    May 25, 2012 at 6:15
  • $\begingroup$ @copper.hat sorry to trouble you. is there any alternate way to choose beta or initial approximation so that my condition of convergence remains the same. $\endgroup$
    – Srijan
    May 25, 2012 at 6:20

1 Answer 1

4
$\begingroup$

As far as I can see, your main concern is due to the large number of steps that your method needs to converge. Hence, you want to use a better initial approximation $X_0$ to arrive at the convergence phase faster.

It should be noted that the main point lies in the iterative methods that you are using, i.e. $X_{k+1}=X_k+\beta X_k(I-AX_k)$, where $\beta$ is a free parameter. This is only the dampled Newton's method on the matrix equation $AX=I$. On the other hand, when you are dealing with matrix inversion, there is no need to use the dampled Newton method, since although it has a free parameter, its convergecne order is mostly LINEARLY. Hence, the best way is to use the quadratical method by choosing $\beta=1$, which results in the well-known Schulz method $$X_{k+1}=X_k(2I-AX_k).$$ Before proceeding, I want to state that low order methods (even the above second-order method) require too much steps to arrive at the convergence phase. Hence I finally would like to suggest you to use the cubically method of Chebyshev given below, or any of the other high order methods (of orders 7,8,9,10) to have a better feedback: $$X_{k+1}=X_k(3I-AX_k(3I-AX_k)).$$

Regarding your need to a better initial approximation, it would be perfect to use the optimal initial choice originally attributed to "V. Y. Pan and R. Schreiber, An improved Newton iteration for the generalized inverse of a matrix, with Applications, SIAM J. Sci. Stat. Comput., 12 (1991), 1109-1131." as follows:

$$X_0=\frac{2}{\sigma_1^2+\sigma_r^2}A^*,$$

wherein $\sigma_1$ and $\sigma_r$ stand for the largest and the smallest singular values of the input matrix $A$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .