Komputasi Numerik Bab2 PDF

Preview

Summary

2 S ISTEM P ERSAMAAN L INIER S istem persamaan linier merupakan salah satu model dan masalah matematika yang banyak dijumpai di dalam berbagai disiplin, termasuk matematika, statistika, fisika, biologi, ilmu-ilmu sosial, teknik, dan bisnis. Sistem-sistem persamaan linier muncul secara lang- sung dar...

Description

2

S ISTEM P ERSAMAAN L INIER

S

istem persamaan linier merupakan salah satu model dan masalah matematika yang banyak dijumpai di dalam berbagai disiplin, termasuk matematika, statistika, fisika, biologi, ilmu-ilmu sosial, teknik, dan bisnis. Sistem-sistem persamaan linier muncul secara langsung dari masalah-masalah nyata, dan merupakan bagian dari proses penyelesaian masalah-masalah lain, misalnya penyelesaian sistem persamaan non-linier simultan. Suatu sistem persamaan linier terdiri atas sejumlah berhingga persamaan linier dalam sejumlah berhingga variabel. Menyelesaikan suatu sistem persamaan linier adalah mencari nilai-nilai variabel-variabel tersebut yang memenuhi semua persamaan linier yang diberikan. Pada dasarnya terdapat dua kelompok metode yang dapat digunakan untuk menyelesaikan suatu sistem persamaan linier. Metode pertama dikenal sebagai metode langsung, yakni metode yang mencari penyelesaian suatu sistem persamaan linier dalam langkah berhingga. Metode-metode ini dijamin berhasil dan disarankan untuk pemakaian secara umum. Kelompok kedua dikenal sebagai metode tak langsung atau metode iteratif, yang bermula dari suatu hampiran penyelesaian awal dan kemudian berusaha memperbaiki hampiran dalam tak berhingga namun langkah konvergen. Metode-metode iteratif digunakan untuk menyelesaikan sistem persamaan linier berukuran besar dan proporsi koefisien nolnya besar, seperti sistem-sistem yang banyak dijumpai dalam sistem persamaan diferensial.

2.1 Pengertian dan Contoh Suatu persamaan dalam matematika merupakan sebuah ekspresi kesamaan (memuat tanda sama dengan, “=”) yang melibatkan konstanta, variabel, dan operasi-operasi hitung/matematika. Di dalam sebuah persamaan, komponen-komponen yang dijumlahkan atau dikurangkan dise51

2.1 Pengertian dan Contoh

53

maan linier. + a12 x2 + : : : + a1n xn a21 x1 + a22 x2 + : : : + a2n xn a31 x1 + a32 x2 + : : : + a3n xn

a11 x1

a

=

b1

=

b2

=

b3

.. .

n1 x1 + an2 x2 + : : : + ann xn

=

b

(2.1)

n

Kuantitas-kuantitas aij (untuk i; j = 1; 2; : : : ; n) disebut koefisien. Nilai koefisien-koefisien aij dan ruas kanan bi pada setiap persamaan diketahui. Kuantitas-kuantitas xij disebut variabel, yang nilainya belum diketahui dan hendak dicari. Sistem persamaan di atas dapat ditulis dalam bentuk matriks sebagai A

X=B  :

dengan A adalah sebuah matriks n

A

0 BB B =B B

a11

a12

:::

a21

a22

:::

a31

a32

:::

n2

:::

.. .

a

dan

n

n1

.. .

a

.. .

n a 2n a3n a1

.. .

Penulisan SPL (2.1) dalam bentuk persamaan matriks. Pengertian matriks koefisien, matriks konstanta, dan matriks augmented.

1 C C C C C A

nn

a

X dan B adalah vektor-vektor -komponen: T B=( X=( 1 2 3 n) 1 2 n

x ;x ;x ;:::;x

b ; b ; b3 ; : : : ; b

T:

n)

dengan pangkat T menyatakan operasi transpose matriks, yakni mengubah baris menjadi kolom dan kolom menjadi baris. Matriks A disebut matriks koefisien, vektor kolom sering disebut vektor konstanta. Gabungan matriks A dan vektor kolom , yakni matriks n  (n + 1) (A j ), disebut matriks augmented dari SPL (2.1). Apabila semua nilai bi = 0 untuk i = 1; 2; :::; n, maka SPL (2.1) disebut sistem homogen. Jika terdapat bk 6= 0 untuk suatu 1  k  n, maka SPL (2.1) disebut sistem tak homogen. Sistem homogen memegang peranan penting untuk mengetahui ada tidaknya penyelesaian SPL (2.1). Teorema berikut meringkaskan beberapa hasil penting tentang sistem-sistem persamaan linier.

B

B

Pengantar Komputasi Numerik

B

c Sahid (2004 – 2012)

2.1 Pengertian dan Contoh

55

Perhatikan bahwa titik potong kedua garis tersebut merupakan penyelesaian SPL di atas.

Gambar 2.1: SPL dengan penyelesaian tunggal dapat disajikan dengan grafik kurva-kurva linier yang berpotongan di satu titik.

C ONTOH 2.2. Perhatikan SPL

x1 + 3x2 3x1 + 9x2

Contoh SPL dalam dua variabel yang tidak konsisten

= 5 = 7

Jika persamaan kedua dikurangi tiga kali persamaan pertama maka kita dapatkan 0 = 7 15. Ini artinya SPL tersebut tidak mempunyai penyelesaian. Apabila kita plot kedua garis yang menyajikan kedua persamaan linier di atas kita dapatkan dua buah kurva linier yang tidak berpotongan, seperti terlihat pada Gambar 2.2. Kedua garis tersebut saling sejajar satu sama lainnya. C ONTOH 2.3. Perhatikan SPL

2x1 + 3x2 = 5 4x1 + 6x2 = 10 Pengantar Komputasi Numerik

Sebuah SPL yang terdiri atas dua buah persamaan linier yang ekivalen bersifat tidak konsisten.

c Sahid (2004 – 2012)

2.2 Eliminasi Gauss

59

2.2 Eliminasi Gauss Metode eliminasi Gauss digunakan untuk menyelesaikan sebuah sistem persamaan linier dengan mengubah SPL tesebut ke dalam bentuk sistem persamaan linier berbentuk segitiga atas, yakni yang semua koefisien di bawah diagonal utamanya bernilai nol. Bentuk segitiga atas ini dapat diselesaikan dengan menggunakan substitusi (penyulihan) balik. Untuk mendapatkan bentuk SPL segitiga dari SPL yang diketahui, metode eliminasi Gauss menggunakan sejumlah operasi baris elementer (OBE): 1. Menukar posisi dua buah persamaan (dua baris matriks augmented)

Operasi baris elementer pada metode eliminasi Gauss

2. Menambah sebuah persamaan (baris matriks augmented) dengan suatu kelipatan persamaan lain (baris lain) 3. Mengalikan sebuah persamaan (baris matriks augmented) dengan sebarang konstanta taknol. Pemakaian operasi-operasi baris elementer di atas pada sebuah SPL tidak akan mengubah penyelesaikan SPL yang bersangkutan. Jelas bahwa penyelesaian sebuah SPL tidak tergantung pada susunan penulisan persamaan, sehingga operasi baris nomor 1 dapat dipakai. Dalam setiap persamaan, kedua ruas menyatakan nilai yang sama, sehingga operasi baris nomor 2 dapat digunakan. Demikian pula, operasi baris nomor 3 menghasilkan persamaan yang ekivalen. Sekarang kita akan menjelaskan proses eliminasi Gauss ini melalui sebuah contoh. Perhatikan SPL

x x x x1 + 5x2 x3 = 12 6x1 + 3x2 + 7x3 = 102 3 1 + 4 2 + 3 3 = 16

(A) (B) (C)

1. Eliminasi x1 dari persamaan (B) dan (C):

x

x x 11 x2 2x3 = 523 3 5x2 + x3 = 70

3 1 + 4 2 + 3 3 = 16

B) (C ) (

A 2  (A ) 1

3

( )

> =====> =====

Pengantar Komputasi Numerik

(A) (D) (E)

c Sahid (2004 – 2012)

Bab 2. Sistem Persamaan Linier

60 2. Eliminasi x2 dari persamaan (E):

3x1 + 4x2 + 3x3 = 16 11

(E ) +

15 11

(

3 D)

2x 3 =

x2

19

=====>

11

x3

=

(A)

52

(D)

3 510

(F)

11

3. Hitung x3 ; x2 ; x1 : Dari (F) diperoleh x3 = 52 diperoleh 11 3 x2 = 3 sukkan nilai-nilai x3 dan

510 19 . Masukkan nilai x3 ke dalam (D) 368 1020 4048 19 = 57 . Jadi, x2 = 19 . Max2 ke dalam (A) untuk mendapatkan x1 : 1472 1102 1530 3306 3x1 = 16 + 19 + 19 = 19 , x1 = 19 = 58. Jadi, vektor penyele368 saian SPL di atas adalah (58; 19 ; 510 19 ).

Metode Eliminasi Gauss terdiri atas dua tahap: 1. Eliminir secara berturut-turut variabel-variabel dari beberapa persamaan.

x1

,

x2

,

x3

, ...,

xn

1

2. Masukkan kembali nilai-nilai yang sudah didapat ke dalam persamaan-persamaan tersebut untuk mendapatkan nilai-nilai yang belum diketahui di antara xn , xn 1 , xn 2 , . . . , x1 . Secara umum, misalkan kita mempunyai SPL seperti pada (2.1): + a12 x2 + : : : + a1n xn + a22 x2 + : : : + a2n xn

=

b1

a21 x1

=

b2

a31 x1

+ a32 x2 + : : : + a3n xn

=

b3

an1 x1

+ an2 x2 + : : : + ann xn

=

a11 x1

.. .

bn

Berikut adalah langkah-langkah eliminasi Gauss untuk SPL (2.1): Tahap I: Eliminasi 1. Eliminir x1 dari persamaan-persamaan kedua, ketiga, . . . , ke-n. Dengan kata lain, buat koefisien-koefisien x1 pada persamaanpersamaan kedua, ketiga, . . . ke-n kenjadi nol. Hal ini dapat dilakukan dengan mengurangkan suatu kelipatan persamaan pertama dari persamaan-persamaan kedua, ketiga, . . . , ke-n. Proses ini mengubah nilai-nilai koefisien-koefisien xi , aij , dan konstanta Pengantar Komputasi Numerik

c Sahid (2004 – 2012)

Bab 2. Sistem Persamaan Linier

62 (k + 1), mik

Akhir tahap I proses eliminasi Gauss adalah SPL bentuk segitiga atas yang ekivalen dengan SPL semula.

=

k

aik akk

+ 2,

. . . , dan ke–n, dengan cara mengurangkan kelipatan baris ke–k dari baris ke–i, untuk i = k + 1; k + 2; : : : ; n:

aij

=

aij

bi

=

bi

 

mik mik

  dan ( + 1)  

untuk

akj

k

bk

j

k

(2.2)

n;

i

(2.3)

n:

4. Akhirnya, setelah kita berhasil mengeliminir variabel-variabel x1 , x2 , x3 , . . . , xn 1 dengan menggunakan operasi-operasi seperti di atas kita dapatkan SPL a

11 x1

12 x2 22 x2

+

a

0

+

a

0

+

0

+

0

0

13 x3 23 x3 a33 x3

+ : : : + a1n xn

0

+ : : : + ann xn

+

a

+

a

+

+

+ : : : + a 2n x n

+ : : : + a3n xn

1 2 b3

=

b

=

b

=

.. . =

(2.4)

bn

dengan matriks koefisien berupa matriks segitiga atas (elemenelemen di bawah diagonal utama bernilai nol).

Tahap II metode eliminasi Gauss adalah proses substitusi (penyulihan) mundur.

Tahap II: Substitusi Pada tahap ini kita perlu menghitung nilai-nilai xn , xn 1 , xn x1 . Dari SPL (2.4) kita dapat melakukan substitusi mundur sbb.: 1. Dari persamaan terakhir didapat xn

=

bn =ann

xi

Elemen pivot, baris pivot, penentuan pivot parsial

.

2. Dengan memasukkan nilai xn ke dalam persamaan ke-(n oleh xn 1 = (bn 1 an 1;n xn )=an 1;n 1 . 3. Secara umum, setelah diperoleh nilai-nilai diperoleh xi dengan rumus =

1 aii

X

2, . . . ,

xn ; xn

1;

1) diper-

: : : ; xi

+1 akan

n

(bi j

= +1

aij xj ):

(2.5)

i

Persamaan (2.5) dapat digunakan untuk menghitung nilai-nilai xn 1 ; xn 2 ; : : : ; x1 setelah xn diketahui.

Permasalahan yang mungkin muncul Perhatikan persamaan-persamaan (2.2), (2.3), (2.5). Dari rumus-rumus tersebut, tampak bahwa metode eliminasi Gauss akan gagal apabila nilaiPengantar Komputasi Numerik

c Sahid (2004 – 2012)

2.2 Eliminasi Gauss

63

nilai akk sama dengan nol, sebab nilai-nilai tersebut digunakan sebagai pembagi pada pengali mik maupun di dalam proses substitusi mundur (2.5). Nilai akk 6= 0 pada baris ke-k di mana akj = 0 untuk j < k , disebut elemen pivot pada langkah ke-k . Baris yang memuat elemen pivot disebut baris pivot. Eliminasi juga dapat menyebabkan hasil yang jelek apabila pada beberapa langkah digunakan pengali mik yang nilainya lebih besar daripada 1. Hal ini dikarenakan pada langkah ke–k , galat pembulatan pada koefisien-koefisien ak;k+1 , ak;k+2 , . . . , dan akn , serta bk diperbesar oleh faktor mik . Apabila nilai-nilai mik pada langkah-langkah berurutan hampir sama besar, maka galat pembulatanya akan terakumulasi secara cepat, menyebabkan metode yang tidak stabil. Angka-angka signifikan mungkin juga akan hilang pada proses penyulihan mundur apabila terdapat elemen-elemen pivot yang bernilai sangat kecil. Salah satu metode untuk mengatasi masalah-masalah ini disebut metode penentuan pivot parsial, yang akan dijelaskan setelah kita bahas contoh berikut ini. C ONTOH 2.5. Selesaikan SPL di bawah ini dengan menggunakan metode eliminasi Gauss.

x1 x2 +2x3 x4 2x1 2x2 +3x3 3x4 x1+ x2 + x3 x1 x2 +4x3+3x4

= = = =

8 20 2 4

Penyelesaian: Matriks augmented-nya adalah

01 1 2 1 8 1 BB 2 2 3 3 20 C 1 1 1 0 2 C A

1.

1 1 4 3 4 Pilih elemen pivot a11 = 1. Misalkan P menyatakan baris ke-j matriks augmented. Maka dengan melakukan operasi-operasi P2 = P2 2P1 , P3 = P3 P1 , dan P4 = P4 P1 , didapat matriks baru j

01 1 2 1 81 BB 0 0 1 1 4 C A 0 2 1 1 6 C 0 0

Pengantar Komputasi Numerik

2

4 12

c Sahid (2004 – 2012)

2.2 Eliminasi Gauss

65

tidak mempunyai penyelesaian atau mempunyai tak berhingga banyak penyelesaian. Selanjutnya, apabila semua elemen tersebut sangat kecil, maka elemen pivot yang terpilih juga sangat kecil. Akibatnya, dari persamaan (2.5) terlihat bahwa nilai-nilai xi sangat sensitif terhadap perubahan kecil pada koefisien. Hal ini menunjukkan bahwa SPL yang bersangkutan dalam kondisi sakit. Suatu strategi penentuan pivot yang sering digunakan di dalam metode Eliminasi Gauss dikenal sebagai penentuan pivot parsial. Di dalam metode ini, suatu elemen pivot akk merupakan elemen maksimum pada kolom k di bawah baris ke-k , untuk k = 1; 2; 3; : : : ; (n 1), yakni elemen pivot = maxfjakk j; untuk

j

ak

k

+1

;k

j j ;

ak

= 1; 2; 3;

+2

;k

:::;

j

; :::;

(n

j jg ank

Strategi penentuan pivot parsial

(2.6)

1)

Kata parsial digunakan untuk membedakan prosedur ini dengan metode penentuan pivot total, yang menggunakan pertukaran baris dan kolom. Penentuan pivot total menghasilkan reduksi tambahan yang mempengaruhi galat-galat pembulatan dan hal ini sangat penting demi keakuratan penyelesaian sistem-sistem tertentu. Kita tidak akan membahas strategi penentuan pivot total di sini. Apabila elemen pivot pada langkah ke-k bernilai nol, maka terdapat tiga kemungkinan: 1. SPL mempunyai solusi tunggal. Dalam hal ini baris pivot ditukar dengan salah satu baris di bawahnya sedemikian hingga diperoleh elemen pivot yang tak nol. 2. SPL yang bersangkutan tidak bebas. Apabila elemen pivot nol tidak dapat dihindari dan SPL-nya bersifat konsisten, maka SPL tersebut mempunyai tak berhingga penyelesaian. Sebagai contoh, SPL di bawah ini bersifat tidak bebas. 2x+

y+ z

=

2

3z

=

1

x+2y +4z

=

1

x

y

Contoh SPL yang tak bebas

Perhatikan, persamaan pertama merupakan jumlah persamaan kedua dan ketiga, sehingga SPL tersebut tidak bebas. SPL tersebut dikatakan bergantung secara linier, karena salah satu persamaan merupakan kombinasi linier kedua persamaan yang lain. Pengantar Komputasi Numerik

c Sahid (2004 – 2012)

2.2 Eliminasi Gauss

67

langkah kedua, menghasilkan 2 x+

y+

3 2y

z

7 2z 0z

=

2

=

0

=

0:

Dari persamaan ketiga diperoleh bahwa z dapat bernilai berapa saja. Penyelesalain SPL di atas dapat ditulis sebagai (x; y; z ) = 7 2 (1 + 3 ; 3 ; ), untuk sebarang nilai . Jadi SPL tersebut konsisten namun tidak bebas, mempunyai tak berhingga penyelesaian. 3. SPL yang bersangkutan tidak konsisten. Dengan mengganti ruas kanan persamaan pertama SPL di atas akan diperoleh SPL lain yang bersifat tidak konsisten. Misalnya, jika ruas kanan persamaan pertama diganti menjadi 1, diperoleh SPL 2x+

y+ z

=

1

3z

=

1

x+2y +4z

=

1:

x

y

Contoh SPL yang tidak konsisten

Setelah langkah eliminasi kedua diperoleh 2 x+

y+

3 2y

z

7 2z 0z

= = =

2 1 2 1:

Di sini jelas tidak ada nilai z yang memenuhi persamaan ketiga, sehingga SPL tersebut bersifat tidak konsisten. (Jumlah persamaan kedua dan ketiga pada SPL semula adalah 2x + y + z = 2, yang bertentangan dengan persamaan pertama.) Suatu SPL yang bersifat bahwa tidak ada satu persamaanpun yang dapat dinyatakan sebagai kombinasi linier persamaan-persamaan yang lain disebut bebas linier. Dari teorema dasar dalam aljabar linier diketahui bahwa setiap SPL bebas linier yang terdiri atas n persamaan dalam n variabel mempunyai penyelesaian tunggal. Akan tetapi di dalam komputasi numerik, karena digunakan pendekatan hampiran dengan menggunakan pehitungan-perhitungan aritmetika oleh komputer, pernyataan tersebut diartikaan secara kurang persis. Khususnya, jika pada suatu langkah eliminasi Gauss diperoleh elemen pivot yang tidak tepat bernilai nol, namun sangat kecil (mendekati nol) dibandingkan dengan koefisienPengantar Komputasi Numerik

Secara teoritis, SPL yang bebas linier mempunyai solusi tunggal, namun secara numerik dapat diperoleh solusi hampiran yang tidak valid, jika terdapat elemen pivot yang nilainya mendekati nol.

c Sahid (2004 – 2012)

Bab 2. Sistem Persamaan Linier

68

koefisien lain dalam baris pivot, pembagian oleh elemen pivot tersebut mengakibatkan penyelesaian numerik yang memuat galat pembulatan yang mungkin cukup berarti, sehingga penyelesaian yang diperoleh tidak valid. Algoritma eliminasi Gauss (2.1) dapat secara mudah dimodifikasi untuk menerapkan strategi pencarian pivot parsial. Dalam hal ini kita ganti langkah 1(a) dengan mencari p di antara i; i + 1; i + 2; : : : ; n sedemikian hingga

f

j j = maxfj j j api

aii ;

ai

+1

;i

jj ;

ai

+2

;i

g

j

; :::;

j jg an;i

:

Strategi penentuan pivot parsial bertujuan untuk menghindari pemakaian elemen pivot yang bernilai hampir nol. Akan tetapi alasan lain yang sama penting adalah, dalam kebanyakan kasus penentuan pivot parsial menurunkan efek perambatan galat akibat pembulatan. Dengan stratedi penentuan pivot parsial, pengali-pengali mik pada (2.2) dan (2.3) memenuhi

j j1 mik

1

;

k < i



n:

Hal ini akan mengurangi timbulnya kasus galat akibat kehilangan angka signifikan, karena perkalian dengan mik tidak akan menghasilkan bilangan yang lebih besar. Apabila algoritma tersebut gagal dalam menggunakan suatu strategi pene...