CONTOH SOLUSI UTS ANUM 2014 1 1 Propagasi eror adalah kejadian di mana eror dari operan suatu komputasi sederhana memberikan eror yang lebih besar pada hasil komputasi tersebut. Misalnya, eror awal suatu representasi bilangan pada presisi berhingga biasanya relatif tidak besar. Namun, dengan melakukan beberapa komputasi, eror ini akan berkontribusi pada eror bilangan yang dihasilkan komputasi tersebut, di mana ada potensi kontribusi ini berakibat buruk pada akurasi. Untuk rumus rekurensi pertama: • e1 = x1 − x(1) = (10x0 + 1) − (10x(0) + 1) = 10e0 • e2 = x2 − x(2) = (10x1 + 1) − (10x(1) + 1) = 10e1 = 100e0 • e3 = x3 − x(3) = (10x2 + 1) − (10x(2) + 1) = 10e2 = 1000e0 . Untuk rumus rekurensi kedua: • e1 = x1 − x(1) = 2−x(0) (2−e0 − 1) • e2 = x2 − x(2) = 2−x(1) (2−e1 − 1) • e3 = x3 − x(3) = 2−x(2) (2−e2 − 1). Pada rumus rekurensi pertama, terjadi amplifikasi 1000 kali eror semula. Pada rumus rekurensi kedua, dapat dilihat bahwa tidak terjadi propagasi eror. Dapat dilihat bahwa meskipun nilai ei negatif, maka nilai ei+1 akan menjadi positif lagi sehingga erornya tidak terpropagasi, namun hanya damping (naik/turun dan mengecil).
1 TB,
HS, AP, AR, AY, LH, RO
1
2 Menggunakan perhitungan demikian, ada beberapa langkah perhitungan yang kita lakukan: x0 := A x1 := x0 + 1 √ x2 := x1 √ x3 := x0 x4 := x2 − x3 . Komputasi x0 , x1 , x2 , x3 sudah stabil. Namun, untuk evaluasi x4 , definisikan g(t) = x2 − t, maka condition number untuk fungsi ini adalah 0 g (t)t t = g(t) x2 − t . Dari condition number ini, evaluasi g akan stabil kecuali saat t ≈ x2 dan t cukup besar. Kasus ini terjadi untuk x yang sangat besar. Sebagai contoh untuk yang ill-conditioned, t = 1010 maka x2 − t ≈ 5 × 10−6 , maka untuk komputasi x4 , condition number-nya adalah 21 × 1016 . Sebagai contoh untuk yang well-conditioned, t = 0.1 maka x2 − t ≈ 0.7236, maka condition number-nya adalah 0.1365. Formula ekivalen untuk f adalah 1 √ . f (x) = √ x+ x+1 Langkah-langkah komputasi untuk formula ini dapat ditunjukkan well-conditioned secara umum.
2
3 Dengan sifat matriks tersebut, hanya terdapat satu elemen tak nol di bawah setiap diagonal. Oleh karena itu, untuk memfaktorisasi A menjadi U pada setiap iterasi, hanya terdapat satu elemen yang perlu dinolkan. Dengan kata lain, hanya terdapat satu baris yang perlu di-update pada setiap iterasi. Sehingga, pada setiap langkah operasi ke-k, kita hanya perlu meng-update vektor berukuran n − k. Secara total, kompleksitasnya adalah n−1
∑ i = O(n2 ).
i=1
Proses faktorisasi LU: L U cost 1 1 3 6 1 2 2 1 0 −2 −5 0 −1 0 5 0 1 8 3 4 5 0 0 0 1 9 4 5 0 1 0 5 6 0 0 1 1 3 6 1 2 2 1 0 −2 −5 0 −1 5 0 0 −9 3 1 4 − 1 2 2 0 0 9 4 5 0 1 0 5 6 0 1 0 0 1 1 3 6 1 2 0 −2 −5 0 −1 2 1 0 0 −9 3 3 1 − 52 1 2 0 0 0 10 8 −2 1 0 5 6 0 1 0 0 1 1 3 6 1 2 0 −2 −5 0 −1 2 1 0 0 −9 3 − 52 1 2 1 2 0 0 −2 1 0 10 8 1 0 0 0 0 2 1 2 ~ Setelah memperoleh LU, kita menyelesaikan LU~x = b. Untuk menyelesaikan L~y = ~b, kita gunakan Forward Algorithm: 1 −2 1 5 1 −2 −2 1 1 1 2
y1 y2 y3 y4 y5
= ~y =
Untuk menyelesaikan U~x =~y, kita gunakan Backward Algorithm: 1 3 6 1 2 0 −2 −5 0 −1 0 0 −9 3 1 2 0 0 0 10 8 0 0 0 0 2
x1 x2 x3 x4 x5
= ~x =
3
5 6 4 10 1
5 −4 −6 −2 2
5 −4 −6 −2 2
1 −1 1 −1 1
.
.
4 Algoritma LU−factorization dengan partial pivoting: U=A, L= I , P= I f o r k = 1 t o m−1 S e l e c t i >= k t o maximize | u ( i , k ) | u ( k , k :m) <−> u ( i , k :m) l ( k , 1 : k −1) <−> l ( i , 1 : k −1) p ( k , : ) <−> p ( i , : ) f o r j = k+1 t o m l ( j , k) = u( j , k )/ u(k , k) u ( j , k :m) = u ( j , k :m) − l ( j , k ) u ( k , k :m) Proses faktorisasi LU, dengan i, L, P,U mengacu pada algoritma di atas (satu baris pada tabel adalah satu buah iterasi k): i U L P L U 1 0 0 0 −3 −3 8 −3 −3 8 −2 1 0 0 0 0 0 1 0 20 1 0 1 0 0 0 1 0 0 −1 1 0 0 0 1 2 4 3 3 32 3 10 2 0 0 1 0 1 0 0 0 − 4 −2 −2 2 0 1 0 0 3 3 1 10 −1 1 6 −3 0 0 0 1 0 0 0 1 0 0 1 0 2 3 3 −3 −3 8 −2 1 0 0 0 1 0 0 0 −3 −3 8 0 0 1 0 10 10 0 2 1 0 0 1 0 0 0 −2 1 0 0 0 2 − 10 2 3 3 −3 3 31 1 3 20 11 1 5 0 0 1 0 0 1 −3 0 1 0 −3 2 1 0 −3 0 0 3 2 10 7 1 1 0 0 0 1 0 0 0 0 2 −3 0 0 1 1 0 1 3 3 3 Sudah didapatkan matriks P, L, dan U (tiga matriks terakhir pada tabel). Untuk mencari solusi persamaan A~x = ~b, akan diselesaikan LU~x = P~b. Gunakan algoritma Forward pada L~y = P~b, 1 0 0 0 7 −2 1 0 0 31 1 ~y = −4 − 5 1 0 3 2 1 7 1 0 1 3 7 2 3 ~y = 7 . 4 Gunakan algoritma Backward pada U~x =~y,
−3 0 0 0
−3 2 0 0
8 10 3
5 0
4
7 −2 2 − 10 3 3 ~ x = 7 −2 1 4 1 2 ~x = 3 . 4
−2 − 11 3 − 10 3 − 73 2 − 10 3 −2 1
5 Model untuk aproksimasi di atas adalah berupa overdetermined-system 1 0 0 0 1 0 a b = 0 0 1 −1 1 0 c 0 −1 1
1950 2350 2700 350 500
di mana a, b, c berturut-turut merupakan tinggi gunung A, B,C. Dengan mendapatkan estimasi yang baik bagi a, b, c, kita menggunakan persamaan normal sehingga persamaan menjadi 2 −1 0 a 1600 −1 3 −1 b = 2200 0 −1 2 c 3200 yang dapat diselesaikan menggunakan sistem eliminasi biasa sehingga diperoleh a = 1950, b = 2300, c = 2750.
5
6 Cara 1. Jika f (x1 , x2 ) = (2x1 − 1)2 + (−x1 + x2 )2 + (2x2 + 1)2 , kita ingin meminimalkan f . Perhatikan bahwa x1 10x1 − 2x2 − 4 ∇f = x2 −2x1 + 10x2 + 4 sehingga dapat dilihat f = 0 dipenuhi oleh x1 = 31 dan x2 = − 31 . Dengan memeriksa determinan turunan kedua, dapat ditunjukkan bahwa di (x1 , x2 ), nilai f menjadi minimum, yaitu f
1 1 ,− 3 3
2 2 1 1 2 1 1 2 = 2× −1 + − − + 2 − +1 = . 3 3 3 3 3
Cara 2. Ekspresi tersebut adalah eror dari overdetermined system 2x1 = 1 −x1 + x2 = 0 2x2 = 1 atau dapat ditulis sebagai
2 −1 0
0 1 x 1 1 = 0 . x2 2 −1
Eror akan minimal jika kita menggunakan persamaan normal yaitu A> A~x = A>~b: 2 0 2 −1 0 x1 2 −1 −1 1 = 0 1 2 x2 0 1 0 2 5 −1 x1 2 = −1 5 x2 −2
0 2
1 0 −1
5x1 − x2 = 2 −x1 + 5x2 = −2 dan dari sistem persamaan ini diperoleh x1 =
1 3
dan x2 = − 13 .
Hasil yang didapatkan dari cara pertama maupun cara kedua adalah sama, yaitu x1 =
6
1 3
dan x2 = − 13 .
7 f (x) = x2 − cos(πx) (a) Untuk menghitung jumlah solusinya, bisa dengan melihat grafik x2 = cos(πx).
Terlihat bahwa kurva biru (x2 ) dan kurva hijau (cos(πx)) berpotongan di dua titik. Jadi, x2 − cos(πx) = 0 mempunyai dua solusi. (b) Syarat interval untuk Metode Bisection agar berhasil mencari akar tunggal di interval [a, b] adalah nilai f yang berbeda tanda untuk f (a) dan f (b). Karena ingin mencari akar terkecil, dari grafik (a) dapat dilihat bahwa akarnya terletak di interval [−1, 0]. Interval ini dapat digunakan karena (−1)2 = 1 ≥ 0 dan cos(−π) = −1 ≤ 0, serta 02 = 0 ≤ 0 dan cos(0) = 1 ≥ 0. Terlihat pula di grafik bahwa memang terdapat akar tunggal di interval [−1, 0]. (c) Metode Newton adalah metode yang konvergen lokal, sehingga perlu dispesifikasi nilai tebakan awal x0 yang cukup dekat dengan solusi (yaitu, berada di interval penyelesaian x dari pertidaksamaan |g0 (x)| < 1 yang mengandung x∗ ). Karena yang ingin dicari adalah akar terkecil, maka nilai x0 = −0.5 adalah tebakan awal yang meyakinkan (agar tidak melaju ke akar yang lebih besar). f (x) = x2 − cos(πx) f 0 (x) = 2x + π sin(πx) x(i+1) = x(i) −
f (x(i) ) f 0 (x(i) )
f (x(0) ) f 0 (x(0) ) 0.25 = −0.5 − −4.146 = −0.4396.
x(1) = x(0) −
f (x(1) ) f 0 (x(1) ) 0.0048 = −0.4396 − −3.9645 = −0.438.
x(2) = x(1) −
x(3) = x(2) −
f (x(2) ) f 0 (x(2) )
= −0.438 − = −0.438.
7
0 −3.9599
8 Metode Newton untuk Sistem Persamaan Nonlinier
Misalkan inisial awal
x(0)
F(x) =
x1 + x2 − x1 x2 + 2 x1 e−x2 − 1
J(x) =
1 − x2 e−x2
1 − x1 −x1 e−x2
0 = , 0 x(1) = x(0) − [J(x(0) )]−1 F(x(0) ) −1 0 1 1 2 = − 0 1 0 −1 0 0 1 2 = − 0 1 −1 −1 0 1 = + 0 −3 1 = −3
x(2) = x(1) − [J(x(1) )]−1 F(x(1) ) −1 1 4 0 3 = − −3 20.086 −20.086 19.086 1 0.25 0 3 = − −3 0.25 −0.05 19.086 1 0.75 = − −3 −0.2 0.25 = −2.8
x(3) = x(2) − [J(x(2) )]−1 F(x(2) ) −1 0.25 3.8 0.75 0.15 = − −2.8 16.441 −4.11 3.11 0.25 0.147 0.027 0.15 = − −2.8 0.588 −0.136 3.11 0.25 0.105 = − −2.8 −0.335 0.145 = −2.465
8
