gaussian elimination pivoting

Gaussian Elimination

CXA

Merupakan salah satu teknik paling populer dalam menyelesaikan sistem persamaan linear dalam bentuk:

Terdiri dari dua step

1. Forward Elimination of Unknowns.

2. Back Substitution

Forward Elimination

112144

1864

1525

Tujuan Forward Elimination adalah untuk membentuk matriks koefisien menjadi Upper Triangular Matrix

7.000

56.18.40

1525

Forward Elimination

Persamaan linear n persamaan dengan n variabel yang tak diketahui

11313212111 ... bxaxaxaxa nn

22323222121 ... bxaxaxaxa nn

nnnnnnn bxaxaxaxa ...332211

. . . . . .

Contoh

83125

12312

71352

21232

8325

1232

7352

2232

4321

4321

4321

4321

xxxx

xxxx

xxxx

xxxx

matriks input

Forward Elimination

83125

12312

71352

21232

32162

190

13140

92120

12112

31

'14

'4

'13

'3

'12

'2

1'1

5

2

2

2

RRR

RRR

RRR

RR

32162

190

13140

92120

12112

31

415994

500

1973002

912110

12112

31

'14

'4

'23

'3

2'2

1'1

219

4

2

RRR

RRR

RR

RR

Forward Elimination

12572

12143000

319

37100

2912

110

12112

31

'34

'4

3'3

2'2

1'1

45

3

RRR

RR

RR

RR

415994

500

1973002

912110

12112

31

12572

12143000

319

37100

2912

110

12112

31

1435721000

319

37100

2912

110

12112

31

121434'

4

3'3

2'2

1'1

RR

RR

RR

RR

Back substitution

4143

5723

193

72

92

1

121

23

4

4

43

432

4321

x

x

xx

xxx

xxxx

Gauss - Jourdan

39743

22342

15231

6150

8120

15231

'13

'3

'12

'2

1'1

3

2

RRR

RRR

RR

142700

42110

152101

'23

'3

2'2

'21

'1

5

2

3

RRR

RR

RRR

6150

8120

15231

142700

42110

152101

4100

2010

1001

273'

3

'32

'2

'31

'1

212

1

RR

RRR

RRR

Warning..

Dua kemungkinan kesalahan

-Pembagian dengan nol mungkin terjadi pada langkah forward elimination. Misalkan:

- Kemungkinan error karena round-off (kesalahan pembulatan)

655

901.36099.23

7710

321

321

21

xxx

xxx

xx

Contoh

Dari sistem persamaan linear

515

6099.23

0710

3

2

1

x

x

x

6

901.3

7

=

Akhir dari Forward Elimination

1500500

6001.00

0710

3

2

1

x

x

x

15004

001.6

7

=

6

901.3

7

515

6099.23

0710

15004

001.6

7

1500500

6001.00

0710

Kesalahan yang mungkin terjadi

Back Substitution

99993.015005

150043 x

5.1 001.0

6001.6 32

x

x

3500.010

077 321

xxx

15004

001.6

7

1500500

6001.00

0710

3

2

1

x

x

x

Contoh kesalahan

Bandingkan solusi exact dengan hasil perhitungan

99993.0

5.1

35.0

3

2

1

x

x

x

X calculated

1

1

0

3

2

1

x

x

x

X exact

Improvements

Menambah jumlah angka pentingMengurangi round-off error (kesalahan

pembulatan)

Tidak menghindarkan pembagian dengan nol

Gaussian Elimination with Partial PivotingMenghindarkan pembagian dengan nol

Mengurangi round-off error

Pivoting

pka ,npk

Eliminasi Gauss dengan partial pivoting mengubah tata urutan baris untuk bisa mengaplikasikan Eliminasi Gauss secara Normal

Bagaimana caranya ?

Di awal sebelum langkah ke-k pada forward elimination, temukan angka maksimum dari:

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

Jika nilai maksimumnya Pada baris ke p,

Maka tukar baris p dan k.

Partial Pivoting

What does it Mean?Gaussian Elimination with Partial Pivoting ensures that each step of Forward Elimination is performed with the pivoting element |akk| having the largest absolute value.

Jadi,

Kita memeriksa pada setiap langkah apakah angka paling atas (pivoting element) adalah selalu paling besar

Partial Pivoting: Example

655

901.36099.23

7710

321

321

21

xxx

xxx

xx

Consider the system of equations

In matrix form

515

6099.23

0710

3

2

1

x

x

x

6

901.3

7

=

Solve using Gaussian Elimination with Partial Pivoting using five significant digits with chopping

Partial Pivoting: Example

Forward Elimination: Step 1

Examining the values of the first column

|10|, |-3|, and |5| or 10, 3, and 5

The largest absolute value is 10, which means, to follow the rules of Partial Pivoting, we don’t need to switch the rows

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

Partial Pivoting: Example

001.6

5.2

7

6001.00

55.20

0710

3

2

1

x

x

x

Forward Elimination: Step 2

Examining the values of the second column

|-0.001| and |2.5| or 0.0001 and 2.5

The largest absolute value is 2.5, so row 2 is switched with row 3

5.2

001.6

7

55.20

6001.00

0710

3

2

1

x

x

x

Performing the row swap

Partial Pivoting: Example

Forward Elimination: Step 2

Performing the Forward Elimination results in:

002.6

5.2

7

002.600

55.20

0710

3

2

1

x

x

x

Partial Pivoting: Example

002.6

5.2

7

002.600

55.20

0710

3

2

1

x

x

x

Back Substitution

Solving the equations through back substitution

1002.6

002.63 x

15.2

55.2 22

xx

010

077 321

xxx

Partial Pivoting: Example

1

1

0

3

2

1

x

x

x

X exact

1

1

0

3

2

1

x

x

x

X calculated

Compare the calculated and exact solution

The fact that they are equal is coincidence, but it does illustrate the advantage of Partial Pivoting