TUGAS 3 METODE INVERSIPENYELESAIAN PERSAMAAN LINIERTinjau sistem linear Ax=b, yang mempunyai satu dan hanya satu penyelesaian untuk setiap sisi kanan b, dan batasi perhatian pada sistem yang mempunyai jumlah persamaan tepat sama dengan jumlah variabelnya, yakni untuk matriks yang koefisiennya A dan dapat diinvers-kan. Suatu uji coba yang seringkali dikutip untuk meneliti dapat tidaknya suatu matriks diinverskan, didasarkan pada konsep determinan. Teorema penting yang bersangkutan menyatakan bahwa matriks A dapat diinverskan, jika hanya jika det(A)0 sebagaimana Dalil Cramer yang menyatakan penyelesaian dari Ax=b dalam determinan. Namun demikian, determinan tidak penting untuk praktek penyelesaian sistem linear, karena perhitungan determinan biasanya mempunyai kesulitan yang sama dengan penyelesaian sistem linear. Karena alasan tersebut tidak digunakan determinan dalam penyelesaian sistem linear dan juga tidak perlu mendefinisikan determinan itu sendiri.Metode komputasi numerik untuk penyelesaian sistem persamaan linear dapat dibagi dalam dua jenis, langsung (direct) dan iterasi(iterative), yaitu:1. Metode langsung adalah metode dengan tidak adanya kesalahan pembulatan atau lain-lainnya, akan memberikan penyelesaian yang tepat dalam jumlah operasi aritmetika elementer yang terbatas banyaknya. Metode dasar yang digunakan adalah eliminasi Gauss dan ada berbagai pilihan metode yang bervariasi dalam efisiensi dan kecermatan hitungan.2. Metode iterasi adalah dimulai dengan pendekatan permulaan menggunakan algoritma yang sesuai, untuk mendapatkan hasil pendekatan yang lebih baik. Metode iterasi bervariasi dalam algoritma dan kecepatan konvergensi. Kelebihan metode iterasi adalah kesederhanaan dan keseragamannya dari operasi yang dilakukan. Matriks yang berkaitan dengan sistem linear juga digolongkan dalam padat (dense) atau longgar (sparse). Matriks padat mempunyai sedikit sekali unsur-unsur nol, dan orde matriks itu cenderung menjadi relatif kecilmungkin berorde 100 atau lebih kecil. Biasanya lebih efisien untuk menangani masalah yang melibatkan matriks semacam itu dengan metode langsung. Matriks longgar mempunyai sedikit sekali unsur-unsur tak nol. Biasanya timbul dari usaha-usaha untuk menyelesaiakan persamaan diferensial dengan metode selisih terhingga. Tingkat matriks semacam ini mungkin besar sekali, dan secara ideal sangat cocok untuk penyelesaian dengan metode iterasi.Berikut ini adalah beberapa metode di dalam menyelesaikan persamaan linear dengan pendekatan matriks, antara lain:1. Kaidah Cramer2. Eliminasi gauss (dengan pivoting)(Stability: -, Precision: Affected by Round-off error, Breadth of Application: General, Programming Effort: Moderat)3. Gauss Jordan4. Dekomposisi LU (Matriks Spesial-Tridiagonal)(Stability: -, Precision: Affected by Round-off error, Breadth of Application: General, Programming Effort: Moderat)5. Gauss Seidel(Stability: may not converge if not diagonally dominant, Precision: Excellent, Breadth of Application: Appropriate only for diagonally dominant system, Programming Effort: Easy)

KAIDAH CRAMERJika AX = B adalah system yang terdiri dari n persamaan dan n bilangan tak diketahui sehingga det(A) 0, maka system tersebut mempunyai pemecahan:

dimana Aj adalah matriks yang didapat dengan menggantikan entri entri dalam kolom ke j dengan entri-entri dalam matriks

Contoh:Gunakan aturan cramer untuk memecahkan x1 + + 2x3 = 6 -3x1 + 4x2 + 6x3 = 30 - x1 2x2 + 3x3 = 8 Maka, penyelesaiannya adalah:

Det(A) = 44, det(A1) = -40, det(A2) = 72, det(A3) = 152 Jadi, x1 = -40/44, x2 = 72/44, x3 = 152/44

ELIMINASI GAUSS (DENGAN PIVOTING)Matriks menjadi skema yang efisien ketika semua koefisien sistem linear Ax=b berada dalam deret berorde Nx(N+1). Koefisien-koefisien b disimpan dalam kolom N+1 dari deret (yaitu ai,N+1=bi). Tiap baris memuat semua koefisien yang diperlukan untuk menyatakan satu persamaan dalam sistem linear. Matriks lengkap dinyatakan oleh [A,b] dan sistem linear itu dinyatakan sebagai berikut:

Sistem Ax=b, dapat diselesaikan dengan melakukan OBE (operasi-operasi baris elementer) pada matriks lengkap [A,b]. Variabel-variabel xk adalah pemegang posisi untuk koefisien-koefisien dan dapat dihilangkan sampai akhir perhitungan. Operasi berikut merupakan operasi baris elementar yang dapat diterapkan pada matriks lengkap dan menghasilkan sistem yang setara, meliputi: Pertukaran : urutan dua baris dapat ditukar Penskalaan : Perkalian sebuah baris dengan tetapan tidak nol Penggantian : Sebuah baris dapat digantikan oleh jumlah baris itu dengan kelipatan sebarang baris lainnya.Tumpuan (pivoting) adalah salah satu bentuk penyelesaian eliminasi Gauss dengan menentukan bilangan akk pada posisi (k,k) untuk mengeliminasi xk dalam baris k+1,k+2,,N. Jika akk=0, maka baris k tidak dapat dipakai untuk menghilangkan elemen-elemen pada kolom k, dan baris k harus ditukar dengan baris lainnya di bawah diagonal untuk memperoleh elemen tumpuan yang tidak nol. Jika ini tidak dapat dilakukan maka sistem persamaan tidak mempunyai selesaian tunggal. Metode eliminasi Gauss memerlukan dua tahap di dalam menyelesaikan suatu sistem persamaan linear. Pertama, tahap eliminasi maju (forward elimination) bertujuan mengubah matriks koefisien menjadi matriks segitiga atas. Kedua, adalah subtitusi balik (back subtitution)Algoritma Eliminasi GaussPseudocode untuk implementasi eliminasi Gauss dan proses subtitusi balik disajikan dibawah ini:

GAUSS-SEIDELDalam sub-bahasan ini akan dibahas metode penyelesaian sistem persamaan linear secara tak langsung atau iteratif. Metode perhitungan secara langsung sudah dibahas dalam sub-bahasan di depan, yaitu eliminasi Gauss. Metode Gauss-Seidel adalah metode iteratif yang secara luas telah digunakan sebagai alternatif metode eliminasi. Tinjau satu set dari n persamaan: [A]{X}={B}, dengan asumsi merupakan persamaan 3x3. Jika elemen diagonal tidak nol dan nilainya tidak diketahui, persamaan pertama bisa diselesaikan sebagai x1, persamaan kedua sebagai x2 dan persamaan ketiga sebagai x3, ditunjukkan berikut ini:

Tahap selanjutnya dimulai proses penyelesaian dengan memilih nilai coba untuk x. Langkah sederhana untuk menentukan nilai coba dengan mengasumsikan bahwa semua nilai awal adalah nol. Jika disubtitusikan pada persamaan pertama, maka didapatkan nilai baru untuk x1=b1/a11. Kemudian kita subtitusikan nilai baru x1 dan nilai awal bernilai nol untuk x3 pada persamaan kedua untuk menghitung nilai baru x2. Proses diulang pada persamaan ketiga untuk mendapatkan nilai baru x3. Kemudian kembali diulang untuk persamaan dan prosedur berulang sampai penyelesaian konvergen cukup rapat untuk nilai kebenaran. Konvergensi bisa dicek menggunakan kriteria. Untuk semua i, dimana j dan j1 adalah iterasi saat itu dan sebelumnya:

Algoritma Gauss-SeidelPseudocode untuk implementasi metode Gauss-Seidel disajikan dibawah ini:

MATRIKS SPESIAL TRIDIAGONAL & NILAI EIGENBanyak masalah terapan melibatkan matriks dengan kebanyakan elemennya nol. Salah satu bentuk matriks yang elemen nolnya berpola adalah matriks pita (banded matrix). Lebar pita adalah maksimum banyaknya elemen taknol pada baris- baris suatu matriks pita. Matriks pita yang terkecil adalah yang lebar pitanya tiga atau dikenal sebagai matriks tridiagonal, seperti ditunjukkan pada persamaan sebelumnya sebagai Sistem linear tridiagonal NxN.

Jika eliminasi Gauss langsung diterapkan pada sistem diatas maka banyak operasi yang sebenarnya tidak perlu dilakukan. Agar metode lebih efisien diperlukan modifikasi. Pivoting tidak diperlukan, karena pada umumnya persamaan diatas yang dijumpai dalam praktek bersifat dominan secara diagonal. Setelah eliminasi akan dihasilkan matriks bidiagonal atas. Beberapa metode bisa digunakan untuk menyelesaikan sistem tridiagonal, diantaranya adalah Secant, Gauss Seidel dan lainnya tergantung dari korelasi perilaku elemen matriks tridiagonal. Di fisika seringkali dijumpai kasus penyelesaian nilai eigen dan fungsi eigen dari suatu fungsi keadaan. Akhir bahasan pada studi kasus akan disinggung tentang nilai eigen dan fungsi eigen untuk partikel yang berada dalam sumur potensial. Metode yang efisien untuk menyelesaikan sistem tridiagonal diantaranya adalah algortima Thomas (Thomas Algorithm). Seperti pada dekomposisi konvensial LU, algoritma terdiri dari tiga langkah yaitu dekomposisi, subtitusi maju dan subtitusi balik. Berikut ini adalah algoritma Thomas:

GAUSS JORDANDalam aljabar linear, eliminasi Gauss-Jordan adalah versi dari eliminasi Gauss. Pada metode eliminasi Gauus-Jordan kita membuat nol elemen-elemen di bawah maupun di atas diagonal utama suatu matriks. Hasilnya adalah matriks tereduksi yang berupa matriks diagonal satuan (Semua elemen pada diagonal utama bernilai 1, elemen-elemen lainnya nol). Metode eliminasi Gauss-Jordan kurang efisien untuk menyelesaikan sebuah SPL, tetapi lebih efisien daripada eliminasi Gauss jika kita ingin menyelesaikan SPL dengan matriks koefisien sama.Jika eliminasi Gauss-Jordan diterapkan dalam matriks persegi, metode tersebut dapat digunakan untuk menghitung invers dari matriks. Eliminasi Gauss-Jordan hanya dapat dilakukan dengan menambahkan dengan matriks identitas dengan dimensi yang sama, dan melalui operasi-operasi matriks:

Kemudian, setelah ditambahkan dengan matriks identitas: Dengan melakukan operasi baris dasar pada matriks[AI] sampai A menjadi matriks identitas, maka didapatkan hasil akhir: Eliminasi Gauss-JordanThomas (1984:93-94) mengatakan bahwa setiap matriks memiliki bentuk eselon baris tereduksi yang unik, artinya kita akan memperoleh bentuk eselon baris tereduksi yang sama untuk matriks tertentu bagaimanapun variasi operasi baris yang dilakukan. Langkah-langkah operasi baris yang dikemukakan oleh Gauss dan disempurnakan oleh Jordan sehingga dikenal dengan Eliminasi Gauss-Jordan, sebagai berikut:1. Jika suatu baris tidak seluruhnya dari nol, maka bilangan tak nol pertama pada baris itu adalah 1. Bilangan ini disebut 1 utama (leading 1).2. Jika terdapat baris yang seluruhnya terdiri dari nol, maka baris-baris ini akan dikelompokkan bersama pada bagian paling bawah dari matriks.3. Jika terdapat dua baris berurutan yang tidak seluruhnya dari nol, maka 1 utama pada baris yang lebih rendah terdapat pada kolom yang lebih kanan dari 1 utama pada baris yang lebih tinggi.4. Setiap kolom memiliki 1 utama memiliki nol pada tempat lain.Misalnya matriks dibawah ini:

Langkah 1. Perhatikan kolom paling kiri yang tidak seluruhnya nol. Langkah 2. Jika perlu, pertukarkan baris paling atas dengan baris lain untuk menempatkan entri taknol pada puncak kolom yang kita peroleh pada langkah 1. Langkah 3. Jika entri yang kini berada pada kolom yang kita peroleh pada langkah 1 adalah a, kalikan dengan baris pertama dengan 1/a sehingga membentuk 1 utama. Langkah 4. Tambahkan kelipatan yang sesuai dari baris paling atas ke baris-baris di bawahnya sehingga semua entri di bawah 1 utama menjadi nol.

Langkah 5. Sekarang tutuplah baris paling atas dari matriks dan mulailah lagi dengan langkah 1 pada submatriks yang tersisa. Lanjutkan langkah ini hingga seluruhnya matriks berada dalam bentuk eselon baris.

Langkah 6. Mulailah dengan baris tak nol terakhir dan bergerak ke atas, tambahkan kelipatan yang sesuai dari tiap-tiap baris ke baris di atasnya untuk memperoleh nol di atas 1 utama.

Langkah 1 5 dinamakan Eliminasi Gauss, jika prosedurnya sampai pada langkah 6 dinamakan Eliminasi Gauss-Jordan. Dari langkah tersebut kita peroleh persamaan:

Dari persamaan tersebut kita dapat memisalkan nilai x2=s dan x3 = t untuk memperoleh nilai x1=7-2s-3t (s dan t adalah parameter dari SPL tersebut).