Masalah Kuadrat Terkecil Linear

Dari sistem tak konsisten menuju pencocokan terbaik

Misalkan $A \in \mathbb{R}^{m \times n}$ , $x \in \mathbb{R}^n$ , dan $b \in \mathbb{R}^m$ . Perhatikan sistem berikut.

Ax=b

Jika $b$ tidak berada dalam ruang kolom $A$ , sistem tersebut tidak memiliki solusi eksak. Keadaan ini sering terjadi ketika model dicocokkan dengan data pengukuran yang mengandung kesalahan acak atau ketika sistem memiliki lebih banyak persamaan daripada variabel dan persamaan-persamaan itu tidak konsisten.

Jika tidak ada vektor $x$ yang memenuhi $Ax=b$ secara eksak, definisikan residual

e(x)=Ax-b

Kita mencari vektor $x$ yang menghasilkan $residual paling kecil$ . Masalah kuadrat terkecil linear ditulis sebagai berikut.

\hat{x}\in\operatorname*{arg\,min}_{x\in\mathbb{R}^n}\|Ax-b\|_2^2

Karena residual memiliki $m$ komponen, fungsi objektifnya dapat diuraikan menjadi

\|Ax-b\|_2^2=\sum_{i=1}^{m}(Ax-b)_i^2

Penguadratan membuat setiap kontribusi tidak negatif dan memberi penalti yang lebih besar kepada komponen residual yang besar.

Syarat geometris

Vektor $A\hat{x}$ adalah titik di $\operatorname{col}(A)$ yang paling dekat dengan $b$ menurut jarak Euklides. Pada solusi optimal, $residual tegak lurus terhadap setiap kolom$ $A$ :

A^{\mathsf T}(A\hat{x}-b)=0

Persamaan kedua disebut $persamaan normal$ .

Proyeksi ortogonal pada masalah kuadrat terkecil

Vektor biru berujung di

A\hat{x}

, vektor jingga berujung di

b

, dan vektor ungu adalah residual

A\hat{x}-b

$x$: $[0; 3]$
$y$: $[0; 3]$
$z$: $[0; 6]$
Garis: 3

Diagram memberi label pada vektor target $b$ , titik proyeksi $A\hat{x}$ , dan residual $A\hat{x}-b$ di antara keduanya. Vektor biru $A\hat{x}$ berada di dalam ruang kolom. Syarat ortogonal di atas membuktikan bahwa titik proyeksi $A\hat{x}$ itu paling dekat dengan $b$ .

Mencocokkan Satu Konstanta dengan Tiga Observasi

Misalkan satu konstanta $x$ harus mencocokkan tiga pengamatan $1$ , $2$ , dan $6$ . Gunakan matriks dan vektor berikut.

A=\begin{pmatrix}1\\1\\1\end{pmatrix},\qquad b=\begin{pmatrix}1\\2\\6\end{pmatrix}

Fungsi objektif untuk contoh ini adalah

\begin{aligned} F(x) &=(x-1)^2+(x-2)^2 \\ &\quad{}+(x-6)^2 \end{aligned}

Dengan menetapkan $turunannya sama dengan nol$ , kita memperoleh $\hat{x}=3$ . Vektor hasil pencocokan dan residualnya adalah

A\hat{x}=\begin{pmatrix}3\\3\\3\end{pmatrix}

Jumlah komponen residual sama dengan nol, sehingga

A^{\mathsf T}(A\hat{x}-b)=2+1-3=0

Hasil nol tersebut memenuhi persamaan normal.

Norma residual lain

Norma yang dipilih menentukan $jenis galat$ yang diprioritaskan oleh pencocokan.

Fungsi objektif	Hal yang dikendalikan
$\displaystyle\min_x\\|Ax-b\\|_2^2=\min_x\sum_{i=1}^{m}(Ax-b)_i^2$	Memberi penalti kuadratik pada residual besar dan menghasilkan proyeksi kuadrat terkecil biasa.
$\displaystyle\min_x\\|Ax-b\\|_1=\min_x\sum_{i=1}^{m}\lvert(Ax-b)_i\rvert$	Menggunakan penalti linear, sehingga residual besar yang sesekali muncul tidak seberpengaruh pada kerugian kuadrat.
$\displaystyle\min_x\\|Ax-b\\|_\infty=\min_x\max_{1\le i\le m}\lvert(Ax-b)_i\rvert$	Meminimumkan residual absolut terburuk.

Formulasi $\ell_1$ dan $\ell_\infty$ dapat ditulis ulang sebagai program linear. Kecocokannya tetap bergantung pada proses pembentukan data dan kriteria galat yang penting bagi penerapan tersebut.

Untuk data yang sama, yaitu 1, 2, dan 6, pilihan norma menghasilkan konstanta yang berbeda. Kuadrat terkecil memilih rata-rata, jumlah nilai mutlak memilih median, dan galat maksimum terkecil menyeimbangkan jarak ke kedua nilai ekstrem.

Kriteria	Konstanta optimal	Nilai objektif minimum
$\ell_2^2$	$(1+2+6)/3=3$	$2^2+1^2+(-3)^2=14$
$\ell_1$	$2$	$1+0+4=5$
$\ell_\infty$	$(1+6)/2=7/2$	$\max(5/2,3/2,5/2)=5/2$

Memilih Metode Numerik yang Stabil

Jika $A$ memiliki $peringkat kolom penuh$ , peminimum kuadrat terkecil bersifat unik. Persamaan normal kemudian memberikan

\hat{x}=(A^{\mathsf T}A)^{-1}A^{\mathsf T}b

Identitas ini menyatakan peminimum unik ketika $A$ memiliki peringkat kolom penuh. Jangan menghitung solusi kuadrat terkecil dengan membentuk invers secara eksplisit. Pilih metode numerik berdasarkan peringkat dan kondisi matriks:

gunakan faktorisasi $\mathrm{QR}$ untuk penyelesaian kuadrat terkecil berperingkat penuh yang stabil
gunakan $\mathrm{SVD}$ jika kekurangan peringkat atau kondisi buruk perlu diperhitungkan
gunakan invers semu untuk memilih solusi bernorma minimum ketika peminimum tidak unik

Kuadrat terkecil juga dapat dijelaskan melalui model statistik berikut.

b=Ax_*+\varepsilon,\qquad \varepsilon\sim\mathcal{N}(0,\sigma^2I),\quad \sigma^2>0

Jika $A$ tetap dan galat Gaussian saling bebas dengan varians yang sama, metode kuadrat terkecil menghasilkan estimator kemungkinan maksimum untuk $x_*$ . Galat yang berkorelasi atau memiliki varians berbeda memerlukan bobot yang mengikuti kovarians galat.