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

2 Answers 2

1
$\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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .