Question

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?

Answer 1

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.

Answer 2

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.