Metode Numerik
Catatan Kuliah
BAB 4 Sistem Persamaan Linear 1. Tinjauan Ulang Matrik 2. Sistem Linear Segitiga Atas 3. Eliminasi Gauss dan Pivoting 4. Invers Matriks 5. Dekomposisi Segitiga 6. Metode Iterasi Jacobi dan Gauss-Seidel 7. Sistem Linear Tridiagonal 1
Metode Numerik
Catatan Kuliah
1. Tinjauan Ulang Matrik Matrik adalah deretan bilangan berbentuk siku empat yang disusun secara bersistem dalam baris-baris dan kolom-kolom. Matrik yang mempunyai M baris dan N kolom disebut matrik M x N. Huruf kapital A menyatakan suatu matrik dan huruf kecil berindeks aij menyatakan satu dari bilangan-bilangan yang membentuk matrik, ditulis
A = (aij ) M x N untuk 1 ≤ i ≤ M dan 1 ≤ j ≤ N dengan aij adalah bilangan yang ada dilokasi (i, j), yaitu elemen yang berada pada baris ke-i dan kolom ke-j dalam deretan tersebut. Dalam bentuk rinci ditulis, a11 a12 ... a1 j ... a1N a a ... a ... a 21 22 2j 2N ... ... ... ... ... ... A= ai1 ai 2 ... aij ... aiN Baris ke-i ... ... ... ... ... ... a M 1 aM 2 ... aMj ... aMN Kolom ke-j 2
Catatan Kuliah
Beberapa matriks khusus: Matriks Bujur sangkar Matriks bujur sangkar adalah matriks yang banyaknya baris sama dengan banyaknya kolom. A berukuran N x N.
Metode Numerik
a11 Matriks Diagonal 0 D = ... Matriks diagonal adalah matrik bujursangkar dengan semua elemen bukan diagonal bernilai nol. 0
0 a 22 ... 0
1 Matriks satuan adalah matrik diagonal yang semua I = 0 ... elemennya bernilai satu. 0
0 1 ... 0
Matriks Satuan
Matriks Segitiga atas
a11 Matrik segitiga atas adalah matriks bujur sangkar 0 dengan semua elemen di bawah diagonal bernilai U = ... nol. aij = 0 untuk i > j. 0
a12 a 22 ... 0
... 0 ... 0 ... ... ... a NN
0 0 ... 1
... a1 N ... a 2 N ... ... ... a NN
... ... ... ...
3
Metode Numerik
Catatan Kuliah
Matriks Segitiga bawah Matriks segitiga bawah adalah matriks bujur sangkar dengan semua elemen di atas diagonal bernilai nol. aij = 0 untuk i < j.
Matriks Tridiagonal Matriks tridiagonal adalah matrik bujursangkar yang memenuhi aij = 0 untuk |i – j | ≥ 2
Sistem Persamaan Linear
a11 a 21 L= ... a N1 a 11 a T = 21 ... 0
0 a 22 ... aN 2 a12 a 22 ... 0
... 0 ... 0 ... ... ... a NN ... 0 ... 0 ... ... ... a NN
Sistem M persamaan linear atau himpunan M persamaan linear simultan dalam N bilangan x1, x2, …, xn yang tidak diketahui adalah suatu himpunan persamaan berbentuk
a11 x1 + a12 x 2 + ... + a1 N x N = c1 a 21 x1 + a 22 x 2 + ... + a 2 N x N = c 2 .......... .......... .......... .......... .......... .. a M 1 x1 + a M 2 x 2 + ... + a MN x N = c M
Koefisien-koefisien aij dan ci adalah bilangan-bilangan yang diberikan Sistem disebut homogen bila semua ci nol, jika tidak sistem disebut tak homogen. 4
Metode Numerik
Catatan Kuliah
Sistem persamaan linear tersebut dapat juga dituliskan sebagai suatu persamaan vektor,
AX = C
dengan matriks koefisien A = [aij] adalah matriks M x N, a11 a A = 21 ... a M1
a12 a 22 ... aM 2
... a1 N ... a 2 N ... ... ... a MN
x1 c1 x Sedangkan X = 2 dan C = c2 adalah vektor ... ... vektor kolom c x N M
Solusi dari sistem persamaan linear adalah himpunan bilangan x1, x2, …, xN yang memenuhi semua M persamaan tersebut. Vektor solusi dari sistem persamaan linear adalah vektor X yang komponen-komponennya merupakan solusi dari sistem persamaan tersebut.
5
Metode Numerik
Catatan Kuliah
2. Sistem Linear Segitiga Atas Sistem persamaan linear AX = C, dengan matrik koefisien A berupa matrik segitiga atas, dapat ditulis dalam bentuk, Dengan asumsi elemen-elemen
a11 x1 + a12 x2 + ... + a1 N x N = c1 a 22 x 2 + ... + a 2 N x N = c 2 .......... .......... .......... .......... .......... .. a N −1, N −1 x N −1 + a N −1, N x N = c N −1 a NN x N = c N
diagonal tak nol, akk ≠ 0, untuk k = 1, 2, 3, …, N maka terdapat suatu solusi tunggal dari sistem linear tersebut. Jika asumsi ini tidak terpenuhi, maka akan tidak terdapat solusi atau tak hingga banyaknya solusi
Solusinya dapat dicari dengan melakukan penyulihan mundur, yaitu dengan menyelesaikan persamaan terakhir pertama kali, diperoleh nilai xN, seterusnya nilai xN-1 dan yang terakhir diperolah dari persamaan pertama adalah nilai x1. Persamaan terakhir bila diselesaikan akan menghasilkan xN dengan x N =
cN a NN
Nilai xN yang diketahui dapat digunakan dalam persamaan c N −1 − a N −1, N x N x = sebelum persamaan terakhir, diperoleh xN-1 dengan N −1
a N −1, N −1
6
Metode Numerik
Catatan Kuliah
Selanjutnya nilai xN dan xN-1 dipakai untuk mencari nilai xN-2. c N − 2 − a N − 2, N −1 x N −1 − a N − 2, N x N xN −2 = a N − 2, N − 2 Setelah nilai-nilai xN, XN-1, xN-2, …, xk+1 diketahui, diperoleh nilai xk sebagai, N
ck − xk =
∑a j = k +1
akk
kj
xj ,
k = N − 1, N − 2, ..., 1
Algoritma Penyulihan Mundur untuk sistem linear Segitiga atas Masukan : n; aij , i, j = 1, 2, 3, …, n; ci , i = 1, 2, 3, …, n Langkah-langkah: x N :=
cN a NN
Untuk k := n-1, n-2, …, 1 lakukan Jumlah := 0 Untuk j := k+1, k+2, …, n lakukan Jumlah := jumlah + akj . xj xk =
ck − jumlah akk 7
Metode Numerik
Catatan Kuliah
Determinan matrik Segitiga Atas Jika A matrik segitiga, maka det(A), determinan A, diberikan oleh hasilkali elemen-elemen diagonal, det(A) = a11.a22 . … aNN Contoh 4.1 Gunakan penyulihan mundur untuk menyelesaikan sistem persamaan linear 4 x1 − x2 + 2 x3 + 3 x4 = 20 − 2 x 2 + 7 x3 − 4 x 4 = − 7 6 x3 + 5 x 4 = 4 3 x4 = 6
Jawab Dari persamaan terakhir diperoleh x4 = 6/3 = 2. Dengan memakai x4 untuk mendapatkan x3 dari persamaan ketiga, diperoleh x3 =
4 − 5(2) = −1 6
Dengan memakai x4 dan x3 untuk mendapatkan x2 dari persamaan kedua, diperoleh − 7 − 7(−1) − 4(2) x2 =
−2
= −4
Akhirnya x1 diperoleh dari persamaan pertama,
x1 =
20 − 1(−4) − 2(−1) − 3(2) =3 4 8
Catatan Kuliah
Metode Numerik
3. Eliminasi Gauss dan Pivoting Akan dikembangkan sebuah skema yang lebih efisien untuk menyelesaikan sistem persamaan linear umum AX = C, dengan N persamaan dan N bilangan yang tidak diketahui. Caranya adalah sistem persamaan linear umum tersebut dirubah menjadi sebuah sistem persamaan segitiga atas UX = Y yang setara dan kemudian dapat diselesaikan menggunakan metode penyulihan mundur. Dua sistem persamaan linear berukuran N x N dikatakan setara jika himpunanhimpunan solusinya sama. Teorema-teorema dari aljabar linear memperlihatkan bahwa bilamana transformasi tertentu diterapkan pada suatu sistem yang diketahui, maka himpunan solusinya tidak berubah. Operasi-operasi berikut bila diterapkan pada sistem linear akan menghasilkan sistem yang setara. 1. Pertukaran : urutan dari dua persamaan dapat ditukar. 2. Penskalaan : perkalian sebuah persamaan dengan konstanta tak nol. 3. Penggantian : sebuah persamaan dapat digantikan oleh jumlah persamaan itu dengan suatu kelipatan sebarang persamaan lainnya. 9
Metode Numerik
Catatan Kuliah
Contoh 4.2 Carilah persamaan parabola y = A + Bx + Cx2 yang melalui titik-titik (1,1), (2,-1) dan (3,1). Jawab Untuk masing-masing titik diperoleh persamaan yang mengaitkan nilai x terhadap nilai y. Hasilnya berupa sistem A+ B + C =1 A + 2 B + 4C = − 1 A + 3 B + 9C = 1
Peubah A dieliminasi dari persamaan kedua dan ketiga dengan cara masingmasing mengurangkan persamaan pertama dari kedua dan ketiga, diperoleh A+ B + C =1 B + 3C = −2 2 B + 8C = 0
Peubah B dieliminasi dari persamaan ketiga dengan cara mengurangkannya dengan dua kali persamaan kedua, diperoleh persamaan yang setara A+ B + C =1 B + 3C = −2 2C = 4
Dengan penyulihan mundur diperoleh C = 2, B = -8 dan A = 7 sehingga persamaan parabola adalah y = 7 - 8x + 2x2. 10
Catatan Kuliah
Metode Numerik
Cara yang paling efisien menyelesaikan sistem linear AX = C adalah menyimpan semua koefisiennya dalam array berukuran N x (N+1). Koefisienkoefisien C disimpan dalam kolom N+1 dari array, yaitu ai,N+1 = ci. Tiap baris memuat semua koefisien yang diperlukan untuk menyatakan satu persamaan dalam sistem linear. Matrik yang dilengkapi, disingkat matrik lengkap dinyatakan oleh [A,C] sehingga sistem linear dinyatakan sebagai, c1 a11 a12 ... a1 N c2 a 21 a 22 ... a 2 N [ A, C ] = ... ... ... ... a c N N 1 a N 2 ... a NN Sistem linear AX = C dengan matrik lengkap yang diberikan dapat diselesaikan dengan melakukan operasi baris elementer (OBE) pada matrik lengkap [A,C]. Peubah-peubah xk adalah pemegang posisi untuk koefisien-koefisien dan dapat dihilangkan sampai akhir perhitungan. Operasi-operasi baris berikut bila diterapkan pada matrik lengkap akan menghasilkan sistem yang setara. 1. Pertukaran : urutan dari dua baris dapat ditukar. 2. Penskalaan : perkalian sebuah baris dengan konstanta tak nol. 3. Penggantian : sebuah baris dapat digantikan oleh jumlah baris itu dengan suatu kelipatan sebarang baris lainnya. 11
Metode Numerik
Catatan Kuliah
Tumpuan Bilangan akk pada posisi (k, k) yang dipakai untuk mengeliminasi xk dalam baris-baris k+1, k+2, …, N dinamakan elemen tumpuan ke-k, dan k disebut baris tumpuan.
Contoh 4.3 Nyatakan sistem berikut dalam bentuk matrik lengkap dan cari suatu sistem segitiga atas yang setara serta solusinya. x1 + 2 x2 + x3 + 4 x4 = 13 2 x1
+ 4 x3 + 3 x 4 = 28
4 x1 + 2 x2 + 2 x3 + x 4 = 20 − 3 x1 + x 2 + 3 x3 + 2 x 4 = 6
Jawab Matrik lengkapnya adalah: Tumpuan p21= 2 p31= 4 p41= -3
1 2 4 − 3
2 0 2 1
1 4 2 3
4 13 Baris pertama sebagai baris tumpuan yang dipakai untuk mengeliminasi kolom pertama dibawah 3 28 diagonal dan a sebagai elemen tumpuan. 11 1 20 Nilai p adalah pengali baris pertama yang i1 2 6 harus dikurangi dari baris i untuk i = 2, 3, 4.
Diperoleh hasil, 12
Metode Numerik
Catatan Kuliah
1 4 13 1 2 0 − 4 2 − 5 2 Tumpuan p32= 1.5 0 − 6 − 2 − 15 − 32 6 14 45 p42= -1.75 0 7
Baris kedua sebagai baris tumpuan yang dipakai untuk mengeliminasi kolom kedua dibawah diagonal dan a22 sebagai elemen tumpuan.
Nilai pi2 adalah pengali baris kedua yang harus dikurangi dari baris i untuk i = 3, 4.
Diperoleh hasil, 1 4 13 Baris ketiga sebagai baris tumpuan yang dipa1 2 kai untuk mengeliminasi kolom ketiga dibawah 0 − 4 2 − 5 2 diagonal dan a sebagai elemen tumpuan. 33 Tumpuan 0 0 − 5 − 7.5 − 35 Nilai p43 adalah pengali baris ketiga yang p43= -1.9 0 0 9.5 5.25 48.5 harus dikurangi dari baris ke 4.
Diperoleh hasil, 1 4 13 1 2 0 − 4 2 − 5 2 0 0 − 5 − 7.5 − 35 0 0 0 − 9 − 18
Berupa matriks segitiga atas.
Menggunakan algoritma penyulihan mundur diperoleh x4= 2, x3 = 4, x2 = -1 dan x1 = 3.
Proses yang dilakukan di atas disebut dengan proses eliminasi Gauss. 13
Catatan Kuliah
Metode Numerik
Proses eliminasi Gauss harus dimodifikasi sehingga dapat dipakai dalam keadaan apapun. Pivoting Jika akk = 0 maka baris ke-k tidak dapat dipakai sebagai elemen tumpuan. Karena itu perlu mencari baris r, dengan ark ≠ 0 dan r > k dan kemudian mempertukarkan baris k dan baris r sehingga diperoleh elemen tumpuan tak nol. Proses ini disebut pivoting, dan kriteria penentuan baris mana yang dipilih disebut strategi pivoting. Jadi strategi pivoting yang paling sederhana adalah jika akk ≠ 0 maka langsung dilanjutkan melakukan eliminasi sedangkan jika akk = 0 maka dilakukan pivoting. Algoritma Eliminasi Gauss Diberikan matrik lengkap A = [aij], n x (n+1); terdiri dari [A,C]. Untuk k = 1, 2, 3, …, n-1 lakukan Cari i > k yang terkecil sehingga aik ≠ 0 Jika i demikian tak ada maka beri tanda bahwa A singulir dan berhenti Jika tidak, tukarkan isi baris I dan k dari A dan lanjutkan Untuk i = k+1, k+2, …, n lakukan p := aik / bkk Untuk j = k+1, k+2, …, n+1 lakukan aij := aij – p.akj Jika ann = 0 maka beri tanda bahwa A singulir dan berhenti. Lanjutkan dengan algoritma penyulihan mundur. 14
Catatan Kuliah
Metode Numerik
Pivoting untuk memperkecil galat Jika terdapat beberapa elemen tak nol pada kolom k yang terletak pada atau di bawah diagonal, maka terdapat pilihan untuk menentukan baris mana yang yang ditukar. Pivoting parsial paling umum digunakan. Karena komputer menggunakan hitungan presisi tetap, maka dimungkinkan bahwa suatu galat kecil akan terjadi setiap kali operasi hitungan dilaksanakan. Untuk memperkecil perambatan galat, maka periksa besarnya semua elemen di kolom ke k yang terletak pada atau di bawah diagonal, dan melokasikan baris r yang mempunyai elemen dengan nilai mutlak terbesar, yaitu
| a rk | = maks {| a kk |, | a k +1, k |, ..., | a N −1, k |, | a Nk | } Kemudian menukarkan baris r dan baris k untuk r > k. Biasanya makin besar elemen tumpuannya, akan menghasilkan perambatan galat yang makin kecil
15
Metode Numerik
Catatan Kuliah
Algoritma Eliminasi Gauss dengan Pivoting Parsial Masukan : n ; aij, i = 1, 2, …, n ; j = 1, 2, …, n+1 Langkah-langkah: Untuk k = 1, 2, 3, …, n-1 lakukan l := k Untuk i = k+1, k+2, …, n lakukakan Jika |aik| > |alk| maka l := i Jika alk = 0 maka matrik singulir dan hentikan Jika l ≠ k maka Untuk j = k, k+1, …, n+1 lakukan t := akj; akj := alj; alj := t Untuk i = k+1, k+2, …, n lakukan p := aik / akk Untuk j = k, k+1, …, n+1 lakukan aij := aij – p.akj xn := an,n+1 / ann Untuk k := n-1, n-2, …, 1 lakukan jumlah := 0 Untuk j := k+1, k+2, …, n lakukan jumlah := jumlah + akj.xj xk := (ak,n+1 - jumlah)/akk
proses
Latihan : Aplikasikan algoritma Eliminasi Gauss dengan Pivoting Parsial untuk menyelesaikan masalah pada Contoh 4.3.
16
Metode Numerik
Catatan Kuliah
4. Invers Matriks Variasi lain dari eliminasi Gauss adalah eliminasi Gauss-Jordan. Dalam hal ini penyulihan mundur dalam eliminasi Gauss dihindari dengan melakukan perhitungan tambahan yang mereduksi matriks ke bentuk diagonal sebagai pengganti bentuk segitiga. Metode ini mempunyai keuntungan dalam menyelesaikan sistem persamaan pada komputer. Invers (balikan) suatu matriks bujur sangkar A yang tak singulir pada prinsipnya dapat ditentukan dari penyelesaian n sistem, AX = cj,
j = 1, 2, …, n
dengan cj adalah kolom ke-j dari matrik satuan nxn. Cara lain yang lebih disukai untuk menghasilkan invers dari matrik A, yaitu A-1, adalah menggunakan eliminasi Gauss-Jordan untuk mengoperasikan matriks A dan matrik satuan I sehingga masing-masing direduksi menjadi matrik I dan matriks A-1. Penyelesaian sistem persamaan linear n x n dapat dilakukan dengan mencari invers dari matriks A. Solusi untuk AX = C diberikan oleh X = A-1C . Namun secara numerik cara ini tidak efisien. 17
Metode Numerik
Catatan Kuliah
Contoh 4.4 Tentukan invers dari matrik Jawab Mulai dengan matrik lengkap [A, I]
2 0 1 1 0 0 3 2 5 0 1 0 1 −1 0 0 0 1
0 1 0.67 1.67 0 0.33 1 1 0 0.20 − 0.60 0 1 0 −1.33 − 2.33 1 − 0.67 Eliminasi elemen-elemen pada kolom 2 kecuali pada diagonal
2 0 1 A = 3 2 5 1 −1 0 Tukar baris 1 dengan baris 2, kemudian bagi baris 1 sehingga a11 = 1
Tukar baris 2 1 dengan baris 3, kemudian bagi 0 baris 2 sehingga 0 a22 = 1
1 0.67 1.67 0 0.33 0 2 0 1 1 0 0 1 −1 0 0 0 1 0.67
0
0.33
− 1.33 − 2.33 1 − 0.67 − 1.67 − 1.67 0 − 0.33
1 0 1 0 0.2 0.4 Bagi baris 3 0 1 1 0 0.2 − 0.6 dengan -1 0 0 −1 1 − 0.4 − 0.8 sehingga a33 = 1
1 − 0.2 − 0.4 A−1 = 1 − 0.2 − 1.4 − 1 0.4 0.8
1.67
Matrik Satuan muncul pada bagian kiri dari matriks lengkap dan matriks invers pada bagian kanan, sehingga
Eliminasi 0 elemen-elemen 0 pada kolom 1 di bawah 1 diagonal
1 0 1 0 0.2 0.4 0 1 1 0 0.2 − 0.6 0 0 1 −1 0.4 0.8 Eliminasi
1 0 0 1 − 0.2 − 0.4 elemen-elemen − − 0 1 0 1 0 . 2 1 . 4 pada kolom 3 0 0 1 −1 0.4 0.8 di atas diagonal 18
Metode Numerik
Catatan Kuliah
Algoritma Gauss-Jordan untuk Invers Matriks Masukan : n ; aij, i = 1, 2, …, n ; j = 1, 2, …, 2n (Matrik A adalah matrik lengkap [A,I]) Langkah-langkah: Untuk k = 1, 2, 3, …, n lakukan l := k Jika k = n, lanjutkan ke langkah (1) Untuk i = k+1, k+2, …, n lakukakan Jika |aik| > |alk| maka l := i (1) Jika alk = 0 maka matrik singulir dan hentikan proses Jika l ≠ k maka Latihan : Untuk j = k, k+1, …, 2n lakukan t := akj; akj := alj; alj := t Aplikasikan algoritma Untuk j = k+1, k+2, …, 2n lakukan Eliminasi Gauss-Jordan akj := akj / akk untuk invers matriks akk := 1 untuk menyelesaikan Untuk i = 1, 2, …, n lakukan masalah pada Contoh jika i ≠ k maka 4.4. p := aik / bkk untuk j := k+1, k+2, …, 2n lakukan aij := aij - p akj Narwen, M.Si / Jurusan Matematika FMIPA Unand
19
Metode Numerik
Catatan Kuliah
5. Dekomposisi Segitiga Pada sub-bab terdahulu terlihat bahwa betapa mudahnya untuk menyelesaikan sistem segitiga atas. Karena itu, diberikan matrik A yang taksingulir, kemudian faktorkan matrik A tersebut menjadi matrik segitiga atas U dan matrik segitiga bawah L. Agar matrik U dan L tunggal maka elemen-elemen diagonalnya tidak boleh sebarang. Ada dua macam pemfaktoran. a. Pemfaktoran Doolittle, mensyaratkan elemen diagonal L semuanya bernilai 1 dan elemen diagonal U taknol. Misalkan matrik A berukuran 3 x 3, bila difaktorkan diperoleh:
a11 A = a21 a 31
a12 a22 a32
a13 1 0 a23 = l21 1 a33 l31 l32
0 u11 u12 0 . 0 u22 1 0 0
u13 u23 u33
b. Pemfaktoran Crout, mensyaratkan elemen diagonal L taknol dan semua elemen diagonal U bernilai 1. Misalkan matrik A berukuran 3 x 3, bila difaktorkan diperoleh:
a11 A = a21 a 31
a12 a22 a32
a13 l11 0 a23 = l21 l22 a33 l31 l32
0 1 u12 0 . 0 1 l33 0 0
u13 u23 1 20
Catatan Kuliah
Metode Numerik
Jika penukaran baris tidak diperlukan pada waktu menggunakan eliminasi Gauss, maka pengali-pengali pij adalah elemen-elemen diagonal bawah dari matrik L dalam pemfaktoran Doolittle. Misalkan untuk matriks A berukuran 3 x 3, maka l21 = p21, l31 = p31 dan l32 = p32. Selain itu, elemen-elemen dari matrik L dan U dapat dihitung secara langsung, dengan menghitung hasil kali LU kemudian memakai sifat kesamaan dua matriks LU = A. Penyelesaian sistem persamaan linear . Misalkan A adalah matrik koefisien dari sistem linear AX = C yang mempunyai pemfaktoran segitiga A = LU. LU Solusi dari sistem linear LUX = C diperoleh dengan cara mendefinisikan Y = UX dan kemudian menyelesaikan dua sistem LY = C dan UX = Y. Pertama diselesaikan Y dari persamaan LY = C memakai algoritma penyulihan maju dan diikuti dengan menyelesaikan X dari UX = Y memakai algoritma penyulihan mundur.
21
Metode Numerik
Catatan Kuliah
Contoh 4.5 Diberikan sitem persamaan linear berikut, 4 x1 + 3 x 2 − x3 = −2 − 2 x1 − 4 x2 + 5 x3 = 20 x1 + 2 x 2 + 6 x3 = 7 a. Bila A adalah matrik koefisien dari sistem persamaan linear di atas, tentukan matrik segitiga L dan U sebagai faktor dari matrik A. b. Tentukan solusi dari sistem persamaan linear diatas dengan menggunakan dekomposisi matrik A tersebut.
Jawab a. Tulis 3 − 1 1 0 0 u11 u12 u13 4 A = − 2 − 4 5 = l21 1 0 . 0 u22 u23 1 2 6 l31 l32 1 0 0 u33 u12 u13 u11 = l21u11 l21u12 + u22 l21u13 + u23 l u l u + l u 31 11 31 12 32 22 l31u13 + l32u23 + u33 22
Metode Numerik
Catatan Kuliah
Dari kesamaan dua matriks dan kesamaan elemen yang seletak, diperoleh u11 = 4 u12 = 3 u13 = − 1 l 21 u11 = − 2 ⇔ l 21 = − 0 . 5 l 21 u12 + u 22 = − 4 ⇔ u 22 = − 2 . 5 l 31 u11 = 1 ⇔ l31 = 0 . 25
l 21 u13 + u 23 = 5 ⇔ u 23 = 4 . 5 l 31 u12 + l 32 u 22 = 2 ⇔ l32 = − 0 . 5
l 31 u13 + l 32 u 23 + u 33 = 6 ⇔ u 33 = 8 . 5 Sehingga matrik segitiga bawah L dan matrik segitiga atas U adalah
b.
Gunakan metode penyulihan maju untuk menyelesaikan persamaan LY = C. Gunakan metode penyulihan mundur untuk menyelesaikan persamaan UX = Y.
0 0 1 L = − 0.5 1 0 0.25 − 0.5 1
= −2
y1 − 0 . 5 y1 +
y2
= 20
0 .25 y1 − 0 .5 y 2 + y 3 = 7 4 x1 + 3 x 2 −
x3 = − 2
− 2 . 5 x 2 + 4 . 5 x 3 = 19 8 . 5 x 3 = 17
3 −1 4 U = 0 − 2.5 4.5 0 8.5 0 Diperoleh nilai-nilai y1 = -2 y2 = 19 y3 = 17 Diperoleh nilai-nilai x3 = 2 x2 = -4 x1 = 3 23
Metode Numerik
Catatan Kuliah
Pemfaktoran Cholesky Misalkan A adalah matrik bujur sangkar yang definit positif dan simetri. Maka A dapat ditulis dalam bentuk A = LU dengan L dan U adalah matrikmatrik segitiga bawah dan atas, dengan U = LT.
Contoh 4.6 Gunakan metode Cholesky untuk menentukan solusi dari sitem persamaan linear , 4 x1 + 2 x2 + 14 x3 = 14 2 x1 + 17 x 2 − 5 x3 = − 101 14 x1 − 5 x 2 + 83 x3 = 155
Jawab Tulis 4
2 14 l11 0 A = 2 17 − 5 = l21 l22 14 − 5 83 l 31 l32
Dari kesamaan dua matriks dan kesamaan elemen yang seletak, diperoleh
l112 l11l12 l11l13 0 l11 l21 l31 2 2 l12l13 + l22l23 0 . 0 l22 l32 = l11l12 l12 + l22 2 2 2 + + + l l l l l l l l l l33 0 0 l33 11 13 13 12 23 22 13 23 33
2
l11 = 4 ⇔ l11 = 2; l11 l12 = 2 ⇔ l12 = 1; l11 l13 = 14 ⇔ l13 = 7 ;
2
2
l12 + l 22 = 17 ⇔ l 22 = 4 2
2
2
l12 l13 + l 22 l 23 = − 5 ⇔ l 23 = − 3; l13 + l 23 + l 33 = 83 ⇔ l 33 = 5 24
Metode Numerik
Catatan Kuliah
Sehingga matrik segitiga bawah L dan matrik segitiga atas LT adalah Gunakan metode penyulihan maju untuk menyelesaikan persamaan LY = C. Gunakan metode penyulihan mundur untuk menyelesaikan persamaan LTX = Y.
2 1 7 LT = 0 4 − 3 0 0 5
2 0 0 L = 1 4 0 7 − 3 5
2 y1
=
y1 + 4 y 2
14
= − 101
7 y1 − 3 y 2 + 5 y 3 = 155 2 x1 + x 2 − 7 x 3 =
7
4 x 2 − 3 x 3 = − 27 5 x3 =
5
Diperoleh nilai-nilai y1 = 7 y2 = -27 y3 = 5 Diperoleh nilai-nilai x3 = 1 x2 = -6 x1 = 3
25
Metode Numerik
Catatan Kuliah
6. Metode Iterasi Jacobi dan Gauss-Seidel Metode penyelesaian sistem persamaan linear yang telah dibahas sebelumnya adalah metode perhitungan secara langsung. Selanjutnya akan dibahas metode penyelesaian sistem persamaan linear secara taklangsung atau metode iteratif.
Iterasi Jacobi Misalkan diberikan sistem persamaan linear,
a11 x1 + a12 x2 + ... + a1 N x N = c1 a 21 x1 + a 22 x 2 + ... + a 2 N x N = c2 .......... .......... .......... .......... .......... .. a N 1 x1 + a N 2 x2 + ... + a NN x N = c N dengan matrik Koefisien
a11 a 21 A= ... a N1
a12 a 22 ... aN 2
... a1 N ... a 2 N ... ... ... a NN
26
