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

Video ini membahas contoh faktorisasi Householder dalam analisis numerik dengan persoalan kuadrat terkecil. Konsep matriks V, V transpose X, dan V transpose V dijelaskan untuk mentransformasikan matriks A menjadi matriks R. Pentingnya menggunakan H kali X daripada membentuk H secara langsung untuk mengurangi kompleksitas operasi menjadi O(n) daripada O(n^2). Algoritma yang akan digunakan akan memanfaatkan X dikurangi alpha kali V, dimana alpha diperoleh dari perhitungan spesifik.

Sekarang saya ambil x sama dengan tekanlah 1, 2, min 1.

Oke, maka matrik V saya itu akan sama dengan 1, 2, min 1 ditambah norm dari ini akar 4 tambah 2, 6.

Dikalikan dengan 1, 0, 0 berarti ini akan sama dengan 1 ditambah akar 6, 2, min 1 ini adalah V.

Oke, nah sekarang bagaimana dengan V transpose X?

V transpose X berarti 1 plus akar 6 kemudian 2, min 1, ini 2, min 1 dikalikan 1, 2, min 1.

Oke, kemudian saya ingin tahu juga V transpose V, V transpose V itu akan sama dengan 1 ditambah akar 6, 2, min 1, 1 plus akar 6, 2, min 1.

Ini bisa kita cari masing-masing berapa dan 2 kali V transpose X itu ternyata sama dengan V transpose V nilainya.

Akibatnya apa? H kali X jadi ini Anda bisa isi ini sama setengah dari ini maka H kalikan X untuk V yang seperti ini

itu akan sama dengan 1, 2, min 1 dikurangi dengan akar 1 plus akar 6, 2, min 1 ini akan sama dengan minus akar 6, 0, 0.

Jadi benar bahwa saya akan melakukan zeroing di bawah sana kecuali pada elemen pertama.

Nah inilah ide yang akan kita gunakan untuk mentransformasikan matrix yang tadinya berupa matrix A yang over determined kita akan bawa menjadi bentuk seperti ini.

Dan inilah yang kita sebut dengan matrix R.

Nah catatan lagi bahwa ternyata saya tidak membutuhkan matrix H.

Matrix H nya sama sekali tidak kelihatan di sini.

Kenapa? Yang saya butuhkan adalah H kali X.

Dan H kali X itu seperti yang tadi sudah kita tunjukkan itu hanya X dikurangi sama konstanta alpha kalikan V.

Kalau saya hitung seperti ini dengan mengambil H atau mengkonstruksikan H terlebih dahulu maka biayanya adalah perkalian matrix kali vektor.

Itu kita kenal dengan saksi level 2 atau quadratic complexity.

Sedangkan yang ini vektor dikurang vektor.

Kalau masing-masing vektor panjangnya n ini adalah O n.

Jadi yang kanan ini O n kompleksitasnya hanya perlu n operasi.

Jadi jangan sampai kita membentuk H untuk melakukan zeroing.

Jadi hanya kita tidak perlukan hanya kita perlukan V saja.

Dan tentu saja dampak dari H kali X yaitu X dikurang alpha kali V.

Dimana alphanya tadi yaitu 2 V transpose X dikalikan V transpose V.

Ini yang kita akan lakukan pada algoritma sebagai berikut.