<jupyter_start><jupyter_text>Please **submit this Jupyter notebook through Canvas** no later than **Monday November 19, 12:59**, before the start of the lecture.Homework is in **groups of two**, and you are expected to hand in original work. Work that is copied from another group will not be accepted.  Exercise 0Write down the names + student ID of the people in your group. <NAME> (10639918)<NAME> (10759697) ------------- Exercise 1 (a)Let $Q$ be a real, square orthogonal matrix. Show that all eigenvalues of $Q$ satisfy $|\lambda |=1$. We know that $Qx = \lambda x$ by definition of the eigenvalues. From there we can state $||Qx||^{2} = ||\lambda x||^{2} = |\lambda|^{2} ||x||^{2}$. Since Q is a square matrix, $||Qx||^{2} = (Qx)^{T}(Qx)$, so $(Qx)^{T}(Qx) = |\lambda|^{2}(x)^{T}(x)$. Since Q is orthogonal, $Q^{T} Q = I$, so $(x)^{T}(x) = |\lambda|^{2}(x)^{T}(x)$. This means that $|\lambda|^{2}$ must be 1, so $|\lambda| = 1$.   (b)A projection matrix is a matrix $P$ for which $P^2=P$. Find the eigenvalues of a projection matrix. We know that $Px = \lambda x$. Since $P = P^{2}$, $Px = \lambda x = P^{2}x = \lambda^{2}x$. So we see that $\lambda x = \lambda^{2}x$, which means that $\lambda = \lambda^{2}$. This can only be true for 2 values: 0 and 1.  ----------- Exercise 2Generate a symmetric $4 × 4$ matrix $A$ randomly, e.g. as below.Implement Rayleigh quotient iteration (Algorithm 4.4) to compute the largest eigenvalue and corresponding eigenvector of $A$. Use a suitable stopping criterion for your iterations (and explain why you think it is suitable). You may use `scipy.linalg.solve`.Example 4.14!<jupyter_code>import numpy as np

# create matrix
B = np.random.randn(4,4)
A = B+B.T

# use built-in function to check real eigenvalues
echteeig = np.linalg.eig(A)[0]

# first approximation of largest eigenvalue
mu = 10

# first approximation of corresponding eigenvector
x0 = np.array([1, 1, 1, 1])

# perform power iteration to improve initial eigenvector
for i in list(range(0, 5)):
    x0 = np.dot(A, x0)
    
x = [x0]
mus = [mu]

# create identity matrix
I = np.identity(4)

stop = False
    
# perform Rayleigh quotient iteration (with result of power iteration)
while(stop == False):
# for i in list(range(0, 5)):
    
    # compute shift of eigenvalue approximation
    prod1 = np.dot(x[-1].transpose(), A)
    prod2 = np.dot(prod1, x[-1])
    prod3 = np.dot(x[-1].transpose(), x[-1])
    nextMu = prod2/prod3
    
    # generate next corresponding eigenvector
    nextX = np.linalg.solve(A - nextMu * I, x[-1])
    
    # normalize eigenvector
    nextX = nextX/np.linalg.norm(nextX)
    
    x.append(nextX)
    mus.append(nextMu)
    
    # stop iterating if no (almost) improvement is made compared to last eigenvalue approximation
    if len(mus)> 1 and abs(mus[-1] - mus[-2]) < 10**-15:
        stop = True
    
print "Built-in maximum absolute eigenvalue calculation: ", max(echteeig, key=abs)
print "Our Rayleigh quotient iteration approximation of largest eigenvalue: ", mus[-1]<jupyter_output>Built-in maximum absolute eigenvalue calculation:  -3.74380748113
Our Rayleigh quotient iteration approximation of largest eigenvalue:  -3.74380748113<jupyter_text>------------- Exercise 3Let $A$ be a $n × n$ tridiagonal matrix that results (up to an overall constant scaling factor) from an$n$-point spatial discretization of the Laplace operator in $1$ spatial dimension. Specifically, all diagonalelements of $A$ have the value $-2$, all elements just below or above the diagonal have value $1$.$${\displaystyle A = \left( \begin{array}{rrrrr} -2 &  1  &  0 &  0& \ldots \\ 1  & -2 & 1 & 0 &\ldots   \\ 0 & 1 & -2 &  1 &\ldots \\ \vdots & & & & \ddots \end{array} \right) \,}$$Take $n = 150$. Use `scipy.linalg.qr` to implement Algorithm 4.7 from the book and compute the full eigenvalue spectrum of $A$. Compare againstthe eigenvalues obtained by the built-in routine `scipy.linalg.eig(A)`. Show in a figure the (approximate)eigenvalues after 10, 100 and 500 QR iterations, as well as the eigenvalues obtained with `eig(A)`.<jupyter_code>from scipy.sparse import diags
from scipy.linalg import qr, eig
import matplotlib.pyplot as plt

# create the tridiagonal matrix
originalA = diags([1, -2, 1], [-1, 0, 1], shape=(150, 150)).toarray()
A10 = originalA
A100 = originalA
A500 = originalA

# perform 10 QR iterations
for i in list(range(0, 10)):
    Q, R = qr(A10)
    A10 = np.dot(R, Q)
    
# perform 100 QR iterations
for i in list(range(0, 100)):
    Q, R = qr(A100)
    A100 = np.dot(R, Q)
    
# perform 500 QR iterations
for i in list(range(0, 500)):
    Q, R = qr(A500)
    A500 = np.dot(R, Q)

# take values from the diagonals of the iterated matrices
eigenA10 = []
eigenA100 = []
eigenA500 = []
for i in list(range(0, 150)):
    eigenA10.append(A10[i, i])
    eigenA100.append(A100[i, i])
    eigenA500.append(A500[i, i])    

# plot computed eigenvalues approximations
fig, ax = plt.subplots()
ax.plot(list(range(0, 150)), eigenA10, label = "10 it QR")
ax.plot(list(range(0, 150)), eigenA100, label = "100 it QR")
ax.plot(list(range(0, 150)), eigenA500, label = "500 it QR")
ax.plot(list(range(0, 150)), eig(originalA)[0], label = "Built-in routine")
ax.set_xlim(0, 150)
ax.set_xlabel("Number of eigenvalue")
ax.set_ylabel("Value of eigenvalue")
ax.legend(fontsize = "medium", loc = 2)
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1463687150837989, 'fraction_numerical': 0.04897579143389199, 'mean_word_length': 3.791257805530776, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, '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': '478766', 'license': 'Apache-2.0', 'n_tokens_mistral': 1994, 'n_tokens_neox': 1780, 'n_words': 666, 'path': 'ComputationalScience/Numerical/.ipynb_checkpoints/Ridderikhoff_deFeijter_homework4-checkpoint.ipynb', 'repo_name': 'TessaRidderikhoff/Programmeerproject', 'size': '5394'}