Marina Hartono: Januari 2012

Senin, 09 Januari 2012

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

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

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 Y₁ sampai Y_n ).

3. Hitung x dengan substitusi mundur (mulai dari X₁ sampai X_n).

menggunakan matriks A dengan dimensi 4×4.

Pada dekomposisi matriks LU , A = LU sehingga didapatkan persamaan

$\begin{pmatrix} 1& 0& 0& 0\\ l_{21} & 1& 0&0 \\ l_{31} & l_{32} & 1&0 \\ l_{41}& l_{42} &l_{43} & 1 \end{pmatrix}\begin{pmatrix} u_{11} &u_{12} &u_{13} &u_{14} \\ 0&u_{22} &u_{23} &u_{24} \\ 0& 0&u_{33} &u_{34} \\ 0& 0& 0& u_{44} \end{pmatrix}=\begin{pmatrix} a_{11} &a_{12} &a_{13} &a_{14} \\ a_{21} &a_{22} &a_{23} &a_{24} \\ a_{31} &a_{32} &a_{33} &a_{34} \\ a_{41} &a_{42} &a_{43} &a_{44} \end{pmatrix}$

Dari perkalian matriks maka didapatkan

a₁₁ = u₁₁
a₁₂ = u₁₂
a₁₃ = u₁₃
a₁₄ = u₁₄
a₂₁= l₂₁u₁₁
a₂₂ = l₂₁u₁₂ + u₂₂
a₂₃ = l₂₁u₁₃ + u₂₃
a₂₄ = l₂₁u₁₄ + u₂₄
a₃₁ = l₃₁u₁₁
a₃₂ = l₃₁u₁₂+ l₃₂u₂₂
a₃₃ = l₃₁u₁₃ + l₃₂u₂₃ + u₃₃
a₃₄ = l₃₁u₁₄ + l₃₂u₂₄ + u₃₄
a₄₁= l₄₁u₁₁
a₄₂ = l₄₁u₁₂+ l₄₂u₂₂
a₄₃ = l₄₁u₁₃ + l₄₂u₂₃ + l₄₃u₃₃
a₄₄ = l₄₁u₁₄ + l₄₂u₂₄ + l₄₃u₂₃ + u₄₄

Sehingga dapat didefinisikanu_1j = a_1j(j= 1, … ,n)

$l_{i1}=\frac{a_{i1}}{u_{11}}$

dengan (i = 2, …, n)

$u_{ij}=a_{ij}-\sum_{k=1}^{i-1}l_{ik}u_{kj}$

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

$l_{ij}=\frac{1}{u{ij}}\left ( a_{ij}-\sum_{k=1}^{j-1}l_{ik}u_{kj} \right )$

dengan (i=3, …, n; j=2, …, i-1)

LY=B, dalam bentuk matriks dapat ditulis
$\begin{pmatrix} 1 & 0 &0 &0 \\ l_{21}&1 &0 &0 \\ l_{31}&l_{32} &1 &0 \\ l_{41}&l_{42} &l_{43} & 1 \end{pmatrix}\begin{pmatrix} y_{1}\\ y_{2}\\ y_{3}\\ y_{4} \end{pmatrix}=\begin{pmatrix} b_{1}\\ b_{2}\\ b_{3}\\ b_{4} \end{pmatrix}$

Sehingga dapat didefinisikan
y₁= b₁

$y_{i}=b_{i}-\sum_{j=1}^{i-1}l_{ij}y_{j}$

dengan (i =2, …, n) dan

UX=Y, dalam bentuk matriks dapat dituliskan
$\begin{pmatrix} u_{11} &u_{12} &u_{13} &u_{14} \\ 0 &u_{22} &u_{23} &u_{24} \\ 0 &0 &u_{33} &u_{34} \\ 0 &0 &0 &u_{34} \end{pmatrix}\begin{pmatrix} x_{1}\\ x_{2}\\ x_{3}\\ x_{4} \end{pmatrix}=\begin{pmatrix} y_{1}\\ y_{2}\\ y_{3}\\ y_{4} \end{pmatrix}$
sehingga dapat didefiniskan
x=y_n
$x_{n-i}=\left ( y_{n-i}-\sum_{j=n-i+1}^{n}u_{n-i,j}x_{j}\frac{1}{u_{n-i,n-i}} \right )$

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

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

DETERMINAN MATRIKS

Determinan adalah suatu fungsi tertentu yang menghubungkan suatu bilangan real dengan suatu matriks bujursangkar.

Sebagai contoh, kita ambil matriks A_2×2

A = $\begin{bmatrix} a & b\\ c & d\\ \end{bmatrix}” /> tentukan determinan A</dd> </dl> </dd> </dl> <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 A_3×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 A_3×3

A = $\begin{bmatrix} 3&2&-1\\ 1&6&3 \\ 2&4&0\\ \end{bmatrix}$

Kofaktor dari matriks A adalah

C₁₁ = -12 C₁₂ = 6 C₁₃ = -16

C₂₁ = 4 C₂₂ = 2 C₂₃ = 16

C₃₁ = 12 C₃₂ = -10 C₃₃ = 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

x₁ + 2x₃ = 6

-3x₁ + 4x₂ + 6x₃ = 30

-x₁ – 2x₂ + 3x₃ = 8

Jawab:
bentuk matrik A dan b

A =

kemudian ganti kolom _j dengan matrik b

A₁ = $\begin{bmatrix} 6 & 0 & 2\\ 30 & 4 & 6\\ 8 & -2 & 3\\ \end{bmatrix}$ A₂ = $\begin{bmatrix} 1 & 6 & 2\\ -3 & 30 & 6\\ -1 & 8 & 3\\ \end{bmatrix}$ A₃ = $\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: E₁,E₂,…,E_r menjadi matrix element yang berhubungan dengan operasi baris yang menghasilkan Rdari A. Maka,
R=E_r…E₂ E₁ Adan,
det(R)=det(E_r)…det(E₂)det(E₁)det(E_A)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} 12 & 4 & 12\\ 6 & 2 & -10\\ -16 & 16 & 16\\ \end{bmatrix} = \begin{bmatrix} \frac{12}{64} & \frac{4}{64} & \frac{12}{64}\\ \frac{6}{64} & \frac{2}{64} & -\frac{10}{64}\\ -\frac{16}{64} & \frac{16}{64} & \frac{16}{64}\\ \end{bmatrix}” /> <h3>Sistem Linear Dalam Bentuk Ax = λx</h3> dalam sistem aljabar linear sering ditemukan <pre> Ax = λx ; dimana λ adalah skalar</pre> sistem linear tersebut dapat juga ditulis dengan λx-Ax=0, atau dengan memasukkan matrix identitas menjadi <pre> (λI - A) x = 0 </pre> contoh: diketahui persamaan linear <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

det (λ I - A) = 0  ;λ adalah eigenvalue dari A

dan dari contoh diperoleh

det (λ I - A) =

$\begin{bmatrix} \lambda\,\!-1 & -3\\ -4 & \lambda\,\!-2\\ \end{bmatrix}$

= 0

atau λ^2 – 3λ – 10 = 0
dan dari hasil faktorisasi di dapat λ₁ = -2 dan λ₂ = 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 x₂ = t maka didapat x₁ = t

x =