3
$\begingroup$

Let $A \in \mathbb{R}^{N \times N}$ be symmetric.

a) The respective Eigenvalue $\lambda$ to an approximately defined Eigenvector $0 \neq x \mathbb \in {R}^n$ from $A$ has to be calculated, so that $||Ax-\lambda x||^2_2$ is minimal. Specify a formula to calculate $\lambda$.

This is an introductory class to numerical methods. Can I use here the same formula that I have always used? Considering $Ax=\lambda x$, solving the linear system $(A-\lambda I)x=0$ should give us the (approximated) Eigenvalue $\lambda$, right? Why wouldn't $||Ax-\lambda x||^2_2$ be $0$?

$A$ has furthermore the Eigenvalues $\lambda_1 \leq \lambda_2 \leq ...\leq \lambda_n$. Show that:

b) $\lambda_1 x^T x \leq x^T Ax \leq \lambda_n x^T x$

I think I'm missing something. Can I simply use $Ax=\lambda x$? Thus $x^T Ax$ is the same as $\lambda x^T x$, as $\lambda$ can be any arbitrary Eigenvalue between the smallest ($\lambda_1$) and the largest ($\lambda_n$), it follows that $\lambda_1 x^T x \leq \lambda x^T x \leq \lambda_n x^T x$ is valid.

c) $\lambda_1 = \min_{x \neq 0} \frac{x^T Ax}{x^T x}= \min_{x^T x = 1} x^T Ax$

I'm a little lost here. I would attempt to use the same trick again, thus $\lambda_1 = \min_{x^T x = 1} x^T \lambda x = \min_{x^T x = 1} \lambda x^T x = \min_{x^T x = 1} \lambda$. However I don't think is proving what they want?

d) $\lambda_n = \max_{x \neq 0} \frac{x^T Ax}{x^T x}= \max_{x^T x = 1} x^T Ax$

Analogue to c)

Many thanks in advance!


Edit: Thanks to Martin I know understand better what they want.

For b) and following the tip that I can diagonalize the Matrix, I now have

Let $D=Q^T AQ$. The eigenvalues of A are in the diagonal from $D$. With $y=Q^T x$ it follows that:

$x^T Ax=x^T Q D Q^T x = y^T D y = \sum \lambda_i y_i^2$

and therefore

$\lambda_1 x^T x=\lambda_1 y^T y \leq \sum \lambda_i y_i^2 \leq \lambda_n y^T y = \lambda_n x^T x$

I think I'm very near to being able to answer c) and d) but I'm still missing something. Any help? Thanks!

  • 0
    The diagonal matrix would contain exactly the eigenvalues. But the methods you are considered are used in numerical analysis precisely because finding $Q$ is far from easy.2012-06-15

1 Answers 1

3

The point is that solving the system $A-\lambda I=0$ is usually computationally intensive. It might be easy when $A$ is $3\times3$, but there are real life applications where your matrix can be huge. That's why there are lots of numerical methods to approximate eigenvalues, and that's what they are teaching you in your class.

In a), $A$ and $x$ are given, and they want you to find the $\lambda$ that minimizes the formula; with that $\lambda$, you can test whether it really looks like an eigenvalue or not (there are different methods for this, too).

So in a) you want to minimize $ ||Ax-\lambda x||^2_2=\langle Ax-\lambda x,Ax-\lambda x\rangle=\langle Ax,Ax\rangle - 2\lambda\langle Ax,x\rangle + \lambda^2\langle x,x\rangle. $ This is a quadratic with positive degree-two coefficient, so its mininum occurs at "$-b/2a$", i.e. at $ \lambda=\frac{2\langle Ax,x\rangle}{2\langle x,x\rangle}=\frac{\langle Ax,x\rangle}{\langle x,x\rangle}. $

Edit: for c) and d), you have already proven that $ \lambda_1 x^Tx\leq x^TAx\leq \lambda_n x^Tx, $ so

$ \lambda_1 \leq \frac{x^TAx}{x^Tx}\leq \lambda_n. $ You achieve the minimum by using an eigenvector for $\lambda_1$, and similarly for $\lambda_n$ and the maximum. This shows the first equality in both c) and d).

For the second equality, if $z^Tz=1$ then $ z^TAz=\frac{z^TAz}{z^Tz}, $ so $ \lambda_1\leq z^TAz\leq\lambda_n. $ To achieve the equality, let $z$ be an eigenvector for $\lambda_1$; then put $x=z/(z^Tz)^{1/2}$. Then $ x^TAx=\frac{z^TAz}{z^Tz}=\lambda_1\,\frac{z^Tz}{z^Tz}=\lambda_1. $ And we proceed similarly for $\lambda_n$.

  • 0
    I'm sorry, I still don't get it Martin... so it satisfies $z^T z=1$, what does this give me? Could you please edit your answer and elaborate on c)? Many many thanks!2012-06-16