$ A \in \mathbb{R}^{n x n} $ of a tridiagonal matrix and $b \in \mathbb{R}^{n}$
What is the least number of arithmetic statements as a function of n to solve $A*x = b$?
$ \left( \begin{matrix} a_{1,1} & a_{1,2} & 0 & \ldots & 0\\ a_{2,1} & a_{22} & a_{2,3} & \ldots & \vdots\\ 0 & a_{3,2} & \ddots &\ddots & 0\\ \vdots & \ddots & \ddots & \ddots & a_{n-1,n}\\ 0 & \ldots & 0 & a_{n,n-1} & a_{n,n} \end{matrix} \right) $
for LU in 4x4 tridiagonal matrix I need 3 to zero operations -> n-1 for LU decomposition
Gaussian Elimination: $((n-1)n(n+1))/3 + ((n-1)n)/2$ subtractions/Multiplications and $(n(n+1))/2$ divisions.
Are the first steps correct?
What is the correct solution?
Thanks.