Sistem persamaan normal ATAx=ATb 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∈Rm×n dengan , sistem persamaan normal selalu memiliki solusi. Lebih spesifik lagi, sistem ini memiliki solusi unik tepat ketika matriks memiliki peringkat penuh, yaitu ketika . Dalam kondisi ini, solusi dapat dinyatakan sebagai .
m≥n
ATAx=ATb
A
Peringkat(A)=n
x^=(ATA)−1ATb
Ketika matriks A tidak memiliki peringkat penuh, himpunan solusi sistem persamaan normal berbentuk x^+Kernel(A), dimana x^ adalah sembarang solusi khusus dari sistem tersebut.
Alasan mendasar mengapa sistem persamaan normal selalu memiliki solusi terletak pada konsep proyeksi ortogonal. Proyeksi ortogonal dari vektor b ke ruang kolom {Ax:x∈Rn} 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 x^+Kernel(A), misalkan x~ adalah solusi lain dari sistem ATAx~=ATb. Maka x~ adalah solusi sistem persamaan normal jika dan hanya jika ATA(x~−x^)=0, yang ekuivalen dengan (x~−x^)TATA(x~−x^)=0, yang selanjutnya ekuivalen dengan A(x~−x^)=0, atau dengan kata lain x~−x^∈Kernel(A).
Untuk matriks A∈Rm×n dengan m≥n dan Peringkat(A)=n, kita dapat mendefinisikan Moore-Penrose pseudoinverse sebagai
A†=(ATA)−1AT
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
AA†A=A
A†AA†=A†
(AA†)T=AA†
(A†A)T=A†A
Keempat sifat ini bersifat unik, artinya jika matriks B memenuhi keempat aksioma tersebut, maka secara otomatis B=A†. Moore-Penrose pseudoinverse dengan demikian berfungsi sebagai operator solusi tunggal untuk masalah kuadrat terkecil linear.
Pendekatan yang lebih stabil secara numerik untuk menyelesaikan sistem persamaan normal menggunakan dekomposisi QR. Untuk matriks A∈Rm×n dengan peringkat penuh dan m≥n, kita dapat menggunakan dekomposisi QR (tipis) A=Q1R1.
Dengan dekomposisi ini, sistem persamaan normal ATAx=ATb dapat diselesaikan melalui
ATAx=R1TQ1TQ1R1x=R1TR1x=R1TQ1Tb=ATb
Karena R1 adalah matriks segitiga atas yang dapat dibalik, persamaan ini ekuivalen dengan
R1x=Q1Tb
Sistem segitiga atas ini dapat diselesaikan dengan substitusi mundur, memberikan solusi x secara langsung dan efisien.
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
A=9410149−3−2−101231111111
b=−2.2−4.2−4.2−1.81.88.215.8
Setiap baris dalam matriks A berformat [ti2,ti,1] untuk mencari koefisien polynomial y=at2+bt+c, sedangkan vektor b berisi nilai pengamatan yang bersesuaian.
Selanjutnya, kita menyelesaikan sistem segitiga atas R1x=Q1Tb menggunakan substitusi mundur. Karena R1 berbentuk segitiga atas, kita mulai dari persamaan paling bawah.
Dari persamaan ketiga, −1.73205x3=3.4806, sehingga x3=−2.00952.
Dari persamaan kedua, 5.29150x2=16.0257, sehingga x2=3.02857.
Dari persamaan pertama, −14.00000x1−2.00000(−2.00952)=−9.7143, sehingga x1=0.98095.
Untuk menyelesaikan sistem persamaan normal, terdapat dua pendekatan utama yang dapat dibandingkan dari segi komputasi dan stabilitas numerik.
Pendekatan Cholesky melibatkan pembentukan eksplisit matriks ATA terlebih dahulu, kemudian menerapkan dekomposisi Cholesky karena matriks ini bersifat positif definit. Metode ini memerlukan sekitar n2⋅m+61n3+O(n2)+O(m⋅n) operasi aritmatika. Namun, perkalian dan dekomposisi dapat menjadi sumber propagasi kesalahan yang besar, terutama ketika m=n dimana cond(ATA)≈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 n2⋅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 ATA dalam metode Cholesky.
Pemilihan metode yang tepat bergantung pada karakteristik data dan tingkat akurasi yang dibutuhkan dalam aplikasi spesifik.
