# 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} & a_{1,2} & \cdots & a_{1,n} & a_{1,n+1} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} & a_{2,n+1} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} & 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} & \hat{a}_{1,2} & \cdots & \hat{a}_{1,n} & \hat{a}_{1,n+1} \\ 0 & \hat{a}_{2,2} & \cdots & \hat{a}_{2,n} & \hat{a}_{2,n+1} \\ \vdots & \ddots & \ddots & \vdots & \vdots \\ 0 & \cdots & 0 & \hat{a}_{n,n} & \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} & 0 & \cdots & 0 & \hat{\hat{a}}_{1,n+1} \\ 0 & \hat{\hat{a}}_{2,2} & \cdots & 0 & \hat{\hat{a}}_{2,n+1} \\ \vdots & \ddots & \ddots & \vdots & \vdots \\ 0 & \cdots & 0 & \hat{\hat{a}}_{n,n} & \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.

• 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 $-\frac{5}{6}n$. – Algebraic Pavel Aug 24 '15 at 9:47
• @AlgebraicPavel Thanks a lot, I've simply missed it. – MathNerd Aug 24 '15 at 10:04

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.

1. 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...