10 BAB 3
PENYELESAIAN PERSAMAAN NON LINIER
1. METODE BAGI DUA (BISECTION METHOD) Jika f(x) kontinyu pada a dan b dan f(a).f(b) < 0 maka terdapat paling sedikit 1 akar pada interval tersebut.
Lokasi akar a
m2
m1
Gambar 3.1 Proses mencari akar dg metode bagi dua
b
Misal f(a) <0 dan f(b)>0 Nilai akar aproksimasi: x 0 (a b) / 2 (3.1) Jika f(x0) =0, maka x merupakan akar dari f(x). Jika akar terletak antara a dan x0 maka f(x0) > 0 b = x 0 shg x1 (a x 0 ) / 2 Jika akar terletak antara b dan x0 maka f(x0) < 0 a = x0 shg x1 (b x 0 ) / 2 …
(3.2)
… Proses terus shg diproleh f(xn) 0. Program metode biseksi PROGRAM BISEKSI; uses wincrt; var a,b,m,fa,fb,fm i,n
: real; : integer;
Function F(x:real) : real; begin F:=sqr(x*x)-2*x-5; end;
11
BEGIN writeln(' Program Biseksi'); write('batas kiri a:');readln(a); write('batas kanan b:');readln(b); writeln('-----------------------------------------------------------------------------'); writeln(' i a b m fa fb fm '); writeln('-----------------------------------------------------------------------------'); i:=0; repeat m:=(a+b)/2; fa:=F(a); fb:=F(b); fm:=F(m); writeln( ' ',i,''); gotoxy(7,i+7); write(a:3:3) ;writeln(' '); gotoxy(15,i+7); write(b:3:3) ;writeln(' '); gotoxy(23,i+7); write(m:3:3) ;writeln(' '); gotoxy(32,i+7); write(fa:11:7);writeln(' '); gotoxy(48,i+7); write(fb:11:7);writeln(' '); gotoxy(61,i+7); write(fm:11:7);writeln(' '); if fm*fb>0 then b:=m else a:=m; i:=i+1; until abs(fm) <=10e-4; writeln('--------------------------------------------------------------------------'); writeln; writeln('Jadi Akar-akarnya =',m:3:3); readln; END.
Jika program tersebut dijalankan dengan tebakan batas kiri a = 0 dan b = 3
12 Akar yang pertama m14 = 1. Akar yang lain diperoleh dengan memasang a = 2, b = 5 dan m14 =4. Nilai maksimum dari f(m) yang dikehendaki adalah 1.0e-4. Soal: Gunakan metode biseksi untuk memperoleh akar dari f(x) = xsin(x) yang terletak antara [1 , 2].
2. METODE POSISI SALAH (REGULA FALSI) Tujuan: untuk mempercepat proses karena metode bagi dua agak lambat
Gambar 3.2 Proses mencari akar dg metode regula falsi
(a,f(a))
a
b2
b1
b0
(b0,f(b0)) Lihat garis yang menghubungkan titik (a,f(a)), (b1,0) dan (b0,f(b0)). Buat gradien garis tersebut dengan dua cara, yaitu yang melalui pasangan (a,f(a)), (b0,f(b0)) dan (b1,0)) , (b0,f(b0)) Dengan menggunakan titik-titik (a,f(a)) dan (b0,f(b0)) maka: f (b 0 ) f (a) m (3.3) b0 a dengan titik (b1,0) dan (b0,f(b0)) maka: 0 f (b0 ) m (3.4) b1 b0 Pers. (3.3) = pers. (3.4) f (b0 )(b0 a) b1 b0 (3.5) f (b 0 ) f (a) Dalam bentuk iterasi:
bn 1 bn
f (bn )(bn an ) f (bn ) f (an )
Program Regula falsi seperti ditampilkan di bawah ini. PROGRAM REGULA_FALSI; uses wincrt; var a,b,c,fa,fb,fc : real;
(3.6)
13 i,n
: integer;
Function F(x:real) : real; begin F:=sqr(x)-5*x+4; end; BEGIN writeln(' PROGRAM REGULA FALSI'); write('batas kiri a:');readln(a); write('batas kanan b:');readln(b); writeln('-----------------------------------------------------------------------------'); writeln(' i a b c fa fb fc '); writeln('-----------------------------------------------------------------------------'); i:=0; repeat fa:=F(a); fb:=F(b); c:=b-fb*(b-a)/(fb-fa)); fc:=F(c); if fc*fb>0 then b:=c else a:=c; writeln( ' ',i,''); gotoxy(7,i+7); write(a:3:3) ;writeln(' '); gotoxy(15,i+7); write(b:3:3) ;writeln(' '); gotoxy(23,i+7); write(c:3:3) ;writeln(' '); gotoxy(32,i+7); write(fa:11:7);writeln(' '); gotoxy(48,i+7); write(fb:11:7);writeln(' '); gotoxy(61,i+7); write(fc:11:7);writeln(' '); i:=i+1; until abs(fc) <=1.0e-4; writeln('-----------------------------------------------------------------------------'); writeln; writeln('Jadi Akar-akarnya =',c:3:3); readln; END.
Jika program tersebut dijalankan maka diperoleh
14
Akar pertama b8= 1 dengan mengambil a = 0 dan b = 3 sedang akar kedua b8 = 4 dengan mengambil a = 2 dan b = 5. Tampak jumlah iterasi untuk metode biseksi = 14 sementara metode regulafalsi 8 sehingga metode regula falsi lebih efektif digunakan jika batas ketelitian yang dikehendaki sama yaitu tinggi f(m) atau f(b) <= 1.0e-4.
3. METODE REGULAFALSI TERMODIFIKASI
(a,f(a))
a
b2
b1
b0
Jika diketahui f(x) kontinyu pada selang [a0,b0] sedemikian rupa sehingga f(a0)f(b0) < 0, maka: Bentuklah F f (a0 ) dan G f (b0 ) dan c 0 a0 Untuk N = 0, 1, 2, sampai cukup lakukan: a G bnF Hitung c n 1 n G F
Jika f (an ) f (c n1 ) 0 maka an 1 an , bn 1 c n 1 , G f (cn1 ) Jika juga f (c n )f (c n 1 ) 0 , maka F = F / 2 Jika tidak, maka an 1 c n 1 , F f (c n1 ) , bn 1 bn Jika juga f (c n )f (c n 1 ) 0 , maka G = G / 2 {BISA DIUBAH MISAL 0.9G} Maka f(x) mempunyai akar dalam selang [an 1 , bn 1 ] Programnya sebagai berikut PROGRAM REGULA_FALSI_TERMODIFIKASI; uses wincrt; var a,b,c,fa,fb,fc,Ge : real; i,n : integer; Function F(x:real) : real; begin F:=sqr(x)-5*x+4; end;
15
BEGIN writeln(' PROGRAM REGULA FALSI TERMODIFIKASI'); WRITELN('FUNGSI F:=x^2-5x+4'); gotoxy(1,3);write('batas kiri a:');read(a); gotoxy(24,3);write('batas kanan b:');readln(b); writeln('--------------------------------------------------------------------------'); writeln(' i a b c Fa Fb Fc '); writeln('--------------------------------------------------------------------------'); Fa:=F(a); Fb:=F(b); i:=0; Repeat c:=(a*Fb-b*Fa)/(Fb-Fa); Fc:=F(c); writeln( ' ',i,''); gotoxy(7,i+7); write(a:3:3) ;writeln(' '); gotoxy(15,i+7); write(b:3:3) ;writeln(' '); gotoxy(23,i+7); write(c:3:3) ;writeln(' '); gotoxy(32,i+7); write(fa:11:7);writeln(' '); gotoxy(48,i+7); write(fb:11:7);writeln(' '); gotoxy(61,i+7); write(fc:11:7);writeln(' '); if Fa*Fc <=0 then begin b:=c ; Fa:=Fa/2 end else begin a:=c; Fb:=Fb/2; end; i:=i+1; until abs(fc) <=1.0e-4; writeln('-------------------------------------------------------------------------'); writeln; writeln('Jadi Akar-akarnya =',c:3:3); readln; END.
Jika program tersebut dijalankan maka hasilnya dengan tebakan awal 0 dn 3 sebagai berikut:
16
Dengan input 2 dan 5 maka akar yang lain diperoleh = 4 dengan 2 iterasi. Tampak metode regula falsi termodifikasi sangat cepat untuk menampilkan akar.
4. METODE ITERASI SEDERHANA Yang dibutuhkan pada proses iterasi adalah: a. Aproksimasi untuk x0 b. Rumus iterasi Jika persamaan f(x) dituliskan dalam bentuk x = F(x) maka diperoleh iterasi secara berturutan: x1 F( x 0 ) x 2 F( x1 ) x 3 F( x 2 ) (3.7) . . x n 1 F( x n ) Kesalahan pada metode iterasi: E a x i1 x i (3.8)
Ex: Tentukan akar dari f ( x ) x 2 5x 4 (seperti soal sebelumnya)
x2 4 Rumus iterasi pertama: x n 1 n 5 5x n 4 Rumus iterasi kedua: x n 1 xn Rumus iterasi ketiga: x n 1 5 x n 4 Program metode iterasi sebagai berikut: Program iterasi; uses wincrt; var x:array[0..100] of real; b: real; i,n:integer;
17 BEGIN clrscr; writeln('Soalnya: f(x)=sqr(x)-5*x+4'); writeln('Rumus Iterasi: x(i+1)=[x(i)^2+4]/5'); write('tebakan awal x[',i,']:=');readln(x[i]); writeln('---------------------------------------------------------------------'); writeln('i x(i) x(i)^2 [x(i)^2+4]/5 x[i+1]-x[i] '); writeln('---------------------------------------------------------------------'); i:=0; Repeat begin x[i+1]:=(x[i]*x[i]+4)/5; b:= x[i+1]-x[i]; write(i); write(' ',x[i]:4:3); write(' ',x[i]*x[i]:4:5); write(' ',(x[i+1]):5:5); writeln(' ',b:5:7); x[i]:=x[i+1]; i:=i+1; end; until b<=0.00001; writeln('--------------------------------------------------------------------'); writeln('akarnya adalah:',x[i]:4:6); readln; END.
Jika program tersebut dijalankan dengan mengambil tebakan awal x0 = 0 maka diperoleh:
Nilai akarnya tidak seeksak metode sebelumnya aau butuh jumlah iterasi yang banyak.
18 5. METODE AITKEN (PERCEPATAN KONVERGENSI) Misal akar dari f(x). Dari metode iterasi sederhana diketahui: x n1 F ( x n )
F ( ) x n 1 F() F( x n ) K x n dengan K < 1
(3.9)
Misal x i1 , x i , x i1 3 akar yang mengaproksimasi nilai akar x = . Maka
x i K ( x i1 )
(3.10)
x i1 K ( x i )
(3.11)
Dengan membagi (3.10) dg (3.11)1
xi K ( x i1 ) x i1 K ( x i ) ( x i1 x i )2 x i1 2 x i x i1
x i1
( x i )2 x i1 2 x i1
(3.12)
Ingat, disini xi F ( xi ) Tabel yang dibutuhkan adalah tabel selisih berhingga untuk data xi sampai selisih tingkat 2.
xi K ( xi 1 ) xi 1 K ( xi ) xi ( xi 1 ) xi 1 ( xi )
xi 2 xi1 xi1 2
2 2xi xi 2 ( xi 1 xi 1 ) xi 1 xi 1 xi 1 2 xi xi 1 xi 1 xi 1 xi
2
2
xi 1 xi 1 xi x x x i 1 i21 i xi1 2 xi xi 1 xi 1
2
2
x i21 x i21 2 xi 1 xi 2 xi 1 xi xi 1 xi 1 xi
xi 1 ( xi 1 2 xi xi 1 ) ( x 2i 1 2 xi 1 xi xi )
xi 12 xi 1 ( x i 1 xi ) 2
2 xi 1 2
1
2 xi 1 2 xi 1
2
xi 1
xi 2 xi 1
19 x i 1 x i1 2 x i1
xi x i x i 1
Program metode Aitken sebagai berikut: PROGRAM METODE_AITKEN; {ATAU PERCEPATAN KONVERGENSI} uses wincrt; var x,dx,d2x : array[0..100] of real; i,n : integer; BEGIN clrscr; writeln('f(x):=x^2-5x+4'); write('nilai awal x[0]:');readln(x[0]); n:=2; writeln('Rumus Iterasi: x[i]:=(x[i-1]^2+4)/5'); writeln('---------------------------------------------------'); writeln('i x[i] dx[i] d2x[i] '); writeln('---------------------------------------------------'); for i:=0 to n do begin x[i]:=(sqr(x[i-1])+4)/5; gotoxy(1,7+2*i); write(i); gotoxy(4,7+2*i); writeln('x[',i,']=',x[i]:3:4); x[i-1]:=x[i]; end; for i:=0 to n-1 do begin dx[i]:=x[i]-x[i-1]; gotoxy(18,6+(2*i)+2); writeln('dx[',i,']=',dx[i]:3:4); end; for i:=0 to n-2 do begin d2x[i]:=dx[i+1]-dx[i]; gotoxy(35,7+(2*i)+2); writeln('d2x[',i,']=',d2x[i]:3:4); end; x[3]:=x[2]-(sqr(dx[1])/d2x[0]); gotoxy(1,13+(2*i)); writeln('---------------------------------------------------'); gotoxy(1,15+2*i); writeln('x[3]:',x[3]:3:4); END.
Jika dijalankan hasilnya sebagai berikut:
20
Tampak nilai x3 = 0.9956 sudah mendekati akar yang dimaksudkan yaitu 1. Dengan rumus iterasi yang lain maka akar kedua dapat diperoleh.
6. METODE NEWTON RAPHSON
OA 0 x 0
(3.13)
A 0B 0 f ( x 0 )
(3.14)
A0 B0 f ( x0 ) A1 A0 A1 A0
f ' ( x0 ) A1A 0
(3.15)
f (x 0 ) f ' (x 0 )
A1 A0 OA0 OA1 x0 x1
x0 x1
f ( x0 ) f ' ( x0 )
(3.16)
x1 x0
f ( x0 ) f ' ( x0 )
(3.17)
21 dengan cara yang sama maka dapat ditentukan x2, x3 dst. Misal x0 = akar aproksimasi untuk f(x) = 0 sedangkan h = kekeliruan aproksimasi tersebut. x1 x 0 h dan f ( x1 ) 0
(3.18)
Ekspansi dengan deret Taylor:
f ( x1 ) f ( x 0 ) hf ' ( x 0 ) h2f " ( x 0 ) ... 0
(3.19)
Untuk h sangat kecil (supaya aproksimasinya terbaik) maka f " ( x 0 ) diabaikan. f ( x 0 ) hf ' ( x 0 ) 0
h
f (x0 ) f ' (x 0 )
(3.20) (3.21)
Subst. (3.16) ke (3.13):
x1 x 0
f (x 0 ) f ' (x 0 )
(3.22)
Dalam bentuk iterasi menjadi:
x n 1 x n
f (xn ) f ' (xn )
(3.23)
Programnya adalah sebagai berikut: Program Newton_Raphson; uses wincrt; var x,y,dy:array [0..100] of real; tol:real; i:integer; BEGIN clrscr; writeln('f(x)=x^2-5x+4'); write (' Titik awal x[0]: '); readln (x[0]); writeln('---------------------------------------------------'); writeln('i x[i] y(i) dy(i) abs(x[i]-x[i-1])'); writeln('---------------------------------------------------'); i:=1; Repeat y[i-1]:=sqr(x[i-1])-5*x[i-1]+4; {fungsi f(x)} dy[i-1]:=2*x[i-1]-5; {turunan dari f(x)} x[i]:=x[i-1]-(y[i-1]/dy[i-1]);{rumus Newton Raphson} write (i-1 , ' ',x[i-1]:4:4,' ',y[i-1]:4:4,' ',dy[i-1]:4:4); writeln(' ', abs(x[i]-x[i-1]):4:7); tol:=abs(x[i]-x[i-1]); i:=i+1; until i=10; writeln('---------------------------------------------------'); writeln; writeln('Akarnya= ',x[i-1]:3:3); readln; END.
22
Jika dijalankan maka hasilnya sebagai berikut:
Tampak sampai iterasi yang ke 4 selisih antara x[i] dan [xi-1] sudah hamper nol sehingga akarnya adalah 1. Akar ang lain dapat dientukan dengan mengambil x[0] yang lain (misalnya 10). Soal: tentukan akar pers. x sin x cos x 0 dengan metode Newton Raphson. 7. METODE MULLER Permisalan untuk kurva f(x) adalah kuadratis. Akar-akar kurva kudratis dianggap merupakan akar dari kurva f(x). Keunggulan: dapat digunakan untuk menghitung akar komplek Misal x i 2 , x i-1 , x i adalah 3 buh aproksmasi akar f(x) = 0 sehingga ( x i 2 , y i 2 ), (x i-1 , y i 1 ), dan (x i , y i ) terletak pada kurva y = f(x).
y Ax 2 Bx C
(3.24)
y i2 Ax 2i 2 Bx i 2 C
(3.25)
y i1 Axi21 Bx i1 C
(3.26)
y i Ax i2 Bx i C
(3.27)
x2 x i2 1 y i 2 i 2 A 2 y i1 x i1 x i1 1 B y C i x2 x 1 i i
(3.28)
23
yi 2
x2 xi22
xi 2
yi 1
x i21
xi 1 1
yi
xi2
xi
y
x
1 1
(3.29)
0
1
Dapat ditulis dalam bentuk:
y
( x x i1 )( x x i ) ( x x i2 )( x x i ) y i 2 y i1 + ( x i 2 x i1 )( x i2 x i ) ( x i1 x i2 )( x i1 x i ) ( x x i1 )( x x i1 ) yi ( x i x i2 )( x i x i1 )
(3.30)
Jika didefinisikan
(x xi ) ( x i x i1 )
(3.31)
i
( x i x i1 ) ( x i1 x i2 )
(3.32)
i
( x i x i 2 ) 1 i ( x i1 x i2 )
(3.33)
maka pers. (3.30) dapat dituliskan:
y i22i y i1ii y ii 2 y i22i y i12i y i (i i ) y yi i i
(3.34)
Dari pers. (3.31) diperoleh:
x x i ( x i x i1 )
(3.35)
Ambil y = 0 pada (3.34) maka
i ( y i 2 i y i1i y i )2 gi i y i 0
(3.36)
dengan
gi y i 22i y i1i2 y i (i i )
(3.37)
dengan membagi pers. (3.36) dengan 2 maka
1 2
y ii
1 gi i ( y i2 i y i1i y i ) 0
(3.38)
Maka
2y ii
1/2 gi gi2 4 y iii ( y i2 i y i1i y i
(3.39)
24 ex: Tentukan akar dari pers. y ( x ) x 3 3x 5 yang terletak antara 2 dan 3. Jawab: dipilih x i2 1 , x i1 2 , x i 3 maka y i2 7 , y i1 3 , y i 13 sehingga x 3 , i 1 , i 2 dan gi 44 . Dari pers. (3.38) diperoleh:
26 2
44 12 0
1 4 688 52 agar pembilangnya terbesar maka dipilih tanda negatif, maka 0,7403 . Pendekatan berikutnya menurut (3.35) xi 1 xi ( xi xi 1 ) :
xi 1 3 0,7403 2,26 . Iterasi akan dihentikan jika xi 1 xi 8. SOLUSI SYSTEM PERSAMAAN TIDAK LINIER a. Metode iterasi f (x , y) 0 g( x , y) 0 pers. (3.40) dapat dibentuk menjadi: x F( x , y ) y G( x , y ) dengan F dan G memenuhi persyaratan: F F 1 x y G G 1 x y Misal ( x 0 , y 0 ) aproksimasi awal x1 F( x 0 , y 0 ) x 3 F( x 2 , y 2 ) x 2 F ( x 1 , y1 ) y1 G( x 0 , y 0 ) y 2 G( x1 , y1 ) y 3 G( x 2 , y 2 ) dan seterusnya hingga diperoleh x n 1 x n dan y n 1 y n .
(3.40)
(3.41)
(3.42)
(3.43)
2. METODE NEWTON RAPHSON f (x , y) 0 g( x , y) 0
(3.44)
Misal ( x 0 , y 0 ) aproksimasi awal dari (3.44). Jika ( x 0 h, y 0 k ) akar dari system pers. tersebut maka: f ( x 0 h, y 0 k ) 0 g( x 0 h, y 0 k ) 0
Ekspansi f dan g menurut deret Taylor menghasilkan:
(3.45)
25 f f k ... 0 x 0 y 0 g g g0 h k ... 0 x 0 y 0 f0 h
(3.46)
dengan mengabaikan suku-suku berderejat >=2 maka f f k ... f0 x 0 y 0 g g h k ... g0 x 0 y 0 h
(3.47)
maka h, k dikatahui. Hasil aproksimasi yang baru adalah: x 1 x 0 h , y1 x 0 k . Proses diulangi hingga diperoleh x n 1 x n dan y n 1 y n . SOAL 1. Tentukan akar dari pers. (a) x 3 x 2 x 7 0 (b) x 3 18 0 teliti sampai 3 angka decimal dengan metode Muller 2. Gunakan metode Newton-Raphson untuk menyelesaikan pers. (a) x 2 y 11
y2 x 7
(b) x 2 4 3 sin y
y 2 4 3 sin x
26
