Linear Equations and Gaussian Elimination
Download
Report
Transcript Linear Equations and Gaussian Elimination
Solving Linear Equations
Given the equations
3x + 4y = 10
2x + z = 7
y + 2z = 7
Solve by removing x and y, to find z, and thence find x and y.
First equation * 2 - second equation * 3 gives
8y - 3z = -1
That equation - third equation * 8 gives
-19z = -57, so z = 3.
So
y = 7 - 2z = 1
2x = 7 - z = 4
So
x=2
We now present a matrix method for doing that.
p1 RJM 07/08/02
EG1C2 Engineering Maths: Matrix Algebra 5
Linear Equations and Gaussian Elimination
A linear system, described by n equations in n unknowns,
a11 x1 + a12 x2 + .. a1n xn = b1
a21 x1 + a22 x2 + .. a2n xn = b2
:
:
:
:
an1 x1 + an2 x2 + .. ann xn = bn
can be expressed in matrix terms: A x = b; where
a11 a12 .. a1n
x1
b1
a
x
b
a
..
a
2n x = 2 b = 2
A = 21 22
:
:
:
:
:
a
x
b
a
..
a
n1 n2
n
n
nn
Can use inverses to find x. Better method - Gaussian elimination.
Reduce A to a triangular matrix (echelon form) then find each x.
p2 RJM 07/08/02
EG1C2 Engineering Maths: Matrix Algebra 5
Form Augmented Matrix then process
a11 a12 .. a1n b1
a
a
..
a
b
~
2n 2
A = 21 22
:
: :
:
a
a
..
a
b
n1 n2
nn n
Augmented Matrix is
A and b combined
Make A part triangular
This means
'
a '
a12
11
'
0 a 22
:
:
0
0
p3 RJM 07/08/02
' x '
.. a1n
b1
1
'
'
.. a 2n x 2 b 2
: : :
'
'
.. a x n b
nn
n
'
a '
a12
11
~ ' 0 a '22
A =
:
:
0
0
'
.. a1n
b1'
'
'
.. a 2n b 2
: :
'
'
.. a nn b n
Hence xn found easily,
then xn-1, xn-2, etc.
EG1C2 Engineering Maths: Matrix Algebra 5
Demonstrate this by example
i1
i2
3
14V
i3
5
1V
2
The equations describing the above are:
1 - 1 - 1 i1 0
i.e. 3 5 0 i 2 14
0 5 - 2 i3 1
1 - 1 - 1 0
~
So, A = 3 5 0 14
0 5 - 2 1
i1 - i 2 - i3 = 0
3 i1 + 5 i 2 = 14
5 i 2 - 2 i3 = 1
p4 RJM 07/08/02
EG1C2 Engineering Maths: Matrix Algebra 5
1 - 1 - 1 0
~
Now get A = 3 5 0 14 into echelon form
0 5 - 2 1
Call the first row the pivot row, and the first element the pivot.
Use the pivot row to eliminate the value in the pivot column in
all the rows below the pivot, i.e. to make these elements 0.
Second row: subtract 2rd row from 3 * the pivot row. Get
[3*1 -3 3*-1-5 3*-1-0 0-14] = [0 -8 -3 -14].
Third row - element is already 0 - don’t need to do anything.
1 - 1 - 1 0
~
Thus now A = 0 - 8 - 3 14
0 5 - 2 1
p5 RJM 07/08/02
EG1C2 Engineering Maths: Matrix Algebra 5
Next eliminate the 5 in row 3. Pivot row is row 2, pivot is -8
Then add 5 * pivot row to 8 * third row, so row 3 becomes
[0 -8*5 + 5*8 -3*5 + -2*8 -14*5 + 8 * 1] = [ 0 0 -31 -62]
0
1 - 1 - 1
1 1 1 i1 0
~
A = 0 - 8 - 3 14 This means 0 8 3 i 2 14
0 0 - 31 62
0 0 31 i3 62
Last row represents:
-31*i3 = -62;
i3 = 2A.
Second row represents: -8*i2 - 3*i3 = -14; i2 = (14-3*2)/8 = 1A.
First row represents
i1 = i2 + i3;
i1 = 3A.
As a check: 5i2 - 2 i3 = 5-4 = 1 and 3i1 + 5 i2 = 9+5 = 14 Good!
Comment - At start of process, if a diagonal has a zero value,
swap its row with one which has a non-zero value.
Note, when doing by hand good idea to multiply rows by integers.
p6 RJM 07/08/02
EG1C2 Engineering Maths: Matrix Algebra 5
Exercise
y3
y2
y1
A cantilever beam bends due to its own weight and an applied
force. The relative heights at points along the beam are given by:
-3 y1 + y2 = -2; y1 - 3 y2 + y3 = -5; 2 y2 - 3 y3 = -7
Use Gaussian elimination to find values y1, y2 and y3.
Put equations in
form: A y = b
y1
y
2
y3
~
Hence A =
p7 RJM 07/08/02
EG1C2 Engineering Maths: Matrix Algebra 5
Make first element in row2 zero; do row2 := row1 + 3 * row2:
[
]=[
]
~
Thus A =
Make second element in row3 zero; do row3 := row2 + 4 * row3:
[
]=[
]
~
Thus A =
Row3 means:
Row2 means:
Row1 means:
* y1 +
p8 RJM 07/08/02
* y2 +
* y2 +
* y3 =
* y3 =
* y3 =
EG1C2 Engineering Maths: Matrix Algebra 5
so y3 =
so y2 =
so y1 =
Comments on Method
Matrices are processed by ‘elementary row operations’: each row
processed by: rowX := p*rowY + q*rowZ (p,q <> 0)
Equivalent to processing equations in this way.
If the equations represent a linear system, then this is valid.
To verify, consider equations: 3x + 2y = 5 and 4x - y = 3.
The solution to this is x = y = 1.
Form p*first equation + q*second? Is x = y = 1 still a solution?
3px +2py + 4qx-qy = 5p+3q.
That is p (3x+2y) + q (4x - y) = 5p+3q
Clearly x = y = 1 is still a solution to this equation.
Thus the method seems to be valid.
This method can in fact be extended - for finding inverses
p9 RJM 07/08/02
EG1C2 Engineering Maths: Matrix Algebra 5
Gauss Jordan Method for Matrix Inverse
The adjoint inverse method is computationally poor - particularly
for large matrices. Consider instead the Gauss-Jordan method.
First write a matrix comprising A and I as one. For a 3*3 matrix:
3 - 1 1
3 1 1 1 0 0
e.g. A - 1 3 4
Then [ A I ] 1 3 4 0 1 0
- 1 1 2
1 1 2 0 0 1
Process this so left half is unit matrix. Then right half is inverse.
Do by processing rows:
Row X = p * Row Y + q * Row Z,
so that a suitable element in the row becomes 0 or 1.
First ensure bottom two rows have 0 in their first column:
Row 2 = Row 1 + 3 * Row 2 & Row3 = Row 1 + 3 * Row 3:
p10 RJM 07/08/02
EG1C2 Engineering Maths: Matrix Algebra 5
1
1
1
0
0 3 1 1 1 0 0
3
AI 3 3 1 9 1 12 1 0 0 3 0 0 0 8 13 1 3 0
3 3 1 3 1 6 1 0 0 0 0 3 0 2 7 1 0 3
Next do Row 3 = Row 2 – 4 * Row 3, so 2nd column in row 3 is 0:
1 0 0
3 1 1
AI 0 8 13 1 3 0
0 0 15 3 3 12
Next process top two rows so their entries in column 3 are 0.
Row 1 = Row 3 + 15 * Row 1; Row 2 = 13 * Row 3 + 15 * Row 2
12
3 12
45 15 0
AI 0 120 0 24 84 156
0 15 3 3 12
0
p11 RJM 07/08/02
EG1C2 Engineering Maths: Matrix Algebra 5
Then, make Row 1 column 2 = 0: Row 1 = Row 2 + 8 * Row 1
0
72 108 252
360 0
AI 0 120 0 24 84 156
0 15 3
3
12
0
Now set diagonals of the left half of the matrix to 1:
Row 1 = Row 1 / 360; Row 2 = Row 2 / 120;
Row 3 = Row 3 / -15.
0.3 0.7
0.3 0.7
1 0 0 0.2
0.2
AI 0 1 0 0.2 0.7 1.3 A -1 0.2 0.7 1.3
0 0 1 0.2 0.2 0.8
0.2 0.2 0.8
0.3 0.7 3 1 1 1 0 0
0.2
Check : A -1A = 0.2 0.7 1.3 1 3 4 0 1 0
0.2 0.2 0.8 1 1 2 0 0 1
p12 RJM 07/08/02
EG1C2 Engineering Maths: Matrix Algebra 5