Number of Arithmetic Operations in Gaussian-elimination/Gauss-Jordan Hybrid Method for Solving Linear Systems I am stucked at this problem from the book Numerical Analysis 8-th Edition (Burden) (Exercise 6.1.16) :



Consider the following Gaussian-elimination/Gauss-Jordan hybrid method for solving linear systems:

First apply the Gaussian-elimination technique to reduce the system to triangular form. Then use the $n$-th equation to eliminate the coefficients of $x_{n}$ in each of the first $n-1$ rows. After this is completed use the $(n-1)$-st equation to eliminate the coefficients of $x_{n-1}$ in the first $n-2$ rows, ans so on. The system will eventually appear as the reduced system we get by applying Gauss-Jordan method to the original system.

Show that this method requires $\frac{n^3}{3}+\frac{3}{2}n^2-\frac{5}{6}n$ multiplication/divisions and $\frac{n^3}{3}+\frac{n^2}{2}-\frac{5}{6}n$ additions/subtractions.



But when I tried to calculate the total number of multiplication/divisions I got $\frac{n^3}{3}+\frac{3}{2}n^2-\frac{11}{6}n$, Here's what I've done (Sorry for being a bit long):

The augmented matrix for the system has the form

$$ \left[
    \begin{array}{cccc|c}
        a_{1,1} &amp; a_{1,2} &amp; \cdots &amp; a_{1,n} &amp; a_{1,n+1} \\
        a_{2,1} &amp; a_{2,2} &amp; \cdots &amp; a_{2,n} &amp; a_{2,n+1} \\
        \vdots  &amp; \vdots  &amp; \ddots &amp; \vdots &amp; \vdots  \\
        a_{n,1} &amp; a_{n,2} &amp; \cdots &amp; a_{n,n} &amp; a_{n,n+1}
    \end{array}
\right] $$

after applying Gaussian-elimination (without backward substitution) to this system we get

$$ \left[
    \begin{array}{cccc|c}
        \hat{a}_{1,1} &amp; \hat{a}_{1,2} &amp; \cdots &amp; \hat{a}_{1,n} &amp; \hat{a}_{1,n+1} \\
        0 &amp; \hat{a}_{2,2} &amp; \cdots &amp; \hat{a}_{2,n} &amp; \hat{a}_{2,n+1} \\
        \vdots  &amp; \ddots  &amp; \ddots &amp; \vdots &amp; \vdots  \\
        0 &amp; \cdots &amp; 0 &amp; \hat{a}_{n,n} &amp; \hat{a}_{n,n+1}
    \end{array}
\right] $$

We know that the total number of multiplications/divisions and additions/subtractions of the Gaussian-elimination technique is $\frac{n^3}{3}+\frac{1}{2}n^2-\frac{5}{6}n$ and $\frac{1}{3}n^3-\frac{1}{3}n$ respectively.

Now we will use the $i$-th row to eliminate the coefficients of $x_i$ in each of the first $i-1$ rows for each $i=n,n-1,...,2$ ($i$ starts at $n$ and goes down to $2$), and we will get:

$$ \left[
    \begin{array}{cccc|c}
        \hat{\hat{a}}_{1,1} &amp; 0 &amp; \cdots &amp; 0 &amp; \hat{\hat{a}}_{1,n+1} \\
        0 &amp; \hat{\hat{a}}_{2,2} &amp; \cdots &amp; 0 &amp; \hat{\hat{a}}_{2,n+1} \\
        \vdots  &amp; \ddots  &amp; \ddots &amp; \vdots &amp; \vdots  \\
        0 &amp; \cdots &amp; 0 &amp; \hat{\hat{a}}_{n,n} &amp; \hat{\hat{a}}_{n,n+1}
    \end{array}
\right] $$

Since for each $i$ we do $i - 1$ divisions (inorder to calculate $\frac{\hat{a}_1,i}{\hat{a}_{i,i}}$ , $\frac{\hat{a}_2,i}{\hat{a}_{i,i}}$ , ... , $\frac{\hat{a}_{i-1},i}{\hat{a}_{i,i}}$), After that we subtract each of the elements in the row $j=1,2,...,i-1$, $\frac{\hat{a}_j,i}{\hat{a}_{i,i}}$ times the $i$-th row, and so additional $i-1$ multiplications are carried out, and we get that the total number of multiplications/divisions in this step is $\Sigma_{i=2}^n2(i-1)=n^2-n$.

And so we get that the total number of multiplications/divisions required to apply the hybrid method is $\frac{n^3}{3}+\frac{1}{2}n^2-\frac{5}{6}n + \frac{1}{2}n^2-\frac{1}{2}n = \frac{1}{3}n^3+\frac{3}{2}n^2-\frac{11}{6}n$ which is different from $\frac{n^3}{3}+\frac{3}{2}n^2-\frac{5}{6}n$.

Thanks for any help.
To provide an answer to the question from Algebraic Pavel's comment:


  You should add the final step: $n$  divisions required to compute the final solution of the diagonal system (or, equivalently, "normalizing" the diagonal matrix to the identity). That will give you the desired term $-\frac56n$.


That is to say, your entries need to be $1$ at the end to actually get the solution.
Gaussian elimination : 
(n+1)(n-1)+(n)(n-2)+...+(3)(1)=sigma(k=1 to n-1)(k+2)(k)=n^3/3+n^2/2-5n/6


2.Backward gaussian method : 
2(n-1)+2(n-2)+...+2(1)=2*sigma(k=1 to n-1)(k)=n^2-n

3.Find the solution : 
n

Sum of multi./div. = sum of 1,2,3 = n^3/3+3n^2/2-5n/6

I tried to upload my picture to explain it in detail but i dont know how to do it...