Sistem Persamaan Normal

Syarat Solusi Kuadrat Terkecil

Persamaan normal mengubah syarat optimalitas orde pertama dari masalah kuadrat terkecil linear menjadi sistem persamaan linear.

Masalah kuadrat terkecil mencari $x$ yang membuat $A \cdot x$ sedekat mungkin dengan $b$:

Peminimumnya memenuhi sistem linear berikut:

Persamaan ini disebut persamaan normal karena residual pada titik minimum bersifat normal, atau tegak lurus, terhadap ruang kolom $A$.

Kuadrat Terkecil dan Persamaan Normal

Vektor $\hat{x} \in \mathbb{R}^n$ meminimumkan $\|A \cdot x - b\|_2^2$ jika dan hanya jika memenuhi $A^T A \cdot \hat{x} = A^T b$. Jadi, masalah optimasi dan persamaan normal memiliki himpunan solusi yang sama. Kesetaraan itulah yang mengubah masalah minimisasi menjadi sistem linear yang dapat diselesaikan dengan eliminasi atau faktorisasi.

Residual Tegak Lurus terhadap Ruang Kolom

Ketika $\hat{x}$ meminimumkan $\|A\hat{x} - b\|_2^2$, vektor residual $A\hat{x} - b$ tegak lurus terhadap setiap vektor dalam ruang kolom $A$.

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

Kondisi ortogonalitas ini berlaku untuk setiap vektor $x \in \mathbb{R}^n$. Sifat perkalian dalam memberikan

Karena kesamaan ini berlaku untuk setiap vektor $x$, vektor di dalam tanda kurung harus sama dengan nol:

Dengan memindahkan suku, kita memperoleh $A^TA\hat{x}=A^Tb$, yaitu 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 persamaan normal, suku silang bernilai nol. Yang tersisa adalah:

Norma kuadrat yang ditambahkan tidak negatif. Jadi, kuadrat norma residual pada sembarang $x$ tidak dapat lebih kecil daripada pada $\hat{x}$:

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

Eksistensi dan Keunikan

Persamaan normal konsisten untuk setiap matriks $A \in \mathbb{R}^{m\times n}$ dan setiap vektor $b \in \mathbb{R}^m$ karena peminimum kuadrat terkecil selalu ada dalam dimensi hingga. Peminimumnya unik tepat ketika $A$ memiliki peringkat kolom penuh:

Dalam kondisi tersebut, $A^{\mathsf T}A$ dapat diinverskan dan

Jika $A$ tidak berperingkat penuh, persamaan normal tetap memiliki solusi, tetapi solusinya tidak unik. Untuk sembarang solusi khusus $\hat{x}$, himpunan lengkapnya adalah

Semua vektor parameter tersebut menghasilkan vektor hasil pencocokan $A\hat{x}$ yang sama.

Pembuktian Ruang Nol dan Sifat Definit

Untuk setiap $z\in\mathbb{R}^n$,

Persamaan ini menunjukkan bahwa $A^{\mathsf T}A$ selalu simetris positif semidefinit. Selain itu,

Jadi,

Kesamaan ruang nol ini menunjukkan bahwa $A^{\mathsf T}A$ positif definit tepat ketika $A$ memiliki peringkat kolom penuh.

Peringatan numerik

Sifat positif definit memberikan keunikan dan memungkinkan penyelesaian Cholesky, tetapi tidak menjamin kondisi numerik yang baik. Untuk matriks berperingkat kolom penuh,

Pembentukan $A^{\mathsf T}A$ secara langsung dapat memperbesar kepekaan dan efek pembulatan. Rumus invers membuktikan sebuah identitas aljabar. Dalam perangkat lunak, gunakan $\mathrm{QR}$ untuk kuadrat terkecil berperingkat penuh dan $\mathrm{SVD}$ ketika matriks kekurangan peringkat atau memiliki kondisi yang sangat buruk.

Contoh Dua Pengamatan

Misalkan $A=(1,2)^T$ dan $b=(2,1)^T$. Satu parameter skalar tidak dapat memenuhi kedua pengamatan. Persamaan pertama meminta $x=2$, sedangkan persamaan kedua meminta $x=1/2$. Solusi kuadrat terkecil meminimumkan jumlah kuadrat residual kedua pengamatan.

Residual tegak lurus terhadap garis yang memuat semua prediksi. Perpindahan di sepanjang garis menambahkan kuadrat jarak tak negatif, sesuai dengan pembuktian Pythagoras.