Sistem Linear Berlebih

Jumlah Persamaan Melebihi Jumlah Variabel

Misalkan kita ingin mencocokkan kurva dengan data hasil pengukuran. Sering kali jumlah pengamatan lebih banyak daripada parameter model. Jika setiap pengamatan ditulis sebagai $satu persamaan$ , terbentuklah $sistem linear berlebih$ .

Sebuah sistem disebut berlebih ketika jumlah persamaan $m$ lebih besar daripada jumlah variabel $n$ , sehingga $m > n$ . Sistem seperti ini masih dapat memiliki solusi eksak. Pada data pengukuran, titik-titiknya biasanya tidak persis mengikuti model yang dipilih.

Pencocokan Kuadrat untuk Tujuh Pengamatan

Perhatikan $7$ titik data yang akan dicocokkan dengan sebuah $polinom kuadrat$ .

Data pengamatannya adalah:

$i$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
$t_i$	$-3$	$-2$	$-1$	$0$	$1$	$2$	$3$
$y_i$	$-2{,}2$	$-4{,}2$	$-4{,}2$	$-1{,}8$	$1{,}8$	$8{,}2$	$15{,}8$

Kita mencari parabola berbentuk:

y = a_2 \cdot t^2 + a_1 \cdot t + a_0

Parameter yang belum diketahui berjumlah $3$ , yaitu $a_2$ (koefisien kuadrat), $a_1$ (koefisien linear), dan $a_0$ (suku konstanta).

Menyusun Sistem Persamaan

Substitusi setiap pasangan $(t_i,y_i)$ ke dalam polinom menghasilkan satu persamaan. Jadi, $7$ pengamatan memberikan $7$ persamaan untuk hanya $3$ $koefisien yang belum diketahui$ .

a_2 \cdot (-3)^2 + a_1 \cdot (-3) + a_0 = -2{,}2

Setelah menghitung pangkat setiap $t_i$ , sistemnya menjadi:

9a_2 - 3a_1 + a_0 = -2{,}2

Bentuk Matriks

Sistem persamaan di atas bisa ditulis dalam $bentuk matriks$ $A \cdot x = b$ .

\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} \begin{pmatrix} a_2 \\ a_1 \\ a_0 \end{pmatrix} = \begin{pmatrix} -2{,}2 \\ -4{,}2 \\ -4{,}2 \\ -1{,}8 \\ 1{,}8 \\ 8{,}2 \\ 15{,}8 \end{pmatrix}

Untuk model kuadrat dengan $m$ titik data, susunan yang sama menghasilkan bentuk umum:

\begin{pmatrix} t_1^2 & t_1 & 1 \\ \vdots & \vdots & \vdots \\ t_m^2 & t_m & 1 \end{pmatrix} \begin{pmatrix} a_2 \\ a_1 \\ a_0 \end{pmatrix} = \begin{pmatrix} y_1 \\ \vdots \\ y_m \end{pmatrix}

Mengapa Tidak Ada Solusi Eksak

Dalam contoh ini, matriks $A$ berukuran $7 \times 3$ dan vektor koefisien $x$ berukuran $3 \times 1$ . Jadi, ada $7$ persamaan untuk $3$ variabel.

Solusi eksak ada tepat ketika $\operatorname{rank}(A)=\operatorname{rank}(A\mid b)$ . Ukuran matriks saja belum menentukan hal itu.

Ketiga kolom $A$ bebas linear. Alasannya, polinom $c_2t^2+c_1t+c_0$ berderajat paling tinggi $2$ yang bernilai nol pada ketujuh nilai $t_i$ yang berbeda harus merupakan polinom nol. Jadi $\operatorname{rank}(A)=3$ .

Setelah vektor $b$ ditambahkan, terbentuk matriks diperluas $(A\mid b)$ . Empat baris pertama saja sudah menghasilkan minor tak nol

\det\begin{pmatrix}9&-3&1&-2{,}2\\4&-2&1&-4{,}2\\1&-1&1&-4{,}2\\0&0&1&-1{,}8\end{pmatrix}=-\frac45

Minor tak nol ini menunjukkan bahwa $\operatorname{rank}(A\mid b)=4$ .

Karena $\operatorname{rank}(A) \ne \operatorname{rank}(A\mid b)$ , sistem ini $tidak memiliki solusi eksak$ . Tidak ada satu polinom kuadrat yang melewati seluruh $7$ pengamatan.

Solusi dengan Kuadrat Terkecil

Jika sistem berlebih tidak memiliki solusi eksak, kita dapat mencari polinom yang paling dekat dengan semua pengamatan menurut kriteria $kuadrat terkecil$ .

Untuk pengamatan ke- $i$ , residual vertikalnya adalah $r_i = y_i-(a_2t_i^2+a_1t_i+a_0)$ . Metode kuadrat terkecil memilih koefisien yang $meminimalkan jumlah kuadrat residual$ :

\min_{a_2,a_1,a_0}\sum_{i=1}^{7}\left[y_i-(a_2t_i^2+a_1t_i+a_0)\right]^2

Kriteria ini memberi penalti lebih besar pada selisih yang besar dan menghasilkan tepat satu parabola terbaik karena $A$ memiliki peringkat kolom penuh. Persamaan normalnya adalah

A^TA=\begin{pmatrix}196&0&28\\0&28&0\\28&0&7\end{pmatrix}

Persamaan tengah langsung memberi koefisien linear. Dari persamaan terakhir, nyatakan konstanta melalui koefisien kuadrat, lalu substitusikan ke persamaan pertama.

28a_1=\frac{424}{5}\quad\Rightarrow\quad a_1=\frac{106}{35}

Penyelesaiannya memberikan

\hat x=\begin{pmatrix}\hat a_2\\\hat a_1\\\hat a_0\end{pmatrix}=\begin{pmatrix}\frac{103}{105}\\\frac{106}{35}\\-\frac{211}{105}\end{pmatrix}

Nilai hasil pencocokan tidak sama dengan setiap observasi, dan memang itulah yang diharapkan. Vektor residualnya adalah

r=b-A\hat x=\begin{pmatrix}\frac1{15}\\-\frac2{35}\\-\frac17\\\frac{22}{105}\\-\frac15\\\frac8{35}\\-\frac{11}{105}\end{pmatrix}

Vektor residual $r$ memenuhi

A^Tr=0

Persamaan $A^Tr=0$ berarti galat yang tersisa ortogonal terhadap setiap kolom $A$ . Secara geometri, $A\hat x$ merupakan proyeksi ortogonal $b$ ke ruang kolom $A$ .

Sistem berlebih banyak muncul dalam rekayasa dan sains karena eksperimen biasanya menghasilkan banyak pengukuran untuk model dengan sedikit parameter. Kuadrat terkecil memanfaatkan seluruh pengukuran tanpa menganggap data yang berisik cocok sempurna dengan model.

Kurva memperlihatkan hasil pencocokan, sedangkan titik menandai pengamatan. Putar atau perbesar diagram untuk membandingkan titik dengan kurva. Selisih vertikal setiap titik merupakan residual pada nilai waktu yang sama.

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]$