# Nakafa Learning Content > For AI agents: use [llms.txt](https://nakafa.com/llms.txt) for the site index. Markdown versions are available by appending `.md` to content URLs or sending `Accept: text/markdown`. URL: https://nakafa.com/id/materi/ai-ds/metode-linear-ai/solusi-sistem-persamaan-normal Source: https://raw.githubusercontent.com/nakafaai/nakafa.com/refs/heads/main/packages/contents/material/lesson/ai-ds/linear-methods/normal-equation-solution/id.mdx Implementasikan solusi persamaan normal dengan dekomposisi QR dan pseudoinverse. Pelajari metode numerik, fitting polynomial, dan perbandingan stabilitas. --- ## Sifat Fundamental Sistem persamaan normal $$A^T A x = A^T b$$ 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. Visible text: Sistem persamaan normal 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 \in \mathbb{R}^{m \times n}$$ dengan $$m \geq n$$, sistem persamaan normal $$A^T A x = A^T b$$ selalu memiliki solusi. Lebih spesifik lagi, sistem ini memiliki solusi unik tepat ketika matriks $$A$$ memiliki peringkat penuh, yaitu ketika $$\text{Peringkat}(A) = n$$. Dalam kondisi ini, solusi dapat dinyatakan sebagai $$\hat{x} = (A^T A)^{-1} A^T b$$. Visible text: Untuk matriks 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 . Ketika matriks $$A$$ tidak memiliki peringkat penuh, himpunan solusi sistem persamaan normal berbentuk $$\hat{x} + \text{Kernel}(A)$$, dimana $$\hat{x}$$ adalah sembarang solusi khusus dari sistem tersebut. Visible text: Ketika matriks tidak memiliki peringkat penuh, himpunan solusi sistem persamaan normal berbentuk , dimana adalah sembarang solusi khusus dari sistem tersebut. ### Mengapa Sistem Selalu Dapat Diselesaikan Alasan mendasar mengapa sistem persamaan normal selalu memiliki solusi terletak pada konsep proyeksi ortogonal. Proyeksi ortogonal dari vektor $$b$$ ke ruang kolom $$\{Ax : x \in \mathbb{R}^n\}$$ selalu ada dan merupakan solusi dari masalah kuadrat terkecil linear, yang secara otomatis juga merupakan solusi sistem persamaan normal. Visible text: Alasan mendasar mengapa sistem persamaan normal selalu memiliki solusi terletak pada konsep proyeksi ortogonal. Proyeksi ortogonal dari vektor ke ruang kolom 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 $$\hat{x} + \text{Kernel}(A)$$, misalkan $$\tilde{x}$$ adalah solusi lain dari sistem $$A^T A \tilde{x} = A^T b$$. Maka $$\tilde{x}$$ adalah solusi sistem persamaan normal jika dan hanya jika $$A^T A(\tilde{x} - \hat{x}) = 0$$, yang ekuivalen dengan $$(\tilde{x} - \hat{x})^T A^T A(\tilde{x} - \hat{x}) = 0$$, yang selanjutnya ekuivalen dengan $$A(\tilde{x} - \hat{x}) = 0$$, atau dengan kata lain $$\tilde{x} - \hat{x} \in \text{Kernel}(A)$$. Visible text: Untuk memahami mengapa solusi lain berbentuk , misalkan adalah solusi lain dari sistem . Maka adalah solusi sistem persamaan normal jika dan hanya jika , yang ekuivalen dengan , yang selanjutnya ekuivalen dengan , atau dengan kata lain . ## Moore-Penrose Pseudoinverse Untuk matriks $$A \in \mathbb{R}^{m \times n}$$ dengan $$m \geq n$$ dan $$\text{Peringkat}(A) = n$$, kita dapat mendefinisikan Moore-Penrose pseudoinverse sebagai Visible text: Untuk matriks dengan dan , kita dapat mendefinisikan Moore-Penrose pseudoinverse sebagai ```math A^{\dagger} = (A^T A)^{-1} A^T ``` 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 Component: MathContainer Children: ```math AA^{\dagger}A = A ``` ```math A^{\dagger}AA^{\dagger} = A^{\dagger} ``` ```math (AA^{\dagger})^T = AA^{\dagger} ``` ```math (A^{\dagger}A)^T = A^{\dagger}A ``` Keempat sifat ini bersifat unik, artinya jika matriks $$B$$ memenuhi keempat aksioma tersebut, maka secara otomatis $$B = A^{\dagger}$$. Moore-Penrose pseudoinverse dengan demikian berfungsi sebagai operator solusi tunggal untuk masalah kuadrat terkecil linear. Visible text: Keempat sifat ini bersifat unik, artinya jika matriks memenuhi keempat aksioma tersebut, maka secara otomatis . Moore-Penrose pseudoinverse dengan demikian berfungsi sebagai operator solusi tunggal untuk masalah kuadrat terkecil linear. ## Penyelesaian Menggunakan Dekomposisi QR Pendekatan yang lebih stabil secara numerik untuk menyelesaikan sistem persamaan normal menggunakan dekomposisi QR. Untuk matriks $$A \in \mathbb{R}^{m \times n}$$ dengan peringkat penuh dan $$m \geq n$$, kita dapat menggunakan dekomposisi QR (tipis) $$A = Q_1 R_1$$. Visible text: Pendekatan yang lebih stabil secara numerik untuk menyelesaikan sistem persamaan normal menggunakan dekomposisi QR. Untuk matriks dengan peringkat penuh dan , kita dapat menggunakan dekomposisi QR (tipis) . Dengan dekomposisi ini, sistem persamaan normal $$A^T A x = A^T b$$ dapat diselesaikan melalui Visible text: Dengan dekomposisi ini, sistem persamaan normal dapat diselesaikan melalui ```math A^T A x = R_1^T Q_1^T Q_1 R_1 x = R_1^T R_1 x = R_1^T Q_1^T b = A^T b ``` Karena $$R_1$$ adalah matriks segitiga atas yang dapat dibalik, persamaan ini ekuivalen dengan Visible text: Karena adalah matriks segitiga atas yang dapat dibalik, persamaan ini ekuivalen dengan ```math R_1 x = Q_1^T b ``` Sistem segitiga atas ini dapat diselesaikan dengan substitusi mundur, memberikan solusi $$x$$ secara langsung dan efisien. Visible text: Sistem segitiga atas ini dapat diselesaikan dengan substitusi mundur, memberikan solusi secara langsung dan efisien. ## Contoh Numerik 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 Component: MathContainer Children: ```math 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} ``` ```math b = \begin{pmatrix} -2.2 \\ -4.2 \\ -4.2 \\ -1.8 \\ 1.8 \\ 8.2 \\ 15.8 \end{pmatrix} ``` Setiap baris dalam matriks $$A$$ berformat $$[t_i^2, t_i, 1]$$ untuk mencari koefisien polynomial $$y = at^2 + bt + c$$, sedangkan vektor $$b$$ berisi nilai pengamatan yang bersesuaian. Visible text: Setiap baris dalam matriks berformat untuk mencari koefisien polynomial , sedangkan vektor berisi nilai pengamatan yang bersesuaian. ### Proses Dekomposisi QR Dekomposisi QR dari matriks $$A$$ menghasilkan Visible text: Dekomposisi QR dari matriks menghasilkan Component: MathContainer Children: ```math Q_1 = \begin{pmatrix} -0.64286 & -0.56695 & 0.16496 \\ -0.28571 & -0.37796 & -0.24744 \\ -0.07143 & -0.18898 & -0.49487 \\ -0.00000 & 0.00000 & -0.57735 \\ -0.07143 & 0.18898 & -0.49487 \\ -0.28571 & 0.37796 & -0.24744 \\ -0.64286 & 0.56695 & 0.16496 \end{pmatrix} ``` ```math R_1 = \begin{pmatrix} -14.00000 & -0.00000 & -2.00000 \\ 0.00000 & 5.29150 & 0.00000 \\ 0.00000 & 0.00000 & -1.73205 \end{pmatrix} ``` ### Tahap Penyelesaian Pertama, kita menghitung $$Q_1^T b$$ untuk memperoleh Visible text: Pertama, kita menghitung untuk memperoleh ```math Q_1^T b = \begin{pmatrix} -9.7143 \\ 16.0257 \\ 3.4806 \end{pmatrix} ``` Selanjutnya, kita menyelesaikan sistem segitiga atas $$R_1 x = Q_1^T b$$ menggunakan substitusi mundur. Karena $$R_1$$ berbentuk segitiga atas, kita mulai dari persamaan paling bawah. Visible text: Selanjutnya, kita menyelesaikan sistem segitiga atas menggunakan substitusi mundur. Karena berbentuk segitiga atas, kita mulai dari persamaan paling bawah. Dari persamaan ketiga, $$-1.73205 x_3 = 3.4806$$, sehingga $$x_3 = -2.00952$$. Visible text: Dari persamaan ketiga, , sehingga . Dari persamaan kedua, $$5.29150 x_2 = 16.0257$$, sehingga $$x_2 = 3.02857$$. Visible text: Dari persamaan kedua, , sehingga . Dari persamaan pertama, $$-14.00000 x_1 - 2.00000(-2.00952) = -9.7143$$, sehingga $$x_1 = 0.98095$$. Visible text: Dari persamaan pertama, , sehingga . Dengan demikian, solusi lengkap adalah ```math \hat{x} = \begin{pmatrix} 0.98095 \\ 3.02857 \\ -2.00952 \end{pmatrix} ``` ### Hasil Fitting Berdasarkan solusi yang diperoleh, polynomial kuadrat yang paling sesuai dengan data adalah ```math y = 0.98095 \cdot t^2 + 3.02857 \cdot t - 2.00952 ``` Visualisasi berikut menunjukkan seberapa baik polynomial ini mewakili data asli Component: LineEquation Props: - title: Fitting Polynomial Kuadrat - description: Kurva polynomial yang dihasilkan dari solusi sistem persamaan normal. - cameraPosition: [15, 10, 15] - data: (() => { // Data asli dari matriks A (kolom t) dan vektor b const originalData = [ [-3, -2.2], [-2, -4.2], [-1, -4.2], [0, -1.8], [1, 1.8], [2, 8.2], [3, 15.8] ]; // Koefisien polynomial dari solusi sistem persamaan normal const a = 0.98095; const b = 3.02857; const c = -2.00952; return [ { points: Array.from({ length: 50 }, (_, i) => { const t = -3 + (i * 6) / 49; const y = a * t * t + b * t + c; return { x: t, y: y, z: 0 }; }), color: getColor("CYAN"), smooth: true, showPoints: false }, { points: originalData.map(([t, y]) => ({ x: t, y: y, z: 0 })), color: getColor("ORANGE"), smooth: false, showPoints: true } ]; })() ## Perbandingan Metode Untuk menyelesaikan sistem persamaan normal, terdapat dua pendekatan utama yang dapat dibandingkan dari segi komputasi dan stabilitas numerik. Pendekatan Cholesky melibatkan pembentukan eksplisit matriks $$A^T A$$ terlebih dahulu, kemudian menerapkan dekomposisi Cholesky karena matriks ini bersifat positif definit. Metode ini memerlukan sekitar $$n^2 \cdot m + \frac{1}{6}n^3 + O(n^2) + O(m \cdot n)$$ operasi aritmatika. Namun, perkalian dan dekomposisi dapat menjadi sumber propagasi kesalahan yang besar, terutama ketika $$m = n$$ dimana $$\text{cond}(A^T A) \approx \text{cond}(A)^2$$. Visible text: Pendekatan Cholesky melibatkan pembentukan eksplisit matriks terlebih dahulu, kemudian menerapkan dekomposisi Cholesky karena matriks ini bersifat positif definit. Metode ini memerlukan sekitar operasi aritmatika. Namun, perkalian dan dekomposisi dapat menjadi sumber propagasi kesalahan yang besar, terutama ketika dimana . Pendekatan QR, sebaliknya, dapat menyelesaikan masalah ini dengan stabilitas numerik yang lebih baik dan kompleksitas komputasi yang sebanding. Kompleksitas utama ditentukan oleh $$n^2 \cdot 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 $$A^T A$$ dalam metode Cholesky. Visible text: Pendekatan QR, sebaliknya, dapat menyelesaikan masalah ini dengan stabilitas numerik yang lebih baik dan kompleksitas komputasi yang sebanding. Kompleksitas utama ditentukan oleh 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 dalam metode Cholesky. Pemilihan metode yang tepat bergantung pada karakteristik data dan tingkat akurasi yang dibutuhkan dalam aplikasi spesifik.