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

Video ini membahas perhitungan kompleksitas algoritma eliminasi Gauss dalam konteks sistem persamaan linear. Kompleksitas algoritma ini terkait dengan biaya eksekusi yang melibatkan jumlah operasi aritmatika, terutama dalam mengupdate matriks pada setiap tahap. Dengan menggunakan sigma notasi, kompleksitas algoritma ini dapat disederhanakan menjadi n pangkat 3 dibagi 3 ditambah O n kuadrat. Meskipun kompleksitasnya tinggi, algoritma ini menjadi dasar penting dalam menyelesaikan sistem persamaan linear secara umum. Implementasinya dalam bahasa Octave atau Matlab juga akan dibahas dalam video.

Nah selanjutnya, sama halnya dengan algoritma untuk substitusi mundur dan maju,

kita akan coba hitung berapa kos atau biaya untuk mengeksekusi algoritma seperti ini.

Saya akan gambarkan tadi lagi-lagi apa yang terjadi sebetulnya.

Jadi pada setiap tahap, pada tahap ke k, saya harus mengupdate suatu matrik berukuran n-k x n-k.

Ukurannya seperti ini, di mana k-nya berjalan dari 1 sampai n-1.

Nah, untuk mengupdate ini, untuk mengupdate elemen di sini,

jumlah operasi atau jumlah elemen yang harus saya hitung itu kan adalah n-k kuadrat.

Kalau matrik saya n-k x n-k, maka jumlah elemen yang harus saya update adalah n-k kuadrat.

Sehingga total operasi yang harus dibutuhkan, total arithmetic operation yang terlibat nanti,

sehingga totalnya adalah biaya total atau total cost-nya.

Total biaya itu adalah sigma n-k kuadrat, di mana k dari 1 sampai n-1.

Ini kan sama saja dengan sigma k kuadrat, di mana k-nya dari 1 sampai n-1.

Jadi kan pertama kan n-1 kuadrat, n-2 kuadrat, n-3 kuadrat, sampai dengan 1 kuadrat terakhir.

Sama saja, 1 kuadrat tambah 2 kuadrat, terakhir n-1 kuadrat.

Dan ini secara keseluruhan adalah n pangkat, 3 dibagi 3 ditambah dengan O n kuadrat.

Artinya kita tidak akan terlalu concern dengan yang lebih rendah.

Jadi, leading term atau suku yang paling mahal untuk mengeksekusi algoritma ini

proportional atau sebanding dengan n pangkat 3 dibagi 3.

Tentu saja sangat-sangat mahal, karena kalau bayangkan n-nya adalah 1000,

berarti ada 10 pangkat 9 dibagi 3, atau apalagi kalau n-nya 1 juta gitu.

Jadi, waktu yang dibutuhkan untuk mengeksekusi ini untuk matrik yang besar itu akan cukup lama.

Ini metode yang akan kita jadikan sebagai basis untuk menyelesaikan sistem persamaan linear yang umum.

Dengan cara mengkonversi A menjadi U, B menjadi B tilde.

Sekarang kita akan coba lihat bagaimana implementasinya dalam bahasa Octave atau Matlab.