Here we want to solve $Ax=b$ using various iterative methods, where $Ain{R}^{1010}$ is given by

$A=([3,1,],[1,3,1,],[,$ddots,ddots,ddots,$],[,1,3,1],[,1,3])$

and $b=(1,$dots,$1{)}^T.$ Choose $x_0=(0,$dots,$0{)}^T$ as initial guess.

$3.$ Implement the SOR iteration method in Python.

Test your routine by solving our sample problem. Record the number of iterations it takes to achieve an iteration error $||x_{k+1}-x_k|{|}_{}$ less than ${10}^{-15}.$

In addition, plot the number of iterations that it takes to achieve an iteration error less than ${10}^{-15}$ as a function of the SOR extrapolation paramter $,$ where $in[1,2).$ Use omega$=$nimpy. linspace $(1,1\mathrm{.}99,100)$ to cover the interval $1,1\mathrm{.}99$ with $100$ linearly spaced values and compute the number of iterations until convergence as a function of these $.$

One can show that the optimal SOR parameter ${}_{\text{o}\text{p}\text{t}}$ is in general

${}_{\text{o}\text{p}\text{t}}=\frac{2}{1+\sqrt[\phantom{2}]{1-(G_J{)}^2}},$

where $G_J=I-D^{-1}A$ is the Jacobi iteration matrix, provided that $G_J$ has only real eigenvalues and that Compute the spectral radius $(G_J)$ for the given matrix A using Python and verify that choosing ${}_{\text{o}\text{p}\text{t}}$ indeed yields the minimum value for the number of iterations until convergence.