Kuliah 7 Analisis Numerik Lanjut

Sistem Persamaan Linear (Bagian 2)

Faktorisasi LU

Mengubah bentuk matriks A menjadi A = LU. Metode ini digunakan untuk menyelesaikan SPL.

Langkah penyelesaian SPL :

1.      Bentuk matriks L dan U dari A

2.      Selesaikan Ly = b

3.      Selesaikan Ux = y

Misalkan diberikan suatu matriks A, maka faktorisasi dapat dilakukan dengan cara berikut

Contoh : berikan matriks L dan U dari matriks berikut

Jawaban

Faktorisasi Dolitle

Mirip seperti faktorisasi LU, hanya saja pada metode ini tidak menggunakan OBD namun menggunakan persamaan dari perkalian matriks L dan U. Misalkan diberikan matriks berikut

arahkan terlebih dahulu ke bentuk berikut

Sehingga LU menjadi

Kemudian hitung masing-masing elemen pada L dan U

Sehingga dekomposisi menjadi

Faktorisasi Crout

Faktorisasi ini menggunakan L dan U pada faktorisasi Dolitle, yaitu L = L^DD, dan U = D^-1U^D dengan D adalah diagonal dari U^D.

Faktorisasi LDL^T

Metode mengharuskan matriks A simetrik dan memanfaatkan faktorisasi Dolitle di mana L didapat dari faktorisasi Dolitle, dan D adalah diagonal dari matriks U Dolitle.

Faktorisasi Cholesky

Faktorisasi ini meneruskan faktorisasi LDL^T, dengan memecah D menjadi D = D^1/2D^(1/2)T, sehingga A = LD^1/2D^(1/2)TL^T = L^ch(L^ch)^T

Solusi Iteratif Persamaan Linear

Metode untuk mencari solusi sistem persamaan linear secara iteratif. Misalkan diberikan SPL sebagai berikut

Dengan mengasumsikan a_kk tidak sama dengan nol maka iterasi dapat dilakukan dengan cara berikut

Nilai awal iterasi ini ditentukan secara bebas, namun akan menentukan kecepatan kekonvergenannya.

Iterasi Jacobi

Metode ini sama dengan sebelumnya dengan rumus umum

Contoh : tentukan solusi SPL menggunakan metode Jacobi dengan matriks A dan b berikut

Misalkan nilai awal = [0,0,0]

Jawaban

Iterasi metode Jacobi

Dengan menggunakan Scilab, didapat solusi pada iterasi ke-21 x⁽²¹⁾ = [2,3,-1]

Metode Gauss-Seidel

Metode ini memodifikasi metode Jacobi dengan menggunakan nilai x_i yang baru didapat untuk mencari x_i+1. Secara sederhana dapat digambarkan sebagai berikut

dengan rumus umum

Nilai Eigen

Misalkan A adalah matriks n x n maka vektor yang tak nol x di R_n  disebut vektor eigen dari A jika Ax adalah kelipatan skalar dari x, yaitu Ax =  λx

untuk suatu skalar λ. Skalar λ dinamakan nilai eigen .

Untuk menentukan nilai eigen dari matriks A dapat menggunakan persamaan karakteristik dari matriks A yaitu det(A-λI) = 0

Contoh : tentukan nilai Eigen dari matriks berikut

Jawaban

Maka nilai Eigennya adalah 5 dan 2

Sifat Nilai Eigen

1. Jika 𝜆 nilai eigen A →𝑝(𝜆)" adalah nilai eigen dari " 𝑝(𝐴)" untuk suatu polinomial P.  Khususnya" 𝜆^k nilai eigen dari 𝐴^k
2. Jika A nonsingular dan 𝜆 nilai eigen A → 𝑝(𝜆^-1 )" adalah nilai eigen dari P(" 𝐴^(−1) ") untuk suatu polinomial P.  Khususnya" 𝜆^-1 nilai eigen  dari 𝐴^-1
3. Jika A matriks real dan simetrik → nilai eigennya real.
4. Jika A kompleks dan hermitian → nilai eigennya real.
5. Jika A hermitian dan definit positif → nilai eigennya positif
6. Jika P nonsingular→A dan PA"P" ^"−1" (Similar) mempunyai nilai eigen yang sama

Teorema Gershgorin

Power Method

Power Method adalah cara untuk mencari nilai Eigen dominan secara iteratif. Nilai Eigen sendiri adalah nilai yang mutlaknya lebih besar dari nilai Eigen yang lain, dengan kata lain

Langkah :

Percepatan Aitken

Cara untuk mempercepat kekonvergenan power method dengan rumus

Contoh : tentukan nilai Eigen dominan dari matriks berikut

Jawaban

Jika diteruskan iterasi akan berhenti pada nilai eigen = r = 6, sehingga nilai eigen dominannya adalah 6.

Invers Power Method

Metode ini dipakai untuk mencari nilai Eigen dominan terkecil. Langkah yang digunakan sama seperti power method, karena metode ini mencari 1/ 𝜆 yang terbesar, akibatnya 𝜆 yang dihasilkan adalah yang terkecil. Metode ini mengubah persamaan Eigen awal menjadi

Nilai Eigen terkecil didapat dengan rumus 𝜆 = 1/ 𝜆^*

Shifted Power Method

Metode ini mencari nilai Eigen terjauh dari suatu nilai μ. Persamaan Eigen awal diubah menjadi

sehingga dengan menerapkan power method akan dihasilkan 𝜆 – μ yang terbesar, atau 𝜆 yang terjauh dari μ.

nilai Eigen dapat dicari dengan rumus 𝜆 = 𝜆^* + μ

Shifted Inverse Power Method

Metode ini mencari nilai Eigen terdekat dari suatu nilai μ. Persamaan Eigen awal diubah menjadi

sehingga dengan menerapkan power method akan dihasilkan 1/ (𝜆 – μ) yang terbesar, atau 𝜆 yang terdekat dari μ.

nilai Eigen dapat dicari dengan rumus 𝜆 = 1/𝜆^* + μ