Blogger Backgrounds
Powered By Blogger

Senin, 09 Januari 2012

Dekomposisi Matriks dengan Metode Doolittle

Dekomposisi Matriks dengan Metode Doolittle

Suatu persamaan linear dapat diselesaikan secara langsung. Salah satu caranya adalah dengan menggunakan dekomposisi LU. Pada metode ini suatu sistem persamaan linier yang berbentuk:

 
difaktorisasi menjadi:
 
Pada dekomposisi LU metode Doolittle, semua komponen diagonal matriks L bernilai 1 sehingga representasi matriks di atas menjadi:


Untuk menghitung setiap komponen matriks L dan U dari matriks A dengan ukuran n x n dapat dengan menggunakan algoritma sebagai berikut:
1. Dapatkan nilai matriks U pada baris pertama:
    untuk i = 1 sampai n

2. Hitung nilai:
    untuk i=2 sampai n
3. untuk i = 2 sampai n-1

 

                   untuk j = i + 1 sampai n





4. Hitung indeks terakhir:


                             
Proses dekomposisi selesai sampai disini, proses berikutnya adalah untuk menyelesaikan sistem persamaan linier nya.

Dari dekomposisi berikut:

Matriks L dan U sudah kita dapatkan, dan dengan memisalkan:
maka
untuk mendapatkan nilai vektor y dapat dilakukan dengan substitusi maju sebagai berikut:

untuk i=2 sampai n
nilai vektor x didapatkan dengan melakukan substitusi mundur persamaan:
dengan cara:
untuk i=n-1 sampai 1

Referensi : http://www.google.com/

Determinan Matriks Hasil Dekomposisi Cara Crout

Determinan Matriks Hasil Dekomposisi Cara Crout

Dekomposisi Matriks Crout adalah dekomposisi LU yang terurai sebuah matriks menjadi matriks segitiga bawah (L), sebuah matriks segitiga atas (U) dan, meskipun tidak selalu diperlukan, matriks permutasi (P).
The Crout matrix decomposition algorithm differs slightly from the Doolittle method . Dekomposisi matriks Crout algoritma sedikit berbeda dari metode Doolittle . Doolittle's method returns a unit lower triangular matrix and an upper triangular matrix, while the Crout method returns a lower triangular matrix and a unit upper triangular matrix. Metode Doolittle itu mengembalikan sebuah unit yang lebih rendah matriks segitiga dan matriks segitiga atas, sedangkan metode Crout mengembalikan sebuah matriks segitiga bawah dan matriks segitiga atas satuan.
dekomposisi matriks matriks A adalah sedemikian rupa sehingga:

A = LDU A = LDU
being L a unit lower triangular matrix, D a diagonal matrix and U a unit upper triangular matrix, then Doolittle's method produces menjadi unit yang lebih rendah L matriks segitiga, matriks diagonal D dan U matriks segitiga atas satuan, maka metode Doolittle yang menghasilkan
A = L(DU) A = L (DU)
and Crout's method produces dan metode yang menghasilkan Crout
A = (LD)U. A = (LD) U.

Referensi : http://www.google.com/

Metode Dekomposisi Matriks

Metode Dekomposisi Matriks

Dekomposisi matriks merupakan salah satu metode numerik untuk menyelesaikan persamaan matriks.
Apabila secara analitik, mungkin akan sangat mudah menyelesaikan persamaan matriks seperti ini AX=B, dimana kita hanya mengetahui nilai matriks A dan matriks B saja, sementara kita tidak tahu nilai dari matriks X. Secara analitik kita dapat tuliskan bahwa matriks X merupakan perkalian dari inverse matriks A dengan matriks B, atau dapat ditulis X=A-1B.



Namun bagaimana jika matriks A merupakan matriks dengan dimensi 100×100 atau 1000×1000, walaupun dikasih uang satu juta saya juga ga bakalan mau ngerjain hal ‘sia-sia’ seperti itu secara analitik. Tetapi dengan metode numerik dan tentu saja dengan bantuan kemampuan programming hal seperti itu akan lebih mudah dikerjakan.
Pertanyaannya, apa sih kegunaan dekomposisi matriks di dunia real? Saya akan menjawab metode ini dapat digunakan untuk melakukan interpolasi polinomial secara numerik tentunya atau dalam bidang yang sedang saya geluti, metode ini dapat membantu saja menyelesaikan persamaan Difusi Netron.
Pada metode LU Decomposition, matriks A ditulis ulang sebagai perkalian matriks L dan U (matriks A diurai menjadi matriks L dan U). Matriks L dan U merupakan matriks segitiga. Matriks B tidak berubah, karena matriks A tidak berubah, melainkan hanya ditulis ulang.
Langkah:
1. Cari matriks L dan U sehingga A = LU. Matriks B tetap.
2. Definisikan sebuah matriks kolom baru, misalnya Y, yaitu Y = UX, sehingga LY = B. Lalu hitung y dengan substitusi maju (mulai dari Y1 sampai Yn ).
3. Hitung x dengan substitusi mundur (mulai dari X1 sampai Xn).

menggunakan matriks A dengan dimensi 4×4.
Pada dekomposisi matriks LU , A = LU sehingga didapatkan persamaan

Dari perkalian matriks maka didapatkan
a11 = u11
a12 = u12
a13 = u13
a14 = u14
a21 = l21u11
a22 = l21u12 + u22
a23 = l21u13 + u23
a24 = l21u14 + u24
a31 = l31u11
a32 = l31u12 + l32u22
a33 = l31u13 + l32u23 + u33
a34 = l31u14 + l32u24 + u34
a41 = l41u11
a42 = l41u12 + l42u22
a43 = l41u13 + l42u23 + l43u33
a44 = l41u14 + l42u24 + l43u23 + u44
Sehingga dapat didefinisikanu1j = a1j (j= 1, … ,n)
dengan (i = 2, …, n) 

dengan (i =2, … ,n; j=i, …, n), kemudian

dengan (i=3, …, n; j=2, …, i-1)
LY=B, dalam bentuk matriks dapat ditulis

Sehingga dapat didefinisikan
y
1 = b1

dengan (i =2, …, n) dan
UX=Y, dalam bentuk matriks dapat dituliskan

sehingga dapat didefiniskan
x=yn

dengan (i =1, … , n-1)


Referensi : http://www.google.com/

DETERMINAN MATRIKS

DETERMINAN MATRIKS

Determinan adalah suatu fungsi tertentu yang menghubungkan suatu bilangan real dengan suatu matriks bujursangkar.
Sebagai contoh, kita ambil matriks A2×2
A = \begin{bmatrix}<br />
a & b\\<br />
c & d\\<br />
\end{bmatrix}” /> tentukan determinan A</dd>
</dl>
</dd>
</dl>
<p><span id=untuk mencari determinan matrik A maka,
detA = ad – bc


Determinan dengan Ekspansi Kofaktor


 Determinan dengan Minor dan kofaktor

A = – 2\begin{bmatrix} 4 & 4\\ 3 & 1\\ \end{bmatrix} + 3\begin{bmatrix} 4 & 5\\3 & 2\\ \end{bmatrix} = 1(-3) – 2(-8) + 3(-7) = -8

Determinan dengan Ekspansi Kofaktor Pada Kolom Pertama

Pada dasarnya ekspansi kolom hampir sama dengan ekspansi baris seperti di atas. Tetapi ada satu hal yang membedakan keduanya yaitu faktor pengali. Pada ekspansi baris, kita mengalikan minor dengan komponen baris pertama. Sedangkan dengan ekspansi pada kolom pertama, kita mengalikan minor dengan kompone kolom pertama.
Misalkan ada sebuah matriks A3×3
A = – 4\begin{bmatrix} 4 & 4\\ 3 & 1\\ \end{bmatrix} + 3\begin{bmatrix} 4 & 5\\3 & 2\\ \end{bmatrix} = 1(-3) – 4(-8) + 3(-7) = 8

Adjoin Matriks 3 x 3

Bila ada sebuah matriks A3×3
A = \begin{bmatrix} 3&2&-1\\ 1&6&3 \\ 2&4&0\\ \end{bmatrix}
Kofaktor dari matriks A adalah
C11 = -12 C12 = 6 C13 = -16
C21 = 4 C22 = 2 C23 = 16
C31 = 12 C32 = -10 C33 = 16
maka matriks yang terbentuk dari kofaktor tersebut adalah
\begin{bmatrix} 12&6&-16\\ 4&2&16\\ 12&-10&16\\ \end{bmatrix}
untuk mencari adjoint sebuah matriks, kita cukup mengganti kolom menjadi baris dan baris menjadi kolom
adj(A) = \begin{bmatrix} 12&4&12\\ 6&2&-10\\ -16&16&16\\ \end{bmatrix}

Determinan Matriks Segitiga Atas

Jika A adalah matriks segitiga nxn (segitiga atas, segitiga bawah atau segitiga diagonal) maka det(A) adalah hasil kali diagonal matriks tersebut
det(A) = a_{11}a_{22}\cdots a_{nn}
Contoh
\begin{bmatrix} 2&7&-3&8&3\\ 0&-3&7&5&1\\ 0&0&6&7&6\\ 0&0&0&9&8\\ 0&0&0&0&4\\ \end{bmatrix} = (2)(-3)(6)(9)(4) = -1296

Metode Cramer

jika Ax = b adalah sebuah sistem linear n yang tidak di ketahui dan det(A)≠ 0 maka persamaan tersebut mempunyai penyelesaian yang unik
X_{1} =  \frac{det(A_{1})} {det(A)},  X_{2} = \frac{det(A_{2})} {det(A)}, ... ,  X_{n} = \frac{det(A_{n})} {det(A)}dimana A j adalah matrik yang didapat dengan mengganti kolom j dengan matrik b
Contoh soal:
Gunakan metode cramer untuk menyelesaikan persoalan di bawah ini
x1 + 2x3 = 6
-3x1 + 4x2 + 6x3 = 30
-x1 – 2x2 + 3x3 = 8
Jawab:
bentuk matrik A dan b
A =
kemudian ganti kolom j dengan matrik b
A1 = \begin{bmatrix} 6 & 0 & 2\\ 30 & 4 & 6\\ 8 & -2 & 3\\ \end{bmatrix} A2 = \begin{bmatrix} 1 & 6 & 2\\ -3 & 30 & 6\\ -1 & 8 & 3\\ \end{bmatrix} A3 = \begin{bmatrix} 1 & 0 & 6\\ -3 & 4 & 30\\ -1 & -2 & 8\\ \end{bmatrix}
dengan metode sarrus kita dapat dengan mudah mencari determinan dari matrik-matrik di atas
maka,
 x_{1} = \frac{det(A_{1})} {det(A)} = \frac{-40} {44} = \frac{-10} {11}
 x_{2} = \frac{det(A_{2})} {det(A)} = \frac{72} {44} = \frac{18} {11}
 x_{3} = \frac{det(A_{3})} {det(A)} = \frac{152} {44} = \frac{38} {11}

Tes Determinan untuk Invertibilitas

Pembuktian: Jika R di reduksi secara baris dari Ä. Sebagai langkah awal, kita akan menunjukkan bahwa det(A) dan det(R) keduanya adalah nol atau tidak nol: E1,E2,…,Er menjadi matrix element yang berhubungan dengan operasi baris yang menghasilkan Rdari A. Maka,
R=ErE2 E1 Adan,
det(R)=det(Er)…det(E2)det(E1)det(EA)Jika A dapat di-invers, maka sesuai dengan teorema equivalent statements , maka R = I, jadi det(R) = 1 ≠ 0 dan det(A) ≠ 0. Sebaliknya, jika det(A) ≠ 0, maka det(R) ≠ 0, jadi R tidak memiliki baris yang nol. Sesuai dengan teorema R = I, maka A adalah dapat di-invers. Tapi jika matrix bujur sangkar dengan 2 baris/kolom yang proposional adalah tidak dapat diinvers.
Contoh Soal :
A=
dengan metode Sarrus, kita dapat menghitung determinan dari matrix A
det(A) = 64
A^{-1} = \frac{1}{det(A)}adj(A) = \frac{1}{64} \begin{bmatrix}<br />
12 &  4 &  12\\<br />
6 &  2 & -10\\<br />
-16 & 16 &  16\\<br />
\end{bmatrix} = \begin{bmatrix}<br />
\frac{12}{64} & \frac{4}{64}  &  \frac{12}{64}\\<br />
\frac{6}{64}  & \frac{2}{64}  & -\frac{10}{64}\\<br />
-\frac{16}{64} & \frac{16}{64} &  \frac{16}{64}\\<br />
\end{bmatrix}” /></p>
<h3>Sistem Linear Dalam Bentuk Ax = λx</h3>
<p>dalam sistem aljabar linear sering ditemukan</p>
<pre>      <em>A</em>x = <em>λ</em>x    ; dimana λ adalah skalar</pre>
<p>sistem linear tersebut dapat juga ditulis dengan λx-Ax=0, atau dengan memasukkan matrix identitas menjadi</p>
<pre>      (<em>λ</em><em>I - A) x = 0 </em></pre>
<p>contoh:</p>
<p>diketahui persamaan linear</p>
<pre>x<span class=1+3x2= λx1 4x1+2x2=λx2
dapat ditulis dalam bentuk
\begin{bmatrix} 1 & 3\\ 4 & 2\\ \end{bmatrix}\begin{bmatrix} x_1\\ x_2\\ \end{bmatrix}
= λ
\begin{bmatrix} x_1\\ x_2\\ \end{bmatrix}
yang kemudian dapat diubah
A =\begin{bmatrix} 1 & 3\\ 4 & 2\\ \end{bmatrix}dan x =\begin{bmatrix} x_1\\ x_2\\ \end{bmatrix}
yang kemudian dapat ditulis ulang menjadi
λ
\begin{bmatrix} x_1\\ x_2\\ \end{bmatrix} - \begin{bmatrix} 1 & 3\\ 4 & 2\\ \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ \end{bmatrix} = \begin{bmatrix} 0\\ 0\\ \end{bmatrix}
λ
\begin{bmatrix} 1 & 0\\ 0 & 1\\ \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ \end{bmatrix} - \begin{bmatrix} 1 & 3\\ 4 & 2\\ \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ \end{bmatrix} = \begin{bmatrix} 0\\ 0\\ \end{bmatrix}\begin{bmatrix} \lambda\,\!-1 & -3\\ -4 & \lambda\,\!-2\\ \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ \end{bmatrix} = \begin{bmatrix} 0\\ 0\\ \end{bmatrix}
sehingga didapat bentuk
λ I - A =
\begin{bmatrix} \lambda\,\!-1 & -3\\ -4 & \lambda\,\!-2\\ \end{bmatrix}
namun untuk menemukan besar dari λ perlu dilakukan operasi
detI - A) = 0  ;λ adalah eigenvalue dari A
dan dari contoh diperoleh
detI - A) =
\begin{bmatrix} \lambda\,\!-1 & -3\\ -4 & \lambda\,\!-2\\ \end{bmatrix}
= 0
atau λ^2 – 3λ – 10 = 0
dan dari hasil faktorisasi di dapat λ1 = -2 dan λ2 = 5
dengan memasukkan nilai λ pada persamaan (λ I – A) x = 0, maka eigenvector bisa didapat bila λ = -2 maka diperoleh
\begin{bmatrix} -3 & -3\\ -4 & -4\\ \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ \end{bmatrix} = \begin{bmatrix} 0\\ 0\\ \end{bmatrix}
dengan mengasumsikan x2 = t maka didapat x1 = t
x = \begin{bmatrix} -t\\ t\\ \end{bmatrix}