4
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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$. $\endgroup$ – Algebraic Pavel Aug 24 '15 at 9:47
  • $\begingroup$ @AlgebraicPavel Thanks a lot, I've simply missed it. $\endgroup$ – MathNerd Aug 24 '15 at 10:04
0
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$
  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...

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.