Metode Newton memiliki konvergensi kuadratik

Salah satu soal yang muncul di Ujian Tengah Semester (UTS) Analisis Numerik di kampus adalah menghitung kecepatan konvergensi salah satu metode numerik untuk mencari akar, yaitu metode Newton-Raphson.

Kecepatan konvergensi pada dasarnya merupakan nilai yang mengukur seberapa cepat solusi hasil iterasi menuju ke solusi yang sebenarnya. Misalkan f(x)=0  merupakan persamaan yang ingin diselesaikan dengan solusi eksak x^* dan x_k (k=1,2,\dots) merupakan solusi numerik hasil iterasi ke-k. Selisih |x_k-x^*| mengukur seberapa jauh solusi numerik dari solusi yang sebenarnya pada iterasi ke-$k$ atau biasanya disebut sebagai eror  (pada iterasi ke-k) dan tentunya sifat yang diinginkan adalah |x_{k+1}-x^*|<|x_k-x^*|. Namun, syarat pengurunan eror ini terlalu pesimistis karena ada metode Newton menjamin bahwa |x_{k+1}-x^*| < C |x_k-x^*|^2 untuk suatu konstanta C. Perhatikan bahwa ketaksamaan ini akan menekan eror lebih cepat dengaan asumsi |x_k-x^*| sudah cukup kecil. Sebagai contoh, jika eror pada iterasi ke-k adalah 10^{-3}, maka pada iterasi berikutnya erornya menjadi 10^{-6} dan pada iterasi berikutnya akan menjadi 10^{-12}, dst.  Secara kasar, dari solusi numerik dengan akurasi tiga digit, kita bisa memperoleh langsung dengan satu kali iterasi lagi diperoleh akurasi enam digit, kemudian dua belas digit, dst. Ini tentu sangat baik dibandingkan jika jumlah digit yang akuratnya bertambah satu per iterasi, yang terjadi pada metode-metode dengan batas eror |x_{k+1}-x^*|<|x_k-x^*| saja.

Metode Newton mencari solusi dari persamaan berbentuk f(x)=0 dengan menggunakan rumus iterasi

x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}

untuk k=0,1,2,\dots dengan tebakan awal x_0 diasumsikan sudah cukup dekat dengan solusi yang sebenarnya, yaitu x^*. Suatu metode numerik dengan solusi hasil iterasi x_0,x_1,x_2,\dots disebut memiliki kecepatan konvergensi kuadratik jika terdapat suatu konstanta C sehingga |x_{k+1}-x^*| < C |x_k-x^*|^2 untuk setiap k yang cukup besar. Menggunakan sifat ini, kita cukup menunjukkan bahwa

\lim_{k \rightarrow \infty} \frac{|x_{k+1}-x^*|}{|x_k-x^*|} = C_0

untuk suatu konstanta C_0>0 (yang mana C_0 ini pada dasarnya sama dengan C pada akhirnya). Hal ini masuk akal karena jika mengikuti definisi limit untuk barisan, pernyataan di atas sama saja dengan mengatakan bahwa terdapat suatu konstanta C_0 sehingga untuk setiap \epsilon > 0 terdapat \delta>0 yang mana untuk k yang cukup besar, dalam hal ini lebih dari \delta, berlaku

$latex  | \frac{|x_{k+1}-x^*|}{|x_k-x^*|}  – C_0| < \epsilon.$

Sekarang, soal UTS yang diujikan di kuliah Analisis Numerik di kampus sendiri hanya membuktikan bahwa iterasi Newton untuk mencari akar x^2-x-6=0 di x^*=3 memiliki konvergensi kuadratik. Ini dapat ditunjukkan secara langsung menggunakan limit seperti di atas, yaitu

\lim_{k \rightarrow \infty} \frac{|x_k - \frac{x_k^2-x_k-6}{2x_k-1}-x^*|}{|x_k-x^*|^2} = \lim_{k \rightarrow \infty} \frac{|x_k - \frac{x_k^2-x_k-6}{2x_k-1}-3|}{|x_k-3|^2}

di mana setelah membagi pembilang dan penyebut dengan |x_k-3|, diperoleh

\lim_{k \rightrrow \infty} \frac{|(2x_k-1)-(x_k+2)|}{|(2x_k-1)(x_k-3)|}=\lim_{k \rightarrow \infty} \frac{1}{|2x_k-1|} yang menuju C_0=\frac{1}{5} karena x_k sendiri konvergen ke solusi x^*=3. Jadi, sudah terbukti bahwa memang metode Newton untuk persamaan tersebut konvergen secara kuadratik ke x^*=3.

Bagaimana dengan metode Newton secara umum? Apakah konvergen secara kuadratik? Jawabannya adalah ya jika metode tersebut mencari akar yang memiliki multiplisitas satu, yang artinya solusi eksak x^* memenuhi f(x^*)=0 tetapi f'(x^*) \ne 0. Untuk akar yang memiliki multiplisitas lebih dari satu, metode Newton akan memiliki kecepatan yang sub-kuadratik, artinya lebih lambat dari kuadratik. Namun, hal ini akan dibahas di post berikutnya.

Kecepatan konvergensi kuadratik dari metode Newton secara umum untuk mencari akar persamaan dengan multiplisitas satu dapat ditunjukkan dengan menggunakan deret Taylor untuk persamaan f(x)=0. Jika x^* merupakan akar dengan multiplisitas 1, maka diperoleh ekspansi Taylor f(x) di titik x^* memberikan

f(x) = f(x^*)+(x-x^*)f'(x^*)+(x-x^*)^2 \frac{f''(x^*)}{2!}+\dots

sehingga karena f(x^*)=0 diperoleh f(x_k)=(x_k-x^*)f'(x^*)+(x-x^*)^2 \frac{f''(x^*)}{2!}+\dots.

Jika kita lihat kembali ekspresi limit untuk eror dari persamaan Newton umum, kita punyai

\lim_{k \rightarrow \infty} \frac{|x_k-\frac{f(x_k)}{f'(x_k)}-x^*|}{|x_k-x^*|^2} = \lim_{k \rightarrow \infty} \frac{|f(x_k)-(x_k-x^*)f'(x_k)|}{|x_k-x^*|^2|f'(x_k)|}

=\frac{1}{|f'(x^*)|} \lim_{k \rightarrow \infty} |\frac{f'(x_k)-f'(x^*)}{x_k-x^*}+ \frac{f''(x^*)}{2!}+(x_k-x^*)\frac{f'''(x^*)}{3!}+\dots| = \frac{1}{f'(x^*)} | f''(x^*)+\frac{f''(x^*)}{2!}+0|

di mana ruas kanan merupakan konstanta tak nol. Jadi, terbukti bahwa metode Newton konvergen secara kuadratik untuk akar dengan multiplisitas satu.

-Raja

 

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s