search
Log In
2 votes
453 views
Derive the expressions for the number of operations required to solve a system of linear equations in $n$ unknowns using the Gaussian Elimination Method. Assume that one operation refers to a multiplication followed by an addition.
in Linear Algebra
retagged by
453 views

1 Answer

2 votes
 
Best answer

Let $A$ be a $n \times n$ matrix and we want to solve the system of linear equations expressed by $Ax=b$.

We start with the augmented matrix $[A : b]$ and follow the following steps.

  • Step 1: Convert the augmented matrix to row echelon form
  • Step 2: Convert pivot elements to 1 (leading coefficient of a non zero row) in the resulting matrix
  • Step 3: Convert the resulting matrix to row reduced echelon form (equivalent to solve equations by backward substitutions) 

Now let us analyze the number of operations performed in each step.

Step 1: It involves multiplying $i^{th}$ row by a constant $c_{ij}$ and subtracting from row $j>i$ to produce $0$ in $ji$ position.

  • For first row we have maximum $n+1$ non-zero elements and this requires $(n+1)(n−1)$ operations (multiplication followed by subtraction/addition)
  • For the second row we have maximum n non-zero elements and this requires $n(n−2)$ operations
  • Like wise the last row will need $3\times 1$ operations.

Total number of multiplication followed by subtraction/addition operations in this step $=(n+1)(n−1)+n(n−2)+(n−1)(n−3)+\ldots+3\times1 =  \displaystyle \sum_{i=1}^n i. (i + 2) = \sum_{i=1}^{n-1} i^2 + \sum_{i=1}^{n-1} 2i = \frac{(n-1).n(2n-1)}{6} + n. (n-1) = n(n-1)(2n+5)/6$

Step 2: To convert pivot elements to $1$ we need to divide each non zero row of the matrix obtained after step 1 by the leading coefficient. 

Total number of divisions $= (n+1) + n+ (n-1) + (n-2) + \ldots + 2 = n(n+3)/2$

Step 3: It involves back substitutions such that all elements above the pivot elements are zero.  To convert all elements to zero above the pivot of $i^{th}$ row, we need $2(n-i)$ number of multiplication followed by subtraction/addition operations.

Total number of multiplication followed by subtraction/addition operations in this step  $= 2(1 + 2 + \ldots+ (n-1)) = n(n-1)$

Hence, total number of multiplication followed by subtraction/addition operations required to solve a system of linear equations using Gaussian Elimination $= n(n-1)(2n+5)/6 + n(n-1) = n(n-1)(2n+11)/6.$


selected by
0

 Size of matrix is n*n then how first row can have maximum n+1 non-zero elements ?

Related questions

16 votes
2 answers
1
2.6k views
Consider the following set of equations $x+2y=5\\ 4x+8y=12\\ 3x+6y+3z=15$ This set has unique solution has no solution has finite number of solutions has infinite number of solutions
asked Sep 26, 2014 in Linear Algebra Kathleen 2.6k views
19 votes
4 answers
2
2.3k views
Consider the following determinant $\Delta = \begin{vmatrix} 1 & a & bc \\ 1 & b & ca \\ 1 & c & ab \end{vmatrix}$ Which of the following is a factor of $\Delta$? $a+b$ $a-b$ $a+b+c$ $abc$
asked Sep 26, 2014 in Linear Algebra Kathleen 2.3k views
15 votes
3 answers
3
2.3k views
The rank of the matrix given below is: $\begin{bmatrix} 1 &4 &8 &7\\ 0 &0& 3 &0\\ 4 &2& 3 &1\\ 3 &12 &24 &21 \end{bmatrix}$ $3$ $1$ $2$ $4$
asked Sep 26, 2014 in Linear Algebra Kathleen 2.3k views
2 votes
1 answer
4
149 views
The values of $\eta$ for which the following system of equations $\begin{array} {} x & + & y & + & z & = & 1 \\ x & + & 2y & + & 4z & = & \eta \\ x & + & 4y & + & 10z & = & \eta ^2 \end{array}$ has a solution are $\eta=1, -2$ $\eta=-1, -2$ $\eta=3, -3$ $\eta=1, 2$
asked Sep 23, 2019 in Linear Algebra Arjun 149 views
...