Solusi Sistem Persamaan Normal

Sifat Fundamental

Sistem persamaan normal $A^T A x = A^T b$ memiliki karakteristik khusus yang membedakannya dari sistem linear biasa. Bayangkan seperti mencari titik terbaik pada sebuah garis untuk mewakili kumpulan data yang tersebar, sistem ini memberikan cara matematis untuk menemukan solusi optimal tersebut.

Untuk matriks $A \in \mathbb{R}^{m \times n}$ dengan $m \geq n$, sistem persamaan normal $A^T A x = A^T b$ selalu memiliki solusi. Lebih spesifik lagi, sistem ini memiliki solusi unik tepat ketika matriks $A$ memiliki peringkat penuh, yaitu ketika $\text{Peringkat}(A) = n$. Dalam kondisi ini, solusi dapat dinyatakan sebagai $\hat{x} = (A^T A)^{-1} A^T b$.

Ketika matriks $A$ tidak memiliki peringkat penuh, himpunan solusi sistem persamaan normal berbentuk $\hat{x} + \text{Kernel}(A)$, dimana $\hat{x}$ adalah sembarang solusi khusus dari sistem tersebut.

Mengapa Sistem Selalu Dapat Diselesaikan

Alasan mendasar mengapa sistem persamaan normal selalu memiliki solusi terletak pada konsep proyeksi ortogonal. Proyeksi ortogonal dari vektor $b$ ke ruang kolom $\{Ax : x \in \mathbb{R}^n\}$ selalu ada dan merupakan solusi dari masalah kuadrat terkecil linear, yang secara otomatis juga merupakan solusi sistem persamaan normal.

Untuk memahami mengapa solusi lain berbentuk $\hat{x} + \text{Kernel}(A)$, misalkan $\tilde{x}$ adalah solusi lain dari sistem $A^T A \tilde{x} = A^T b$. Maka $\tilde{x}$ adalah solusi sistem persamaan normal jika dan hanya jika $A^T A(\tilde{x} - \hat{x}) = 0$, yang ekuivalen dengan $(\tilde{x} - \hat{x})^T A^T A(\tilde{x} - \hat{x}) = 0$, yang selanjutnya ekuivalen dengan $A(\tilde{x} - \hat{x}) = 0$, atau dengan kata lain $\tilde{x} - \hat{x} \in \text{Kernel}(A)$.

Moore-Penrose Pseudoinverse

Untuk matriks $A \in \mathbb{R}^{m \times n}$ dengan $m \geq n$ dan $\text{Peringkat}(A) = n$, kita dapat mendefinisikan Moore-Penrose pseudoinverse sebagai

Moore-Penrose pseudoinverse berfungsi seperti "kebalikan terbaik" dari matriks yang tidak persegi. Ia memberikan cara optimal untuk "membatalkan" transformasi linear dalam konteks kuadrat terkecil.

Moore-Penrose pseudoinverse memenuhi empat aksioma Penrose yang menentukan karakteristiknya secara unik

Keempat sifat ini bersifat unik, artinya jika matriks $B$ memenuhi keempat aksioma tersebut, maka secara otomatis $B = A^{\dagger}$. Moore-Penrose pseudoinverse dengan demikian berfungsi sebagai operator solusi tunggal untuk masalah kuadrat terkecil linear.

Penyelesaian Menggunakan Dekomposisi QR

Pendekatan yang lebih stabil secara numerik untuk menyelesaikan sistem persamaan normal menggunakan dekomposisi QR. Untuk matriks $A \in \mathbb{R}^{m \times n}$ dengan peringkat penuh dan $m \geq n$, kita dapat menggunakan dekomposisi QR (tipis) $A = Q_1 R_1$.

Dengan dekomposisi ini, sistem persamaan normal $A^T A x = A^T b$ dapat diselesaikan melalui

Karena $R_1$ adalah matriks segitiga atas yang dapat dibalik, persamaan ini ekuivalen dengan

Sistem segitiga atas ini dapat diselesaikan dengan substitusi mundur, memberikan solusi $x$ secara langsung dan efisien.

Contoh Numerik

Mari kita terapkan metode ini pada contoh konkret. Misalkan kita memiliki data eksperimen yang ingin kita cocokkan dengan polynomial kuadrat. Kita akan menggunakan data berikut

Setiap baris dalam matriks $A$ berformat $[t_i^2, t_i, 1]$ untuk mencari koefisien polynomial $y = at^2 + bt + c$, sedangkan vektor $b$ berisi nilai pengamatan yang bersesuaian.

Proses Dekomposisi QR

Dekomposisi QR dari matriks $A$ menghasilkan

Tahap Penyelesaian

Pertama, kita menghitung $Q_1^T b$ untuk memperoleh

Selanjutnya, kita menyelesaikan sistem segitiga atas $R_1 x = Q_1^T b$ menggunakan substitusi mundur. Karena $R_1$ berbentuk segitiga atas, kita mulai dari persamaan paling bawah.

Dari persamaan ketiga, $-1.73205 x_3 = 3.4806$, sehingga $x_3 = -2.00952$.

Dari persamaan kedua, $5.29150 x_2 = 16.0257$, sehingga $x_2 = 3.02857$.

Dari persamaan pertama, $-14.00000 x_1 - 2.00000(-2.00952) = -9.7143$, sehingga $x_1 = 0.98095$.

Dengan demikian, solusi lengkap adalah

Hasil Fitting

Berdasarkan solusi yang diperoleh, polynomial kuadrat yang paling sesuai dengan data adalah

Visualisasi berikut menunjukkan seberapa baik polynomial ini mewakili data asli

Perbandingan Metode

Untuk menyelesaikan sistem persamaan normal, terdapat dua pendekatan utama yang dapat dibandingkan dari segi komputasi dan stabilitas numerik.

Pendekatan Cholesky melibatkan pembentukan eksplisit matriks $A^T A$ terlebih dahulu, kemudian menerapkan dekomposisi Cholesky karena matriks ini bersifat positif definit. Metode ini memerlukan sekitar $n^2 \cdot m + \frac{1}{6}n^3 + O(n^2) + O(m \cdot n)$ operasi aritmatika. Namun, perkalian dan dekomposisi dapat menjadi sumber propagasi kesalahan yang besar, terutama ketika $m = n$ dimana $\text{cond}(A^T A) \approx \text{cond}(A)^2$.

Pendekatan QR, sebaliknya, dapat menyelesaikan masalah ini dengan stabilitas numerik yang lebih baik dan kompleksitas komputasi yang sebanding. Kompleksitas utama ditentukan oleh $n^2 \cdot m$ operasi untuk dekomposisi QR, sehingga sebanding dengan pendekatan Cholesky. Namun, keunggulan signifikan QR terletak pada fakta bahwa transformasi ortogonal tidak memperburuk kondisi masalah, berbeda dengan pembentukan $A^T A$ dalam metode Cholesky.

Pemilihan metode yang tepat bergantung pada karakteristik data dan tingkat akurasi yang dibutuhkan dalam aplikasi spesifik.