Syarif Abdullah (G ) Matematika Terapan FMIPA Institut Pertanian Bogor

Syarif Abdullah (G551150381) Matematika Terapan FMIPA Institut Pertanian Bogor e-mail: [email protected] 25 Maret 2016 Ringkasan Kuliah ke-6 Analisis Numerik (16 Maret 2016) Materi : System Persamaan Linear Sistem Persamaan Linear Persamaan linear: 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 = 𝑘 Sistem persamaan linear (SPL): 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 = 𝑏1 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 = 𝑏2 ⋮ 𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 = 𝑏𝑚 SPL dapat ditulis dalam bentuk matriks: 𝐴x = b 𝑎11 𝑎21 [ ⋮ ⏟𝑎𝑚1

𝑎12 𝑎22 ⋮ 𝑎𝑚2

⋯ ⋯ ⋱ ⋯

𝐴



𝑎1𝑛 𝑥1 𝑏1 𝑎2𝑛 𝑥2 𝑏2 ⋮ ][ ⋮ ] = [ ⋮ ] 𝑥𝑛 𝑎𝑚𝑛 ⏟ 𝑏𝑛 ⏟ x

b

Kekonsistenan Sistem Persamaan Linear

 Pangkat(A) = pangkat(A|b) = n  SPL mempunyai solusi tunggal.  Pangkat(A) ≠ pangkat(A|b)  SPL tidak mempunyai solusi.

 Bila suatu SPL mempunyai solusi tunggal, maka terdapat banyak cara untuk mencari penyelesaian SPL tersebut, di antaranya adalah : x = A-1b.  Metode langsung yang dapat digunakan untuk mencari penyelesaian SPL antara lain: Metode substitusi langkah mundur & substitusi langkah maju, metode eliminasi Gauss, dan sebagainya.



Bentuk Matriks Segitiga Atas dan Substitusi Langkah Mundur 𝑎11 𝑥1 + 𝑎12 𝑥2 + 𝑎13 𝑥3 + ⋯ +

𝑎1,𝑛−1 𝑥𝑛−1 +

𝑎1𝑛 𝑥𝑛 = 𝑏1

𝑎22 𝑥2 + 𝑎23 𝑥3 + ⋯ +

𝑎2,𝑛−1 𝑥𝑛−1 +

𝑎2𝑛 𝑥𝑛 = 𝑏2

𝑎33 𝑥3 + ⋯ +

𝑎3,𝑛−1 𝑥𝑛−1 +

𝑎3𝑛 𝑥𝑛 = 𝑏3

⋮

⋮

⋮

𝑎𝑛−1,𝑛−1 𝑥𝑛−1 + 𝑎𝑛−1,𝑛 𝑥𝑛 = 𝑏𝑛−1 𝑎𝑛𝑛 𝑥𝑛 = 𝑏𝑛 𝑎11 0 0 ⋮ 0 [ 0

𝑎12 𝑎22 0 ⋮ 0 0

𝑎13 𝑎23 𝑎33 ⋮ 0 0

⋯ ⋯ ⋯ ⋱ ⋯ ⋯

𝑎1,𝑛−1 𝑎2,𝑛−1 𝑎3,𝑛−1 ⋮ 𝑎𝑛−1,𝑛−1 0

𝑎1𝑛 𝑥 𝑏1 1 𝑎2𝑛 𝑥 𝑏2 2 𝑎3𝑛 𝑥3 𝑏3 = ⋮ ⋮ ⋮ 𝑏𝑛−1 𝑎𝑛𝑛 𝑥𝑛−1 𝑎𝑛𝑛 ] [ 𝑥𝑛 ] [ 𝑏𝑛 ]

•

Andaikan Ax = b adalah sistem persamaan linear segitiga atas. Jika aii ≠ 0 , untuk setiap i

•

= 1, 2, …, n, maka terdapat suatu penyelesaian tunggal bagi SPL tersebut. Untuk menyelesaikan Ax = b dengan metode substitusi langkah mundur, maka semua unsur pada diagonal utama haruslah tak nol.

Mula-mula hitung: 𝑥𝑛 =

𝑏𝑛 𝑎𝑛𝑛

Kemudian gunakan aturan: 𝑥𝑖 =

𝑏𝑖 − ∑𝑛𝑗=𝑖+1 𝑎𝑖𝑗 𝑥𝑗 untuk 𝑖 = 𝑛 − 1, 𝑛 − 2, … ,1. 𝑎𝑖𝑖



Bentuk Matriks Segitiga Bawah dan Substitusi Langkah Maju

𝑎11 𝑥1

= 𝑏1

𝑎21 𝑥1 +

𝑎22 𝑥2

𝑎31 𝑥1 +

𝑎32 𝑥2 +

= 𝑏2 𝑎33 𝑥3

⋮

= 𝑏3

⋮

⋮

𝑎𝑛−1,1 𝑥1 + 𝑎𝑛−1,2 𝑥2 + 𝑎𝑛−1,3 𝑥3 + ⋯ + 𝑎𝑛−1,𝑛−1 𝑥𝑛−1 = 𝑏𝑛−1 𝑎𝑛1 𝑥1 +

• •

𝑎𝑛2 𝑥2 +

𝑎𝑛3 𝑥3 + ⋯ +

𝑎11 𝑎21 𝑎31 ⋮

0 𝑎22 𝑎32 ⋮

0 0 𝑎33 ⋮

𝑎𝑛−1,1 [ 𝑎𝑛1

𝑎𝑛−1,2 𝑎𝑛2

𝑎𝑛−1,3 𝑎𝑛3

𝑎𝑛𝑛 𝑥𝑛 = 𝑏𝑛 ⋯ 0 ⋯ 0 ⋯ 0 ⋱ ⋮ ⋯ 𝑎𝑛−1,𝑛−1 ⋯ 𝑎𝑛−1,𝑛

0 𝑏1 𝑥1 0 𝑏2 𝑥2 0 𝑥3 𝑏3 = ⋮ ⋮ ⋮ 𝑏𝑛−1 0 𝑥𝑛−1 𝑎𝑛𝑛 ] [ 𝑥𝑛 ] [ 𝑏𝑛 ]

Andaikan Ax = b adalah sistem persamaan linear segitiga bawah. Jika aii ≠ 0 untuk setiap i = 1, 2, …, n, maka terdapat suatu penyelesaian tunggal bagi SPL tersebut. Untuk menyelesaikan Ax = b menggunakan metode substitusi langkah maju, maka semua unsur pada diagonal utama haruslah tak nol.

Mula-mula hitung: 𝑥1 =

𝑏1 𝑎11

Kemudian gunakan aturan: 𝑏𝑖 − ∑𝑖−1 𝑗=1 𝑎𝑖𝑗 𝑥𝑗 𝑥𝑖 = untuk 𝑖 = 2,3, … , 𝑛. 𝑎𝑖𝑖

2. Eliminasi Gauss Naïve  

Operasi OBE pada Matriks Segitiga Atas Langkah Substitusi Mundur

Metode eliminasi Gauss naif merupakan metode yang dikembangkan dari metode eliminasi. Langkah penyelesaian: 1. Tulis SPL dalam bentuk matriks diperbesar 2. Ubah matriks tersebut menjadi matriks segitiga atas atau segitiga bawah dengan operasi baris elementer (OBE) Contoh soal: Diketahui SPL dengan 4 persamaan dan 4 variabel sebagai berikut: 6𝑥1 − 2𝑥2 + 2𝑥3 + 4𝑥4 = 16 12𝑥1 − 8𝑥2 + 6𝑥3 + 10𝑥4 = 26 3𝑥1 − 13𝑥2 + 9𝑥3 + 3𝑥4 = −19 −6𝑥1 + 4𝑥2 + 𝑥3 − 18𝑥4 = −34 Tentukan penyelesaian SPL tersebut dengan eliminasi Gauss!

Dengan substitusi mundur, diperoleh: 𝑥1 = 3, 𝑥2 = 1, 𝑥3 = −2, 𝑥4 = 1

VEKTOR ERROR DAN VEKTOR RESIDU Misalkan diberikan SPL sebagai berikut: 𝐴𝑥 = 𝑏 Vektor error dari SPL tersebut adalah e  x - x dengan

𝑥̃: nilai hampiran 𝑥: nilai eksak

Vektor residu dari SPL tersebut adalah

r  Ax  b

Secara verbal, vektor residu adalah sisa yang dihasilkan oleh suatu nilai hampiran x jika dimasukkan kembali ke SPL awal.

r  Ax  b r  Ax  Ax r  A( x  x) r  Ae 3. Eliminasi Gauss dengan Pivoting 

Partial Pivoting

Langkah penyelesaian SPL dengan pivot parsial: 1) 2) 3) 4) 5)

Tentukan r sehingga Tukarkan baris i dengan baris r, jika i = r maka tidak ditukar Buat nol elemen di bawah aii, i = 1, 2, …, n-1. Kembali ke langkah 1 hingga membentuk matriks segitiga atas Lakukan substitusi mundur untuk memperoleh solusi

Contoh SPL (1) dari ilustrasi:

𝜀 𝑥 + 𝑥2 = 1 { 1 𝑥1 + 𝑥2 = 2

Dengan menggunakan pivot parsial akan diperoleh:

𝑥 + 𝑥2 = 2 { 1 𝜀 𝑥1 + 𝑥2 = 1 dan diperoleh solusi: 𝑥2 = 

1 − 2𝜀 ≈ 1, 1−𝜀

Scaled Partial Pivoting

Langkah penyelesaian SPL dengan pivot parsial terskala: 1) Definisikan vektor indeks ℓ = [ℓ1 , ℓ2 , … , ℓ𝑛 ] = [1,2, … , 𝑛] Definisikan vektor skala

𝑠 = [𝑠1 , 𝑠2 , … , 𝑠𝑛 ] dengan 𝑠𝑖 = max |𝑎𝑖𝑗 | , 1 ≤ 𝑖 ≤ 𝑛 1≤j≤n

2) Tentukan rasio masing-masing baris

{

|𝑎𝑙𝑖 ,1 | ; 1 ≤ 𝑖 ≤ 𝑛} 𝑠𝑙𝑖

3) Pilih j, yaitu indeks dengan rasio maksimum. Baris j adalah pivot untuk iterasi k (k = 1, 2, …, n-1). Jika banyaknya rasio maksimum lebih dari satu, maka pilih indeks terkecil. 4) Tukarkan lk dengan lk pada vektor indeks. 5) Tukarkan baris pada matriks sesuai dengan vektor indeks. 6) Buat nol elemen di bawah akk. 7) Kembali ke langkah 3. Vektor indeks yang digunakan adalah yang terbentuk pada langkah 5.

Contoh: Tentukan solusi dari SPL berikut menggunakan eliminasi Gauss dengan pivot parsial terskala! −1 2 2 𝑥1 −5 [ 1 −1 −1] [𝑥2 ] = [ 2 ] −1 4 2 𝑥3 1 1) Definisikan vektor indeks dan vektor skala ℓ = [1,2,3] = [ℓ1 , ℓ2 , ℓ3 ] 𝑠 = [2,1,4] = [𝑠1 , 𝑠2 , 𝑠3 ] 2) Untuk iterasi pertama (k = 1), tentukan j, yaitu indeks dengan rasio maksimum. Jika banyaknya rasio maksimum lebih dari satu, maka dipilih indeks terkecil. |𝑎ℓ ,1 | 1 2 1 { 𝑖 ; 𝑖 = 1,2,3} = { , , } = {0.5,1,0.25} 𝑠ℓ𝑖 2 2 4 3) Diperoleh vektor indeks baru:

 [2,1,3] 4) Tukarkan baris pada matriks sesuai dengan vektor indeks. Diperoleh: 1 −1 −1 𝑥1 2 𝑥 [−1 2 ] [ ] = [ 2 2 −5] 𝑥 −1 4 2 3 1 5) Buat nol elemen-elemen di bawah a11. Diperoleh: 1 −1 −1 𝑥1 2 [0 1 1 ] [𝑥2 ] = [−3] 0 3 1 𝑥3 3 6) Untuk iterasi kedua (k=2), vektor indeks dan vektor skala yang digunakan adalah: ℓ = [2,1,3] = [ℓ1 , ℓ2 , ℓ3 ] 𝑠 = [2,1,4] = [𝑠1 , 𝑠2 , 𝑠3 ] 7) Tentukan rasio baru dengan menggunakan vektor indeks dan vektor skala pada 6. {

|𝑎ℓ𝑖 ,2 | 1 3 ; 𝑖 = 2,3} = { , } = {0.5 , 0.75} 𝑠ℓ𝑖 2 4

Baris ketiga menjadi pivot untuk k=2. 8) Diperoleh vektor indeks

 [2,3,1]

9) Tukarkan baris pada matriks sesuai dengan vektor indeks (tukarkan baris kedua dan ketiga), diperoleh: 1 −1 −1 𝑥1 2 [0 3 1 ] [𝑥2 ] = [ 3 ] 0 1 1 𝑥3 −3 10) Buat nol elemen di bawah a22, diperoleh:

1 [0 0

−1 −1 𝑥1 2 3 1 ] [𝑥2 ] = [ 3 ] 2 𝑥3 0 −4 3

11) Dengan substitusi mundur, diperoleh: x1  1, x2  3, x3  6

4. Sistem Tridiagonal dan Sistem Banded Kestabilan Numerik Eliminasi Gauss dikatakan stabil secara numerik jika matriks koefisien A dari SPL yang diberikan adalah dominan secara diagonal (strictly diagonally dominant), atau merupakan matriks simetris definit positif. 

Sistem Tridiagonal

Sebuah matriks berukuran n x n disebut mempunyai struktur banded jika terdapat bilangan bulat k (k ≤ n) sehingga aij = 0 ketika | i – j | ≥ k. Suatu sistem yang direpresentasikan dengan matriks yang memenuhi: 1. Terdapat 3 diagonal, yaitu diagonal utama, superdiagonal, dan subdiagonal. 2. Elemen-elemen aij ≠ 0 jika |i–j|≤ 1 dan aij=0 jika |i–j|≥ 2.

 d1 a  1         

c1 d2 a2

c2 d3 ...

c3 ... ... ai di ...

ci ... an  2

... d n 1 an 1

  x1   b1   x   b   2   2    x3   b3        ...    ...    xi   bi        ...   ...  cn 1   xn 1  bn 1      d n   xn   bn 

Langkah penyelesaian sistem tridiagonal dengan metode eliminasi Gauss: 

Buat nol elemen-elemen a1, a2, …, an-1, dengan



Nilai di dan bi akan berubah menjadi:

i = 1,2,…,n-1

Dengan metode substitusi mundur, diperoleh solusi untuk x1, x2, …, xn.

Matriks A = (aij)nxn adalah strictly diagonally dominant, jika:

Dalam kasus tridiagonal sistem, dengan asumsi: a0 = an = 0



Sistem Pentadiagonal

Suatu sistem yang direpresentasikan dengan matriks yang memenuhi: 1.Terdapat 5 diagonal, yaitu diagonal utama, 2 super-diagonal, dan 2 subdiagonal. 2.Elemen-elemen aij ≠ 0 jika |i–j|≥ 2 dan aij = 0 jika|i–j|≥ 3, untuk setiap i, j.

Langkah penyelesaian sistem pentadiagonal dengan metode eliminasi Gauss: ①Buat a1=0, dengan cara:

②Nilai d2, c2, dan b2 akan berubah menjadi:

③Buat e1=0, dengan cara:

④Elemen-elemen a2, d3, dan b3 akan berubah menjadi:

⑤Buat nol elemen ai, dengan:

⑥Elemen-elemen di+1, ci+1, dan bi+1 akan berubah menjadi:

⑦Buat nol elemen ei, dengan:

⑧Elemen-elemen ai+1, di+2, dan bi+2 juga akan berubah menjadi:

Solusi yang diperoleh dengan metode eliminasi Gauss:

Dengan substitusi mundur, diperoleh solusi untuk x1, x2, …, xn:



Block Pentadiagonal

Di mana:

Contoh: Tentukan solusi dari SPL berikut:

Jawab:

Dengan substitusi mundur, diperoleh:

KESIMPULAN 

SPL adalah kumpulan dari m persamaan linear dengan n variabel, yang secara umum dapat dituliskan ke dalam bentuk:



Metode untuk menyelesaikan SPL:

1. Metode eliminasi Gauss (tanpa pivot) 2. Metode eliminasi Gauss dengan pivot 

Sistem tridiagonal dan pentadiagonal dapat diselesaikan dengan metode eliminasi Gauss (tanpa pivot).

Sumber : 1. Cheney, Ward and David Kingaid, Numerical Mathematics and Computing, Sixth Edition, The Thomson Corporation, 2008. 2. Munir, Rinaldi, Metode Numerik, Revisi Ketiga, Informatika, Bandung, 2013.