The Gateway to Computer Science Excellence
+1 vote
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 by Veteran (52.2k points)
retagged by | 318 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.$

by Loyal (6k points)
selected by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,565 answers
101,699 users