Seminar Nasional Pascasarjana VI 2006, Surabaya
Implementasi Algoritma Turan Untuk Menentukan Nilai Aproksimasi Pada Proses Mencari Akar-akar Polinomial Supriono
Choirul Imron Bandung Arry Sanjoyo Jurusan Matematika Institut Teknologi Sepuluh Nopember (ITS) Surabaya Kampus ITS Sukolilo Surabaya 60111 Email:
[email protected] Abstraks
Proses untuk menentukan n akar dari persamaan polinomial derajat n yang dikembangkan oleh Herman Weyl membutuhkan sebuah inputan berupa bujur sangkar. Bujur sangkar awal tersebut akan mengalami proses penyempitan sampai diperoleh aproksimasi akar-akar dari persamaan polinomial. Pada proses penyempitan bujur sangkar tersebut tentunya membutuhkan algoritma lain dalam hal ini digunakan algoritma Turan. Algoritma Turan adalah algoritma untuk mencari aproksimasi jarak terdekat antara sebuah titik dengan akar-akar polinomial. Pada proses menentukan nilai aproksimasi dibutuhkan langkah-langkah translasi polinomial, membentuk polinomial balikan, membentuk polinomial monik, iterasi Graeffe kemudian mencari nilai maksimum. Invers dari nilai maksimum adalah merupakan nilai Turan. Dari percobaan numerik dapat disimpulkan bahwa semakin banyak iterasi yang dilakukan maka nilai Turan konvergen ke satu. Kata kunci: polinomial, iterasi Graeffe, algoritma Turan
1. PENDAHULUAN Input dari algoritma Weyl pada proses menentukan akar-akar polionomial derajat tinggi adalah sebuah bujur sangkar, koefisien polinomial, dan banyaknya iterasi. Bujur sangkar awal tersebut akan mengalami proses penyempitan sampai diperoleh aproksimasi akar-akar polinomial. Dalam proses penyempitan bujur sangkar tersebut digunakan algoritma Turan. Dalam penelitian ini dikaji algoritma Turan dan bagaimana implementasinya untuk mencari nilai aproksimasi. Proses kerja algoritma Turan membutuhkan inputan berupa koefisien polinomial, derajat polinomial, sebuah bilangan sebagai faktor translasi, dan banyaknya iterasi. Iterasi yang digunakan algoritma Turan adalah iterasi Graeffe. Nilai aproksimasi yang diperoleh dari algoritma Turan digunakan untuk proses penyempitan bujur sangkar pada algoritma Weyl. 2. Persamaan Polinomial Jika n adalah bilangan bulat tak negatif dan p0, p1, ..., pn ∈ R adalah konstanta, maka persamaan Pn(x) = p0 + p1x + p2x2 + ... + pnxn, p n ≠ 0 disebut
polinomial real dengan pn disebut leading coefficient. Jika pn = 1, maka Pn(x) disebut polinomial monik. Bilangan z ∈ C disebut akar dari Pn(x) jika Pn(z) = 0. [4]
Teorema 2.1 (Teorema Dasar Aljabar) Jika Pn(x) = p0 + p1x + p2x2 + ... + pnxn, p n ≠ 0 adalah polinomial real berderajat n > 0 ,
2-42
maka terdapat sebuah bilangan kompleks sedemikian sehingga Pn ( z ) = 0 .
z
Teorema 2.2: Jika Pn(x) = p0 + p1x + p2x2 + ... + pnxn, p n ≠ 0 adalah polinomial real berderajat n ≥ 1 ,
dan misalkan z1, adalah akar dari Pn ( x ) , maka n – 1 terdapat polinomial Pn −1 (x ) berderajat sedemikian sehingga Pn ( x ) = ( x − z1 )Pn −1 ( x ) .
Teorema 2.3: Setiap polinomial Pn (x ) = p0 + p1 x + ... + p n x n dengan derajat tertinggi n dan p 0 , p1 , K , p n ∈ R di
mana p n ≠ 0 dapat dituliskan sebagai perkalian dari faktor-faktor linear, dalam bentuk Pn ( x ) = (x − z1 )( x − z 2 )...( x − z n )P0 ( x ) n
= P0 ( x )∏ ( x − z i ) i =1
dengan zi adalah akar-akar dari Pn ( x ) untuk
i = 1, 2, 3, …, n. 3. Algoritma Turan Algoritma Turan adalah algoritma untuk memperoleh aproksimasi jarak antara sebarang bilangan C ∈ C yang di berikan, dengan akar dari Pn (x ) yang terdekat dengan C. Algoritma Turan ini
digunakan dalam algoritma Weyl dalam proses penyempitan bujur sangkar. Pada bagian ini akan diterangkan tentang definisi, proposisi dan teorema yang merupakan konsep dasar dari algoritma Turan,
ISBN 979-545-027-1 @2006 ITS
Seminar Nasional Pascasarjana VI 2006, Surabaya juga akan diberikan langkah–langkah dari algoritma Turan. [7]
Definisi 3.1 (Root Radii dan Radius Akar) : Diberikan polinomial Pn ( x ) yang
memiliki n buah akar dan sebarang titik C ∈ C. Root Radii dari pada C adalah n buah jarak dari titik C ke setiap n buah akar dari Pn ( x ) dengan sifat r1(C) ≥ r2(C) ≥ … ≥ rn(C) dan rs(C) disebut radius (jarak) akar ke-s dari Pn ( x ) pada titik C. Proposisi 3.2 Jika z1,z2,…,zn adalah akar-akar dari polinominal Pn ( x ) , Tn(x) adalah polinomial
translasi dari Pn ( x ) sejauh C dan Bn(x) adalah
polinomial balikan dari Pn ( x ) maka : 1.
1 zi
adalah akar-akar dari Bn(x) = xn
n
(
2 ∏ x − zi i =1
) dengan z adalah akar-akar dari P (x) i
n
n
Definisikan Sk = ∑ z j , maka akan berlaku identitas k
j =1
Newton berikut : Sk + pn-1Sk-1 + ...+p0Sk-n = 0 , (k > n) Sk + pn-1Sk-1 + … +pn-k+1S1 = -kpn-k , (1≤ k ≤ n)
(ξ1 ,..., ξ n )
sebarang
bilangan
max ξ g
dengan
=
g =1,...,n
kompleks 1
berlaku
pertidaksamaan
⎛ ξ1g + ... + ξ ng max ⎜ g =1,...., n⎜ n ⎝
Proposisi 3.3 Jika rs(C) adalah jarak akar ke-s dari
Pn ( x ) pada titik C dan rs* (0 ) adalah jarak akar Tn(x) = Pn(x + C) pada titik 0 maka
a. rs(C) dari Pn ( x ) sama dengan r (0 ) dari * s
Tn (x ) = Pn ( x + C ) 1 dari Pn ( x ) sama dengan r(n + 1- s)(0) dari b. rs (0)
⎛1⎞ polinom balikan Bn(x) = xnPn ⎜ ⎟ ⎝ x⎠ 1 c. dari Pn ( x ) sama dengan r1(0) dari Bn(x) rn (C ) ⎛1⎞ ⎟ ⎝ x⎠
= xnTn ⎜
1
⎞g 1 ⎟ > ⎟ 5 ⎠
Teorema 3.8 Jika Pn ( x ) = p0 + p1x + . . .+ pnxn = 0
dengan z1, z2, . . ., zn adalah akar- akar dari Pn ( x ) . n
Jika
SgN = ∑ z j
gN
j =1
dengan g = 1,. . .,n dan N
adalah bilangan asli. Maka berlaku pertidaksamaan 1≤
r1 (0)
max
g =1,..., n
S gN
1 1 gN
≤ 5N
n
Algoritma Turan membutuhkan tiga input yaitu: koefisien dari Pn(x), sebarang bilangan real C dan sebarang bilangan asli N (log 2N adalah jumlah iterasi maksimum iterasi Graeffe). Langkah-langkah dari Algoritma Turan adalah sebagai berikut: Langkah 1 : Lakukan translasi polinomial Tn ( x ) = Pn ( x + C )
= q0 + q1 x + ... + q n x n '
Definisi 3.4 (Iterasi Graeffe)
(0 )
Diberikan polinomial monik Pn (x) = p0 + p1x + p2x2 + … + pnxn. Iterasi Graeffe didefinisikan secara rekursif sebagai
Pn
h
polinomial monik dengan akar-akar zj untuk j = 1,2,…,n
untuk i = 1,2,…,n
(v +1)
(h )
Teorema 3.6 (Identitas Newton)[5] Jika Pn ( x ) = xn + pn-1 xn-1 + … + p0 adalah
⎛1⎞ Pn ⎜ ⎟ ⎝ x⎠
ke-s dari berlaku:
) ( x ) , v = 1, 2, …, h.
Pada iterasi ke-h diperoleh polinomial Pn (x) =
Teorema 3.7[10] Untuk
zi – C adalah akar dari Tn(x) = Pn(x + C)
2.
(
Pn(v ) = (-1)n pv-1 − x pv-1
(
= (-1) pv − n
kemudian bentuk polinomial balikan dari Tn(x) yaitu ⎛1⎞ Bn ( x) = x n Tn ⎜ ⎟ ⎝ x⎠
= q 0 x n + q1 x n −1 + ... + q n
) ( x ) , v = 0, 1, 2, …
x .pv
Langkah 2 : Bentuk polinomial monik Proposisi 3.5
Diberikan polinomial real lakukan iterasi Graeffe
(0 )
Pn
dan
M n ( x) =
Bn ( x ) q0
dan lakukan iterasi Graeffe
ISBN 979-545-027-1 @2006 ITS
2-43
Seminar Nasional Pascasarjana VI 2006, Surabaya Gn(1) ( x) = (−1) n t i −1 ( x )t i −1 (− x ),
i = 1,..., h h = log 2 N
dengan prosesor Pentium 2,4 GB dan RAM 256 MB. Pada langkah ke-1 algoritma Turan dilakukan suatu translasi polinomial Pn ( x ) pada titik C sehingga menjadi polinomial Tn ( x ) = Pn ( x + C ) ,
sehingga pada iterasi ke-h diperoleh n
Gnh ( x) = ∏ ( x − xiN )
karena itu diperlukan sebuah algoritma untuk memperoleh koefisien dari Tn(x) tersebut. Prosedur dari algoritma Translasi ditunjukkan oleh algoritma dibawah ini. Input : Polinomial Pn ( x ) (berupa koefisien-
i =1
= t 0,h + t1,h x + L + t n ,h x n = t 0,h + t1,h x + L + x n
koefisien polinomial {p0, p1, p2,…, pn}), titik C ∈ R FOR i ← 0 TO n DO ki ← 1; END FOR FOR i ← 0 TO n DO qi ← 0; FOR j ← i TO n DO qi ← qi + k(j-i+1)PjC(j-i) END FOR FOR l ← 1 TO n-i DO kl ← kl + k(l-1) END FOR END FOR Output : q0, q1,…qn
dimana xi (i= 1,2,…,n) adalah akar-akar dari
Gn(0 ) ( x )
Langkah 3: Hitung n
s gN = ∑ xigN ,
g = 1,2,…n
i =1
dimana
xi(i=1,2,…,n)
adalah
akar-akar
dari
Gn ( x ) , dengan menyelesaikan identitas Newton (0 )
berikut: S1N
= −t n −1,h
t n −1,h S1N + S 2 N
= −2t n − 2, h
t n − 2,h S1N + t n −1,h S 2 N + S 3 N
= −3t n − 3, h
M
(3.1)
t1,hS1N + t2,hS2N + ... + tn-1,hS(n-1)N + SnN = − nt o ,h SPL (3.1) dapat dituliskan dituliskan dalam notasi matriks berikut: ⎛1 ⎜ ⎜ t n −1,h ⎜ ⎜ t n − 2 ,h ⎜M ⎜⎜ ⎝ t1,h
0 1
0
0
0
0
t n −1,h 1
0
t 2 ,h
L
O t n −1,h
0 ⎞⎛ s1 N ⎞ ⎛ − t n −1, h ⎞ ⎟ ⎟⎜ ⎟ ⎜ 0 ⎟⎜ s 2 N ⎟ ⎜ − 2 tn − 2, h ⎟ ⎟ ⎜ ⎟ 0 ⎟⎜⎜ s3 N ⎟⎟ = ⎜ − 3tn −3, h ⎟ ⎟ M ⎟⎜ M ⎟ ⎜ M ⎟ ⎟⎟⎜ ⎟ ⎜⎜ 1 ⎠⎝ s nN ⎠ ⎝ − nt 0, h ⎟⎠
dengan matriks koefisien merupakan matriks segitiga bawah Toeplitz. SPL (3.1) dapat diselesaikan menggunakan algoritma subtitusi maju untuk mendapatkan nilai S1N,S2N,…,SnN
Pada langkah ke-2 Algoritma Turan, dilakukan iterasi Graeffe sebanyak h kali pada sebuah polinomial monik Mn(x). Prosedur dari algoritma Graeffe dengan h iterasi ditunjukan oleh algoritma dibawah ini. Input : Polinomial
t i ,1 ← t i ,1 + (−1) k t j .0 t k .0
Langkah 4: Setelah diperoleh SgN (g=1,2…,n) hitung nilai
⎛ S gN ⎜ * r = ⎜ max ⎜ g =1,..., n n ⎝
1 gn
⎞ ⎟ ⎟ ⎟ ⎠
1) n }
HASIL DAN PEMBAHASAN Pembuatan program algoritma Weyl digunakan software MATLAB 7.01 yang dilakukan pada komputer dengan sistem operasi Windows-Xp
2-44
END IF END FOR {mengalikan setiap koefisien S(x) dengan (-
−1
sebagai output dari algoritma Turan 4.
Pn ( x ) (berupa koefisien-
koefisien Polinomial {p0,p1,p2,…,pn}), banyak iterasi Graeffe h. FOR l 1 TO h DO FOR i 0 TO n DO {membuat koefisien S(x) setelah dilakukan satu iterasi Graeffe) ti,1 0; FOR j 0 TO n DO k 2i-j; IF k ≥ 0 AND k > n
t i.1 ← (−1) n t i.1 ; END FOR t 0 ← t1 ; END FOR
Secara keseluruhan prosedur dari Algoritma Turan ditunjukkan oleh algoritma berikut.
ISBN 979-545-027-1 @2006 ITS
Seminar Nasional Pascasarjana VI 2006, Surabaya Input : polinomial
Pn ( x )
(berupa
koefisien-
koefisien polinomial {p0,p1,p2,…,pn}), titik C ∈ R , bilangan asli N (log 2 N adalah iterasi maksimum Algoritma Graeffe) h ← log 2 N ; {menentukan koefisien polinomial translasi Tn(x) = Pn(C+ x)} q ← translasi (Pn(x),C) {menentukan koefisien polinomial balikan
Polinomial yang akan di uji P5(x)=x5+2x3-4x2+10, dengan faktor translasi C=1,2,3,4,5 dan banyak iterasi h = 2,4,8,12,16 dengan h = 2 log N P5(x)=x5+2x3-4x2+10 Tabel 4.1
⎛1⎞ Bn ( x) = x nTn ⎜ ⎟ } ⎝ x⎠
FOR i ← 1 TO n+1 DO
t (i ) ← q(n + 2 − i );
C
h
1 2 3 4 5
1 1 1 1 1
Nilai aproksimasi 0.8911 1.1181 1.1983 1.2582 1.3065
Tabel 4.2
END FOR {membuat polinomial monik} FOR i ← 1 TO n-1 DO t 0 (i ) ← t (i ) / t (n); END FOR
t 0 (n) ← 1; {melakukan iterasi Graeffe sebanyak h kali} t h ← Graeffe t 0, h
( )
{membuat matriks segitiga bawah Toeplitz} FOR i 1 TO n -1 DO FOR j 1 TO n-1 DO IF i >= j THEN k ← i − j; A(i,j) ← t h (n − k ); END IF END FOR END FOR {membuat matriks konstanta dari SPL} FOR i ← 1 TO n-1 DO B(i) ← −i * t h (n − i ); END FOR {menyelesaikan SPL dengan metode substitusi maju} S ← subtutusi maju (A,B) {mencari aproksimasi jarak terdekat akar dari Pn ( x ) dengan bilangan kompleks C} FOR g ← 1 TO n-1 DO
∧ * r (g ) ← (abs ( S ( g ) /( n − 1))) (1 /( g N )); END FOR Solusi ← (maks(r))(-1)
h
2 2 2 2 2
2 4 8 12 16
Nilai aproksimasi 0.7216 0.6640 0.6536 1.0002 1.0000
Dari Tabel 4.1 menunjukkan bahwa semakin besar faktor translasi dengan h = 1, maka nilai aproksimasi 1
akan menuju 5 N dimana N=2. Dari Tabel 4.2 menunjukkan bahwa nilai semakin besar iterasi yang dilakukan maka nilai aproksimasi akan konvergen ke satu dengan C=2. 5. PENUTUP
Dari hasil pembahasan dalam penelitian ini, dapat diambil kesimpulan bahwa nilai aproksimasi yang didapatkan dipengaruhi oleh besarnya faktor translasi dan banyaknya iterasi yang dilakukan, jika diperhatikan lebih lanjut maka pada iterasi lebih besar nilai aproksimasi akan konvergen ke satu. Nilai aproksimasi ini dapat digunakan pada algoritma Weyl untuk mencari akar-akar polinomial. REFERENSI
[1] [2]
Output : solusi {output dari Algoritma Turan} Percobaan dilakukan untuk melihat pengaruh dari: Faktor translasi Banyaknya iterasi. terhadap nilai aproksimasi yang didapatkan.
C
[3] [4] [5]
Bond,C. 2002. A Method for Finding Real and Complex Roots of Real Polynomials With Multiple Roots. Bond,C. 2003. A Robust Strategy for Finding All Real and Complex Roots of Real Polynomials. Golub, G. H. & Van Loan, C. F. 1996. Matrix Computations, Baltimore , Johns Hopkins University Press. Henrici, P. 1964. Elements of Numerical Analysis, New York:John Wiley. Kalman, D. 1999. A Matrix Proof of Newton’s Identities.
ISBN 979-545-027-1 @2006 ITS
2-45
Seminar Nasional Pascasarjana VI 2006, Surabaya [6] [7]
2-46
Paliouras, J.D. 1975. Complex Variables For Scientists And Engineers. Pan, V.Y. 1996. On Approximating polynomial Zeros: Modified Quadtree (Weyl’s) Construction and Improved Newton’s Iteration. Research report 2894, INRIA, Sophia-Antipolis, France.
[8] [9]
Pan, V.Y. 1997. Solving A Polynomial Equation: Some History And Recent Progress. SIAM Rev.Vol.39. Turan, P. 1984. On A New Method of Analysis and Its Applications, New Jersey, Willey and Sons.
ISBN 979-545-027-1 @2006 ITS
