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

Video ini membahas algoritma faktorisasi Householder untuk menyelesaikan persoalan kuadrat terkecil dengan transformasi matriks A menjadi R dan ruas kanan B. Proses melibatkan zeroing elemen-elemen matriks dengan memperhatikan faktor V dan menghindari loss of significant digit. Hasilnya adalah matriks R dan solusi least square untuk persoalan tersebut. Contoh penerapan algoritma ini dilakukan dengan data penduduk Indonesia tahun 2030 berdasarkan data 10 tahun terakhir.

Oke, sekarang kita akan membuat fungsi dalam oktav untuk memperoleh dua matriks tadi, yaitu A berubah menjadi R, kemudian B ruas kanan.

Ingat tadi persoalan kita adalah AX sama dengan B atau meminimumkan AX kurang B.

Tapi saya akan cari dulu matriks R yang merupakan hasil transformasi Householder pada A, kemudian ruas kanan dari tadinya B menjadi katakanlah BT.

Jadi saya akan taruh dulu sekarang A menjadi R dengan BT, ini koma BT, kemudian saya tutup.

Oke, nama filenya adalah House, inputnya itu ada dua yaitu matriks A yang overdetermined sifatnya, dan vektor B yang panjangnya sama dengan M sama dengan banyanya baris dari A.

Oke, sekarang ada beberapa hal yang harus saya ketahui, yang pertama adalah dimensi dari matriks A, dan ini saya bisa panggil namanya size yang memberikan dimensi dari matriks A.

Jadi ini size dari A. Jadi dengan adanya saya tulis demikian maka artinya, saya sekarang sudah tahu banyaknya baris dari matriks A itu sama dengan M, banyaknya kolomnya adalah N.

Nah sekarang saya akan bekerja pada matriks yang sudah menggabungkan A dengan B, tapi itu saya simpan kembali di A lagi.

Jadi sama dengan kemarin waktu kita melakukan Naive Gaussian Elimination, kita lakukan augmentation atau kita gabung A dengan B.

Jadi sekarang A dengan B itu sudah menjadi satu di A.

Sekarang proses zeroing, pengenolan yang harus saya lakukan adalah sejumlah kolom dari A, jadi saya harus punya loop sekarang, yaitu loop untuk kolom-kolom dari A.

Namakan sekarang loopnya J itu dari 1 sampai N karena kolomnya A itu sejumlah N.

Nah untuk masing-masing kolom yang pertama harus saya lakukan adalah mencari atau mendefinisikan V.

Ingat V ini bersesuaian dengan kolom atau saya turunkan dari kolom yang ingin saya nolkan.

Pada saat ini kolom yang saya ingin nolkan itu kan kolom ke J.

Jadi V saya itu akan sama dengan kolom ke J, ini nulisnya adalah seperti ini, kolom ke J.

Ini tadi X yang kita ceritakan tadi, sekarang namanya kolom ke J.

Tapi dia barisnya itu tidak selalu harus dari 1, tapi saya mulainya dari baris ke J saja sampai ke M.

Jadi ini adalah X yang tadi saya maksudkan yang ingin kita lakukan zeroing atau pengenolan pada elemen-elemen di bawahnya.

Jadi di kolom pertama Anda bayangkan elemen pertamanya itu kita pertahankan atau tidak kita nolkan,

tapi elemen kedua, karena ini kolom pertama ya, elemen kedua sampai ke M itu harus kita nolkan.

Ada satu hal lain yang belum saya sebutkan bahwa kita harus menghindari terjadinya cancellation atau pengurangan dua bilangan yang hampir sama.

Kalau itu terjadi kita akan mengalami apa yang disebut dengan loss of significant digit.

Untuk itu saya akan gunakan fungsi sine atau tanda, jadi akan sangat bergantung pada AJJ-nya.

Jadi kalau AJJ-nya positif dia akan plus, kalau AJJ-nya negatif dia akan minus.

Jadi sudah cocok kan tidak akan terjadi pengurangan dengan bilangan yang hampir sama.

Tapi kalau dia minus menjadi minus-minus, kalau dia plus menjadi plus-plus.

Setelah itu saya membutuhkan norm dari yang akan saya nolkan tadi yaitu A dari J sampai dengan M, J.

Ini kolom ke J dimulai dari defaultnya adalah 62, jadi tanpa saya harus sebutkan bahwa yang dimaksud adalah 62.

Kemudian saya harus kalikan dengan matrik atau faktor yang elemen pertamanya satu, tapi dibawahnya itu harus nol semua sejumlah M dikurangi dengan J.

Jadi disini saya akan kasih 0, K, M, kurang J, 1.

Ini akan menyebabkan saya punya faktor yang satu, nol, nol, nol semua disana.

Saya akan cek terlebih dahulu, katakanlah matrik saya ukurannya 5x2, maka untuk yang pertama kali maka yang nolnya itu ada 4.

Karena yang paling atas itu sudah berisi satu, benar kan?

Karena J nya sama dengan satu, maka 5 dikurang satu 4, jadi ini benar.

Nah, setelah saya temukan V, maka saya sekarang bisa mulai menghitung skalar yang tadi saya taruh sebagai V,

saya namakan alpha tadi, tapi sementara ini kita akan pisah karena V transpose X nya akan bergantung pada kolom.

Jadi saya akan ambil sekarang konstanta saya namanya alpha, itu akan sama dengan 2 dibagi dengan V transpose dikalikan V.

Jadi ini jangan sampai kita hitung berulang-ulang karena untuk setiap kolom yang akan kita update dari A itu akan sama saja,

jadi tidak akan berubah sama sekali V transpose V nya.

Nah, sekarang yang harus saya eliminir atau saya akan lakukan proses perkalian dengan Q itu bukan hanya kolom pertama,

tapi juga kolom kedua, kolom ketiga, sampai kolom terakhir, kolom ke N dan juga B.

Jadi seluruh kolom pada A itu harus saya kalikan, artinya apa?

H kali X itu harus saya lakukan pada semua kolom dari matrix A.

Jadi saya harus pakai loop sekarang mulai dari kolom ke J, ini kolom lagi nih orientasinya, sampai ke N plus 1.

Kenapa N plus 1? Karena di kolom ke N plus 1 itu ada B.

Nah, apa yang harus saya lakukan? Saya harus mengupdate elemen dari matrix A pada kolom ke K.

Jadi mulai dari kolom pertama sampai ke N plus 1.

Ini sama dengan rumus yang tadi, ingat tadi H kali X sama dengan X dikurang 2 kali V transpose X dibagi V transpose V dikalikan V.

Berarti ini akan menjadi Xnya sendiri adalah dirinya sendiri, jadi A, J sampai M, K dirinya sendiri.

Kemudian dikurangi dengan, saya sudah punya alfa, jadi cukup saya sekarang kalikan dengan V transpose dikalikan dengan X yaitu dirinya sendiri.

Sampai M, K masih harus dikalikan dengan V.

Jadi inilah yang akan melakukan proses zeroing tersebut.

Nah, sudah selesai saya lakukan zeroing maka ini akan terjadi kolom demi kolom dan hanya pada elemen yang dibutuhkan untuk diupdate.

Jadi elemen-elemen pada A yang sudah selesai diupdate tidak diupdate kembali.

Oke, ini yang akan terjadi dan sudah selesai.

Sekarang apa yang harus saya retrieve? Rnya berada di mana?

R tersebut itu akan tersimpan di kolom N kolom pertama pada A.

Jadi semua baris masuk tapi ini dari 1 sampai N saja.

Sedangkan BT itu berada di kolom terakhir dari A yaitu kolom ke N plus 1.

Jadi sama dengan tadi barisnya semua diambil tapi ini kolom ke N plus 1.

Dan kita sudah selesai, sekarang kita simpan, sudah tersimpan matriknya.

Oke, sekarang saya bentuk dulu misalkan saya punya A, katakanlah matrik random 6 x 3 misalnya.

Sedangkan B karena matrik A nya 6 x 3 berarti 6 x 1 B nya.

Oke, saya punya A dan B, nah sekarang bagaimana dengan R?

Maka saya panggil sekarang fungsi saya tadi, saya akan mendapatkan sekarang hasil sebagai berikut.

Namanya tadi house dan ini inputnya A dan B.

Oke, jadi perhatikan bahwa benar saya sudah dapatkan ini matriknya yang atas ini adalah matrik R1 saya tadi.

Jadi sudah dapat sekarang bahwa yang namanya solusi least square kita yaitu penyelesaian dari R1 bagian atas ini dengan ruas kanan Bt1.

Jadi xls katakan least square nya itu adalah R1 sampai 3, kebetulan kolomnya sisanya 3 berarti saya bisa pakai titik 2 gini aja.

Dan saya pakai backslash Bt dari 1 sampai 3.

Oke, jadi ini adalah solusi least square yang kita cari.

Sedangkan yang namanya residu tadi kita sudah tunjukkan bahwa ini akan sama dengan norm dari Bt yang sisanya yang tidak saya pakai tadi dari 4 sampai 6.

Jadi elemen ke 4 sampai ke 6 itu tidak dipakai karena yang dipakai untuk mencari least square solusinya itu hanya 1 sampai 3 dari Bt.

Jadi ini saya dapatkan hasilnya adalah 0,4013 sebagai residual dan inilah yang disebut dengan norm dari Ax dikurang B, benar nggak?

Coba kita lihat norm dari A dikalikan dengan xls solusi saya dikurangi dengan B.

Betul kan? Jadi kita dapatkan sekarang bahwa solusi least square solusi kita sudah ketemu yaitu 0,9802, minus 0,1726, dan 0,2187.

Oke, sekarang kita ambil contoh yang kita coba cari di internet data-datanya terlebih dahulu.

Jadi misalkan saya ingin tahu berapa sih penduduk Indonesia tahun 2030 misalnya gitu ya.

Data yang saya punya adalah data 10 tahun terakhir.

Nanti kita coba cek ada nggak datanya di BPS jumlah penduduk Indonesia tahun 2010 sampai tahun 2020 kita punya atau tidak gitu.