Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  copper.hat May 25 '12 at 5:22
    
@copper.hat i have edited sir –  srijan May 25 '12 at 6:07
    
What is the question? How to choose $\beta$? –  copper.hat May 25 '12 at 6:12
    
Sorry, what is the question? Are you asking how to analyze the sequence $X_k$? –  copper.hat May 25 '12 at 6:15
    
@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. –  srijan May 25 '12 at 6:20

1 Answer 1

up vote 3 down vote accepted

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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