# Nakafa Framework: LLM

URL: /id/subject/university/bachelor/ai-ds/linear-methods/normal-equation-solution
Source: https://raw.githubusercontent.com/nakafaai/nakafa.com/refs/heads/main/packages/contents/subject/university/bachelor/ai-ds/linear-methods/normal-equation-solution/id.mdx

Output docs content for large language models.

---

export const metadata = {
  title: "Solusi Sistem Persamaan Normal",
  description: "Implementasikan solusi persamaan normal dengan dekomposisi QR dan pseudoinverse. Pelajari metode numerik, fitting polynomial, dan perbandingan stabilitas.",
  authors: [{ name: "Nabil Akbarazzima Fatih" }],
  date: "07/15/2025",
  subject: "Metode Linear AI",
};

import { getColor } from "@repo/design-system/lib/color";
import { LineEquation } from "@repo/design-system/components/contents/line-equation";

## Sifat Fundamental

Sistem persamaan normal <InlineMath math="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.

Untuk matriks <InlineMath math="A \in \mathbb{R}^{m \times n}" /> dengan <InlineMath math="m \geq n" />, sistem persamaan normal <InlineMath math="A^T A x = A^T b" /> selalu memiliki solusi. Lebih spesifik lagi, sistem ini memiliki solusi unik tepat ketika matriks <InlineMath math="A" /> memiliki peringkat penuh, yaitu ketika <InlineMath math="\text{Peringkat}(A) = n" />. Dalam kondisi ini, solusi dapat dinyatakan sebagai <InlineMath math="\hat{x} = (A^T A)^{-1} A^T b" />.

Ketika matriks <InlineMath math="A" /> tidak memiliki peringkat penuh, himpunan solusi sistem persamaan normal berbentuk <InlineMath math="\hat{x} + \text{Kernel}(A)" />, dimana <InlineMath math="\hat{x}" /> 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 <InlineMath math="b" /> ke ruang kolom <InlineMath math="\{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.

Untuk memahami mengapa solusi lain berbentuk <InlineMath math="\hat{x} + \text{Kernel}(A)" />, misalkan <InlineMath math="\tilde{x}" /> adalah solusi lain dari sistem <InlineMath math="A^T A \tilde{x} = A^T b" />. Maka <InlineMath math="\tilde{x}" /> adalah solusi sistem persamaan normal jika dan hanya jika <InlineMath math="A^T A(\tilde{x} - \hat{x}) = 0" />, yang ekuivalen dengan <InlineMath math="(\tilde{x} - \hat{x})^T A^T A(\tilde{x} - \hat{x}) = 0" />, yang selanjutnya ekuivalen dengan <InlineMath math="A(\tilde{x} - \hat{x}) = 0" />, atau dengan kata lain <InlineMath math="\tilde{x} - \hat{x} \in \text{Kernel}(A)" />.

## Moore-Penrose Pseudoinverse

Untuk matriks <InlineMath math="A \in \mathbb{R}^{m \times n}" /> dengan <InlineMath math="m \geq n" /> dan <InlineMath math="\text{Peringkat}(A) = n" />, kita dapat mendefinisikan Moore-Penrose pseudoinverse sebagai

<BlockMath 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

<MathContainer>
<BlockMath math="AA^{\dagger}A = A" />
<BlockMath math="A^{\dagger}AA^{\dagger} = A^{\dagger}" />
<BlockMath math="(AA^{\dagger})^T = AA^{\dagger}" />
<BlockMath math="(A^{\dagger}A)^T = A^{\dagger}A" />
</MathContainer>

Keempat sifat ini bersifat unik, artinya jika matriks <InlineMath math="B" /> memenuhi keempat aksioma tersebut, maka secara otomatis <InlineMath math="B = A^{\dagger}" />. 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 <InlineMath math="A \in \mathbb{R}^{m \times n}" /> dengan peringkat penuh dan <InlineMath math="m \geq n" />, kita dapat menggunakan dekomposisi QR (tipis) <InlineMath math="A = Q_1 R_1" />.

Dengan dekomposisi ini, sistem persamaan normal <InlineMath math="A^T A x = A^T b" /> dapat diselesaikan melalui

<BlockMath 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 <InlineMath math="R_1" /> adalah matriks segitiga atas yang dapat dibalik, persamaan ini ekuivalen dengan

<BlockMath math="R_1 x = Q_1^T b" />

Sistem segitiga atas ini dapat diselesaikan dengan substitusi mundur, memberikan solusi <InlineMath math="x" /> 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

<MathContainer>
<BlockMath 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}" />
<BlockMath math="b = \begin{pmatrix} -2.2 \\ -4.2 \\ -4.2 \\ -1.8 \\ 1.8 \\ 8.2 \\ 15.8 \end{pmatrix}" />
</MathContainer>

Setiap baris dalam matriks <InlineMath math="A" /> berformat <InlineMath math="[t_i^2, t_i, 1]" /> untuk mencari koefisien polynomial <InlineMath math="y = at^2 + bt + c" />, sedangkan vektor <InlineMath math="b" /> berisi nilai pengamatan yang bersesuaian.

### Proses Dekomposisi QR

Dekomposisi QR dari matriks <InlineMath math="A" /> menghasilkan

<MathContainer>
<BlockMath 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}" />
<BlockMath 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}" />
</MathContainer>

### Tahap Penyelesaian

Pertama, kita menghitung <InlineMath math="Q_1^T b" /> untuk memperoleh

<BlockMath math="Q_1^T b = \begin{pmatrix} -9.7143 \\ 16.0257 \\ 3.4806 \end{pmatrix}" />

Selanjutnya, kita menyelesaikan sistem segitiga atas <InlineMath math="R_1 x = Q_1^T b" /> menggunakan substitusi mundur. Karena <InlineMath math="R_1" /> berbentuk segitiga atas, kita mulai dari persamaan paling bawah.

Dari persamaan ketiga, <InlineMath math="-1.73205 x_3 = 3.4806" />, sehingga <InlineMath math="x_3 = -2.00952" />.

Dari persamaan kedua, <InlineMath math="5.29150 x_2 = 16.0257" />, sehingga <InlineMath math="x_2 = 3.02857" />.

Dari persamaan pertama, <InlineMath math="-14.00000 x_1 - 2.00000(-2.00952) = -9.7143" />, sehingga <InlineMath math="x_1 = 0.98095" />.

Dengan demikian, solusi lengkap adalah

<BlockMath 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

<BlockMath math="y = 0.98095 \cdot t^2 + 3.02857 \cdot t - 2.00952" />

Visualisasi berikut menunjukkan seberapa baik polynomial ini mewakili data asli

<LineEquation
  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 <InlineMath math="A^T A" /> terlebih dahulu, kemudian menerapkan dekomposisi Cholesky karena matriks ini bersifat positif definit. Metode ini memerlukan sekitar <InlineMath math="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 <InlineMath math="m = n" /> dimana <InlineMath math="\text{cond}(A^T A) \approx \text{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 <InlineMath math="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 <InlineMath math="A^T A" /> dalam metode Cholesky.

Pemilihan metode yang tepat bergantung pada karakteristik data dan tingkat akurasi yang dibutuhkan dalam aplikasi spesifik.