Given a linear system: $A \in \mathcal{R}^{n \times n}$
$$ A = \begin{bmatrix} n & 1 & 1 & \cdots & 1 \\ 1 & n & 1 & \cdots & 1 \\ 1 & 1 & n & \cdots & 1 \\ \cdots & & & \dots & n \\ \end{bmatrix} $$ which has elements $n's$ on the diagonal and $1's$ everywhere, and $b = [1,2,...,n]^{T}$. Consider this linear system:
$$ Ax = b $$
I am trying to find the expectation of execution time for this linear system with LU algorithm solving linear system and Gauss-Seidel method. For LU algorithm, I figured out using computational cost for LU is $W = \frac{2}{3} n^{3} + 2n^{2} + O(n)$ deducing the ratio is near to $8$ when $n$ size is scaled by double its size. I tried to run the Gauss Seidel in python for problem sizes $n =250,500,1000,2000,4000$ the number of convergence iterations are $18,18,19,20,20$ respectively. However, for the method Gauss-Seidel, how can I find the execution time as a scale asymptotically as a function of $n$ ? I was given a hint that for number of iterations as a function of $n$ it is very specific for this type of matrix $A$.
The Gauss-Sidel iterations are $x_{k+1} = L^{-1}(b-Ux_k)$. If your initial guess is $x_0 = 0$, then we have $$x_m = \left(\sum_{k = 0}^{m-1}(-L^{-1}U)^k\right)L^{-1}b.$$ This converges when $\rho(L^{-1}U) < 1$, and the error is $$x_{\infty}-x_m = \left(\sum_{k = m}^{\infty}(-L^{-1}U)^k\right)L^{-1}b = (-L^{-1}U)^{m}(I+L^{-1}U)^{-1}L^{-1}b,$$ which has norm $$\|x_{\infty}-x_m\| = \left|(-L^{-1}U)^{m}(I+L^{-1}U)^{-1}L^{-1}b\right\| \le \|L^{-1}U\|^m \cdot \|(I+L^{-1}U)^{-1}L^{-1}b\|.$$
Using this equation, you can figure out what value of $m$ makes the norm small enough to meet the convergence criteria.