Dunia ini dikendalikan oleh Algoritma!

Pernyataan tersebut seringkali saya dengar di mana-mana. Pernyataan in juga yang membuat saya ingin berkuliah lagi mengambil studi master sains komputasi.

Namun setelah mengikuti kuliah beberapa minggu belakangan, saya sadar bahwa pernyataan itu salah sepenuhnya. Pernyataan yang tepat adalah:

Dunia ini dikendalikan oleh ALJABAR!

Tidak menyangka bahwa dalam dunia numerik, konsep-konsep di aljabar linear sangat amat digunakan. Sebagai contoh, saat kita hendak menyelesaikan suatu sistem persamaan linear berikut:

Sistem Persamaan Linear

Suatu sistem persamaan linear bisa dituliskan dalam bentuk aljabar berupa matriks dan vektor sebagai berikut:

\[Ax = b\]

SPL tersebut akan memiliki solusi saat \(A\) memiliki invers, yakni \(A^{-1}\).

Bagaimana caranya menghitung \(A^{-1}\) dari \(A\)?

Pada aljabar linear elementer, kita bisa melakukan operasi baris elementer (OBE) sebagai berikut:

\[[A | I] \rightarrow [I|A^{-1}]\]

Jika \(A\) merupakan matriks yang berukuran kecil, kita bisa menghitungnya dengan mudah. Namun saat kita berhadapan dengan matriks berukuran sangat amat besar dan kompleks, kita bisa mengandalkan metode aproksimasi.

Ternyata metode aproksimasi juga berlandaskan konsep aljabar linear yang kuat!

Oleh karena itu, sebelum saya lanjut berbicara mengenai metode aproksimasi, saya akan menuliskan beberapa materi refreshment terkait aljabar linear.

Refreshment Aljabar Linear

Teorema SPL

Jika \(A\) adalah matriks \(n \times n\) inversible, maka untuk setiap vektor \(b\) \(1 \times n\) pada sistem persamaan linear \(Ax = b\) memiliki tepat satu solusi. Yaitu:

\[x = A^{-1}b\]

Berikut ini kita coba review kembali secara singkat beberapa konsep dalam aljabar yang kelak akan membantu kita memahami bagaimana cara penyelesaian SPL secara numerik.

Matriks Singular dan Tak Singular

Dari penjelasan sebelumnya kita telah mengenal apa itu matriks invers. Kita akan mengingat kembali suatu konsep bernama determinan matriks. Di R kita bisa menghitung determinan dari suatu matriks dengan perintah det(matriks).

Jika suatu matriks persegi memiliki determinan = 0, maka matriks tersebut tidak memiliki invers. Matriks yang tidak memiliki invers disebut matriks singular.

Kebalikannya:

Jika suatu matriks memiliki determinan \(\neq 0\), maka matriks memiliki invers. Matriks berinvers disebut matriks tak singular.

Determinan Matriks

Untuk matriks berukuran \(2 \times 2\), cara menghitung determinan matriksnya adalah sebagai berikut:

\[A = \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix}\]

\[|A| = ad - bc\]

Bagaimana dengan matriks berukuran \(3 \times 3\)? Berikut caranya:

Kita perlu memperlebar kolom dari matriks tersebut agar semua elemen terkena.

\[A = \begin{bmatrix} a & b & c\\ d & e & f \\ g & h & i \\ \end{bmatrix}\]

\[|A| = (aei + bfg + cdh) - (ceg + afh + bdi)\]

Sifat-Sifat Determinan Matriks

Misalkan \(A\) adalah matriks yang memiliki determinan, maka:

  1. \(|A^T| = |A|\)
  2. \(|A . B| = |A| . |B|\)
  3. \(|A^n| = |A|^n\)
  4. \(|A^{-1}| = \frac{1}{|A|}\)
  5. \(|k \times A_{m \times m}| = k^m \times |A|\)

Nilai Eigen dan Vektor Eigen

Definisi

Jika \(A\) adalah matriks \(n \times n\), maka vektor tak nol \(x \in \mathbb{R}^n\) dinamakan vektor eigen dari \(A\) jika \(Ax\) adalah kelipatan skalar dari \(x\). Yakni:

\[Ax = \lambda x\]

untuk suatu skalar \(\lambda\) tertentu. \(\lambda\) disebut sebagai nilai eigen yang bersesuaian dengan vektor eigen.

Teorema

Jika \(A\) adalah matriks berukuran \(n \times n\), maka \(\lambda\) adalah nilai eigen dari \(A\) jika dan hanya jika ia memenuhi persamaan:

\[det(\lambda I - A) = 0\]

Persamaan di atas disebut dengan persamaan karakterisktik.

Vektor dan nilai eigen bisa dihitung di R menggunakan function eigen(matriks).

Norm Vektor

Norm vektor merupakan fungsi pemetaan dari vektor-vektor di \(x \in \mathbb{R}^n\) ke bilangan real \(||x||\) sehingga memenuhi:

Sifat Norm Vektor

Sifat Norm Vektor

Norm Matriks

Norm matriks merupakan fungsi pemetaan dari matriks-matriks bujur sangkar di \(\mathbb{R}^{n \times n}\) ke \(\mathbb{R}\) sehingga memenuhi:

Sifat Norm Matriks

Sifat Norm Matriks

\[\forall z \neq 0 \text{ dan natural matrix norm } ||.|| \text{ diperoleh } ||Az|| \leq ||A|| . ||z||\]

Cara menghitung norm matriks

Beberapa teorema dan definisi yang berguna:

Norm Matriks dan Jari-jari Spektral

Norm Matriks dan Jari-jari Spektral

Summaries:

  1. Norm \(\infty\) adalah nilai max sum harga mutlak baris.
  2. Norm \(1\) adalah nilai max sum harga mutlak kolom.

Teorema Kekonvergenan

Suatu matriks \(A\) dikatakan konvergen ke 0 jika \(\lim_{k \rightarrow \infty} (A^k)_{ij} = 0\).

Pernyataan berikut ini ekivalen:

  1. \(A\) matriks yang konvergen.
  2. \(\lim_{k \rightarrow \infty} ||A^k|| = 0\), untuk suatu natural norm.
  3. \(\lim_{k \rightarrow \infty} ||A^k|| = 0\), untuk setiap natural norm.
  4. \(\rho(A) < 1\).
  5. \(\lim_{k \rightarrow \infty} A^kx = 0, \forall x\).

Perhatikan baik-baik teorema di atas. Terutama pada poin 4 dimana menjadi kunci kekonvergenan dari suatu skema iterasi kelak.

Matriks Diagonal, Upper, dan Lower

Matriks diagonal adalah matriks yang hanya berisi elemen di diagonalnya saja. Matriks upper triangle adalah matriks yang hanya berisi segitiga di atas. Matriks lower triangle adalah matriks yang hanya berisi segitiga di bawah.

Matriks Diagonal Dominan Kuat

Matriks diagonal dominan kuat adalah matriks yang memiliki elemen harga mutlak diagonal terbesar.

Misalkan:

##      [,1]  [,2]  [,3] 
## [1,] "a11" "a12" "a13"
## [2,] "a21" "a22" "a23"
## [3,] "a31" "a32" "a33"

Definisi diagonal dominan kuat adalah:

\[|a_{ii}| > \sum_{i=1,j \neq i}^n |a_{ij}|\]

Contoh:

##      [,1] [,2] [,3]
## [1,]    7    2    0
## [2,]    3    5   -1
## [3,]    0    5   -6

\(A\) merupakan matriks diagonal dominan kuat karena:

\[|7| > |2| + |0|\]

\[|5| > |3| + |-1|\]

\[|-6| > |0| + |-5|\]

Matriks diagonal dominan kuat adalah non singular.

Bagaimana jika \(A\) kita bukan matriks diagonal dominan kuat?

Kita harus lakukan pre-processing sehingga menjadi matriks diagonal dominan kuat dengan cara:

  1. Tukar baris, atau
  2. Tukar kolom.

Aljabar di R

Dari semua konsep aljabar yang telah dijelaskan pada bagian sebelumnya, mari kita lihat beberapa function di R-nya:

Misalkan saya definisikan \(v\) suatu vektor sebagai berikut:

v = c(2,4,-1,3)
# menghitung norm 1 dari vektor v
norm_vec_1 = function(x)sum(abs(x))
norm_vec_1(v)
## [1] 10
# menghitung norm 2 dari vektor v
norm_vec_2 = function(x)sqrt(sum(abs(x)^2))
norm_vec_2(v)
## [1] 5.477226
# menghitung norm infinity dari vektor v
norm_vec_inf = function(x)max(abs(x))
norm_vec_inf(v)
## [1] 4

Misalkan saya definisikan matriks \(A\) sebagai berikut:

A = matrix(c(2,4,-1,3,1,5,-2,3,-1),ncol = 3)
A
##      [,1] [,2] [,3]
## [1,]    2    3   -2
## [2,]    4    1    3
## [3,]   -1    5   -1
# transpose matriks
t(A)
##      [,1] [,2] [,3]
## [1,]    2    4   -1
## [2,]    3    1    5
## [3,]   -2    3   -1
# inverse matriks
matlib::inv(A)
##             [,1]       [,2]       [,3]
## [1,]  0.22535211 0.09859155 -0.1549296
## [2,] -0.01408451 0.05633803  0.1971831
## [3,] -0.29577465 0.18309859  0.1408451
# menghitung nilai dan vektor eigen
eigen(A)
## eigen() decomposition
## $values
## [1] -5.607665  5.148415  2.459250
## 
## $vectors
##            [,1]      [,2]       [,3]
## [1,]  0.4119543 0.3651285 -0.4204609
## [2,] -0.5715723 0.7504594  0.4578471
## [3,]  0.7096469 0.5509010  0.7833190
# perkalian matriks
A %*% matlib::inv(A) %>% round()
##      [,1] [,2] [,3]
## [1,]    1    0    0
## [2,]    0    1    0
## [3,]    0    0    1
# menghitung norm 1 dari matriks A
norm(A,"1")
## [1] 9
# menghitung norm 2 dari matriks A
norm(A,"2")
## [1] 6.161479
# menghitung norm infinity dari matriks A
norm(A,"i")
## [1] 8
# menghitung rho
rho = function(matriks){
  ei = eigen(matriks)
  ei = max(abs(ei$values))
  return(ei)
}
rho(A)
## [1] 5.607665
# norm 2 juga bisa dihitung dengan cara
rho(t(A) %*% A) %>% sqrt()
## [1] 6.161479

Key Take Points Materi Aljabar Linear

Perhatikan betul teorema kekonvergenan matriks dan bagaimana cara menghitung \(\rho\).

Demikian refreshment materi aljabar linear. Aplikasinya pada analisa numerik akan saya tuliskan di posts selanjutnya.

Find me at my personal blog ikanx101.com.