PRESENTACION GAUUSS. ELIMINACION

8/9/2019 PRESENTACION GAUUSS. ELIMINACION

1/94

Gaussian Elimination

Major: All Engineering Majors

Author(s): Autar Kaw

http://numericalmethods.eng.usf.eduTransforming Numerical Methods Education for STEM

Undergraduates


2/94

Nave Gauss Elimination

http://numericalmethods.eng.usf.edu


3/94

Nave Gaussian Elimination

A method to solve simultaneous linearequations of the form [A][X]=[C]

Two steps1. Forward Elimination2. Back Substitution


4/94

Forward Elimination

-

!

-

-

2.279

2.177

8.106

112144

1864

1525

3

2

1

x

x

x

The goal of forward elimination is to transform thecoefficient matrix into an upper triangular matrix

-

!

-

-

735.0

21.96

8.106

7.000

56.18.40

1525

3

2

1

x

x

x


5/94

Forward Elimination

A set of n equations and n unknowns

11313212111 ... bxaxaxaxa nn !

22323222121 ... bxaxaxaxa nn !

nnnnnnn bxaxaxaxa ! ...332211

. .

. .

. .

(n-1) steps of forward elimination


6/94

Forward Elimination

Step 1For Equation 2, divide Equation 1 by andmultiply by .

)...( 1131321211111

21 bxaxaxaxaa

ann !

-

111

21

111

21

21211

21

121... b

a

axa

a

axa

a

axa

nn!

11a

21a


7/94

Forward Elimination

1

11

211

11

21212

11

21121 ... b

a

axa

a

axa

a

axa nn !

1

11

2121

11

212212

11

2122 ... b

a

abxa

a

aaxa

a

aa nnn !

'

2

'

22

'

22 ... bxaxa nn !

22323222121 ... bxaxaxaxa nn !Subtract the result from Equation 2.

_________________________________________________

or


8/94

Forward Elimination

Repeat this procedure for the remainingequations to reduce the set of equations as

11313212111 ... bxaxaxaxa nn !

'2

'23

'232

'22 ... bxaxaxa nn !

'

3

'

33

'

332

'

32 ... bxaxaxa nn !

''

3

'

32

'

2 ... nnnnnn bxaxaxa !

. . .

. . .

. . .

End of Step 1


9/94

Step 2Repeat the same procedure for the 3rd termof Equation 3.

Forward Elimination

11313212111

... bxaxaxaxann

!

'

2

'

23

'

232

'

22 ... bxaxaxa nn !

"

3

"

33

"

33 ... bxaxa nn !

""

3

"

3 ... nnnnn bxaxa !

. .

. .

. .

End of Step 2


10/94

Forward Elimination

At the end of (n-1) Forward Elimination steps, thesystem of equations will look like

'

2'

23'

232'

22 ... bxaxaxa nn !"

3

"

33

"

33 ... bxaxa nn !

11 ! nnnn

nn bxa

. .

. .

. .

11313212111 ... bxaxaxaxa nn !

End of Step (n-1)


11/94

Matrix Form at End of Forward

Elimination

-

!

-

-

)(n-

n

"

'

n

)(n

nn

"

n

"

'

n

''

n

b

b

b

b

x

x

x

x

a

aa

aaa

aaaa

1

3

2

1

3

2

1

1

333

22322

1131211

0000

00

0

///.///

.

.

.


12/94

Back Substitution

Solve each equation starting from the last equation

Example of a system of 3 equations

-

!

-

-

735.0

21.96

8.106

7.000

56.18.40

1525

3

2

1

x

x

x


13/94

Back Substitution Starting Eqns

'

2

'

23

'

232

'


3

"

3

"

33 ... bxaxa nn !

11!

n

nn

n

nn bxa

. .

. .

. .

11313212111 ... bxaxaxaxa nn !


14/94

Back Substitution

Start withthe lastequation because ithas only oneunknown

)1(

)1(

!n

nn

n

nn

a

bx


15/94

Back Substitution

1,...,1for11

11

!!!

nia

xabxi

ii

n

ij j

i

ij

i

i

i

)1(

)1(

!n

nn

n

nn

a

bx

1,...,1or

...1

1,212,111,1!!

nia

xaxaxabxi

ii

n

i

nii

i

iii

i

ii

i

i

i


16/94

THEEND



17/94

Additional Resources

For all resources on this topic such as digital audiovisuallectures, primers, textbook chapters, multiple-choice tests,worksheets in MATLAB, MATHEMATICA, MathCad andMAPLE, blogs, related physical problems, please visit

http://numericalmethods.eng.usf.edu/topics/gaussian_elimination.html


18/94

Nave Gauss EliminationExample



19/94

Example 1

Theupward velocity ofarocket is given atthree

differenttimes

Time, Veloc

ity,

5 106.8

8 177.2

12 279.2

The velocity data isapproximated by apolynomial as:

12.t5,3221 ee! atatatvFindthe velocity att=6seconds .

st m/sv

Table 1 Velocity vs. timedata.


20/94

Example 1 Cont.Assume

12.t5,atatatv ee! 3221

-

!

-

-

3

2

1

3

2

3

2

2

2

1

2

1

1

11

v

vv

a

aa

tt

tttt

3

2

1

Results in a matrix template ofthe form:

Using data from Table 1, the matrix becomes:

-

!

-

-

2.279

2.177

8.106

112144

1864

1525

3

2

1

a

a

a


21/94


22/94

Forward Elimination


23/94

Number of Steps of Forward

Elimination

Number of steps of forward elimination is

(n1)!(31)!2


24/94

Divide Equation 1 by 25 and

multiply it by 64, .

Forward Elimination: Step 1

.

? A ? A408.27356.28.126456.28.1061525 // !v

? A

? A

? A208.9656.18.40

408.27356.28.1264

177.21864

/

/

/

-

2.279112144

2.17718648.1061525

/

/

/

-

2.279112144

208.9656.18.40

8.1061525

/

/

/

56.225

64!

Subtract the result fromEquation 2

Substitute new equation forEquation 2


25/94

Forward Elimination: Step 1 (cont.)

.

? A ? A168.61576.58.2814476.58.1061525 // !v

-

2.279112144

208.9656.18.40

8.1061525

/

/

/

? A

? A

? A968.33576.48.160

168.61576.58.28144

279.2112144

/

/

/

-

968.33576.48.160

208.9656.18.40

8.1061525

/

/

/


multiply it by 144, .76.525

144!




26/94


? A ? A728.33646.58.1605.3208.9656.18.40 !v //

-

968.33576.48.160

208.9656.18.40

8.1061525

/

/

/

? A

? A

? A.7607.000

728.33646.516.80

335.96876.416.80

/

/

/

-

76.07.000

208.9656.18.40

8.1061525

/

/

/

Divide Equation 2 by 4.8

and multiply it by 16.8,

.5.38.4

8.16!




27/94

Back Substitution


28/94

Back Substitution

-

!

-

-

-

76.0

208.96

8.106

7.000

56.18.40

1525

7.07.000

2.9656.18.40

8.1061525

3

2

1

a

a

a

/

/

/

08571.1

7.076.0

76.07.0

3

3

3

!

!

!

a

a

a

Solving for a3


29/94

Back Substitution (cont.)

Solving for a2

690519.

4.8

1.085711.5696.208

8.4

56.1208.96

208.9656.18.4

2

2

32

32

!

v!

!

!

a

a

aa

aa

-

!

-

-

76.0

208.96

8.106

7.000

56.18.40

1525

3

2

1

a

a

a


30/94


Solving for a1

290472.0

25

08571.16905.1958.10625

58.106

8.106525

321

321

!

v!

!

!

aaa

aaa

-

!

-

-

76.0

2.96

8.106

7.000

56.18.40

1525

3

2

1

a

a

a


31/94

Nave Gaussian Elimination Solution

-

!

-

-

2279

2177

8106

112144

1864

1525

3

2

1

.

.

.

a

a

a

-

!

-

08571.1

6905.19

290472.0

3

2

1

a

a

a


32/94

Example 1 Cont.

Solution

Thesolution vector is

-

!

-

08571.1

6905.19

290472.0

3

2

1

a

a

a

Thepolynomial thatpassesthroughthethreedatapoints isthen:

125,08571.16905.19290472.02

32

2

1

ee!

!

ttt

atatatv

.m/s686.129

08571.166905.196290472.062

!

!v


33/94

THEEND



34/94

Nave Gauss EliminationPitfalls



35/94

955

11326

3710

321

321

32

!

!

!

xxx

xxx

xx

Pitfall#1. Division by zero

-

!

-

-

911

3

515326

7100

3

2

1

xx

x


36/94

Is division by zero an issue here?

955

14356

1571012

321

321

321

!

!

!

xxx

xxx

xxx

-

!

-

-

9

14

15

515

356

71012

3

2

1

x

x

x


37/94

Is division by zero an issue here?YES

28524

14356

1571012

321

321

321

!

!

!

xxx

xxx

xxx

-

!

-

-

28

14

15

5124

356

71012

3

2

1

x

x

x

-

!

-

-

2

5.6

15

192112

5.600

71012

3

2

1

x

x

x

Division by zero is a possibility at any stepof forward elimination


38/94

Pitfall#2. Large Round-off Errors

-

!

-

-

9

751.1

45

315

7249.23

101520

3

2

1

x

x

x

Exact Solution

-

!

-

1

1

1

3

2

1

x

x

x


39/94


-

!

-

-

9

751.1

45

315

7249.23

101520

3

2

1

x

x

x

Solve it on a computer using 6 significant digits with chopping

-

!

-

999995.0

05.1

9625.0

3

2

1

x

x

x


40/94


-

!

-

-

9

751.1

45

315

7249.23

101520

3

2

1

x

x

x

Solve it on a computer using5 significant digits with chopping

-

!

-

99995.0

5.1

625.0

3

2

1

x

x

x

Is there a way to reduce the round off error?


41/94

Avoiding Pitfalls

Increase the number of significant digits

Decreases round-off error

Does not avoid division by zero


42/94

Avoiding Pitfalls

Gaussian Elimination with Partial Pivoting

Avoids division by zero

Reduces round off error


43/94

THEEND



44/94

Gauss Elimination withPartial Pivoting



45/94

Pitfalls of Nave Gauss Elimination

Possible division by zero

Large round-off errors


46/94

Avoiding Pitfalls

Increase the number of significant digits

Decreases round-off error

Does not avoid division by zero


47/94

Avoiding Pitfalls

Gaussian Elimination with Partial Pivoting

Avoids division by zero

Reduces round off error


48/94

What is Different About PartialPivoting?

pka

At the beginning of the kth step of forward elimination,find the maximum of

nkkkkk aaa .......,,........., ,1

If the maximum of the values is

in the p th row, ,npk ee then switch rows p and k.


49/94


50/94

Example (2nd step of FE)

-

!

-

-

3

9

8

6

5

431112170

862390

1111240

21670

67.31.5146

5

4

3

2

1

x

x

x

x

x

Which two rows would you switch?


51/94

Example (2nd step of FE)

-

!

-

-

6

9

8

3

5

21670

862390

1111240

431112170

67.31.5146

5

4

3

2

1

x

x

x

x

x

Switched Rows


52/94

Gaussian Eliminationwith Partial Pivoting

A method to solve simultaneous linearequations of the form [A][X]=[C]

Two steps1. Forward Elimination

2. Back Substitution


53/94

Forward Elimination

Same as nave Gauss elimination methodexcept that we switch rows before eachof the (n-1) steps of forward elimination.


54/94

Example: Matrix Form at Beginning

of 2nd Step of Forward Elimination

-

!

-

-

'

'

3

2

1

3

2

1

''

4'

32

'

3

'

3332

22322

1131211

0

00

n

'

nnnnn'n

n

'

'

n

''

n

b

bb

b

x

xx

x

aaaa

aaa

aaa

aaaa

///.///

.

.

.


55/94

Matrix Form at End of Forward

Elimination

-

!

-

-

)(n-n

'

n)(n

nn

n

'

n

''

n

b

bb

b

x

xx

x

a

aa

aaa

aaaa

1

3

2

1

3

2

1

1

333

22322

1131211

0000

000

///.///

.

.

.


56/94

Back Substitution Starting Eqns

'

2

'

23

'

232

'


3

"

3

"

33... bxaxa

nn!

11 !

n

nn

n

nn bxa

. .

. .

. .

11313212111 ... bxaxaxaxa nn !


57/94

Back Substitution

1,...,1or11

11

!

!

!

nia

xab

xi

ii

n

ijj

i

ij

i

i

i

)1(

)1(

!n

nn

n

nn

a

bx


58/94

THEEND



59/94

Gauss Elimination withPartial PivotingExample



60/94

Example 2

-

!

-

-

2279

2177

8106

112144

1864

1525

3

2

1

.

.

.

a

a

a

Solve the following set of equationsby Gaussian elimination with partialpivoting


61/94

Example 2 Cont.

-

!

-

-

2279

2177

8106

112144

1864

1525

3

2

1

.

.

.

a

a

a

1. Forward Elimination

2. Back Substitution

-

2.279112144

2.1771864

8.1061525

/

/

/


62/94

Forward Elimination


63/94

Number of Steps of Forward

Elimination

Number of steps of forward elimination is

(n1)=(31)=2


64/94


Examine absolute values of first column, first rowand below.

144,64,25

Largest absolute value is 144 and exists in row 3.

Switch row 1 and row 3.

-

-

8.10615252.1771864

2.279112144

2.2791121442.1771864

8.1061525

/

/

/

/

/

/


65/94


.

? A ? A1.1244444.0333.599.634444.02.279112144 // !v

-

8.1061525

2.17718642.279112144

/

/

/

? A

? A

? A10.53.55560667.20

124.10.44445.33363.99

177.21864

/

/

/

-

8.1061525

10.535556.0667.20

2.279112144

/

/

/



64!




66/94


.

? A ? A47.481736.0083.200.251736.0279.2112144

// !v

? A

? A

? A33.588264.0917.20

48.470.17362.08325

106.81525

/

/

/

-

8.1061525

10.535556.0667.202.279112144

/

/

/

-

33.588264.0917.20

10.535556.0667.20

2.279112144

/

/

/



25!




67/94


Examine absolute values of second column, second rowand below.

2.917,667.2

Largest absolute value is 2.917 and exists in row 3.

Switch row 2 and row 3.

-

-

10.535556.0667.20

33.588264.0917.20

2.279112144

33.588264.0917.20

10.535556.0667.20

2.279112144

/

/

/

/

/

/


68/94


.

? A ? A33.537556.0667.209143.058.330.82642.9170 // !v

-

10.535556.0667.20

33.588264.0917.202.279112144

/

/

/

? A

? A

? A23.02.000

53.330.75562.6670

53.100.55562.6670

/

/

/

-

23.02.000

33.588264.0917.20

2.279112144

/

/

/

Divide Equation 2 by 2.917 and

multiply it by 2.667,

.9143.0917.2

667.2!




69/94

Back Substitution


70/94

Back Substitution

1.15

2.0

23.0

23.02.0

3

3

!

!

!

a

a

Solving for a3

-

!

-

-

-

230

3358

2279

2000

8264091720

112144

23.02.000

33.588264.0917.20

2.279112144

3

2

1

.

.

.

a

a

a

.

..

/

/

/


71/94


Solving for a2

6719.

917.2

15.18264.033.58917.2

8264.033.58

33.588264.0917.2

32

32

!

v!

!

!

aa

aa

-

!

-

-

230

3358

2279

2000

8264091720

112144

3

2

1

.

.

.

a

a

a

.

..


72/94


Solving for a1

2917.0

144

15.167.19122.279144

122.279

2.27912144

321

321

!

v!

!

!

aaa

aaa

-

!

-

-

230

3358

2279

2000

8264091720

112144

3

2

1

.

.

.

a

a

a

.

..


73/94

Gaussian Elimination with Partial

Pivoting Solution

-

!

-

-

2279

2177

8106

112144

1864

1525

3

2

1

.

.

.

a

a

a

-

!

-

15.1

67.19

2917.0

3

2

1

a

a

a


74/94

Gauss Elimination withPartial PivotingAnother Example



75/94

Partial Pivoting: Example

Considerthesystem ofequations

655

901.36099.23

7710

321

321

21

!

!

!

xxx

xxx

xx

In matrix form

-

515

6099.23

0710

-

3

2

1

x

x

x

-

6

901.3

7

=

Solveusing Gaussian Elimination with Partial Pivoting using five

significantdigits withchopping


76/94


Forward Elimination:Step 1

Examining the values ofthe firstcolumn

|10|, |-3|, and |5| or10, 3, and 5

The largestabsolute value is 10, which means, to

follow therules of Partial Pivoting, weswitch

row1 withrow1.

-

!

-

-

6

901.3

7

515

6099.23

0710

3

2

1

x

x

x

-

!

-

-

5.2

001.6

7

55.20

6001.00

0710

3

2

1

x

x

x

Performing Forward Elimination


77/94



Examining the values ofthe firstcolumn

|-0.001| and |2.5| or0.0001 and 2.5

The largestabsolute value is 2.5, so row 2 isswitched withrow 3

-

!

-

-

5.2

001.67

55.20

6001.000710

3

2

1

x

xx

-

!

-

-

001.6

5.27

6001.00

55.200710

3

2

1

x

xx

Performing therow swap


78/94



Performing theForward Elimination results in:

-

!

-

-

002.6

5.2

7

002.600

55.20

0710

3

2

1

x

x

x


79/94


Back Substitution

Solving theequationsthrough back substitution

1002.6

002.6

3 !!x

15.2

55.2 32 !

!

xx

010

077 321 !

!

xxx

-

!

-

-

002.6

5.2

7

002.600

55.20

0710

3

2

1

x

x

x


80/94


? A

-

!

-

!

1

1

0

3

2

1

x

x

x

X exact? A

-

!

-

!

1

1

0

3

2

1

x

x

x

Xcalculated

Comparethecalculatedandexactsolution

The factthatthey areequal iscoincidence, but it

does illustratetheadvantage of Partial Pivoting


81/94

THEEND



82/94

Determinant of a Square MatrixUsing Nave Gauss Elimination

Example



83/94

Theorem ofDeterminants

If a multiple of one row of [A]nxn is added or

subtracted to another row of [A]nxn to result in

[B]nxn then det(A)=det(B)


84/94

Theorem ofDeterminants

The determinant of an upper triangular matrix

[A]nxn is given by

nnii aaaa vvvvv! ......Adet 2211

!

!n

i

iia1

Forward Elimination of a


85/94

Forward Elimination of aSquare Matrix

Using forward elimination to transform [A]nxn to an

upper triangular matrix, [U]nxn.

? A ? A nnnn UA vv p

UA detdet !


86/94

Example

112144

1864

1525

-

Using nave Gaussian elimination find thedeterminant of the following squarematrix.


87/94

Forward Elimination


88/94


.

? A ? A56.28.126456.21525 !v ? A

? A

? A56.18.40

56.28.1264

1864

112144

18641525

-

112144

56.18.40

1525

-



64!




89/94


.

? A ? A76.58.2814476.51525 !v

? A

? A

? A76.48.160

76.58.28144

112144

76.48.160

56.18.40

1525

-

112144

56.18.40

1525

-



144!




90/94


.

76.48.160

56.18.401525

-

? A

? A

46.58.1605.356.18.40

!v

? A

? A

? A7.000

46.58.160

76.48.160

7.000

56.18.40

1525

-

Divide Equation 2 by 4.8

and multiply it by 16.8,

.5.38.4

8.16!




91/94

Finding the Determinant

.

7.000

56.18.40

1525

112144

1864

1525

-

p

-

After forward elimination

00.84

7.08.425

det 332211

!vv!

vv! uuu


92/94

Summary

-Forward Elimination

-Back Substitution

-Pitfalls

-Improvements

-Partial Pivoting

-Determinant ofa Matrix


93/94

Additional Resources

For all resources on this topic such as digital audiovisuallectures, primers, textbook chapters, multiple-choice tests,worksheets in MATLAB, MATHEMATICA, MathCad andMAPLE, blogs, related physical problems, please visit

http://numericalmethods.eng.usf.edu/topics/gaussian_elimination.html


94/94

THEEND


Documents

PRESENTACION GAUUSS. ELIMINACION