Prof. Drs. T. Basaruddin, Ph.D.

Video ini membahas faktorisasi Cholesky pada matriks nxn yang simetrik positif definit. Dengan asumsi matriks G x G transpose sama dengan A, penjelasan dilakukan untuk mencari elemen-elemen matriks ini. Proses faktorisasi Cholesky dilakukan dengan menghitung elemen diagonal, di mana G i j dapat dihitung menggunakan rumus tertentu. Algoritma Cholesky melibatkan perhitungan elemen diagonal dan penggunaan dua loop j dan i. Dengan demikian, algoritma ini dapat diterapkan secara umum, termasuk di MATLAB, untuk mendapatkan faktorisasi Cholesky dari matriks simetris positif definit.

Sekarang kita lihat bagaimana kalau matriks kita umum ukuran n x n dan simetrik positif definit.

Sekarang saya akan balik bahwa G x G transpose sama dengan A.

Jadi saya asumsikan bahwa matriks saya adalah G 1 1 G 2 1 disini akan ada G i 1 disini ada G n 1 disini ada G 2 2 disini ada G n n.

Semua disini akan nol, saya harus sekalikan dengan G 1 1 G 2 1 karena transpose nya G n 1 disini adalah G 2 2 dan disini nanti akan ada G i i

kemudian G i i plus 1 dan seterusnya sampai dengan G n n disini dan ini harus sama dengan A 1 1 disini ada A 2 1 yang sama dengan ini

sampai dengan A n 1 disini ada A n 1 ingat matriks kita simetrik disini ada A n n.

Nah sekarang bagaimana saya mencari elemen-elemen pada matriks ini.

Pertama kalau saya mengalikan baris ke i dikalikan dengan kolom ke j, by the way perhatikan bahwa matriks saya itu segitiga bawah

berarti elemen yang perlu saya cari indeks baris pasti lebih besar daripada indeks kolom.

Jadi yang ingin saya cari itu adalah G i, j dengan i lebih besar dari j.

Kalau i nya lebih kecil dari j dia pasti nol karena dia berada di atas sini, ini yang perlu saya cari.

Gimana ini saya proleh, elemen ini saya proleh, kalikan baris ke i dengan kolom ke j.

Coba kita lihat, baris ke i isinya kan adalah G i 1 di kanannya G i 2 dan dia berhenti di G i i setelah itu dia akan nol.

Sedangkan kolom ke j itu kan isinya adalah G, perhatikan kita tadi bicara tentang ini adalah ke kanan,

G 1, G j 2 sampai dengan G j j setelah itu dia akan nol ke bawah.

Ini adalah kolom ke j, sebetulnya kolom ke j itu adalah baris ke j di transpose.

Baris ke j di transpose, baris ke j berarti kan ini G j 1, G j 2 sampai G j j tapi di transpose ke bawah.

Sekarang kita tahu bahwa panjang dari faktor ini sama tapi yang tidak nol ini sampai i i di mana i nya lebih besar dari j berarti lebih pendek.

Dia akan berhenti berarti di G i j, ini akan dapat apa? Sigma G i k di kalikan G j k tapi ini akan berhenti k nya dari 1 sampai j saja.

Karena di sebelah kanan ini di bawahnya ini maksud saya itu akan nol semua dan j lebih kecil i gitu ya.

Tapi perkalian antara baris ke i dengan kolom ke j itu kan mestinya a i j kan disininya.

Sekarang saya pecah yang untuk j nya saya tulis sendiri, jadi pada saat sampai j itu saya tulis terpisah berarti saya dapatkan ini akan sama dengan sigma k sama dengan 1 sampai j minus 1.

Sama G i k kali G j k tapi ditambah dengan G i j kalikan G j j sama dengan a i j.

Sehingga saya dapat kesimpulan sekarang bahwa kalau demikian G i j itu akan sama dengan a i j

Dikurang sigma G j k kalikan G i k sama saja sih terbalik k nya dari 1 sampai j minus 1 dibagi dengan G j j.

Sehingga kalau saya punya G 1 1 tadi yang gampang sekali dihitung pertama adalah G 1 1 akar dari A 1 1 maka untuk j sama dengan 1 saya sudah bisa hitung semua seluruh kolom pada saat j sama dengan 1.

Jadi prinsip kerjanya adalah pertama hitung G 1 1 sama dengan akar dari A 1 1 setelah itu hitung kolom pertama j nya sama dengan 1 dapat setelah itu move ke menghitung G 2 2 dan seterusnya.

Untuk itu kita harus menghitung yang elemen diagonal nya.

Untuk yang pertama kali gampang yaitu akar dari A 1 1.

Untuk yang berikutnya coba perhatikan saya tinggal kalikan saja baris ke i dengan kolom ke i.

Kalau baris ke i saya kalikan dengan kolom ke i maka saya akan dapatkan ini jadi sama dengan j.

Berarti akan kuadrat kan jadi sigma G i k kuadrat k nya dari 1 sampai i harus sama dengan A i i.

Jadi pada saat i sama dengan j taruh disini kita akan dapatkan rumus yang untuk menghitung saya taruh disini sekarang.

Jadi untuk menghitung elemen diagonal nya gunakan ini bahwa sigma G i k kuadrat karena j nya sama dengan i.

Jadi i sama dengan 1 sampai k sama dengan 1 tapi saya pecah yang i min 1 saja disini.

Kemudian saya tambahkan dengan G i i kuadrat ini akan sama dengan A i i.

Berarti G i i itu akan sama dengan akar dari A i i dikurangi dengan sigma G i k kuadrat k dari 1 sampai i min 1.

Sebetulnya rumus ini bisa kita terapkan kalau di MATLAB secara umum.

Kenapa? Pada saat i sama dengan 1 berarti ini sama dengan 0 berarti benar hanya akar A11 saja.

Jadi rumus ini sebetulnya berlaku untuk i berapapun termasuk i sama dengan 1 kalau tidak mau menginitialize dengan ini.

Sehingga halur pikir dari algoritma nya adalah pertama hitung ini, kedua hitung ini.

Dan kita akan bekerja dalam 2 loop jadi loop j dan loop i.

Saya pikir mungkin untuk konsisten karena j adalah kolom saya akan pakai ini j saja.

Supaya konsisten dengan notas yang di bawah.

Ini adalah j karena j adalah loop terluar saya nanti.

Loop terluarnya adalah j ini adalah loop dalamnya adalah i nanti.

Sehingga dari sini kita akan bikin algoritma untuk Cholesky yaitu hitung elemen diagonal mulai dari j sama dengan 1.

Setelah itu hitung itu dan kita putar loop nya.