<jupyter_start><jupyter_text>Eigenvalue and eigenvectors calculation$$A\mathbf{x} = \lambda \mathbf{x}$$ Power method (vector iteration)- find the largest eigenvalue $\lambda_{max}$\begin{align}\mathbf{q}_k & = \frac{\mathbf{z}_{k-1}}{\|\mathbf{z}_{k-1}\|_2}\\\mathbf{z}_k & = A\mathbf{q}_{k}\\\lambda_{max}^k & = \mathbf{q}^T_k \mathbf{z}_k\end{align}<jupyter_code>%matplotlib inline
from numpy import *
from matplotlib.pyplot import *
import numpy.linalg
import scipy.linalg

n = 9
h = 1./(n-1)

x=linspace(0,1,n)

a = -ones((n-1,))
b = 2*ones((n,))
A = (diag(a, -1) + diag(b, 0) + diag(a, +1))

A /= h**2

print(A)



z0 = ones_like(x)
print(z0)


def PM(A,z0,tol=1e-5,nmax=500):
    q = z0/numpy.linalg.norm(z0,2)
    it = 0
    err = tol + 1.
    while it < nmax and err > tol:
        z = dot(A,q)
        l = dot(q.T,z)
        err = numpy.linalg.norm(z-l*q,2)
        q = z/numpy.linalg.norm(z,2)
        
        it += 1
    print("error =", err, "iterations =", it)
    print("lambda_max =", l)
    return l,q

l,x = PM(A,z0)
    
l_np, x_np = numpy.linalg.eig(A)

print("numpy")
print(l_np)<jupyter_output>[[128. -64.   0.   0.   0.   0.   0.   0.   0.]
 [-64. 128. -64.   0.   0.   0.   0.   0.   0.]
 [  0. -64. 128. -64.   0.   0.   0.   0.   0.]
 [  0.   0. -64. 128. -64.   0.   0.   0.   0.]
 [  0.   0.   0. -64. 128. -64.   0.   0.   0.]
 [  0.   0.   0.   0. -64. 128. -64.   0.   0.]
 [  0.   0.   0.   0.   0. -64. 128. -64.   0.]
 [  0.   0.   0.   0.   0.   0. -64. 128. -64.]
 [  0.   0.   0.   0.   0.   0.   0. -64. 128.]]
[1. 1. 1. 1. 1. 1. 1. 1. 1.]
error = 8.456086477502974e-06 iterations = 82
lambda_max = 249.7352340857781
numpy
[249.73523409 231.55417528 203.23651229 167.55417528 128.
   6.26476591  24.44582472  88.44582472  52.76348771]<jupyter_text>Power method with shift- find the eigenvalue $\lambda$ **closest** to $\mu$\begin{align}M & = A-\mu I\\M & = LU \\& \\M\mathbf{x}_k &= \mathbf q_{k-1}\\\mathbf{q}_k & = \frac{\mathbf{x}_k}{\|\mathbf{x}_k\|_2}\\\mathbf{z}_k & = A\mathbf{q}_{k}\\\lambda^k & = \mathbf{q}^T_k \mathbf{z}_k\end{align}<jupyter_code>def IPM(A,x0,mu,tol=1e-5,nmax=500):
    M = A - mu * eye(A.shape[0])
    Minv = numpy.linalg.inv(M)
    y = x0/numpy.linalg.norm(x0, 2)
    l = 1/dot(y.T,dot(Minv,y))
    it = 0
    err = tol + 1
    while it < nmax and err > tol:
        x = dot(Minv,y)
        y = x/numpy.linalg.norm(x,2)
        l_new = 1/dot(y.T,dot(Minv,y))
        err = abs(l_new - l)
        l = l_new
        it += 1
    print("error =", err, "iterations =", it)
    print("lambda_max =", l + mu)
    return l + mu,y
    pass


l,x = IPM(A,z0,6.)

M = A - 6 * eye(A.shape[0])
A.shape[0]<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.21561338289962825, 'fraction_numerical': 0.11152416356877323, 'mean_word_length': 2.054483541430193, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '420038', 'license': 'CC-BY-4.0', 'n_tokens_mistral': 1446, 'n_tokens_neox': 1284, 'n_words': 271, 'path': 'notes/08_eigenvalues.ipynb', 'repo_name': 'gsarti/P1.4_seed', 'size': '2690'}