Nama: Epsiarto Rizqi Nurwijayadi
NPM: 2506565433
Mata Kuliah: Komputasi Teknik

Artikel ini membahas bab pertama dari buku Fedorov, yaitu mengenai persamaan linear.

Mari kita ikuti secara bertahap sesuai isi buku.

Pendahuluan

Bagian ini dibuat dengan kata-kata sendiri.

1. Triangular

Persamaan triangular ini hanya dapat dipakai untuk matrix lower dan matrix upper. Yaitu L yang di sisi kiri bawah berisi nol semua, atau U yang di sisi kanan atas nol semua.

Persamaan triangular ini, bila digunakan untuk matrix yang tidak triangular, akan menyebabkan hasil yang tidak tepat.

1.2.1. LU Decomposition

Untuk matriks L, nilai diagonal semua bernilai 1.

Penurunan persamaannya adalah sebagaimana berikut

A.x = b
L.U.x = b

L.y = b
U.x = y

Dari sini dapat dipecahkan dengan backward subtitution maupun forward substitution.

1.2.2. QR Decomposition

Penurunan persamaannya adalah sebagaimana berikut

A.x = b
A.x = Q.R.x = b
R.x = Qᵗ.b

Di mana R adalah matrix upper triangular.

Sisi kanan mudah dipecahkan karean cukup memakai matrix transpose saja.

Dari sini dapat dipecahkan dengan back subtitution.

1.3. Determinant of a matrix

Ini adalah salah satu manfaat dekomposisi.

Memudahkan perhitungan karena det(L) = 1

1.4. Matrix inverse

Ini adalah salah satu manfaat dekomposisi.

Bagaimana mendapatkan Aˉ¹ dari dekomposisi L.U ?

Penurunan persamaannya adalah sebagaimana berikut:

A.Aˉ¹ = I
L.U.Aˉ¹ = I

L.Y = b
Y = U.Aˉ¹

Maka dapat diselesaikan dengan cara substitusi sebagaimana dekompoisisi L.U.

1.5. JavaScript implementations

Tidak dibahas di artikel ini.

Persamaan Terkait Triangular

Bagian ini dibuat dengan AI.

Transformasi Sistem Persamaan Linear ke Bentuk Segitiga

Algoritma yang efisien untuk menyelesaikan sistem persamaan linear secara numerik adalah dengan mengubah sistem asli menjadi sistem segitiga yang ekuivalen.

Sistem segitiga atas dapat ditulis sebagai:

\[T\mathbf{y} = \mathbf{c}\]

di mana \(T\) adalah matriks segitiga: jenis khusus matriks persegi di mana elemen-elemen di bawah atau di atas diagonal utama bernilai nol.

Substitusi Mundur (Back Substitution)

Sistem segitiga atas dapat diselesaikan dengan mudah menggunakan substitusi mundur:

\[y_{i} = \frac{1}{T_{ii}} \left( c_{i} – \sum_{k=i+1}^{n} T_{ik} y_{k} \right), \quad i = n, \ldots, 1\]

Titik Awal: Sistem Asli

Ketika kita memiliki sistem segitiga \(T\mathbf{y} = \mathbf{c}\), mari kita tuliskan apa artinya ini untuk baris ke-\(i\):

\[T_{i1}y_1 + T_{i2}y_2 + T_{i3}y_3 + \cdots + T_{ii}y_i + T_{i(i+1)}y_{i+1} + \cdots + T_{in}y_n = c_i\]

Mengapa Penyebut \(T_{ii}\)?

Derivasi Langkah demi Langkah

Untuk matriks segitiga atas, persamaan ke-\(i\) terlihat seperti:

\[T_{ii}y_i + T_{i(i+1)}y_{i+1} + T_{i(i+2)}y_{i+2} + \cdots + T_{in}y_n = c_i\]

Langkah 1: Pindahkan semua suku “yang sudah diketahui” ke sisi kanan

\[T_{ii}y_i = c_i – T_{i(i+1)}y_{i+1} – T_{i(i+2)}y_{i+2} – \cdots – T_{in}y_n\]

Langkah 2: Tulis sisi kanan dalam bentuk notasi sigma

\[T_{ii}y_i = c_i – \sum_{k=i+1}^{n} T_{ik}y_k\]

Langkah 3: Bagi kedua sisi dengan \(T_{ii}\) untuk mendapatkan \(y_i\) sendiri

\[y_i = \frac{1}{T_{ii}} \left( c_i – \sum_{k=i+1}^{n} T_{ik}y_k \right)\]

Bagaimana Persamaan Biasa Menjadi Bentuk Ini?

Proses transformasi sistem persamaan linear biasa menjadi bentuk segitiga melibatkan beberapa langkah:

Langkah 1: Memulai dengan sistem persamaan linear biasa \(A\mathbf{x} = \mathbf{b}\)

Langkah 2: Menerapkan eliminasi Gauss untuk membuat matriks segitiga atas

Langkah 3: Melakukan operasi baris elementer untuk membuat elemen di bawah diagonal utama menjadi nol

Langkah 4: Setelah matriks menjadi segitiga atas, kita mendapatkan sistem \(T\mathbf{y} = \mathbf{c}\)

Langkah 5: Menyelesaikan sistem segitiga dengan substitusi mundur

Dalam Bahasa Indonesia, proses ini disebut sebagai “eliminasi Gauss” atau “metode eliminasi Gaussian”. Metode ini sangat efisien untuk menyelesaikan sistem persamaan linear, terutama ketika diimplementasikan secara numerik dalam program komputer.

Keuntungan utama dari bentuk segitiga adalah kemudahan dalam penyelesaiannya. Dengan dimulai dari persamaan terakhir yang hanya mengandung satu variabel, kita dapat mensubstitusikan nilai yang ditemukan ke persamaan sebelumnya, dan seterusnya hingga semua variabel ditemukan.

Perhatikan bahwa dalam rumus substitusi mundur, penyebut \(T_{ii}\) sangat penting karena merupakan faktor pengali untuk variabel \(y_i\) yang ingin kita cari. Jika \(T_{ii} = 0\), maka sistem tidak memiliki solusi unik atau metode ini tidak dapat digunakan.

Implementasi Javascript Dari Dekomposisi L.U

Dekomposisi Matrix Metode Lower-Upper Tahap Demi Tahap

Dalam komputasi secara umum, yang dipakai bukan rumus berikut:

A = L.U

Namun dilakukan Pivot terlebih dahulu, untuk menghindari kesalahan ketelitian maupun pembagian dengan nol.

P.A = L.U

Supaya coding lebih rapi, maka menggunakan tool math.js, supaya lebih sederhana.

Berkas code selengkapnya di python ada di sini:
https://github.com/epsi-rns/kom-tek/blob/main/01-linear-equations/24-lu-sympy.ipynb

External library
https://mathjs.org/

Step-by-Step LU Decomposition with Partial Pivoting

Input Matrix

Algorithm Controls

Click “Next Step” to begin the decomposition…

Current State

Working Matrix:

Lower Triangular Matrix L:

Upper Triangular Matrix U:

Permutation Matrix P:

Algorithm Steps

Dekomposisi Matrix Metode Lower-Upper Tahap Demi Tahap

ccitonline.com

Dekomposisi LU