Menyelesaikan Persamaan Normal

Masalah yang Diselesaikan

Diberikan $A \in \mathbb{R}^{m \times n}$ dan $b \in \mathbb{R}^m$ , masalah kuadrat terkecil linear mencari vektor parameter yang membuat residual sekecil mungkin:

\min_x \|Ax-b\|_2^2

Setiap peminimum memenuhi persamaan normal

A^T A\hat{x}=A^T b

Persamaan ini $selalu konsisten$ . Peminimumnya unik tepat ketika $\operatorname{rank}(A)=n$ , yang mensyaratkan $m\ge n$ . Dalam kasus rank kolom penuh ini,

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

Ketika $A$ kekurangan rank, vektor hasil fitting $A\hat{x}$ tetap unik, tetapi vektor parameternya tidak. Jika $\hat{x}$ adalah salah satu solusi, semua solusi berada dalam

\hat{x}+\ker(A)

Ruang kolom $A$ adalah subruang tertutup berdimensi hingga dari $\mathbb{R}^m$ . Karena itu, $b$ memiliki $proyeksi ortogonal yang unik$ ke ruang tersebut. Setiap $\hat{x}$ yang memenuhi $A\hat{x}=\operatorname{proj}_{\operatorname{col}(A)}b$ merupakan solusi kuadrat terkecil.

Persamaan normal menyatakan geometri yang sama karena

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

Persamaan ini berarti residual $A\hat{x}-b$ tegak lurus terhadap setiap kolom $A$ .

Pseudoinvers Moore Penrose

Pseudoinvers Moore-Penrose didefinisikan untuk setiap matriks real, termasuk matriks persegi panjang dan matriks yang kekurangan rank. Tuliskan dekomposisi nilai singular sebagai

A=U\Sigma V^T

Persamaan di atas merupakan dekomposisi nilai singular. Untuk membentuk pseudoinvers, ganti setiap nilai singular tak nol $\sigma_i$ dengan $1/\sigma_i$ dan biarkan setiap nilai singular nol tetap nol. Hasilnya adalah

\Sigma^{\dagger}_{ii}=\begin{cases}1/\sigma_i,&\sigma_i>0,\\0,&\sigma_i=0,\end{cases}

Vektor $x^{\dagger}$ adalah $solusi kuadrat terkecil unik dengan norma Euklides minimum$ . Ketika $A$ memiliki rank kolom penuh, definisi umum tersebut menyederhana menjadi

A^{\dagger}=(A^T A)^{-1}A^T

Pseudoinvers ditentukan secara unik oleh empat identitas Penrose:

AA^{\dagger}A=A

Penyelesaian Langsung dengan Dekomposisi QR

Untuk matriks dengan rank kolom penuh dan $m\ge n$ , gunakan dekomposisi $\mathrm{QR}$ tipis

A=Q_1R_1,\qquad Q_1^TQ_1=I

Objektif kuadrat terkecil terpisah menjadi

\begin{aligned} \|Ax-b\|_2^2 &=\|R_1x-Q_1^Tb\|_2^2 \\ &\quad{}+\|(I-Q_1Q_1^T)b\|_2^2 \end{aligned}

Suku kedua tidak bergantung pada $x$ . Karena itu, peminimum diperoleh dengan menyelesaikan $sistem segitiga atas$

R_1\hat{x}=Q_1^Tb

Jalur ini menyelesaikan masalah kuadrat terkecil semula secara langsung. Kita tidak membentuk $A^TA$ lalu menyelesaikan persamaan normal.

Contoh Fitting Polinomial

Faktor numerik dan koefisien berikut $dibulatkan menjadi lima angka di belakang koma$ . Kesamaan matriks eksak berlaku sebelum pembulatan.

Cocokkan $y=at^2+bt+c$ ke tujuh pengamatan. Matriks desain dan vektor pengamatannya adalah

A=\begin{pmatrix}9&-3&1\\4&-2&1\\1&-1&1\\0&0&1\\1&1&1\\4&2&1\\9&3&1\end{pmatrix}

Setiap baris $A$ adalah $[t_i^2,t_i,1]$ . Salah satu dekomposisi $\mathrm{QR}$ tipis yang valid adalah

Q_1=\begin{pmatrix}-0{,}64286&-0{,}56695&0{,}16496\\-0{,}28571&-0{,}37796&-0{,}24744\\-0{,}07143&-0{,}18898&-0{,}49487\\0&0&-0{,}57735\\-0{,}07143&0{,}18898&-0{,}49487\\-0{,}28571&0{,}37796&-0{,}24744\\-0{,}64286&0{,}56695&0{,}16496\end{pmatrix}

Tanda kolom $Q_1$ dan baris $R_1$ yang bersesuaian dapat berbeda antarimplementasi $\mathrm{QR}$ yang valid. Hasil kali $Q_1R_1$ dan hasil fitting akhirnya tidak berubah.

Pertama, hitung

Q_1^Tb=\begin{pmatrix}-9{,}71429\\16{,}02569\\3{,}48060\end{pmatrix}

Kemudian gunakan $substitusi mundur$ :

\begin{aligned} &-1{,}73205x_3=3{,}48060 \\ &\Longrightarrow \\ &x_3=-2{,}00952 \end{aligned}

Dengan demikian,

\hat{x}=\begin{pmatrix}0{,}98095\\3{,}02857\\-2{,}00952\end{pmatrix}

Fitting kuadrat terkecil

\hat{y}(t)=0{,}98095t^2+3{,}02857t-2{,}00952

Kurva sian adalah polinomial hasil fitting, sedangkan titik jingga adalah tujuh pengamatan dalam

b

$x$: $[-3; 3]$
$y$: $[-4{,}35; 15{,}9]$

Memilih Metode Numerik

Metode	Perkiraan biaya padat untuk $m\ge n$	Kekuatan utama	Keterbatasan utama
Persamaan normal dan Cholesky	bentuk $A^TA$ dalam $O(mn^2)$ , lalu faktorkan dalam sekitar $\frac{1}{3}n^3$ flop	cepat ketika masalah terkondisi baik dan ber-rank penuh	$\kappa_2(A^TA)=\kappa_2(A)^2$
$\mathrm{QR}$ Householder	sekitar $2mn^2-\frac{2}{3}n^3$ flop	tidak membentuk $A^TA$ dan biasanya lebih stabil	memerlukan varian yang peka terhadap rank ketika kolom saling bergantung
$\mathrm{SVD}$	lebih mahal daripada $\mathrm{QR}$	memperlihatkan rank dan memberikan $solusi bernorma minimum$	biaya tertinggi di antara ketiganya

Gunakan $\mathrm{QR}$ sebagai pilihan umum untuk masalah padat ber-rank penuh. Gunakan $\mathrm{SVD}$ ketika matriks kekurangan rank, kondisinya sangat buruk, atau solusi bernorma minimum dibutuhkan. Bentuk matriks normal hanya jika peningkatan kecepatannya sepadan dengan penurunan stabilitas numerik. Jangan menghitung invers secara eksplisit dalam kode produksi.