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

Video ini membahas teknik Iterative Error Refinement dalam Analisis Numerik pada bab Sistem Persamaan Linear. Konsep utama yang dibahas meliputi penggunaan residual error untuk mengukur akurasi solusi, backward error untuk mengevaluasi kesalahan, dan proses refinement untuk meningkatkan akurasi solusi secara iteratif. Melalui pendekatan ini, solusi yang lebih akurat dapat diperoleh dengan biaya komputasi yang lebih efisien, terutama dengan memanfaatkan hasil faktorisasi matriks. Metode ini memungkinkan peningkatan akurasi solusi tanpa menambah kompleksitas perhitungan secara signifikan.

Kita sudah membahas sejauh ini teknik-teknik untuk menyelesaikan sistem persamaan linear,

kemudian kita juga sudah melihat kompleksitas dari algoritma-algoritmanya

yang menunjukkan bahwa secara umum cukup mahal, yaitu sekitar n pangkat 3 per 3,

tapi untuk matrik khusus yang sudah kita bahas, yaitu matrik simetrik,

baik itu simetrik indefinite maupun yang positif definite,

itu bisa setengah dari kos umum, jadi n pangkat 3 per 6.

Beberapa matrik lainnya seperti fundamental atau tuplis itu bisa sampai n kwadrat,

matrik bandit juga tergantung lebar pitanya atau bandwidthnya.

Algoritma-algoritma yang sudah kita bahas juga kita sudah lengkapi dengan safety measure,

yaitu yang kita sebut dengan pivoting, untuk menjamin bahwa proses itu tidak akan breakdown

Kalau matriknya singulir memang tidak akan ada solusi.

Nah khusus untuk matrik simetrik dan positif definite sebetulnya tidak perlu measure apa-apa,

karena algoritma kita pasti akan berjalan tanpa membutuhkan adanya pivoting

Sekarang perhatikan bahwa apa yang kita sudah peroleh sekarang adalah suatu solusi X,

Jadi setelah kita selesaikan kita peroleh solusi kita namanya X topi, kita namakan ini.

Bagaimana kita mengetahui apakah hasil kita tersebut sudah akurat, sudah sesuai atau belum?

Kita definisikan sekarang yang disebut dengan residual error,

R itu sama dengan kita masukkan A ke sini, A kali X dikurangi dengan B.

Jadi R itu adalah dikalikan X solusi, hasil komputasi dikurangi dengan B.

Idealnya R ini akan sama dengan 0, kalau komputasi kita berjalan secara exact.

Nah secara umum R ini akan menyatakan akurasi.

Jadi norm R itu akan memberikan akurasi atau error.

Tapi ini kita kenal dengan backward error, karena saya tidak tahu yang sebenarnya berapa,

X yang sebenarnya berapa, kita tidak membandingkan antara X topi dengan X yang sebenarnya,

tapi kita masukkan kembali ke sistem dan kita lihat selisih antara A kali X topi dengan B.

Dan inilah makanya disebut dengan backward error.

Sekarang apa yang terjadi kalau kita tidak happy dengan hasil error tersebut?

Jika norm dari R masih terlalu besar atau belum sesuai dengan harapan.

Kita berharap normnya itu harus di bawah 10 pangkat minus 5,

tapi ternyata hasil hitungan kita masih 10 pangkat minus 4.

Maka kita bisa melakukan apa yang disebut dengan refinement, penghalusan.

Jadi pertama, kita hitung R yaitu A kali X dikurangi dengan B.

A itu sama dengan X dikurangi dengan X yang sebenarnya.

Sekarang kita lihat bahwa B ini sama dengan AX.

Sehingga R sama dengan AX topi dikurangi dengan AX.

Berarti sama dengan A kali X topi dikurangi X.

Sehingga langkah kedua kita adalah selesaikan atau cari E

itu akan sama dengan X yang lama ditambahkan dengan E.

Adalah solusi yang lebih akurat atau lebih tinggi akurasinya.

Nah, apabila hasil yang baru ini juga belum happy.

Artinya hitung lagi R yang baru kemudian cari lagi E

Ini akan mendapatkan solusi yang makin lama makin akurat.

Tentu saja kita harus memanfaatkan hasil faktorisasi pada A

Jadi disini juga contoh mengapa LU faktorisasi itu lebih menarik

Jadi tidak ada cost tambahan yang pangkat tiga disini.

Jauh lebih murah daripada mencari X di awal.

Pada saat X di awal ini kita perlu N pangkat tiga per tiga atau per enam.

Sehingga proses iteratif ini sepanjang tidak N kali harus dilakukan

itu masih tetap tidak lebih tinggi, lebih mahal daripada original problem.