repository.usd.ac.idrepository.usd.ac.id/27004/2/033114007_full.pdf · ketika pagi tiba bila aku...
TRANSCRIPT
PENYELESAIAN SISTEM PERSAMAAN NON-LINEAR DENGAN
METODE NEWTON DAN TERAPANNYA
Skripsi
Diajukan untuk Memenuhi Salah
Satu Syarat Memperoleh Gelar Sarjana Sains
Program Studi Matematika
Disusun Oleh :
Maria Nirmala Anggi Fitra Murti Martosudjito
NIM : 033114007
PROGRAM STUDI MATEMATIKA
JURUSAN MATEMATIKA
FAKULTAS SAINS DAN TEKNOLOGI
UNIVERSITAS SANATA DHARMA
YOGYAKARTA
2007
SOLUTION OF NON-LINEAR SYSTEM OF EQUATIONS WITH
NEWTON’S METHOD AND ITS APPLICATION
Thesis
Presented As Partial Fulfillment of The Requirement
To Obtain The Sarjana Sains Degree in Mathematics
By :
Maria Nirmala Anggi Fitra Murti Martosudjito
Student Number : 033114007
STUDY PROGRAM OF MATHEMATICS SCIENCE
DEPARTEMENT OF MATHEMATICS
FACULTY OF SCIENCE AND TECHNOLOGY
SANATA DHARMA UNIVERSITY
JOGJAKARTA
2007
PERNYATAAN KEASLIAN KARYA
Saya menyatakan dengan sesungguhnya bahwa skripsi yang saya tulis ini
tidak memuat karya atau bagian karya orang lain, kecuali yang telah disebutkan
dalam kutipan atau daftar pustaka, sebagaimana layaknya karya ilmiah.
Yogyakarta, Desember 2007
Penulis,
Maria Nirmala Anggi Fitra Murti Martosudjito
iv
Ketika Pagi Tiba Bila aku susah tidur, dan kemudian terbangun .... Lalu kurasa BERAT dan KELABU semuanya, maka teringatlah aku, KEGELAPAN adalah juga bagian dari kehidupan ... Bila malam kulewatkan,
dengan penuh KEGELISAHAN, dan aku sadar ... betapa hidupku penuh dengan ^ BEBAN ^ ... Lalu sambil merasa ibu bumi masih menyanggaku ... Aku menghela Nafas ... Maka aku pun merasa pula, diriku ditopang oleh segala perasaanku,
... GEMBIRA maupun SUSAH ... Bila tidurku lewat, dalam mimpi menyesakkan ... dan aku harus berhadapan dengan masalah yang belum ku selesaikan, yang ingin KU LUPAKAN ... Lalu aku sadar ... TERANG ataupun GELAP, Harus ku terima semuanya ... Maka ketika pagi tiba,
teristimewa hari ini ... Aku pun akan menemui diriku “APA ADANYA” dengan penuh PERHATIAN dan CINTA ... dan akan menerima ^ Keterbatasanku ^ ...
Aku pun akan mengajak sesamaku, mengalami apa sesungguhnya MANUSIA itu ...
Ia tertawa dan menangis, Ia mencari dan menemukan, Ia ragu-ragu dan percaya ...
Segala sesuatu indah pada waktunya. (Pengkotbah 3:11)
Tuhan itu adalah kekuatan dan mazmurku.
Ia telah menjadi keselamatanku (Mzm 118:14)
In times of difficulties don’t ever say “God I have a big problem” but instead “Hey problem, I have a big God” and everything will be alright.
Tugas di hadapan kita tidak akan pernah sebesar kekuatan di belakang kita
Bila selama ini aku masih bertahan ...
Semua ini aku persembahkan hanya karena cintaku untuk :
Tuhan Yesus dan Bunda Maria, Teman dan Bunda tersayang yang dengan setia mendengarkan
semua kepedihan hatiku
Bapak-Ibuku tercinta.... Aku memang bukan ysng terbaik, tapi ketahuilah bahwa kalianlah
motivasi hidupku .....
Adik-adikku tersayang... Bram dan Christi... Jangan pernah berhenti meraih prestasi .....
Do the best that you can do, not for me or our parents but for your life ....
Keluarga Besar Martosudjito dan Keluarga Besar Sudarsono.... Aku bangga
menjadi bagian dari keluarga ini ....
Seseorang yang sudah hadir dan mewarnai hidupku..... Di atas semua yang pernah
terjadi di antara kita, baik ataupun buruk, you must know that I’m so glad to have you ....
Sahabat-sahabatku ... Aku akan selalu ada untuk kalian... FRIENDS FOREVER ...
Almamaterku ....
ABSTRAK
Sistem persamaan non-linear adalah himpunan m persamaan non-linear dengan yang dapat dinotasikan dengan 1m > ( ) =F x 0 . Sistem persamaan non-linear dapat diselesaikan dengan metode numeris, antara lain dengan metode Newton dan metode Turun Tercuram. Metode Newton adalah suatu algoritma iterasi fungsional yang membangkitkan dengan dan adalah matriks Jacobian. Apabila nilai awal yang dipilih cukup baik maka iterasi Newton akan konvergen dengan sifat q-kuadratik.
( ) ( 1) ( 1) 1 ( 1)( ) (k k k k− − −= −x x J x F x )−
) )
1k ≥ ( )J x
Metode Turun Tercuram merupakan metode optimasi yang akan digunakan untuk mengatasi kelemahan metode Newton. Penyelesaian yang diberikan adalah
dengan , dan adalah
gradien dari . Dalam mencapai konvergensinya, metode Turun Tercuram akan memiliki arah gerak yang zigzag atau vektor-vektor penyelesaiannya akan ortogonal.
(( ) ( 1) ( 1) ( 1)k k k kgλ− − −= − ∇x x x 1k ≥ ( 2
1( ) ( )
n
ii
g f=
= ∑x x ( )g∇ x
( )g x
Metode Newton dan metode Turun Tercuram dapat diaplikasikan dalam bidang fisika, khususnya dalam menghitung konsentrasi unsur dalam sampel.
vii
ABSTRACT
The system of non-linear equations is defined as a set of m of non-linear equations which can be denoted by ( ) =F x 0 in the condition . System of non-linear equations can be solved with numerical methods, for instance Newton Method and Steepest Descent Method. The Newton Method is a functional iteration procedure generated by in the condition and the Jacobian matrix . If the selected starting value is sufficiently accurate, the Newton’s Method will converge q-quadratic.
1m >
( ) ( 1) ( 1) 1 ( 1)( ) (k k k k− − −= −x x J x F x )−
) )
1k ≥( )J x
The Steepest Descent Method is considered as an optimization method which is employed to overcome the weakness of the Newton Method. The given solution is
in the condition , where and
which is defined as the gradient of . To converge, the Steepest Descent Method will have zigzag motion or the vectors of the solution will be orthogonal each other.
(( ) ( 1) ( 1) ( 1)k k k kgλ− − −= − ∇x x x 1k ≥ ( 2
1( ) ( )
n
ii
g f=
= ∑x x
( )g∇ x ( )g x
The Newton Method and the Steepest Descent Method can be applied to the field of physics, especially to estimate the concentrated subtance that is contained in some sample.
viii
KATA PENGANTAR
Segala puji dan syukur, penulis panjatkan kepada Tuhan Yesus Kristus, sang
Juru Selamat, sehingga karena kasih dan karunia-Nya skripsi ini dapat terselesaikan
tepat waktu.
Dalam penyusunan skripsi ini penulis membutuhkan bantuan dari berbagai
pihak. Oleh karena itu, dengan segala kerendahan hati penulis ingin menyampaikan
ucapan terima kasih kepada :
1. Ibu Lusia Krismiyati Budiasih, S.Si., M.Si., selaku dosen pembimbing dan
Kaprodi Matematika FST-USD yang dengan rendah hati mau meluangkan
banyak waktu luang dan penuh kesabaran telah membimbing selama penyusunan
skripsi ini walaupun penulis sering terlambat bahkan kabur dari jadwal
bimbingan dengan waktu yang cukup lama.
2. Bapak Sadmoko dan Ibu Darni, untuk semua pelajaran hidup, cinta, kasih sayang,
pengorbanan, doa, motivasi dan kepercayaan yang sangat berarti.
3. Bapak Y.G. Hartono, S.Si., M.Sc., yang telah bersedia menjadi dosen penguji
dan untuk semua bahan serta chatting sampai tengah malam.
4. Ibu M.V. Any Herawati, S.Si., M.Si., selaku dosen penguji yang telah
memberikan nilai yang cukup mengejutkan.
5. Ir. Greg. Heliarko, S.J., S.S., B.S.T., M.Sc., M.A., selaku Dekan FST-USD.
6. Segenap dosen, karyawan sekretariat FST khususnya Bapak Tukija dan Ibu Linda
dan karyawan Perpustakaan Paingan dan Mrican, atas ide, pelayanan dan
kesempatan kerja yang pernah diberikan.
ix
7. Adik-adikku, Bram dan Christian, yang selalu membuatku kesal tapi sangat aku
sayangi. Jangan pernah menyerah dan raihlah hasil yang lebih baik dariku.
8. Keluarga Besar Martosudjito dan R.Sudarsono, yang selalu mendoakan penulis.
9. Herry ‘Pokilz’, yang telah memberikan semangat, kerjaan dan teman tengah
malamku yang mau nemenin aku belajar serta curhat lewat rutinitas freetalk kita.
10. Sahabat terbaikku di Matematika’03, Eko, Ridwan ‘Djembat’, Kamto ‘Kambing’,
Koko ‘BruCab’, si putri solo Dewi ‘Cemplux’, si lemot Mekar ‘Kuncup’, si
pembuat heboh tapi multitalenta Anin ‘Berukwati’, si panik room Merry, si
perkasa Septi ‘Gondeswati’, si feminim dan teman senasib seperjuangan Valent,
anak kesasar angkatan Cicil dan si invisible Itha. Terimakasih untuk pelukan,
pinjaman bahu untuk menangis dan sandaran hati serta kebersamaan kita selama
ini. Tidak akan pernah ku lupakan semua waktu yang pernah kita lewati bersama.
11. Sahabat dan saudaraku, Nela, Teaka ‘si Kecil’ miss Berantakan yang selalu panik,
Uchie ‘my twin’ yang selalu memberikan bantuan dalam segala hal. Kalian selalu
ada untukku bahkan di saat paling kelam hidupku.
12. Sahabat-sahabatku, Shindy, yang dari kecil selalu menemani aku, Juna, si cuek
yang paling bisa aku ajak bicara dan buat aku tertawa, Ivan ‘Boy’, yang selalu
ada kalau aku butuh bantuannya, Sugriwo club, Ikoq ‘Sublek’, Lusi, Agnes
‘Supat’, yang selalu menyemangatiku. Teristimewa untuk Resti ‘adek dan juga
sahabatku’, yang selalu dengan setia dan sabar mendengarkan ceritaku. Banyak
kisah kebersamaan kita yang tak mungkin dapat ku lupakan dan kamu mengajari
aku banyak hal. Terimakasih karena kamu selalu mendukung aku walaupun aku
tahu bahwa kamu juga cukup sulit. Maaf, aku pernah membuatmu kecewa.
x
13. Teman-temen kostku, crew Palm, Triana ‘Babay’, Esti ‘Ndhoel’, Nana, Wening,
Adel, Puput, oma Vero, nenek Lusi, mami Ika, mbak Naning serta bapak-ibu
Petrus. Crew Muria, Lisa, k.Hetty, k.Titin, Riris, de’Lusi, Rere, Lita, Grace, sizta
Hermin, si kembar Rosa-Rosi, Ana, Ribut, Novi, Linda, Nancy, Rinus, Paul dan
mbak Niken. Terimakasih atas kebersamaan kita selama ini.
14. Teman-teman selama mengabdi bersama baik di fakultas maupun universitas,
crew DEMA 2004 dan DEMA 2005 yang kompak, kakak dan adik angkatan
Matematika, Ikom dan Fisika, dan semua kepanitian yang pernah ku ikuti.
15. Carloku tersayang yang dengan setia menemaniku kemanapun aku pergi.
16. Dyan Avando Michael Mendroza Sembiring Meliala, yang mengajariku banyak
hal tentang cinta, kesabaran dan pengurbanan bahkan sudah mengisi hidupku
dengan penuh warna.
17. Semua pihak yang telah membantu yang tidak dapat disebutkan satu persatu.
Tak ada gading yang tak retak, penulis menyadari kekurangan dalam skripsi
ini, untuk itu saran serta kritik sangat diharapkan dalam peningkatan kualitas skripsi
ini, dan akhirnya penulis berharap semoga skripsi ini dapat bermanfaat bagi semua
pihak.
Yogyakarta, Desember 2007
Penulis,
Maria Nirmala Anggi Fitra Murti Martosudjito
xi
DAFTAR ISI
Halaman
HALAMAN JUDUL ..................................................................................... i
HALAMAN PERSETUJUAN PEMBIMBING ........................................... ii
HALAMAN PENGESAHAN ....................................................................... iii
PERNYATAAN KEASLIAN KARYA ........................................................ iv
HALAMAN PERSEMBAHAN .................................................................... v
ABSTRAK .................................................................................................... vii
ABSTRACT .................................................................................................. viii
KATA PENGANTAR ................................................................................... ix
DAFTAR ISI .................................................................................................. xii
DAFTAR GAMBAR ..................................................................................... xv
DAFTAR TABEL .......................................................................................... xvi
BAB I PENDAHULUAN .............................................................................. 1
A. Latar Belakang Masalah .................................................................... 1
B. Perumusan Masalah ........................................................................... 3
C. Batasan Masalah ................................................................................ 4
D. Tujuan Penulisan ............................................................................... 4
E. Metode Penulisan ............................................................................... 4
F. Manfaat Penelitian ............................................................................. 4
G. Sistematika Penulisan ........................................................................ 5
xii
BAB II KONSEP DASAR DAN PERSAMAAN NON-LINEAR ............... 7
A. Ruang Vektor dan Matriks ................................................................. 7
B. Konvergensi ....................................................................................... 14
C. Penyelesaian Persamaan Non-Linear dengan Iterasi Titik Tetap ...... 22
D. Penyelesaian Persamaan Non-Linear dengan Metode Newton-
Raphson ............................................................................................. 27
E. Optimasi Fungsi menggunakan Quadratic Fit Line Seach ................ 30
BAB III PENYELESAIAN SISTEM PERSAMAAN NON-LINEAR ........ 34
A. Sistem Persamaan Non-Linear .......................................................... 34
B. Konsep Dasar dan Iterasi Titik Tetap ................................................ 36
C. Metode Newton ................................................................................. 41
D. Konvergensi Metode Newton ............................................................ 62
E. Metode Turun Tercuram .................................................................... 67
F. Konvergensi Metode Turun Tercuram ............................................... 85
BAB IV TERAPAN METODE NEWTON DAN METODE TURUN
TERCURAM DALAM MENGHITUNG KONSENTRASI
UNSUR DALAM SUATU SAMPEL ............................................ 95
A. Metode Penyerapan Cahaya ............................................................... 95
B. Terapan Metode Newton dan Metode Turun Tercuram untuk
Menghitung Konsentrasi Unsur ......................................................... 97
C. Analisis Perhitungan Konsentrasi Unsur dengan Metode Newton
dan Metode Turun Tercuram ............................................................. 101
xiii
1. Analisis Sifat Konvergensi pada Hasil .................................. 101
a. Metode Newton ...................................................... 102
b. Metode Turun Tercuram ......................................... 103
2. Pengaruh Nilai Awal terhadap Hasil ..................................... 105
3. Pengaruh Pendekatan Fungsi terhadap Hasil ........................ 109
a. Metode Newton ...................................................... 110
b. Metode Turun Tercuram ......................................... 110
4. Perbandingan Nilai Absorban Hasil Pengukuran dengan
Hasil Perhitungan ................................................................... 111
5. Konsentrasi Parasetamol dan Kafein yang memenuhi ........... 113
BAB V PENUTUP ........................................................................................ 114
A. Kesimpulan ........................................................................................ 114
B. Saran .................................................................................................. 116
DAFTAR PUSTAKA .................................................................................... 117
LAMPIRAN .................................................................................................. 119
xiv
DAFTAR GAMBAR
Halaman
Gambar 2.2.1 ............................................................................................. .... 17
Gambar 2.2.2 ................................................................................................. 18
Gambar 2.5.1 ................................................................................................. 31
Gambar 2.5.2 ................................................................................................. 31
Gambar 2.5.3 ................................................................................................. 32
Gambar 3.3.1 ................................................................................................. 55
Gambar 3.5.1 ................................................................................................ 71
Gambar 3.5.2 ................................................................................................ 78
Gambar 3.6.1 ................................................................................................. 89
xv
DAFTAR TABEL
Halaman
Tabel 3.3.1 ..................................................................................................... 60
Tabel 3.4.1 ..................................................................................................... 66
Tabel 3.4.2 ..................................................................................................... 67
Tabel 3.5.1 ..................................................................................................... 82
Tabel 3.5.2 ..................................................................................................... 83
Tabel 3.6.1 ..................................................................................................... 91
Tabel 3.6.2 ..................................................................................................... 92
Tabel 3.6.3 ..................................................................................................... 93
Tabel 4.2.1 ..................................................................................................... 98
Tabel 4.2.2 ..................................................................................................... 98
Tabel 4.2.3 ..................................................................................................... 99
Tabel 4.2.4 ..................................................................................................... 100
Tabel 4.2.5 ..................................................................................................... 101
Tabel 4.3.1 ..................................................................................................... 102
Tabel 4.3.2 ..................................................................................................... 103
Tabel 4.3.3 ..................................................................................................... 104
Tabel 4.3.4 ..................................................................................................... 106
Tabel 4.3.5 ..................................................................................................... 107
Tabel 4.3.6 ..................................................................................................... 112
Tabel 4.3.7 ..................................................................................................... 112
xvi
BAB I
PENDAHULUAN
A. Latar Belakang Masalah
Dalam berbagai bidang ilmu pengetahuan sering muncul persoalan yang
melibatkan model matematika. Sering kali model matematika yang muncul bukanlah
suatu model yang biasa, melainkan suatu model yang rumit bahkan sulit untuk dicari
penyelesaiannya. Model matematika ini bisa berupa suatu persamaan atau suatu
sistem persamaan. Persamaan bisa dibagi menjadi persamaan linear dan persamaan
non-linear. Sistem persamaan juga bisa dibagi menjadi sistem persamaan linear dan
sistem persamaan non-linear.
Persamaan linear dengan n variabel bebas 1 2, , , nx x x… adalah persamaan
yang berbentuk 1 1 2 2 n ny a x a x a x= + + +… . Sedangkan persamaan non-linear
merupakan negasi dari persamaan linear. Persamaan non-linear sendiri dibagi
menjadi persamaan non-linear satu variabel dan persamaan non-linear dengan n
variabel, dengan . Bentuk umum persamaan non-linear dengan satu variabel
adalah dengan
1>n
0)( =xf ( )f x adalah fungsi non-linear. Sedangkan bentuk umum
persamaan non-linear dengan n variabel adalah dengan 0),,,( 21 =nxxxf …
1 2( , , , )nf x x x… adalah fungsi non-linear.
Sistem persamaan linear adalah himpunan n persamaan linear, dengan .
Penyelesaian sistem persamaan linear dapat dicari dengan beberapa metode yang
sederhana, yaitu seperti metode subsitusi, metode eliminasi dan metode campuran.
1>n
2
Sistem persamaaan non-linear adalah himpunan n persamaan non-linear,
dengan . Sistem persamaan non-linear secara umum berbentuk: 1>n
0),,,(
0),,,(0),,,(
21
212
211
=
==
nn
n
n
xxxf
xxxfxxxf
…
……
di mana tiap fungsi merupakan pemetaan vektor dari ke
. Sistem ini dapat ditulis dalam bentuk lain dengan mendefinisikan fungsi F, yang
memetakan ke .
ift
nxxx ),,,( 21 …=x n
n n
tnnnnn xxxfxxxfxxxfxxx )),,,(,,),,,(,),,,((),,,( 2121221121 …………… =F
Dengan menggunakan notasi vektor, sistem di atas dapat diasumsikan dengan bentuk
F(x) = 0
Secara umum, ada dua metode penyelesaian suatu sistem persamaan yaitu
metode analitis dan metode numeris. Metode analitis adalah metode penyelesaian
model matematika dengan rumus-rumus aljabar yang sudah baku (lazim). Metode
numeris adalah teknik yang digunakan untuk memformulasikan persoalan
matematika dengan data numerik.
Sistem persamaan non-linear tidak mudah diselesaikan dengan metode
analitis dalam mendapatkan penyelesaian exact (exact solution) karena sistem terlalu
rumit tidak seperti sistem persamaan linear biasa. Selain itu, sistem ini mempunyai
masalah yang melibatkan banyak persamaan non-linear dan banyak variabel. Alasan
yang demikian menyebabkan sistem persamaan non-linear pada umumnya
diselesaikan dengan metode numeris.
3
Sistem persamaan non-linear dapat diselesaikan dengan beberapa metode
numeris, salah satunya adalah metode Newton. Metode Newton merupakan
perkembangan dari iterasi Titik-Tetap (Fixed-Point) dan metode Newton-Raphson
dalam menyelesaikan persamaan non-linear. Langkah awal penyelesaian persamaan
non-linear dengan metode Newton-Raphson adalah mencari turunan fungsinya.
Tidak jauh berbeda dengan metode Newton-Raphson, langkah awal penyelesaian
sistem persamaan non-linear dengan metode Newton adalah mencari turunan parsial
semua fungsinya terhadap setiap variabel yang ada dalam sistem tersebut. Semua
turunan parsial dalam sistem dibentuk menjadi suatu matriks yang dinamakan
matriks Jacobian.
Metode Newton merupakan metode yang paling mudah dan paling sering
digunakan akan tetapi mempunyai kelemahan yaitu konvergensinya akan sangat sulit
dicapai apabila pendekatan awal tidak baik, artinya terlalu jauh dari nilai yang
sebenarnya. Sebagai akibatnya, muncullah suatu metode yang dinamakan Metode
Turun Tercuram (Steepest Descent Method). Metode ini dapat mengatasi kelemahan
yang muncul pada Metode Newton, maksudnya pendekatan awal apapun yang dipilih
akan menyebabkan konvergensinya menjadi lebih cepat.
B. Perumusan Masalah
Berdasarkan uraian yang dikemukakan dalam latar belakang, pokok
permasalahan dalam skripsi ini dapat dirumuskan sebagai berikut :
a. Bagaimana mencari penyelesaian sistem persamaan non-linear dengan metode
Newton?
4
b. Bagaimana mencari penyelesaian sistem persamaan non-linear dengan metode
Turun Tercuram?
c. Bagaimana terapan penyelesaian sistem persamaan non-linear di bidang fisika,
khususnya dalam masalah menghitung konsentrasi unsur dalam sampel?
C. Batasan Masalah
1. Sistem persamaan non-linear terdiri dari n persamaan dan n variabel.
2. Bahasa pemrograman yang digunakan untuk menyelesaikan sistem persamaan
non-linear adalah Matlab.
D. Tujuan Penulisan
Tujuan penulisan skripsi ini adalah untuk menyelesaikan sistem persamaan
non-linear dengan metode Newton dan metode Turun Tercuram untuk mempercepat
konvergensinya serta terapannya dalam bidang fisika khususnya dalam masalah
menghitung konsentrasi unsur dalam sampel.
E. Metode Penulisan
Metode penulisan skripsi ini adalah dengan menggunakan metode studi
pustaka dan analisis data.
F. Manfaat Penulisan
Manfaat penulisan skripsi ini adalah mengetahui cara penyelesaian dari
sistem persamaan non-linear dengan metode Newton dan metode Turun Tercuram
5
serta terapannya dalam bidang fisika, khususnya dalam masalah menghitung
konsentrasi unsur dalam sampel.
G. Sistematika Penulisan
BAB I : PENDAHULUAN
Dalam bab I akan dibahas tentang latar belakang, perumusan masalah,
batasan masalah, tujuan penulisan, metode penulisan, manfaat
penulisan, dan sistematika penulisan.
BAB II : KONVERGENSI DAN PERSAMAAN NON-LINEAR
Dalam bab II akan dibahas konsep ruang vektor dan matriks,
konvergensi, penyelesaian persamaan non-linear dengan iterasi Titik
Tetap, penyelesaian persamaan non-linear dengan metode Newton-
Raphson serta optimasi fungsi dengan Quadratic Fit Line Search.
BAB III : PENYELESAIAN SISTEM PERSAMAAN NON-LINEAR
Dalam bab III akan dibahas tentang sistem persamaan non-linear,
konsep dasar dan iterasi Titik Tetap, metode Newton, konvergensi
metode Newton, metode Turun Tercuram serta konvergensi metode
Turun Tercuram. Pengimplementasian penyelesaian sistem persamaan
non-linear dengan metode Newton dan metode Turun Tercuram
dengan menggunakan bahasa pemrograman Matlab.
6
BAB IV : TERAPAN METODE NEWTON DAN METODE TURUN
TERCURAM DALAM MENGHITUNG KONSENTRASI
UNSUR DALAM SUATU SAMPEL
Dalam bab IV akan dibahas tentang metode penyerapan cahaya,
terapan metode Newton dan metode Turun Tercuram untuk
menghitung konsentrasi unsur serta analisis penghitungan konsentrasi
unsur dengan metode Newton dan metode Turun Tercuram
BAB V : PENUTUP
Dalam bab V akan dibahas tentang kesimpulan dan saran.
BAB II
KONSEP DASAR DAN PERSAMAAN NON-LINEAR
Dalam bab ini akan dibahas konsep ruang vektor dan matriks, konvergensi,
penyelesaian persamaan non-linear dengan iterasi Titik-Tetap dan metode Newton-
Raphson serta optimasi fungsi dengan Quadratic Fit Line Search yang nantinya akan
digunakan untuk memahami metode Newton dan metode Turun Tercuram serta
konvergensinya.
A. Ruang Vektor dan Matriks
Definisi 2.1.1
Misalkan V adalah himpunan di mana didefinisikan operasi-operasi penjumlahan dan
perkalian dengan skalar. Penjumlahan adalah kaidah untuk mengasosiasikan setiap
pasang elemen u dan v di dalam V dengan sebuah elemen +u v , yang dinamakan
jumlah (sum). Perkalian skalar adalah sebuah kaidah untuk mengasosiakan setiap
skalar k dan setiap elemen u di dalam V dengan sebuah elemen ku, yang dinamakan
kelipatan skalar (scalar multiple). Jika aksioma-aksioma berikut dipenuhi oleh
semua elemen u, v, dan w di dalam V dan oleh semua skalar k dan l, maka V
dinamakan ruang vektor dan elemen-elemen di dalam V dinamakan vektor.
(1) Jika u dan v adalah elemen-elemen di dalam V, maka +u v berada di dalam V.
(2) + = +u v v u
(3) ( ) ( )+ + = + +u v w u v w
8
(4) Ada sebuah elemen 0 di dalam V sehingga + = + =0 u u 0 u untuk semua u di
dalam V.
(5) Untuk setiap u di dalam V, ada sebuah elemen –u di dalam V yang dinamakan
negatif dari u sehingga ( ) ( )+ − = − + =u u u u 0
k
u
.
(6) Jika k adalah sebarang bilangan real dan u adalah sebarang elemen di dalam V,
maka ku berada di dalam V.
(7) ( )k k+ = +u v u v
(8) ( )k l k l+ = +u u
(9) ( ) ( )k l kl=u u
(10) 1 =u u
Vektor 0 di dalam Aksioma 4 dinamakan vektor nol (zero vector) untuk V.
Definisi 2.1.2
Hasil kali dalam pada ruang vektor V adalah pemetaan dari V V× ke , dimana V
setiap pasang vektor-vektor u dan v di dalam V dipetakan ke sebuah bilangan real
n
,u v yang memenuhi syarat berikut:
(1) , ≥u u 0 Nonnegatif
(2) , =u u 0 jika dan hanya jika 0=u Positif
(3) , , ,+ = +u v w u w v w Penjumlahan
(4) ,α α=u v u v, untuk semua skalar α Homogenitas
Sebuah ruang vektor V dengan hasil kali dalam disebut ruang hasil kali dalam.
9
Definisi 2.1.3
Hasil kali dalam baku untuk adalah hasil kali skalar n
, T=x y x y
Definisi 2.1.4
Sebuah ruang vektor V dikatakan ruang linear bernorma (normed linear space)
jika untuk setiap vektor V∈v dikaitkan dengan sebuah bilangan real v yang
disebut norma dari v yang memenuhi :
(1) 0≥v Nonnegatif
(2) 0=v jika dan hanya jika 0=v Positif
(3) α α=v v untuk semua skalar α Homogenitas
(4) + ≤ +v w v w Ketaksamaan segitiga
Teorema 2.1.5 (Pertidaksamaan Cauchy-Schwarz)
Jika u dan v adalah vektor-vektor di dalam sebuah ruang hasil kali dalam V, maka
, ≤ ⋅u v u v
Bukti :
Bukti teorema 2.1.5 bisa dilihat pada buku karangan Leon, Steven J. (2001). Aljabar
Linear dan Aplikasinya (Terjemahan). Edisi kelima. Jakarta : Penerbit Erlangga.
10
Teorema 2.1.6
Jika V adalah sebuah ruang hasil kali dalam, maka persamaan
,=v v v untuk semua V∈v
Bukti :
Bukti teorema 2.1.6 bisa dilihat pada buku karangan Leon, Steven J. (2001). Aljabar
Linear dan Aplikasinya (Terjemahan). Edisi kelima. Jakarta : Penerbit Erlangga.
Beberapa contoh norma sebuah vektor
1. Norma Euclidean (Euclidean norm atau norm) dalam 2ln
( )1
122 2 2 22
1 221
,n
n ii
x x x x=
⎛ ⎞= + + + = =⎜ ⎟
⎝ ⎠∑x x… x
i sering disebut juga sebagai panjang vektor.
2. Norma jumlah (norm sum atau norm) dalam 1ln
1 211
n
n ii
x x x=
= + + + = x∑x …
3. Norma maksimum (max norm atau l∞ norm) dalam n
{ }1 2 1max , , , maxn ii n
x x x∞ ≤ ≤= =x … x
4. Norma ( norm) dalam pl pl n
1
1
n ppip
ix
=
⎛ ⎞= ⎜ ⎟⎝ ⎠∑x
untuk setiap bilangan real . 1≥p
11
Untuk selanjutnya norma yang akan digunakan dalam adalah norma Euclidean
kecuali ada ketentuan khusus dan akan ditulis dengan notasi
n
i .
Definisi 2.1.7
Misalkan adalah vektor-vektor di dalam sebuah ruang hasil kali dalam
V. Jika
1 2, , , nv v v…
,i j =v v 0 j bilamana i ≠ , maka { }1 2, , , nv v v… dikatakan sebagai sebuah
himpunan ortogonal dari vektor-vektor.
Definisi 2.1.8
Sebuah himpunan ortonormal dari vektor-vektor adalah sebuah himpunan
ortogonal dari vektor-vektor satuan dengan vektor satuan adalah vektor yang
panjangnya satu.
Himpunan { }1 2, , , nu u u… akan menjadi ortonormal jika dan hanya jika
,i j ijδ=u u
di mana
1 jika 0 jika ij
i ji j
δ=⎧
= ⎨ ≠⎩
12
Definisi 2.1.9
Sebuah matriks A yang berorde n n× dikatakan nonsingular jika ada sebuah matriks
yang berorde dengan 1−A n n× 1 1− −= =AA A A I . Matriks 1−A dinamakan invers
matriks A. Sebuah matriks yang tidak mempunyai invers disebut matriks singular.
Definisi 2.1.10
Sebuah matriks Q yang berorde n n× dikatakan sebagai matriks ortogonal jika
vektor-vektor kolom dari Q membentuk sebuah himpunan ortonormal di dalam . n
Teorema 2.1.11
Sebuah matriks Q yang berorde n n× adalah ortogonal jika dan hanya jika T =Q Q I
Bukti :
Berdasarkan definisi, sebuah matriks Q yang berorde n n× adalah ortogonal jika dan
hanya jika vektor kolom-kolomnya memenuhi
Ti j ijδ=q q
Tetapi adalah entri dari . Jadi Q adalah ortogonal jika dan hanya
jika .
Tiq q j )( ,i j TQ Q
T =Q Q I
■
13
Definisi 2.1.12
Misalkan adalah himpunan semua matriks berukuran nnM n× . Sebuah fungsi
: n →Mi dikatakan suatu norma matriks jika untuk setiap akan
memenuhi kelima aksioma di bawah ini:
, n∈A B M
(1) 0≥A Nonnegatif
(1a) 0=A jika dan hanya jika 0=A Positif
(2) c c=A A untuk semua skalar c Homogenitas
(3) + ≤ +A B A B Ketaksamaan segitiga
(4) ≤AB A B Submultiplikatif
Beberapa contoh norma matriks
1. Norma untuk yang didefinisikan dengan 1l n∈A M
1, 1
n
iji j
a=
= ∑A
2. Norma Euclidean atau norma untuk 2l n∈A M yang didefinisikan dengan
122
2, 1
n
iji j
a=
⎛ ⎞= ⎜ ⎟⎝ ⎠∑A
3. Norma untuk yang didefinisikan dengan l∞ n∈A M
1 ,max iji j n
a∞ ≤ ≤=A
14
Untuk selanjutnya norma yang akan digunakan dalam adalah norma Euclidean
kecuali ada ketentuan khusus dan akan ditulis dengan notasi
nM
i .
B. Konvergensi
Barisan bilangan real adalah suatu fungsi dari ke dalam . Jadi, fungsi
atau :f → ( )f n dengan n∈ adalah barisan bilangan real. Biasanya ( )f n
dinyatakan dengan . Barisan dengan sebagai suku ke-n akan ditulis ns ns ns atau
{ }ns .
Definisi 2.2.1
Misalkan f adalah fungsi yang terdefinisi di dalam himpunan bilangan real X; f
dikatakan mempunyai limit L di 0x , dan ditulis 0
lim ( )x x
f x L→
= , jika diberikan sebuah
bilangan 0ε > , maka ada sebuah 0δ > sedemikian sehingga ( )f x L ε− < bila
x X∈ dan 00 x x δ< − < .
Definisi 2.2.2
Misalkan f adalah fungsi yang terdefinisi di dalam himpunan bilangan real X dan
0x X∈ ; f dikatakan kontinu di 0x jika 0
0lim ( ) ( )x x
f x f x→
= . Fungsi f dikatakan kontinu
pada X jika f kontinu pada setiap titik di X.
15
Definisi 2.2.3
Barisan { }ns dikatakan konvergen jika terdapat s∈ dengan sifat, untuk sebarang
0ε > yang diberikan, terdapat N ∈ sehingga untuk semua dengan
berlaku
n∈ n ≥
ns s ε− < . Bilangan s dinamakan limit { }ns untuk dan ditulis
atau disingkat
n →∞
lim nns
→∞= s slim ns = . Suatu barisan yang tidak mempunyai limit
disebut divergen.
Definisi 2.2.4 (Deret Taylor)
Jika f terdiferensial pada semua tingkat di x b= maka dapat didefinisikan deret
Taylor untuk f di sekitar x b= adalah
( )2 3''( ) '''( ) ( )( ) ( ) '( )( ) ( ) ( ) ( )
2! 3! !
nnf b f b f bf x f b f b x b x b x b x b
n= + − + − + − + + − +… …
Teorema 2.2.5 (Teorema Rolle)
Misalkan [ ],f C a b∈ dan f terdiferensial dalam interval ( Jika
, maka ada paling sedikit satu bilangan c pada sedemikian
sehingga berlaku .
)
)
,a b
( ) ( ) 0f a f b= = ( ,a b
'( ) 0f c =
Bukti :
Karena ( )f x kontinu dalam a x b≤ ≤ berarti ( )f x mempunyai nilai maksimum M
dan nilai minimum m dalam [ ],a b , jadi ( )m f x M≤ ≤ dalam [ ],a b .
Bila maka m M= ( )f x =konstan, berarti '( ) 0f x = .
16
Karena dan m M< ( ) ( )f a f b= , maka paling sedikit salah satu dari m atau M tidak
sama dengan ( ) ( )f a f b= , misalnya ( )M f a≠ . Maka nilai maksimum M tidak pada
titik akhir dari ( , melainkan terletak di ),a b x c= , ( )a c b< < dan berarti '( ) 0f c = .
■
Teorema 2.2.6 (Teorema Nilai Rata-Rata)
Jika [ ],f C a b∈ dan terdifferensial dalam interval ( ),a b , maka paling sedikit ada
satu nilai c antara a dan b sedemikian hingga berlaku
( ) ( ) '( )f b f a f cb a−
=−
(2.2.1)
Bukti :
Gambar grafik f sebagai kurva pada bidang dan gambar sebuah garis lurus dari titik
( ), ( )A a f a dan ( ), ( )B b f b (lihat Gambar 2.2.1 ) maka fungsinya
( ) ( )( ) ( ) ( )f b f ag x f a x ab a−
= + −−
(2.2.2)
Selisih antara grafik f dan g pada x adalah
( ) ( )( ) ( ) ( ) ( ) ( ) ( )f b f ah x f x g x f x f a x ab a−
= − = − − −−
(2.2.3)
Dari persamaan (2.2.3) maka ( ) ( ) 0h a h b= = . Oleh karena fungsi-fungsi ( )f x dan
( )x a− adalah kontinu dalam a x b≤ ≤ dan terdiferensial dalam , maka
menurut teorema 2.2.5, ada (paling sedikit) nilai x yang turunannya = 0 dan misalkan
untuk
a x b< <
x c= , berlaku a c b< < '( ) 0h c = .
17
Gambar 2.2.1
Dari persamaan (2.2.3) diperoleh
( ) ( )'( ) '( ) f b f ah x f xb a−
= −−
(2.2.4)
Untuk x c= , maka persamaan (2.2.4) menjadi
( ) ( )'( ) '( ) f b f ah c f cb a−
= −−
( ) ( )0 '( ) f b f af cb a−
= −−
'( ) 0h c =
( ) ( )'( ) f b f af cb a−
=−
■
Teorema 2.2.7 (Teorema Nilai Antara)
Jika [ ],f C a b∈ dan K adalah sebuah bilangan yang berada di antara ( )f a dan
( )f b , maka ada sebuah nilai c di ( ),a b sedemikian sehingga ( )f c K= . (lihat
gambar 2.2.2)
18
Gambar 2.2.2
Bukti :
Dimisalkan ( ) ( )f a f b< dan m dan M berturut-turut nilai minimum dan maksimum
mutlak dari f pada [ . Maka ],a b [ ]( ) [ ], ,f a b m M= karena f kontinu pada [ ],a b .
Jadi . Karena pada ( ) ( )m f a c f b M≤ < < ≤ [ ],a b fungsi f mencapai semua nilai
mulai dari m sampai dengan M, maka pasti terdapat ( ),K a b∈ sehingga ( )f c K= .
■
Teorema 2.2.8 (Teorema Titik Ekstrem)
Andaikan f didefinisikan pada selang I yang memuat titik c. Jika ( )f c adalah nilai
ekstrim, maka c haruslah berupa suatu titik kritis, yakni c berupa salah satu :
(i) titik ujung dari I
(ii) titik stasioner dari f ( )'( ) 0f c = atau
(iii) titik singular dari f ( '( )f c tidak ada)
19
Bukti :
Bukti teorema 2.2.8 bisa dilihat pada buku karangan Varberg, Dale, Purcell, Edwin J.
(2001). Kalkulus (Terjemahan). Edisi Tujuh. Jilid Satu. Jakarta : Interaksara.
Teorema 2.2.9 (Perluasaan Teorema Nilai Rata-Rata yang Pertama ke Rumus
Taylor)
Jika f dan 'f kontinu pada [ ],a b dan 'f diferensial pada ( ),a b , maka ada sebuah
bilangan ξ antara a dan b sedemikian serupa sehingga
2''( )( ) ( ) '( )( ) ( )2!
ff b f a f a b a b aξ= + − + − (2.2.5)
Bukti :
Bukti teorema 2.2.9 bisa dilihat pada buku karangan Thomas, George B., Finney,
Ross L. (1986). Kalkulus dan Geometri Analitik (Terjemahan). Edisi keenam. Jilid I.
Jakarta : Penerbit Erlangga.
Lemma 2.2.10
Jika M adalah matriks yang berukuran n n× dengan 1<M maka adalah
nonsingular dan
−I M
( ) 1 11
−− ≤−
I MM
(2.2.6)
20
Bukti :
Akan ditunjukkan bahwa −I M adalah nonsingular dan pertidaksamaan (2.2.6) akan
diperoleh dengan menunjukkan bahwa deret
1
0( )l
l
∞−
=
= −∑M I M
Jumlah parsial deret tersebut
0
kl
kl=
= ∑S M
yang merupakan bentuk barisan Cauchy di n n× . Dari pernyataan tersebut maka
untuk semua m k>
1
ml
k ml k= +
− ≤ ∑S S M
Kemudian, ll ≤M M karena i adalah norma matriks yang sudah termasuk
norma vektor. Karena itu,
1
1
10
1
m kml k
k ml k
−+
= +
⎛ ⎞−⎜ ⎟− ≤ = →⎜ ⎟−⎝ ⎠
∑M
S S M MM
dengan . Oleh sebab itu, barisan konvergen, ditulis S. Karena
, maka didapatkan
,m k →∞ kS
1k ++ =M S I Sk + =M S I S dan sebab itu . Ini
membuktikan bahwa adalah nonsingular dan
( )− =I M S I
−I M ( ) 1−= −S I M .
Perlu dicatat bahwa
( ) ( ) 11
0
1l
l
∞ −−
=
− ≤ = −∑I M M M
■
21
Definisi 2.2.11
B merupakan pendekatan invers dari A jika 1− <I BA .
Teorema 2.2.11 (Lemma Banach)
Jika A dan B adalah matriks yang berukuran n n× dan B merupakan pendekatan
invers dari A, maka A dan B keduanya adalah nonsingular dan
1
1− ≤
− −B
AI BA
, 1
1− ≤
− −A
BI BA
(2.2.7)
dan
1
1− −− ≤
− −B I BA
A BI BA
, 1
1− −
− ≤− −
A I BAA B
I BA (2.2.8)
Bukti :
Misalkan . Berdasarkan dari Lemma 2.2.9, = −M I B A ( )− = − − =I M I I B A B A
adalah nonsingular. Oleh karena itu, A dan B keduanya adalah nonsingular. Dari
pertidaksamaan (2.2.6)
( ) 11 1 1 11 1
−− − = − ≤ =− − −
A B I MM I BA
1− B
(2.2.9)
Karena , pertidaksamaan (2.2.9) implikasi dengan bagian pertama
dari (2.2.7). Bagian kedua akan didapatkan dengan cara yang sama dari
.
1 ( )− = −A I M
1 1( )− −= −B A I M
Untuk melengkapi bukti ini, perlu dicatat bahwa
22
1 1( )− −− = −A B I B A A , 1 1( )− −− = −A B B I B A
dan yang akan menggunakan pertidaksamaan (2.2.7). ■
C. Penyelesaian Persamaan Non-Liner dengan Iterasi Titik-Tetap
Persamaan non-linear persamaan non-linear merupakan negasi dari
persamaan linear. Persamaan non-linear dapat dibedakan menjadi persamaan non-
linear satu variabel dan persamaan non-linear dengan n variabel, dengan .
Bentuk umum persamaan non-linear dengan satu variabel adalah , dengan
1>n
0)( =xf
( )f x adalah fungsi non-linear. Sedangkan bentuk umum persamaan non-linear
dengan n variabel adalah 0),,,( 21 =nxxxf … , dengan 1 2( , , , )nf x x x… adalah
fungsi non-linear.
Contoh 2.3.1 :
• Persamaan non-linear satu variabel
0cos =− xx
• Persamaaan non-linear dengan 3-variabel
06cos22 321 =−++ − xe xx
Titik tetap untuk suatu fungsi g adalah titik p dengan . Masalah
mencari akar persamaan dan masalah titik tetap adalah equivalen. Misalkan :
diberikan masalah mencari akar persamaan
( )g p p=
( ) 0f p = . Akan didefinisikan suatu
fungsi g dengan titik tetap p, yaitu ( ) ( )g x x f x= − . Dengan demikian, jika fungsi g
23
memiliki titik tetap di p maka fungsi yang didefinsikan dengan
memiliki nilai nol di p.
( ) ( )g x x f x= −
Teorema 2.3.1
Jika [ ],g C a b∈ dan [ ]( ) ,g x a b∈ untuk semua [ ],x a b∈ maka g memiliki titik tetap
di . Misalkan, ditambahkan, bahwa ada di [ ,a b] '( )g x ( ),a b dan ada sebuah
konstanta positif dengan 1k <
'( ) 1g x k≤ < , untuk semua ( ),x a b∈ (2.3.1)
Maka titik tetap di [ adalah tunggal. ],a b
Bukti :
Jika atau , titik tetap jelas ada. Misalkan tidak maka pasti akan
benar dengan dan
( )g a a= ( )g b b=
( )g a a> ( )g b b< . Definisikan ( ) ( )h x g x x= − , maka h akan
kontinu dalam [ dan ],a b
( ) ( ) 0h a g a a= − > , ( ) ( ) 0h b g b b= − <
Teorema Nilai Antara berimplikasi dengan ada ( ),p a b∈ sedemikian sehingga
( ) 0h p = . Kemudian, ( ) 0g p p− = dan p adalah titik tetap dari g.
Misalkan, ditambahkan, dari pertidaksamaan (2.3.1) dan bahwa p dan q
keduanya adalah titik tetap di [ ],a b dengan p q≠ . Dari Teorema Nilai Rata-Rata,
ada sebuah ξ antara p dan q , dan di [ ],a b , dengan
24
( ) ( ) ( )'g p g q
gp q
ξ−
=−
Maka
( ) ( ) ( )'p q g p g q g p q k p q p qξ− = − = − ≤ − < −
Kontradiksi. Kontradiksi muncul dari permisalan bahwa p q≠ . Oleh karena itu,
dan titik tetap di [ adalah tunggal. p q= ],a b
■
Untuk mendekati titik tetap fungsi g, akan dipilih suatu pendekatan awal (0)p dan
akan dibangkitkan barisan { }( )
0
n
np
∞
= dengan maka ( ) ( 1)(n np g p −= )
( ) ( )( ) ( 1) ( 1)lim lim lim ( )n n n
n n np p g p g p g− −
→∞ →∞ →∞= = = = p
dan penyelesaian ( )x g x= terpenuhi. Teknik ini disebut Iterasi Titik-Tetap atau
Iterasi Fungsional.
Teorema 2.3.2 (Teorema Titik-Tetap)
Misalkan [ ],g C a b∈ dan ( ) [ ],g x a b∈ untuk semua x di [ . Misalkan,
ditambahkan, bahwa ada ' di
],a b
g [ ],a b dengan
'( ) 1g x k≤ < , untuk semua ( ),x a b∈ (2.3.2)
Jika (0)p adalah nilai di [ , maka barisan yang didefinisikan dengan ],a b
( )( ) ( 1)n np g p −= , 1n ≥
25
konvergen ke suatu titik tetap secara tunggal di [ ],a b .
Bukti :
Berdasarkan Teorema 2.3.1, ada sebuah titik tetap tunggal p di [ . Karena g
merupakan pemetaan [ ke
]
]
,a b
,a b [ ],a b , maka barisan { }( )
0
n
np
∞
= didefinisikan untuk
semua dan 0n ≥ [ ]( ) ,np a b∈ untuk semua n. Dengan menggunakan pertidaksamaan
(2.3.2) dan Teorema Nilai Antara, didapatkan
( ) ( ) ( )( ) ( 1) ( 1) ( 1)'n n n np p g p g p g p p k p pξ− −− = − = − ≤ −−
)
(2.3.3)
dengan . Menggunakan pertidaksamaan tersebut akan memberikan ( ,a bξ ∈
( ) ( 1) 2 ( 2) (0)n n n np p k p p k p p k p− −− ≤ − ≤ − ≤ ≤ −… p (2.3.4)
Karena , 1k <
( ) (0)lim lim 0n n
n np p k p p
→∞ →∞− ≤ − =
dan { }( )
0
n
np
∞
= konvergen ke p.
■
Akibat 2.3.3
Jika g memenuhi hipotesis Teorema 2.3.2, batas untuk kesalahan (error) yang
terlibat dengan menggunakan ( )np untuk mendekati p diberikan sebagai
{ }( ) (0) (0)max ,n np p k p a b p− ≤ − −
dan ( ) (0) (1)
1
nn kp p p
k− ≤ −
−p , untuk semua . 1n ≥
26
Bukti :
Batasan pertama menurut pertidaksamaan (2.3.4) :
{ }( ) (0) (0) (0)max ,n n np p k p p k p a b p− ≤ − ≤ − −
karena [ ],p a b∈ .
Untuk , prosedur akan digunakan untuk bukti Teorema 2.3.2 yang implikasi
dengan
1n ≥
( ) ( )( 1) ( ) ( ) ( 1) ( ) ( 1) (1) (0)n n n n n n np p g p g p k p p k p p+ − −− = − ≤ − ≤ ≤ −…
Kemudian, untuk 1m n> ≥
( ) ( ) ( ) ( 1) ( 1) ( 1) ( )m n m m m np p p p p p p− − +− = − + − + −… n
( ) ( 1) ( 1) ( 2) ( 1) ( )m m m m np p p p p p− − − +≤ − + − + + −… n
1 (1) (0) 2 (1) (0) (1) (0)m m nk p p k p p k p p− −≤ − + − + + −…
( )2 1 (1)1n m nk k k k p p− −= + + + + −… (0)
Berdasarkan Teorema 2.3.2, ( )lim m
mp p
→∞= , sehingga
( ) ( ) ( ) (1) (0)
0
limn m n n
m i
p p p p k p p k∞
→∞=
− = − ≤ − i∑
Karena adalah barisan geometri dengan konstanta rasio k, maka akan
didapatkan batasan yang kedua sebagai berikut:
0
i
i
k∞
=∑
( ) (1) (0)
1
nn kp p p
k− ≤ −
−p
■
27
D. Penyelesaian Persamaan Non-Linear dengan Metode Newton-Raphson
Metode Newton-Raphson merupakan salah satu metode numerik yang
paling kuat dan paling banyak diketahui untuk menyelesaikan masalah mencari akar
persamaan . ( ) 0f x =
Misalkan [ ]2 ,f C a b∈ . Misalkan [ ],x a b∈ akan menjadi pendekatan
untuk p sedemikian sehingga '( ) 0f x ≠ dan x p− adalah “kecil”. Dengan
mempertimbangkan bentuk deret Taylor untuk ( )f x di sekitar x ,
2( )( ) ( ) ( ) '( ) ''( ( ))2
x xf x f x x x f x f xξ−≈ + − +
dengan ( )xξ berada di antara x dan x . Karena ( ) 0f p = dengan x p= , maka
persamaan akan menjadi
2( )0 ( ) ( ) '( ) ''( ( )2
p x )f x p x f x f pξ−≈ + − +
Metode Newton-Raphson diperoleh dari asumsi tersebut, karena p x− kecil, maka
2( p x− ) dapat diabaikan dan akan didapatkan
0 ( ) ( ) '( )f x p x f x≈ + − (2.4.1)
Menyelesaikan p dalam persamaan tersebut diberikan dengan
( )'( )
f xp xf x
≈ −
Persamaan tersebut merupakan bentuk penyelesaian untuk metode Newton-Raphson
dengan pendekatan awal (0)p dan akan membangkitkan barisan { }( )np yang
didefinisikan dengan
28
( 1)
( ) ( 1)( 1)
( )'( )
nn n
n
f pp pf p
−−
−= − , (2.4.2) 1n ≥
Teknik-pemberhentian pada metode Newton-Raphson. Pilih toleransi dengan 0ε >
dan menyusun (1) ( ), , np p… sehingga
( ) ( 1)n np p ε−− < (2.4.3)
( ) ( 1)
( )
n n
n
p p
pε
−−< , ( ) 0np ≠ (2.4.4)
atau
( )( )nf p ε< (2.4.5)
Metode Newton-Raphson adalah teknik iterasi fungsional dengan bentuk
, berlaku ( ) ( 1)(n np g p −= )
( )( 1)
( 1) ( 1)( 1)
( )'( )
nn n
n
f pg p pf p
−− −
−= − , 1n ≥
Akan menjadi sangat jelas dari persamaan tersebut bahwa iterasi pada Metode
Newton-Raphson tidak dapat dilanjutkan jika ( 1)'( ) 0nf p − = .
Teorema 2.4.1
Misalkan [ ]2 ,f C a b∈ . Jika [ ],p a b∈ sedemikian hingga dan ( ) 0f p = ( )' 0f p ≠ ,
maka ada sebuah 0δ > sedemikian sehingga metode Newton-Raphson akan
29
membangkitkan barisan { }( )
1
n
np
∞
= konvergen ke p untuk beberapa pendekatan awal
[ ](0) ,p p pδ δ∈ − + .
Bukti :
Bukti akan didasarkan dengan menganalisa metode Newton-Raphson sebagai pola
iterasi fungsional , untuk , dengan ( ) ( 1)(n np g p −= ) 1n ≥
( ) ( )'( )
f xg x xf x
= − .
Untuk sebuah nilai k di ( )0,1 , interval [ ],p pδ δ− + sedemikian sehingga g
merupakan pemetaan dari interval [ ],p pδ δ− + ke [ ],p pδ δ− + dan '( ) 1g x k≤ <
untuk [ ],x p pδ δ∈ − + .
Karena ( )'f p ≠ 0 dan 'f kontinu , maka ada sebuah 1 0δ > sedemikian sehingga
untuk '( ) 0f x ≠ [ ] [ ]1 1, ,x p p aδ δ∈ − + ⊂ b . Kemudian, g didefinisikan dan kontinu
pada [ ]1,p p 1δ δ− + . Sehingga
[ ] [ ]2 2
'( ) '( ) ( ) ''( ) ( ) ''( )'( ) 1'( ) '( )
f x f x f x f x f x f xg xf x f x−
= − =
untuk [ ]1,x p p 1δ δ∈ − + ; karena [ ]2 ,f C a b∈ , akan didapatkan
[ ]11,g C p p 1δ δ∈ − + . Berdasarkan asumsi ( ) 0f p = sehingga
[ ]2
( ) ''( )'( ) 0'( )
f p f pg pf x
= =
30
Karena ' kontinu , akan implikasi dengan untuk sebuah bilangan positif g 1k <
maka ada a δ , dengan 10 δ δ< < dan
'( )g x k≤ untuk [ ],x p pδ δ∈ − +
Akan ditunjukkan bahwa [ ] [ ]: , ,g p p p pδ δ δ δ− + → − + . Jika [ ],x p pδ δ∈ − + ,
Teorema Nilai Rata-Rata akan implikasi dengan untuk sebuah bilangan ξ antara x
dan p, ( ) ( ) '( )g x g p g x pξ− = − sehingga
( ) ( ) ( ) '( )g x p g x g p g x p k x p x pξ− = − = − ≤ − < −
Karena [ ],x p pδ δ∈ − + , yang diikuti dengan x p δ− < dan ( )g x p δ− < . Akan
berimplikasi dengan [ ] [ ]: , ,g p p p pδ δ δ− + → − +δ .
Semua kesimpulan yang terdapat pada Teorema 2.3.2 akan dipenuhi untuk
( )( )'( )
f xg x xf x
= − , sehingga barisan { }( )
1
n
np
∞
= didefinisikan dengan
( )( ) ( 1)n np g p −= untuk 1, 2,3,n = …
konvergen ke p untuk sebuah [ ](0) ,p p pδ δ∈ − + .
■
E. Optimasi Fungsi menggunakan Metode Quadratic Fit Line Search
Definisi 2.5.1
Himpunan S di dikatakan konveks jika setiap garis penghubung antara kedua
nilai yang ada di himpunan berada juga pada himpunan tersebut. Dengan kata lain,
jika dan ada di , maka
n
1x 2x S 1 (1 ) 2λ λ+ −x x harus ada di S untuk setiap [ ]0,1λ∈ .
31
x1●
● x2
(a) konveks (b) bukan konveks
Gambar 2.5.1 . Ilustrasi dari himpunan konveks
Contoh 2.5.1
Beberapa contoh himpunan konveks.
1. ( ){ }2 21 2 1 2, : 4S x x x x= + ≤ 2⊂
)
Himpunan ini merepresentasikan nilai yang berada di dalam lingkaran dengan pusat
dan radius 2 seperti pada gambar 2.5.2 (0,0
Gambar 2.5.2
2. ( ){ }2 2, :S x y y x= ≥ ⊂
Himpunan ini mempresentasikan semua nilai yang berada di atas kurva 2y x=
seperti pada gambar 2.5.3
32
Gambar 2.5.3
Definisi 2.5.2 (Quasikonveks)
Misalkan dengan S adalah himpunan konveks tak kosong dalam E1: ESf → n.
Fungsi f dikatakan quasikonveks jika untuk setiap dan , maka berlaku
pertidaksamaan
1x 2x S∈
{ } )1,0( semuauntuk )(),(maximum])1([ 2121 ∈≤−+ λλλ xxxx fff
Fungsi f dikatakan quasikonkav jika – f adalah quasikonveks.
Misalkan akan diminimumkan fungsi kontinu, suatu fungsi quasiconvex
)(λθ yang keras (strength) dengan 0≥λ dan akan diasumsikan tiga nilai
3210 λλλ <<≤ sedemikian sehingga 21 θθ ≥ dan 32 θθ ≥ dengan )( jj λθθ =
dengan . Jika 3,2,1=j θθθ == 21 maka akan mudah dipastikan bahwa semuanya
adalah penyelesaian minimumnya. Oleh karena itu, misalkan salah satu dari
pertidaksamaan 21 θθ ≥ dan 32 θθ ≥ bernilai benar. Kemudian akan mengarah
kepada kondisi yang dipenuhi oleh pola tiga nilai (Three Point Pattern atau TPP).
Sebagai awalnya, ambil 01 =λ dan menghitung nilai percobaan λ yang
dapat merupakan besarnya langkah dari metode line search dalam iterasi berikutnya.
Misalkan )(λθθ = . Jika 1θθ ≥ maka dapat ditentukan λλ =3 dan 2λ dapat
33
ditemukan dari membagi dua interval [ ]31 ,λλ secara berulang-ulang sampai
mencapai TPP. Dengan kata lain, jika 2θθ < maka dapat ditentukan λλ =3 dan 3λ
dapat ditemukan dengan penggandaan interval [ ]21,λλ sampai mencapai TPP.
Akan diberikan tiga titik ( ) 3,2,1,, =jjj θλ . Dapat disusun sebuah kurva
kuadratik yang melalui ketiga titik dan dapat meminimumkan λ dimana harus
terletak dalam ),( 31 λλ dengan TPP. Misalkan )(λθθ = dan newλ sebagai
peninjauan kembali himpunan dari tiga nilai ( )321 ,, λλλ yang diperbaharui adalah
sebagai berikut
i. Kasus I : 2λλ >
Jika 2θθ ≥ maka ( )λλλλ ,, 21=new . Dengan kata lain, jika 2θθ ≤ maka
( )32 ,, λλλλ =new .
ii. Kasus II : 2λλ <
Mirip dengan kasus I, jika 2θθ ≥ maka ( )32 ,, λλλλ =new dan jika 2θθ ≤
maka ( )21 ,, λλλλ =new
iii. Kasus III : 2λλ =
Dalam kasus ini, tidak perlu dicari nilai yang berbeda untuk mencapai TPP.
Jika ( ) ελλ ≤− 13 untuk beberapa toleransi konvergensi dengan 0>ε dapat
berhenti untuk menentukan besar langkah. Sebaliknya dapat ditentukan
sebuah nilai baru λ sebagai jarak 2/ε dari 2λ terhadap 1λ atau 3λ .
BAB III
PENYELESAIAN SISTEM PERSAMAAN NON-LINEAR
Dalam Bab III ini akan dibahas tentang beberapa metode untuk
menyelesaikan sistem persamaan non-linear yaitu Metode Newton dan Metode Turun
Tercuram serta konvergensi kedua metode. Di dalam pembahasan kedua metode ini,
pertama penulis akan membahas terlebih dahulu tentang sistem persamaan non-linear
serta Iterasi Titik-Tetap sebagai konsep dasar untuk metode Newton. Kemudian akan
dibahas Metode Newton serta konvergensinya dan yang terakhir Metode Turun-
Tercuram serta konvergensinya. Pengimplementasian penyelesaian sistem persamaan
non-linear dengan Metode Newton dan Metode Turun-Tercuram menggunakan
bahasa pemrograman Matlab.
A. Sistem Persamaan Non-Linear
Sistem persamaaan non-linear adalah himpunan m persamaan non-linear,
dengan 1>m . Sistem persamaan non-linear dengan m persamaan dan n variabel
secara umum berbentuk:
0),,,(
0),,,(0),,,(
21
212
211
=
==
nm
n
n
xxxf
xxxfxxxf
…
……
(3.1.1)
35
Setiap fungsi if dengan ni ,,2,1 …= merupakan pemetaan vektor
tnxxx ),,,( 21 …=x dari n ke . Sistem ini dapat ditulis dalam bentuk lain dengan
mendefinisikan fungsi F yakni pemetaan dari n ke n yang dapat ditulis sebagai
tnmnnn xxxfxxxfxxxfxxx )),,,(,,),,,(,),,,((),,,( 2121221121 …………… =F
Dengan menggunakan notasi vektor, sistem di atas dapat dinyatakan dalam bentuk
F(x) = 0 (3.1.2)
Fungsi mfff ,,, 21 … disebut koordinat fungsi F.
Contoh sistem persamaan non-linear
020
006.1sin)1.0(81
0)cos(3
3310
3
32
22
1
21
321
21 =++
=+++−
=−−
−− πxe
xxx
xxx
xx
(3.1.3)
Sistem persamaan (3.1.3) dalam bentuk persamaan (3.1.2) dengan mendefinisikan
tiga fungsi 21 , ff dan 3f dari 3 ke sebagai berikut
020),,(
006.1sin)1.0(81),,(
0)cos(3),,(
3310
33213
32
22
13212
21
3213211
21 =++=
=+++−=
=−−=
−− πxexxxf
xxxxxxf
xxxxxxf
xx
Dengan demikian F merupakan fungsi dari 3 3→ dengan
txx
t
xexxxxxx
xxxfxxxfxxxf
xxx
)20,06.1sin)1.0(81,)cos(3(
)),,(),,,(),,,((
),,()(
3310
332
22
121
321
321332123211
321
21 −− +++++−−−=
=
=
π
FxF
36
B. KONSEP DASAR DAN ITERASI TITIK TETAP
Teorema 3.2.1
Jika F terdiferensial dalam suatu himpunan terbuka nΩ⊂ dan Ω∈*x maka untuk
semua Ω∈x yang dekat dengan *x berlaku
∫ −−+′=−1
0
*)*))((*(*)()( dtt xxxxxFxFxF
Bukti
Misalkan Ω∈*x dan Ω∈x dengan nΩ⊂ .
Perhatikan bahwa ∫ ′= duufuf )()( .
Misalkan *)(* xxxu −+= t maka dtd *)( xxu −=
untuk *0 xu =⇒=t dan xu =⇒= 1t
Sehingga
∫∫ ′=−−+′x
x
uuFxxxxtxF*
1
0
)(*)*))((*( ddt
1
0**))(*()( xxxFuF x
x−+== t
*)(*))(*( xFxxxF −−+=
*)()( xFxF −=
■
37
Definisi 3.2.2
Misalkan { }( )n n⊂x dan * n∈x
i. *)( xx →n q-kuadratik jika *)( xx →n dan ada sebuah 0>K sedemikian
sehingga
2)()1( ** xxxx −≤−+ nn K
ii. *)( xx →n q-superlinear dengan q-orde 1>α jika *)( xx →n dan ada sebuah
0>K sedemikian sehingga
α** )()1( xxxx −≤−+ nn K
iii. *)( xx →n q-superlinear jika
0*
*lim
)(
)1(
=−
−+
∞→ xx
xxn
n
n
iv. *)( xx →n q-linear dengan q-faktor )1,0(∈σ jika
** )()1( xxxx −≤−+ nn σ
Definisi 3.2.3
Misalkan nΩ⊂ dan : nΩ→G . G memenuhi kondisi kontinu Lipschitz dalam Ω
dengan konstanta Lipschitz γ jika
yxyGxG −≤− γ)()(
38
Asumsi 3.2.4
1. Persamaaan (3.1.2) mempunyai penyelesaian *x .
2. : n n×′ Ω→F merupakan kontinu Lipshitz dengan konstanta Lipshitz γ .
3. *)(xF′ adalah nonsingular.
Dalam hal ini *x adalah akar penyelesaian dari F. Misalkan )(rΒ menyatakan suatu
bola dengan radius r di sekitar *x .
{ } *dengan |)( xxeex −=<= rrΒ
Jika )(kx merupakan iterasi ke-k dari barisan maka *)()( xxe −= kk merupakan
kesalahan dari iterasi tersebut.
Lemma 3.2.5
Misalkan Asumsi 3.2.4 terpenuhi. Maka ada 0>δ sedemikian sehingga untuk
semua )(δΒ∈x
, *)(2)( xFxF ′≤′ (3.2.1)
, *)(2)( 11 −− ′≤′ xFxF (3.2.2)
dan
exFxFe
xF *)(2)(2
*)(11 ′≤≤′−− (3.2.3)
39
Bukti
i). Akan dibuktikan bahwa *)(2)( xFxF ′≤′
Karena F′ merupakan kontinu Lipschitz dan )(δΒ∈x maka
δγγγ ≤≤−≤′−′ exxxFxF **)()(
Pilih γ
δ*)(xF′
= sedemikian sehingga 1*)(*)()( −′≤′−′ xFxFxF
*)()(*)()(*)( xFxFxFxFxF ′−′≥′−′≥′
)(*)(2*)(*)( xFxFxFxF ′≥′=′+′
Sehingga *)(2)( xFxF ′≤′
ii). Akan dibuktikan bahwa *)(2)( 11 −− ′≤′ xFxF
Perlu diingat tentang Lemma Banach bahwa
BAIA
B−−
≤−
11
Misalkan 1*)( −′= xFA dan )(xFB ′=
1
11
*)()(1
*)()(
−
−−
′′−−
′≤′
xFxFI
xFxF
maka 21*)()(1 1 ≤′′−− −xFxFI
1111 *)(*)(*))()((*)(*)()( −−−− ′≤′≤′−′′=′′− xFexFxFxFxFxFxFI δγγ
40
Pilih γ
δ2
*)(11 −−′
=xF
sedemikian sehingga
21*)(
2
*)(*)()( 1
111 ≤′
′≤′′− −
−−− xF
xFxFxFI
γγ (3.2.4)
dengan demikian
1
21
1
21
11 *)(2
*)(
1
*)()( −
−−− ′=
′≤
−
′≤′ xF
xFxFxF
iii). Akan dibuktikan exFxFe
xF *)(2)(2
*)(11 ′≤≤′−−
Untuk membuktikan pertidaksamaan tersebut, perlu dicatat bahwa jika )(δΒ∈x
maka )(* δΒt ∈+ ex untuk semua .10 ≤≤ t Dari teorema 3.2.1 dan pertidaksamaan
(3.2.1) akan didapatkan
exFexFeexFxFxFxF *)(2*)(2)*()(*)()(1
0
1
0
′=′≤+′≤≤− ∫∫ dtdtt
yang merupakan sebelah kanan dalam pertidaksamaan (3.2.3).
Sedangkan untuk membuktikan sebelah kiri dari pertidaksamaan (3.2.3) diperoleh
dengan cara
∫∫ +′=′=1
0
1
0
)*()()( dttd eexFxxFxF
∫∫∫∫ +′′+−=+′′=′ −−−1
0
11
0
1
0
1
0
11 )*(*)()*(*)()(*)( dttdtdtdtt eexFxFeeeexFxFxFxF
41
∫∫ +′′−−= −1
0
11
0
))*(*)(( dttdt eexFxFIe
∫ +′′−−= −1
0
1 ))*(*)(( dtt eexFxFIe
Dan dari pertidaksamaan (3.2.4) didapatkan
∫ +′′−−=′ −−1
0
11 ))*(*)(()(*)( dtt eexFxFIexFxF
∫ +′′−−≥ −1
0
1 ))*(*)(( dtt eexFxFIe
2
))*(*)((11
0
1 eexFxFIe ≥
⎥⎥⎦
⎤
⎢⎢⎣
⎡+′′−−= ∫ − dtt
sehingga
)(*)()(*)(2
11 xFxFxFxFe −− ′≤′≤
■
C. METODE NEWTON
Metode Newton merupakan salah satu metode yang paling terkenal dan sering
digunakan dalam menyelesaikan suatu sistem persamaan non-linear. Metode ini
merupakan perkembangan dari metode Newton-Raphson dan metode Fixed-Point
yang digunakan untuk menyelesaikan persamaan non-linear.
42
Dalam membangun suatu algoritma akan digunakan pendekatan metode
fixed-point untuk kasus satu dimensi yakni mencoba untuk menemukan suatu fungsi
φ yang memenuhi :
)()()( xfxxxg φ−=
yang akan konvergen kuadratik ke titik p dari g. Dari kondisi tersebut, Metode
Newton mengembangkannya dengan memilih )(/1)( xfx ′=φ .
Dengan menggunakan pendekatan serupa, untuk kasus n-dimensi dapat
disajikan dalam bentuk matriks
⎥⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢
⎣
⎡
=
)()()(
)()()()()()(
)(
21
22221
11211
xxx
xxxxxx
xA
nnnn
n
n
aaa
aaaaaa
(3.3.1)
Setiap elemen )(xija merupakan fungsi dari n ke . Algoritma ini memerlukan
)(xA sehingga memenuhi
G(x) = x – A(x)-1F(x)
menyebabkan penyelesaian dari 0xF =)( konvergen kuadratik dan
)(xA nonsingular.
Definisi 3.3.1
Suatu fungsi G dari nD ⊂ ke n mempunyai titik tetap di D∈p jika ppG =)( .
43
Teorema 3.3.2
Misalkan ( ){ }nibxaxxxD iiit
n ,,2,1 setiapuntuk |,,, 21 …… =≤≤= untuk beberapa
konstanta naaa ,,, 21 … dan nbbb ,,, 21 … . Misalkan G adalah fungsi kontinu dari
nD ⊂ ke n dengan D∈)(xG jika D∈x . Maka G mempunyai titik tetap di D.
Misalkan bahwa G mempunyai derivatif parsial yang kontinu dan ada suatu konstanta
K < 1 dengan
D nK
xg
j
i ∈≤∂
∂x
x jika
)(, (3.3.2)
untuk setiap nj ,,2,1 …= dan setiap fungsi ig . Maka barisan { }∞=0)(
kkx didefinisikan
dengan memilih )0(x yang berubah-ubah di D dan dibangkitkan oleh
( ) 1 setiapuntuk ,)1()( ≥= − kkk xGx
konvergen ke suatu titik tetap secara tunggal D∈p dan
.1
)0()1()(
∞∞−
−≤− xxpx
KK k
k
Bukti
i). Jika aaG =)( dan bbG =)( jelas ada titik tetapnya. Misalkan salah maka pasti
benar bahwa aaG >)( dan bbG <)( . Definisikan xxGxH −= )()( maka H akan
kontinu dalam D dan
0aaGaH >−= )()( 0bbGbH <−= )()(
44
Teorema Nilai Antara akan implikasi dengan jika ada D∈p untuk semua
0pH =)( maka 0ppGpH =−= )()( dan p adalah titik tetap dari G.
Misalkan pertidaksamaan (3.3.2) berlaku dan bahwa p dan q keduanya adalah
titik tetap di D dengan qp ≠ . Berdasarkan Teorema Rata-Rata, ada ξ antara p
dan q, dan oleh karena itu berada di D, dengan
)()()(
ξqp
j
i
ii
ii
xg
qpgg
∂∂
=−−
Maka
iiiiiij
iiiii qpqp
nKqp
xg
ggqp −<−≤−∂∂
=−=− )()()( ξqp
akan menyebabkan kontradiksi. Oleh karena itu, ii qp = dan titik tetap di D akan
tunggal.
Sehingga G mempunyai titik tetap secara tunggal p di D.
ii). G mempunyai titik tetap secara tunggal D∈p . Karena G merupakan suatu
pemetaan D ke D barisan { }∞=0)(
kkx terdefinisi untuk semua 0≥k dan Dk ∈)(x
untuk semua k. Dengan menggunakan pertidaksamaan (3.3.2) dan Teorema Nilai
Rata-Rata akan didapatkan
ik
iik
ij
ii
kii
ki px
nKpx
xg
ggpx −≤−∂
∂=−=− − )()()1()( )(
)()(ξ
px
dengan D∈ξ .
45
Pertidaksamaan tersebut dikembangkan secara induksi sehingga
ii
k
ik
iik
iik
i pxnKpx
nKpx
nKpx −⎟
⎠⎞
⎜⎝⎛≤≤−⎟
⎠⎞
⎜⎝⎛≤−≤− −− )0()2(
2)1()( … (3.3.3)
Karena 1<K
0limlim )0()( =−⎟⎠⎞
⎜⎝⎛=−
∞→∞→ ii
k
kik
ikpx
nKpx
sehingga { }∞=0)(
kk
ix konvergen ke p dan menyebabkan { }∞=0)(
kkx juga konvergen ke
p.
iii). Untuk 1≥k pertidaksamaan (3.3.3) implikasi dengan
)2()1(2
)1()()1()()()1( )()( −−−−+ −⎟⎠⎞
⎜⎝⎛≤−≤−=− k
ik
ik
ik
ik
ik
ik
ik
i xxnKxx
nKggxx xx
)0()1()0()1()3()2(3
iik
ii
kk
ik
i xxKxxnKxx
nK
−≤−⎟⎠⎞
⎜⎝⎛≤≤−⎟
⎠⎞
⎜⎝⎛≤ −− …
Kemudian untuk 1≥> km
)()1()1()1()()()( ki
ki
mi
mi
mi
ki
mi xxxxxxx −+−+−=− +−− …
)()1()2()1()1()( ki
ki
mi
mi
mi
mi xxxxxx −++−+−≤ +−−− …
)0()1()0()1(2)0()1(1ii
kii
mii
m xxKxxKxxK −++−+−≤ −− …
( ) )0()1(121 iikmk xxKKKK −++++= −−…
Perlu diingat bahwa im
impx =
∞→
)(lim sehingga
46
∑∞
=∞→
−≤−=−0
)0()1()()()( limi
iii
kki
mik
kii KxxKxxxp
Karena ∑∞
=0i
iK merupakan barisan geometri dengan konstanta rasio K, maka akan
didapatkan
)0()1()(
1 ii
k
ik
i xxK
Kpx −−
≤−
Perlu diingat bahwa ijnjia
≤≤∞=
,1maxA sehingga
ik
ini
k px −=−≤≤∞
)(
1
)( maxpx
)0()1(
1
)0()1(
1max
11max ii
ni
k
ii
k
nixx
KKxx
KK
−−
=−−
≤≤≤≤≤
∞
−−
= )0()1(
1xx
KK k
■
Teorema 3.3.3
Misalkan p adalah penyelesaian dari xxG =)( untuk suatu fungsi
G tngg ),,,(g 21 …= yang memetakan dari n ke n . Jika ada sebuah 0>δ
sedemikian sehingga { }δδ <−= pxx |N maka untuk semua
( ) δNxxx tm ∈= ,,, 21 …x , G(x) dapat dijabarkan menjadi deret Taylor linear sebagai
berikut :
47
∑∑∑= ==
−−∂∂
∂+−
∂∂
+=m
jkkjj
m
k kj
ijj
m
j j
iii pxpx
xxg
pxxg
gg1 1
2
1))()((
!21)()()()( ξppx (3.3.4)
dengan Ν∈m dan ni ,,2,1 …=
Bukti :
Akan dibuktikan bahwa )(xig benar dengan menggunakan Prinsip Induksi
Matematika.
• untuk m = 2
txx ),( 21=x
tpp ),( 21=p
∑∑∑= ==
−−∂∂
∂+−
∂∂
+=2
1
2
1
22
1))()((
!21)()()()(
jkkjj
k kj
ijj
j j
iii pxpx
xxg
pxxg
gg ξppx
⎢⎢⎣
⎡⎜⎜⎝
⎛−
∂∂∂
+⎥⎦
⎤⎢⎣
⎡−
∂∂
+−∂∂
+= ∑=
2
1 1
2
222
111
))((!2
1))(())(()(j
jjj
iiii px
xxg
pxxg
pxxg
g ξppp
⎥⎥⎦
⎤⎟⎟⎠
⎞−−
∂∂∂
+− ))()(()( 222
2
11 pxpxxx
gpx jj
j
i ξ
⎢⎣
⎡+−
∂
∂+⎥
⎦
⎤⎢⎣
⎡−
∂∂
+−∂∂
+= 2112
1
2
222
111
))((!2
1))(())(()( pxxg
pxxg
pxxg
g iiii ξppp
⎥⎦
⎤−
∂
∂+−−
∂∂∂
+−−∂∂
∂ 2222
2
2
112221
2
221112
2
))(())()(())()(( pxxg
pxpxxx
gpxpx
xxg iii ξξξ
48
⎢⎣
⎡+−
∂
∂+⎥
⎦
⎤⎢⎣
⎡−
∂∂
+−∂∂
+= 2112
1
2
222
111
))((!2
1))(())(()( pxxg
pxxg
pxxg
g iiii ξppp
⎥⎦
⎤−
∂
∂+−−
∂∂∂ 2
2222
2
221112
2
))(())()((2 pxxg
pxpxxx
g ii ξξ
⎢⎣
⎡+
−∂
∂+⎥
⎦
⎤⎢⎣
⎡−
∂∂
+−∂∂
+=2
)()())(())(()()(2
112
1
2
222
111
pxxg
pxxg
pxxg
gg iiiii ξpppx
⎥⎦
⎤−∂
∂+−−
∂∂∂
2)(
)())()((2
222
2
2
221112
2 pxxg
pxpxxx
g ii ξξ
• diandaikan benar untuk m = r
tr
tr
ppp
xxx
),,,(
),,,(
21
21
……
=
=
p
x
∑∑∑= ==
−−∂∂
∂+−
∂∂
+=r
jkkjj
r
k kj
ijj
r
j j
iii pxpx
xxg
pxxg
gg1 1
2
1))()((
!21)()()()( ξppx
• untuk m = r + 1
),(),,,,(),,,( 1121121 +++ == rirriri xgxxxxgxxxg x……
∑∑∑+
=
+
=
+
=+++ −−
∂∂∂
+−∂∂
+=1
1
1
1
21
1111 ))()((
!21)(),(),(),(
r
jkkjj
r
k kj
ijj
r
jr
j
iriri pxpx
xxgpxp
xgpgxg ξppx
∑∑∑+
=
+
=
+
=
−−∂∂
∂+−
∂∂
+=1
1
1
1
21
1
### ))()((!2
1)()()()(r
jkkjj
r
k kj
ijj
r
j j
iii pxpx
xxg
pxxg
gg ξppx
dengan trxxx ),,,( 121
#+= …x dan t
rppp ),,,( 121#
+= …p
49
Jadi, benar bahwa deret Taylor linear pada persamaan (3.3.4) berlaku untuk semua
Ν∈m .
■
Teorema 3.3.4
Misalkan p adalah penyelesaian dari xxG =)( untuk suatu fungsi
G tngg ),,,(g 21 …= yang memetakan dari n ke n .
Jika ada sebuah 0>δ dengan sifat :
i) j
i
xg∂∂
kontinu pada { }δδ <−= pxx |N untuk setiap ni ,,2,1 …= dan
nj ,,2,1 …=
ii) )()(2
kj
i
xxg∂∂
∂ x kontinu dan Mxx
g
kj
i ≤∂∂
∂)()(2 x
untuk suatu konstanta M, jika δN∈x untuk
setiap ni ,,2,1 …= , nj ,,2,1 …= dan nk ,,2,1 …=
iii) 0)(=
∂∂
j
i
xg p
untuk setiap ni ,,2,1 …= dan nj ,,2,1 …=
maka ada sebuah δδ ≤ sedemikian sehingga barisan yang dibangkitkan oleh
( ))1()( −= kk xGx konvergen secara kuadratik ke p untuk sebarang )0(x yang dipilih,
asalkan bahwa δ<−px )0(
Selain itu
50
2)1(2
)(
2 ∞
−
∞−≤− pxpx kk Mn untuk setiap 1≥k
Bukti :
Misalkan ada 0>δ sedemikian sehingga :
i) j
i
xg∂∂
kontinu dalam { }δδ <−= pxx |N untuk setiap ni ,,2,1 …= dan
nj ,,2,1 …=
ii) )()(2
kj
i
xxg∂∂
∂ x dengan δN∈x untuk setiap ni ,,2,1 …= , nj ,,2,1 …= dan
nk ,,2,1 …=
iii) 0)(=
∂∂
j
i
xg p
untuk setiap ni ,,2,1 …= dan nj ,,2,1 …=
Pilih δδ ≤ˆ sedemikian sehingga ada dalam interval δN , G memiliki derivatif parsial
yang kontinu, nK
xg
j
i ≤∂
∂ )(x dan
)()(2
kj
i
xxg∂∂
∂ x kontinu untuk setiap
ni ,,2,1 …= , nj ,,2,1 …= dan nk ,,2,1 …= . Karena nK
xg
j
i ≤∂
∂ )(x maka syarat-
syarat dari barisan { }∞=0)(
nnp berada dalam δN .
Penjabaran G(x) dalam deret Taylor linear untuk ( ) δNxxx tm ∈= ,,, 21 …x dan setiap
ni ,,2,1 …= sebagai berikut :
51
∑∑∑= ==
−−∂∂
∂+−
∂∂
+=m
jkkjj
m
k kj
ijj
m
j j
iii pxpx
xxg
pxxg
gg1 1
2
1))()((
!21)()()()( ξppx
dengan ( )iii px ,∈ξ .
Dengan menggunakan hipotesa G(p) = p dan 0)(=
∂∂
j
i
xg p
untuk setiap
ni ,,2,1 …= dan nj ,,2,1 …= dapat disimpulkan bahwa
∑∑= =
−−∂∂
∂+=
m
jkkjj
m
k kj
ii pxpx
xxg
g1 1
2
))()((!2
1)( ξpx
Jika )(npx = untuk suatu n ,
∑∑= =
+ −−∂∂
∂+==
m
jk
nkj
nj
m
k
n
kj
ii
ni
ni pppp
xxg
pgp1
)()(
1
)(2
)()1( ))()((!2
1)( ξp
dan ( )in
in
i pp ,)()( ∈ξ
Jadi,
∑∑= =
++
∂∂∂
==−m
j
nk
nj
m
k
n
kj
ini
ni
ni ee
xxg
epp1
)()(
1
)(2
)1()()1( ))()((!2
1 ξ
Untuk ikj == maka akan diperoleh
( )( )2)()(2
2)1(
21 n
in
i
ini e
xg
e ξ∂
∂=+
nK
xg
j
i ≤∂
∂ )(x dalam δN dan G memetakan n ke n . Berdasarkan pada teorema
3.3.2 maka barisan { }∞=0)(
nn
ip yang didefinisikan dengan memilih sebarang )0(ip dan
membangkitkan
52
( ))1()( −= ni
ni gp p untuk setiap 1≥n
konvergen ke suatu titik tetap secara tunggal p .
)(niξ berada dalam δ̂)( <− i
ni pp untuk setiap n. { }∞=0
)(n
niξ konvergen ke p juga dan
)(21lim 2
2
2)(
)1(
pi
i
ni
ni
n xg
e
e
∂
∂=
+
∞→
Ini berarti bahwa barisan { }∞=0)(
nnp adalah konvergen kuadratik.
Jadi benar bahwa ada δδ ≤ sedemikian sehingga barisan yang dibangkitkan oleh
( ))1()( −= kk G xx konvergen secara kuadrat ke p untuk sebarang )0(x asalkan bahwa
δ<−px )0( .
Karena )()(2
kj
i
xxg∂∂
∂ x kontinu dan Mxx
g
kj
i ≤∂∂
∂)()(2 x
untuk suatu konstanta M dengan
δN∈x untuk setiap ni ,,2,1 …= , nj ,,2,1 …= dan nk ,,2,1 …= sehingga ini
berlaku juga untuk nilai n yang cukup besar,
2)1(2
)(
2 ∞
−
∞−≤− pxpx kk Mn
■
Dalam menggunakan Teorema 3.3.4, misalkan bahwa A(x) adalah matriks
nn× dari fungsi n ke dalam bentuk persamaan (3.3.1) dengan spesifikasi setiap
elemen akan dipilih kemudian.
53
Misalkan bahwa A(x) adalah nonsingular yang dekat dengan penyelesaian p dari
0xF =)( dan )(xijb menyatakan elemen dari 1)( −xA dengan baris ke-i dan kolom
ke-j.
Karena )()()( 1 xFxAxxG −−= dengan ∑=
−=n
jjijii fbxg
1)()()( xxx maka
⎪⎪
⎩
⎪⎪
⎨
⎧
≠⎟⎟⎠
⎞⎜⎜⎝
⎛∂
∂+
∂
∂−
=⎟⎟⎠
⎞⎜⎜⎝
⎛∂
∂+
∂
∂−
=∂
∂
∑
∑
=
=
kifxb
xf
b
kifxb
xf
b
xg
n
jj
k
ij
k
jij
n
jj
k
ij
k
jij
k
i
jika,)()()()(
jika,)()()()(1)(
1
1
xxxx
xxxxx
Teorema 3.3.4 menyatakan bahwa diperlukan 0)(=
∂∂
j
i
xg p
untuk setiap
ni ,,2,1 …= dan nj ,,2,1 …= . Ini berarti untuk ki = ,
∑= ∂
∂−=
n
j i
jij x
fb
1,)()(10 pp
sehingga
1)()(1
=∂
∂∑=
n
j i
jij x
fb pp (3.3.5)
Sedangkan untuk ki ≠ ,
∑= ∂
∂−=
n
j i
jij x
fb
1,)()(0 pp
sehingga
0)()(1
=∂
∂∑=
n
j i
jij x
fb pp (3.3.6)
54
Dengan mendefinisikan matriks J(x) sebagai
1 1 1
1 2
2 2 2
1 2
1 2
( ) ( ) ( )
( ) ( ) ( )( )
( ) ( ) ( )
n
n
n n n
n
f f fx x x
f f fx x x
f f fx x x
∂ ∂ ∂⎡ ⎤⎢ ⎥∂ ∂ ∂⎢ ⎥∂ ∂ ∂⎢ ⎥⎢ ⎥∂ ∂ ∂= ⎢ ⎥⎢ ⎥⎢ ⎥∂ ∂ ∂⎢ ⎥⎢ ⎥∂ ∂ ∂⎣ ⎦
x x x
x x xJ x
x x x
(3.3.7)
maka persamaan (3.3.5) dan (3.3.6) memerlukan
1( ) ( ) ,− =A p J p I
sehingga
( ) ( ).=A p J p
Sebagai akibatnya suatu pilihan pendekataan untuk A(x) adalah ( ) ( )=A x J x
karena kondisi (iii) pada teorema 3.3.4 terpenuhi.
Dengan demikian fungsi G didefinisikan dengan
1( ) ( ) ( )−= −G x x J x F x
dan algoritma iterasi fungsional tersusun dari memilih )0(x dan membangkitkannya
untuk 1≥k ,
( ) ( ) ( )1( ) ( 1) ( 1) ( 1) ( 1)k k k k k−− − − −= = −x G x x J x F x (3.3.8)
Metode ini disebut Metode Newton untuk Sistem Persamaan Non-Linear
dan biasanya diharapkan dapat menyebabkan konvergen kuadratik, asalkan diketahui
nilai awal yang cukup tepat dan ada 1( )−J p .
55
Flowchart dari algoritma Metode Newton dalam menyelesaikan sistem
persamaan non-linear.
Gambar 3.3.1
start
Nilai awal (x)Tol.error (error)
Iterasi maksimum (N)k=1
while k<=N
y=-inv(jx)*fx
if norm(y)<tol x
x=x+y'k=k+1
end ya
tidak
fx=fungsi(x) jx=jacobian(x)
56
Contoh 3.3.1
Carilah penyelesaian sistem persamaan non-linear di bawah ini dengan menggunakan
metode Newton
020
006.1sin)1.0(81
0)cos(3
3310
3
32
22
1
21
321
21 =++
=+++−
=−−
−− πxe
xxx
xxx
xx
Penyelesaian
Dengan pendekatan awal ( )(0) 0.1,0.1, 0.1 t= −x , toleransi 210ε −= dan 10N =
Matriks Jacobian ( )J x untuk sistem ini adalah
1 2 1 2
3 2 3 2 2 3
1 2 3 1 2 3
2 1
3 sin sin( , , ) 2 162( 0.1) cos
20x x x x
x x x x x xx x x x x x
x e x e− −
⎡ ⎤⎢ ⎥= − +⎢ ⎥⎢ ⎥− −⎣ ⎦
J
dan
( ) ( 1) ( 1)1 1 1
( ) ( 1) ( 1)2 2 2
( ) ( 1) ( 1)3 3 3
k k k
k k k
k k k
x x yx x yx x y
− −
− −
− −
⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ ⎢ ⎥= +⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦
,
dengan ( )( ) ( )( 1)
11
( 1) ( 1) ( 1) ( 1) ( 1) ( 1) ( 1)2 1 2 3 1 2 3
( 1)3
, , , ,
k
k k k k k k k
k
yy x x x x x xy
−
−− − − − − − −
−
⎡ ⎤⎢ ⎥ = −⎢ ⎥⎢ ⎥⎣ ⎦
J F
Kemudian, pada iterasi ke-k sistem linear ( ) ( )( 1) ( 1) ( 1)k k k− − −= −J x y F x harus dapat
diselesaikan, dengan
57
( 1) ( 1) ( 1) ( 1)1 2 1 2
( 1) ( 1) ( 1) ( 1) ( 1) ( 1)3 2 3 2 2 3
( 1) ( 1) ( 1)1 2 3 1 2 3
( 1) ( 1)2 1
3 sin sin( , , ) 2 162( 0.1) cos
20k k k k
k k k k k k
k k k
x x x xk k
x x x x x xx x x x x x
x e x e− − − −
− − − − − −
− − −
− −− −
⎡ ⎤⎢ ⎥
= − +⎢ ⎥⎢ ⎥− −⎣ ⎦
J ,
( 1)1
( 1) ( 1)2
( 1)3
k
k k
k
yyy
−
− −
−
⎡ ⎤⎢ ⎥= ⎢ ⎥⎢ ⎥⎣ ⎦
y , dan ( ) ( )( 1) ( 1)
1 2
( 1) ( 1) ( 1) 11 2 3 2
2( 1) ( 1) ( 1) 2 ( 1)1 2 3
( 1) 10 33 3
3 cos( )
81( 0.1) sin 1.06
20k k
k k k
k k k k
x x k
x x x
x x x
e x π− −
− − −
− − − −
− − −
⎡ ⎤− −⎢ ⎥⎢ ⎥= − + + +⎢ ⎥⎢ ⎥+ +⎣ ⎦
F x .
Hasil penyelesaian sistem dengan menggunakan metode Newton
-------------------------------------------------------
k | x1 | x2 | x3
-------------------------------------------------------
0 0.100000 0.100000 -0.100000
1 0.499870 0.019467 -0.521520
2 0.500014 0.001589 -0.523557
3 0.500014 0.001589 -0.523557
Dari tabel di atas dapat dilihat bahwa metode Newton dapat konvergen dengan cepat
sekali pendekatan yang dihasilkan dekat dengan penyelesaian yang sebenarnya.
Bagaimanapun juga, tidak selalu mudah menentukan nilai awal yang pasti untuk
penyelesaiannya. Sebagai perbandingannya, akan diberikan contoh nilai awal yang
tidak mudah konvergen bahkan yang tidak memiliki penyelesaiannya.
58
a. (0) (9,7,5)t=x
Hasil penyelesaian sistem dengan menggunakan metode Newton
-------------------------------------------------------
k | x1 | x2 | x3
-------------------------------------------------------
0 9.000000 7.000000 5.000000
1 -8.280243 3.248734 -0.473599
2 -11.696025 1.787791 -11.656614
3 -13.705411 1.395148 -39.452404
4 -13.332672 1.360127 -11.309331
5 -13.403049 1.277946 -103.319472
6 -8.516938 1.669231 -307.691679
7 -12.372097 0.796947 -445.951097
8 8.409240 2.040590 167.213419
9 43.684234 3.253246 -0.473599
10 0.970759 -1.779062 -0.473599
11 0.555568 -0.942758 -0.318800
12 0.478269 -0.526994 -0.532366
13 0.496891 -0.325048 -0.532349
14 0.497836 -0.234536 -0.529738
15 0.498104 -0.204134 -0.528944
16 0.498104 -0.204134 -0.528944
59
b. (0) (10,10,10)t=x
Hasil penyelesaian sistem dengan menggunakan metode Newton
-------------------------------------------------------
k | x1 | x2 | x3
-------------------------------------------------------
0 10.000000 10.000000 10.000000
1 -26.3859 4.5720 -0.4736
(Warning: Matrix is close to singular or badly scaled. Results may be inaccurate.
RCOND = 5.762925e-054.)
Untuk nilai awal ini, dengan metode Newton, karena pada iterasi ke-2, matriks
Jacobiannya akan dekat dengan matriks singular maka invers dari matriks Jacobian
mendekati nol. Apabila dilanjutkan maka hasilnya tidaklah akurat dan jauh dari
penyelesaian yang sebenarnya, kalaupun dapat diselesaikan maka akan membutuhkan
iterasi yang cukup banyak.
c. ( )(0) 100,100,100 t=x
Hasil penyelesaian sistem dengan menggunakan metode Newton
-------------------------------------------------------
k | x1 | x2 | x3
-------------------------------------------------------
0 100.000000 100.000000 100.000000
1 -1761.168869 27.606920 -0.473599
60
Warning: Matrix is singular to working precision. (Type "warning off
MATLAB:singularMatrix" to suppress this warning.)
> In D:\Skripsi1\Burden\newton.m at line 24
2 NaN NaN NaN
Untuk nilai awal ini, dengan metode Newton, sistem tidak memiliki penyelesaian
yang konvergen. Dikarenakan pada iterasi ke-1, matriks Jacobian yang terbentuk
merupakan matriks singular yang menyebabkan matriks tidak mempunyai invers dan
iterasi tidak dapat dilanjutkan. Kalaupun dilanjutkan maka hasilnya tidak terdefinisi.
Berikut ini akan diberikan tabel perbandingan pengaruh nilai awal dengan hasil akhir
dan jumlah iterasi yang diperlukan pada metode Newton untuk menyelesaikan sistem
persamaan non-linear. Akan digunakan toleransi 210ε −=
Tabel 3.3.1 Tabel pengaruh nilai awal Metode Newton
No. Nilai Awal ( (0)x ) Penyelesaian Sistem ( ( )kx ) Iterasi
1. ( )5, 3, 1 t− − − ( )0.498126,-0.201667,-0.528880 t 7
2. ( )9, 12, 4 t− − − ( )0.498127,-0.201518,-0.528876 t 9
3. ( )20, 30, 40 t− − − ( )0.498134,-0.200732,-0.528855 t 64
4. ( )2,3,4 t ( )0.498075,-0.207249,-0.529026 t 25
5. ( )5,5,5 t ( )0.498046,-0.208749,-0.529064 t 20
6. ( )6,8,5 t ( )0.500047,0.005152,-0.523464 t 8
61
7. (9,7,5)t ( )0.498104,-0.204134,-0.528944 t 16
8. ( )10,10,10 t ( )0.500029,0.003170,-0.523516 t 105*)
9. ( )20,25,30 t ( )0.498138,-0.200313,-0.528845 t 23 *)
10. ( )78,96,120 t ( )0.500222,0.001023,-0.524215 t 146 *)
11. ( )100,100,100 t ( )NaN,NaN,NaN t 2 **)
12. ( )250,275,300 t ( )NaN,NaN,NaN t 6 **)
Keterangan:
*) Pada iterasi tertentu, matriks Jacobiannya akan dekat dengan matriks singular
**) Pada iterasi tertentu, matriks Jacobiannya akan menjadi matriks singular
Dengan menggunakan Tabel 3.3.1 di atas dapat dilihat bahwa dengan nilai
awal yang berbeda-beda, sistem persamaan non-linear apabila diselesaikan dengan
metode Newton akan memberikan hasil akhir yang berbeda. Untuk beberapa nilai
awal yang cukup dekat dengan penyelesaian yang sebenarnya (no.2-3 dan no.5-7)
akan konvergen ke suatu nilai yang sama yaitu ( )0.500014,0.001589,-0.523557 t
dengan iterasi yang relatif sedikit ( 30≤ ). Untuk nilai awal yang diberikan pada no.3
dan no.8-10 akan konvergen ke suatu nilai yang sama juga yaitu
( )0.500014,0.001589,-0.523557 t dengan iterasi yang relatif banyak ( 20≥ ). Keadaan
ini dikarenakan pada iterasi tertentu seperti pada no.8 ( )1 68− , no.9 ( )1 8− dan
62
no.10 ( )1 136− , matriks Jacobiannya akan dekat dengan matriks singular sehingga
perhitungannya pun akan cukup sulit dan kurang akurat. Sedangkan untuk nilai awal
yang diberikan pada no.11 dan no.12, sistem tidak akan memiliki penyelesaian yang
konvergen ke suatu nilai bahkan penyelesaian yang diberikan tidak terdefinisi.
Keadaan ini dikarenakan pada iterasi yang tertera pada tabel, matriks Jacobian yang
terbentuk akan menjadi matriks singular yang tidak mempunyai invers sehingga
syarat 1( ) 0− ≠J x tidak terpenuhi.
Dari sini, dapat ditarik suatu kesimpulan bahwa nilai awal akan sangat
mempengaruhi hasil akhir sistem, kekonvergenan sistem dan jumlah iterasi yang
diperlukan dalam menyelesaikan sistem persamaan non-linear. Nilai awal yang bagus
dan cukup dekat dengan penyelesaian yang sebenarnya akan membutuhkan iterasi
yang relatif sedikit untuk konvergen. Sedangkan untuk nilai awal yang cukup jauh
akan membutuhkan iterasi yang relatif banyak untuk konvergen bahkan ada nilai awal
yang akan membuat sistem tidak konvergen. Selain nilai awal, yang mempengaruhi
adalah syarat bahwa 1( ) 0− ≠J x haruslah terpenuhi.
D. KONVERGENSI METODE NEWTON
Teorema 3.4.1
Misalkan Asumsi 3.2.4 terpenuhi. Maka ada sebuah 0>K dan 0>δ sedemikian
sehingga jika )()( δΒ∈kx suatu iterasi Newton dari )(kx yang diberikan pada
persamaan )()( )(1)()()1( kkkk xFxFxx −+ ′−= memenuhi
63
2)()1( kk K ee ≤+ (3.4.1)
Bukti :
Pilih δ sedemikian sehingga Lemma 3.2.5 terpenuhi.
Berdasarkan Teorema 3.2.1
∫ +′′−=′−= −−+1
0
)()(1)()()(1)()()1( )*()()()( dtt kkkkkkkk eexFxFexFxFee
⎥⎦
⎤⎢⎣
⎡+′−′′= ∫−
1
0
)()()()(1)( )*()()( dtt kkkkk eexFexFxF
∫ +′−′′= −1
0
)()()(1)( ))*()(()( dtt kkkk eexFxFxF
Berdasarkan Lemma 3.2.5 dan karena F′ merupakan kontinu Lipschitz maka
∫ +′−′′= −+1
0
)()()(1)()1( ))*()(()( dtt kkkkk eexFxFxFe
∫ +′−′′= −1
0
)()()(1)( ))*()(()( dtt kkkk eexFxFxF
∫ +−′≤ −1
0
)()()(1 )*(*)(2 dtt kkk exxexF γ
∫∫ −′=−′= −−1
0
)()(11
0
)()()(1 )1(*)(2*)(2 dttdtt kkkkk eexFeeexF γγ
1
0
221
2)(11
0
2)(1 )(*)(2)1(*)(2 ttdtt kk −′=−′= −− ∫ exFexF γγ
64
2)(1
2)(1 *)(
2*)(2 k
k
exFe
xF −− ′=′= γγ
dengan mengambil 1*)( −′= xFγK maka 2)()1( kk K ee ≤+ .
■
Dengan menentukan δ sedemikian sehingga 1<δK maka δ≤+ )1(ke untuk setiap
)()1( δBk ∈+x
Teorema 3.4.2
Misalkan Asumsi 3.2.4 terpenuhi. Maka ada sebuah δ sedemikian sehingga jika
)()0( δΒ∈x , iterasi Newton
)()( )(1)()()1( kkkk xFxFxx −+ ′−=
konvergen q-kuadratik ke x*.
Bukti
Pilih δ sedemikian sehingga Teorema 3.4.1 terpenuhi dan 1<=ηδK . Jika 0≥k
dan )()( δΒ∈kx maka Teorema 3.4.1 menyatakan bahwa
)()()(2)()1( kkkkk KK eeeee ≤=≤≤+ ηδ (3.4.2)
65
Oleh karena itu )()()1( δηδ Β⊂Β∈+kx . Sehingga jika )()( δΒ∈kx maka iterasi dapat
dilanjutkan. Karena dari asumsi bahwa )()0( δΒ∈x maka seluruh barisan
{ } )()( δΒ⊂kx . Persamaan (3.4.2) menyatakan bahwa *)( xx →k q-kuadratik.
■
Contoh 3.4.1
Dengan menggunakan salah satu nilai awal dan penyelesaian yang didapatkan dari
penyelesaian sistem persamaan non-linear dengan metode Newton (lihat Tabel
3.3.1), akan dianalisis sifat-sifat konvergensinya. Menurut Teorema 3.4.2 bahwa
penyelesaian yang diberikan oleh metode Newton bersifat konvergen q-kuadratik
dengan relasi kesalahan ( 1) ( )k k+ ≤e e . Maka akan dibuktikan bahwa hasil
perhitungan yang diperoleh dari penyelesaian sistem persamaan non-linear dengan
metode Newton akan memenuhi teorema 3.4.2.
Diberikan (0) (6,8,5)t=x , 10N = , 0.01ε = yang memiliki penyelesaian
( )0.500047,0.005152,-0.523464 t=x . Berikut ini adalah hasil perhitungan dari setiap
iterasi dengan menggunakan metode Newton yang akan disajikan dalam Tabel 3.4.1
di bawah ini.
66
Tabel 3.4.1 Hasil Perhitungan dengan menggunakan Metode Newton
Iterasi ke- 1x 2x 3x
0. 6.000000 8.000000 5.000000
1. 15.706802 4.065097 -0.473599
2. 0.410482 1.636929 -0.473599
3. 0.488415 0.771338 -0.504950
4. 0.501551 0.341471 -0.514759
5. 0.501038 0.132117 -0.520160
6. 0.500331 0.037631 -0.522616
7. 0.500047 0.005152 -0.523464
8. 0.500047 0.005152 -0.523464
Akan dibuktikan bahwa hasil perhitungan yang didapat pada Tabel 3.4.1 bersifat q-
kuadratik dari hasil perhitungan berikut :
Metode Newton bersifat konvergen q-kuadratik bila memenuhi ( 1) ( )k k+ ≤e e .
( 1) ( 1) ( )k k k+ += −e x x dan ( ) ( 1)k k+= −e x x
(2) (2) (1)= −e x x
( ) ( )0.410482, 1.636929, -0.473599 15.706802, 4.065097, -0.473599t t= −
( )-15.2963, -2.4282, 0 15.4878t= =
(3) (3) (2)= −e x x
( ) ( )0.488415, 0.771338, -0.504950 0.410482, 1.636929, -0.473599t t= −
67
( )0.0779, -0.8656, -0.0314 0.8697t= =
Tabel 3.4.2 Perhitungan kesalahan pada iterasi ke-k
( )ke ( )ke
(2)e 15.4878
(3)e 0.8697
(4)e 0.4302
(6)e 0.0945
(7)e 0.0325
(8)e 0
Berdasarkan dari tabel 3.4.2 dapat dilihat bahwa (8) (7) (3) (2)≤ ≤ ≤ ≤e e e e… .
Dapat disimpulkan bahwa sistem persamaan non-linear ini mempunyai penyelesaian
yang konvergen q-quadratik.
E. METODE TURUN TERCURAM
Keuntungan dalam menggunakan metode Newton untuk menyelesaikan
sistem persamaan non-linear adalah bahwa iterasi akan cepat konvergen bila
pendekatan awal yang digunakan cukup baik. Akan tetapi, kelemahan dari metode ini
adalah pendekatan awal yang diberikan harus cukup akurat untuk dapat menjamin
konvergensinya. Metode Turun Tercuram dapat dipertimbangkan sebagai salah satu
68
metode penyelesaian sistem persamaan non-linear yang dapat mengatasi masalah
tersebut. Biasanya dengan menggunakan metode ini walaupun pendekatan awalnya
buruk tetapi akan tetap konvergen.
Metode Turun Tercuram termasuk salah satu metode yang populer dan sering
digunakan. Secara umum, metode ini merupakan metode untuk menentukan
minimum lokal dari fungsi multivariabel dengan bentuk : ng → .
Hubungan antara meminimumkan suatu fungsi dari n ke dan solusi suatu
sistem persamaan non-linear adalah misalkan terdapat sistem dengan bentuk
0),,,(
0),,,(0),,,(
21
212
211
=
==
nn
n
n
xxxf
xxxfxxxf
…
……
yang memiliki suatu penyelesaian di tnxxx ),,,( 21 …=x maka fungsi g yang
didefinisikan dengan
[ ]∑=
=n
inin xxxfxxxg
1
22121 ),,,(),,,( …… (3.5.1)
akan mempunyai nilai minimum nol.
Metode Turun Tercuram dalam mencari nilai minimum lokal untuk fungsi g
dari n ke yang berubah-ubah dapat digambarkan sebagai berikut :
i. Menaksir nilai g dengan pendekatan awal tnxxx ),,,( )0()0(
2)0(
1)0( …=x .
ii. Menentukan arah dari )0(x yang dapat mengurangi nilai g.
iii. Memindahkan jarak arah yang tepat dan memanggil vektor baru )1(x .
69
iv. Mengulangi langkah i sampai iii dan mengganti )0(x dengan )1(x
Perlu diingat kembali dalam kalkulus, Teorema Nilai Ekstrem hanya akan berlaku
apabila derivatif fungsinya bernilai nol.
Definisi 3.5.1
Jika : ng → maka gradien g di tnxxx ),,,( 21 …=x akan dinotasikan dengan
)(xg∇ dan didefinisikan sebagai berikut
t
nxg
xg
xgg ⎟⎟
⎠
⎞⎜⎜⎝
⎛∂∂
∂∂
∂∂
=∇ )(,),(),()(21
xxxx …
Gradien untuk fungsi multivariabel analog dengan derivatif untuk fungsi satu
variabel. Fungsi multivariabel yang differensiabel ini dapat memiliki minimum di x
hanya ketika gradiennya bernilai nol. Dalam hal ini, gradien akan berperan sebagai
arah untuk suatu perpindahan kecil yang diberikan dan nilai fungsi g akan meningkat
dalam arah gradien daripada sebarang arah lainnya.
Gradien memiliki hubungan lain yang cukup penting dengan minimum dari
fungsi multivariabel. Misalkan bahwa tnvvv ),,,( 21 …=v adalah vektor dalam n ,
sedemikian sehingga
11
22
2== ∑
=
n
iivv
70
Vektor d disebut sebagai arah turunan dari fungsi g di x jika ada 0>δ
sedemikian sehingga )()( xdx gg <+ λ untuk semua ),0( δλ ∈ .
Algoritma ini akan dimulai dengan menentukan 0>ε sebagai skalar akhir
dan memilih sebarang )0(x sebagai pendekatan awal. Iterasi akan berjalan mulai dari
0=k . Apabila 0)( =∇ xg berarti bahwa g sudah memiliki penyelesaian dan iterasi
akan berhenti. Akan tetapi bila tidak maka iterasi akan dilanjutkan kembali dengan
nilai x yang baru.
Misalkan )(kx adalah nilai x pada iterasi ke-k dan 0=k merupakan nilai
awal. Akan dipilih suatu arah turun d dan besar langkah 0>λ sedemikian sehingga
nilai baru dx λ+)(k yang akan membuat )()( )()( kk gg xdx <+ λ . Untuk mengetahui
λ yang akan dipilih, maka g akan dijabarkan dengan menggunakan deret Taylor
sebagai berikut :
)()()()( 2)()()( λλλ Oggg tkkk +∇+=+ dxxdx
gδ yang berubah-ubah dalam g akan diberikan sebagai
)()( )()( kk ggg xdx −+= λδ sehingga
)()( 2)( λλδ Ogg tk +∇= dx
Untuk λ yang cukup kecil, )( 2λO dapat dihilangkan. Akibatnya, akan
didapatkan
dx tkgg )( )(∇≅ λδ
71
Untuk membuat )()( )()( kk gg xdx <+ λ yang berarti bahwa 0<gδ , d
diperlukan sebagai arah turunan atau arah yang memenuhi
0)( )( <∇ dx tkg
Dengan demikian akan didapatkan,
)( )()( kk g xd −∇=
Berikut ini akan diberikan ilustrasi bila g adalah fungsi dengan dua variabel atau
peubah.
Gambar 3.5.1
Lemma 3.5.2
Misalkan : ng → fungsi yang memiliki diferensial di x dan misalkan bahwa
0)( ≠∇ xg . Penyelesaian optimal untuk masalah meminimumkan );( dxg ′ mengarah
72
kepada 1≤d yang diberikan kepada )(/)( xxd gg−∇= jika )(/)( xx gg∇−
adalah arah turun tercuram g di x.
Bukti
Derivatif berarah dari g di x dengan arah λ didefinisikan sebagai berikut
dxxdxxdx td ggggDg )()()(lim)();(
0∇=
−+==′
→ λλ
λ
Kemudian ditetapkan masalah mereduksi untuk meminimumkan dx tg )(∇ dengan
1≤d . Dari pertidaksamaan Schwatz, untuk 1≤d akan didapatkan
)()()( xdxdx ggg t ∇−≥∇−≥∇
Pertidaksamaan tersebut dapat dipenuhi jika dan hanya jika )(/)( xxdd gg−∇≡=
sehingga d adalah penyelesaian optimal dan bukti akan lengkap.
■
Karena g(x) akan direduksi sampai nilai minimumnya nol maka perbaikan nilai )(kx
adalah
)( )()()1( kkk g xxx ∇−=+ λ (3.5.2)
Sehingga nilai )( )()()1( kkk g xxx ∇−=+ λ merupakan perbaikan nilai dari )(kx
dalam mencari nilai minimum g.
73
Proporsisi 3.5.3
Jika { }∞=0)(
kkx adalah barisan turun tercuram untuk : ng → dan 0)( )( ≠∇ kg x
maka )()( )()1( kk gg xx <+
Bukti:
Perlu diingat kembali bahwa
)( )()()()()1( kkkkk g xxdxx ∇−=+=+ λλ
dengan 0)( ≥kλ yang membuat minimum fungsi
))(()( )()()( kkk gg xx ∇−= λλφ
untuk semua 0)( ≥kλ . Oleh karena itu untuk 0≥λ , akan didapatkan
)()( )()()( λφλφ kkk ≤
Berdasarkan aturan rantai,
0)()()))(0(()0()0(2)()()()(
)()( <∇−=∇∇−∇−== kktkk
kk gggg
dd xxxxλφφ
karena 0)( )( ≠∇ kg x dari asumsi. Kemudian, 0)0()( <′kφ dan berimplikasi dengan
ada 0>λ sedemikian sehingga )()0( )()( λφφ kk > untuk semua ( ]λλ ,0∈ .
Oleh karena itu
)()0()()()( )()()()()()1( kkkkkk gg xx =<≤=− φλφλφ
dan bukti dari pernyataan ini akan lengkap.
■
74
Berdasarkan proporsisi 3.5.3 dapat disimpulkan bahwa masalah dapat
direduksi menjadi menentukan λ sedemikian sehingga )( )1(xg akan kurang dari
)( )0(xg . Dalam menentukan pilihan tepat bagi nilai λ dapat dipertimbangkan
menjadi fungsi 1-variabel
))(()( )0()0( xx ggh ∇−= λλ (3.5.3)
Nilai λ yang dapat meminimumkan h merupakan nilai λ yang diperlukan dalam
persamaan (3.5.2).
Dalam mencari nilai minimum untuk fungsi h akan memerlukan diferensial
dari h dan kemudian menyelesaikan masalah mencari akar persamaan untuk
menentukan titik kritis dari h. Prosedur ini akan sangat merugikan. Dengan alasan
demikian, maka h akan diinterpolasikan dengan menggunakan polinomial kuadratik P
dan tiga nilai 321 ,, λλλ dengan harapan akan dekat dengan nilai minimum dari h.
Definisikan λ sebagai minimum mutlak P dalam interval tertutup paling
kecil yang memiliki 321 ,, λλλ dan menggunakan )(λP sebagai pendekatan nilai
miminum dari )(λh . Kemudian λ akan digunakan untuk menentukan iterasi baru
untuk pendekatan nilai minimum g.
)( )0()0()0( xxx g∇−= λ
75
Karena )( )0(xg sudah tersedia maka pertama akan dipilih 01 =λ untuk
meminimumkan perhitungan. Kemudian nilai 3λ ditentukan dengan )()( 13 λλ hh < .
Berdasarkan Quadratic Fit Line Search, akhirnya 2λ didapatkan dari 2/3λ .
Nilai minimum λ dari P dalam [ ]31 ,λλ terdapat salah satu hanya pada di
nilai kritis P atau di sisi kanan nilai akhir 3λ . Sebagai asumsinya,
)()()()( 1133 λλλλ PhhP =<= . Nilai kritis P dapat ditemukan karena P merupakan
polinomial kuadratik. Akan dibentuk suatu interpolasi )(λP dengan menggunakan
prinsip Interpolasi Kuadratik (Quadratic Interpolation). Diberikan tiga titik
),(dan ),(),,( 332211 ggg λλλ . Terdapat sebuah parabola yang melalui ketiga titik
tersebut. Persamaan parabola tersebut dapat ditulis dengan bentuk
))(()()( 213110 λλλλλλλ −−+−+= hhhP (3.5.4)
Akan dicari 310 dan , hhh yang memenuhi persamaan (3.5.4)
• untuk 01 == λλ
1 0 1 0 1 1( ) ( ) ( )P h g h g gλ λ λ= = → = =
• untuk 2λλ =
2 1 2 12 0 1 1 2 1
2 1 2
( ) ( )( ) ( ) ( ) g g g gP h h g h λ λλ λ λ λλ λ λ− −
= + − = → = =−
• untuk 3λλ =
3 0 1 1 3 1 2 3( ) ( ) ( )( ) ( )P h h h gλ λ λ λ λ λ λ λ= + − + − − =
76
23
23
23
232
3
12
13
12
12
23
23
3
)()(dengan ,
)()()()(
λλλλλλ
λ
λλλλλλ
λλλλ
−−
=−−
=−
=
−−−
−−−
=→
gggghhh
gggg
h
Sehingga,
)()( 2311 λλλλλ −++= hhgP
Titik kritis P, misalkan dinotasikan sebagai 0λ , dapat dicari dengan menggunakan
Teorema Nilai Ekstrem.
0dPdλ
=
1 3 2 32 0dP h h hd
λ λλ= − + =
Sehingga diperoleh
23132 λλ hhh −=−
3
231
2 hhh λ
λ−
=−
⎟⎟⎠
⎞⎜⎜⎝
⎛−=
3
125.0
hh
λλ
Dengan demikian, titik kritis dari P adalah ( )0 ( )g g gλ= − ∇x x . Sehingga terdapat
empat buah nilai λ dan ( ( ))g gλ− ∇x x . Metode Turun Tercuram merupakan salah
satu metode yang termasuk klasifikasi Metode Gradien. Metode Gradien adalah
metode yang meminimumkan suatu fungsi dengan cara mencari besar gradien yang
77
dibutuhkan agar nilai fungsi yang baru bernilai paling kecil. Dengan kata lain, iterasi
akan berlanjut dengan memilih λ pada himpunan { }30 ,λλ supaya nilai
( ( ))g gλ− ∇x x akan minimum diantara himpunan { }30 , gg . Nilai λ yang didapatkan
akan digunakan untuk mendapatkan nilai x yang baru dengan
)( )()()1( kkk g xxx ∇−=+ λ
Apabila ε<− 1gg maka iterasi akan berhenti. Akan tetapi apabila tidak maka
iterasi akan berulang lagi dari awal.
78
Flowchart dari Metode Turun Tercuram dalam menyelesaikan sistem
persamaan non-linear.
start
N ilai aw al (x )T o leransi (erro r)Iterasi m ax . (N )
k = 0
w hile k <= N
If z0=0 x
z = z / z0a 1 = 0a 3 = 1
g3 = g_baru_3(x ,a 3 ,z)
a
ya
tidak
g1= g_aw al(x )z= grad(x )
z0= norm (z)
w hile g3 >= g1
end
a 3 = a 3 / 2g3 = g_baru_3(x ,a 3 ,z)
b
tidak
ya
79
Gambar 3.5.2
a
If a3 < error/2a2 = a3/2
g2 = g_baru_2(x,a2,z)
h1 = (g2-g1)/a2h2 = (g3-g2)/(a3-a2)
h3 = (h2-h1)/a3
a0 = 0.5(a2-h1/h3)g0 = g_baru(x,a0,z)
g = min(g0,g3)
x = x-az
If abs(g-g1) < error x end
k = k+1
end
ya
tidak
b
tidak ya x
80
Contoh 3.5.1
Carilah penyelesaian sistem persamaan non-linear dengan menggunakan metode
Turun Tercuram.
1 2
11 1 2 3 1 2 3 2
2 22 1 2 3 1 2 3
10 33 1 2 3 3 3
( , , ) 3 cos( ) 0
( , , ) 81( 0.1) sin 1.06 0
( , , ) 20 0x x
f x x x x x x
f x x x x x x
f x x x e x π− −
= − − =
= − + + + =
= + + =
Penyelesaian
Dengan pendekatan awal ( )(0) 0,0,0 t=x , toleransi 25 10ε −= × dan 10N =
Misalkan [ ] [ ] [ ]2 2 21 2 3 1 1 2 3 2 1 2 3 3 1 2 3( , , ) ( , , ) ( , , ) ( , , )g x x x f x x x f x x x f x x x= + + , maka
31 21 2 3
1 1 1
31 21 2 3 1 2 3
2 2 2
31 21 2 3
3 3 3
2 ( ) ( ) 2 ( ) ( ) 2 ( ) ( ),
( , , ) 2 ( ) ( ) 2 ( ) ( ) 2 ( ) ( ),
2 ( ) ( ) 2 ( ) ( ) 2 ( ) ( )
tff ff f f
x x xff fg x x x f f f
x x xff ff f f
x x x
⎛ ⎞∂∂ ∂+ +⎜ ⎟∂ ∂ ∂⎜ ⎟
⎜ ⎟∂∂ ∂∇ = + +⎜ ⎟
∂ ∂ ∂⎜ ⎟⎜ ⎟∂∂ ∂
+ +⎜ ⎟⎜ ⎟∂ ∂ ∂⎝ ⎠
x x x x x x
x x x x x x
x x x x x x
2 ( ) ' ( )= J x F x
Untuk ( )(0) 0,0,0 t=x , akan didapatkan
( )(0) 111.9748g =x , 0 2419.5538z = =z
Untuk 1 0α = 1 111.975g =
2 0.5α = 2 2.5357g = , 1 218.878h = −
3 1α = 3 93.5649g = 2 182.059h = 3 400.937h =
81
sehingga ( ) ( )111.975 218.878 400.937 0.5P α α α α= − + − . Oleh karena itu,
0 0.522959α = , 0 2.32762g =
Kemudian, 0 0.522959α = ,
(1) (0) (0.0112182,0.0111964, 0.522741)tα= − = −x x z
dan (1)( ) 2.32762g =x
Hasil penyelesaian dengan metode Turun Tercuram untuk iterasi selanjutnya
----------------------------------------------------------------------------
k | x1 | x2 | x3 | g(x)
----------------------------------------------------------------------------
1 0.0112 0.0101 -0.5227 111.9748
2 0.1379 -0.2055 -0.5221 2.3276
3 0.2670 0.0055 -0.5585 1.2741
4 0.2727 -0.0081 -0.5220 1.0681
5 0.3295 -0.0275 -0.5395 0.4683
6 0.3360 -0.0154 -0.5115 0.4100
7 0.3360 -0.0154 -0.5115 0.3142
Berikut ini akan diberikan tabel perbandingan pengaruh nilai awal dengan hasil akhir
dan jumlah iterasi yang diperlukan dalam metode Turun Tercuram. Akan digunakan
toleransi 210ε −=
82
Tabel 3.5.1 Pengaruh nilai awal pada Metode Turun Tercuram
No. Nilai Awal ( (0)x ) Penyelesaian ( ( )kx ) Iterasi
1. ( )0.1,0.1, 0.1 t− ( )0.421764,-0.005186,-0.520248 t 27
2. ( )5, 3, 1 t− − − ( )-1.736315,-0.332644,-0.522844 t 70
3. ( )9, 12, 4 t− − − ( )0.422740,-0.005132,-0.520248 t 398
4. ( )20, 30, 40 t− − − ( )-18.390576,-2.158388,-1.593550 t 500
5. ( )2,3,4 t ( )0.576013,-0.204810,-0.533606 t 36
6. ( )5,5,5 t ( )0.578528,-0.204851,-0.526207 t 91
7. ( )6,8,5 t ( )3.419360,0.296436,-0.490472 145
8. (9,7,5)t ( )3.375527,0.291598,-0.491060 t 308
9. ( )10,10,10 t ( )3.399235,0.294131,-0.490740 t 371
10. ( )20,25,30 t ( )18.643130,1.960350,0.370337 t 500
11. ( )78,96,120 t ( )79.352378,8.688564,72.737394 t 500
12. ( )100,100,100 t ( )102.171461,11.280871,90.699988 t 500
Berikut ini akan diberikan tabel perbandingan pengaruh nilai awal yang diberikan
oleh Metode Turun Tercuram yang diperoleh dari tabel 3.5.1 terhadap penyelesaian
akhir dan jumlah iterasi dengan menggunakan Metode Newton untuk menyelesaikan
sistem persamaan non-linear
83
Tabel 3.5.2 Pengaruh nilai akhir Metode Turun Tercuram terhadap Metode Newton
No. Nilai Akhir MTT ( (0)x ) Penyelesaian MN ( ( )kx ) Iterasi
1. ( )0.421764,-0.005186,-0.520248 t ( )0.500001,-0.000258,-0.523624 t 2
2. ( )-1.736315,-0.332644,-0.522844 t ( )0.498065,-0.208387,-0.529055 t 7
3. ( )0.422740,-0.005132,-0.520248 t ( )0.500001,-0.000251,-0.523624 t 2
4. ( )-18.390576,-2.158388,-1.593550 t ( )0.498135,-0.200712,-0.528855 t 9
5. ( )0.576013,-0.204810,-0.533606 t ( )0.498153,-0.199380,-0.528786 t 2
6. ( )0.578528,-0.204851,-0.526207 t ( )0.498150,-0.199359,-0.528784 t 2
7. ( )3.419360,0.296436,-0.490472 ( )0.500028,0.002968,-0.523516 t 3
8. ( )3.375527,0.291598,-0.491060 t ( )0.500028,0.002942,-0.523517 t 3
9. ( )3.399235,0.294131,-0.490740 t ( )0.500028,0.002978,-0.523516 t 3
10. ( )18.643130,1.960350,0.370337 t ( )0.500008,0.000909,-0.523575 t 4
11. ( )79.352378,8.688564,72.737394 t ( )0.500059,0.006573,-0.523427 t 6
12. ( )102.171461,11.280871,90.699988 t
( )0.500006,0.000612,-0.523583 t 7
Dengan menggunakan tabel 3.5.1 di atas, dapat diketahui bahwa nilai awal
tidaklah terlalu berpengaruh terhadap sistem dan metode. Untuk nilai awal yang
dekat dengan penyelesaian sebenarnya akan konvergen ke suatu nilai yaitu
( )0.500014,0.001589,-0.523557 t dengan iterasi yang cukup banyak juga. Bila
dibandingkan dengan metode Newton maka untuk nilai awal yang bisa dikatakan
84
cukup dekat dengan penyelesaian sebenarnya, metode Newton lebih menguntungkan
karena iterasi yang dibutuhkan untuk konvergen lebih sedikit dibandingkan dengan
metode Turun Tercuram Sedangkan untuk nilai awal yang cukup jauh, nilai akhir
tidak konvergen ke suatu nilai yang sama. Hasil penyelesaiannya akan berbeda-beda
dan iterasi yang dibutuhkan untuk mendapatkan hasil akhir juga relatif banyak. Akan
tetapi, nilai akhir yang didapatkan dari metode Turun Tercuram dapat menjadi nilai
awal yang cukup layak bagi metode Newton untuk menyelesaikan sistem persamaan
non-linear.
Dapat dilihat kembali tabel 3.5.2 yang memperlihatkan bahwa nilai awal yang
dekat ataupun yang jauh dari penyelesaian yang sebenarnya akan konvergen ke suatu
nilai yang sama yaitu ( )0.500014,0.001589,-0.523557 t dengan jumlah iterasi yang
relatif sedikit ( 16≤ ). Apabila dibandingkan dengan tabel 3.3.1, untuk nilai awal
(no.12) yang dengan metode Newton tidak memiliki penyelesaian dikarenakan
matriks Jacobiannya singular maka dengan nilai awal yang sudah diperbaiki oleh
metode Turun Tercuram, akan konvergen ke suatu nilai yang cukup dekat dengan
penyelesaian sebenarnya. Sehingga untuk nilai awal yang cukup jauh dari
penyelesaiannya, metode Turun Tercuram ini akan sangat membantu mengatasi
kelemahan metode Newton.
85
F. Konvergensi Metode Turun Tercuram
Asumsi 3.6.1
1. Nilai fungsi mempunyai batas bawah nol.
( ) 0 , ng = ∀ ∈x x
2. ( )(xg∇ merupakan kontinu Lipschitz) Fungsi g merupakan diferensiable yang
kontinu, yaitu ada sebuah konstanta K yang sedemikian sehingga
22)()( yxyx −≤∇−∇ Kgg
Lemma 3.6.2 ( Lemma Descent )
Jika g memenuhi kondisi Lipschitz dalam asumsi 3.6.1 (b) maka
2
22)()()( yKggg t +∇+≤+ xyxyx
Bukti :
Bukti lemma 3.6.2 bisa dilihat pada buku karangan Bertsekas, Dimitri P., Tsitsiklis,
John N. (1989). Parallel and Distributed Computation: Numerical Methods. Upper
Saddle River : Prentice Hall.
http://dspace.mit.edu/handle/1721.1/3719 (7 Oktober 2007, 07:15 AM)
Proporsisi 3.6.3 ( Konvergensi Algoritma Descent )
Misalkan asumsi 3.6.1 dipenuhi dan K1 dan K2 adalah konstanta positive. Barisan
{ })(kx yang dibangkitkan oleh algoritma dengan bentuk
86
( 1) ( ) ( )k k kλ+ = +x x d
dengan ( )kd memenuhi
( ) ( )12 2
( ) ,k kK g k≥ ∇ ∀d x (3.6.1)
dan
2( ) ( ) ( )2 2
( ) ,k t k kg K k∇ ≤ − ∀d x d (3.6.2)
Jika KK /20 2<< λ maka
0)(lim )( =∇∞→
k
kg x
Bukti
Dengan menggunakan Lemma Descent dan asumsi 3.6.1 akan didapatkan
2( 1) ( ) ( ) ( ) 2 ( )
2( ) ( ) ( )
2k k k t k kKg g gλ λ+ ≤ + ∇ +x x d x d
2( ) ( )
2 2( )
2k kKg K λλ ⎛ ⎞≤ − −⎜ ⎟
⎝ ⎠x d
Misalkan )2/( 2 λλβ KK −= dengan asumsi λ positif. Dari pertidaksamaan dan
kondisi nonnegatif dari asumsi 3.6.1 (a) akan didapatkan
2( 1) (0) ( )
20
0 ( ) (k
kg g τ
τ
β+
=
≤ ≤ − ∑x x d
Karena pertidaksamaan ini berlaku untuk semua k maka
2( ) (0)
20
1 ( )gτ
τ β
∞
=
≤ < ∞∑ d x
87
( )lim 0k
k→∞=d dan persamaan (3.6.1) menunjukkan bahwa 0)(lim )( =∇
∞→
k
kg x
■
Teorema 3.6.4
Misalkan asumsi 3.6.1 dipenuhi dan Lemma Descent juga berlaku. Berdasarkan atas
Konvergensi Algoritma Descent dengan 121 == KK dan Algoritma Gradien yang
diberikan
( 1) ( ) ( )k k kλ+ = +x x d
dengan )(ks
( ) ( )
2 2( ) ,k kg k≥ ∇ ∀d x (3.6.3)
2( ) ( ) ( )
2( )k t ki kg∇ ≤ −d x d (3.6.4)
Jika K20 << λ maka 0)(lim )( =∇
∞→
k
kg x
Bukti
Dari pertidaksamaan 3.6.4 dan Lemma Descent maka
2( 1) ( ) ( ) ( ) 2 ( )
2( ) ( ) ( )
2k k k t k kKg g gλ λ+ ≤ + ∇ +x x d x d
2( ) ( )
2( ) 1
2k kKg λλ ⎛ ⎞≤ − −⎜ ⎟
⎝ ⎠x d
88
Kemudian akan didapatkan pertidaksamaan untuk setiap k jika jumlah total untuk
semua 0>k , setelah itu
2( 1) (0) ( )
20
0 ( ) ( ) 12
kk Kg g τ
τ
λλ+
=
⎛ ⎞≤ ≤ − −⎜ ⎟⎝ ⎠
∑x x d
Akan didapatkan bahwa pertidaksamaan bernilai benar untuk semua k, sedemikian
sehingga
2( ) (0)
20
1 ( )1
2
gK
τ
τ λλ
∞
=
≤ < ∞⎛ ⎞−⎜ ⎟⎝ ⎠
∑ d x
Dapat dilihat bahwa pangkat untuk sisi kanan – sisi kiri terbatas, sehingga
( )lim 0t
k→∞=d
Yang berimplikasi dengan
0)(lim )( =∇∞→
k
kg x
■
Karakterisitik Konvergensi dari Metode Turun Tercuram
Metode Turun Tercuram akan bekerja cukup baik selama iterasinya akan
dekat dengan titik stasioner dan akan mendekati langkah ortogonal. Zigzaging terjadi
di sepanjang lembah yang ditunjukkan dengan garis titik-titik seperti pada gambar
3.6.1.
89
Gambar 3.6.1
Metode Turun Tercuram dalam mencapai nilai optimumnya akan
mempunyai arah gerak zigzag. Ini dikarenakan setiap iterasi sebelumnya ortogonal
dengan iterasi selanjutnya. Pernyataan tersebut didasarkan bahwa λ diperoleh
dengan meminimumkan ( ) ( )( )k kg λ+x d sehingga ( ){ }( ) ( ) 0k kd gd
λλ
+ =x d dengan
( )kλ λ= . Dengan diferensiasi akan didapatkan ( )( ) ( ) ( ) 0tk k kg λ∇ + =x d d . Karena
( )( 1)kg += −∇d x akan didapatkan hasil ( 1) ( ). 0k k+ =d d .
Proporsisi 3.6.5
Jika { }∞=0)(
kkx adalah barisan turun tercuram untuk fungsi yang diberikan : ng →
maka untuk setiap k vektor )()1( kk xx −+ adalah ortogonal dengan vektor
)1()2( ++ − kk xx .
90
Bukti:
Dari bentuk iterasi metode turun tercuram akan didapatkan
)(),(, )1()()1()()1()2()()1( +++++ ∇∇=−− kkkkkkkk gg xxxxxx λλ
Untuk melengkapi bukti cukup ditunjukkan bahwa
0)(),( )1()( =∇∇ +kk gg xx
Kemudian akan diperlihatkan bahwa )(kλ merupakan skalar tidak negatif yang
meminimumkan ))(()()( )()()()()( kkkkk ggg xxdx ∇−=+= λλλφ .
Oleh sebab itu, dengan menggunakan aturan rantai 0)( )()( =′ kk λφ akan didapatkan
)()( )()(
)()( kk
kk
dd λλφλφ =
′
))(())((0 )()()()( ktkkk ggg xxx −∇∇−∇= λ
)(),(0 )()1( kk gg xx ∇∇−= +
■
Contoh 3.6.1 Dengan menggunakan salah satu nilai awal dan penyelesaian yang didapatkan dari
penyelesaian sistem persamaan non-linear dengan metode Turun Tercuram (lihat
Tabel 3.5.1), akan dianalisis sifat-sifat konvergensinya. Menurut teorema 3.6.4 bahwa
metode Turun Tercuram mempunyai konvergen bila ( )lim ( ) 0k
kg
→∞∇ =x dan menurut
proporsisi 3.6.5 bahwa vektor-vektor penyelesaiannya akan ortogonal, maka akan
91
dibuktikan bahwa hasil perhitungan yang diperoleh dari penyelesaian sistem
persamaan non-linear dengan metode Turun Tercuram akan konvergen dan vektor-
vektor penyelesaiannya ortogonal.
Diberikan (0) (5,5,5)t=x , 100N = , 0.01ε = yang memiliki penyelesaian
( )0.578528, -0.204851, -0.526207 t=x . Berikut ini adalah hasil perhitungan dari
setiap iterasi dengan menggunakan metode Turun Tercuram yang akan disajikan
dalam Tabel 3.6.1 di bawah ini.
Tabel 3.6.1 Hasil perhitungan dengan metode Turun Tercuram
Iterasi ke-k 1x 2x 3x
0. 5.000000 5.000000 5.000000
1. 5.024567 2.966354 4.998120
2. 5.051793 1.611924 4.990655
3. 5.087377 0.613226 4.954122
89. 0.585583 -0.204980 -0.517213
90. 0.582978 -0.205237 -0.532617
91. 0.578528 -0.204851 -0.526207
( ) ( )(1) 5.024567, 2.966354, 4.998120 tg g∇ = ∇x
( )5 5 5-0.1471 10 ,7.3159 10 , 0.0403 10t
= × × ×
( ) ( )(1) 5 5 5lim lim -0.1471 10 ,7.3159 10 , 0.0403 10t
k kg
→∞ →∞∇ = × × ×x
92
( )5 5 5-0.1471 10 ,7.3159 10 , 0.0403 10t
= × × ×
( ) ( )(2) 5.051793, 1.611924, 4.990655 tg g∇ = ∇x
( )5 5 5-0.0419 10 , 1.1760 10 , 0.0430 10t
= × × ×
( ) ( )(2) 5 5 5lim lim -0.0419 10 , 1.1760 10 , 0.0430 10t
k kg
→∞ →∞∇ = × × ×x
( )5 5 5-0.0419 10 , 1.1760 10 , 0.0430 10t
= × × ×
Tabel 3.6.2 Perhitungan gradien pada iterasi ke-k
( )kx ( )( )kg∇ x ( )lim ( )k
kg
→∞∇ x
(1)x ( )5 5 5-0.1471 10 ,7.3159 10 , 0.0403 10t
× × × ( )5 5 5-0.1471 10 ,7.3159 10 , 0.0403 10t
× × ×
(2)x ( )5 5 5-0.0419 10 , 1.1760 10 , 0.0430 10t
× × × ( )5 5 5-0.0419 10 , 1.1760 10 , 0.0430 10t
× × ×
(3)x ( )3 3 3-0.2213 10 ,3.4876 10 , 4.3386 10t
× × × ( )3 3 3-0.2213 10 ,3.4876 10 ,4.3386 10t
× × ×
(89)x ( )1.7291, 0.1704, 10.2260 t ( )1.7291, 0.1704, 10.2260 t
(90)x ( ) 1.4931, -0.1297, -2.1506 t ( )1.4931, -0.1297, -2.1506 t
(91)x ( )1.4800, 0.0176, 8.0280 t ( )1.4800, 0.0176, 8.0280 t
93
( ) ( )(1) (2),g g∇ ∇x x
( ) ( )5 5 5 5 5 5-0.1471 10 ,7.3159 10 , 0.0403 10 , -0.0419 10 , 1.1760 10 , 0.0430 10t t
= × × × × × ×
108.6117 10= ×
Tabel 3.6.3 Perhitungan hasil kali dalam vektor-vektor penyelesaian
( ) ( )(1) (2),g g∇ ∇x x 108.6117 10×
( ) ( )(2) (3),g g∇ ∇x x 84.2975 10×
( ) ( )(89) (90),g g∇ ∇x x -19.4319
( ) ( )(90) (91),g g∇ ∇x x -15.0572
Berdasarkan tabel 3.6.2, dapat disimpulkan bahwa sistem persamaan non-linear ini
apabila diselesaikan dengan metode Turun Tercuram dapat memiliki penyelesaian
yang konvergen tetapi hasil penyelesaian yang terdapat pada tabel 3.6.1 belum hasil
yang maksimal karena nilai ( )lim ( )k
kg
→∞∇ x mendekati dengan nol. Apabila sistem
dikerjakan dengan toleransi kesalahan ε yang lebih kecil, sistem dapat memiliki
penyelesaian yang konvergen ke penyelesaian yang sebenarnya. Selain itu,
berdasarkan tabel 3.6.3, langkah dari metode ini belum mendekati langkah ortogonal
94
dikarenakan penyelesaian yang ada belum cukup dekat dengan titik stasioner yang
merupakan penyelesaian yang sebenarnya.
BAB IV
TERAPAN METODE NEWTON DAN METODE TURUN TERCURAM
DALAM MENGHITUNG KONSENTRASI UNSUR DALAM SUATU
SAMPEL
Dalam Bab IV ini akan dibahas mengenai penerapan metode Newton dan
metode Turun Tercuram dalam bidang fisika, yaitu untuk mengetahui konsentrasi
unsur dalam suatu sampel dengan metode penyerapan cahaya.
A. Metode Penyerapan Cahaya
Bila cahaya dengan intensitas 0I datang menuju sampel, setelah mengalami
penyerapan intensitasnya akan berkurang menjadi I . Dari kedua nilai tersebut dapat
diperoleh nilai absorban A seperti dalam persamaan (4.1.1) [Harris, 1999].
0log IAI
= (4.1.1)
Sesuai dengan hukum Beer-Lambert, besarnya penyerapan tergantung pada
konsentrasi penyerap, panjang lintasan interaksi cahaya dan penyerap, serta jenis
penyerapnya [Brehm dan Mullin, 1989; Desember, 1996]. Karena persamaan (4.1.1)
dapat dinyatakan dalam persamaan (4.1.2)
A b cε= (4.1.2)
dengan ε : absorptivitas molar
b : panjang lintasan interaksi cahaya dan sampel
96
c : konsentrasi
Nilai absorptivitas molar ini tergantung pada jenis penyerap dan panjang
gelombang cahaya yang digunakan. Untuk cahaya dengan panjang gelombang i,
persamaan (4.1.2) akan menjadi
i iA b cε= (4.1.3)
Bila sampel memiliki n buah komponen, masing-masing komponen ke-j akan
memberikan sumbangan absorban seperti pada persamaan (4.1.3), sehingga absorban
totalnya akan mengikuti persamaan (4.1.4) di bawah.
1
n
T i i jj
A A=
= ∑ (4.1.4)
atau
1
n
T i i j jj
A bcε=
=∑ (4.1.5)
Persamaan (4.1.5) dapat dinyatakan dalam bentuk persamaan (4.1.6)
1
n
T i i j jj
A f c=
=∑ (4.1.6)
dengan
i j i jf bε= (4.1.7)
Untuk mengukur konsentrasi n buah komponen dilakukan pengukuran absorban pada
n buah panjang gelombang yang berbeda. Sehingga akan diperoleh sistem persamaan
seperti pada persamaan (4.1.8)
97
1 11
2 21
1
n
j jj
n
j jj
n
n n jj
A f c
A f
A f
=
=
=
=
=
=
∑
∑
∑ j
c
c
(4.1.8)
Untuk setiap komponen sampel ke-j, hubungan antara absorban dan
konsentrasi dapat diperoleh dengan kalibrasi melalui pengukuran pada panjang
gelombang ke-i, dari komponen sampel ke-j yang sudah diketahui konsentrasinya.
Selanjutnya dengan menggunakan persamaan (4.1.8), nilai konsentrasi dari n buah
komponen dalam suatu sampel dapat ditentukan dengan mengukur absorban dari
sampel pada n buah panjang gelombang yang berbeda. Penyelesaian sistem
persamaan (4.1.8) tergantung pada hubungan antara absorban dan konsentrasi. Bila
diperoleh hubungan yang non-linear, maka sistem persamaannya juga non-linear
yang dapat diselesaikan secara numerik dengan berbagai metode.
B. Terapan Metode Newton dan Metode Turun Tercuram untuk menghitung
Konsentrasi Unsur
Dalam penerapan metode Newton dan metode Turun Tercuram ini, data-data
yang digunakan untuk membentuk sistem persamaan non-linear diperoleh dari
eksperimen yang telah dilakukan oleh rekan-rekan dari Program Studi Fisika, yaitu
mengukur konsentrasi larutan yang terdiri dari parasetamol dan kafein. Diasumsikan
98
bahwa untuk parasetamol dan kafein didapatkan hubungan antara absorban A
terhadap konsentrasi c mengikuti hubungan polinomial sebagai berikut :
20 1 2 3
3A a a c a c a c= + + + (4.2.1)
Konstanta pada persamaan (4.2.1) yang diperoleh dari data kalibrasi yang
disajikan pada Tabel 4.2.1 di bawah ini:
0 1 2 3, , ,a a a a
Tabel 4.2.1 Koefisien polinomial 2 30 1 2 3A a a c a c a c= + + +
Hubungan antara absorban dan konsentrasi dari parasetamol dan kafein untuk
berbagai panjang gelombang (lambda)
Komponen Lambda
(nm) 0a 1a 2a 3a
272,2 1,83E-3 1,44E-4 -4,99E-8 0 Parasetamol
249,1 5,38E-3 6,53E-5 0 0
272,2 -3,73E-4 -9,62E-8 -9,62E-8 3,49E-11 Kafein
249,1 1,09E-3 4,36E-5 -2,48E-8 0
Tabel 4.2.2 Hasil pengukuran absorban dari satu sampel yang
mengandung 500 ppm parasetamol dan 500 mg kafein.
No. Lambda (nm) Absorban
1. 272,2 0,073
2. 249,1 0,054
99
Misalkan 1x adalah variabel untuk konsentrasi parasetamol, dan 2x adalah
variabel untuk konsentrasi kafein. Kemudian dari data di atas pada panjang
gelombang 272,2 nm, 249,1 nm dapat diperoleh sistem persamaan non-linear dengan
dua variabel sebagai berikut :
3 4 8 2 4 5 8 2
1 1 2 21.83 10 1.44 10 4.99 10 3.73 10 8.95 10 9.62 10 0.073x x x x− − − − − −× + × − × − × + × − × =
3 5 3 5 8 21 25.38 10 6.53 10 1.09 10 4.36 10 2.48 10 0.054x x− − − − −× + × + × + × − × =2x
(4.2.2)
Sistem persamaan tersebut kemudian digunakan untuk menentukan
konsentrasi parasetamol dan kafein pada suatu campuran yang mengandung
keduanya. Dengan menggunakan konsentrasi awal 500 ppm parasetamol dan 500
ppm kafein, maka sistem (4.2.2) dapat diselesaikan secara numerik dengan metode
Newton dan metode Turun Tercuram.
Sistem persamaan (4.2.2) apabila diselesaikan secara numerik dengan
mengggunakan metode Newton dapat diperoleh hasil sebagai berikut :
Tabel 4.2.3 Hasil Perhitungan Konsentrasi Parasetamol dan Kafein antara
panjang gelombang 272,2 nm dengan 249,1 nm
Konsentrasi No.
Iterasi Parasetamol 1( )x Kafein 2( )x
0 500.000000 500.000000
100
1 423.843759 726.223539
2 449.335171 674.055561
3 450.905444 670.608507
4 450.912307 670.593663
5 450.912307 670.593663
Sistem persamaan (4.2.2) apabila diselesaikan secara numerik dengan
mengggunakan metode Turun Tercuram dapat diperoleh hasil sebagai berikut :
Tabel 4.2.4 Hasil Perhitungan Konsentrasi Parasetamol dan Kafein antara
panjang gelombang 272,2 nm dengan 249,1 nm
Konsentrasi No.
Iterasi Parasetamol 1( )x Kafein 2( )x
0 500.000000 500.000000
1 429.000257 503.667811
2 439.844950 515.576743
3 428.301140 526.854819
37 450.236144 668.645748
38 450.530737 668.740995
39 450.404301 669.131891
101
Berikut ini akan diberikan tabel perbandingan hasil perhitungan konsentrasi
parasetamol dan kafein yang diselesaikan dengan menggunakan metode Newton dan
metode Turun Tercuram.
Tabel 4.2.5 Tabel Perbandingan Perhitungan Konsentrasi dengan menggunakan
Metode Newton dan Metode Turun Tercuram
Metode Newton Metode Turun Tercuram
Konsentrasi Konsentrasi Lambda
Parasetamol Kafein Iterasi
Parasetamol Kafein Iterasi
272,2 dan
249,1 nm 450.912307 670.593663 5 450.404301 669.131891 39
C. Analisis Perhitungan Konsentrasi Umur dengan Metode Newton dan Metode
Turun Tercuram
Dalam subbab ini akan dianalisis tentang penyelesaian sistem persamaan non-
linear dengan menggunakan metode Newton dan metode Turun Tercuram. Analisis
secara lengkap dari perhitungan konsentrasi unsur dengan metode Newton dan
metode Turun Tercuram, antara lain :
1. Analisis sifat konvergensi pada hasil
Dengan menggunakan hasil yang diperoleh dari penyelesaian sistem
persamaan dengan metode Newton dan metode Turun Tercuram akan dianalisis sifat-
sifat konvergensinya.
102
a. Metode Newton
Sesuai dengan teori dari metode Newton yang mempunyai sifat konvergensi
q-kuadratik, maka akan dibuktikan bahwa hasil yang diperoleh dari penyelesaian
sistem persamaan non-linear dengan metode Newton bersifat q-kuadratik. Bukti
dapat dilihat dari hasil perhitungan berikut :
(2) (2) (1)= −e x x
( ) ( )449.335171, 674.055561 423.843759, 726.223539t t= −
( )25.4914, -52.1680 58.0630t= =
Tabel 4.3.1 Perhitungan kesalahan pada iterasi ke-k
( )ke ( )ke
(2)e 58.0630 (3)e 3.7879 (4)e 0.0164 (5)e 0
Berdasarkan dari tabel 4.3.1 dapat dilihat bahwa (5) (4) (3) (2)≤ ≤ ≤e e e e
Dengan menggunakan teorema 3.4.2 dapat disimpulkan bahwa sistem persamaan
non-linear di atas mempunyai sifat konvergen q-kuadratik. Sehingga menurut
teorema 3.3.4, bahwa metode Newton akan konvergen kuadratik ke suatu nilai p
103
yang merupakan penyelesaian dari sistem. Dalam hal ini, untuk sistem (4.2.2)
akan konvergen ke ( ) . 450.912307, 670.593663 t
b. Metode Turun Tercuram
Menurut Teorema 3.6.4 dalam membuktikan konvergensi metode Turun
Tercuram cukup membuktikan ( )( )lim 0k
kg
→∞∇ =x dan berdasarkan proporsisi 3.6.5
vektor-vektor dalam setiap iterasinya akan ortogonal. Maka akan dibuktikan
bahwa hasil yang diperoleh dari penyelesaian sistem persamaan dengan metode
Turun Tercuram akan konvergen dan vektornya saling ortogonal.
( ) ( )(1) 429.000257, 503.667811 tg g∇ =∇x ( )-6 -6-0.1537 10 , -0.1688 10t
= × ×
( ) ( )(1) -6 -6lim lim -0.1537 10 , -0.1688 10t
k kg
→∞ →∞∇ = × ×x
( )-6 -6-0.1537 10 , -0.1688 10t
= × × 0≈
Tabel 4.3.2 Perhitungan gradien pada iterasi ke-k
( )kx ( )( )kg∇ x ( )lim ( )k
kg
→∞∇ x
(1)x ( )-6 -6-0.1537 10 , -0.1688 10t
× × 0
(2)x ( )-6 -60.1617 10 , -0.1579 10t
× × 0
(3)x ( )-6 -6-0.1644 10 , -0.1553 10t
× × 0
104
(37)x ( )-8 -8-0.6495 10 , -0.2100 10t
× × 0
(38)x ( )-8 -80.1187 10 , -0.3671 10t
× × 0
(39)x ( )-8 -8-0.4874 10 , -0.1576 10t
× × 0
( ) ( )(1) (2),g g∇ ∇x x
( ) ( )-6 -6 -6 -6-0.1537 10 , -0.1688 10 , 0.1617 10 ,-0.1579 10t t
= × × × ×
-15-2.0417 10 0= × ≈
Tabel 4.3.3 Perhitungan hasil kali dalam vektor-vektor penyelesaian
( ) ( )(1) (2),g g∇ ∇x x 0
( ) ( )(2) (3),g g∇ ∇x x 0
( ) ( )(37) (38),g g∇ ∇x x 0
( ) ( )(38) (39),g g∇ ∇x x 0
Dengan menggunakan teorema 3.6.4 dan proporsisi 3.6.5, maka dapat
disimpulkan bahwa sistem persamaan non-linear konvergen dan vektor-vektor
105
penyelesaiannya akan ortogonal. Dalam hal ini, sistem (4.2.2) akan konvergen ke
. ( )450.404301, 669.131891 t
2. Pengaruh nilai awal terhadap hasil
Sistem persamaan non-linear pada panjang gelombang 272,2 nm dengan
249,1 nm mula-mula diselesaikan dengan metode Newton dan metode Turun
Tercuram dengan nilai awal . Pada sistem persamaan (4.2.2),
dengan metode Newton akan didapatkan penyelesaian
((0) 500,500 t=x )
( )450.912307, 670.593663 t
yang konvergen q-kuadratik sedangkan dengan metode Turun Tercuram akan
didapatkan penyelesaian yang hasilnya mendekati penyelesaian dengan metode
Newton yaitu ( yang konvergen dan vektor-vektor
penyelesaiannya ortogonal. ortogonal. Kemudian sistem persamaan non-linear
tersebut dicoba diselesaikan menggunakan metode Newton dan metode Turun
Tercuram dengan nilai awal yang berbeda-beda, sehingga diperoleh hasil yang akan
disajikan dalam tabel-tabel di bawah ini.
)450.404301, 669.131891 t
106
Tabel 4.3.4 Hasil Perhitungan Konsentrasi Parasetamol dan Kafein pada panjang
gelombang 272,2 nm dan 249,1 nm menggunakan metode Newton dengan nilai
awal yang berbeda-beda
Percob. Konsentrasi Awal Konsentrasi Hasil Perhitungan Iterasi
Parasetamol : 501 ppm Parasetamol : 450.912307 ppm 1
Kafein : 502 ppm Kafein : 670.593663 ppm 6
Parasetamol : 400 ppm Parasetamol : 450.912307 ppm 2
Kafein : 600 ppm Kafein : 670.593663 ppm 5
Parasetamol : 450 ppm Parasetamol : 450.912307 ppm 3
Kafein : 550 ppm Kafein : 670.593663 ppm 5
Parasetamol : 300 ppm Parasetamol : 450.912307 ppm 4
Kafein : 700 ppm Kafein : 670.593663 ppm 5
Parasetamol : 250 ppm Parasetamol : 450.912307 ppm 5
Kafein : 600 ppm Kafein : 670.593663 ppm 6
Parasetamol : 50 ppm Parasetamol : 450.912307 ppm 6
Kafein : 200 ppm Kafein : 670.593663 ppm 8
Parasetamol : 50 ppm Parasetamol : 450.912307 ppm 7
Kafein : 20 ppm Kafein : 670.593663 ppm 17
107
Tabel 4.3.5 Hasil Perhitungan Konsentrasi Parasetamol dan Kafein pada panjang
gelombang 272,2 nm dan 249,1 nm menggunakan metode Turun Tercuram
dengan nilai awal yang berbeda-beda
Percob. Konsentrasi Awal Konsentrasi Hasil Perhitungan Iterasi
Parasetamol : 501 ppm Parasetamol : 450.578267 ppm 1
Kafein : 502 ppm Kafein : 668.984190 ppm 38
Parasetamol : 400 ppm Parasetamol : 450.825941 ppm 2
Kafein : 600 ppm Kafein : 669.584988 ppm 18
Parasetamol : 450 ppm Parasetamol : 450.718464 ppm 3
Kafein : 550 ppm Kafein : 669.139080 ppm 28
Parasetamol : 300 ppm Parasetamol : 450.576308 ppm 4
Kafein : 700 ppm Kafein : 668.639602 ppm 15
Parasetamol : 250 ppm Parasetamol : 451.447881 ppm 5
Kafein : 600 ppm Kafein : 672.090105 ppm 18
Parasetamol : 50 ppm Parasetamol : 450.884851 ppm 6
Kafein : 200 ppm Kafein : 670.703908 ppm 229
Parasetamol : 50 ppm Parasetamol : 450.481547 ppm 7
Kafein : 20 ppm Kafein : 669.467190 ppm 61
Dengan menggunakan tabel 4.3.4 dapat dilihat bahwa dengan nilai awal yang
berbeda-beda, sistem persamaan non-linear yang terbentuk apabila diselesaikan
dengan metode Newton akan konvergen ke suatu nilai yang sama atau mendekati
dengan tingkat kesalahan yang relatif kecil. Sedangkan dari tabel 4.3.5 dapat dilihat
pula bahwa dengan nilai yang berbeda-beda, sistem persamaan non-linear yang
terbentuk apabila diselesaikan dengan metode Turun Tercuram akan konvergen ke
suatu nilai yang mendekati penyelesaian yang didapatkan dari penyelesaian sistem
108
persamaan dengan metode Newton. Meskipun nilai awalnya sangat jauh berbeda,
tetapi diperoleh hasil yang konvergen ke suatu nilai yang sama atau mendekati, yang
membedakan hanyalah jumlah iterasi yang terjadi sampai sistem persamaan non-
linear konvergen. Pada metode Newton, untuk mendapatkan hasil yang konvergen
walaupun dengan nilai awal yang relatif cukup jauh, tidak memerlukan iterasi yang
cukup banyak. Dengan iterasi yang relatif sedikit, sistem persamaan sudah
konvergen. Sedangkan pada metode Turun Tercuram, untuk mendapatkan hasil yang
konvergen dengan nilai awal yang relatif cukup jauh, memerlukan iterasi yang cukup
banyak. Bahkan ada nilai awal yang membutuhkan 229 iterasi sampai sistem
persamaan dapat konvergen.
Berdasarkan analisis di atas, dapat dikatakan bahwa dalam menyelesaikan
sistem persamaan antara panjang gelombang 272,2 nm dan 249,1 nm dapat
menggunakan metode Newton dan metode Turun Tercuram. Hal ini dikarenakan,
dalam sistem ini, nilai awal tidaklah berpengaruh. Dengan nilai awal yang berbeda-
beda, kedua metode akan memberikan hasil akhir yang konvergen dan mendekati
bahkan cukup dekat ke suatu nilai yang sama walaupun dengan jumlah iterasi yang
berbeda-beda. Dengan demikian, pada sistem ini, dapat disimpulkan bahwa metode
Newton dan metode Turun Tercuram tidak sensitif terhadap nilai awal.
Dalam hal ini, perlu dibedakan antara pernyataan tidak sensitif atau sensitif
terhadap nilai awal dengan nilai awal yang baik. Kesensitifan terhadap nilai awal
akan mempengaruhi apakah dengan nilai awal berapapun yang diberikan, sistem akan
konvergen ke suatu nilai yang sama atau mendekati. Sedangkan nilai awal yang baik
109
adalah nilai awal yang dapat membuat sistem non-linear lebih cepat konvergen ke
suatu nilai atau dengan kata lain dengan jumlah iterasi yang relatif sedikit.
3. Pengaruh pendekatan fungsi terhadap hasil
Sistem persamaan non-linear yang dibentuk terdiri dari fungsi-fungsi
polinomial yang merupakan pendekatan dengan menggunakan data-data atau
koefisien yang diperoleh dari percobaan tentang pengukuran konsentrasi unsur dalam
larutan parasetamol dan kafein. Dengan data yang ada dapat dibentuk sistem
persamaan non-linear seperti pada sistem persamaan (4.2.2). Data yang disajikan
sebagian besar merupakan hasil pembulatan.
Kemudian untuk menganalisis lebih mendalam tentang fungsi, dilakukan
penghitungan dengan metode Newton dan metode Turun Tercuram. Koefisien-
koefisien fungsi diubah dengan tingkat kesalahan atau selisih yang relatif kecil,
kemudian dibentuk sistem persamaan non-linear baru. Sistem persamaan non-linear
yang baru kemudian dicoba diselesaikan secara numerik dengan metode Newton dan
metode Turun Tercuram dan menggunakan nilai awal yang sama. Namun,
penyelesaian yang diperoleh sangat jauh berbeda dengan penyelesaian semula. Hal ini
disebabkan perhitungan dengan metode Newton dan metode Turun Tercuram
melibatkan banyak subsitusi fungsi, diantaranya sebagai berikut :
110
a. Metode Newton
Pada langkah awal, fungsi diturunkan untuk membentuk matriks Jacobi ( )J x ,
subsitusi nilai awal ke fungsi-fungsi dalam sistem persamaan non-linear
sehingga diperoleh ( )(0)F x , subsitusi nilai awal ke matriks Jacobi sehingga
diperoleh , serta menghitung invers dari ( (0)J x ) ( ) 1(0) −J x yang akan
digunakan untuk menghitung penyelesaian pada iterasi berikutnya dan akan
didapatkan nilai baru . Nilai baru tersebut akan
digunakan untuk menghitung nilai dengan
(1) (0) (0) 1 (0)( ) (−= −x x J x F x )
( )kx 1, 2,k = … pada iterasi
selanjutnya sampai akan menghasilkan penyelesaian akhir sistem persamaan
non-linear. Perlu diingat dalam metode Newton, selain karena fungsi-fungsi
yang ada di dalam sistem persamaan non-linear dan nilai awal yang diberikan,
iterasi dalam metode Newton dapat dilanjutkan kembali asalkan ada ( ) 1−J x .
b. Metode Turun Tercuram
Pada langkah pertama, akan dibentuk suatu fungsi baru dan akan
dibentuk (
21g f f= + 2
2
( ) 2 ( ) ( )tg∇ =x J x F x ( )g∇ x dijabarkan berdasarkan definisi 3.5.1).
Kemudian, akan dicari ( )z g= ∇ x . Subsitusikan nilai awal ke dalam ,
dan z sehingga diperoleh , dan . Kemudian,
menurut Quadratic Fit Line Search dan Interpolasi Kuadratik akan didapatkan
( )g x
( )g∇ x (0)( )g x (0)(g∇ x ) (0)z
111
0 1 2 3, , ,α α α α dan nilai dengan
serta . Setelah itu akan dipilih nilai
0 1 2, , ,g g g g3 )(0) (0) (0)( ) ( (i ig g gα= − ∇x x x
0,1, 2,3i = α dari himpunan { }0 3,α α
suapaya nilai akan minimum diantara himpunan {( (0)g x ) }0 3,g g . Nilai α
yang didapatkan akan digunakan untuk mendapatkan nilai dengan
. Nilai baru tersebut akan digunakan untuk menghitung
nilai dengan
(1)x
((1) (0) (0)gα= − ∇x x x )( )kx 1, 2,k = … pada iterasi selanjutnya sampai akan
menghasilkan penyelesaian akhir sistem persamaan non-linear.
Dengan pernyataan di atas, dapat disimpulkan bahwa metode Newton dan
metode Turun Tercuram sangat sensitif terhadap fungsi-fungsi yang membentuk
sistem persamaan non-linear. Walaupun dengan metode Turun Tercuram dapat
mengatasi kelemahan metode Newton tetapi dengan fungsi dan data yang akurat serta
tepat akan menghasilkan penyelesaian yang lebih baik lagi. Sedikit pembulatan
koefisien fungsi, penyelesaian yang diperoleh dapat sangat jauh berbeda. Oleh karena
itu data yang digunakan harus benar-benar akurat dan pendekatan fungsi yang
dibentuk juga haruslah tepat.
4. Perbandingan nilai absorban hasil pengukuran dengan hasil perhitungan
Dengan mensubsitusi hasil yang diperoleh dengan metode Newton dan
metode Turun Tercuram (lihat Tabel 4.2.5) ke fungsi-fungsi yang membentuk sistem
112
persamaan non-linear, akan diperoleh nilai absorban. Perbandingan nilai absorban
hasil pengukuran dan hasil perhitungan yang didapatkan dari metode Newton dan
metode Turun Tercuram akan disajikan dalam Tabel di bawah ini :
Tabel 4.3.6 Perbandingan nilai absorban hasil perhitungan dari metode Newton dan
nilai absorban hasil pengukuran
Konsentrasi Hasil
Perhitungan (ppm)
Lambda
(nm)
Absorban dari
Perhitungan
Absorban dari
Pengukuran
Parasetamol : 450.912307 272,2 0.0730 0.073
Kafein : 670.593663 249,1 0.0540 0.054
Tabel 4.3.7 Perbandingan nilai absorban hasil perhitungan dari Metode Turun
Tercuram dengan nilai absorban hasil pengukuran
Konsentrasi Hasil
Perhitungan (ppm)
Lambda
(nm)
Absorban dari
Perhitungan
Absorban dari
Pengukuran
Parasetamol : 450.404301 272,2 0.0730 0.073
Kafein : 669.131891 249,1 0.0540 0.054
Dengan Tabel 4.3.6 dan Tabel 4.3.7 di atas, nilai absorban hasil perhitungan untuk
sistem persamaan non-linear pada panjang gelombang 272,2 nm dan 249,1 nm yang
didapatkan dari metode Newton adalah ( )0.0730,0.0540 t sedangkan dari metode
Turun Tercuram adalah ( )0.0730,0.0540 t . Kedua nilai absorban tersebut sama
dengan nilai absorban hasil pengukuran yaitu ( )0.073,0.054 t . Ini menunjukkan
113
bahwa penyelesaian yang diperoleh merupakan akar-akar dari sistem persamaan di
atas.
5. Konsentrasi Parasetamol dan Kafein yang memenuhi
Dari seluruh hasil yang diperoleh setelah diadakan analisis secara menyeluruh
dapat diperoleh konsentrasi parasetamol yang memenuhi atau masuk akal baik secara
matematika maupun fisika. Perlu dilihat kembali Tabel 4.2.9 di atas, terlihat bahwa
pada sistem persamaan (4.2.2) dengan panjang gelombang 272,2 nm dengan 249,1
nm apabila diselesaikan dengan metode Newton akan diperoleh konsentrasi
parasetamol sebesar 450.912307 dan konsentrasi kafein sebesar 670.593663,
sedangkan bila diselesaikan dengan metode Turun Tercuram akan diperoleh
konsentrasi parasetamol sebesar 450.404301 dan konsentrasi kafein sebesar
669.131891 yang mendekati dengan konsentrasi unsur yang didapatkan dari metode
Newton. Nilai konsentrasi kedua unsur di atas semuanya positif dan perbandingan
nilai absorban hasil perhitungan dengan nilai absorban hasil pengukuran dari sistem
persamaan non-linear (4.2.2) di atas sama (lihat Tabel 4.3.6 dan Tabel 4.3.7). Jadi,
dapat disimpulkan bahwa metode Newton dan metode Turun Tercuram dapat
diterapkan untuk mengkombinasikan besarnya konsentrasi parasetamol dan kafein
dalam larutan untuk memperoleh nilai absorban yang diinginkan. Nilai konsentrasi
yang diperoleh adalah parasetamol sebesar 450.912307 ppm dan kafein sebesar
670.593663 ppm.
BAB V
PENUTUP
A. Kesimpulan
Berdasarkan uraian dari bab-bab sebelumnya, maka dapat disimpulkan
beberapa hal berikut ini :
1. Metode Newton merupakan salah satu metode untuk menyelesaikan sistem
persamaan non-linear dan merupakan perluasan dari Metode Newton-Raphson
dan Iterasi Titik Tetap. Syarat dalam menyelesaikan sistem persamaan non-linear
dengan metode Newton adalah sebagai berikut :
a. Sistem persamaan non-linear yang dimaksud adalah sistem persamaan non-
linear yang terdiri dari n persamaan dan n variabel.
b. Semua fungsi yang terlibat dalam sistem persamaan non-linear harus
diferensiabel.
Metode Newton adalah suatu algoritma iterasi fungsional yang membangkitkan
dengan dan adalah matriks Jacobi
dari sistem persamaan non-linear. Metode Newton memiliki konvergensi yang
bersifat q-kuadratik dengan relasi kesalahan
( ) ( 1) ( 1) 1 ( 1)( ) (k k k k− − −= −x x J x F x )− 1k ≥ ( )J x
( 1) ( )k+ ≤e e k . Metode Newton
sangat populer karena bentuk iterasinya yang sederhana, meskipun demikian
metode Newton mempunyai dua kelemahan yang utama, yaitu :
115
a. Metode Newton cukup sensitif terhadap nilai awal sehingga memerlukan
pendekatan awal yang baik (mendekati akar) untuk menghasilkan barisan
iterasi yang konvergen.
b. Keharusan untuk memiliki 1( )−J x , apabila syarat ini tidak terpenuhi maka
iterasi tidak dapat dilanjutkan kembali.
2. Metode Turun Tercuram merupakan metode optimasi yang dapat digunakan
untuk mengatasi kelemahan Metode Newton. Secara umum, metode ini
merupakan metode untuk menentukan minimum lokal dari fungsi multivariabel
dengan bentuk . Misalkan terdapat suatu sistem persamaan : ng → ( ) =F x 0
yang memiliki suatu penyelesaian maka dapat didefinisikan
fungsi g dengan . Penyelesaian minimum merupakan
penyelesaian dari sistem
tnxxx ),,,( 21 …=x
[ 2
1( ) ( )
n
ii
g f=
= ∑x ]x ( )g x
( ) =F x 0 . Penyelesaian yang diberikan adalah
dengan dan (( ) ( 1) ( 1) ( 1)k k k kgλ− − −= − ∇x x x ) 1k ≥ ( )g∇ x adalah gradien dari
. Metode Turun Tercuram akan konvergen apabila dan
memiliki karakteristik bahwa vektor-vektor penyelesaian akan ortogonal apabila
dekat dengan titik stasionernya.
( )g x ( )lim ( ) 0k
kg
→∞∇ x =
3. Metode Turun Tercuram juga sensitif terhadap nilai awal. Akan tetapi,
penyelesaian yang dihasilkan dari metode Turun Tercuram dapat menjadi nilai
116
awal yang baik bagi metode Newton, yang artinya bahwa berapapun nilai awal
yang sudah diperbaiki oleh metode Turun Tercuram dapat membuat penyelesaian
sistem persamaan non-linear dengan metode Newton akan konvergen ke suatu
nilai yang sama atau dengan kesalahan yang relatif kecil.
4. Metode Newton dan Metode Turun Tercuram dapat diaplikasikan dalam bidang
fisika yaitu menghitung konsentrasi unsur dalam sampel. Metode Newton dan
metode Turun Tercuram akan diterapkan untuk mengkombinasikan besarnya
konsentrasi parasetamol dan kafein dalam larutan untuk memperoleh nilai
absorban yang diinginkan. Dalam hal ini, konsentrasi parasetamol dan kafein
yang memenuhi adalah parasetamol sebesar 450.912307 ppm dan kafein sebesar
670.593663 ppm.
B. Saran
1. Masih banyak terdapat metode numeris yang dapat digunakan untuk
menyelesaikan sistem persamaan non-linear, contohnya Iterasi GMRES.
2. Pada metode Turun Tercuram, masih banyak terdapat metode line search yang
dapat digunakan dalam mencari λ .
3. Masih banyak terdapat metode optimasi yang dapat digunakan untuk
menyelesaikan sistem persamaan non-linear.
117
DAFTAR PUSTAKA
Anton, Howard. (2000). Dasar-Dasar Aljabar Linear (Terjemahan). Edisi ketujuh.
Jilid I. Batam Centre : Interaksa.
Bazaraa, Mokhtar S., Sherali, Hanif D., Shetty, C.M. (1993). Nonlinear
Programming Theory and Algoritma, 2 nd ed. New York : John Willey & Sons.
Bertsekas, Dimitri P., Tsitsiklis, John N. (1989). Parallel and Distributed
Computation: Numerical Methods. Upper Saddle River : Prentice Hall.
http://dspace.mit.edu/handle/1721.1/3719 (7 Oktober 2007, 07:15 AM) Budhi, Wono Setya. (1995). Aljabar Linear. Jakarta : Gramedia Pustaka Utama.
Burden, R. L , and Faires, J. D. (1985). Numerical Analysis. Boston: PWS Publisher.
Cahyaningsih, C. Duduk Dwi. (2005). Perbandingan Metode-Metode Penyelesaian
Persamaan Non-Linear Secara Numeris. Yogyakarta : USD.
Chung, Timothy, and Gupta, Vijay. (2004). Distributed Algoritms and Optimization :
A Case Study. (Mobile Robotics Reading Group)
http://robotics.caltech.edu/readinggroup/distoptim/DistOptimNotes2.pdf (30 Agustus 2007, 10:30 PM ) Edi, S. (2006). Modifikasi pada AAS IL451 untuk Pengukuran Konsentrasi Unsur
dalam Sampel. (Makalah disampaikan dalam seminar dosen rumpun MIPA
Universitas Sanata Dharma Yogyakarta)
Horn, Roger A., and Johnson, Charles A. (1990). Matrix Analysis. New York :
Cambridge.
Kelley, C. T. (1995). Iterative Methods for Linear and Non-Linear Equations.
Philadelphia.
www.ec-securehost.com/SIAM/FR16.html (17 September 2006, 01:00 AM)
Leon, Steven J. (2001). Aljabar Linear dan Aplikasinya (Terjemahan). Edisi kelima.
Jakarta : Penerbit Erlangga.
Linfield, G, and Penny, J. (2000). Numerical Methods Using Matlab. Upper Saddle
River: Prentice Hall.
118
Pramustiwi, Valentina Rian. (2007). Penyelesaian Sistem Persamaan Non-Linear
dengan Metode Broyden dan Terapannya. Yogyakarta : USD.
Sert, Cuneyt. ME 310 Numerical Methods Interpolation.Ankara.
http://www.me.metu.edu.tr/cuneyt/me310/me310%20interpolation.pdf (15 Oktober 2007, 09:56 PM) Soemantri, R., Tutoyo, A. (2006). Diktat Pengantar Analisis Real. Yogyakarta :
FMIPA USD.
Thomas, George B., Finney, Ross L. (1986). Kalkulus dan Geometri Analitik
(Terjemahan). Edisi keenam. Jilid I. Jakarta : Penerbit Erlangga.
Varbeg, Dale., Purcell, Edwin J. (1997). Calculus, 7 th ed. New Jersey : Prentice Hall.
Vekantaraman, P. (2001). Applied Optimization with Matlab Programming. New
York : John Willey & Sons.
119
LAMPIRAN 1
PROGRAM MENU UTAMA
Listing Program pilih=0; while pilih~=3 fprintf('\n\n\n\n'); disp('Program Penyelesaian Sistem Persamaan Non-Linear'); disp('oleh Maria Nirmala Anggi Fitra Murti Martosudjito (033114007)'); disp('sebagai syarat memperoleh gelar S.Si'); fprintf('\n\n\n\n'); disp('-------------------------------------------------------'); disp(' Menu Utama'); disp(' Penyelesaian Sistem Persamaan Non-Linear'); disp('-------------------------------------------------------'); disp(' 1. Metode Newton'); disp(' 2. Metode Turun Tercuram'); disp(' 3. Keluar'); fprintf('\n\n'); pilih=input('Masukkan menu pilihan anda='); switch pilih case 1 newton; case 2 turun_tercuram; case 3 disp('Keluar'); otherwise disp('Masukkan anda salah'); end end disp('Terimakasih anda telah menggunakan program ini.');
OUTPUT >> skripsi Program Penyelesaian Sistem Persamaan Non-Linear oleh Maria Nirmala Anggi Fitra Murti Martosudjito (033114007) sebagai syarat memperoleh gelar S.Si ------------------------------------------------------- Menu Utama Penyelesaian Sistem Persamaan Non-Linear ------------------------------------------------------- 1. Metode Newton 2. Metode Turun Tercuram 3. Keluar Masukkan menu pilihan anda=
120
LAMPIRAN 2 PROGRAM METODE NEWTON Listing Program % program metode newton % dibuat oleh Maria Nirmala Anggi Fitra Murti Martosudjito % 033114007 % sebagai lampiran skripsi clc %memasukkan beberapa data seperti x0,tol dan iterasi maksimum. fprintf('Metode Newton\n\n'); fprintf('Masukkan data yang dibutuhkan\n\n'); x=input('x0 = '); tol=input('Toleransi error = '); N=input('Max.iterasi = '); k=1; fprintf('\n\nOutput\n'); fprintf('\n---------------------------------------------------'); fprintf('\n\tk | x1 | x2 | x3'); fprintf('\n---------------------------------------------------'); fprintf('\n%4.0f %12f %12f %12f',k-1,x); tic while k <= N fx=fungsi(x); %menghitung nilai fungsi f(x). jx=jacobian(x); %menghitung nilai matriks jacobian. y=-inv(jx)*fx; if norm(y)<tol %mengecek apakah iterasi akan berhenti atau dilanjutkan. fprintf('\n%4.0f %12f %12f %12f',k,x); break end x=x+y'; %nilai x yang baru. fprintf('\n%4.0f %12f %12f %12f',k,x); k=k+1;%iterasi akan dilanjutkan kembali. end if k>=N fprintf('\nIterasi Maksimum Terlewati'); %pemberitahuan bahwa iterasi maksimum sudah terlampaui. end toc function fx=fungsi(x) x1=x(1);x2=x(2);x3=x(3); f1=3*x1-cos(x2*x3)-0.5; f2=x1^2-81*(x2+0.1)^2+sin(x3)+1.06; f3=exp(-x1*x2)+20*x3+((10*pi-3)/3); fx=[f1;f2;f3];
121
function jx=jacobian(x) x1=x(1);x2=x(2);x3=x(3); j11=3; j12=x3*sin(x2*x3); j13=x2*sin(x2*x3); j21=2*x1; j22=-162*(x2+0.1); j23=cos(x3); j31=-x2*exp(-x1*x2); j32=-x1*exp(-x1*x2); j33=20; jx=[j11 j12 j13;j21 j22 j23;j31 j32 j33]; %j(ik)=turunan fungsi ke-i terhadap variabel ke-k OUTPUT >> newton Metode Newton Masukkan data yang dibutuhkan x0 = [0 0 0] Toleransi error = 10e-6 Max.iterasi = 100 Output --------------------------------------------------- k | x1 | x2 | x3 --------------------------------------------------- 0 0.000000 0.000000 0.000000 1 0.500000 -0.016889 -0.523599 2 0.500016 0.001720 -0.523554 3 0.500000 0.000015 -0.523598 4 0.500000 0.000000 -0.523599 5 0.500000 0.000000 -0.523599 elapsed_time = 0.1500
122
LAMPIRAN 3 PROGRAM METODE TURUN TERCURAM Listing Program % program metode turun tercuram % dibuat oleh Maria Nirmala Anggi Fitra Murti Martosudjito % 033114007 % sebagai lampiran skripsi function turun_tercuram clc %memasukkan beberapa data seperti x0,toleransi dan maksimum iterasi fprintf('Metode Turun Tercuram\n\n'); fprintf('Masukkan data yang dibutuhkan\n\n'); x=input('x0='); %nilai awal tol=input('Toleransi eror='); %toleransi error N=input('Iterasi maksimum='); k=1; n=length(x); g1=g_awal(x); fprintf('\n\nOutput\n'); fprintf('\n--------------------------------------------------'); fprintf('\n\tk | x1 | x2 | x3 | g(x)'); fprintf('\n--------------------------------------------------'); fprintf('\n%4.0f %12f %12f %12f %12f',k-1,x,g1); tic while k<=N %fungsi awal F(x)=0 fx=fungsi(x); %fungsi g(x)=f1(x)^2+f2(x)^2+f3(x)^2 g1=g_awal(x); %gradien g(x) z=grad(x); z0=norm(z,2); if z0==0 fprintf('\n%4.0f %12f %12f %12f %12f\n',k,x,g1); %mengecek apakah iterasi akan berhenti atau dilanjutkan. disp('stopping kriteria : 1'); break end z=z/z0; lamda1=0; lamda3=1; g3=g_baru_3(x,lamda3,z); while g3>=g1 lamda3=lamda3/2; g3=g_baru_3(x,lamda3,z); if lamda3 < (tol/2)
123
fprintf('\n%4.0f %12f %12f %12f %12f\n',k,x,g1); %mengecek apakah iterasi akan berhenti atau dilanjutkan. disp('stopping kriteria : 2'); break end end lamda2=lamda3/2; g2=g_baru_2(x,lamda2,z); h1=(g2-g1)/lamda2; h2=(g3-g2)/(lamda3-lamda2); h3=(h2-h1)/lamda3; lamda0=0.5*(lamda2-(h1/h3)); ld=[lamda0 lamda1 lamda2 lamda3]; for i=1:4 g(i)=g_baru(x,ld(i),z); end h=min(g); p=find(h==g); lamda=ld(p); for m=1:n x(m)=x(m)-lamda*z(m); %nilai x yang baru end if abs(h-g1)<tol fprintf('\n%4.0f %12f %12f %12f %12f\n',k,x,g1); %mengecek apakah iterasi akan berhenti atau dilanjutkan. disp('stopping kriteria : 3'); break end fprintf('\n%4.0f %12f %12f %12f %12f',k,x,g1); k=k+1; %iterasi akan dilanjutkan kembali. end if k>N fprintf('\nIterasi maksimum terlewati'); %pemberitahuan bahwa iterasi maksimum sudah terlampaui end toc function fx=fungsi(x) x1=x(1);x2=x(2);x3=x(3); f1=3*x1-cos(x2*x3)-0.5; f2=x1^2-81*(x2+0.1)^2+sin(x3)+1.06; f3=exp(-x1*x2)+20*x3+((10*pi-3)/3); fx=[f1;f2;f3]; function g1=g_awal(x0) x1=x0(1);x2=x0(2);x3=x0(3); f1=3*x1-cos(x2*x3)-0.5; f2=x1^2-81*(x2+0.1)^2+sin(x3)+1.06; f3=exp(-x1*x2)+20*x3+((10*pi-3)/3); g1=f1^2+f2^2+f3^2;
124
function z=grad(x0) x1=x0(1);x2=x0(2);x3=x0(3); fx=fungsi(x0); jx=jacobian(x0); z=2*jx'*fx; function jx=jacobian(x) x1=x(1);x2=x(2);x3=x(3); j11=3; j12=x3*sin(x2*x3); j13=x2*sin(x2*x3); j21=2*x1; j22=-162*(x2+0.1); j23=cos(x3); j31=-x2*exp(-x1*x2); j32=-x1*exp(-x1*x2); j33=20; jx=[j11 j12 j13;j21 j22 j23;j31 j32 j33]; %j(ik)=turunan fungsi ke-i terhadap variabel ke-k function g3=g_baru_3(x0,lamda,z) x1=x0(1);x2=x0(2);x3=x0(3); z1=z(1);z2=z(2);z3=z(3); f1=3*(x1-lamda*z1)-cos((x2-lamda*z2)*(x3-lamda*z3))-0.5; f2=(x1-lamda*z1)^2-81*((x2-lamda*z2)+0.1)^2+sin(x3-lamda*z3)+1.06; f3=exp(-(x1-lamda*z1)*(x2-lamda*z2))+20*(x3-lamda*z3)+((10*pi-3)/3); g3=f1^2+f2^2+f3^2; function g2=g_baru_2(x0,lamda,z) x1=x0(1);x2=x0(2);x3=x0(3); z1=z(1);z2=z(2);z3=z(3); f1=3*(x1-lamda*z1)-cos((x2-lamda*z2)*(x3-lamda*z3))-0.5; f2=(x1-lamda*z1)^2-81*((x2-lamda*z2)+0.1)^2+sin(x3-lamda*z3)+1.06; f3=exp(-(x1-lamda*z1)*(x2-lamda*z2))+20*(x3-lamda*z3)+((10*pi-3)/3); g2=f1^2+f2^2+f3^2; function g=g_baru(x0,lamda,z) x1=x0(1);x2=x0(2);x3=x0(3); z1=z(1);z2=z(2);z3=z(3); f1=3*(x1-lamda*z1)-cos((x2-lamda*z2)*(x3-lamda*z3))-0.5; f2=(x1-lamda*z1)^2-81*((x2-lamda*z2)+0.1)^2+sin(x3-lamda*z3)+1.06; f3=(exp(-(x1-lamda*z1)*(x2-lamda*z2))+20*(x3-lamda*z3)+((10*pi-3)/3))^2; g=f1^2+f2^2+f3^2;
125
OUTPUT >> turun_tercuram Metode Turun Tercuram Masukkan data yang dibutuhkan x0=[0 0 0] Toleransi eror=10e-5 Iterasi maksimum=500 Output ------------------------------------------------------------ k | x1 | x2 | x3 | g(x) ------------------------------------------------------------ 0 0.000000 0.000000 0.000000 111.974771 1 0.011218 0.010096 -0.522741 111.974771 2 0.137860 -0.205453 -0.522059 2.327617 3 0.266959 0.005511 -0.558494 1.274058 4 0.272734 -0.008118 -0.522006 1.068131 5 0.329502 -0.027514 -0.539540 0.468309 6 0.336015 -0.015417 -0.511472 0.409987 7 0.340035 -0.011098 -0.525940 0.314165 8 0.365968 -0.002590 -0.510719 0.233251 9 0.369629 -0.005242 -0.525676 0.232554 10 0.381781 -0.010456 -0.517353 0.155591 11 0.387115 -0.005500 -0.531178 0.146196 12 0.392156 -0.007284 -0.516497 0.137422 13 0.396954 -0.005207 -0.531221 0.126224 14 0.401578 -0.006774 -0.516379 0.118461 15 0.405922 -0.004695 -0.531243 0.109379 16 0.410166 -0.006335 -0.516295 0.102757 17 0.414106 -0.004215 -0.531266 0.095305 18 0.417997 -0.005928 -0.516231 0.089716 19 0.421573 -0.003769 -0.531287 0.083561 20 0.425140 -0.005551 -0.516179 0.078874 21 0.428388 -0.003357 -0.531305 0.073766 22 0.431657 -0.005203 -0.516138 0.069853 23 0.434607 -0.002976 -0.531319 0.065599 24 0.437604 -0.004882 -0.516103 0.062342 25 0.440283 -0.002624 -0.531330 0.058790 26 0.443031 -0.004586 -0.516075 0.056086 27 0.445463 -0.002300 -0.531339 0.053114 28 0.446756 -0.003333 -0.523497 0.050876 29 0.477514 -0.000432 -0.528199 0.025534 30 0.478065 -0.001307 -0.523567 0.013336 31 0.493563 -0.001754 -0.525507 0.004332 32 0.493752 -0.000261 -0.521902 0.002169 33 0.493914 -0.000237 -0.523848 0.001512 34 0.494142 -0.000404 -0.523450 0.000363 stopping kriteria : 3 elapsed_time = 0.0400