Numerical Methods
Solution of Systems of Linear
Equations
1
Vector, Matrices, and
Linear Equations
2
VECTORS
Vector : a one dimensional array of numbers
Examples :
2
row vector 1 4 2 column vector
1
1 0 0 0
0 1 0 0
Identity vectors e1 , e2 , e3 , e4
0 0 1 0
0 0 0 1
3
MATRICES
Matrix : a two dimensiona l array of numbers
Examples :
0 0 0 1 0
zero matrix identity matrix
0 0 0 0 1
1 0 0 0 1 2 0 0
0 4 0 0 3 4 1 0
diagonal , Tridiagona l
0 0 0 0 0 1 4 1
0 0 0 6 0 0 2 1
4
MATRICES
Examples :
1 2 1 3
2 1 1 0 4 1 0
symmetric 1 0 5 , upper triangular
0 0 4 1
1 5 4
0 0 0 1
5
Determinant of a
MATRICES
Defined for square matrices only
Examples :
2 3 1
0 5 3 -1 3 -1
det 1 0 5 2 -1 -1
5 4 5 4 0 5
1 5 4
2( 25) 1(12 5) 1(15 0) 82
6
Adding and Multiplying
Matrices
The addition of two matrices A and B
* Defined only if they have the same size
* C A B c ij a ij b ij i, j
Multiplication of two matrices A(n m) and B(p q)
* The product C AB is defined only if m p
m
* C A B c ij a ik b kj i, j
k 1
7
Systems of Linear
Equations
A system of linear equations can be presented
in different forms
2 x1 4 x2 3 x3 3 2 4 3 x1 3
2.5 1 3 x 5
2.5 x1 x2 3 x3 5 2
x1 6 x3 7 1 0 6 x3 7
Standard form Matrix form
8
Solutions of Linear
Equations
x1 1
x 2 is a solution to the following equations :
2
x1 x2 3
x1 2 x2 5
9
Solutions of Linear
Equations
A set of equations is inconsistent if there
exists no solution to the system of equations:
x1 2 x2 3
2 x1 4 x2 5
These equations are inconsistent
10
Solutions of Linear
Equations
Some systems of equations may have infinite
number of solutions
x1 2 x2 3
2 x1 4 x2 6
have infinite number of solutions
x1 a
x 0.5(3 a ) is a solution for all a
2
11
Graphical Solution of Systems
of
Linear Equations
x1 x2 3
x1 2 x2 5
Solution
x1=1, x2=2
12
Cramer’s Rule is Not
Practical
Cramer' s Rule can be used to solve the system
3 1 1 3
5 2 1 5
x1 1, x2 2
1 1 1 1
1 2 1 2
Cramer' s Rule is not practical for large systems .
To solve N by N system requires (N 1)(N - 1)N! multiplications.
To solve a 30 by 30 system, 2.38 1035 multiplications are needed.
It can be used if the determinants are computed in efficient way
13
Lecture 13
Naive Gaussian
Elimination
Naive Gaussian Elimination
Examples
14
Naive Gaussian Elimination
The method consists of two steps:
Forward Elimination: the system is reduced
to upper triangular form. A sequence of
elementary operations is used.
Backward Substitution: Solve the system
starting from the last variable.
a11 a12 a13 x1 b1 a11 a12 a13 x1 b1
a a22 a23 x b 0 a22 ' a23 ' x b '
21 2 2 2 2
a31 a32 a33 x3 b3 0 0 a33 ' x3 b3 '
15
Elementary Row Operations
Adding a multiple of one row to another
Multiply any row by a non-zero constant
16
Example
Forward Elimination
6 2 2 4 x1 16
12 8 6 10 x 26
2
3 13 9 3 x3 19
6 4 1 18 x4 34
Part 1 : Forward Elimination
Step1 : Eliminate x1 from equations 2, 3, 4
6 2 2 4 x1 16
0 4 2 2 x 6
2
0 12 8 1 x3 27
0 2 3 14 x4 18
17
Example
Forward Elimination
Step2 : Eliminate x2 from equations 3, 4
6 2 2 4 x1 16
0 4 2 2 x 6
2
0 0 2 5 x3 9
0 0 4 13 4 21
x
Step3 : Eliminate x3 from equation 4
6 2 2 4 x1 16
0 4 2 2 x 6
2
0 0 2 5 x3 9
0 0 0 3 x4 3
18
Example
Forward Elimination
Summary of the Forward Elimination :
6 2 2 4 x1 16 6 2 2 4 x1 16
12 8 6 10 x 26 0 4 2 2 x 6
2 2
3 13 9 3 x3 19 0 0 2 5 x3 9
6 4 1 18 x
4 34 0 0 0 3 x4 3
19
Example
Backward Substitution
6 2 2 4 x1 16
0 4 2 2 x 6
2
0 0 2 5 x3 9
0 0 0 3 x4 3
Solve for x4 , then solve for x3 ,... solve for x1
3 95
x4 1, x3 2
3 2
6 2( 2) 2(1) 16 2(1) 2( 2) 4(1)
x2 1, x1 3
4 6
20
Forward Elimination
ai1
aij aij a1 j (1 j n )
a11
To eliminate x1 2 i n
a
bi bi i1 b1
a11
ai 2
aij aij a2 j ( 2 j n )
a 22
To eliminate x2 3 i n
a
bi bi i 2 b2
a 22
21
Forward Elimination
aik
aij aij a kj ( k j n )
a kk
To eliminate xk k 1 i n
aik
bi bi bk
a kk
Continue until xn 1 is eliminated.
22
Backward Substitution
bn
xn
a n ,n
bn 1 a n 1,n xn
xn 1
a n 1,n 1
bn 2 a n 2,n xn a n 2,n 1 xn 1
xn 2
a n 2, n 2
n
bi ai , j x j
j i 1
xi
a i ,i
23
Naive Gaussian
Elimination
Summary of the Naive Gaussian Elimination
Example
Problems with Naive Gaussian Elimination
Failure due to zero pivot element
Error
Pseudo-Code
24
Naive Gaussian Elimination
o The method consists of two steps
o Forward Elimination: the system is reduced to
upper triangular form. A sequence of elementary
operations is used.
a11 a12 a13 x1 b1 a11 a12 a13 x1 b1
a a22 a23 x b 0 a22 ' a23 ' x b '
21 2 2 2 2
a31 a32 a33 x3 b3 0 0 a33 ' x3 b3 '
o Backward Substitution: Solve the system starting
from the last variable. Solve for xn ,xn-1,…x1.
25
Example 1
Solve using Naive Gaussian Elimination :
Part 1 : Forward Elimination ___ Step1 : Eliminate x1 from equations 2, 3
x1 2 x2 3 x3 8 eq1 unchanged ( pivot equation)
2
2 x1 3x2 2 x3 10 eq2 eq2 eq1
1
3
3x1 x2 2 x3 7 eq3 eq3 eq1
1
x1 2 x2 3x3 8
x2 4 x3 6
5 x2 7 x3 17
26
Example 1
Part 1 : Forward Elimination Step2 : Eliminate x2 from equation 3
x1 2 x2 3 x3 8 eq1 unchanged
x2 4 x3 6 eq 2 unchanged ( pivot equation)
5
5 x2 7 x3 17 eq3 eq3 eq 2
1
x1 2 x2 3 x3 8
x2 4 x3 6
13 x3 13
27
Example 1
Backward Substitution
b3 13
x3 1
a3,3 13
b2 a2,3 x3 6 4 x3
x2 2
a2, 2 1
b1 a1, 2 x2 a1,3 x3 8 2 x2 3 x3
x1 1
a1,1 a1,1
x1 1
The solution is x2 2
x3 1
28
Determinant
The elementary operations do not affect the determinant
Example :
1 2 3 1 2 3
A 2 3 2 Elementary A' 0 1 4
operations
3 1 2 0 0 13
det (A) det (A') 13
29
How Many Solutions Does a
System of Equations AX=B
Have?
Unique No solution Infinite
det(A) 0 det(A) 0 det(A) 0
reduced matrix reduced matrix reduced matrix
has no zero rows has one or more has one or more
zero rows zero rows
corresponding B corresponding B
elements 0 elements 0
30
Examples
Unique No solution infinte # of solutions
1 2 1 1 2 2 1 2 2
3 4 X 2 2 4 X 3 2 4 X 4
1 2 1 1 2 2 1 2 2
0 2 X 1 0 0 X 1 0 0 X 0
solution : No solution Infinite # solutions
0
X 0 1 impossible! X
0.5 1 .5
31
Pseudo-Code: Forward
Elimination
Do k = 1 to n-1
Do i = k+1 to n
factor = ai,k / ak,k
Do j = k+1 to n
ai,j = ai,j – factor * ak,j
End Do
bi = bi – factor * bk
End Do
End Do
32
Pseudo-Code: Back
Substitution
xn = bn / an,n
Do i = n-1 downto 1
sum = bi
Do j = i+1 to n
sum = sum – ai,j * xj
End Do
xi = sum / ai,i
End Do
33
Gaussian Elimination
with Scaled Partial
Pivoting
Problems with Naive Gaussian Elimination
Definitions and Initial step
Forward Elimination
Backward substitution
Example
34
Problems with Naive Gaussian
Elimination
o The Naive Gaussian Elimination may fail for very
simple cases. (The pivoting element is zero).
0 1 x1 1
1 1 x 2
2
o Very small pivoting element may result in
serious computation errors
10 10 1 x1 1
1 1 x2 2
35
Example 2
Solve the following system using Gaussian Elimination
with Scaled Partial Pivoting :
1 1 2 1 x1 1
3 2 1 4 x 1
2
5 8 6 3 x3 1
4 2 5 3 x 1
4
36
Example 2
Initialization step
Scale vector:
1 1 2 1 x1 1 disregard sign
3 2 1
4 x2 1 find largest in
magnitude in
each row
5 8 6 3 x3 1
4 2 5 3 x4 1
Scale vector S 2 4 8 5
Index Vector L 1 2 3 4
37
Why Index Vector?
Index vectors are used because it is much
easier to exchange a single index element
compared to exchanging the values of a
complete row.
In practical problems with very large N,
exchanging the contents of rows may not
be practical.
38
Example 2
Forward Elimination-- Step 1: eliminate
x1
Selection of the pivot equation
1 1 2 1 x1 1
3 2 1 4 x 1
2 S [2 4 8 5]
5 8 6 3 x3 1 L [1 2 3 4 ]
4 2 5 3 x4 1
al ,1 1 3 5 4
Ratios i
i 1,2,3,4 , , , max corresponds to l4
Sli 2 4 8 5
equation 4 is the first pivot equation Exchange l4 and l1
L [ 4 2 3 1 ]
39
Example 2
Forward Elimination-- Step 1: eliminate
x1
Update A and B
1 1 2 1 x1 1
3 2 1 4 x 1
2 First pivot
5 8 6 3 x3 1
equation
4 2 5 3 x4 1
0 1.5 0.75 0.25 x1 1.25
0 0.5 2.75 1.75 x 1.75
2
0 5.5 0.25 0.75 x3 2.25
4 2 5 3 4 1
x
40
Example 2
Forward Elimination-- Step 2: eliminate
x2
Selection of the second pivot equation
0 1.5 0.75 0.25 x1 1.25
0 0.5 2.75 1.75 x 1.75
2
0 5.5 0.25 0.75 x3 2.25
4 2 5 3 x4 1
S [2 4 8 5 ] L [ 4 2 3 1]
al , 2 0.5 5.5 1.5
Ratios : i
i 2,3,4 L [ 41 3 2 ]
Sli 4 8 2
41
Example 2
Forward Elimination-- Step 3: eliminate
x3
Third pivot
0 1.5 0.75 0.25 x1 1.25
0 x 2.1667 equation
0 2.5 1.8333 2
0 0 0.25 1.6667 x3 6.8333
4 2 5 3 x
4 1
L [ 4 1 2 3]
0 1.5 0.75 0.25 x1 1.25
0 0 2.5 1.8333 x 2.1667
2
0 0 0 2 x3 9
4 2 5 3 x
4 1
42
Example 2
Backward Substitution
0 1.5 0.75 0.25 x1 1.25 L [ 4 1 2 3]
0 0 2.5 1.8333 x 2.1667
2
0 0 0 2 x3 9
4 2 5 3 x 1
4
b3 9 b a 2,4 x4 2.1667 1.8333x4
x4 4.5, x3 2 2.4327
a3,4 2 a 2,3 2 .5
b1 a1,4 x4 a1,3 x3 1.25 0.25 x4 0.75 x3
x2 1.1333
a1,2 1. 5
b4 a 4,4 x4 a 4,3 x3 a 4,2 x2 1 3 x 4 5 x3 2 x 2
x1 7.2333
al1 ,1 4
43
Example 3
Solve the following sytstem using Gaussian Elimination
with Scaled Partial Pivoting
1 1 2 1 x1 1
3 2 1 4 x 1
2
5 8 6 3 x3 1
4 2 5 3 x4 1
44
Example 3
Initialization step
1 1 2 1 x1 1
3 2 1
4 x2 1
5 8 6 3 x3 1
4 2 5 3 x4 1
Scale vector S 2 4 8 5
Index Vector L 1 2 3 4
45
Example 3
Forward Elimination-- Step 1: eliminate
x1
Selection of the pivot equation
1 1 2 1 x1 1
3 2 1 4 x 1
2 S [2 4 8 5]
5 8 6 3 x3 1 L [1 2 3 4 ]
4 2 5 3 x4 1
al ,1 1 3 5 4
i
Ratios i 1,2,3,4 , , , max corresponds to l4
Sli 2 4 8 5
equation 4 is the first pivot equation Exchange l4 and l1
L [ 4 2 3 1 ]
46
Example 3
Forward Elimination-- Step 1: eliminate
x1
Update A and B
1 1 2 1 x1 1
3 3 1
4 x2 1
5 8 6 3 x3 1
4 2 5 3 x4 1
0 1.5 0.75 0.25 x1 1.25
0 0.5
2.75 1.75 x2 1.75
0 10.5 0.25 0.75 x3 2.25
4 2 5 3 4 1
x
47
Example 3
Forward Elimination-- Step 2: eliminate
x2
Selection of the second pivot equation
0 1. 5 0.75 0.25 x1 1.25
0 0.5 2.75 1.75 x 1.75
2
0 10.5 0.25 0.75 x3 2.25
4 2 5 3 x4 1
S [2 4 8 5] L [ 4 2 3 1 ]
al , 2
i 0.5 10.5 1.5
Ratios : i 2,3,4 L [ 4 3 2 1]
Sli 4 8 2
48
Example 3
Forward Elimination-- Step 2: eliminate
x2
Updating A and B
0 1. 5 0.75 0.25 x1 1.25
0 0.5 2.75 1.75 x 1.75
2
0 10.5 0.25 0.75 x3 2.25
4 2 5 3 x4 1
L [ 4 1 3 2]
0 0 0.7857 0.3571 x1 0.9286
0 0 - 2.7619 1.7143 x 1.8571
2
0 10.5 0.25 0.75 x3 2.25
4 2 5 3 x
4 1
49
Example 3
Forward Elimination-- Step 3: eliminate
x3
Selection of the third pivot equation
0 0 0.7857 0.3571 x1 0.9286
0 0 2.7619 1.7143 x 1.8571
2
0 10.5 0.25 0.75 x3 2.25
4 2 5 3 x4 1
S [2 4 8 5 ] L [ 4 3 2 1 ]
al ,3 2.7619 0.7857
Ratios : i
i 3,4 L [ 4 3 2 1]
Sli 4 2
50
Example 3
Forward Elimination-- Step 3: eliminate
x3
0 0 0.7857 0.3571 x1 0.9286
0 0 2.7619 1.7143 x 1.8571
2
0 10.5 0.25 0.75 x3 2.25
4 2 5 3 x
4 1
L [ 4 3 2 1]
0 0 0 0.8448 x1 1.4569
0 0 2.7619 1.7143 x 1.8571
2
0 10.5 0.25 0.75 x3 2.25
4 2 5 3 x4 1
51
Example 3
Backward Substitution
0 0 0 0.8448 x1 1.4569 L [ 4 3 2 1]
0 0 2.7619 1.7143 x2 1.8571
0 10.5 0.25 0.75 x3 2.25
4
2 5 3 x4 1
bl4 1.4569 bl3 al3 ,4 x4 1.8571 1.7143x4
x4 1.7245, x3 0.3980
al4 ,4 0.8448 a l3 ,3 2.7619
bl2 al2 ,4 x4 al2 ,3 x3
x2 0.3469
al2 , 2
bl1 al1 ,4 x4 al1 ,3 x3 al1 ,2 x2 1 3 x 4 5 x3 2 x 2
x1 1.8673
al1 ,1 4
52
How Do We Know If a Solution
is Good or Not
Given AX=B
X is a solution if AX-B=0
Compute the residual vector R= AX-B
Due to rounding error, R may not be zero
The solution is acceptable if max ri
i
53
How Good is the Solution?
1 1 2 1 x1 1 x1 1.8673
3 2 1 4 x 1 x 0.3469
2 solution 2
5 8 6 3 x3 1 x3 0.3980
4 2 5 3 x4 1 x4 1.7245
0.005
0.002
Residues : R
0.003
0.001
54
Remarks:
We use index vector to avoid the need to move
the rows which may not be practical for large
problems.
If we order the equation as in the last value of the
index vector, we have a triangular form.
Scale vector is formed by taking maximum in
magnitude in each row.
Scale vector does not change.
The original matrices A and B are used in
checking the residuals.
55
Tridiagonal & Banded
Systems
and Gauss-Jordan
Method
Tridiagonal Systems
Diagonal Dominance
Tridiagonal Algorithm
Examples
Gauss-Jordan Algorithm
56
Tridiagonal Systems
Tridiagonal Systems:
The non-zero elements are
in the main diagonal,
5 1 0 0 0 x1 b1
super diagonal and 3 4 1 0
0 x2 b2
subdiagonal.
0 2 6 2 0 x3 b3
a =0 if |i-j| > 1
ij
0 0 1 4 1 x4 b4
0 0 0 1 6 x5 b5
57
Tridiagonal Systems
Occur in many applications
Needs less storage (4n-2 compared to n +n for the general cases)
2
Selection of pivoting rows is unnecessary
(under some conditions)
Efficiently solved by Gaussian elimination
58
Algorithm to Solve Tridiagonal
Systems
Based on Naive Gaussian elimination.
As in previous Gaussian elimination algorithms
Forward elimination step
Backward substitution step
Elements in the super diagonal are not affected.
Elements in the main diagonal, and B need
updating
59
Tridiagonal System
All the a elements will be zeros, need to update the d and b elements
The c elements are not updated
d1 c1 x1 b1 d1 c1 x1 b1
a d c2 x b d 2' c2 x b'
1 2 2
2 2 2'
a2 d3 x3 b3 d 3' x3 b3
cn 1 cn 1
'
'
an 1 d n xn bn d n xn bn
60
Diagonal Dominance
A matrix A is diagonally dominant if
n
a ii a ij for (1 i n)
j 1,
j i
The magnitude of each diagonal element is larger than
the sum of elements in the corresponding row.
61
Diagonal Dominance
Examples :
3 0 1 3 0 1
1 6 1 2 3 2
1 2 5 1 2 1
Diagonally dominant Not Diagonally dominant
62
Diagonally Dominant Tridiagonal
System
A tridiagonal system is diagonally dominant if
d i ci ai 1 (1 i n)
Forward Elimination preserves diagonal dominance
63
Solving Tridiagonal System
Forward Elimination
ai 1
d i d i ci 1
di 1
ai 1
bi bi bi 1 2 i n
di 1
Backward Substituti on
bn
xn
dn
1
xi bi ci xi 1 for i n 1, n 2,...,1
di
64
Example
Solve
5 2 x1 12 5 1 2 12
1 5 2 x 9 5 1 2 9
2 D , A , C , B
1 5 2 x3 8 5 1 2 8
1 5 x4 6 5
6
Forward Elimination
ai 1 ai 1
d i d i ci 1 , bi bi bi 1 2 i 4
di 1 di 1
Backward Substitution
bn 1
xn , xi bi ci xi 1 for i 3,2,1
dn di
65
Example
5 1 2 12
5 1 2 9
D , A , C , B
5 1 2 8
5
6
Forward Eliminatio n
a 12 a1 112
d 2 d 2 1 c1 5 4.6, b2 b2 b1 9 6.6
d1 5 d1 5
a 12 a2 16.6
d 3 d 3 2 c2 5 4.5652, b3 b3 b2 8 6.5652
d2 4. 6 d2 4. 6
a 12 a3 16.5652
d 4 d 4 3 c3 5 4.5619, b4 b4 b3 6 4.5619
d3 4.5652 d3 4.5652
66
Example
Backward Substitution
After the Forward Elimination:
DT 5 4.6 4.5652 4.5619, B T 12 6.6 6.5652 4.5619
Backward Substitution:
b4 4.5619
x4 1,
d 4 4.5619
b3 c3 x4 6.5652 2 1
x3 1
d3 4.5652
b2 c2 x3 6.6 2 1
x2 1
d2 4.6
b1 c1 x2 12 2 1
x1 2
d1 5
67
Gauss-Jordan Method
The method reduces the general system of
equations AX=B to IX=B where I is an identity
matrix.
Only Forward elimination is done and no
backward substitution is needed.
It has the same problems as Naive Gaussian
elimination and can be modified to do partial
scaled pivoting.
It takes 50% more time than Naive Gaussian
method.
68
Gauss-Jordan Method
Example
2 2 2 x1 0
4 2 1 x 7
2
2 2 4 x3 2
Step 1 Eleminate x1 from equations 2and 3
eq1 eq1 / 2
1 1 1 x1 0
4 0 6 5 x 7
eq 2 eq 2 eq1 2
1
0 0 2 x3 2
2
eq3 eq3 eq1
1
69
Gauss-Jordan Method
Example
1 1 1 x1 0
0 6 5 x 7
2
0 0 2 x3 2
Step 2 Eleminate x 2 from equations 1 and 3
eq 2 eq 2 / 6
1 0 0.1667 x1 1.1667
1 0 1 0.8333 x 1.1667
eq1 eq1 eq2 2
1 0 0 2 x3 2
0
eq3 eq3 eq2
1
70
Gauss-Jordan Method
Example
1 0 0.1667 x1 1.1667
0 1 0.8333 x 1.1667
2
0 0 2 x3 2
Step 3 Eleminate x 3 from equations 1 and 2
eq3 eq3 / 2
1 0 0 x1 1
0.1667 0 1 0 x 2
eq1 eq1 eq3 2
1 0 0 1 x3 1
0.8333
eq 2 eq 2 eq3
1
71
Gauss-Jordan Method
Example
2 2 2 x1 0
4 2 1 x 7
2
2 2 4 x3 2
is transformed to
1 0 0 x1 1 x1 1
0 1 0 x 2 solution is x 2
2 2
0 0 1 x3 1 x3 1
72