3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I've given you a full explanation and representation of the method used down below, make sure to check it out ! $\endgroup$ – Rebellos Dec 7 '17 at 1:23
  • $\begingroup$ It's very helpful thank you! $\endgroup$ – dembrownies Dec 7 '17 at 1:28
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'll try to apply this to the problem and see how it works out. Thank you ! $\endgroup$ – dembrownies Dec 7 '17 at 1:21
  • $\begingroup$ @dembrownies Great. Let me know if you have any more questions. $\endgroup$ – Carl Schildkraut Dec 7 '17 at 2:13
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ that makes more sense. thank you! $\endgroup$ – dembrownies Dec 7 '17 at 1:20
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Its the power itaratin method

https://en.wikipedia.org/wiki/Power_iteration

The main reason way it works is that, if J is the Jordan canonical (possibly diagonal) form of A, which "contains" A's eigenvalues :

$$A=P^{-1}JP \\ A^2=P^{-1}JPP^{-1}JP=P^{-1}J^2P\\ A^3=P^{-1}J^2PP^{-1}JP=P^{-1}J^3P\\ ...\\ A^n=P^{-1}J^{n-1}PP^{-1}JP=P^{-1}J^nP$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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