Loading Preview
Sorry, preview is currently unavailable. You can download the paper by clicking the button above.
Pencarian Akar Persamaan Non Linear
1.1 Pendahuluan Dalam bab ini, kita akan membahas tentang beberapa metode numerik yang dapat digunakan untuk menemukan akar-akar persamaan non-linier. Masalah yang akan kita bahas tersebut secara matematis dapat diterangkan sebagai pencarian harga-harga x sedemikian hingga memenuhi persamaan non-liner ( ) Manakala kita mengatakan bahwa ( ) adalah fungsi non-linier dalam , ini berarti bahwa ( ) tidak dinyatakan dalam bentuk , dimana dan merupakan konstanta dan manakala kita mengatakan bahwa ( ) adalah fungsi aljabar, ini berarti bahwa fungsi tersebut tidak melibatkan bentuk diferensial . Masalah menemukan akar dari suatu persamaan non linier ini merupakan masalah yang muncul dalam berbagai disiplin ilmu. Contoh sederhana dari persamaan nonlinier adalah persamaan kuadratik yang berbentuk ( )
Persamaan non linier yang lain misalnya, 1. 2. 3. ( ) ( ) ( )
Dalam kenyataannya, akar-akar persamaan non linier tersebut tidak mudah untuk ditemukan secara analitik, kecuali pada kasus-kasus sederhana. Oleh sebab itu, alasan utama mengapa penyelesaian masalah pencarian akar persamaan nonlinier memerlukan pendekatan numerik disebabkan karena penyelesaian menggunakan cara analitik biasanya akan menemui kesulitan, meskipun persamaan tersebut kelihatannya sederhana. Hal inilah yang menjadi sebab mengapa metode numerik menjadi sangat diperlukan dalam memecahkan persoalan-persoalan dalam bidang sains dan teknologi bahkan ekonomi sekalipun.
Di dalam bab ini kita akan mempelajari berbagai teknik pendekatan numerik untuk masalah mendapatkan akar persamaan nonlinier. Cara termudah sudah kita perlihatkan secara sekilas pada bab 1 yaitu dengan cara grafis. Teknik tersebut sebenarnya tidak termasuk ke dalam metode numerik, mengingat teknik ini tidak melewati serangkaian kaidah-kaidah analisis numerik. Meskipun demikian kita akan membahasnya karena pada saatnya nanti akan sangat berguna ketika kita memerlukan terkaan awal dari sebuah akar persamaan yang dicari. Disamping itu, beberapa metode numerik akan dibahas secara detail antara lain metode bagi dua (bisection), Newton-Raphson, posisi palsu (regulafalsi/interpolasi linier), Secant dan metode iterasi langsung.
2.1 Metode Bagi Dua (BISECTION) 2.1.1 Defenisi Metode Bagi Dua Metode bagi dua merupakan metode analisis numerik paling sederhana diantara metode-metode analisis lainnya. Metode ini termasuk metode yang robust atau tangguh. Artinya, meskipun metode ini idenya sangat sederhana namun selalu dapat menemukan akar persamaan yang dicari. Salah satu kekurangan yang dimiliki oleh metode ini adalah bahwa kita harus menentukan dua terkaan awal, yaitu apabila dan ( yang mengurung sebuah akar persamaan yang idcari, sehingga ) dan ( ) , maka akan dipenuhi . Contoh dari maka salah
masalah ini digambarkan pada gambar 1. Apabila dipenuhi satu dari dan yang berada pada
atau keduanya merupakan akar
persamaan yang dicari. Algoritma dasar dari metode bagi dua dapat dinyatakan sebagai berikut: Algoritma dasar dari metode bagi dua dapat dinyatakan sebagai berikut: 1. Tentukan 2. Tentukan 3. Apabila ( ) ( ( ) , maka ) ( ) ( )
merupakan penyelesaian eksaknya
4. Apabila
, maka akar persamaan berada di dalam interval
5. Apabila interval
atau
, maka akar persamaan berada di
6. Ulangi proses nomor 2 hingga nomor 5 sampai interval yang mengurung akar persamaan sudah sangat sempit.
Gambar 1Pencarian Akar dengan Metode Bagi 2
Berikut gamabaran algoritma pencarian bagi dua pada flowchart :
Gambar 2Flowchart MetodeBagi 2
Dengan selalu mengupdate interval( (
) baik dengan (
) maupun , ( )
) tergantung pada interval mana yang mengurung akar persamaan
maka kesalahan (error) dalam penaksiran terhadap akar persamaan
adalah rata rata dari kedua interval tersebut dibagi dua. Kita akan mengulangi prosedur membagi dua interval secara terus menerus hingga ditemukan akar persamaan yang sudah sangat dekat dengan harga eksaknya atau syukur-syukur diperoleh harga eksaknya. 2.1.2 Kriteria Henti Metode Bagi Dua Biasanya, pencarian akar persamaan secara numerik tidak akan pernah menemukan harga eksak dengan kesalahan sama dengan nol. Yang dapat dilakukan hanyalah pendekatan dengan tingkat ketelitian tertentu. Untuk menghindari pencarian akar secara terus-menerus tanpa henti, maka diperlukan suatu syarat agar proses tersebut dapat dihentikan. Nah hal ini perlu dengan apa yang dimanakan harga toleransi. Harga toleransi untuk menghentikan pencarian terus menerus ini dapat diatur sesuai kebutuhan. Contoh Ditinjau sebuah fungsi nonlinier ( ) ( ) ( ) seperti digambarkan
pada gambar 3. Dengan menggunakan metode bagi dua akan ditunjukkan cara memperoleh akar persamaan akar diberikan dan . Terkaan awal untuk mengurung
Gambar 3Grafik Fungsi f(x) = cos(x)-x
Peneyelesaiannya Langkah pertama, kita lakukan perhitungan untuk terkaan awal yang diberikan, yaitu : Untuk Untuk ( ) ( ) ( ) ( )
Dari dua harga fungsi yang berhubungan dengan terkaan awal yang diberikan hasilnya diuji dan menurut hitungan diperoleh bahwa hasil kalinya berharga negatif. Ini berarti bahwa harga terkaan tersebut telah mengurung akar persamaan yang sedang dicari. Selanjutnya diteruskan dengan menghitung 3 x dengan cara merataratakan kedua terkaan awal dan dihitung ( )
(
) Karena
(
)
( ) berharga positif maka akar persamaan berada di antara , karena ( ) ( ) .
absis
dan
Langkah berikutnya adalah membuat setengah interval berikutnya yang mengurung akar persamaan yang dicari. Demikian prosedur tersebut diulangulang hingga interval yang mengurung akar tersebut sangat dekat dengan akar eksaknya. 2.2 Metode Posisi Palsu (Regula Falsi/Interpolasi Linier) Metode posisi palsu mirip dengan metode bagi dua. Kemiripannya terletak dalam hal diperlukan dua harga taksiran awal pada awal pengurungan akar persamaan. Sedangkan, perbedaannya terletak pada proses pencarian pendekatan akar persamaan selanjutnya setelah pendekatan akar saat ini ditemukan. Prinsip pencarian akar persamaan dari metode ini didasarkan pada penggunaan interpolasi linier seperti diperlihatkan pada gambar 4. Interpolasi linier 1 dilakukan melalui dua titik pertama. Garis interpolasi memotong sumbu x dan dititik perpotongan tersebut kita dapatkan pendekatan akar yang pertama. Kemudian pendekatan tersbut dievaluasi pada fungsi nonlinier sehingga diperoleh titik pada fungsi nonlinier tersebut. Kemudian dilakukan lagi interpolasi melalui ujung sebelumnya dan diperoleh pendekatan akar berikutnya. Demikian seterusnya, hingga diperoleh harga pendekatan akar yang sudah sangat dekat dengan akar persamaan eksaknya. Perhatikan pula bahwa titik tolak interpolasi berasal dari satu titik tertentu. Jika sebuah akar persamaan berada pada interval linier yang melalui titik ( ( )) dan ( , maka fungsi
( )) dapat dituliskan sebagai
Selanjutnya, jika pernyataan (2-4) dinyatakan dalam x , maka dapat sebagai ( ) ( ) ( ) ( )
Selanjutnya, jika pernyataan (2-4) dinyatakan dalam x , maka dapat ditulis sebagai
(
)
(
)
(
(
))
Saat garis interpolasi memotong sumbu x di titik ( harga ( ) dinyatakan oleh ( ( ) ( ) ( )
( )) , dimana
(
)
(
)
( ) ( )
Setelah menemukan titik xb , maka sekarang interval [ xa , xb ] dibagi menjadi [ xa , xc ] dan [ xc , xb ] . Apabila dipenuhi f(xa) f(xc) < 0 , maka akar yang dicari berada di dalam interval [ xa , xc ] , sebaliknya jika f(xa) f(xc) > 0 atau f(xc) f(xb) < 0 , maka akar tersebut berada di dalam interval [ x c , xb ] . Sekarang diupdate harga xb yang baru dengan harga xc yang baru saja kita peroleh, sehingga pencarian akar persamaan tetap pada interval [ xa , xb ] . Prosedur interpolasi diulang lagi hingga akar taksiran mencapai konvergen ke akar sebenarnya. Kelemahan dari metode posisi palsu ini adalah bahwa salah satu ujungnya tidak mengalami perpindahan atau stagnan seperti terlihat pada gambar 1. Dengan demikian pendekatan ke harga akar sebenarnya hanya berasal dari salah satu ujung saja. Algoritma metode posisi palsu dapat dinyatakan sebagai berikut 1. Berikan terkaan awal xa dan xb yang mengurung akar persamaan; 2. Untuk menguji bahwa terkaan awal mengurung akar persamaan maka ujilah apakah f(xa) f(xb) < 0 , jika ya maka terkaan kita sudah benar. 3. Tentukan salah satu titik yang akan digunakan sebagai titik tolak interpolasi linier misalnya (xa, fa) . 4. Tentukan xc dengan cara ( ) ( ) ( ) ( ) ( ( ))
( ) ( )
5. Update harga xb dengan xc dan f b dengan f c .
6. Ulangi proses dari poin 4 hingga ditemukan harga xc yang sudah sangat dengan akar sebenarnya. Oleh karena pada setiap langkah akar persamaan selalu terkurung dalam suatu interval, maka konvergensi dapat dijamin seperti halnya pada metode bagi dua. Metode tersebut dapat memberikan harga eksak jika fungsi f linier.
2.3 Metode Newton-Raphson 2.3.1 Defenisi Metode Newton-Raphson Metode Newton-Raphson merupakan metode yang paling sering digunakan diantara metode-metode pencarian akar persamaan yang lain. Metode ini sederhana, namun cukup handal dalam mendapatkan akar persamaan nonlinier, dengan catatan terkaan awal yang diberikan cukup dekat. Metode NewtonRaphson tidak memerlukan dua buah terkaan awal seperti halnya metode bagi dua dan Regula Falsi, melainkan cukup satu saja tetapi diusahakan terkaan tersebut cukup dekat dengan akar persamaan yang dicari. Ide dari metode ini dapat dijelaskan sebagai berikut. Jika kita memberikan satu terkaan awal x = xn terhadap akar persamaan x0 , maka kita memiliki titik (xn,f(xn)) pada fungsi. Dengan menarik garis singgung pada titik tersebut dan diperpanjang hingga memotong sumbu x, maka kita akan memperlol
Page 2
BabBab 7 7 SistemSistem PesamaanPesamaan LinierLinier
OlehOleh ::Devie Rosa Devie Rosa AnamisaAnamisa
PendahuluanPendahuluan BentukBentuk umumumum daridari aljabaraljabar linier linier sebagaisebagai berikutberikut::
aa1111XX11 + a+ a1212XX22 + ...... + a+ ...... + a1n1nXXnn = b= b11aa2121XX11 + a+ a2222XX22 + ..... + a+ ..... + a2n2nXXnn = b= b22...... ...... ..... ........ .......... ...... ..... ........ ....aam1m1XX11 + a+ am2m2XX22 + ...... + + ...... + aamnmnXXnn = = bbnndimanadimana ::a = a = koefisienkoefisien konstantakonstantax x = = variabelvariabeln = n = jumlahjumlah variabelvariabelb = b = konstantakonstanta
PersamaanPersamaan tersebuttersebut dalamdalam matrikmatrik akanakan ditulisditulis sebagaisebagaiberikutberikut::
dapatdapat ditulisditulis : A x = B: A x = B MatriksMatriks adalahadalah suatusuatu lariklarik bilanganbilangan yang yang berbentukberbentuk
empatempat persegipersegi panjangpanjang.. MisalMisal : a: a23 23 mempunyaimempunyai artiarti elemenelemen yang yang terletakterletak padapada
barisbaris 2 2 dandan kolomkolom 3 3
AugmentasiAugmentasi MatrikMatrik
AugmentasiAugmentasi matrikmatrik ((perluasanperluasan matrikmatrik) ) adalahadalahperluasanperluasan matrikmatrik A A dengandengan menambahkanmenambahkanvector B vector B padapada kolomkolom terakhirterakhir..
MacamMacam macammacam matriksmatriks MatrikMatrik simetrisimetri, , apabilaapabila aijaij = = ajiaji, , misalmisal matrikmatrik simetrissimetris
3x3.3x3. MatrikMatrik diagonal diagonal adalahadalah matriksmatriks bujurbujur sangkarsangkar dimanadimana
semuasemua elemenelemen kecualikecuali diagonal diagonal utamautama adalahadalah nolnol.. MatrikMatrik identitasidentitas adalahadalah matriksmatriks diagonal diagonal dimanadimana semuasemua
elemenelemen padapada diagonal diagonal utamautama adalahadalah 1.1. MatriksMatriks segitigasegitiga atasatas adalahadalah matriksmatriks dimanadimana semuasemua
elemenelemen dibawahdibawah diagonal diagonal utamautama adalahadalah nolnol.. MatriksMatriks segitigasegitiga bawahbawah adalahadalah matriksmatriks dimanadimana semuasemua
elemenelemen diatasdiatas diagonal diagonal utamautama adalahadalah nolnol.. MatriksMatriks pita pita adalahadalah matrikmatrik yang yang mempunyaimempunyai elemenelemen
samasama dengandengan nolnol, , kecualikecuali padapada jalurjalur yang yang berpusatberpusat padapadadiagonal diagonal utamautama atauatau disebutdisebut matrikmatrik tridiagonaltridiagonal..
OperasiOperasi PadaPada MatriksMatriks PenjumlahanPenjumlahan::
A + B = B + AA + B = B + A (A+B)+C = A + (B +C)(A+B)+C = A + (B +C)
PenguranganPengurangan:: A A B B B B AA A A B = |B B = |B A|A|
PerkalianPerkalian:: (AB)C = A(BC)(AB)C = A(BC) (A+B)C = AC + BC(A+B)C = AC + BC A(B+C) = AB + ACA(B+C) = AB + AC
InversInvers:: A B x = b1A B x = b1
C D y b2C D y b2
makamaka A . AA . A--11 = I= I
MetodeMetode PersamaanPersamaan LinierLinier
EliminasiEliminasi GaussGauss MenjadikanMenjadikan persamaanpersamaan linier yang linier yang terdiriterdiri daridari
beberapabeberapa bilanganbilangan yang yang tidaktidak diketahuidiketahui menjadimenjadi satusatubilanganbilangan taktak diketahuidiketahui ((dengandengan membuatmembuat suatusuatumatriksmatriks triangular triangular atasatas).).
ProsedurProsedur eliminasieliminasi gausgaus:: SusunSusun matriksmatriks untukuntuk persamaanpersamaan yang yang akanakan diselesaikandiselesaikan GunakanGunakan operasioperasi penjumlahanpenjumlahan sederhanasederhana antarantar barisbaris untukuntuk
memperolehmemperoleh matriksmatriks triangular triangular atasatas / / bawahbawah TulisTulis kembalikembali barisbaris terbaruterbaru dalamdalam persamaanpersamaan matriksmatriks SelesaikanSelesaikan sistemsistem persamaanpersamaan terbaruterbaru dengandengan caracara subtitusisubtitusi
mundurmundur
ContohContoh EliminasiEliminasi GausGaus CarilahCarilah x, y x, y dandan z z daridari persamaanpersamaan berikutberikut iniini ::
X + Y + Z = 0X + Y + Z = 0 X X 2Y + 2Z = 42Y + 2Z = 4 X + 2Y X + 2Y Z = 2Z = 2
JawabJawab :: AugmentasiAugmentasi matriksmatriks ::
1 1 1 0 B11 1 1 0 B11 1 --2 2 4 B22 2 4 B21 2 1 2 --1 2 B31 2 B3
BarisBaris 3 3 dikurangidikurangi barisbaris 1 (B31 (B3--B1) :B1) :1 1 1 01 1 1 01 1 --2 2 42 2 40 1 0 1 --2 22 2
BarisBaris 2 2 dikurangidikurangi barisbaris 1 (B2 1 (B2 B1) :B1) :1 1 1 01 1 1 00 0 --3 1 43 1 40 1 0 1 --2 22 2
BarisBaris 3 3 dikalidikali 3 3 kemdiankemdian ditambahditambah dengandengan barisbaris 2 :2 :1 1 1 01 1 1 00 0 --3 1 43 1 40 0 0 0 --5 105 10
--5Z = 10 5Z = 10 Z = Z = --2 ......(3)2 ......(3)--3Y + Z = 4 ..... (2)3Y + Z = 4 ..... (2)--3Y + 3Y + --2 = 4 2 = 4 --3Y = 6 3Y = 6 Y = Y = --22X + Y + Z = 0 .....(1)X + Y + Z = 0 .....(1)X + X + --2 + (2 + (--2) = 0 2) = 0 X = 4X = 4
JadiJadi dapatdapat disimpulkandisimpulkan x=4, y =x=4, y =--2 2 dandan z=z=--22
EliminasiEliminasi GausGaus JordanJordan MiripMirip dengandengan metodemetode eliminasieliminasi gausgaus AlgoritmaAlgoritma ::
TulisTulis sistemsistem persamaanpersamaan dalamdalam matrikmatrik augmentasiaugmentasi[[sistemsistem] ] [A|B][A|B]
UbahUbah matrikmatrik [A|B] [A|B] kedalamkedalam bentukbentuk::[A|B] [A|B] [I|C] [I|C] dimanadimana I I adalahadalah matrikmatrik identitasidentitas
KetikaKetika langkahlangkah keduakedua sudahsudah terpenuhiterpenuhi, , tulistulismatriksmatriks [I|C] [I|C] sebagaisebagai hasilhasil akhirakhir persamaanpersamaan..
ContohContoh EliminasiEliminasi GausGaus JordanJordan CarilahCarilah x, y x, y dandan z z daridari persamaanpersamaan berikutberikut iniini ::
X + Y = 3X + Y = 3 X X 4Y = 84Y = 8
JawabJawab :: AugmentasiAugmentasi matriksmatriks ::
1 1 3 B11 1 3 B11 1 --4 8 B24 8 B2
BarisBaris 2 2 dikurangidikurangi 2 2 dikalidikali barisbaris 1 (B21 (B2--2B1) :2B1) :1 1 3 1 1 3 1 2 2 1 2 2
BarisBaris 2 2 dibagidibagi 2 :2 :1 1 31 1 30 1 10 1 1
BarisBaris 1 1 dikurangidikurangi dengandengan barisbaris 2 :2 :1 0 2 1 0 2 0 1 10 1 1
JadiJadi Y = 1 Y = 1 dandan X = 2X = 2
MetodeMetode CholeskyCholesky MempunyaiMempunyai unsurunsur koefisienkoefisien variabelvariabel yang yang
simetrissimetris MatrikMatrik simetrisimetri dinyatakandinyatakan dalamdalam produkproduk
matrikmatrik triangular triangular bawahbawah dengandengan matrikmatriktriangular triangular atasatas dengandengan keduakedua matrikmatrik satusatusamasama lain lain adalahadalah matrikmatrik transposetranspose
FaktorisasiFaktorisasi matrikmatrik : [A] =[: [A] =[U]U]trasnposetrasnpose [U][U]
aa1111 aa1212 aa1313 uu1111 0 0 u0 0 u1111 uu2121 uu3131aa2121 aa2222 aa2323 = u= u2121 uu2222 0 * 0 u0 * 0 u2222 uu2323aa3131 aa3232 aa3333 uu3131 uu3232 uu3333 0 0 u0 0 u3333
HubunganHubungan UnsurUnsur aaijij dandan uuijij :: PadaPada barisbaris pertamapertama ::
UU1n1n = = aainin / a/ a1111JadiJadi ::UU1111 = a= a1111 , U, U1212 = a= a1212 / a/ a11 11 , U, U1313 = a= a1313 / a/ a1111
PadaPada BarisBaris KeduaKedua ::UU2222 = (a= (a2222 uu1212) = (a) = (a2222 (a(a1212/ a/ a1111))UU2323 = [(a= [(a2323 uu12 12 uu1313)/ u)/ u2222]]
PadaPada BarisBaris KetigaKetiga ::U33 = (aU33 = (a2323 uu1313 uu2323))
ContohContoh :: TentukanTentukan matrikmatrik [[u]u]transposetranspose.[u.[u] ] daridari matrikmatrik
[A] = 9 [A] = 9 --3 63 6--3 17 3 17 --10106 6 --10 1210 12
DenganDengan [u] = [u] = uu11 11 uu12 12 uu13130 0 uu21 21 uu13130 00 0 uu3333
PelajariPelajari keluarkeluar didi UAS!!!!UAS!!!! MetodeMetode IterasiIterasi
GausGaus SeidelSeidel AdalahAdalah metodemetode yang yang menggunakanmenggunakan prosesproses iterasiiterasi hinggahingga
diperolehdiperoleh nilainilai--nilainilai berubahberubah BilaBila diketahuidiketahui persamaanpersamaan linier:linier:
a11X1 + a12X2 + ...... + a1nXn = b1a11X1 + a12X2 + ...... + a1nXn = b1
a21X1 + a22X2 + ..... + a2nXn = b2a21X1 + a22X2 + ..... + a2nXn = b2...... ...... ..... ........ .......... ...... ..... ........ ....am1X1 + am2X2 + ...... + am1X1 + am2X2 + ...... + amnXnamnXn = = bnbn
BerikanBerikan nilainilai awalawal daridari setiapsetiap Xi (i=1 Xi (i=1 s/ds/d n) n) kemudiankemudian sistemsistempersamaanpersamaan linier linier diatasdiatas ditulisditulis menjadimenjadi:: XX11 = 1/a= 1/a1111 (b(b11 aa1212xx2 2 -- aa1313xx3 3 --........-- aa1n1nxxnn)) XX22 = 1/a= 1/a2222 (b(b22 aa2121xx1 1 -- aa2323xx3 3 --........-- aa2n2nxxnn)) XXnn = 1/a= 1/annnn ((bbnn aan1n1x1x1--aan2n2xx22--...a...a2n2nxxnn))
ContohContoh:: SelesaikanSelesaikan sistemsistem persamaanpersamaan berikutberikut dengandengan metodemetode
iterasiiterasi gauss gauss seidelseidel untukuntuk mendapatkanmendapatkan nilainilai x, y x, y dandanz:z: 3x + y 3x + y z =5z =5 4x + 7y 4x + 7y 3z = 203z = 20 2x 2