Name: Implementasi Algoritma Rotasi Givens pada Octave/ Matlab]
Uploaded: 2024-02-21

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

Video ini membahas implementasi algoritma rotasi Givens pada Octave/Matlab untuk persoalan kuadrat terkecil. Metode ini mirip dengan Householder, dengan langkah awal menentukan dimensi matriks dan melakukan augmentasi. Proses selanjutnya melibatkan perhitungan cosinus dan sinus untuk melakukan rotasi baris. Algoritma ini dapat menemukan matriks segitiga atas dan solusi persamaan kuadrat terkecil. Meskipun lebih mahal secara komputasi daripada Householder, algoritma rotasi Givens tetap stabil dan akurat karena menggunakan orthogonal transformation. Teknik ini cocok untuk matriks dengan kolom-kolom independen linear, namun memerlukan penyesuaian jika terdapat kolom dependent linear. Solusi yang diperoleh akan mencakup variabel independent saja, sementara variabel dependent dapat diatur menjadi 0 untuk mempermudah perhitungan.

Baik, sekarang kita akan coba implementasikan metode transformasi dengan rotasi given yang barusan kita jelaskan.

Jadi outputnya sama dengan tadi Householder, kita namakan fungsi kita given, inputnya juga sama yaitu matrix A dan ruas kanan B.

Kemudian apa yang kita butuhkan di awal sama dengan tadi, pertama saya perlu tahu dimensi dari matrixnya.

Kemudian yang kedua saya lakukan augmentation, A di augment dengan B.

Kemudian saya akan melakukan proses zeroing kolom demi kolom, tapi setiap kali operasinya baris adalah 2 baris.

Jadi sama dengan tadi saya pakai indeks kolom saya jitu dari 1 sampai n karena saya hanya punya n kolom.

Kemudian apa yang harus saya lakukan, saya harus menghitung C dan S, untuk itu saya akan bekerja pada pengenolan mulai dari baris ke J plus 1 sampai baris ke M.

Jadi saya membutuhkan indeks baris sekarang namakan I, tapi mulai dari mana yang saya mau nolkan itu, mulai dari J plus 1, ini yang mau di nolkan.

Selanjutnya saya membutuhkan R panjang faktornya, jadi adalah akar dari, ada dua tadi kan,

yang elemen X nya adalah yang di diagonal berarti ajj, kemudian yang Y nya adalah aij berarti ajj2.

Oke dapat R, sekarang tinggal cari cosinus, itu sama dengan yang cosinus berarti ajj dibagi R.

Sedangkan sinusnya adalah aij dibagi dengan R, dapat sinus, dapat cosinus, selanjutnya saya akan mengupdate baris ke I dan baris ke J, saya mulai dengan baris ke J terlebih dahulu.

Tapi baris ke J ini saya masih butuhkan untuk dipakai pada penghitungan baris ke I, berarti nggak bisa saya langsung override.

Jadi saya masukkan dulu ke temporary, jadi temporary sama dengan tadi rumusnya cosinus, kalikan dengan baris ke J.

Baris ke J itu saya hanya bekerja mulai dari kolom ke J sampai kolom ke N plus 1 karena disitu ada B, dan ini baris ke J, ditambah dengan sinus, dikalikan dengan A, ini baris ke I nya.

Saya indexnya salah, ini baris ke J, kolomnya dari J sampai N plus 1, kemudian baris ke I dari J sampai N plus 1.

Oke, sedangkan yang baris ke I nya sudah boleh saya override karena sudah tidak diperlukan lagi, sudah tidak terpakai lagi nanti.

Dari J sampai dengan N plus 1, sama dengan minus S, dikalikan dengan baris ke J, ingat ini baris ke J yang lama sebelum saya rotasi.

Itu minus sudah benar, sekarang ditambah dengan cosinus, dikalikan baris ke I, dari J sampai N plus 1.

Nah, setelah itu saya baru update baris ke J nya, itu akan sama dengan temporary tadi, TMP kita set disana.

Oke, jadi ini sudah selesai, sama dengan tadi, sekarang saya ambil R nya, yaitu komponen pertama, N kolom pertama, jadi dari 1 sampai N.

Barisnya semua diambil, kolomnya dari 1 sampai N saja, sedangkan bt nya adalah kolom ke N plus 1.

Oke, ini sudah selesai, sekarang kita coba tes bagaimana hasilnya dan kita bandingkan dengan yang tadi sudah kita peroleh.

Oke, sekarang saya akan namakan untuk given ini R1, bt1, ini akan sama dengan given, sama tadi matriknya A dan B,

yang B tadi waktu kita bicara tentang model yang kependudukan. Oke, coba dibandingkan, ini adalah R pakai rotasi, apa namanya, pakai householder, sedangkan R1 pakai rotasi given.

Jadi, perhatikan yang beda cuma tandanya, jadi yang satu minus, minus, yang ini jadi plus, jadi beda tanda saja.

Nah, sekarang pastilah berhubungan dengan B, jadi kalau bt nya seperti ini yang pakai rotasi, pakai householder, maka yang pakai rotasi given, bt1, lagi-lagi beda tanda.

Jadi, keduanya ini persis sama kalau kita lihat secara keseluruhan, jadi baik rotasi given maupun householder itu dapat menemukan R atau matrik segitiga atasnya dan bt.

Nah, selanjutnya dari sisi kompleksitas atau cost dari eksekusi programnya, kita bisa lihat dari struktur program baik householder maupun given,

ini kalau kita lihat householder kan cost terdalamnya disini, jadi saya punya, ini makin pendek, tapi jumlah kolomnya ini n, jadi disini ada mn,

n disini, kemudian disini ada n, berarti kira-kira m kali n kuadrat, ini costnya, konstantannya kita tidak hitung, jadi kira-kira kompleksitasnya m kali n kuadrat.

Sama dengan yang rotasi given, kira-kira om n kuadrat, tapi koefisiennya akan lebih tinggi karena dia satu-satunya, jadi setiap elemen itu akan ada dua operasi baris yang harus dilakukan.

Jadi secara cost, tentu saja kalau matriknya dense, yang rotasi given akan lebih sedikit lebih mahal dari householder.

Dari sisi akurasi, tentu saja kedua-dua algoritma ini sangat stabil dan akurat karena memanfaatkan apa yang kita kenal dengan orthogonal transformation

yang tentu saja tidak akan terhindar dari operasi-operasi yang bisa menyebabkan amplifikasi error dari penghitungan cost sin s dan sin s,

lihat saja bahwa ini pembaginya itu dengan r, dimana r itu adalah akar dari a kuadrat tambah b kuadrat, artinya x kuadrat tambah y kuadrat, sedangkan yang akan dibagi adalah x dan y,

jadi tentu saja c dan s ini akan selalu lebih kecil dari satu harga mutlaknya, jadi propagasi errornya juga akan cukup terkendali.

Demikian untuk teknik penyelesaian least square problem apabila matriks coefficient A itu memiliki range yang penuh atau semua kolom dari A bersifat independent linear.

Untuk yang dependent linear, jika ada kolom yang dependent linear, artinya range dari A itu kurang dari n, maka tekniknya akan sedikit berbeda,

karena kita harus menjamin bahwa seluruh kolom-kolom yang bebas linear itu harus berada di depan,

supaya struktur dari matriks R itu benar-benar akan mendapatkan non singular corner atau sudut yang non singular ngumpul di depan sehingga kita akan mendapatkan solusi.

Perhatikan bahwa solusi yang akan kita peroleh hanya akan sejumlah variable independent saja, jadi variable yang bebasnya katakanlah cuma k,

maka solusi x-nya hanya akan memuat k elemen.

Bagaimana dengan yang n-k-nya, sebetulnya dia merupakan free variable karena kolom-kolom tersebut atau variable tersebut dependent linear,

cuma untuk memudahkan biasanya kita akan ambil 0 atau 0 untuk variable yang tidak terpakai.

Jadi yang tidak terpakai kita akan set to 0, toh tidak ada manfaatnya nanti, hanya yang akan terpakai kita akan ketemukan nilai-nilainya sebagai parameter model.

Jadi tadi sudah saya jelaskan bahwa kasus yang row rank deficient, artinya ada variable yang dependent linear,

itu task atau terjadi pada saat model construction dimana yang mengkonstruksikan model itu tidak aware,

tidak sadar bahwa parameter-parameter yang dilibarkan itu ternyata saling dependent linear.