$2$ Linear equation $(80$ Pts $)$

Define

$A^{(n)}=\left[\begin{array}{cccccccc}-2& 1& 0& 0& \text{c}\text{d}\text{o}\text{t}\text{s}& 0& 0& 0\\ 1& -2& 1& 0& \text{c}\text{d}\text{o}\text{t}\text{s}& 0& 0& 0\\ 0& 1& -2& 1& \text{c}\text{d}\text{o}\text{t}\text{s}& 0& 0& 0\\ 0& 0& 1& -2& \text{c}\text{d}\text{o}\text{t}\text{s}& 0& 0& 0\\ \text{v}\text{d}\text{o}\text{t}\text{s}& \text{v}\text{d}\text{o}\text{t}\text{s}& \text{v}\text{d}\text{o}\text{t}\text{s}& \text{v}\text{d}\text{o}\text{t}\text{s}& \text{d}\text{d}\text{o}\text{t}\text{s}& \text{v}\text{d}\text{o}\text{t}\text{s}& \text{v}\text{d}\text{o}\text{t}\text{s}& \text{v}\text{d}\text{o}\text{t}\text{s}\\ 0& 0& 0& 0& \text{c}\text{d}\text{o}\text{t}\text{s}& -2& 1& 0\\ 0& 0& 0& 0& \text{c}\text{d}\text{o}\text{t}\text{s}& 1& -2& 1\\ 0& 0& 0& 0& \text{c}\text{d}\text{o}\text{t}\text{s}& 0& 1& -2\end{array}\right]in{R}^{nn},v^{(n)}=\left[\begin{array}{c}1\\ 0\\ 0\\ 0\\ \text{v}\text{d}\text{o}\text{t}\text{s}\\ 0\\ 0\\ 0\end{array}\right]in{R}^n.$

As a special case, when $n=3,$ we have

$A^{(3)}=\left[\begin{array}{ccc}-2& 1& 0\\ 1& -2& 1\\ 0& 1& -2\end{array}\right]in{R}^{nn},v^{(3)}=\left[\begin{array}{c}1\\ 0\\ 0\end{array}\right].$

$(20$ pts$)($Coding$)$ How do LU and GS algorithms scale with the problem

size, n $($try n $=4,8,16,32,64,128)($solve the problem to $\backslash |\backslash$epsi for

GS$)?$ Show a scalablity plot $($log$-$log$).$