2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Some further assumption is in order, like e.g. $A$ invertible, otherwise this procedure may generate a sequence within the kernel of $A$ $\endgroup$
    – Pietro Majer
    Jun 28, 2011 at 13:08

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Denis Serre
    Jun 28, 2011 at 14:30
  • $\begingroup$ 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. $\endgroup$
    – Pietro Majer
    Jun 28, 2011 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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