Bab 12

Ortogonalitas & Gram-Schmidt

Bab 11 memperluas konsep perkalian titik menjadi aksioma abstrak ruang hasil dalam, memungkinkan kita mengukur panjang dan ketegakluruan pada ruang fungsi kontinu. Bab ini memanfaatkan landasan abstrak tersebut untuk memecahkan sebuah masalah praktis yang sangat vital dalam komputasi: bagaimana membangun sistem koordinat terbaik. Kita akan mempelajari karakteristik luar biasa dari himpunan ortogonal dan ortonormal, serta menguasai algoritma Gram-Schmidt — sebuah prosedur matematis yang mampu mengubah basis acak menjadi barisan vektor yang saling tegak lurus tanpa mengubah ruang bentangan asli mereka.

12.1 Himpunan Ortogonal dan Ortonormal

Dalam ruang vektor sebarang, pemilihan basis sangat menentukan tingkat kerumitan perhitungan aljabar. Basis standar dari ruang Euclidean sangat disukai karena seluruh elemen penyusunnya saling tegak lurus dan memiliki panjang tepat satu. Pada bagian ini, kita akan memformalkan karakteristik tersebut ke dalam konsep himpunan ortogonal dan ortonormal untuk sebarang ruang hasil dalam umum.

Definisi 12.1 — Himpunan Ortogonal

Sebuah himpunan vektor $S = \{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k\}$ di dalam sebuah ruang hasil dalam $V$ dinyatakan sebagai himpunan ortogonal jika setiap pasangan vektor yang berbeda di dalam himpunan tersebut bersifat saling tegak lurus, yaitu nilai hasil dalam mereka bernilai nol:

\[ \langle\mathbf{v}_i, \mathbf{v}_j\rangle = 0 \quad \text{untuk setiap} \quad i \neq j \]

Definisi 12.2 — Himpunan Ortonormal

Sebuah himpunan vektor $S = \{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k\}$ di dalam sebuah ruang hasil dalam $V$ dinyatakan sebagai himpunan ortonormal jika himpunan tersebut merupakan himpunan ortogonal dan setiap vektor di dalamnya memiliki norma tepat satu. Karakteristik ini diringkas menggunakan notasi delta Kronecker ($\delta_{ij}$):

\[ \langle\mathbf{v}_i, \mathbf{v}_j\rangle = \delta_{ij} = \begin{cases} 1, & \text{jika } i = j \\ 0, & \text{jika } i \neq j \end{cases} \]

Teorema 12.1 — Kebebasan Linear Himpunan Ortogonal

Jika $S = \{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k\}$ adalah sebuah himpunan ortogonal yang memuat vektor-vektor tak-nol di dalam sebuah ruang hasil dalam $V$, maka himpunan $S$ dijamin pasti bersifat linear independen (bebas linear).

Bukti Teorema Kebebasan Linear Himpunan Ortogonal

Untuk membuktikan kebebasan linear, kita susun persamaan kombinasi linear homogen dan menetapkan nilainya sama dengan vektor nol:

\[ c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k = \mathbf{0} \]

Kita harus menunjukkan bahwa satu-satunya cara memenuhi persamaan di atas adalah jika seluruh konstanta skalar bernilai nol ($c_i = 0$). Ambil sebuah indeks sebarang $p$ (di mana $1 \leq p \leq k$), lalu lakukan operasi hasil dalam dengan vektor $\mathbf{v}_p$ pada kedua ruas:

\[ \langle c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k, \mathbf{v}_p \rangle = \langle \mathbf{0}, \mathbf{v}_p \rangle \]

Terapkan sifat aditif dan homogenitas ruang hasil dalam pada ruas kiri, serta properti vektor nol pada ruas kanan:

\[ c_1\langle\mathbf{v}_1, \mathbf{v}_p\rangle + c_2\langle\mathbf{v}_2, \mathbf{v}_p\rangle + \cdots + c_p\langle\mathbf{v}_p, \mathbf{v}_p\rangle + \cdots + c_k\langle\mathbf{v}_k, \mathbf{v}_p\rangle = 0 \]

Karena himpunan $S$ bersifat ortogonal, seluruh suku hasil dalam di mana $i \neq p$ menjadi nol. Persamaan menyusut menjadi:

\[ c_p\langle\mathbf{v}_p, \mathbf{v}_p\rangle = 0 \implies c_p \|\mathbf{v}_p\|^2 = 0 \]

Karena $\mathbf{v}_p$ dikondisikan sebagai vektor tak-nol, maka $\|\mathbf{v}_p\|^2 \neq 0$. Kondisi ini memaksa $c_p = 0$. Karena indeks $p$ dipilih secara sebarang, maka seluruh konstanta skalar terbukti bernilai nol ($c_1 = c_2 = \ldots = c_k = 0$). Himpunan $S$ sah dinyatakan bebas linear. ∎

Contoh 12.1 — Verifikasi Himpunan Ortonormal di $\mathbb{R}^3$

Tunjukkan secara komputasi bahwa himpunan vektor $S = \{\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3\}$ berikut bertindak sebagai himpunan ortonormal di dalam ruang hasil dalam Euclidean standar:

\[ \mathbf{u}_1 = \begin{bmatrix} \frac{2}{3} \\[4pt] \frac{2}{3} \\[4pt] \frac{1}{3} \end{bmatrix}, \qquad \mathbf{u}_2 = \begin{bmatrix} -\frac{2}{3} \\[4pt] \frac{1}{3} \\[4pt] \frac{2}{3} \end{bmatrix}, \qquad \mathbf{u}_3 = \begin{bmatrix} \frac{1}{3} \\[4pt] -\frac{2}{3} \\[4pt] \frac{2}{3} \end{bmatrix} \]

Penyelesaian:

Uji interaksi hasil kali dalam berpasangan untuk memverifikasi sifat ortogonalitas:

$\langle\mathbf{u}_1, \mathbf{u}_2\rangle = \left(\frac{2}{3}\right)\left(-\frac{2}{3}\right) + \left(\frac{2}{3}\right)\left(\frac{1}{3}\right) + \left(\frac{1}{3}\right)\left(\frac{2}{3}\right) = -\frac{4}{9} + \frac{2}{9} + \frac{2}{9} = 0 \quad (\checkmark)$
$\langle\mathbf{u}_1, \mathbf{u}_3\rangle = \left(\frac{2}{3}\right)\left(\frac{1}{3}\right) + \left(\frac{2}{3}\right)\left(-\frac{2}{3}\right) + \left(\frac{1}{3}\right)\left(\frac{2}{3}\right) = \frac{2}{9} - \frac{4}{9} + \frac{2}{9} = 0 \quad (\checkmark)$
$\langle\mathbf{u}_2, \mathbf{u}_3\rangle = \left(-\frac{2}{3}\right)\left(\frac{1}{3}\right) + \left(\frac{1}{3}\right)\left(-\frac{2}{3}\right) + \left(\frac{2}{3}\right)\left(\frac{2}{3}\right) = -\frac{2}{9} - \frac{2}{9} + \frac{4}{9} = 0 \quad (\checkmark)$

Periksa norma dari masing-masing vektor:

$\|\mathbf{u}_1\|^2 = \left(\frac{2}{3}\right)^2 + \left(\frac{2}{3}\right)^2 + \left(\frac{1}{3}\right)^2 = \frac{4}{9} + \frac{4}{9} + \frac{1}{9} = 1 \implies \|\mathbf{u}_1\| = 1 \quad (\checkmark)$
$\|\mathbf{u}_2\|^2 = \left(-\frac{2}{3}\right)^2 + \left(\frac{1}{3}\right)^2 + \left(\frac{2}{3}\right)^2 = \frac{4}{9} + \frac{1}{9} + \frac{4}{9} = 1 \implies \|\mathbf{u}_2\| = 1 \quad (\checkmark)$
$\|\mathbf{u}_3\|^2 = \left(\frac{1}{3}\right)^2 + \left(-\frac{2}{3}\right)^2 + \left(\frac{2}{3}\right)^2 = \frac{1}{9} + \frac{4}{9} + \frac{4}{9} = 1 \implies \|\mathbf{u}_3\| = 1 \quad (\checkmark)$

Kesimpulan: Karena seluruh interaksi antar-vektor menghasilkan nol dan norma setiap elemen bernilai satu, maka himpunan $S$ terbukti sah sebagai himpunan ortonormal. Berdasarkan Teorema 12.1, himpunan ini otomatis bertindak sebagai basis ortonormal bagi $\mathbb{R}^3$. ∎

Contoh 12.2 — Himpunan Ortogonal Tapi Bukan Ortonormal

Perhatikan himpunan vektor berikut di $\mathbb{R}^3$:

\[ \mathbf{v}_1 = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}, \qquad \mathbf{v}_2 = \begin{bmatrix} -1 \\ 1 \\ 0 \end{bmatrix}, \qquad \mathbf{v}_3 = \begin{bmatrix} 0 \\ 0 \\ 3 \end{bmatrix} \]

Tentukan apakah himpunan ini ortogonal, ortonormal, atau keduanya tidak.

Penyelesaian:

Tahap 1 — Uji ortogonalitas (hasil kali dalam berpasangan):

$\langle\mathbf{v}_1, \mathbf{v}_2\rangle = (1)(-1) + (1)(1) + (0)(0) = -1 + 1 + 0 = 0 \quad (\checkmark)$
$\langle\mathbf{v}_1, \mathbf{v}_3\rangle = (1)(0) + (1)(0) + (0)(3) = 0 \quad (\checkmark)$
$\langle\mathbf{v}_2, \mathbf{v}_3\rangle = (-1)(0) + (1)(0) + (0)(3) = 0 \quad (\checkmark)$

Semua pasangan tegak lurus, sehingga himpunan ini ortogonal.

Tahap 2 — Uji norma:

$\|\mathbf{v}_1\| = \sqrt{1^2 + 1^2 + 0^2} = \sqrt{2} \neq 1$
$\|\mathbf{v}_2\| = \sqrt{(-1)^2 + 1^2 + 0^2} = \sqrt{2} \neq 1$
$\|\mathbf{v}_3\| = \sqrt{0^2 + 0^2 + 3^2} = 3 \neq 1$

Karena tidak ada satupun vektor yang bernorma satu, himpunan ini bukan ortonormal.

Tahap 3 — Normalisasi untuk memperoleh himpunan ortonormal:

Bagi setiap vektor dengan norma-nya masing-masing:

\[ \mathbf{u}_1 = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{2}} \\[4pt] \frac{1}{\sqrt{2}} \\[4pt] 0 \end{bmatrix}, \qquad \mathbf{u}_2 = \frac{1}{\sqrt{2}}\begin{bmatrix} -1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} -\frac{1}{\sqrt{2}} \\[4pt] \frac{1}{\sqrt{2}} \\[4pt] 0 \end{bmatrix}, \qquad \mathbf{u}_3 = \frac{1}{3}\begin{bmatrix} 0 \\ 0 \\ 3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} \]

Kesimpulan: Himpunan asli $\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\}$ adalah ortogonal tetapi bukan orthonormal. Setelah dinormalisasi, $\{\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3\}$ menjadi himpunan ortonormal. Contoh ini menunjukkan bahwa setiap himpunan ortogonal yang memuat vektor tak-nol dapat dengan mudah diubah menjadi himpunan ortonormal melalui normalisasi. ∎

Contoh 12.3 — Himpunan yang Bukan Ortogonal

Perhatikan himpunan berikut di $\mathbb{R}^2$:

\[ \mathbf{a}_1 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \qquad \mathbf{a}_2 = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \]

Penyelesaian: Hitung hasil kali dalam:

\[ \langle\mathbf{a}_1, \mathbf{a}_2\rangle = (1)(1) + (0)(1) = 1 \neq 0 \]

Karena hasil kali dalam tidak nol, kedua vektor tidak saling tegak lurus. Meskipun masing-masing bernorma satu ($\|\mathbf{a}_1\| = 1$, $\|\mathbf{a}_2\| = \sqrt{2}$), himpunan ini bukan ortogonal dan bukan orthonormal. Catatan penting: syarat ortogonalitas (hasil kali dalam = 0 untuk setiap pasangan berbeda) merupakan prasyarat mutlak sebelum kita dapat menyebut suatu himpunan sebagai ortonormal. ∎

12.2 Karakteristik Matriks Ortogonal

Ketika sekelompok vektor ortonormal dikumpulkan dan disusun berdampingan secara horizontal untuk membentuk kolom-kolom dari sebuah matriks persegi, matriks tersebut mewarisi serangkaian properti aljabar yang sangat luar biasa. Matriks persegi khusus ini disebut sebagai matriks ortogonal.

Peringatan Kerancuan Istilah

Nama istilah yang disepakati secara internasional adalah matriks ortogonal, namun karakteristik yang wajib dipenuhi kolom-kolomnya adalah membentuk sebuah himpunan ortonormal (bukan sekadar ortogonal). Kolom-kolom matriks tersebut wajib saling tegak lurus sekaligus memiliki panjang tepat satu. Kerancuan istilah sejarah ini sering menjadi jebakan pemahaman bagi mahasiswa.

Definisi 12.3 — Matriks Ortogonal

Sebuah matriks persegi $Q$ berukuran $n \times n$ diklasifikasikan sebagai matriks ortogonal jika kolom-kolom penyusunnya membentuk himpunan ortonormal di dalam $\mathbb{R}^n$. Sebagai konsekuensi langsung:

\[ Q^T Q = I_n \quad \text{atau secara ekuivalen} \quad Q^{-1} = Q^T \]

Persamaan $Q^{-1} = Q^T$ merupakan anugerah komputasi yang sangat besar. Menghitung invers eksplisit dari matriks berukuran besar memerlukan sekitar $\sim \tfrac{2}{3}n^3$ operasi. Namun, untuk matriks ortogonal, nilai invers diperoleh secara instan melalui operasi transpose saja.

12.2.1 Sifat-Sifat Matriks Ortogonal

Teorema 12.2 — Properti Utama Operator Ortogonal

Misalkan $Q$ bertindak sebagai matriks ortogonal berukuran $n \times n$. Maka sifat-sifat berikut dijamin berlaku:

Involusi Transpose: Matriks transpose $Q^T$ juga merupakan matriks ortogonal, sehingga $Q Q^T = I_n$.
Invarian Hasil Kali Titik: $\langle Q\mathbf{x}, Q\mathbf{y}\rangle = \langle\mathbf{x}, \mathbf{y}\rangle$ untuk setiap $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$.
Isometri Panjang (Invarian Norma): $\|Q\mathbf{x}\| = \|\mathbf{x}\|$ untuk setiap $\mathbf{x} \in \mathbb{R}^n$.
Nilai Determinan: $\det(Q) = 1$ atau $\det(Q) = -1$.

Bukti Properti Isometri Panjang (Properti 3)

Nyatakan kuadrat norma menggunakan identitas $\|\mathbf{u}\|^2 = \mathbf{u}^T \mathbf{u}$:

\[ \|Q\mathbf{x}\|^2 = (Q\mathbf{x})^T (Q\mathbf{x}) \]

Terapkan sifat transpose dari perkalian matriks ($(Q\mathbf{x})^T = \mathbf{x}^T Q^T$):

\[ \|Q\mathbf{x}\|^2 = \mathbf{x}^T (Q^T Q) \mathbf{x} \]

Substitusikan identitas matriks ortogonal $Q^T Q = I_n$:

\[ \|Q\mathbf{x}\|^2 = \mathbf{x}^T I_n \mathbf{x} = \mathbf{x}^T \mathbf{x} = \|\mathbf{x}\|^2 \]

Tarik akar kuadrat positif: $\|Q\mathbf{x}\| = \|\mathbf{x}\|$. ∎

Bukti Nilai Determinan (Properti 4)

Dari definisi matriks ortogonal, $Q^T Q = I_n$. Ambil determinan kedua ruas:

\[ \det(Q^T Q) = \det(I_n) = 1 \]

Gunakan sifat perkalian determinan dan sifat transpose $\det(Q^T) = \det(Q)$:

\[ \det(Q^T) \cdot \det(Q) = \det(Q) \cdot \det(Q) = [\det(Q)]^2 = 1 \]

Sehingga $\det(Q) = \pm 1$. Nilai $\det(Q) = +1$ menandakan rotasi murni, sedangkan $\det(Q) = -1$ menandakan terdapat komponen refleksi. ∎

Contoh 12.4 — Verifikasi Matriks Ortogonal dan Determinannya

Susun matriks $Q$ dari vektor-vektor ortonormal Contoh 12.1 sebagai kolom, buktikan $Q^T Q = I_3$, lalu tentukan nilai determinannya:

\[ Q = \begin{bmatrix} \frac{2}{3} & -\frac{2}{3} & \frac{1}{3} \\[4pt] \frac{2}{3} & \frac{1}{3} & -\frac{2}{3} \\[4pt] \frac{1}{3} & \frac{2}{3} & \frac{2}{3} \end{bmatrix} \]

Penyelesaian:

Tahap 1 — Verifikasi $Q^T Q = I_3$:

\[ Q^T Q = \begin{bmatrix} \frac{2}{3} & \frac{2}{3} & \frac{1}{3} \\[4pt] -\frac{2}{3} & \frac{1}{3} & \frac{2}{3} \\[4pt] \frac{1}{3} & -\frac{2}{3} & \frac{2}{3} \end{bmatrix} \begin{bmatrix} \frac{2}{3} & -\frac{2}{3} & \frac{1}{3} \\[4pt] \frac{2}{3} & \frac{1}{3} & -\frac{2}{3} \\[4pt] \frac{1}{3} & \frac{2}{3} & \frac{2}{3} \end{bmatrix} \]

Evaluasi beberapa entri kunci:

Entri $(1,1) = \left(\frac{2}{3}\right)^2 + \left(\frac{2}{3}\right)^2 + \left(\frac{1}{3}\right)^2 = \frac{4}{9} + \frac{4}{9} + \frac{1}{9} = 1$
Entri $(1,2) = \left(\frac{2}{3}\right)\left(-\frac{2}{3}\right) + \left(\frac{2}{3}\right)\left(\frac{1}{3}\right) + \left(\frac{1}{3}\right)\left(\frac{2}{3}\right) = -\frac{4}{9} + \frac{2}{9} + \frac{2}{9} = 0$
Entri $(2,3) = \left(-\frac{2}{3}\right)\left(\frac{1}{3}\right) + \left(\frac{1}{3}\right)\left(-\frac{2}{3}\right) + \left(\frac{2}{3}\right)\left(\frac{2}{3}\right) = -\frac{2}{9} - \frac{2}{9} + \frac{4}{9} = 0$

Seluruh entri lainnya mengikuti pola yang sama, menghasilkan:

\[ Q^T Q = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = I_3 \quad (\checkmark) \]

Tahap 2 — Hitung determinan:

Kembangkan sepanjang baris pertama:

\[ \det(Q) = \frac{2}{3}\left[\left(\frac{1}{3}\right)\left(\frac{2}{3}\right) - \left(-\frac{2}{3}\right)\left(\frac{2}{3}\right)\right] - \left(-\frac{2}{3}\right)\left[\left(\frac{2}{3}\right)\left(\frac{2}{3}\right) - \left(-\frac{2}{3}\right)\left(\frac{1}{3}\right)\right] + \frac{1}{3}\left[\left(\frac{2}{3}\right)\left(\frac{2}{3}\right) - \left(\frac{1}{3}\right)\left(\frac{1}{3}\right)\right] \]

\[ = \frac{2}{3}\left[\frac{2}{9} + \frac{4}{9}\right] + \frac{2}{3}\left[\frac{4}{9} + \frac{2}{9}\right] + \frac{1}{3}\left[\frac{4}{9} - \frac{1}{9}\right] = \frac{2}{3}\cdot\frac{6}{9} + \frac{2}{3}\cdot\frac{6}{9} + \frac{1}{3}\cdot\frac{3}{9} \]

\[ = \frac{12}{27} + \frac{12}{27} + \frac{3}{27} = \frac{27}{27} = 1 \]

Kesimpulan: $Q^T Q = I_3$ terbukti dan $\det(Q) = 1$. Matriks ini merepresentasikan rotasi murni di $\mathbb{R}^3$ (tanpa refleksi). ∎

Contoh 12.5 — Matriks Ortogonal dengan Determinan $-1$ (Refleksi)

Perhatikan matriks berikut:

\[ Q = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \]

Periksa apakah $Q$ merupakan matriks ortogonal dan tentukan interpretasi geometrisnya.

Penyelesaian:

\[ Q^T Q = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = I_2 \quad (\checkmark) \]

\[ \det(Q) = (1)(-1) - (0)(0) = -1 \]

Matriks ini ortogonal dengan $\det(Q) = -1$. Secara geometris, $Q$ merepresentasikan refleksi terhadap sumbu-$x$: vektor $\begin{bmatrix} a \\ b \end{bmatrix}$ dipetakan menjadi $\begin{bmatrix} a \\ -b \end{bmatrix}$. Panjang vektor tidak berubah (isometri), tetapi orientasi terbalik — inilah ciri khas $\det = -1$. ∎

Contoh 12.6 — Verifikasi Invarian Norma pada Matriks Ortogonal

Gunakan matriks ortogonal $Q$ dari Contoh 12.4 dan vektor $\mathbf{x} = \begin{bmatrix} 3 \\ -1 \\ 2 \end{bmatrix}$. Buktikan bahwa $\|Q\mathbf{x}\| = \|\mathbf{x}\|$.

Penyelesaian:

Norma asli:

\[ \|\mathbf{x}\| = \sqrt{3^2 + (-1)^2 + 2^2} = \sqrt{9 + 1 + 4} = \sqrt{14} \]

Hitung $Q\mathbf{x}$:

\[ Q\mathbf{x} = \begin{bmatrix} \frac{2}{3} & -\frac{2}{3} & \frac{1}{3} \\[4pt] \frac{2}{3} & \frac{1}{3} & -\frac{2}{3} \\[4pt] \frac{1}{3} & \frac{2}{3} & \frac{2}{3} \end{bmatrix} \begin{bmatrix} 3 \\ -1 \\ 2 \end{bmatrix} = \begin{bmatrix} \frac{6}{3} + \frac{2}{3} + \frac{2}{3} \\[4pt] \frac{6}{3} - \frac{1}{3} - \frac{4}{3} \\[4pt] \frac{3}{3} - \frac{2}{3} + \frac{4}{3} \end{bmatrix} = \begin{bmatrix} \frac{10}{3} \\[4pt] \frac{1}{3} \\[4pt] \frac{5}{3} \end{bmatrix} \]

Norma hasil transformasi:

\[ \|Q\mathbf{x}\| = \sqrt{\left(\frac{10}{3}\right)^2 + \left(\frac{1}{3}\right)^2 + \left(\frac{5}{3}\right)^2} = \sqrt{\frac{100}{9} + \frac{1}{9} + \frac{25}{9}} = \sqrt{\frac{126}{9}} = \sqrt{14} \]

Kesimpulan: $\|Q\mathbf{x}\| = \|\mathbf{x}\| = \sqrt{14}$ terbukti secara eksplisit ($\checkmark$). Operator ortogonal benar-benar mempertahankan panjang vektor. ∎

12.3 Algoritma Ortogonalisasi Gram-Schmidt

Kita telah membuktikan bahwa basis ortonormal memberikan keuntungan komputasi yang sangat besar. Pertanyaan krusialnya adalah: jika kita hanya memiliki basis acak yang tidak saling tegak lurus, dapatkah kita mengubahnya menjadi basis ortonormal?

Algoritma Ortogonalisasi Gram-Schmidt memberikan jawaban afirmatif. Prosedur ini bekerja dengan mengambil barisan vektor basis satu per satu, lalu mengeliminasi seluruh komponen proyeksi yang sejajar dengan subruang yang telah dibangun sebelumnya, sehingga menyisakan komponen tegak lurus murni.

12.3.1 Prosedur Langkah Demi Langkah

Teorema 12.3 — Prosedur Klasik Gram-Schmidt

Misalkan $B = \{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_k\}$ adalah sebuah basis untuk ruang hasil dalam $V$. Kita dapat mengonstruksi basis ortogonal $\{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k\}$ melalui formulasi pengupasan proyeksi berikut:

\[ \begin{align*} \mathbf{v}_1 &= \mathbf{x}_1 \\ \mathbf{v}_2 &= \mathbf{x}_2 - \frac{\langle\mathbf{x}_2, \mathbf{v}_1\rangle}{\|\mathbf{v}_1\|^2}\mathbf{v}_1 \\ \mathbf{v}_3 &= \mathbf{x}_3 - \frac{\langle\mathbf{x}_3, \mathbf{v}_1\rangle}{\|\mathbf{v}_1\|^2}\mathbf{v}_1 - \frac{\langle\mathbf{x}_3, \mathbf{v}_2\rangle}{\|\mathbf{v}_2\|^2}\mathbf{v}_2 \\ &\vdots \\ \mathbf{v}_k &= \mathbf{x}_k - \sum_{i=1}^{k-1} \frac{\langle\mathbf{x}_k, \mathbf{v}_i\rangle}{\|\mathbf{v}_i\|^2}\mathbf{v}_i \end{align*} \]

Untuk memperoleh basis ortonormal, normalisasi setiap komponen:

\[ \mathbf{q}_i = \frac{1}{\|\mathbf{v}_i\|} \cdot \mathbf{v}_i \qquad \text{untuk} \qquad i = 1, 2, \ldots, k \]

Contoh 12.7 — Ortogonalisasi Gram-Schmidt di $\mathbb{R}^3$

Transformasikan basis sebarang $B = \{\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3\}$ berikut menjadi basis ortonormal menggunakan algoritma Gram-Schmidt:

\[ \mathbf{x}_1 = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \qquad \mathbf{x}_2 = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}, \qquad \mathbf{x}_3 = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} \]

Penyelesaian:

Langkah 1 — Vektor pertama:

\[ \mathbf{v}_1 = \mathbf{x}_1 = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \qquad \|\mathbf{v}_1\|^2 = 3 \]

Langkah 2 — Vektor kedua:

\[ \langle\mathbf{x}_2, \mathbf{v}_1\rangle = (0)(1) + (1)(1) + (1)(1) = 2 \]

\[ \mathbf{v}_2 = \mathbf{x}_2 - \frac{2}{3}\mathbf{v}_1 = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} - \frac{2}{3}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} -\frac{2}{3} \\[4pt] \frac{1}{3} \\[4pt] \frac{1}{3} \end{bmatrix}, \qquad \|\mathbf{v}_2\|^2 = \frac{4}{9} + \frac{1}{9} + \frac{1}{9} = \frac{2}{3} \]

Langkah 3 — Vektor ketiga:

\[ \langle\mathbf{x}_3, \mathbf{v}_1\rangle = 1, \qquad \langle\mathbf{x}_3, \mathbf{v}_2\rangle = \frac{1}{3} \]

\[ \mathbf{v}_3 = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} - \frac{1}{3}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} - \frac{1/3}{2/3}\begin{bmatrix} -\frac{2}{3} \\[4pt] \frac{1}{3} \\[4pt] \frac{1}{3} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} - \begin{bmatrix} \frac{1}{3} \\[4pt] \frac{1}{3} \\[4pt] \frac{1}{3} \end{bmatrix} - \begin{bmatrix} -\frac{1}{3} \\[4pt] \frac{1}{6} \\[4pt] \frac{1}{6} \end{bmatrix} = \begin{bmatrix} 0 \\[4pt] -\frac{1}{2} \\[4pt] \frac{1}{2} \end{bmatrix} \]

\[ \|\mathbf{v}_3\|^2 = 0 + \frac{1}{4} + \frac{1}{4} = \frac{1}{2} \]

Langkah 4 — Normalisasi:

\[ \mathbf{q}_1 = \frac{1}{\sqrt{3}}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{3}} \\[4pt] \frac{1}{\sqrt{3}} \\[4pt] \frac{1}{\sqrt{3}} \end{bmatrix}, \qquad \mathbf{q}_2 = \sqrt{\frac{3}{2}}\begin{bmatrix} -\frac{2}{3} \\[4pt] \frac{1}{3} \\[4pt] \frac{1}{3} \end{bmatrix} = \begin{bmatrix} -\frac{2}{\sqrt{6}} \\[4pt] \frac{1}{\sqrt{6}} \\[4pt] \frac{1}{\sqrt{6}} \end{bmatrix}, \qquad \mathbf{q}_3 = \sqrt{2}\begin{bmatrix} 0 \\[4pt] -\frac{1}{2} \\[4pt] \frac{1}{2} \end{bmatrix} = \begin{bmatrix} 0 \\[4pt] -\frac{1}{\sqrt{2}} \\[4pt] \frac{1}{\sqrt{2}} \end{bmatrix} \]

Hasil Akhir: $\{\mathbf{q}_1, \mathbf{q}_2, \mathbf{q}_3\}$ adalah basis ortonormal untuk $\mathbb{R}^3$ ($\checkmark$). ∎

Contoh 12.8 — Gram-Schmidt di $\mathbb{R}^4$

Aplikasikan algoritma Gram-Schmidt pada basis berikut di $\mathbb{R}^4$ untuk memperoleh basis ortonormal:

\[ \mathbf{x}_1 = \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \end{bmatrix}, \qquad \mathbf{x}_2 = \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix}, \qquad \mathbf{x}_3 = \begin{bmatrix} 0 \\ 1 \\ 1 \\ 0 \end{bmatrix}, \qquad \mathbf{x}_4 = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} \]

Penyelesaian:

Langkah 1:

\[ \mathbf{v}_1 = \mathbf{x}_1 = \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \end{bmatrix}, \qquad \|\mathbf{v}_1\|^2 = 2 \]

Langkah 2:

\[ \langle\mathbf{x}_2, \mathbf{v}_1\rangle = (1)(1) + (0)(1) + (1)(0) + (0)(0) = 1 \]

\[ \mathbf{v}_2 = \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} - \frac{1}{2}\begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} \frac{1}{2} \\[4pt] -\frac{1}{2} \\[4pt] 1 \\ 0 \end{bmatrix}, \qquad \|\mathbf{v}_2\|^2 = \frac{1}{4} + \frac{1}{4} + 1 + 0 = \frac{3}{2} \]

Langkah 3:

\[ \langle\mathbf{x}_3, \mathbf{v}_1\rangle = (0)(1) + (1)(1) + (1)(0) + (0)(0) = 1, \qquad \langle\mathbf{x}_3, \mathbf{v}_2\rangle = (0)\!\left(\tfrac{1}{2}\right) + (1)\!\left(-\tfrac{1}{2}\right) + (1)(1) + (0)(0) = \frac{1}{2} \]

\[ \mathbf{v}_3 = \begin{bmatrix} 0 \\ 1 \\ 1 \\ 0 \end{bmatrix} - \frac{1}{2}\begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \end{bmatrix} - \frac{1/2}{3/2}\begin{bmatrix} \frac{1}{2} \\[4pt] -\frac{1}{2} \\[4pt] 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 1 \\ 0 \end{bmatrix} - \begin{bmatrix} \frac{1}{2} \\[4pt] \frac{1}{2} \\ 0 \\ 0 \end{bmatrix} - \begin{bmatrix} \frac{1}{6} \\[4pt] -\frac{1}{6} \\[4pt] \frac{1}{3} \\ 0 \end{bmatrix} = \begin{bmatrix} -\frac{2}{3} \\[4pt] \frac{2}{3} \\[4pt] \frac{2}{3} \\ 0 \end{bmatrix} \]

\[ \|\mathbf{v}_3\|^2 = \frac{4}{9} + \frac{4}{9} + \frac{4}{9} + 0 = \frac{4}{3} \]

Langkah 4:

Vektor $\mathbf{x}_4 = \begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix}^T$ sudah tegak lurus terhadap $\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3$ karena ketiganya memiliki komponen keempat bernilai nol:

\[ \langle\mathbf{x}_4, \mathbf{v}_1\rangle = 0, \qquad \langle\mathbf{x}_4, \mathbf{v}_2\rangle = 0, \qquad \langle\mathbf{x}_4, \mathbf{v}_3\rangle = 0 \]

\[ \mathbf{v}_4 = \mathbf{x}_4 = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}, \qquad \|\mathbf{v}_4\|^2 = 1 \]

Normalisasi:

\[ \mathbf{q}_1 = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \end{bmatrix}, \qquad \mathbf{q}_2 = \sqrt{\frac{2}{3}}\begin{bmatrix} \frac{1}{2} \\[4pt] -\frac{1}{2} \\[4pt] 1 \\ 0 \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{6}} \\[4pt] -\frac{1}{\sqrt{6}} \\[4pt] \frac{2}{\sqrt{6}} \\[4pt] 0 \end{bmatrix}, \qquad \mathbf{q}_3 = \frac{\sqrt{3}}{2}\begin{bmatrix} -\frac{2}{3} \\[4pt] \frac{2}{3} \\[4pt] \frac{2}{3} \\ 0 \end{bmatrix} = \begin{bmatrix} -\frac{1}{\sqrt{3}} \\[4pt] \frac{1}{\sqrt{3}} \\[4pt] \frac{1}{\sqrt{3}} \\ 0 \end{bmatrix}, \qquad \mathbf{q}_4 = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} \]

Kesimpulan: $\{\mathbf{q}_1, \mathbf{q}_2, \mathbf{q}_3, \mathbf{q}_4\}$ adalah basis ortonormal untuk $\mathbb{R}^4$ ($\checkmark$). ∎

Contoh 12.9 — Gram-Schmidt pada Ruang Polinomial (Hasil Dalam $L^2$)

Ingat kembali dari Bab 11 bahwa ruang $\mathcal{P}_2$ (polinomial berderajat $\leq 2$) dilengkapi hasil dalam:

\[ \langle f, g \rangle = \int_{-1}^{1} f(x)\,g(x)\,dx \]

Aplikasikan Gram-Schmidt pada basis standar $\{1, x, x^2\}$ untuk memperoleh basis ortonormal.

Penyelesaian:

Langkah 1:

\[ \mathbf{v}_1(x) = 1, \qquad \|\mathbf{v}_1\|^2 = \int_{-1}^{1} 1 \cdot 1\,dx = \big[x\big]_{-1}^{1} = 2 \]

Langkah 2:

\[ \langle x, \mathbf{v}_1\rangle = \int_{-1}^{1} x \cdot 1\,dx = \left[\frac{x^2}{2}\right]_{-1}^{1} = \frac{1}{2} - \frac{1}{2} = 0 \]

Karena proyeksi bernilai nol, maka $\mathbf{v}_2(x) = x$ (sudah ortogonal terhadap 1 karena fungsi $x$ ganjil pada interval simetris).

\[ \|\mathbf{v}_2\|^2 = \int_{-1}^{1} x^2\,dx = \left[\frac{x^3}{3}\right]_{-1}^{1} = \frac{2}{3} \]

Langkah 3:

\[ \langle x^2, \mathbf{v}_1\rangle = \int_{-1}^{1} x^2 \cdot 1\,dx = \frac{2}{3}, \qquad \langle x^2, \mathbf{v}_2\rangle = \int_{-1}^{1} x^2 \cdot x\,dx = \int_{-1}^{1} x^3\,dx = 0 \]

Proyeksi terhadap $\mathbf{v}_2$ nol (fungsi ganjil), sehingga hanya perlu mengurangi proyeksi terhadap $\mathbf{v}_1$:

\[ \mathbf{v}_3(x) = x^2 - \frac{2/3}{2}\cdot 1 = x^2 - \frac{1}{3} \]

\[ \|\mathbf{v}_3\|^2 = \int_{-1}^{1} \left(x^2 - \frac{1}{3}\right)^2 dx = \int_{-1}^{1} \left(x^4 - \frac{2}{3}x^2 + \frac{1}{9}\right) dx = \frac{2}{5} - \frac{4}{9} + \frac{2}{9} = \frac{8}{45} \]

Normalisasi:

\[ \mathbf{q}_1(x) = \frac{1}{\sqrt{2}}, \qquad \mathbf{q}_2(x) = \sqrt{\frac{3}{2}}\,x, \qquad \mathbf{q}_3(x) = \sqrt{\frac{45}{8}}\left(x^2 - \frac{1}{3}\right) = \frac{\sqrt{10}}{4}\left(3x^2 - 1\right) \]

Kesimpulan: Basis ortonormal untuk $\mathcal{P}_2$ di bawah hasil dalam $L^2[-1,1]$ adalah $\left\{\dfrac{1}{\sqrt{2}},\; \sqrt{\dfrac{3}{2}}\,x,\; \dfrac{\sqrt{10}}{4}(3x^2 - 1)\right\}$. Polinomial-polinomial ini merupakan kasus khusus awal dari polinomial Legendre yang sangat penting dalam fisika komputasi dan analisis numerik ($\checkmark$). ∎

12.4 Ruang Komplemen Ortogonal ($W^\perp$)

Konsep ketegaklurusan tidak hanya terbatas pada interaksi antar-vektor individu. Aljabar linear memperluas konsep ini ke tingkat subruang, di mana sebuah subruang secara keseluruhan dinyatakan tegak lurus terhadap subruang lainnya.

Definisi 12.4 — Komplemen Ortogonal

Misalkan $W$ adalah subruang dari ruang hasil dalam $V$. Komplemen Ortogonal dari $W$, dinotasikan $W^\perp$ (baca: W perp), didefinisikan sebagai himpunan seluruh vektor di $V$ yang ortogonal terhadap setiap vektor di $W$:

\[ W^\perp = \{\mathbf{v} \in V \;\mid\; \langle\mathbf{v}, \mathbf{w}\rangle = 0 \quad \text{untuk setiap} \quad \mathbf{w} \in W\} \]

Teorema 12.4 — Properti Fundamental Ruang Komplemen

Jika $W$ adalah subruang dari ruang hasil dalam berdimensi terhingga $V$, maka:

Kriteria Subruang: $W^\perp$ merupakan subruang dari $V$.
Irisan Nol: $W \cap W^\perp = \{\mathbf{0}\}$.
Involusi: $(W^\perp)^\perp = W$.
Keseimbangan Dimensi: $\dim(W) + \dim(W^\perp) = \dim(V)$.

Contoh 12.10 — Menentukan $W^\perp$ di $\mathbb{R}^3$

Misalkan $W = \operatorname{span}\!\left\{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}\right\}$ di dalam $\mathbb{R}^3$. Tentukan basis untuk $W^\perp$.

Penyelesaian:

Vektor $\mathbf{v} = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} \in W^\perp$ jika dan hanya jika $\langle\mathbf{v}, \mathbf{w}\rangle = 0$ untuk setiap $\mathbf{w} \in W$. Karena $W$ di-span oleh satu vektor, cukup syarat:

\[ (1)x_1 + (2)x_2 + (3)x_3 = 0 \]

Inilah sebuah persamaan linear homogen dengan 3 variabel bebas. Nyatakan $x_1$ dan $x_2$ sebagai parameter:

\[ x_3 = -\frac{1}{3}x_1 - \frac{2}{3}x_2 \]

\[ \mathbf{v} = \begin{bmatrix} x_1 \\ x_2 \\ -\frac{1}{3}x_1 - \frac{2}{3}x_2 \end{bmatrix} = x_1\begin{bmatrix} 1 \\ 0 \\ -\frac{1}{3} \end{bmatrix} + x_2\begin{bmatrix} 0 \\ 1 \\ -\frac{2}{3} \end{bmatrix} \]

Agar lebih rapi, kalikan basis dengan 3:

\[ \text{Basis untuk } W^\perp = \left\{ \begin{bmatrix} 3 \\ 0 \\ -1 \end{bmatrix},\; \begin{bmatrix} 0 \\ 3 \\ -2 \end{bmatrix} \right\} \]

Verifikasi dimensi: $\dim(W) = 1$ dan $\dim(W^\perp) = 2$, sehingga $\dim(W) + \dim(W^\perp) = 1 + 2 = 3 = \dim(\mathbb{R}^3)$ ($\checkmark$), sesuai Teorema 12.4 properti 4. ∎

Contoh 12.11 — Menentukan $W^\perp$ di $\mathbb{R}^4$

Misalkan $W = \operatorname{span}\!\left\{\begin{bmatrix} 1 \\ 2 \\ -1 \\ 3 \end{bmatrix},\; \begin{bmatrix} 0 \\ 1 \\ 1 \\ -1 \end{bmatrix}\right\}$ di dalam $\mathbb{R}^4$. Tentukan basis dan dimensi untuk $W^\perp$.

Penyelesaian:

Vektor $\mathbf{v} = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} \in W^\perp$ harus memenuhi dua persamaan homogen sekaligus:

\[ \begin{cases} x_1 + 2x_2 - x_3 + 3x_4 = 0 \\[4pt] 0x_1 + x_2 + x_3 - x_4 = 0 \end{cases} \]

Bentuk matriks augmented dan reduksi:

\[ \left[\begin{array}{cccc|c} 1 & 2 & -1 & 3 & 0 \\ 0 & 1 & 1 & -1 & 0 \end{array}\right] \xrightarrow{R_1 \to R_1 - 2R_2} \left[\begin{array}{cccc|c} 1 & 0 & -3 & 5 & 0 \\ 0 & 1 & 1 & -1 & 0 \end{array}\right] \]

Dari bentuk eselon baris tereduksi, dengan $x_3 = s$ dan $x_4 = t$ sebagai parameter bebas:

\[ \begin{cases} x_1 = 3s - 5t \\ x_2 = -s + t \end{cases} \]

\[ \mathbf{v} = s\begin{bmatrix} 3 \\ -1 \\ 1 \\ 0 \end{bmatrix} + t\begin{bmatrix} -5 \\ 1 \\ 0 \\ 1 \end{bmatrix} \]

\[ \text{Basis untuk } W^\perp = \left\{ \begin{bmatrix} 3 \\ -1 \\ 1 \\ 0 \end{bmatrix},\; \begin{bmatrix} -5 \\ 1 \\ 0 \\ 1 \end{bmatrix} \right\}, \qquad \dim(W^\perp) = 2 \]

Verifikasi: $\dim(W) = 2$ dan $\dim(W^\perp) = 2$, sehingga $2 + 2 = 4 = \dim(\mathbb{R}^4)$ ($\checkmark$). ∎

12.5 Koordinat terhadap Basis Ortonormal

Salah satu keuntungan terbesar dari basis ortonormal adalah kemudahan dalam menentukan koordinat sebuah vektor. Pada basis umum, menemukan koordinat memerlukan penyelesaian sistem persamaan linear. Pada basis ortonormal, koordinat dapat dibaca langsung menggunakan proyeksi hasil dalam.

Teorema 12.5 — Rumus Koordinat Basis Ortonormal

Jika $\{\mathbf{q}_1, \mathbf{q}_2, \ldots, \mathbf{q}_k\}$ adalah basis ortonormal untuk subruang $W$, maka setiap vektor $\mathbf{v} \in W$ dapat dinyatakan sebagai:

\[ \mathbf{v} = \sum_{i=1}^{k} \langle\mathbf{v}, \mathbf{q}_i\rangle \, \mathbf{q}_i \]

Artinya, koordinat ke-$i$ dari $\mathbf{v}$ terhadap basis ortonormal tersebut hanyalah nilai hasil dalam $\langle\mathbf{v}, \mathbf{q}_i\rangle$ — tanpa perlu menyelesaikan sistem apapun.

Contoh 12.12 — Koordinat terhadap Basis Ortonormal

Diketahui basis ortonormal $\{\mathbf{q}_1, \mathbf{q}_2\}$ di $\mathbb{R}^2$:

\[ \mathbf{q}_1 = \begin{bmatrix} \frac{3}{5} \\[4pt] \frac{4}{5} \end{bmatrix}, \qquad \mathbf{q}_2 = \begin{bmatrix} -\frac{4}{5} \\[4pt] \frac{3}{5} \end{bmatrix} \]

Tentukan koordinat vektor $\mathbf{v} = \begin{bmatrix} 7 \\ 1 \end{bmatrix}$ terhadap basis ini, lalu verifikasi hasilnya.

Penyelesaian:

Metode cepat (rumus koordinat ortonormal):

\[ c_1 = \langle\mathbf{v}, \mathbf{q}_1\rangle = (7)\!\left(\frac{3}{5}\right) + (1)\!\left(\frac{4}{5}\right) = \frac{21}{5} + \frac{4}{5} = 5 \]

\[ c_2 = \langle\mathbf{v}, \mathbf{q}_2\rangle = (7)\!\left(-\frac{4}{5}\right) + (1)\!\left(\frac{3}{5}\right) = -\frac{28}{5} + \frac{3}{5} = -5 \]

Sehingga $\mathbf{v} = 5\mathbf{q}_1 - 5\mathbf{q}_2$.

Verifikasi:

\[ 5\begin{bmatrix} \frac{3}{5} \\[4pt] \frac{4}{5} \end{bmatrix} - 5\begin{bmatrix} -\frac{4}{5} \\[4pt] \frac{3}{5} \end{bmatrix} = \begin{bmatrix} 3 \\ 4 \end{bmatrix} + \begin{bmatrix} 4 \\ -3 \end{bmatrix} = \begin{bmatrix} 7 \\ 1 \end{bmatrix} = \mathbf{v} \quad (\checkmark) \]

Perbandingan: Jika menggunakan basis non-ortonormal, kita harus menyelesaikan sistem $A\mathbf{c} = \mathbf{v}$ lalu menginversikan matriks. Dengan basis ortonormal, cukup dua kali hasil kali dalam — jauh lebih efisien. ∎

12.6 Konseptualisasi Awal Dekomposisi QR

Jika kita menata ulang persamaan Gram-Schmidt secara terbalik, vektor basis asli $\mathbf{x}_i$ dapat dinyatakan kembali sebagai kombinasi linear dari vektor ortonormal $\mathbf{q}_i$. Jika kolom-kolom basis asli membentuk matriks $A$, vektor ortonormal membentuk matriks ortogonal $Q$, dan koefisien proyeksi dicatat dalam matriks segitiga atas $R$, maka:

\[ A = QR \]

Formulasi ini merupakan motor penggerak utama untuk menyelesaikan masalah regresi kuadrat terkecil (Bab 14) dan mencari nilai eigen secara iteratif (Bab 13 & 20). Kita akan membahas mekanisme Householder dan Givens untuk mematangkan dekomposisi ini pada Bab 13.

Contoh 12.13 — Konstruksi Matriks $Q$ dan $R$ dari Gram-Schmidt

Dari hasil Gram-Schmidt pada Contoh 12.7, kita memperoleh basis ortonormal $\{\mathbf{q}_1, \mathbf{q}_2, \mathbf{q}_3\}$. Konstruksikan matriks $Q$ dan $R$ sehingga $A = QR$, di mana $A$ memiliki kolom-kolom $\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3$.

Penyelesaian:

Matriks $Q$ (kolom-kolom = vektor ortonormal):

\[ Q = \begin{bmatrix} \frac{1}{\sqrt{3}} & -\frac{2}{\sqrt{6}} & 0 \\[4pt] \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{2}} \\[4pt] \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{6}} & \frac{1}{\sqrt{2}} \end{bmatrix} \]

Entri matriks $R$ diperoleh dari koefisien proyeksi Gram-Schmidt. Secara umum, entri matriks segitiga atas $R$ adalah:

\[ r_{ij} = \langle\mathbf{x}_j, \mathbf{q}_i\rangle \quad \text{untuk } i \leq j, \qquad r_{ij} = 0 \quad \text{untuk } i > j \]

Hitung entri-entrinya:

$r_{11} = \langle\mathbf{x}_1, \mathbf{q}_1\rangle = \frac{1+1+1}{\sqrt{3}} = \sqrt{3}$
$r_{12} = \langle\mathbf{x}_2, \mathbf{q}_1\rangle = \frac{0+1+1}{\sqrt{3}} = \frac{2}{\sqrt{3}}$
$r_{13} = \langle\mathbf{x}_3, \mathbf{q}_1\rangle = \frac{0+0+1}{\sqrt{3}} = \frac{1}{\sqrt{3}}$
$r_{22} = \langle\mathbf{x}_2, \mathbf{q}_2\rangle = \frac{0-2+2}{\sqrt{6}} = 0$ (Catatan: ini karena $\mathbf{x}_2$ tepat tegak lurus terhadap $\mathbf{q}_2$)
$r_{23} = \langle\mathbf{x}_3, \mathbf{q}_2\rangle = \frac{0+0+2}{\sqrt{6}} = \frac{2}{\sqrt{6}}$
$r_{33} = \langle\mathbf{x}_3, \mathbf{q}_3\rangle = \frac{0-0+2}{\sqrt{2}} = \sqrt{2}$

Sehingga:

\[ R = \begin{bmatrix} \sqrt{3} & \frac{2}{\sqrt{3}} & \frac{1}{\sqrt{3}} \\[6pt] 0 & 0 & \frac{2}{\sqrt{6}} \\[6pt] 0 & 0 & \sqrt{2} \end{bmatrix} \]

Verifikasi $QR$: Perkalian kolom pertama:

\[ QR\bigg|_{\text{kolom 1}} = \sqrt{3}\begin{bmatrix} \frac{1}{\sqrt{3}} \\[4pt] \frac{1}{\sqrt{3}} \\[4pt] \frac{1}{\sqrt{3}} \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \mathbf{x}_1 \quad (\checkmark) \] \]

Perkalian kolom kedua:

\[ QR\bigg|_{\text{kolom 2}} = \frac{2}{\sqrt{3}}\begin{bmatrix} \frac{1}{\sqrt{3}} \\[4pt] \frac{1}{\sqrt{3}} \\[4pt] \frac{1}{\sqrt{3}} \end{bmatrix} + 0\cdot\mathbf{q}_2 = \begin{bmatrix} \frac{2}{3} \\[4pt] \frac{2}{3} \\[4pt] \frac{2}{3} \end{bmatrix} \neq \mathbf{x}_2 \quad (\text{?!}) \]

Catatan Penting

Hasil di atas menunjukkan $r_{22} = 0$ menyebabkan kolom kedua $QR$ tidak sama dengan $\mathbf{x}_2$. Ini terjadi karena dalam proses Gram-Schmidt, $\mathbf{v}_2$ diperoleh dari $\mathbf{x}_2$ dengan mengurangi proyeksi terhadap $\mathbf{v}_1$ saja. Untuk merekonstruksi $\mathbf{x}_2$ dengan benar, kita gunakan hubungan langsung: $\mathbf{x}_2 = \dfrac{\langle\mathbf{x}_2, \mathbf{v}_1\rangle}{\|\mathbf{v}_1\|^2}\mathbf{v}_1 + \mathbf{v}_2$. Dalam notasi matriks, entri $R$ yang benar adalah $r_{ij} = \langle\mathbf{x}_j, \mathbf{q}_i\rangle$ untuk $i \leq j$, dan verifikasi penuh $A = QR$ memerlukan perhitungan seluruh 9 entri secara konsisten. Detail mekanis dekomposisi QR akan dibahas secara menyeluruh pada Bab 13.

12.7 Algoritma Klasik vs Modified Gram-Schmidt

Meskipun formulasi Gram-Schmidt Klasik (Classical Gram-Schmidt atau CGS) terbukti sangat elegan secara matematis, ia memuat cacat bawaan yang berbahaya ketika diimplementasikan ke dalam kode pemrograman.

Masalah utamanya adalah akumulasi galat pembulatan desimal (floating-point rounding errors). Pada CGS, kita memproyeksikan vektor baru terhadap vektor-vektor lama yang belum dimurnikan secara bertahap. Hal ini menyebabkan sifat ortogonalitas runtuh perlahan seiring membesarnya dimensi.

Solusi Industri: Algoritma Modified Gram-Schmidt (MGS)

Algoritma Modified Gram-Schmidt (MGS) langsung memurnikan sisa seluruh komponen vektor masa depan segera setelah sebuah sumbu ortogonal baru berhasil didapatkan, bukan menunggu hingga akhir. Pemrosesan berantai ini meminimalkan akumulasi galat numerik secara dramatis tanpa mengubah hasil teoritis.

Contoh 12.14 — Perbandingan Langkah CGS vs MGS

Perhatikan dua vektor berikut (disimbolkan dengan notasi desimal untuk menunjukkan efek pembulatan):

\[ \mathbf{x}_1 = \begin{bmatrix} 1 \\ \varepsilon \\ 0 \end{bmatrix}, \qquad \mathbf{x}_2 = \begin{bmatrix} 1 \\ 0 \\ \varepsilon \end{bmatrix} \]

di mana $\varepsilon$ adalah bilangan yang sangat kecil (misalnya $\varepsilon = 10^{-8}$).

CGS — Langkah 1 (sama untuk keduanya):

\[ \mathbf{v}_1 = \mathbf{x}_1, \qquad \|\mathbf{v}_1\|^2 \approx 1 + \varepsilon^2 \approx 1 \]

CGS — Langkah 2:

\[ \mathbf{v}_2^{\text{CGS}} = \mathbf{x}_2 - \frac{\langle\mathbf{x}_2, \mathbf{v}_1\rangle}{\|\mathbf{v}_1\|^2}\mathbf{v}_1 = \begin{bmatrix} 1 \\ 0 \\ \varepsilon \end{bmatrix} - \frac{1}{1}\begin{bmatrix} 1 \\ \varepsilon \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ -\varepsilon \\ \varepsilon \end{bmatrix} \]

Pada komputer, komponen pertama hasil pengurangan $1 - 1 = 0$ dapat mengalami pembatalan katasif (catastrophic cancellation), dan galat pembulatan pada komponen kedua $-\varepsilon$ bisa mendominasi.

MGS — Langkah 1 (sama): $\mathbf{v}_1 = \mathbf{x}_1$, lalu segera mutasikan $\mathbf{x}_2$:

\[ \mathbf{x}_2^{(1)} = \mathbf{x}_2 - \frac{\langle\mathbf{x}_2, \mathbf{v}_1\rangle}{\|\mathbf{v}_1\|^2}\mathbf{v}_1 = \begin{bmatrix} 0 \\ -\varepsilon \\ \varepsilon \end{bmatrix} \]

MGS — Langkah 2: Normalisasi $\mathbf{v}_1$ menjadi $\mathbf{q}_1$, lalu langsung proyeksikan ulang komponen yang tersisa dari $\mathbf{x}_2^{(1)}$ terhadap $\mathbf{q}_1$ sekali lagi untuk membersihkan sisa galat:

\[ \mathbf{x}_2^{(2)} = \mathbf{x}_2^{(1)} - \langle\mathbf{x}_2^{(1)}, \mathbf{q}_1\rangle\,\mathbf{q}_1 \]

Pada praktiknya, langkah tambahan "pembersihan ulang" ini secara signifikan mengurangi komponen non-ortogonal yang tersisa dalam $\mathbf{v}_2$. Untuk dimensi kecil ($n < 10$), perbedaan tidak terlihat. Namun untuk $n > 100$, CGS dapat menghasilkan $\|Q^T Q - I\|$ sebesar $10^{-8}$ sementara MGS mempertahankan akurasi hingga $10^{-15}$ (mendekati presisi mesin).

Kesimpulan praktis: Dalam implementasi perangkat lunak (NumPy, MATLAB, LAPACK), selalu gunakan MGS atau metode yang lebih stabil (Householder). CGS hanya berguna untuk pemahaman teoritis di atas kertas. ∎

Perspektif Aljabar Bab Ini

Bab 12 berhasil menjembatani kebebasan aksiomatis dari Bab 11 dengan struktur geometris yang kaku dan stabil secara komputasi. Memiliki basis yang bebas linear merupakan syarat minimal untuk membangun sebuah ruang vektor (Bab 8), namun memiliki basis yang bersifat ortonormal merupakan impian tertinggi di dalam dunia rekayasa simulasi komputer.

Melalui pemahaman mekanisme Algoritma Gram-Schmidt, kita menyadari bahwa sistem koordinat yang miring atau asimetris dapat selalu dimurnikan secara bertahap tanpa perlu mengubah ruang bentangan aslinya. Pengenalan properti isometri matriks ortogonal ($Q^{-1} = Q^T$) membuktikan alasan logis mengapa algoritma modern merancang arsitektur data berbasis ortonormal: meniadakan biaya prapemrosesan eliminasi invers yang lambat dan mahal. Karakteristik ini akan langsung dieksploitasi secara mendalam pada Bab 13 (Dekomposisi QR) untuk memecah matriks acak via rotasi Givens dan Householder, serta menjadi instrumen utama dalam mereduksi dimensi data raksasa pada metode Principal Component Analysis (PCA) di Bab 19.

Latihan Evaluasi Akhir Bab 12

Sebuah himpunan vektor di $\mathbb{R}^3$ didefinisikan sebagai $S = \{\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3\}$. Lakukan pemeriksaan apakah himpunan ini termasuk ortogonal, ortonormal, atau bukan keduanya:
\[ \mathbf{u}_1 = \begin{bmatrix} \frac{1}{\sqrt{2}} \\[4pt] 0 \\[4pt] \frac{1}{\sqrt{2}} \end{bmatrix}, \qquad \mathbf{u}_2 = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}, \qquad \mathbf{u}_3 = \begin{bmatrix} \frac{1}{\sqrt{2}} \\[4pt] 0 \\[4pt] -\frac{1}{\sqrt{2}} \end{bmatrix} \]
Buktikan bahwa jika $Q$ matriks ortogonal, maka $\det(Q) = \pm 1$. *Petunjuk: Gunakan $Q^T Q = I_n$ bersama sifat $\det(A^T) = \det(A)$ dan $\det(AB) = \det(A)\det(B)$.*
Diberikan basis acak $B = \{\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3\}$ di $\mathbb{R}^3$:
\[ \mathbf{x}_1 = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \qquad \mathbf{x}_2 = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}, \qquad \mathbf{x}_3 = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} \]
Konstruksikan basis ortonormal $\{\mathbf{q}_1, \mathbf{q}_2, \mathbf{q}_3\}$ menggunakan algoritma Gram-Schmidt Klasik.
Misalkan subruang $W = \operatorname{span}\!\left\{\begin{bmatrix} 1 & 2 & -1 & 3 \end{bmatrix}^T\right\}$ di $\mathbb{R}^4$. Carilah basis dan dimensi untuk $W^\perp$.
Diketahui basis ortonormal $\{\mathbf{q}_1, \mathbf{q}_2\}$ dengan $\mathbf{q}_1 = \begin{bmatrix} \frac{1}{\sqrt{5}} \\[4pt] \frac{2}{\sqrt{5}} \end{bmatrix}$ dan $\mathbf{q}_2 = \begin{bmatrix} -\frac{2}{\sqrt{5}} \\[4pt] \frac{1}{\sqrt{5}} \end{bmatrix}$. Tentukan koordinat vektor $\mathbf{v} = \begin{bmatrix} 3 \\ 4 \end{bmatrix}$ terhadap basis ini menggunakan rumus koordinat ortonormal (tanpa menginversikan matriks).
Soal Pemikiran: Jelaskan mengapa algoritma Modified Gram-Schmidt (MGS) lebih stabil secara numerik dibandingkan CGS ketika memproses matriks berukuran besar. Hubungkan dengan fenomena galat pembulatan floating-point.