Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This might not be very difficult, but I think I may have gotten a little confused.

Suppose we are given a matrix A, and would like to find the vector x of modulus 1 which maximises the product xt A x (xtranspose times A times x) Consider the following iteration: We start with some vector y of modulus 1, find the vector z of modulus 1 which maximises zt A y, and then put y=z and continue the iteration.

Question1: Will this work? i.e. Is the fixed point of this procedure merely a local maximiser or global too? And does that depend on any properties of the matrix A?

Question2: Will the goal function zt A y increase in every iteration?

share|improve this question
    
Some further assumption is in order, like e.g. $A$ invertible, otherwise this procedure may generate a sequence within the kernel of $A$ –  Pietro Majer Jun 28 '11 at 13:08
add comment

2 Answers

Assuming A is square (so xt A x makes sense).

For a fixed y and A, the vector z that maximizes zt A y is z = A y / ||A y||_2 (Cauchy Schwartz) now, y_new = A y / ||A y||_2. Then the new maximizer z_new = A^2 y / ||A^2 y||_2 and so on.

  1. Just a guess: Seems like we are dependent on the initial value y.

  2. If A is a contraction the obj_new = zt A^2 y will potentially decrease.

share|improve this answer
add comment

Assuming $A$ invertible, the sequence started with $x_0:=y$ is $x_m:=\frac{A^m y}{\|A^m y\|}$, which is the classical power iteration; you can find a discussion on its asymptotic behavior on the given link or in most textbooks on numeric analysis and linear algebra. To get a picture of what happens, first complexify, and change basis writing $A$ in Jordan form. Clearly, the study is reduced to each single Jordan block, a matrix of the form $B:=\lambda I+N$, with idempotent $N$. In this case you can exactly write down the corresponding sequence $x_m$ (note that the matrix $N$ gives a harmless polynomial contribution, and that the non-convergence is linked to non-real eigenvalues. It also follows easily that, if the principal eigenvalue of $A$ is real positive, there is convergence to an eigenvector of its for almost all $y$. In particular, in general, not the maximizer you are looking for).

edit. Since $(x\cdot Ax)=(x\cdot A^S x)$ where $A^S:=\frac{1}{2}(A+A^T)$ is the symmetric part of $A$ you can use $A^S$ instead of $A$ in your iteration as suggested by Denis Serre. Since it is diagonalizable with real eigenvalues, in this case you do have convergence to the maximizer for a.e. $y$, by an even simpler analysis.

share|improve this answer
1  
Pietro, Bratt doesn't look for an eigenvalue. Or if it is, it is an eigenvalue of $A^S:=A+A^T$. He could apply the power method to $A^S$. –  Denis Serre Jun 28 '11 at 14:30
    
Well the original question is about the behavior of the iteration he considers, which is $A^m y / \| A^m y \|$. Having clarified this point, he can modify his method as you suggest. –  Pietro Majer Jun 28 '11 at 14:48
add comment

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.