next up previous
Next: About this document ...

Chapter 4 Eigenvector and Eigenvalue

[Def] $A \in {I\!\!R}^{n \times n} , v \ne 0$ If $Av = \lambda v$ , then v is called the eigenvector of A associated with the Eigenvalue $\lambda$.

${\varphi}_{\lambda} = \{ v \vert Av = \lambda v \} $is a subspace of ${I\!\!R}^n$ is called the Eigen Space of A associated with $\lambda$

< Characteristic Polynomial : $det( \lambda I - A) = P (\lambda)$ >

If $\lambda$ is an eigenvalue of A , then

1. $det( \lambda I - A ) = 0$ 2. $( \lambda I - A )$ is singular

$\Rightarrow$ If $\lambda$ is an eigenvalue $\Rightarrow P ( \lambda ) = 0 $

$\left \{ \matrix{
{{d x_1 (t)} \over {dt}} = a_{11} x_1 + a_{12} x_2 + \cdots ...
... (t)} \over {dt}} = a_{n1} x_1 + a_{n2} x_2 + \cdots + a_{nn} x_n \cr
}\right $ $\Rightarrow {{dx} \over {dt}} = Ax$

The solution is of the form x(t) = f(t) v

$\Rightarrow$ differentiate with respected to t .

$\Rightarrow {x^'} (t) = {f^'} (t) v$

because f' (t) v = A f(t) v $\Rightarrow {f^'}(t) v = f(t) Av $ $\Rightarrow Av = {{{f^'} (t)} \over {f(t)}} v$

Let ${{{f^'} (t)} \over {f(t)}} = \lambda \Rightarrow f(t) = c e^{\lambda t}$

$\Rightarrow Av = \lambda v
\par\Rightarrow Av = c e^{\lambda t} v$

1. Power Method ( Find MAX. eigenvalue ) 2. Inverse Power Method ( Find MIN. eigenvalue) 3. Shift Inverse Power Method ( Find the eigenvalue close to fixed u )

Power Method :

If ${\lambda}_1 , {\lambda}_2 , \cdots , {\lambda}_n $ are eigenvalue of A with $\vert {\lambda}_1 \vert > \vert {\lambda}_1 \vert
\geq \vert {\lambda}_3 \vert \geq \cdots \geq \vert {\lambda}_n \vert$ and $v_1 , v_2 , \cdots , v_n $ are eigenvectors and linear indep. associated with ${\lambda}_1 , {\lambda}_2 , \cdots , {\lambda}_n $ respectively .

STEP : Let q be any vector in ${I\!\!R}^n$ consider the sequence $q , Aq , A^2 q , \cdots , A^n q$

because $\{ v_1 , v_2 , \cdots , v_n \}$ form a basis of ${I\!\!R}^n$

$\Rightarrow q = c_1 v_1 + c_2 v_2 + \cdots + c_n v_n $

W.l.o.G. ( Without loss of Generality )

We may assume

$ q = v_1 + v_2 + \cdots + v_n$ $\Rightarrow$ $Aq = A ( v_1 + v_2 + \cdots + v_n )$ = ${\lambda}_1 v_1 + {\lambda}_2 v_2 + \cdots + {\lambda}_n v_n$

$\Rightarrow$ A2 q = ${\lambda}^2_1 v_1 + {\lambda}^2_2 v_2 + \cdots + {\lambda}^2_n v_n$

In general ,

An q = ${\lambda}^n_1 v_1 +
{\lambda}^n_2 v_2 + \cdots + {\lambda}^n_n v_n $ =
${\lambda}^n_1 ( v_1 + {( {{\lambda}_2} \over {{\lambda}_1} )}^n v_2
+ \cdots +
{({ {{\lambda}_n} \over {{\lambda}_1} })}^n v_n)$

$\Rightarrow$ ${ {A^n q} \over {\lambda}^n_1} $ = $v_1 + {( { {{\lambda}_2} \over {{\lambda}_1} } )}^n v_2$ + $\cdots$ + ${( { {{\lambda}_n} \over {{\lmbda}_1} } )}^n v_n $
= $v_1 + \varepsilon ({ {{\lambda}_2} \over {{\lambda}_1} })$

An q = ${\lambda}^n_1 ( v_1 + \varepsilon ({ {{\lambda}_2} \over {{\lambda}_1} }))$where $ \varepsilon ({{{\lambda}_2} \over {{\lambda}_1}}) \rightarrow 0 $ when $ n \rightarrow \infty $

Let $\phi (x)$ be a linear functional [ for example : $\phi (x) = {\Vert x \Vert}_{\infty} $]

${
{\phi( {\lambda}^{n+1}_1
( v_1 + \varepsilon ({ {{\lambda}_2} \over
{{\lam...
...\lambda}^n_1
( v_1 + \varepsilon ({ {{\lambda}_2} \over
{{\lambda}_1} }) ) }}$= ${\lambda}_1 {{\phi ( v_1 + \varepsilon ({{{\lambda}_2} \over {{\lambda}_1}}) ) } \over {\phi ( v_1 + \varepsilon ({{{\lambda}_2} \over {{\lambda}_1}}) ) }}$= ${\lambda}_1 $

Example : 4.3.5

A = $\left [ \matrix{ 9 & 1 \cr 1 & 2 \cr } \right ]$ , q0 = ${\left [ \matrix{ 1 & 1 \cr } \right ]}^T$

[Sol]

STEP 1. Find a sequence $q_0 , A q_0 , \cdots , A^n q_0$A q0 = $\left [ \matrix{ 9 & 1 \cr 1 & 2 \cr } \right ]$ $\left [ \matrix{ 1 \cr 1 \cr } \right ]$ = $\left [ \matrix{ 10 \cr 3 \cr } \right ]$ = q1

STEP 2. $\phi (x)$ = ${\Vert x \Vert}_{\infty}$ $\Rightarrow$ ${\left \Vert \matrix{
\left [ \matrix{ 10 \cr 3 \cr } \right ] \cr } \right \Vert }_{\infty}$ = 10 = ${\sigma}_1 $

$\Rightarrow$ ${\~ g}_1$ = ${ 1 \over {10}}$ $\left [ \matrix{ 10 \cr 3 \cr } \right ]$ = $\left [ \matrix{ 1 \cr { 3 \over {10} } \cr } \right ]$


STEP 3. repeat STEP 2.

A2 q0 $\Rightarrow$ A (A q0) = A q2 = $10 A {\~ q}_1$

consider $A {\~ q}_1$ = $\left [ \matrix{ 9 & 1 \cr 1 & 2 \cr } \right ]$ $\left [ \matrix{ 1 \cr { 3 \over {10} } \cr } \right ]$ = $\left [ \matrix{ 9.3 \cr 1.6 \cr } \right ]$ = q2

${\~ q}_2$ = ${{q_2} \over {\Vert q_2 \Vert}_{\infty}}$ = $\left [ \matrix{ 1 \cr {{1.6} \over {9.3}} } \right ]$

By Table 4.1 ( P213 )
Eigenvalue : 9.140055
Eigenvector : ( 1 , 0.140055 )

$ {{A^n q_0} \over {\lambda}^n_1}$ = $u_1 + \varepsilon ({ {{\lambda}_2} \over {{\lambda}_1} })$

$\Rightarrow$ An q0 = ${\lambda}^n_1 ( u_1 + \varesilon
( { ({ {{\lambda}_2} \over {{\lambda}_1} }) }^n )$

$ {\sigma}_j \rightarrow {\lambda}_1$ , when $j \rightarrow \infty$

${\sigma}_1 = {\Vert A q_0 \Vert}_{\infty}$

${\sigma}_2 = {\Vert A {\~ q_1} \Vert}_{\infty}$

$~~~~~~~~~~~~~~\vdots$

${\sigma}_n$ = ${\Vert A {{\~ q}_n-1} \Vert}_{\infty}$ = ${{\vert {\lambda}^n_1 \vert {\Vert u_1 + \varepsilon
{( {{{\lambda}_2} \over {...
...\varepsilon {( {{{\lambda}_2}
\over {{\lambda}_1}} )}^{n-1} \Vert}_{\infty}}
}$ $\rightarrow {\lambda}_1$

[Thm] If a is nonsingular , if $\lambda$ is an Eigenvalue of A , then ${\lambda}^{-1}$ isi an Eigenvalue of A-1 .

<Proof> If $\lambda$ is an Eigenvalue of A

$\Rightarrow Ax = \lambda x
\par\Rightarrow x = A^{-1} \lambda x = \lambda (A^{-1} x)
\par\Rightarrow {\lambda}^{-1} x = A^{-1} x $

Inverse Power Method :

( For finding the smallest Eigenvlaue of A )

1. If $\vert {\lambda}_1 \vert \geq \vert {\lambda}_2 \vert \geq \cdots \geq \vert {\lambda}_{n-1} \vert \geq \vert {\lambda}_n \vert$2. and $v_1 , v_2 , \cdots , v_n $ are L.I. Eigenvectors . 3. A is nonsingular .

$\Rightarrow {\vert {\lambda}^{-1}_n \vert} > {\vert {\lambda}^{-1}_{n-1} \vert}...
...rt {\lambda}^{-1}_{n-2} \vert} \geq \cdots \geq {\vert {\lambda}^{-1}_1 \vert} $

apply Power Method to A-1

$\Rightarrow$ ${\lambda}^{-1}_n $ can be found by regular Power Method on A-1

Shift Inverse Power Method :

[Thm] If $\lambda$ is an Eigenvalue of A , then $\lambda - u $ is an Eigenvalue of (A - uI) .

<Proof> because $Ax = \lambda x$

$\Rightarrow ( A - uI ) x = Ax - ux = \lambda x - ux = ( \lambda - u ) x$

so $\lambda - u $ is an Eigenvalue of ( A - uI )

1. Given $\varepsilon > 0 $

s.t. $\vert {\lambda}_j - u \vert < \varepsilon $ , and $\vert {\lambda}_k - u \vert > \varepsilon $ for all $k \ne j$2. $v_1 , \cdots , v_n $ L.I. Eigenvectors 3. A-1 exists

Example : ${\lambda}_1 = 1 , {\lambda}_2 = 1.3 , {\lambda}_3 = 2 $ are Eigenvalue of A

[Sol] Let u = 1.2 , consider $\vert {\lambda}_i - u \vert
\par\Rightarrow \vert {\lambda}_1 - u \vert , \ver...
...a}_2 - u \vert , \vert {\lambda}_3 - u \vert
\par\Rightarrow 0.2 , 0.1 , 0.8 , $ are Eigenvalues of ( A - uI )

1. If ${\lambda}_1 , {\lambda}_2 , \cdots , {\lambda}_n $ are Eigenvalues of A ,

then ${\lambda}_1 - u , {\lambda}_2 - u , \cdots , {\lambda}_n - u $ are Eigenvalues of A - uI2. If $\vert {\lambda}_j - u \vert$ are the smallest Eigenvalue of A - uI ,

then Apply the inverse Power Method on (A - uI) ,

we can find ${\lambda}_j - u $ ( $\Rightarrow {\lambda}_i$ can be fonud )

Issue :

1. Power Method : find MAX. Eigenvalue and Eigenvector 2. Inverse Power Method : find MIN. Eigenvalue and Eigenvector 3. Shift Inverse Power Method : find the Eigenvalue colse to fixed u



 
next up previous
Next: About this document ...

1998-08-15