Transcript Ch3a-Systems of Linear Equations

Chapter: 3a
System of Linear Equations
Dr. Asaf Varol
1
Introduction (I)
• Linear Equation: an equations where only the first exponent of the
unknown is present
• System of Linear Equations: the set of linear equations where there
are more than one unknown
For example
5x + 2y = -13
x - 2y = 1
is a system of two linear equations with two unknowns x and y. There may be cases
that the equation contains exponents of the unknown other than one, but by algebraic
manipulation it can be reduced to a linear form. Consider the following system of
equations
5x2 + 2xy2 -13x = 0
x - y2 = 1
Dividing the first equation by x (x can not be zero in this case), and substituting z = y2
the above system reduces to
5x + 2z = 13
x - z = 1
2
Introduction (II)
3
Introduction Example Vibration of Three Railroad Cars
x1
k1
x2
k2
x3
k3
m1
m2
m3
Vibration of three railroad cars connected to each other by a
spring on a barge.
Newton’s second law to each car yields
-k1 x1
+ k2 (x2 – x1)
=
m1 a1
-k2 (x2 – x1) + k3 (x3 – x2) =
m2 a2
-k3 (x3 – x2)
=
m3 a3
4
Introduction Example Vibration of Three Railroad Cars
Let k1 = k2 = k3 = k =10000 kg/s2, and m1 = 2000 kg, m2 = 3000 kg, and m3 = 1000 kg.
Determine the relative location of each car when their acceleration are all the same and
equal to 1 m/s2. Substituting these values into the above equations and rearranging yield
-2x1 + x2
x1 - 2x2
x2
+
-
x3
x3
= 0.2
= 0.3
= 0.1
This particular form is very suitable for matrix representation of the system of equations
such that
[A]{X} = {C}
where [A] denotes the matrix of coefficients, {X} represents the vector of the unknowns,
x1, x2, x3, and {C} represents the right hand side coefficients (or constants) as a vector:
 2
1

 0
1
2
1
0  x1  0.2
   
1  x 2    0.3
1 x 3   01
. 
5
Introduction Example Forces Acting on a Simple Truss
Drawing a free body diagram at every joint and setting the summation of forces in x- and
y-directions separately to zero give the following set of equations.
from joint a:
from joint c:
Fax + Fab cos45 + Fad cos30 = 0
Fay + Fab sin45 + Fad sin30 = 0
-Fcd cos30 – Fbc cos45 = 0
Fcy + Fcd sin30 + Fbc sin45 = 0
from joint b:
from joint d:
-Fab cos45 + Fbc cos45 + 3 = 0
-Fab sin45 – Fbc sin45 –Fbd = 0
-Fad cos30 + Fcd cos30 = 0
Fbd – Fad sin30 – Fcd sin30
6
Introduction Example Forces Acting on a Simple Truss
Rearranging and organizing the equations:
Fax
Fay
+
+
-
cos(45) Fab
sin(45) Fab
cos(45) Fab
sin(45) Fab
+ cos(30) Fad
+ sin(30) Fad
+ cos(45) Fbc
- sin(45) Fbc
- cos(45) Fbc
sin(45) Fbc
- cos(30) Fad
- sin(30) Fad
- Fbd
+ Fbd
+
+
-
cos(30) Fcd
sin(30) Fcd
cos(30) Fcd
sin(30) Fcd
+ Fcy
=0
=0
= -3
=0
=0
=0
=0
=0
Again we have arranged the equations in such an organized fashion that it can be easily
put into the form of a matrix equation. Let
F1 = Fax, F2 = Fay, F3 = Fab, F4 = Fad, F5 = Fbc, F6 = Fbd, F7 = Fcd, and F8 = Fcy
The matrix equation then can be written as
[G]{F} = {L}
Where the [G] is the geometry matrix, {F} is the force vector, and {L} is the load vector.7
Introduction Example Forces Acting on a Simple Truss
Gi1
Gi2
Gi3
Gi4
Gi5
Gi6
Gi7
Gi8

Colm. 1
2
3
4
5
6
7
8
Row i

1
2
3
4
5
6
7
8
0
1
0
0
0
0
0
0
.707
.707
-.707
-.707
0
0
0
0
.866
.5
0
0
0
0
-.866
-.5
0
0
.707
-.707
-.707
.707
0
0
0
0
0
-1
0
0
0
1
0
0
0
0
-.866
.5
.866
-.5
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
Fi
Li
F1
F2
F3
F4
F5
F6
F7
F8
0
0
-3
0
0
0
0
0
The system of equations Equation 3.1.11 should be solved for the 8 unknowns. The
solutions are Fax = -3 kN, Fay = -1.5 kN, Fab = -0.776 kN, Fad = 4.10 kN, Fbc = -5.02
kN, Fbd = 4.10 kN, Fcd = 4.10 kN, Fcy = 1.5 kN. Solving 8 equations for 8 unknowns by
hand is, of course, not a desirable assignment. Thanks to the computers and the solution
algorithms we shall present in this chapter this task can be performed with relative ease. 8
Review of Matrix Algebra
Let [A] be a general 3x3 matrix denoted as
[A] = aij =
a11
a21
a31
a12
a22
a32
a13
a23
a33
where the first index i=1,2,3 denotes the row number, and the second index j=1,2,3
denotes the column number. We call the elements aii, i.e. a11, a22, a33 the dioganal
elements, those elements above the diagonal the upper diagonal elements, and those
below the diagonal the lower diagonal elements.
When the lower diagonal elements are zero the matrix is called an upper triangular matrix,
and when the upper diagonal elements are zero it is called lower triangular matrix.
In general a matrix with m rows and n columns is donated by
[A] = aij ; i=1,2,3,...,m; j=1,2,3,...,n
When m=n the matrix is called a square matrix. The size of the matrix is denoted by nxm.
9
Review of Matrix Algebra Addition
In order that two matrices can be added to each other they must be of the same size. The
elements of the sum of two matrices is the sum of the corresponding elements of the two
matrices, hence
[A] + [B] = [C]
means
aij + bij = cij
i.e. c11 = a11 + b11; c12 = a12 + b12; c21 = a21 + b21 etc.
10
Review of Matrix Algebra Multiplication
In order that two matrices can be multiplied the latter matrix must have the same
number of rows as the number of columns of the first. That is
[A]mxn [B]nxk = [C]mxk
The resulting product matrix has the same number of rows as the first and the same
number of columns as the second matrix. In index notation the multiplication of two
matrices is written as
 aij bjk = cik
where the summation is over the index “j”. It is important to note that the order of
multiplication can not be changed, that is
[A][B]  [B][A]
11
Example E3.2.1
Problem: Find the product of the matrices given below:
[A] = aij =
1
2
3
-1
-2
0
0
1
-1
[B] = bjk =
2
0
3
-1
1
0
Solution:
i=1, k=1
c11 = a11b11 + a12b21 + a13b31 = 1 * 2 + -1 * 0 + 0 * 3 = 2
i=2,k=1
c21 = a21b11 + a22b21 + a23b31 = 2 * 2 + -2 * 0 + 1 * 3 = 7
i=3,k=1
c31 = a31b11 + a32b21 + a33b31 = 3 * 2 + 0 * 0 + -1 * 3 = 3
i=1,k=2
c12 = a11b12 + a12b22 + a13b32 = 1 * -1 + -1 * 1 + 0 * 0 = -2
i=2,k=2
c12 = a21b12 + a22b22 + a23b32 = 2 * -1 + -2 * 1 + 1 * 0 = -4
i=3,k=2
c12 = a31b12 + a32b22 + a33b32 = 3 * -1 + 0 * 1 + -1 * 0 = -3
[C] = cik =
2
7
3
-2
-4
-3
12
Transpose and Determinant of a Matrix
The transpose of a matrix, [A]T is obtained by interchanging the rows of the original
matrix by the columns.
[B] = [A]T ; bij = aji
For a symmetric matrix [A] it follows then, [A]T = [A].
The Determinant of a matrix is defined by
det[A] = (-1)i+j aij (determinants of the minor matrices)
The minor matrix is a submatrix of the original matrix obtained by closing the ith row and
the jth column. If two rows are interchanged the determinant changes sign. The smallest
submatrix is a 2x2 matrix and its determinant is given by
a
det  11
a 21
a 12 
 a 11a 22  a 21a 12
a 22 
If det[A] = 0, then the matrix [A] is said to be singular and the system has no unique
solution.
13
Example E3.2.2 Find the Determinant of a Matrix
14
Identity Matrix and the Inverse of a Matrix
The inverse, [A]-1, of a matrix, [A], is defined such that
[A][A]-1 = [I] = [A]-1[A]
where the matrix [I] is called the identity matrix with diagonal elements
equal to one, and all other elements are zero. For example a 4x4 identity
matrix is given by
1
0
I  0

0
0
1
0
0
0
0
1
0
0
0
0

1
15
Inverse of a matrix
16
Inverse of a matrix (Cont’d)
17
Rules Governing Matrix Algebra
Associative laws
([A]+[B])+[C] = [A]+([B]+[C])
([A][B])[C] = [A]([B][C])
Commutative law
[A] + [B] = [B] + [A]
Distributive law
[A]([B]+[C]) = [A][B] + [A][C]
([A][B])T = [B]T [A]T
([A] + [B])T =[A]T + [B]T
Inverse
(c=constant)
([A][B])-1 = [B]-1 [A]-1
(c[A])-1 = [A]-1/c
Determinant
det([A][B]) = det[A]det[B]
det([A]T) = det[A]
det(c[A]) = cn det[A]
(c=constant)
(n=order)
18
Matrix Norms
The norm of a vector or a matrix is a non-negative number that is a measure of the
magnitude of that vector or matrix. The magnitude (or the norm) of a scalar number is its
absolute value. Since there are more than one scalar involved in vectors and matrices the
norms for vectors and matrices can be defined and computed in many ways. The
magnitude of vector is usually defined as the square root of the sum of the squares of its
elements (or components), i.e. for {v} = -1i + 2j -3k; v1 = -1, v2 = 2, v3 = -3 the magnitude
is given by
{V} =
v 12  v 22  v 23  (1  4  9)
1
2
 3.74
This norm is known as the Euclidian norm, and is give by
{V} 
 
n
v
i 1
2
i
1
2
In general a “p” norm can be defined by
{V} 
 
n
v
i 1
p
i
1
p
19
Matrix Norms (II)
Another commonly used norm is the so-called uniform vector norm given by
{V}  max v i for 1 i  n
Similar norms are defined for a matrix, [A] of size nxn as follows:
Frobenius norm:
[A ] e 

n n
 a
i 1 j1
2
ij

1
2
Uniform matrix norm (or row-sum norm):
[ A ]   max
  for 1 i  n
n
 a ij
j1
Column norm (or column-sum norm):
[ A ] c  max
  for 1 j  n
n
 a ij
i 1
20
Example E3.2.3
Problem: Compute the three common norms for the following matrix
1
A   2
 3
2
3
4
1
2
5 
Solution: Using the definitions, we obtain
Frobenius norm:
[ A ] e  {(1)2 + (2)2 + (3)2 + (-2)2 + (3)2 + (4)2 + (-1)2 + (-2)2 + (5)2 }1/2 = 8.54
Uniform matrix norm:
[A ]  
max{(1+2+1), (2+3+2), (3+4+5)}
= max(4,7,12) = 12
Column norm:
[A ] c 
max{(1+2+3), (2+3+4), (1+2+5)}
= max(6,9,8) = 9
21
Condition Number and Ill-Conditioned Systems
The condition number of a matrix, A. is defined by
Cond([A]) = [A ] [A ]1
where the symbol
indicates any norm of the matrix. It can be shown by matrix
algebra, that the condition number of a matrix is always greater than or equal to one.,
i.e.
1
1
= I = 1
Cond ([A]) = [A ] [A]  [A][A ]
If the condition number of a matrix is “large” it is said to be ill-conditioned. Systems
of equations that involve ill-conditioned matrices are difficult to solve. These systems
must be first preconditioned before attempting to find a numerical solution. How
large should the condition number be before one can call a matrix truly illconditioned is a matter of order of magnitudes. For ill-conditioned systems, a small
change in coefficients leads to large changes in the solution.
22
Example E3.3.1
Problem:Find the condition number of the following matrix:
[A] =
 23
[A]-1 = (1/56)  16

 1
1  2  1 
 2 3  2


5 
 3 4
6
8
10
7
0
7
Solution: Using the uniform matrix norm:
[A]  = Max (4, 7, 12) = 12;
[A ]1  = Max[(1/56) (36, 24, 18)] = 36/56 = 9/14
Cond ([A]) = (12)(9/14) = 54/7
Using the Column norm
[A] c = Max (6, 9, 8) = 9;
[ A ]1 c = Max[(1/56) (40, 24, 14)] = 40/56 = 5/7
Cond ([A]) = (9)(5/7) = 45/7
23
Rules of Thumb for Checking the Condition of a
Matrix
Apply the following tests after scaling (or normalizing) the matrix, [A], such that the
largest element in each row is one.
(i) If the sum of the absolute value of off-diagonal elements is less than the
absolute value of the diagonal element for each row separately, this matrix is most
likely to be well-conditioned. Note that interchanging the rows, i.e. partial pivoting,
does not improve the condition number of a matrix.
(ii) If det[A]  0. This matrix is ill-conditioned.
(iii) If there are elements of [A]-1 which are several order of magnitude
larger than one, it is most likely that this matrix is ill-conditioned.
(iv) Let [I]* = [A] [A]-1; if [I]* is significantly different (i.e. the diagonal
elements are not close to one) than the identity matrix, [I], then the matrix [A] is
likely to be ill-conditioned.
(v) Let [A]* = {[A]-1}-1 ; if [A]* is not close to the original matrix [A] the
matrix is most likely to be ill-conditioned.
24
Example E3.3.2
Problem: Given the following
 0.0001
A  
 1.0000
1.0000 
0.1000
Show that the condition number of the matrix does not change when the rows are
interchanged.
A
1
Solution:
0.1000

1.0000
1.0000
0.0001
Now interchange the rows to obtain
 1.0000
B  
 0.0001
0.1000
1.0000 
B
1
 1.0000

 0.0001
0.1000
1.0000 
One can show that the inverse of the matrices are right by checking if the product
[B][B]-1 = I is satisfied.
Using the Froberius norm we find
cond([A]) = ||[A]||e||[A]-1||e = (1.4177)(1.4177) = 2.001
cond([B]) = ||[B]||e||[B]-1||e = (1.4177)(1.4177) = 2.001
25
Direct Methods for Solving Linear Systems
Survey of several commonly used direct methods meaning that when the outlined
procedure or (algorithm) is completed we get the solution, hence there is no need for
iteration to improve an approximate solution.
Cramer’s Method:
This method is the oldest but the most cumbersome and expensive method to solve a
given system of linear equations. It requires computation of (n+1) determinants of nxn
matrices, where n is the number of unknowns. The rule is given by
xi = det{[A]*}/det[A]
(3.4.1)
for i=1,2,3,...,n
where [A]* is the modified matrix where the “i”th column is replaced by the right
hand side of the equations, i.e. by {c}T = (c1,c2,c3, ...
26
Example E3.4.1
Problem: Find the solution of the system of equations given by Equation (3.1.4).
Solution: First we write the equations in matrix form [A]{X}={C}
and observe that
0
a 0 
1
1
1
 
 
1

C

X

a


A

1
1


1
  
 1

 1
a 
1
2
4
 
 2
x1 = a0 = det[A*]1/det[A];
where
A 
*
2
1
 1
1
It follows then
a0 = 8/6
0
1
1
x2 = a1 = det[A*]2/det[A];
1
1
4
A 
*
3
1
 1
1
1
1
2
0
1 
1
x3 = a2 = det[A*]3/det[A]
A 
*
1
0
  1
1
1
1
2
1
1
4
det[A] = 6
a1 = 3/6 a2 = -5/6
27
References
•
•
•
•
•
•
Celik, Ismail, B., “Introductory Numerical Methods for Engineering Applications”,
Ararat Books & Publishing, LCC., Morgantown, 2001
Fausett, Laurene, V. “Numerical Methods, Algorithms and Applications”, Prentice Hall,
2003 by Pearson Education, Inc., Upper Saddle River, NJ 07458
Rao, Singiresu, S., “Applied Numerical Methods for Engineers and Scientists, 2002
Prentice Hall, Upper Saddle River, NJ 07458
Mathews, John, H.; Fink, Kurtis, D., “Numerical Methods Using MATLAB” Fourth
Edition, 2004 Prentice Hall, Upper Saddle River, NJ 07458
Varol, A., “Sayisal Analiz (Numerical Analysis), in Turkish, Course notes, Firat
University, 2001
http://math.uww.edu/faculty/mcfarlat/inverse.htm
28