Solusi Sistem Persamaan Linear Ax = b Kie Van Ivanky Saputra
April 27, 2009
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
April 27, 2009
1/9
Review
1
Substitusi mundur pada sistem persamaan linear segitiga atas,
2
Eliminasi Gauss biasa,
3
Eliminasi Gauss dengan tumpuan berskala.
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
April 27, 2009
2/9
Faktorisasi LU
Apa itu faktorisasi?
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
April 27, 2009
3/9
Faktorisasi LU
Apa itu faktorisasi? Faktorisasi pada bilangan real : 8 = 2 × 4.
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
April 27, 2009
3/9
Faktorisasi LU
Apa itu faktorisasi? Faktorisasi pada bilangan real : 8 = 2 × 4. Faktorisasi pada matriks n × n : A = LU.
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
April 27, 2009
3/9
Faktorisasi LU
Apa itu faktorisasi? Faktorisasi pada bilangan real : 8 = 2 × 4. Faktorisasi pada matriks n × n : A = LU. L adalah matriks segitiga bawah dan U adalah matriks segitiga 1 0 ··· 0 u11 u12 · · · l21 1 · · · 0 0 u22 · · · L= . .. .. , U = .. .. .. .. .. . . . . . . ln1 ln2 · · · 1 0 0 ···
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
atas. u1n u2n .. . unn
April 27, 2009
3/9
Faktorisasi LU
Apa itu faktorisasi? Faktorisasi pada bilangan real : 8 = 2 × 4. Faktorisasi pada matriks n × n : A = LU. L adalah matriks segitiga bawah dan U adalah matriks segitiga 1 0 ··· 0 u11 u12 · · · l21 1 · · · 0 0 u22 · · · L= . .. .. , U = .. .. .. .. .. . . . . . . ln1 ln2 · · · 1 0 0 ···
atas. u1n u2n .. . unn
Tidak semua matrix bisa difaktorisasi.
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
April 27, 2009
3/9
Solusi dari system persamaan Ax = b Algoritma mencari solusi Ax = b, menggunakan faktorisasi LU:
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
April 27, 2009
4/9
Solusi dari system persamaan Ax = b Algoritma mencari solusi Ax = b, menggunakan faktorisasi LU: 1 Cari L dan U sehingga A = LU, sehingga SPL yang akan diselesaikan menjadi LUx = b.
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
April 27, 2009
4/9
Solusi dari system persamaan Ax = b Algoritma mencari solusi Ax = b, menggunakan faktorisasi LU: 1 Cari L dan U sehingga A = LU, sehingga SPL yang akan diselesaikan menjadi LUx = b. 2 Cari y dimana y adalah solusi dari Ly = b, 1 0 ··· 0 y1 b1 l21 1 · · · 0 y2 b2 .. .. .. .. = .. . . . . . . . . ln1
K V I Saputra (Analisis Numerik)
ln2
···
1
yn
c Kuliah Sistem Persamaan Linier
bn
April 27, 2009
4/9
Solusi dari system persamaan Ax = b Algoritma mencari solusi Ax = b, menggunakan faktorisasi LU: 1 Cari L dan U sehingga A = LU, sehingga SPL yang akan diselesaikan menjadi LUx = b. 2 Cari y dimana y adalah solusi dari Ly = b, 1 0 ··· 0 y1 b1 l21 1 · · · 0 y2 b2 .. .. .. .. = .. . . . . . . . . ln1 3
ln2
···
Kemudian cari x dimana x adalah u11 u12 · · · 0 u22 · · · .. .. .. . . . 0 K V I Saputra (Analisis Numerik)
0
···
1
yn
bn
solusi dari Ux = y . x1 u1n u2n x2 .. .. = . .
y1 y2 .. .
unn
yn
xn
c Kuliah Sistem Persamaan Linier
April 27, 2009
4/9
Contoh
Contoh Selesaikan sistem persamaan linear berikut ini dengan menggunakan faktorisasi LU.
K V I Saputra (Analisis Numerik)
4x1 + 3x2 − x3
=
−2
−2x1 − 4x2 + 5x3
=
20
x1 + 2x2 + 6x3
=
7
c Kuliah Sistem Persamaan Linier
April 27, 2009
5/9
Contoh
Contoh Selesaikan sistem persamaan linear berikut ini dengan menggunakan faktorisasi LU. 4x1 + 3x2 − x3
=
−2
−2x1 − 4x2 + 5x3
=
20
x1 + 2x2 + 6x3
=
7
Diketahui bahwa matriks A dari SPL diatas dapat difaktorisasi menjadi: 4 3 −1 1 0 0 4 3 −1 −2 −4 5 = −0.5 1 0 0 −2.5 4.5 1 2 6 0.25 −0.5 1 0 0 8.5
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
April 27, 2009
5/9
Contoh(2) Maka, dengan substitusi maju, kita 1 0 −0.5 1 0.25 −0.5
K V I Saputra (Analisis Numerik)
dapat mencari y 0 y1 −2 0 y2 = 20 1 y3 7
c Kuliah Sistem Persamaan Linier
April 27, 2009
6/9
Contoh(2) Maka, dengan substitusi maju, kita 1 0 −0.5 1 0.25 −0.5
dapat mencari y 0 y1 −2 0 y2 = 20 1 y3 7
y1 = −2, y2 = 20 − (−0.5)(−2) = 19, y3 = 7 − (0.25)(−2) − (−0.5)(19) = 17
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
April 27, 2009
6/9
Contoh(2) Maka, dengan substitusi maju, kita 1 0 −0.5 1 0.25 −0.5
dapat mencari y 0 y1 −2 0 y2 = 20 1 y3 7
y1 = −2, y2 = 20 − (−0.5)(−2) = 19, y3 = 7 − (0.25)(−2) − (−0.5)(19) = 17 Langkah berikutnya yaitu mencari x, 4 3 −1 x1 −2 0 −2.5 4.5 x2 = 19 0 0 8.5 x3 17
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
April 27, 2009
6/9
Contoh(2) Maka, dengan substitusi maju, kita 1 0 −0.5 1 0.25 −0.5
dapat mencari y 0 y1 −2 0 y2 = 20 1 y3 7
y1 = −2, y2 = 20 − (−0.5)(−2) = 19, y3 = 7 − (0.25)(−2) − (−0.5)(19) = 17 Langkah berikutnya yaitu mencari x, 4 3 −1 x1 −2 0 −2.5 4.5 x2 = 19 0 0 8.5 x3 17 Dengan substitusi mundur, kita dapat mencari x, x3 = 17/8.5 = 2, x2 =
K V I Saputra (Analisis Numerik)
19 − 4.5(2) −2 + (2) − 3(−4) = −4, x1 = = 3. −2.5 4 c Kuliah Sistem Persamaan Linier
April 27, 2009
6/9
Mencari faktorisasi A = LU
4 A = −2 1
3 −4 2
K V I Saputra (Analisis Numerik)
−1 5 6
c Kuliah Sistem Persamaan Linier
April 27, 2009
7/9
Mencari faktorisasi A = LU
4 A = −2 1
3 −4 2
K V I Saputra (Analisis Numerik)
−1 1 5 = 0 6 0
0 1 0
0 4 0 −2 1 1
c Kuliah Sistem Persamaan Linier
3 −4 2
−1 5 6
April 27, 2009
7/9
Mencari faktorisasi A = LU
4 3 −1 1 0 0 4 A = −2 −4 5 = 0 1 0 −2 1 2 6 0 0 1 1 1 0 0 4 3 −1 A = −0.5 1 0 0 −2.5 4.5 0.25 0 1 0 1.25 6.25
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
3 −4 2
−1 5 6
April 27, 2009
7/9
Mencari faktorisasi A = LU
4 3 −1 1 0 0 4 A = −2 −4 5 = 0 1 0 −2 1 2 6 0 0 1 1 1 0 0 4 3 −1 A = −0.5 1 0 0 −2.5 4.5 0.25 0 1 0 1.25 6.25 1 0 0 4 3 −1 1 0 0 −2.5 4.5 A = −0.5 0.25 −0.5 1 0 0 8.5
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
3 −4 2
−1 5 6
April 27, 2009
7/9
FYI: For your information
Proses mengubah matriks A menjadi matriks segitiga atas dan proses mencari faktorisasi matriks A = LU adalah proses yang sama, yaitu eliminasi Gauss atau operasi baris elementer (OBE).
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
April 27, 2009
8/9
FYI: For your information
Proses mengubah matriks A menjadi matriks segitiga atas dan proses mencari faktorisasi matriks A = LU adalah proses yang sama, yaitu eliminasi Gauss atau operasi baris elementer (OBE). Metoda faktorisasi berguna jika ada lebih dari satu SPL yang harus diselesaikan dimana matriks A tetap dan vektor b yang berubah-ubah, sehingga OBE/ eliminasi Gauss tidak perlu dilakukan terus.
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
April 27, 2009
8/9
FYI: For your information
Proses mengubah matriks A menjadi matriks segitiga atas dan proses mencari faktorisasi matriks A = LU adalah proses yang sama, yaitu eliminasi Gauss atau operasi baris elementer (OBE). Metoda faktorisasi berguna jika ada lebih dari satu SPL yang harus diselesaikan dimana matriks A tetap dan vektor b yang berubah-ubah, sehingga OBE/ eliminasi Gauss tidak perlu dilakukan terus. Tetapi, jika hanya ada satu SPL yang harus diselesaikan, kedua metoda tersebut adalah sama, kecuali dimana faktorisasi LU akan terus menyimpan data-data eliminasi Gauss.
K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
April 27, 2009
8/9
Tugas, dikumpulkan saat UAS 1
Carilah faktorisasi LU dari matriks-matriks berikut ini: 4 2 −1 −5 2 −1 (a) 2 5 −2 (b) 1 0 3 1 −2 7 3 1 6
2
Carilah faktorisasi LU dari matriks A dibawah ini, dan gunakan faktorisasi tersebut untuk menyelesaikan SPL Ax = b jika diketahui (a) b = (8, −4, 10, −4) dan (b) b = (28, 13, 23, 4). 4 8 4 0 1 5 4 −3 A= 1 4 7 2 1 3 0 −2
3
Tidak semua matriks dapat berhasil untuk difaktorisasi. Salah satu metoda agar suatu matriks dapat difaktorisasi adalah dengan mengalikan suatu matriks permutasi. Buatlah algoritma seperti yang telah diberikan di kuliah ini dengan melibatkan matriks permutasi. K V I Saputra (Analisis Numerik)
c Kuliah Sistem Persamaan Linier
April 27, 2009
9/9
