Please Solve this problem using Matlab. I know this is a big question! But please complete it as good as you can. Please show the code of how you get to the answers.

Thanks in advance!!

$[A_n{]}_{ij}=$min$(i,j),$ for example, $A_4=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 2& 2& 2\\ 1& 2& 3& 3\\ 1& 2& 3& 4\end{array}\right],$

$($a$)[2+1$ marks$]$ Implement the QR algorithm to compute the eigenvalues of $A_{10}.$ Use a suitable preliminary reduction,

but no shifts or deflation. Terminate when the largest magnitude entry on the subdiagonal is less than $0\mathrm{.}5{10}^{-10}.$

How many QR iterations are required? $($Note: You may use built$-$in codes to compute the preliminary reduction

and the QR factorisation at each step, but you should implement the QR iteration yourself $-$ i$.$e$.,$ not simply call

MATLABs eig routine!$)[$Bonus$]$ Since $A$ is symmetric, what form does the preliminary reduction take? What about

the resulting $R?$ Is the structure of A preserved during the iterations? If not, why? Add an additional line of code

to ensure the structure is preserved.

$($b$)[2$ marks$]$ Repeat the above $($including the preliminary reduction$),$ but now using a Rayleigh shift and deflating with

a tolerance of $0\mathrm{.}5{10}^{-10}$ as described in the lecture notes. How many iterations are required here?

$($c$)[2$ marks$]$ Use your software system to compute the Cholesky factorisation of $A_n$ for a few small values of $n$ and hence

convince yourself that $A_n$ is SPD$.$ Comment on any interesting properties of the Cholesky factors $L$ and $L^{TT}$ and

discuss how this property could be used to evaluate $A_{n}x$ in $O(n)$ FLOPs. Use this idea to implement an efficient

normalised power iteration to find the largest eigenvalue of $A_{1000}.$

$($d$)[4$ marks$]$ Implement the Lanczos algorithm with starting vector $q_1=[1,1,$dots,$1{]}^{TT}$ to compute the reduced Hessenberg

factorisation of a matrix. Apply the algorithm to $A_{10}($preferably using the fast application of $A_n$ derived in $($CP$1$c$))$

to compute the $kk$ reduced Hessenberg factorisation for $k=1,$dots,$10.$ For each $k$ compute the associated Ritz

values by computing the eigenvalues of the Hessenberg matrix $H_k.($You may either use your built$-$in eigenvalue solver

to do this or adapt your code from $($c$),$ although I suggest the former.$)$ On a single figure, plot the exact eigenvalues

$($as returned by eig or your QR iteration in previous questions$)$ as dots at height $11$ and, for each $k,$ plot the $k$ Ritz

values as dots at a height $k$ to produce an image similar to that on the front of the Heath textbook $($see below$).$

Hint: The figure below shows the first $3$ values, to get you on the right track. $($Note: Since the one eigenvalue is way

bigger than the others, this results in a lot of white space, so perhaps manually adjust the $x-$axis to $0,6,$ e$.$g$.,$ via

$x\underset{?}{lim}([0,6]).$

Left: Three iterations of Lanczos applied to $A_{10}.$ Middle: Same, but only showing Ritz$/$eigenvalues in $[0,6].$ Right: First $10$ sets of Ritz

values for $A_{100}^{-1}.$

$($e$)[2$ bonus marks$]$ Prove that for any $n$ the inverse of $A_n$ is given by

$A_n^{-1}=\left[\begin{array}{ccccc}2& -1& ?& ?& ?\\ -1& 2& -1& ?& ?\\ ?& \text{d}\text{d}\text{o}\text{t}\text{s}& \text{d}\text{d}\text{o}\text{t}\text{s}& \text{d}\text{d}\text{o}\text{t}\text{s}& ?\\ ?& -1& 2& -1& ?\\ ?& -1& 1& ?& ?\end{array}\right].$

$($Note: The $1$ in the bottom right is not a typo.$)$

$($f$)[2$ marks$]$ Use $($CP$1$e$)$ to implement an efficient variant of the inverse power iteration to find the smallest eigenvalue

of $A_{100}$ to an accuracy of ${10}^{-10}.($Hint: You may need as many as $20000$ iterations $($why$?),$ so efficiency is key!$)$