Soient λ une valeur propre A et x = (x1, ..., xn) un vecteur propre associé.
Pour $i$ compris entre 1 et $n$, on a
$(\lambda -a_{ii})x_{i} = \sum_{j\neq i} a_{ij} x_{j}$
Choisissons un indice i pour lequel le module de $x_i$ est maximal.
Puisque x est un vecteur propre, $|x_i|$ est non nul et il est possible de former le quotient $\frac {|x_j|}{|x_i|} \leq 1$.
On a :
$|a_{ii}-\lambda |$ $=\left|\sum _{j\neq i}a_{ij}{\frac {x_{j}}{x_{i}}}\right|$ $\leq \sum _{j\neq i}\left|a_{ij}{\frac {x_{j}}{x_{i}}}\right|$ $\leq \sum _{j\neq i}|a_{ij}|$
On veut $\min |\lambda_i - \lambda | \leq \epsilon$
J'ai fait au tableau par l'absurde :
$ (A - \lambda) u = (A - \lambda) \sum u_i v_i = A (\sum u_i v_i) - \lambda (\sum u_i v_i)$
$= \sum u_i A v_i - \sum u_i (\lambda v_i) = \sum u_i (\lambda_i v_i) - \sum u_i (\lambda v_i)$
$= \sum u_i (\lambda_i - \lambda ) v_i$
D'après Pythagore
$\| (A - \lambda) u \|^2 = \sum u_i^2 |\lambda_i - \lambda |^2$
et si $\min |\lambda_i - \lambda | > \epsilon$ alors
$ \| (A - \lambda) u \|^2 > \epsilon^2 \| u \|^2$
import numpy as np
import matplotlib.pyplot as plt
est un algorithme permettant d'estimer
d'une matrice $A$. L'idée est que, si on définit une suite $(x_n)$ de vecteurs de $\mathbb R^n$ par la relation $$x_{n+1}=Ax_n,$$ alors les vecteurs $x_n$ vont "se tourner" dans la direction des vecteurs propres associés à la plus grande des valeurs propres.
Théorème : Soit $A\in\mathcal M_n(\mathbb R)$ une matrice diagonalisable
Alors, si $x_0$ est un vecteur non orthogonal à $v_1$, et si $(x_n)$ est définie par la relation de récurrence $x_{n+1}=Ax_n$, alors
A = np.array([99,1,0,1,100,1,0,1,98]).reshape(3,3) # - 97 * np.identity(3)
A
array([[ 99, 1, 0], [ 1, 100, 1], [ 0, 1, 98]])
np.linalg.eig(A)[0]
array([100.87938524, 98.65270364, 97.46791111])
centers = np.diag(A).astype(complex)
radii = np.sum(np.abs(A - np.diag(centers)), axis = 1)
fig, ax = plt.subplots()
ax.set_title('Gershgorin circles')
for cc, rr in zip(centers, radii):
# this is dumb but must plot the centers first
ax.plot([cc.real],[cc.imag])
ax.add_patch(plt.Circle((cc.real,cc.imag),rr,
color='r', alpha=.5))
MAXITER = 1000
EPSILON = 10**-11
# I know how many there will be so don't need a dynamic list
x = np.zeros((MAXITER + 1, 3))
# initial vector should check not eigenvector
x[0] = A[0]
for k in range(MAXITER):
#iterate
x[k+1] = A @ x[k]
# normalise see above
x[k+1] /= np.linalg.norm(x[k+1])
#stopping condition
if np.linalg.norm(x[k+1] - x[k]) < EPSILON: break
vecs = x[:k]
#eigenvalue
vecs[-1]@A@vecs[-1]
100.87938524157182
def pow_meth(A,
MAXITER = 1000,
EPSILON = 10**-11):
# I know how many there will be so don't need a dynamic list
x = np.zeros((MAXITER + 1,3))
# initial vector should check not eigenvector
x[0,0] = 1
for k in range(MAXITER):
#iterate
x[k+1] = A @ x[k]
# normalise see above
x[k+1] /= np.linalg.norm(x[k+1])
#stopping condition
if np.linalg.norm(x[k+1] - x[k]) < EPSILON: break
else:
raise ValueError
return x[:k]
low memory use version
MAXITER = 1000
EPSILON = 10**-11
# initial vector should check not eigenvector
# you should program it
x = A[0].astype(float)
for _ in range(MAXITER):
x, y = A@x, x
# normalise
x /= np.linalg.norm(x)
#stopping condition
if np.linalg.norm(x - y) < EPSILON: break
# eigenvalue, eigenvector
y@A@y, y
(100.8793852415718, array([0.44909879, 0.84402963, 0.29312841]))
and compare it with numpy.
np.linalg.eigvals(A)[0]
100.87938524157187
import matplotlib.pyplot as plt
vecs = pow_meth(A )
Y = [np.linalg.norm(v) for v in vecs[:-1] - vecs[-1]]
YY = np.log(Y)
plt.plot(YY)
# calculate the rate of convergence
a,b = 450,200
slope = (YY[b] - YY[a])/(b-a)
plt.title(f'log plot for $A$ slope = {slope}');
the slope should be $\log( \lambda_2/\lambda_1)$.
vv = np.linalg.eig(A)[0]
np.log(vv[1]/vv[0])
-0.022319959154051165
vecs = pow_meth(A - 97*np.identity(3))
Y = np.array([np.linalg.norm(v) for v in vecs[:-1] - vecs[-1]])
YY = np.log(Y)
plt.plot(YY)
a,b = 5,20
slope = (YY[b] - YY[a])/(b-a)
plt.title(f'log plot for $A - 97I_3$ slope = {slope}');
vv = np.linalg.eig(A - 97*np.identity(3))[0]
np.log(vv[1]/vv[0])
-0.8532641787457773
'/home/macbuse'