CHAPTER 2 - EXERCICES- Gaussian Elimination

EXERCICE 1: Basic application

   
1 2 1 4
Let A=2 2 1 and b=5. Apply ’by hand’ the Naive Gaussian Elimination to solve Ax=b.
1 1 1 3

EXERCICE 2: Basic application

Apply ’by hand’ the Gaussian Elimination with Partial Pivoting to solve the following linear system, if
possible; Precise the row interchanges, the pivots and the values of the linear combinaison you are using.

a/ 
 x1 −x2 +3x3 =2
3x1 −3x2 +x3 = −1
x1 +x2 =3


b/ 

 x1 +x2 +x4 =2
2x1 +x2 −x3 +x4 =1


 4x1 −x2 −2x3 +2x4 =0
3x1 −x2 −x3 +2x4 = −3

(Help : you should find : no solution, why?)

c/ 

 x1 +x2 +x4 =2
2x1 +x2 −x3 +x4 =1


 −x1 +2x2 +3x3 −x4 =4
3x1 −x2 −x3 +2x4 = −3


(Help : you should find : x=(-1;2;0;1)T )

EXERCICE 3: Roundoff error illustration ⇒ utility of Partial Pivoting

a/ Use the Naive Gaussian Elimination and 3-digit chopping arithmetic to solve the following linear systems
and compare the approximation to the actual solution (10,1)T .

0.03x1 +58.9x2 = 59.2
5.31x1 −6.10x2 = 47.0

b/ Solve again the previous system with 3-digit chopping arithmetic but with Gaussian Elimination with
Partial Pivoting.

c/ Comment.

EXERCICE 4: Graphics vs Gaussian Elimination

For each of the following linear systems, obtain a solution by graphical methods, if possible. Explain.
Compare by using Naive Gaussian Elimination.
a/ 
x1 +2x2 = 3
x1 −x2 =0
(Help : you should find a point solution (1,1)T ).

1
2

b/ 
x1 +2x2 = 3
2x1 +4x2 = 6
(Help : you should find an infinite number of solutions : which?)

c/ 
x1 +2x2 =3
−2x1 −4x2 =6
(Help : you should find no solution : why?)

EXERCICE 5: Algorithm understanding

Read the algorithm of Gaussian Elimination with Partial Pivoting on the system of exercice 2a/, in the
same way a computer will do. tol= 10−15 .

INPUT: A,b,tol

for k=1 to n-1

max=akk
line=0;
for h=k+1:n
if abs(ahk )>abs(max)
max=ahk
line = h
endif
endfor
if line 6= 0
auxA=A(k,k:n)
auxb=b(k)
A(k,k:n)=A(line,k:n)
b(k)=b(line)
A(line,k:n)=auxA
b(line)=auxb
endif
if | Akk | < tol
Error message (’pivot = 0’)
Stop
else
for i=k+1 to n
c= aakk
ik

b(i)=b(i)-c*b(k)
aik =0
for j=k+1 to n
aij = aij -c*akj
endfor
endfor
endif
endfor
if |Ann | <tol
Error message (’Last pivot is 0’)
endif
 3

EXERCICE 6: Counting the operations

Usually we can compare methods time costing by counting the number of operations they need. In general,
the amount of time required to perform a multiplication or a division on a computer is approximately the
same and is considerably greater than that required to perform an addition or substration.
In the Naive Gaussian Elimination algorithm given just after, prove the number :

n3 n2
a/ of Multiplications/Divisions is 3 + 2 − 56 n

n3 n
b/ of Additions/Substractions is 3 − 3

Help1: Count from the inner loop to the outer one.

Help2:
n
X n(n + 1)
k=
2
k=1
n
X n(n + 1)(2n + 1)
k2 =
6
k=1

Help3: The algorithm is:

INPUT: A,b,tol

for k=1 to n-1

if | Akk | < tol
Error message (’pivot = 0’)
Stop
else
for i=k+1 to n
c= aakk
ik

b(i)=b(i)-c*b(k)
aik =0
for j=k+1 to n
aij = aij -c*akj
endfor
endfor
endif
endfor
if |Ann | <tol
Error message (’Last pivot is 0’)
endif