Bab 20

Sinyal & Metode Numerik

Bab 19 membawa kita ke garda terdepan industri sains data lewat visualisasi reduksi dimensi analisis komponen utama. Bab 20 bertindak sebagai menara penutup paripurna dari seluruh rangkaian kurikulum buku ini dengan memadukan aljabar linear terapan langsung ke dalam dunia pemrosesan sinyal digital serta analisis galat algoritma iteratif. Kita akan mempelajari keagungan struktur kompleks Transformasi Fourier Diskrit (DFT), menguasai mekanisme filtrasi frekuensi via aljabar konvolusi, serta menguji performa konvergensi metode Jacobi dan Gauss-Seidel. Terakhir, kita akan menutup lembar perkuliahan dengan membedah bilangan kondisi (condition number) untuk mengunci batas galat komputasi absolut dari sebarang sistem komputer di alam semesta.

20.1 Transformasi Fourier Diskrit (DFT) & Matriks F

Dalam bidang teknik elektro dan pemrosesan sinyal, sebuah data rekaman suara atau gelombang elektromagnetik direkam dalam bentuk rangkaian sampel diskrit berbasis waktu. Untuk menganalisis kandungan frekuensi internal dari sinyal tersebut (misalnya memisahkan suara vokal manusia dari gangguan bising latar belakang), kita harus memindahkan domain data dari domain waktu menuju domain frekuensi.

Prosedur perpindahan domain abstrak ini diselesaikan secara instan menggunakan operator linear khusus yang disebut sebagai **Matriks Transformasi Fourier Diskrit (Matriks Fourier, $F_n$)**.

Definisi 20.1 — Matriks Fourier Diskrit ($F_n$)

Misalkan $n$ menyatakan jumlah total sampel diskrit data yang diuji. Kita definisikan konstanta bilangan kompleks primitif \(\omega\) (baca: omega) yang bertindak sebagai akar satuan ke-$n$ (primitive $n$-th root of unity) berdasarkan rumus identitas Euler:

\[ \omega = e^{-\frac{2\pi i}{n}} = \cos\left(\frac{2\pi}{n}\right) - i \sin\left(\frac{2\pi}{n}\right) \]

Matriks Fourier $F_n$ berukuran $n \times n$ dikonstruksi secara simetris dengan memangkatkan konstanta primitif tersebut berdasarkan jalinan produk indeks baris dan kolom, memuat susunan koordinat entri:

\[ F_n = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{n-1} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(n-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)(n-1)} \end{bmatrix} \]

Di mana baris dan kolom dihitung menggunakan konvensi indeks basis nol (\(0, 1, \ldots, n-1\)).

Sifat aljabar dari matriks Fourier kompleks $F_n$ ini sangatlah luar biasa. Jika kita mengalikan matriks $F_n$ dengan matriks konjugat transposenya sendiri (\(F_n^*\) atau \(F_n^H\)), hasil perkalian akan meluncur runtuh menjadi matriks identitas yang telah diskalakan: **$F_n^H F_n = n I_n$**.

Hubungan ini membuktikan bahwa matriks Fourier sejatinya merupakan **matriks ortogonal kompleks (matriks uniter)** setelah disesuaikan dengan skalar pembagi \(\frac{1}{\sqrt{n}}\). Konsekuensinya, proses transformasi balik dari domain frekuensi menuju domain waktu (Inverse DFT) dijamin selalu eksis dan stabil secara mutlak tanpa prapemrosesan invers yang lambat.

Contoh 20.1 — Konstruksi Matriks Fourier Sinyal Empat Sampel Diskrit ($F_4$)

Konstruksikan susunan entri matriks Fourier $F_4$ berukuran $4 \times 4$ secara utuh, dan sederhanakan entri kompleks internalnya menggunakan nilai imajiner murni.

Penyelesaian Analitis:

Langkah 1: Menghitung Nilai Konstanta Primitif \(\omega\) untuk Ordo \(n = 4\)

Substitusikan nilai dimensi ke dalam rumusan rumus Euler dasar:

\[ \omega = e^{-\frac{2\pi i}{4}} = e^{-\frac{\pi i}{2}} = \cos\left(-\frac{\pi}{2}\right) + i \sin\left(-\frac{\pi}{2}\right) = 0 + i(-1) = -i \]

Langkah 2: Menghitung Nilai Pangkat Berantai Variabel \(\omega\)

Evaluasi nilai perpangkatan siklis dari bilangan imajiner di atas:

  • \(\omega^2 = (-i)^2 = -1\)
  • \(\omega^3 = (-i)^3 = (-i)^2 \cdot (-i) = (-1)(-i) = i\)
  • \(\omega^4 = (-i)^4 = 1\), \(\;\omega^6 = \omega^4 \cdot \omega^2 = -1\), \(\;\omega^9 = \omega^8 \cdot \omega = 1 \cdot (-i) = -i\)

Langkah 3: Pemetaan Entri Komponen ke dalam Blok Matriks $F_4$

Susun seluruh hasil penyederhanaan pangkat bilangan kompleks di atas mengikuti format struktur Definisi 20.1:

\[ F_4 = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & \omega & \omega^2 & \omega^3 \\ 1 & \omega^2 & \omega^4 & \omega^6 \\ 1 & \omega^3 & \omega^6 & \omega^9 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \end{bmatrix} \]

Kesimpulan: Matriks transformasi Fourier diskrit berordo empat berhasil dikunci secara sempurna $\checkmark$. Arsitektur blok uniter ini merupakan motor penggerak utama di balik pemrosesan kompresi file audio digital skala industri.

Contoh 20.2 — Verifikasi Unitaritas Matriks Fourier $F_2$

Konstruksikan $F_2$ dan buktikan secara eksplisit bahwa $Q = \frac{1}{\sqrt{2}} F_2$ memenuhi $Q^H Q = I_2$.

Penyelesaian Analitis:

Langkah 1: Konstruksi $F_2$

\[ \omega = e^{-\pi i} = \cos(-\pi) + i\sin(-\pi) = -1 \]
\[ F_2 = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \]

Langkah 2: Verifikasi $Q^H Q = I_2$

Karena seluruh entri $F_2$ bersifat riil, konjugat transpose sama dengan transpose biasa: $F_2^H = F_2^T = F_2$ (matriks simetris). Oleh karena itu:

\[ Q^H Q = \left(\frac{1}{\sqrt{2}} F_2^T\right)\!\left(\frac{1}{\sqrt{2}} F_2\right) = \frac{1}{2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \]
\[ = \frac{1}{2}\begin{bmatrix} 1+1 & 1-1 \\ 1-1 & 1+1 \end{bmatrix} = \frac{1}{2}\begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} = I_2 \quad \checkmark \]

Kesimpulan: $F_2$ yang ternormalisasi terbukti uniter. Catatan menarik: $F_2$ identik dengan matriks Hadamard $H_2$ — menunjukkan hubungan mendalam antara analisis Fourier dan teori kode koreksi galat $\checkmark$.

20.2 Aljabar Konvolusi & Filtering Sinyal

Mengubah domain data ke dalam bentuk frekuensi via matriks Fourier hanyalah langkah prapemrosesan awal. Di dalam pemrosesan sinyal digital dan visi komputer, aplikasi riil yang paling sering dieksekusi adalah **pemfilteran sinyal (signal filtering)**—seperti memotong frekuensi bising tinggi atau menonjolkan fitur tepi pada citra digital. Operasi interaksi ini dimodelkan melalui kalkulus diskrit bernama konvolusi.

Definisi 20.2 — Konvolusi Sirkular (Circular Convolution)

Misalkan $\mathbf{x} = \begin{bmatrix} x_0 & x_1 & \cdots & x_{n-1} \end{bmatrix}^T$ bertindak sebagai vektor input sinyal diskrit, dan $\mathbf{h} = \begin{bmatrix} h_0 & h_1 & \cdots & h_{n-1} \end{bmatrix}^T$ bertindak sebagai vektor koefisien filter (kernel). Operasi konvolusi sirkular, dinotasikan dengan simbol bintang dalam lingkaran $\mathbf{y} = \mathbf{h} \circledast \mathbf{x}$, didefinisikan secara aljabar sebagai urutan perkalian pergeseran siklis:

\[ y_k = \sum_{j=0}^{n-1} h_{(k-j) \pmod n} \cdot x_j \]

Menghitung pergeseran modulo indeks secara manual satu demi satu sangat lambat dan melelahkan. Aljabar linear menyederhanakan mekanika diskrit ini dengan merangkum vektor filter $\mathbf{h}$ ke dalam susunan matriks persegi khusus bernama Matriks Sirkulan (Circulant Matrix, $C$):

\[ C(\mathbf{h}) = \begin{bmatrix} h_0 & h_{n-1} & h_{n-2} & \cdots & h_1 \\ h_1 & h_0 & h_{n-1} & \cdots & h_2 \\ h_2 & h_1 & h_0 & \cdots & h_3 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ h_{n-1} & h_{n-2} & h_{n-3} & \cdots & h_0 \end{bmatrix} \]

Dengan menyusun operator sirkulan tersebut, proses filtrasi sinyal dapat dieksekusi sebagai aksi perkalian matriks-vektor linear standar dari arah kiri: $\mathbf{y} = C(\mathbf{h})\,\mathbf{x}$.

Teorema 20.1 — Teorema Konvolusi Diskrit (Discrete Convolution Theorem)

Matriks Fourier $F_n$ bertindak sebagai operator universal yang selalu berhasil **mendiagonalkan sebarang matriks sirkulan $C$** apa pun. Konsekuensinya, operasi konvolusi di domain waktu berubah secara ekuivalen menjadi operasi **perkalian titik entri-per-entri (Hadamard product)** biasa di domain frekuensi:

\[ F_n (\mathbf{h} \circledast \mathbf{x}) = (F_n \mathbf{h}) \odot (F_n \mathbf{x}) \]

Di mana lambang $\odot$ merepresentasikan operasi perkalian elemen-per-elemen secara langsung tanpa penjumlahan silang.

Contoh 20.3 — Konvolusi Sirkular via Matriks Sirkulan dan Verifikasi Teorema Konvolusi

Diberikan vektor filter (kernel) dan vektor sinyal input berikut:

\[ \mathbf{h} = \begin{bmatrix} 1 \\ -1 \\ 0 \\ 0 \end{bmatrix}, \qquad \mathbf{x} = \begin{bmatrix} 3 \\ 1 \\ 4 \\ 2 \end{bmatrix} \]

(a) Hitung $\mathbf{y} = \mathbf{h} \circledast \mathbf{x}$ melalui matriks sirkulan $C(\mathbf{h})$.
(b) Verifikasi hasilnya melalui rumus konvolusi langsung.
(c) Verifikasi Teorema 20.1 menggunakan matriks $F_4$ dari Contoh 20.1.

Penyelesaian Analitis:

Bagian (a): Konstruksi Matriks Sirkulan dan Perkalian

Susun matriks sirkulan dari $\mathbf{h} = [h_0, h_1, h_2, h_3]^T = [1, -1, 0, 0]^T$:

\[ C(\mathbf{h}) = \begin{bmatrix} 1 & 0 & 0 & -1 \\ -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{bmatrix} \]

Filter ini merupakan backward difference filter yang mendeteksi perubahan tingkat sinyal (deteksi tepi). Eksekusi perkalian:

\[ \mathbf{y} = C(\mathbf{h})\,\mathbf{x} = \begin{bmatrix} 1 & 0 & 0 & -1 \\ -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{bmatrix}\begin{bmatrix} 3 \\ 1 \\ 4 \\ 2 \end{bmatrix} = \begin{bmatrix} 3 - 2 \\ -3 + 1 \\ -1 + 4 \\ -4 + 2 \end{bmatrix} = \begin{bmatrix} 1 \\ -2 \\ 3 \\ -2 \end{bmatrix} \]

Bagian (b): Verifikasi via Rumus Konvolusi Langsung

\begin{aligned} y_0 &= h_0 x_0 + h_3 x_1 + h_2 x_2 + h_1 x_3 = 1(3) + 0(1) + 0(4) + (-1)(2) = 1 \;\checkmark \\ y_1 &= h_1 x_0 + h_0 x_1 + h_3 x_2 + h_2 x_3 = (-1)(3) + 1(1) + 0(4) + 0(2) = -2 \;\checkmark \\ y_2 &= h_2 x_0 + h_1 x_1 + h_0 x_2 + h_3 x_3 = 0(3) + (-1)(1) + 1(4) + 0(2) = 3 \;\checkmark \\ y_3 &= h_3 x_0 + h_2 x_1 + h_1 x_2 + h_0 x_3 = 0(3) + 0(1) + (-1)(4) + 1(2) = -2 \;\checkmark \end{aligned}

Bagian (c): Verifikasi Teorema Konvolusi via $F_4$

Langkah i: Hitung DFT kedua vektor:

\[ F_4 \mathbf{h} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \end{bmatrix}\begin{bmatrix} 1 \\ -1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 1+i \\ 2 \\ 1-i \end{bmatrix} \]
\[ F_4 \mathbf{x} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \end{bmatrix}\begin{bmatrix} 3 \\ 1 \\ 4 \\ 2 \end{bmatrix} = \begin{bmatrix} 10 \\ -1+i \\ 4 \\ -1-i \end{bmatrix} \]

Langkah ii: Perkalian Hadamard (entri-per-entri):

\[ (F_4 \mathbf{h}) \odot (F_4 \mathbf{x}) = \begin{bmatrix} 0 \\ (1{+}i)(-1{+}i) \\ 2 \cdot 4 \\ (1{-}i)(-1{-}i) \end{bmatrix} \]

Sub-hitungan kompleks: $(1+i)(-1+i) = -1+i-i+i^2 = -2$ dan $(1-i)(-1-i) = -1-i+i+i^2 = -2$, sehingga:

\[ (F_4 \mathbf{h}) \odot (F_4 \mathbf{x}) = \begin{bmatrix} 0 \\ -2 \\ 8 \\ -2 \end{bmatrix} \]

Langkah iii: Inverse DFT — kalikan dengan $\frac{1}{4}F_4^H$ (konjugat transpose dari $F_4$):

\[ \mathbf{y} = \frac{1}{4}\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{bmatrix}\begin{bmatrix} 0 \\ -2 \\ 8 \\ -2 \end{bmatrix} = \frac{1}{4}\begin{bmatrix} 0-2+8-2 \\ 0-2i-8+2i \\ 0+2+8+2 \\ 0+2i-8-2i \end{bmatrix} = \frac{1}{4}\begin{bmatrix} 4 \\ -8 \\ 12 \\ -8 \end{bmatrix} = \begin{bmatrix} 1 \\ -2 \\ 3 \\ -2 \end{bmatrix} \]

Hasil IDFT persis identik dengan hasil matriks sirkulan pada Bagian (a) $\checkmark$. Teorema 20.1 terverifikasi secara eksplisit: konvolusi di domain waktu ekuivalen dengan perkalian titik di domain frekuensi.

Keunggulan Algoritma Fast Fourier Transform (FFT) Industri

Mari kita lakukan analisis efisiensi untuk melihat dampak dari Teorema 20.1. Mengeksekusi perkalian matriks sirkulan secara langsung memakan biaya kompleksitas sebesar $\sim n^2$ operasi (Big-O $O(n^2)$).

Melalui implementasi Teorema Konvolusi bersama algoritma **Fast Fourier Transform (FFT)**, superkomputer menghitung DFT sinyal, mengalikan elemen secara instan ($\sim n$ operasi), lalu mengembalikan koordinat data via Inverse FFT. Skenario prapemrosesan berantai ini memotong total biaya komputasi secara radikal meluncur turun menuju tingkat **\(O(n \log n)\)**. Kecepatan kilat inilah yang mengizinkan perangkat telepon seluler pintar Anda mampu memfilter panggilan video streaming beresolusi tinggi secara real-time.

20.3 Metode Iteratif: Jacobi & Gauss-Seidel

Pada Bab 2 dan Bab 4, kita menyelesaikan sistem persamaan linear $A\mathbf{x} = \mathbf{b}$ menggunakan metode eliminasi langsung seperti eliminasi Gauss-Jordan atau Faktorisasi LU. Metode-metode langsung tersebut sangat tangguh untuk matriks berukuran kecil hingga sedang. Namun, ketika kita menghadapi matriks masif berukuran raksasa dalam simulasi pemodelan cuaca atau dinamika fluida ($n > 10^6$), biaya komputasi langsung sebesar $\sim \frac{2}{3}n^3$ akan langsung memboroskan memori komputer.

Untuk menghemat siklus kerja prosesor, kita beralih ke Metode Iteratif. Metode ini bekerja dengan cara menebak sebuah solusi awal, kemudian melakukan perbaikan nilai elemen secara berulang-ulang hingga barisan solusi tersebut konvergen mendekati nilai eksak aslinya.

20.3.1 Formulasi Pemecahan Matriks (Matrix Splitting)

Untuk menurunkan rumusan Jacobi dan Gauss-Seidel secara matematis, kita memecah (split) struktur matriks koefisien $A$ menjadi tiga bagian komponen matriks segitiga, ditulis secara aljabar: $A = D + L + U$. Harap dicatat dengan cermat: komponen pembentuk di sini didefinisikan secara berbeda dari bab-bab sebelumnya:

  • Matriks $D$ (Diagonal): Matriks diagonal murni yang hanya menampung entri diagonal utama milik matriks $A$.
  • Matriks $L$ (Strictly Lower Triangular): Matriks segitiga bawah murni yang entri diagonal utama dan area atasnya bersih bernilai nol.
  • Matriks $U$ (Strictly Upper Triangular): Matriks segitiga atas murni yang entri diagonal utama dan area bawahnya bersih bernilai nol.
Definisi 20.3 — Skema Iterasi Metode Jacobi

Dalam Metode Jacobi, kita mengisolasi seluruh entri diagonal utama ke ruas kiri. Persamaan iterasi langkah ke-$(k+1)$ disusun menggunakan barisan komponen langkah ke-$k$ sebelumnya secara eksklusif:

\[ D \mathbf{x}^{(k+1)} = -(L + U)\mathbf{x}^{(k)} + \mathbf{b} \quad \implies \quad \mathbf{x}^{(k+1)} = D^{-1}\big( \mathbf{b} - (L + U)\mathbf{x}^{(k)} \big) \]
Definisi 20.4 — Skema Iterasi Metode Gauss-Seidel

Dalam Metode Gauss-Seidel, kita langsung **mengupdate dan menggunakan nilai elemen terbaru** segera setelah nilai tersebut berhasil dihitung pada langkah aktif berjalan, tanpa menunggu siklus iterasi berikutnya selesai. Formulasi aljabar matriksnya dituliskan sebagai:

\[ (D + L) \mathbf{x}^{(k+1)} = -U \mathbf{x}^{(k)} + \mathbf{b} \quad \implies \quad \mathbf{x}^{(k+1)} = (D + L)^{-1}\big( \mathbf{b} - U \mathbf{x}^{(k)} \big) \]

20.3.2 Kriteria Konvergensi Mutlak

Apakah barisan iterasi numerik tersebut selalu dijamin pasti konvergen menuju solusi eksak dari sebarang matriks koefisien $A$? Jaminan teoretis ini dikunci secara universal melalui kriteria dominasi diagonal.

Teorema 20.2 — Teorema Dominasi Diagonal Ketat (Strictly Diagonally Dominant)

Sebuah matriks persegi $A$ berukuran $n \times n$ diklasifikasikan bersifat dominan diagonal ketat (SDD) jika nilai absolut dari entri diagonal utama pada setiap baris terbukti selalu lebih besar daripada jumlah nilai absolut seluruh entri off-diagonal lainnya sepanjang baris tersebut:

\[ |a_{ii}| \;>\; \sum_{j \neq i} |a_{ij}| \qquad \text{untuk setiap baris} \quad i = 1, 2, \ldots, n \]

Jaminan Konvergensi: Jika matriks koefisien $A$ memenuhi kriteria SDD, maka metode Jacobi dan Gauss-Seidel dijamin **pasti konvergen secara mutlak** menuju solusi eksak, sepenuhnya independen dari pilihan tebakan awal $\mathbf{x}^{(0)}$.

Contoh 20.4 — Perbandingan Konvergensi Jacobi vs Gauss-Seidel

Diberikan sistem persamaan linear persegi berordo $2 \times 2$ berikut:

\[ \begin{bmatrix} 4 & 1 \\ 1 & 5 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 7 \\ -4 \end{bmatrix} \]

Verifikasikan status SDD, kemudian jalankan dua iterasi pertama ($\mathbf{x}^{(1)}$ dan $\mathbf{x}^{(2)}$) untuk kedua metode dari $\mathbf{x}^{(0)} = \begin{bmatrix} 0 & 0 \end{bmatrix}^T$, dan bandingkan kecepatan konvergensi terhadap solusi eksak.

Penyelesaian Analitis:

Langkah 0: Verifikasi SDD dan Solusi Eksak

Baris 1: $|4| > |1| = 1$ $\checkmark$. Baris 2: $|5| > |1| = 1$ $\checkmark$. Matriks bersifat SDD.

Solusi eksak (via Cramer): $\Delta = 20 - 1 = 19$, $\Delta_1 = 35 - (-4) = 39$, $\Delta_2 = -16 - 7 = -23$.

\[ \mathbf{x}^* = \begin{bmatrix} 39/19 \\ -23/19 \end{bmatrix} \approx \begin{bmatrix} 2{,}0526 \\ -1{,}2105 \end{bmatrix} \]

Langkah 1: Persamaan Skalar Iterasi

Jacobi (seluruh komponen langkah ke-$k$):

\[ x_1^{(k+1)} = \frac{7 - x_2^{(k)}}{4}, \qquad x_2^{(k+1)} = \frac{-4 - x_1^{(k)}}{5} \]

Gauss-Seidel (menggunakan $x_1$ terbaru untuk $x_2$):

\[ x_1^{(k+1)} = \frac{7 - x_2^{(k)}}{4}, \qquad x_2^{(k+1)} = \frac{-4 - x_1^{(k+1)}}{5} \]

Langkah 2: Eksekusi Iterasi

Iterasi Jacobi $\mathbf{x}^{(k)}$ Gauss-Seidel $\mathbf{x}^{(k)}$
$k = 0$ $\begin{bmatrix} 0 \\ 0 \end{bmatrix}$ $\begin{bmatrix} 0 \\ 0 \end{bmatrix}$
$k = 1$ $\begin{bmatrix} \frac{7}{4} \\[6pt] -\frac{4}{5} \end{bmatrix} \approx \begin{bmatrix} 1{,}75 \\[6pt] -0{,}80 \end{bmatrix}$ $\begin{bmatrix} \frac{7}{4} \\[6pt] -\frac{23}{20} \end{bmatrix} \approx \begin{bmatrix} 1{,}75 \\[6pt] -1{,}15 \end{bmatrix}$
$k = 2$ $\begin{bmatrix} \frac{39}{20} \\[6pt] -\frac{23}{20} \end{bmatrix} \approx \begin{bmatrix} 1{,}95 \\[6pt] -1{,}15 \end{bmatrix}$ $\begin{bmatrix} \frac{163}{80} \\[6pt] -\frac{483}{400} \end{bmatrix} \approx \begin{bmatrix} 2{,}0375 \\[6pt] -1{,}2075 \end{bmatrix}$

Analisis Perbandingan:

Metode $\|\mathbf{x}^{(1)} - \mathbf{x}^*\|_\infty$ $\|\mathbf{x}^{(2)} - \mathbf{x}^*\|_\infty$
Jacobi $0{,}411$ $0{,}103$
Gauss-Seidel $0{,}303$ $0{,}015$

Pada iterasi pertama, Gauss-Seidel mengungguli Jacobi (galat $0{,}303$ vs $0{,}411$). Pada iterasi kedua, keunggulan Gauss-Seidel menjadi sangat dramatis — galatnya menyusut hingga $0{,}015$, sekitar tujuh kali lebih kecil dibandingkan Jacobi ($0{,}103$). Pola ini konsisten dengan teori: Gauss-Seidel umumnya konvergen sekitar dua kali lebih cepat dari Jacobi karena memanfaatkan informasi terbaru secara langsung, meskipun keduanya dijamin konvergen untuk matriks SDD $\checkmark$.

20.4 Metode Power untuk Aproksimasi Nilai Eigen

Pada Bab 13, kita mengulas algoritma QR sebagai standar utama untuk menghitung seluruh spektrum nilai eigen secara simultan. Namun, dalam aplikasi rekayasa tertentu—seperti penentuan kecepatan kritis getaran jembatan atau penghitungan algoritma perankingan halaman internet (Google PageRank)—kita hanya membutuhkan satu buah nilai eigen terbesar bersama dengan pasangan vektor eigennya.

Untuk kebutuhan khusus tersebut, kita mengimplementasikan Metode Power (Power Method). Algoritma iteratif ini bekerja sangat cepat dengan memanfaatkan efek dominasi eksponensial dari nilai eigen terbesar saat sebuah vektor dikalikan secara berulang-ulang.

Definisi 20.5 — Prosedur Barisan Iterasi Metode Power

Misalkan $A$ adalah sebuah matriks persegi berukuran $n \times n$ yang memuat nilai eigen dominan tunggal, memenuhi urutan batas $|\lambda_1| > |\lambda_2| \geq \ldots \geq |\lambda_n|$. Rangkaian barisan vektor tak-nol dikonstruksi secara induktif melalui aturan tahapan berikut dari sebuah tebakan awal $\mathbf{x}^{(0)}$ untuk setiap nilai langkah $k = 0, 1, 2, \ldots$:

  1. Hitung perkalian matriks-vektor aktif:
    \[ \mathbf{y}^{(k+1)} = A \mathbf{x}^{(k)} \]
  2. Tentukan konstanta skalar penormalisasi $\mu_{k+1}$ yang nilainya diambil dari entri komponen yang memuat nilai absolut terbesar di dalam elemen vektor $\mathbf{y}^{(k+1)}$.
  3. Konstruksikan vektor satuan untuk langkah berikutnya melalui pembagian faktor skala:
    \[ \mathbf{x}^{(k+1)} = \frac{1}{\mu_{k+1}} \mathbf{y}^{(k+1)} \]

Seiring membesarnya indeks iterasi ($k \to \infty$), nilai skalar $\mu_k$ akan stabil konvergen mendekati nilai eigen dominan asli ($\lambda_1$), dan vektor $\mathbf{x}_k$ akan terkunci bertindak sebagai vektor eigen pasangannya.

Contoh 20.5 — Konvergensi Metode Power pada Matriks $2 \times 2$

Aplikasikan Metode Power sebanyak empat iterasi pada matriks berikut:

\[ A = \begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix} \]

dengan tebakan awal $\mathbf{x}^{(0)} = \begin{bmatrix} 1 & 0 \end{bmatrix}^T$. Identifikasi nilai eigen dominan dan bandingkan hasil aproksimasi dengan nilai eksak.

Penyelesaian Analitis:

Langkah 0: Identifikasi Nilai Eigen Eksak (untuk verifikasi)

\[ \det(A - \lambda I) = (4 - \lambda)(3 - \lambda) - 2 = \lambda^2 - 7\lambda + 10 = (\lambda - 5)(\lambda - 2) = 0 \]

Nilai eigen: $\lambda_1 = 5$ (dominan, karena $|5| > |2|$), $\lambda_2 = 2$. Rasio konvergensi teoretis: $|\lambda_2/\lambda_1| = 2/5 = 0{,}4$ — konvergensi cepat.

Vektor eigen untuk $\lambda_1 = 5$: $(A - 5I)\mathbf{v} = \begin{bmatrix} -1 & 1 \\ 2 & -2 \end{bmatrix}\mathbf{v} = \mathbf{0} \implies \mathbf{v}_1 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}^T$ (setelah normalisasi: $\begin{bmatrix} 1/\sqrt{2} & 1/\sqrt{2} \end{bmatrix}^T$).

Langkah 1–4: Eksekusi Iterasi Power Method

$k$ $\mathbf{y}^{(k+1)} = A\mathbf{x}^{(k)}$ $\mu_{k+1}$ $\mathbf{x}^{(k+1)}$
$0$ $A\begin{bmatrix}1\\0\end{bmatrix} = \begin{bmatrix}4\\2\end{bmatrix}$ $4$ $\begin{bmatrix}1\\1/2\end{bmatrix}$
$1$ $A\begin{bmatrix}1\\1/2\end{bmatrix} = \begin{bmatrix}9/2\\7/2\end{bmatrix}$ $9/2 \approx 4{,}5$ $\begin{bmatrix}1\\7/9\end{bmatrix} \approx \begin{bmatrix}1\\0{,}778\end{bmatrix}$
$2$ $A\begin{bmatrix}1\\7/9\end{bmatrix} = \begin{bmatrix}43/9\\39/9\end{bmatrix}$ $43/9 \approx 4{,}778$ $\begin{bmatrix}1\\39/43\end{bmatrix} \approx \begin{bmatrix}1\\0{,}907\end{bmatrix}$
$3$ $A\begin{bmatrix}1\\39/43\end{bmatrix} = \begin{bmatrix}211/43\\203/43\end{bmatrix}$ $211/43 \approx 4{,}907$ $\begin{bmatrix}1\\203/211\end{bmatrix} \approx \begin{bmatrix}1\\0{,}962\end{bmatrix}$

Analisis Konvergensi:

$k$ $0$ $1$ $2$ $3$
$\mu_{k+1}$ $4{,}000$ $4{,}500$ $4{,}778$ $4{,}907$
$|\mu_{k+1} - 5|$ $1{,}000$ $0{,}500$ $0{,}222$ $0{,}093$

Setiap iterasi memangkas galat dengan faktor $\approx 0{,}4$, konsisten dengan prediksi rasio konvergensi $|\lambda_2/\lambda_1| = 0{,}4$. Hanya dalam 4 langkah, estimasi $\mu$ sudah berada pada $98{,}1\%$ dari nilai eigen dominan eksak. Vektor $\mathbf{x}^{(4)} \approx \begin{bmatrix} 1 & 0{,}962 \end{bmatrix}^T$ juga terlihat konvergen menuju $\begin{bmatrix} 1 & 1 \end{bmatrix}^T$ (arah vektor eigen $\lambda_1 = 5$) $\checkmark$.

20.5 Analisis Kondisi Matriks dan Kriteria Norma

Sebagai bab penutup dari seluruh rangkaian kurikulum buku ini, kita wajib melakukan analisis kritis mengenai keandalan sebuah sistem linear ketika dihadapkan pada batas limitasi penyimpanan komputer. Kita perlu tahu seberapa besar galat komputasi dapat membesar dan merusak presisi data.

20.5.1 Batasan Norma Vektor dan Norma Matriks

Sebelum kita dapat mengukur tingkat sensitivitas sebuah matriks koefisien, kita harus memperluas konsep panjang "norma" (Bab 6 dan Bab 11) dari elemen vektor menuju ke elemen operator matriks persegi.

Definisi 20.6 — Norma Matriks Alami (Induced Matrix Norm)

Misalkan $A$ adalah sebuah matriks persegi berukuran $n \times n$. **Norma Matriks** yang diinduksi secara alami oleh norma vektor didefinisikan sebagai nilai batas regangan maksimum yang dapat dihasilkan oleh operator matriks tersebut terhadap sebarang vektor satuan \(\|\mathbf{x}\| = 1\):

\[ \|A\| = \max_{\|\mathbf{x}\| = 1} \|A\mathbf{x}\| \]

Berdasarkan pilihan jenis pengujian vektor, terdapat tiga rumpun norma matriks alami yang paling sering digunakan di dalam analisis metode numerik industri:

  • Norma Kolom Maksimum (Norma-$1$, \(\|A\|_1\)): Diperoleh dengan menjumlahkan nilai absolut seluruh entri sepanjang tiap kolom lalu mengambil nilai terbesar.
  • Norma Baris Maksimum (Norma-$\infty$, \(\|A\|_\infty\)): Diperoleh dengan menjumlahkan nilai absolut seluruh entri sepanjang tiap baris lalu mengambil nilai terbesar.
  • Norma Spektral (Norma-$2$, \(\|A\|_2\)): Nilai batas atas geometris yang dihitung dari akar kuadrat nilai eigen terbesar matriks produk simetris: \(\|A\|_2 = \sqrt{\lambda_{\max}(A^T A)}\). Sesuai Bab 16, nilai ini tidak lain adalah **nilai singular terbesar (\(\sigma_1\))**.

20.5.2 Bilangan Kondisi (Condition Number)

Ketika sebuah sistem komputer dipaksa untuk menyelesaikan sistem linear persegi $A\mathbf{x} = \mathbf{b}$, sedikit saja gangguan derau data (noise) atau pembulatan digit desimal pada vektor ruas kanan \(\mathbf{b}\) dapat menyebabkan pergeseran posisi solusi final \(\mathbf{x}\). Tingkat kerentanan sistem terhadap pembesaran galat ini dikunci oleh **bilangan kondisi**.

Definisi 20.7 — Bilangan Kondisi Matriks (Condition Number)

Misalkan $A$ adalah sebuah matriks persegi invertibel berukuran $n \times n$. Bilangan Kondisi dari matriks $A$ relatif terhadap suatu kriteria norma tertentu, dinotasikan dengan simbol $\kappa(A)$ (baca: kappa A), didefinisikan sebagai hasil perkalian antara norma matriks asli dengan norma matriks inversnya:

\[ \kappa(A) = \|A\| \cdot \|A^{-1}\| \]

Nilai bilangan kondisi dijamin selalu lebih besar atau sama dengan satu (\(\kappa(A) \geq 1\)). Berdasarkan pilihan norma spektral (norma-2), rumus ini mengevaluasi rasio perbandingan nilai singular ekstrem dari Bab 16: $\kappa_2(A) = \dfrac{\sigma_{\max}}{\sigma_{\min}}$.

Berdasarkan kuantitas nilainya, sifat kestabilan matriks dikelompokkan ke dalam dua kategori industri:

  • Matriks Sehat (Well-Conditioned): Terjadi jika \(\kappa(A)\) bernilai kecil (mendekati satu). Sistem ini sangat kebal terhadap derau, menjamin akurasi solusi numerik tetap tinggi.
  • Matriks Sakit (Ill-Conditioned): Terjadi jika \(\kappa(A)\) bernilai sangat raksasa (\(\kappa \gg 1\)). Sedikit saja riak galat desimal mesin pada input data akan diamplifikasi secara liar menjadi malapetaka galat masif yang menghancurkan validitas solusi final.

20.5.3 Estimasi Batasan Galat Komputasi

Hubungan matematis yang mengikat antara galat relatif pada data ruas kanan dengan galat relatif pada solusi final dikunci secara ketat oleh hukum ketaksamaan batas bilangan kondisi.

Teorema 20.3 — Teorema Batasan Galat Relatif Absolut

Misalkan \(\mathbf{x}\) bertindak sebagai solusi eksak dari sistem \(A\mathbf{x} = \mathbf{b}\), dan \(\delta\mathbf{b}\) merepresentasikan vektor gangguan derau data input. Jika terjadi pergeseran solusi sebesar \(\delta\mathbf{x}\) sedemikian rupa sehingga memenuhi hubungan \(A(\mathbf{x} + \delta\mathbf{x}) = \mathbf{b} + \delta\mathbf{b}\), maka batas atas amplifikasi galat relatif dijamin terkunci secara absolut oleh formulasi:

\[ \frac{\|\delta\mathbf{x}\|}{\|\mathbf{x}\|} \;\leq\; \kappa(A) \cdot \frac{\|\delta\mathbf{b}\|}{\|\mathbf{b}\|} \]

Teorema 20.3 membongkar rahasia terdalam dari metode numerik: bilangan kondisi bertindak sebagai **faktor amplifikasi galat maksimal**. Jika sebuah matriks memuat nilai \(\kappa(A) = 10^4\), maka galat pembulatan mesin sekecil $10^{-7}$ di awal dapat meledak tak terkendali menjadi galat sebesar $10^{-3}$ di akhir pengerjaan, merusak empat digit angka signifikan solusi Anda secara total.

Contoh 20.6 — Komputasi Bilangan Kondisi Tiga Norma dan Analisis Galat

Hitung bilangan kondisi matriks berikut terhadap ketiga norma alami, lalu analisis dampak galat:

\[ A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} \]

Penyelesaian Analitis:

Langkah 1: Invers Matriks

\[ A^{-1} = \frac{1}{3}\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} \]

Langkah 2: Komputasi Tiga Norma

Norma $\|A\|$ $\|A^{-1}\|$ $\kappa(A)$
$\|\cdot\|_1$ (kolom max) $\max(3, 3) = 3$ $\max(1, 1) = 1$ $3$
$\|\cdot\|_\infty$ (baris max) $\max(3, 3) = 3$ $\max(1, 1) = 1$ $3$
$\|\cdot\|_2$ (spektral) $\sigma_1 = 3$ $1/\sigma_2 = 1$ $\sigma_1/\sigma_2 = 3$

Untuk norma spektral, hitung nilai singular dari $A$:

\[ A^T A = \begin{bmatrix} 5 & 4 \\ 4 & 5 \end{bmatrix}, \qquad \det(A^T A - \lambda I) = (5-\lambda)^2 - 16 = \lambda^2 - 10\lambda + 9 = 0 \]
\[ \lambda = \frac{10 \pm \sqrt{100-36}}{2} = \frac{10 \pm 8}{2} \implies \lambda_1 = 9,\; \lambda_2 = 1 \]

Langkah 3: Analisis Dampak Galat

Ketiga norma memberikan $\kappa = 3$ — matriks ini sangat sehat. Jika data input memuat galat relatif $\frac{\|\delta\mathbf{b}\|}{\|\mathbf{b}\|} = 10^{-6}$, maka:

\[ \frac{\|\delta\mathbf{x}\|}{\|\mathbf{x}\|} \;\leq\; 3 \times 10^{-6} \]

Galat output masih pada orde $10^{-6}$ — tidak ada digit signifikan yang hilang $\checkmark$.

Perbandingan: Matriks Sakit

Bandingkan dengan $B = \operatorname{diag}(10,\; 0{,}01)$: nilai singular $\sigma_1 = 10$, $\sigma_2 = 0{,}01$, sehingga $\kappa_2(B) = 10/0{,}01 = 1000$. Galat yang sama $10^{-6}$ pada input akan meledak menjadi:

\[ \frac{\|\delta\mathbf{x}\|}{\|\mathbf{x}\|} \;\leq\; 1000 \times 10^{-6} = 10^{-3} \]

Tiga digit signifikan hilang — dari presisi 6 digit menjadi hanya 3 digit. Inilah bahaya matriks sakit yang dijelaskan oleh Teorema 20.3 $\checkmark$.

Epilog — Perspektif Aljabar Seluruh Buku Ini

Bab 20 berhasil menyatukan seluruh potongan teka-teki aljabar linear terapan yang kita bangun sejak halaman pertama Bab 1. Kita menyaksikan bagaimana konsep abstrak yang semula terasa teoritis berubah menjadi perkakas industri yang sangat perkasa.

Matriks Fourier kompleks membuktikan kekuatan uniter ruang hasil dalam (Bab 11) dalam membedah kandungan frekuensi sinyal gelombang (Contoh 20.1–20.2). Aljabar konvolusi dan matriks sirkulan mengeksploitasi struktur ruang eigen (Bab 10) untuk memotong kompleksitas pemrosesan multimedia dari $O(n^2)$ menuju $O(n \log n)$ — diverifikasi secara eksplisit pada Contoh 20.3. Di sisi numerik, perbandingan konvergensi Jacobi vs Gauss-Seidel pada Contoh 20.4 dan konvergensi Metode Power pada Contoh 20.5 mengunci kepastian bahwa algoritma iteratif sekuensial mampu mereduksi beban memori superkomputer secara masif. Akhirnya, komputasi tiga norma bilangan kondisi pada Contoh 20.6 dan dekonstruksi nilai singular ekstrem mengembalikan kesadaran kita pada realitas limitasi mesin: bahwa kestabilan struktur data jauh lebih penting daripada sekadar kecepatan kalkulasi.

Dari eliminasi baris linear Bab 2, visualisasi determinan Bab 5, abstraksi subruang Bab 7, hingga unifikasi SVD Bab 16 dan bilangan kondisi Bab 20—aljabar linear bukan lagi sekadar ilmu hitung kurung siku, melainkan sebuah bahasa universal tunggal yang menggerakkan seluruh arsitektur teknologi komputer, kecerdasan buatan, dan simulasi rekayasa modern di muka bumi ini. Perkuliahan komprehensif Anda resmi selesai secara paripurna.

Latihan Evaluasi Akhir Bab 20
  1. Sebuah sistem pemrosesan sinyal digital melakukan pemetaan sampel diskrit berordo dua menggunakan konstanta akar satuan Euler primitif \(\omega = e^{-\pi i}\). Konstruksikan susunan entri matriks Fourier $F_2$ berukuran $2 \times 2$ secara utuh, dan sederhanakan seluruh entri bilangan kompleks internalnya menggunakan bilangan bulat murni.
  2. Diberikan sebuah sistem persamaan linear persegi berordo $2 \times 2$ sebagai berikut:
    \[ \begin{bmatrix} 5 & -2 \\ 1 & 4 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 3 \\ 9 \end{bmatrix} \]
    • (a) Buktikan secara formal bahwa matriks koefisien di atas memenuhi kriteria Teorema Dominasi Diagonal Ketat (SDD).
    • (b) Jalankan satu siklus langkah pertama (\(k=0\)) untuk menghitung vektor pendekatan numerik \(\mathbf{x}^{(1)}\) via skema iterasi metode Jacobi, menggunakan tebakan titik awal nol \(\mathbf{x}^{(0)} = \begin{bmatrix} 0 & 0 \end{bmatrix}^T\).
    • (c) Ulangi langkah (b) menggunakan metode Gauss-Seidel. Bandingkan kedua hasil dan tentukan mana yang lebih dekat ke solusi eksak.
  3. Misalkan sebuah operator matriks kuadratis berukuran $2 \times 2$ didefinisikan sebagai $A = \begin{bmatrix} 3 & 0 \\ 0 & 1 \end{bmatrix}$. Aplikasikan prosedur berantai Metode Power (Definisi 20.5) sebanyak tepat satu kali iterasi awal (\(k=0\)) untuk mengestimasi nilai eigen dominannya, menggunakan asumsi vektor tebakan awal sebarang \(\mathbf{x}^{(0)} = \begin{bmatrix} 1 & 1 \end{bmatrix}^T\). Tentukan kuantitas nilai skalar penormalisasi \(\mu_1\) yang dihasilkan.
  4. Diberikan sebuah matriks diagonal yang mengalami sakit parah akibat ketergantungan linear semu, memuat susunan entri komponen:
    \[ A = \begin{bmatrix} 10 & 0 \\ 0 & 0{,}001 \end{bmatrix} \]
    • (a) Hitunglah nilai norma spektral matriks (\(\|A\|_2\)) dan norma spektral matriks inversnya (\(\|A^{-1}\|_2\)) memanfaatkan kriteria penentuan nilai singular ekstrem Bab 16.
    • (b) Tentukan nilai Bilangan Kondisi (\(\kappa_2(A)\)) dari matriks tersebut.
    • (c) Jika data target ruas kanan mengalami gangguan derau kecil mesin sebesar \(\frac{\|\delta\mathbf{b}\|}{\|\mathbf{b}\|} = 10^{-5}\), hitunglah estimasi batas atas pembesaran galat relatif solusi (\(\frac{\|\delta\mathbf{x}\|}{\|\mathbf{x}\|}\)) berdasarkan hukum Teorema 20.3.
  5. Soal Pemikiran Analitis Fleksibilitas Matriks Uniter: Buktikan secara formal menggunakan kombinasi manipulasi aljabar konjugat transpose matriks kompleks bahwa untuk sebarang matriks Fourier $F_n$ berukuran $n \times n$, matriks penormalisasi khusus berupa \(Q = \frac{1}{\sqrt{n}} F_n\) dijamin bertindak sebagai matriks uniter sah, memenuhi hubungan identitas ortogonalitas kompleks: \(Q^H Q = I_n\).
  6. Soal Komputasi Konvolusi: Diberikan vektor filter \(\mathbf{h} = \begin{bmatrix} 1 & 2 & 3 \end{bmatrix}^T\) dan vefor sinyal \(\mathbf{x} = \begin{bmatrix} 4 & 5 & 6 \end{bmatrix}^T\).
    • (a) Konstruksikan matriks sirkulan \(C(\mathbf{h})\) berukuran $3 \times 3$.
    • (b) Hitung \(\mathbf{y} = C(\mathbf{h})\,\mathbf{x}\) melalui perkalian matriks-vektor.
    • (c) Verifikasi entri $y_0$ menggunakan rumus konvolusi sirkular langsung: \(y_0 = h_0 x_0 + h_2 x_1 + h_1 x_2\).
Bab sebelumnya
Analisis Data: PCA & Regresi