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.
Best Answer
To provide an answer to the question from Algebraic Pavel's comment:
That is to say, your entries need to be $1$ at the end to actually get the solution.