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/𝜆^* + μ

Kuliah 6 Analisis Numerik Lanjut

Sistem Persamaan Linear

Persamaan Linear

Persamaan linear adalah sebuah persamaan yang tidak ada perkalian antar variabel bebas, seperti 3x + 2y = 1.

Sistem Persamaan Linear

Sebuah sistem yang berisi persamaan-persamaan linear, bentuk umumnya adalah

a₁₁ x₁ + a₁₂ x₂ +...+a_1n x_n = b₁

a₂₁ x₁ + a₂₂ x₂ +...+a_2n x_n = b₂

_...

a_m1 x₁ + a_m2 x₂ +...+a_mn x_n = b_m

jika ditulis dalam bentuk matriks akan menghasilkan

Ax = b

Atau

Pangkat(A) = pangkat(A|b) = n  à  SPL mempunyai solusi tunggal.

Pangkat(A) ≠ pangkat(A|b) à SPL tidak mempunyai solusi.

Bila suatu SPL mempunyai solusi tunggal, maka terdapat banyak cara untuk mencari penyelesaian SPL tersebut, di antaranya adalah : x = A^-1b. 

Metode Substitusi Maju

Metode ini dimulai dengan mengubah terlebih dahulu atriks A menjadi matriks segitiga bawah

kemudian menyelesaikannya mulai dari x₁

Metode Substitusi Mundur

Metode ini dimulai dengan mengubah terlebih dahulu atriks A menjadi matriks segitiga atas

kemudian menyelesaikannya mulai dari x_n

Eliminasi Gauss Naif

Metode ini adalah kembangan dari metode eliminasi.

Langkah penyelesaian:

1.      Tulis SPL dalam bentuk matriks diperbesar

2.      Ubah matriks tersebut menjadi matriks segitiga atas atau segitiga bawah dengan operasi baris dasar (OBD)

Contoh : selesaikan SPL berikut dengan metode eliminasi Gauss

6x₁ – 2x₂ + 2x₃ + 4x₄ = 16

12x₁ – 8x₂ + 6x₃ + 10x₄ = 26

3x₁ – 13x₂ + 9x₃ + 3x₄ = -19

-6x₁ + 4x₂ + x₃ - 18x₄ = -34

Jawaban

kemudian solusi diperoleh dengan menerapkan substitusi mundur

Vektor Eror

Untuk suatu SPL, didefinisikan vektor eror sebagai berikut

yaitu hampiran dikurangi nilai eksak

Vektor Residu

Untuk suatu SPL, didefinisikan vektor residu sebagai berikut

yaitu sisa yang dihasilkan oleh hampiran

Contoh : misalkan diberikan matriks A, vektor b, hampiran, dan nilai eksak sebagai berikut

tentukan eror dan residu

Jawaban

Eliminasi Gauss dengan Pivoting

Metode ini digunakan untuk mengantisipasi gagalnya proses komputasi Eliminasi Gauss tanpa pivoting. Gagalnya eliminasi Gauss disebabkan oleh adanya elemen diagonal utama matriks A yang bernilai nol.

Pivot Parsial

Langkah :

1.      Tentukan r sehingga

2.      Tukar baris i dengan r, jika i=r tidak ditukar

3.      Buat nol elemen di bawah a_ii

4.      Ulangi langkah 1-3 sampai membentuk matriks segitiga atas

5.      Lakukan subtsitusi mundur

Pivot Parsial Terskala

1.      Definisikan vektor indeks l = [l₁,l₂,...,l_n] = [1,2,...,n]

2.      Definisikan vektor skala s = [s₁,s₂,...,s_n] dengan

3.      Tentukan rasio masing-masing baris menggunakan

4.      Pilih j, yaitu indeks dengan rasio maksimum. Baris j adalah pivot untuk iterasi k (k = 1, 2, …, n-1). Jika banyaknya rasio maksimum lebih dari satu, maka pilih indeks terkecil.

5.      Tukar l_k dengan l_j pada vektor indeks

6.      Tukarkan baris pada matriks sesuai dengan vektor indeks.

7.      Buat nol elemen di bawah a_kk.

8.      Kembali ke langkah 3. Vektor indeks yang digunakan adalah yang terbentuk pada langkah 5.

Contoh : Tentukan solusi dari SPL berikut menggunakan eliminasi Gauss dengan pivot parsial terskala

Jawaban (hanya 1 iterasi)

Pertama definisikan vektor indeks dan vektor skala

l = [1,2,3] = [l₁,l₂,l₃]

s = [2,1,4] = [s₁,s₂,s₃]

Untuk iterasi pertama (k = 1), tentukan j, yaitu indeks dengan rasio maksimum. Jika banyaknya rasio maksimum lebih dari satu, maka dipilih indeks terkecil.

Tukarkan l_k  dengan l_j  pada vektor indeks. Artinya, untuk k=1 dan j=2, tukarkan l₁ dan l₂ , sehingga diperoleh vektor indeks baru l = [2,1,3]

Tukarkan baris pada matriks sesuai dengan vektor indeks sehingga diperoleh

Buat nol elemen-elemen di bawah a₁₁

Iterasi pertama selesai

Struktur Banded

Sebuah matriks berukuran n x n disebut mempunyai struktur banded jika terdapat bilangan bulat k (k ≤ n) sehingga a_ij = 0  ketika | i – j | ≥ k.

Tridiagonal System

Suatu sistem yang direpresentasikan dengan matriks yang memenuhi:

1. Terdapat 3 diagonal, yaitu diagonal utama, superdiagonal, dan subdiagonal.
2. Elemen-elemen a_ij ≠ 0 jika |i–j|≤ 1  dan a_ij=0 jika |i–j|≥ 2.

Contoh :

Strictly Diagonal Domiance

Matriks A = (a_ij)_nxn adalah strictly diagonally dominant jika memenuhi syarat berikut

Pentadiagonal System

Suatu sistem yang direpresentasikan dengan matriks yang memenuhi:

1. Terdapat 5 diagonal, yaitu diagonal utama,  2 super-diagonal, dan 2 subdiagonal.
2. Elemen-elemen a_ij ≠ 0 jika |i–j|≥ 2  dan a_ij = 0 jika|i–j|≥ 3, untuk setiap i, j.

Contoh :