Finding approximation of largest eigenvalue

Question

Given the following matrix, find an approximation of the largest eigenvalue. $$ A = \begin{bmatrix} 3 & 2 \\ 7 & 5 \\ \end{bmatrix} $$

And I was also given $$\vec x= \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} $$

How my professor solves this is by calculating the slopes of $A\vec x = \vec b_1$, $A^2 \vec x = \vec b_2$, $A^3 \vec x = \vec b_3$ and so on until we get the slope of $\vec b_i$ converging to the same value. Then when we get the approximated $\vec b$, he plug into $A \vec b = \lambda \vec b$, and the corresponding $\lambda$ is the largest eigenvalue.

Since slope is $\frac yx$ , it works fine for $2 x 2$ matrix. But how do I apply this method for a bigger matrix?

Answer 1

Here's a hint: You want to determine when $\mathbf{b}_n$ is a near-scalar multiple of $\mathbf{b}_{n-1}$. In $\mathbb{R}^2$, (nonzero) vectors are scalar multiples of one another iff their slopes are equal. A possibly more useful definition is that two vectors $\mathbf{v}$ and $\mathbf{w}$ are scalar multiples of one another if and only if

$$\hat{\mathbf{v}} = \pm\hat{\mathbf{w}},$$

where

$$\hat{\mathbf{v}} = \frac{\mathbf{v}}{|\mathbf{v}|},$$

which extends more nicely to multiple dimensions.

Answer 2

You normalize the vector at each iteration by dividing by its length, and wait until the resulting sequence of unit vectors has gotten close enough to converging for your purpose. (This is called the power method. It's pretty much the worst iterative method for eigenvalues there is, but it is the theoretical basis for lots of better methods.)

This is similar to what you're doing when you measure the slope in the 2D case, except in that case you divide by $x$ instead of dividing by $\sqrt{x^2+y^2}$. The point is that all that matters is the direction, not the magnitude.

Answer 3

The method you are thinking of is called Power Iteration. More formally, take any vector $x_0\ne 0$. (In practice, it is good to choose $x_0$ randomly. Then define

$$ x_k := \frac{Ax_{k-1}}{\|Ax_{k-1}\|_2}, \quad k\in\{1,2,\ldots\} $$

With high probability, $x_k$ will converge to an eigenvector of $A$ corresponding to the largest eigenvalue $\lambda_1$ of $A$ with

$$ \lambda_1 = \lim_{k\to\infty} x_k^T Ax_k. $$

In practice, in computer arithmetic, this method is numerically stable. For a better method, see for example, this.

Answer 4

What you mention, is a known numerical analysis method for the approximation of the largest (by absolute value) eigenvalue of a matrix.

Let $A\in \mathbb R^{n\times n}$ have $n$ linearly independent eigenvalues $\{ u \}_{i=1}^n$ as well as a unique eigenvalue $λ_1$ such that : $|λ_1| < |λ_2| \leq \dots \leq |λ_n|$ where $λ_1 \in \mathbb R$ and $u_1 \in \mathbb R^n$ : $Au_1=λ_1u_1.$

The method "Power Iteration" :

$$\begin{cases} x_k= Ax_{k-1} \to x_k = A^kx_0 \quad k=1,2,\dots \\ x_0 \end{cases}$$

Thorem : The method "Power Iteration" converges $\forall x_0$ (that is adequate for the problem given) and it is :

$$\lim_{k\to \infty} ε_k\frac{x_k}{||x_k||_2}=u_1$$

$$\lim_{k \to \infty} \frac{x_{k,i}}{x_{k-1,i}}=λ_1 \quad \forall \space i=1,2,\dots,n \quad \text{with} \quad u_{1,i} \neq 0 $$

where $\{ ε_k\}_{k=1}^\infty = \{ \pm1\}$ and $u_1$ eigenvector of $A$ with $||u_1||_2=1$.

I've given you a formal explanation of the method according to my old notes and my knowledge, for more, check here.