Sistem Persamaan Normal

Apa itu Sistem Persamaan Normal

Bayangkan kamu punya masalah optimasi yang rumit, tapi ternyata ada jalan pintas yang elegan. Dalam masalah kuadrat terkecil, alih-alih melakukan optimasi langsung, kita bisa mengubahnya menjadi sistem persamaan yang lebih mudah diselesaikan.

Ketika kita ingin meminimumkan

ternyata solusinya dapat ditemukan dengan menyelesaikan sistem persamaan berikut

Persamaan ini disebut sistem persamaan normal karena melibatkan konsep ortogonalitas atau keadaan "normal" (tegak lurus) dalam ruang vektor.

Hubungan Fundamental

Ada hubungan yang sangat menarik antara masalah minimisasi dan sistem persamaan normal ini. Vektor $\hat{x} \in \mathbb{R}^n$ merupakan solusi dari masalah kuadrat terkecil jika dan hanya jika vektor tersebut memenuhi sistem persamaan normal.

Dengan kata lain, mencari $\hat{x}$ yang membuat $\|A \cdot x - b\|_2^2$ minimal sama persis dengan mencari $\hat{x}$ yang memenuhi $A^T A \cdot \hat{x} = A^T b$.

Mengapa Sistem Ini Bekerja

Untuk memahami mengapa hubungan ini berlaku, kita perlu melihat dari sudut pandang geometris.

Ketika $\hat{x}$ memberikan nilai minimum untuk $\|A\hat{x} - b\|_2^2$, maka vektor kesalahan $A\hat{x} - b$ harus ortogonal terhadap semua vektor dalam ruang kolom matriks $A$.

Ruang kolom ini terdiri dari semua vektor yang dapat ditulis sebagai $Ax$ untuk $x \in \mathbb{R}^n$. Kondisi ortogonalitas berarti

untuk setiap vektor $x \in \mathbb{R}^n$. Dengan menggunakan sifat perkalian dalam, kita dapat menuliskan

Karena hubungan ini harus berlaku untuk semua vektor $x$, maka

Inilah yang memberikan sistem persamaan normal.

Pembuktian Menggunakan Teorema Pythagoras

Kita juga bisa memverifikasi hasil ini dengan cara yang berbeda. Misalkan $\hat{x}$ adalah solusi sistem persamaan normal dan $x$ adalah sembarang vektor di $\mathbb{R}^n$.

Menggunakan teorema Pythagoras, kita dapat menuliskan

Karena $\hat{x}$ memenuhi sistem persamaan normal, maka $A^T A\hat{x} - A^T b = 0$ dan norm kuadrat selalu non-negatif. Oleh karena itu

Ketidaksamaan ini membuktikan bahwa $\hat{x}$ memang memberikan nilai minimum.

Kapan Sistem Persamaan Normal Dapat Diselesaikan

Tidak semua sistem persamaan normal dapat diselesaikan dengan mudah. Ada kondisi khusus yang harus dipenuhi.

Untuk matriks $A \in \mathbb{R}^{m \times n}$ dengan $m \geq n$, matriks simetrik $A^T A \in \mathbb{R}^{n \times n}$ dapat diinversi jika dan hanya jika matriks $A$ memiliki peringkat penuh, yaitu $\text{Peringkat}(A) = n$.

Kondisi ini sangat penting karena menentukan apakah sistem persamaan normal memiliki solusi yang unik. Ketika $A^T A$ dapat diinversi, solusi dapat ditulis secara eksplisit sebagai

Pembuktian Kondisi Invertible

Untuk memahami kapan $A^T A$ dapat diinversi, kita perlu melihat hubungan antara ruang nul (kernel) dan peringkat.

Jika $A^T A$ dapat diinversi, maka ruang nul dari $A^T A$ hanya berisi vektor nol. Karena ruang nul dari $A^T A$ mencakup ruang nul dari $A$, maka $A$ juga hanya memiliki vektor nol dalam ruang nulnya. Ini berarti $\text{Peringkat}(A) = n$.

Sebaliknya, jika $\text{Peringkat}(A) = n$, maka persamaan $Ax = 0$ hanya memiliki solusi $x = 0$. Untuk melihat bahwa $A^T A$ dapat diinversi, perhatikan bahwa jika $A^T Ax = 0$, maka

Karena perkalian dalam hanya bernilai nol jika $Ax = 0$, dan kita tahu bahwa ini hanya terjadi ketika $x = 0$, maka $A^T A$ memang dapat diinversi.

Sifat Positif Definit

Lebih dari sekadar dapat diinversi, matriks $A^T A$ memiliki sifat khusus. Ketika $\text{Peringkat}(A) = n$ dan $x \neq 0$, kita memiliki $Ax \neq 0$ dan

Ini menunjukkan bahwa $A^T A$ adalah matriks positif definit. Properti ini menjamin bahwa sistem persamaan normal tidak hanya memiliki solusi unik, tetapi juga stabil secara numerik ketika diselesaikan dengan metode komputasi. Algoritma seperti dekomposisi Cholesky dapat digunakan dengan aman untuk menyelesaikan sistem ini.