SISTEM PERSAMAAN LINEAR ( BAGIAN II )

D1

1. FAKTORISASI MATRIKS

D2

2. METODE ITERASI UNTUK MENYELESAIKAN SPL

D3

3. NILAI EIGEN DAN VEKTOR EIGEN

D4

4. POWER METHOD

23/03/2016 Matematika FMIPA IPB

Beserta contoh soal untuk setiap subbab

1

SISTEM PERSAMAAN LINEAR ( BAGIAN II )

FAKTORISASI 𝑳𝑼

FAKTORISASI DOLITTLE 𝑳𝑫 𝑼𝑫

D1

FAKTORISASI CROUT 𝑳𝑪 𝑼𝑪 FAKTORISASI 𝑳𝑫𝑳𝑻 𝑪

𝑪 𝑻


2

FAKTORISASI CHOLESKY 𝑳 𝑳

• Suatu masalah yang sering dihadapi di dalam menyelesaikan SPL 𝑨𝒙 = 𝒃 adalah perlunya mendapatkan beberapa penyelesaian untuk berbagai vektor 𝒃, sedangkan matriks 𝑨 tetap. • Penggunaan metode eliminasi Gauss mengharuskan penyelesaian setiap SPL 𝑨𝒙 = 𝒃 secara terpisah untuk setiap vektor 𝒃 , dengan menggunakan operasi aritmetika yang pada prinsipnya sama sampai dilakukannya proses substitusi mundur (backward substitusion).


3

Sumber : //staff.uny.ac.id/sites/default/files/131930136/KomputasiNumerikBab2.pdf

• Suatu proses yang dikenal sebagai faktorisasi LU menangani permasalahan ini dengan hanya berkonsentrasi pada matriks koefisien 𝑨. • Metode Faktorisasi LU bermanfaat untuk komputer digital dan merupakan basis untuk banyak pemrograman komputer praktis.


4

Sumber : //staff.uny.ac.id/sites/default/files/131930136/KomputasiNumerikBab2.pdf

Penyelesaian 𝐴𝑥 = 𝑏 dengan faktorisasi LU 1. Bentuklah matriks 𝑳 dan 𝑼 dari 𝑨 2. Pecahkan 𝑳𝒚 = 𝒃, lalu hitung 𝒚 dengan teknik substitusi maju 3. Pecahkan 𝑼𝒙 = 𝒚, lalu hitung 𝒙 dengan teknik substitusi mundur

Hanya berlaku untuk Faktorisasi LU, Dolittle, dan Crout


5

Sumber : R.Munir 2003

FAKTORISASI 𝑳𝑼

Definisikan persamaan matriks 𝑨𝒙 = 𝒃, 𝑨 ∈ 𝑴𝒏×𝒏 dengan matriks 𝑨 dapat difaktorkan dalam bentuk 𝑨 = 𝑳𝑼 dimana: 𝑎12 𝑎22 𝑎32 ⋮ 𝑎𝑛2

𝑎13 𝑎23 𝑎33 ⋮ 𝑎𝑛3


⋯ ⋯ ⋯ ⋱ ⋯

𝑎1𝑛 1 𝑎2𝑛 𝑙21 𝑎3𝑛 = 𝑙31 ⋮ ⋮ 𝑎𝑛𝑛 𝑙𝑛1

0 1

0 0 1 ⋮

𝑙32 ⋮ 𝑙𝑛2 𝑙𝑛3

⋯ ⋯ ⋯ ⋱ ⋯

0 𝑢11 0 0 0 0 ⋮ ⋮ 1 0

𝑢12 𝑢13 𝑢22 𝑢23 0 𝑢33 ⋮ ⋮ 0 0

⋯ ⋯ ⋯ ⋱ ⋯

𝑢1𝑛 𝑢2𝑛 𝑢3𝑛 ⋮ 𝑢𝑛𝑛

6

𝑎11 𝑎21 𝑎31 ⋮ 𝑎𝑛1

Contoh soal Faktorkan matriks 𝐴 berikut 2 4 𝐴 = 1 −1 4 1

−2 5 −2

6 𝑏= 0 2


7

Sumber : //staff.uny.ac.id/sites/default/files/131930136/KomputasiNumerikBab2.pdf.page 82.

Penyelesaian

2 4 𝐴 = 1 −1 4 1

faktor pengali 𝑚21

−2 5 −2

𝟏 𝑅2 − 𝑅 𝟐 1 ~ 𝑅3 − 𝟐 𝑅1

2 4 0 −3 0 −7

−2 6 = 𝐴1 2


1 0 𝟏 𝑀1 = − 1 𝟐 −𝟐 0

0 0 1

Bukti :


8

𝑴𝟏 𝑨 = 𝑨𝟏


elemen pivotnya

2 4 𝐴1 = 0 −3 0 −7

−2 6 2

𝑅3 −

𝑀2 =

𝟕 𝑅 𝟑 2 ~

1 0 0

2 0 0

0 1 𝟕 𝟑

4 −3 0

−2 6 = 𝐴2 −12

0 0 1

Bukti :


9

𝑴𝟐 𝑨𝟏 = 𝑨𝟐

𝑴𝟏 𝑨 = 𝑨𝟏 Bentuk Umum :

𝑴𝟐 𝑨𝟏 = 𝑨𝟐

−𝟏 𝑳 = 𝑴𝟏−𝟏 𝑴−𝟏 … 𝑴 𝟐 𝒏−𝟏

𝑴𝟐 𝑴𝟏 𝑨 = 𝑨𝟐

𝑳 23/03/2016 Matematika FMIPA IPB

𝑨𝟐

𝑼 = 𝑨𝒏−𝟏

𝑼 10

𝑨 = 𝑴𝟏−𝟏 𝑴−𝟏 𝟐

𝑳


0 0 1

2 0 0

4 −2 2 −3 6 = 1 0 −12 4

𝑼

4 −2 −1 5 1 −2

𝑨

11

𝑀1−1 𝑀2−1 𝐴2 =

1 0 1 1 2 7 2 3

1 0 1 1 𝐿𝑦 = 𝑏 → 2 7 2 3

0 𝑦1 6 0 𝑦 2 = 0 𝑦3 2 1

𝑦1 = 6, 𝑦2 = −3, 𝑦3 = −3. 2 𝑈𝑥 = 𝑦 → 0 0

4 −3 0 1

−2 𝑥1 6 𝑥2 = −3 6 −12 𝑥3 −3 3

1

𝑥1 = 4, 𝑥2 = 2, 𝑥3 = 4

Jadi, solusi SPLnya adalah

Matematika FMIPA IPB

𝑇

12

23/03/2016

1 3 1 𝑥= , , 4 2 4

FAKTORISASI DOLITTLE Tinjau matriks 3 × 3 berikut : 𝑎11 𝐴 = 𝑎21 𝑎31

𝑎12 𝑎22 𝑎32

𝑎13 𝑎23 𝑎33

1 𝐿𝐷 = 𝑙21 𝑙31

0 1 𝑙32

0 0 1

𝑢11 𝑈𝐷 = 0 0

𝑢12 𝑢22 0

𝑢 𝑢23 𝑢33

hasil perkalian 𝐿 dan 𝑈 dapat ditulis 𝑢11 𝑢12 𝑢13 𝑙21 𝑢12 + 𝑢22 𝑙21 𝑢13 + 𝑢23 𝐿𝐷 𝑈 𝐷 = 𝑙21 𝑢11 𝑙31 𝑢13 𝑙31 𝑢12 + 𝑙32 𝑢22 𝑙31 𝑢13 + 𝑙32 𝑢23 + 𝑢33


𝑎12 𝑎22 𝑎32

𝑎13 𝑎23 = 𝐴 𝑎33 Sumber : R.Munir 2003

13

𝑎11 = 𝑎21 𝑎31

Dari kesamaan dua buah matriks 𝐿𝑈 = 𝐴, diperoleh

𝑢11 = 𝑎11 , 𝑢12 = 𝑎12 , 𝑢13 = 𝑎13 𝑎21 𝑢11 𝑎31 = 𝑢11

Baris Pertama 𝑈

𝑙21 𝑢11 = 𝑎21 → 𝑙21 =

𝑙21 𝑢12 + 𝑢22 = 𝑎22 → 𝑢22 = 𝑎22 − 𝑙21 𝑢12

𝑙21 𝑢13 + 𝑢23 = 𝑎23 → 𝑢23 = 𝑎23 − 𝑙21 𝑢13

𝑙31 𝑢12 + 𝑙32 𝑢22 = 𝑎32 → 𝑙32

𝑎32 − 𝑙31 𝑢12 = 𝑢22

Baris Kedua 𝑈

Kolom Kedua 𝐿

𝑙31 𝑢13 + 𝑙32 𝑢23 + 𝑢33 = 𝑎33 → 𝑢33 = 𝑎33 − (𝑙31 𝑢13 + 𝑙32 𝑢23 ) 23/03/2016 Matematika FMIPA IPB

Baris Ketiga 𝑈


14

𝑙31 𝑢11 = 𝑎31 → 𝑙31

Kolom Pertama 𝐿

Contoh soal Selesaikan dengan faktorisasi 𝐿𝑈 SPL berikut : 2𝑥1 + 4𝑥2 − 2𝑥3 = 6 𝑥1 − 𝑥2 + 5𝑥3 = 0 4𝑥1 + 𝑥2 − 2𝑥3 = 2


15

Dalam hal ini 𝐿 dan 𝑈 dihitung dengan faktorisasi Dollitle.

Penyelesaian : 2 4 𝐴 = 1 −1 4 1

−2 5 −2

6 𝑏= 0 2

Diperoleh :

𝑎21 1 𝑙21 = = 𝑢11 2 𝑎31 4 𝑙31 = = =2 𝑢11 2


𝑢23 = 𝑎23 − 𝑙21 𝑢13

𝑙32 =

𝑎32 − 𝑙31 𝑢12 1 − 2(4) 7 = = 𝑢22 −3 3

𝑢33 = 𝑎33 − 𝑙31 𝑢13 + 𝑙32 𝑢23 7 = −2 − 2 −2 + 6 3

= −12

16

𝑢11 = 𝑎11 = 2 𝑢12 = 𝑎12 = 4 𝑢13 = 𝑎13 = −2

1 4 = −3 2 1 =5− −2 = 6 2

𝑢22 = 𝑎22 − 𝑙21 𝑢12 = −1 −

Diperoleh 𝐿𝐷 dan 𝑈 𝐷 sebagai berikut,

1 𝐿𝐷

=

1 2

2

0 0 1 0 7 3

𝑈𝐷

1

2 4 −2 = 0 −3 6 0 0 −12

dan

6 𝑏= 0 2

Berturut-turut dihitung 𝑦 dan 𝑥 :

𝑦1 = 6, 𝑦2 = −3, 𝑦3 = −3 1 4

3 2

𝑥1 = , 𝑥2 = , 𝑥3 =

1 4

Jadi, solusi SPL di atas adalah


𝑇

17

1 3 1 𝑥= , , 4 2 4

FAKTORISASI CROUT Faktorisasi Crout menghasilkan 𝑨 = 𝑳𝑼, dengan 𝑳 = 𝑳𝑫 𝑫 dan 𝑼 = 𝑫−𝟏 𝑼𝑫 , 𝑨 = 𝑳𝑫 𝑼𝑫 adalah hasil faktorisasi Dolittle dan 𝑫 matriks diagonal dari 𝑼𝑫


2 0 𝐷 = 0 −3 0 0

0 0 −12

𝑈𝐷

2 = 0 0

4 −3 0

−2 6 −12

1 2

0

𝐷 −1 = 0

−

0

0

1 3

0 0 −

1 12

18

Sumber : //staff.uny.ac.id/site s/default/files/131 930136/Komputas iNumerikBab2.pdf. page 87.

1 0 0 1 1 0 𝐿𝐷 = 2 7 2 1 3

1 1 𝐿𝐶 = 𝐿𝐷 𝐷 = 2

𝑈𝐶

=

𝐷 −1 𝑈𝐷

𝐿𝐶 𝑈 𝐶

1 0

2

7 1 3

1 2

0

1 = 0 − 3 0

Bukti

0 0

0

2 0 0

0 0 1 0 −3 0 = 1 −3 0 −12 4 −7

0 0 −12

0 0 1 − 12

2 0 0

4 −2 1 2 −3 6 = 0 1 0 −12 0 0

−1 −2 1

1 0 0 1 2 −1 1 0 0 1 2 −1 = 1 −3 0 0 1 −2 = 1 −3 0 0 1 −2 4 −7 −12 0 0 1 4 −7 −12 0 0 1 2 4 = 1 −1 4 1

−2 5 =𝐴 −2


sebelumnya untuk menghasilkan 𝒙 =

𝟏 𝟑 𝟏 𝑻 , , 𝟒 𝟐 𝟒

19

lakukan hal yang sama untuk menghasilkan 𝒚 dan 𝒙 seperti

FAKTORISASI 𝑳𝑫𝑳𝑻 Syarat: 𝑨 harus matriks simetrik yaitu 𝒂𝒊𝒋 = 𝒂𝒋𝒊

𝐿𝑈 = 𝐴 = 𝐴𝑇 = 𝐿𝑈 𝐿𝑈 = 𝑈 𝑇 𝐿𝑇 𝑈 = 𝐿−1 𝑈𝑇 𝐿𝑇 𝑈 𝐿𝑇 −1 = 𝐿−1 𝑈 𝑇 𝑫 = 𝑳−𝟏 𝑼𝑻

𝑇

𝐿𝐷 = 𝑈 𝑇 𝐿𝐷 𝑇 = 𝑈 𝐷 𝑇 𝐿𝑇 = 𝑈 𝐷𝐿𝑇 = 𝑈


Sumber : W. Cheney, D. Kincaid. 2008

20

Sehingga 𝐿𝐷𝐿𝑇 = 𝐿𝑈 = 𝐴

Contoh soal Tentukan Faktorisasi 𝑳𝑫𝑳𝑻 dari matriks berikut

4 3 𝐴= 2 1

3 3 2 1

2 2 2 1

1 1 1 1


21


Penyelesaian :

𝑨 = 𝑳𝑼 =

𝑫 = 𝑳−𝟏 𝑼𝑻 =


=𝑨

22

𝑳𝑫𝑳𝑻 =

FAKTORISASI 𝑪𝑯𝑶𝑳𝑬𝑺𝑲𝒀 Syarat : 𝑨 simetrik definit positif (semua diagonal utama (+) ). Sehingga 𝟏 𝟐

𝑫 dapat diperoleh.


1 𝑇 𝐷2 𝐿𝑇

= 𝐿𝐶𝐻 𝐿𝐶𝐻

𝑇


23

𝐴 = 𝐿𝐷𝐿𝑇 =

1 𝐿𝐷 2

Contoh soal Tentukan Faktorisasi 𝑪𝑯𝑶𝑳𝑬𝑺𝑲𝒀 berikut


3 3 2 1

2 2 2 1

1 1 1 1


24

4 𝐴= 3 2 1

dari matriks

Penyelesaian :

=

𝟏 𝑳𝑫𝟐

𝑳𝑪𝑯 𝑳𝑪𝑯

𝑻


=𝑨

25

𝑳𝑪𝑯

SOLUSI ITERATIF DARI PERSAMAAN LINEAR

ILL – CONDITION

BILANGAN KONDISI MATRIKS

D2

METODE ITERATIF DASAR

ITERASI JACOBI


SUCCESIVE OVER-RELAXATION (SOR)

26

ITERASI GAUSS – SEIDEL

ILL – CONDITION

1. Matriks 𝑨 dikatakan berkondisi buruk ( ill – condition ) jika terdapat sebuah vektor kolom 𝒃 sehingga untuk perubahan kecil 𝑨 atau 𝒃 akan menghasilkan perubahan besar pada solusi 𝒙 = 𝑨−𝟏 𝒃. 2. Sistem 𝑨𝒙 = 𝒃 dikatakan berkondisi buruk bila 𝑨 berkondisi buruk. 3. Apabila sistem 𝑨𝒙 = 𝒃 berkondisi buruk, hasil perhitungannya mempunyai galat yang besar.


27


Contoh soal Tinjau SPL berikut : 𝒙𝟏 + 𝟐𝒙𝟐 = 𝟏𝟎 𝟏. 𝟏𝒙𝟏 + 𝟐𝒙𝟐 = 𝟏𝟎. 𝟒

yang memiliki solusi sejati 𝒙𝟏 = 𝟒 dan 𝒙𝟐 = 𝟑. Jika sekarang 𝒂𝟐𝟏 = 𝟏. 𝟏 diubah menjadi 𝟏. 𝟎𝟓, 𝒙𝟏 + 𝟐𝒙𝟐 = 𝟏𝟎 𝟏. 𝟎𝟓𝒙𝟏 + 𝟐𝒙𝟐 = 𝟏𝟎. 𝟒 diperoleh 𝒙𝟏 = 𝟖 dan 𝒙𝟐 = 𝟏.



28

Penambahan sebesar 𝜺 pada koefisien 𝟏. 𝟏 dinyatakan sebagai berikut : 𝒙𝟏 + 𝟐𝒙𝟐 = 𝟏𝟎 𝟏. 𝟏 + 𝜺 𝒙𝟏 + 𝟐𝒙𝟐 = 𝟏𝟎. 𝟒

Yang mempunyai solusi 𝟎. 𝟒 𝒙𝟏 = 𝟎. 𝟏 + 𝜺 𝟎. 𝟔 + 𝟏𝟎𝜺 𝒙𝟐 = 𝟎. 𝟐 + 𝟐𝜺 Solusi ini memperlihatkan bahwa sistem berkondisi buruk sebab perubahan kecil 𝜺 menghasilkan perubahan besar pada solusi SPL.


29

Pada contoh di atas, 𝜺 = −𝟎. 𝟎𝟓, sehingga 𝟎. 𝟒 𝒙𝟏 = =𝟖 𝟎. 𝟏 − 𝟎. 𝟎𝟓 𝟎. 𝟔 − 𝟏𝟎 𝟎. 𝟎𝟓 𝒙𝟐 = =𝟏 𝟎. 𝟐 − 𝟐 𝟎. 𝟎𝟓

4. Beberapa ukuran untuk kondisi buruk telah dikemukakan para ahli numerik, antara lain 𝒅𝒆𝒕 𝑨 sangat kecil dibandingkan dengan nilai maksimum |𝒂𝒊𝒋 | dan 𝒃𝒊 .


30

5. Ukuran determinan sukar dikaitkan dengan kondisi buruk. Kesukaran tersebut dapat diatasi bila SPL dinormalkan sedemikian sehingga koefisien terbesar pada tiap baris persamaan sama dengan 1.

Contoh soal Tentukan determinan matriks 𝑨 pada SPL berikut 𝒙𝟏 + 𝟐𝒙𝟐 = 𝟏𝟎 𝟏. 𝟏𝒙𝟏 + 𝟐𝒙𝟐 = 𝟏𝟎. 𝟒 bila : ( i ) SPL tanpa penormalan


31

( ii ) SPL dinormalkan

Penyelesaian : ( i ) SPL tanpa penormalan 𝒅𝒆𝒕 𝑨 = 𝟏 𝟐 − 𝟏. 𝟏 𝟐 = −𝟎. 𝟐 yang dekat dengan nol, karena itu SPL berkondisi buruk.

( ii ) SPL dinormalkan Penormalan menghasilkan 𝟎. 𝟓𝒙𝟏 + 𝒙𝟐 = 𝟓 𝟎. 𝟓𝟓𝒙𝟏 + 𝒙𝟐 = 𝟓. 𝟐 sehingga, 𝒅𝒆𝒕 𝑨 = 𝟎. 𝟓 𝟏 − 𝟏 𝟎. 𝟓𝟓 = −𝟎. 𝟓𝟓


32

yang dekat ke nol, karena itu berkondisi buruk.

Contoh soal Tentukan determinan matriks 𝑨 pada SPL berikut 𝟑𝒙𝟏 + 𝟐𝒙𝟐 = 𝟏𝟖 −𝒙𝟏 + 𝟐𝒙𝟐 = 𝟐 bila ( i ) SPL tanpa penormalan,


33

( ii ) SPL dinormalkan

Penyelesaian : ( i ) SPL apa adanya 𝒅𝒆𝒕 𝑨 = 𝟑 𝟐 − 𝟐 −𝟏 = 𝟖 yang nilainya jauh dari nol, karena itu SPL berkondisi baik.

( ii ) SPL dinormalkan Penormalan menghasilkan 𝒙𝟏 + 𝟎. 𝟔𝟔𝟕𝒙𝟐 = 𝟔 −𝟎. 𝟓𝒙𝟏 + 𝒙𝟐 = 𝟏 sehingga, 𝒅𝒆𝒕 𝑨 = 𝟏 𝟏 − 𝟎. 𝟔𝟔𝟕 −𝟎. 𝟓 = 𝟏. 𝟑𝟑𝟑


34

yang nilainya jauh dari nol, karena itu berkondisi baik.

Walaupun terdapat beragam cara untuk memeriksa kondisi

sistem, akan lebih disukai mendapatkan bilangan tunggal yang dapat berlaku sebagai petunjuk adanya kondisi buruk.


35

Bilangan tersebut dinamakan “ bilangan kondisi matriks “.

BILANGAN KONDISI MATRIKS

Misal SPL 𝑨𝒙 = 𝑩, bilangan kondisi matriks dinyatakan sebagai :

𝜿 𝑨 = 𝑨

𝑨−𝟏

Yang dalam hal ini 𝑨 adalah norma ( norm ) tak – hingga matriks 𝑨, yang didefinisikan sebagai : 𝒏


∞

= max

𝟏≤𝒊≤𝒏

|𝒂𝒊𝒋 | 𝒋=𝟏


36

𝑨 = 𝑨

Teorema Sistem persamaan linear 𝑨𝒙 = 𝒃 yang bilangan kondisinya kecil menyatakan sistem berkondisi baik. Bilangan kondisi besar menandakan bahwa sistem berkondisi buruk.


37

“ Jika bilangan kondisi matriks 𝑨 besar, maka galat relatif solusi SPL juga akan besar. Sebaliknya, jika bilangan kondisinya kecil, galat relatif solusi SPL juga kecil “.

Contoh soal Hitung bilangan kondisi matriks 𝑨 berikut


38

𝟑. 𝟎𝟐 −𝟏. 𝟎𝟓 𝟐. 𝟓𝟑 𝑨 = 𝟒. 𝟑𝟑 𝟎. 𝟓𝟔 −𝟏. 𝟕𝟖 −𝟎. 𝟖𝟑 −𝟎. 𝟓𝟒 𝟏. 𝟒𝟕

Penyelesaian : Tentukan terlebih dahulu matriks balikannya,

𝟑. 𝟎𝟐 −𝟏. 𝟎𝟓 𝟐. 𝟓𝟑 𝑨 = 𝟒. 𝟑𝟑 𝟎. 𝟓𝟔 −𝟏. 𝟕𝟖 , −𝟎. 𝟖𝟑 −𝟎. 𝟓𝟒 𝟏. 𝟒𝟕

𝑨−𝟏

𝟓. 𝟔𝟔𝟏 −𝟕. 𝟐𝟕𝟑 −𝟏𝟖. 𝟓𝟓 = 𝟐𝟎𝟎. 𝟓 −𝟐𝟔𝟖. 𝟑 −𝟔𝟔𝟗. 𝟗 𝟕𝟔. 𝟖𝟓 −𝟏𝟎𝟐. 𝟔 −𝟐𝟓𝟓. 𝟗

maka dapat dihitung 𝑨 = 𝟒. 𝟑𝟑 + 𝟎. 𝟓𝟔 + 𝟏. 𝟕𝟖 = 𝟔. 𝟔𝟕 𝑨

−𝟏

= 𝟐𝟎𝟎. 𝟓 + −𝟐𝟔𝟖. 𝟑 + −𝟔𝟔𝟗. 𝟗 = 𝟏𝟏𝟑𝟖. 𝟕

sehingga bilangan kondisi matriks 𝑨 adalah 𝜿 𝑨 = 𝟔𝟔. 𝟕 𝟏𝟏𝟑𝟖. 𝟕 = 𝟕𝟓𝟗𝟓


39

Jadi, sistem tersebut berkondisi buruk, karena bilangan kondisinya besar.

Tinjau SPL 𝑎11 𝑥1 + 𝑎12 𝑥2 + … + 𝑎1𝑛 𝑥𝑛 = 𝑏1 𝑎21 𝑥1 + 𝑎22 𝑥2 + … + 𝑎2𝑛 𝑥𝑛 = 𝑏2 . . . . 𝑎𝑛1 𝑥1 + 𝑎𝑛2 𝑥2 + … + 𝑎𝑛𝑛 𝑥𝑛 = 𝑏𝑛 Syarat 𝑎𝑘𝑘 ≠ 0, 𝑘 = 1,2, … 𝑛, maka persamaan iterasinya : (𝑘−1)

𝑥2 (𝑘) =

𝑎11

𝑏2 − 𝑎21 𝑥1

𝑘−1

. . 𝑥𝑛

(𝑘)

=


𝑏𝑛 − 𝑎𝑛1 𝑥1

(𝑘−1)

… − 𝑎1𝑛 𝑥𝑛

𝑘−𝟏

− 𝑎23 𝑥3 𝑘−1 − ⋯ −𝑎2𝑛 𝑥𝑛 (𝑘−1) 𝑎22 . . − 𝑎𝑛2 𝑥2 𝑘−𝟏 − ⋯ −𝑎𝑛𝑛−1 𝑥𝑛−1 (𝑘−𝟏) 𝑎𝑛𝑛

40

𝑥1 (𝑘) =

𝑏1 − 𝑎12 𝑥2

Iterasi dimulai dengan memberikan tebakan awal untuk 𝑥,

𝑥0 =

0 𝑥1

0 , 𝑥2

0 , … , 𝑥𝑛

𝑇

Iterasi berhenti jika (𝑘−1)

− 𝑥𝑖 (𝑘) 𝑥𝑖


<𝜀

𝑖 = 1,2,3, … , 𝑛

41

(𝑘)

𝑥𝑖

METODE ITERASI JACOBI

Misalkan diberikan tebakan awal 𝑥 (0) :

𝑥0 =

0 𝑥1

0 , 𝑥2

0 , … , 𝑥𝑛

𝑇

Proedur iterasi untuk iterasi pertama, kedua, dan seterusnya adalah sebagai berikut :


42


Iterasi pertama :

𝑥𝑛

𝑥1

(1)

𝑥2

(1)

(1)

=

𝑥1

(2)

𝑥2

(2)

= =

𝑏1 − 𝑎12 𝑥2

0

− 𝑎13 𝑥3 𝑎11

0

− ⋯ −𝑎1𝑛 𝑥𝑛 (0)

𝑏2 − 𝑎21 𝑥1

0

− 𝑎23 𝑥3 𝑎22

0

− ⋯ −𝑎2𝑛 𝑥𝑛 (0)


0

− 𝑎𝑛2 𝑥2 0 − ⋯ −𝑎𝑛𝑛−1 𝑥𝑛−1 (0) 𝑎𝑛𝑛

Iterasi kedua :


=

=

1

− 𝑎13 𝑥3 𝑎11

1

− ⋯ −𝑎1𝑛 𝑥𝑛 (1)

𝑏2 − 𝑎21 𝑥1

1

− 𝑎23 𝑥3 𝑎22

1

− ⋯ −𝑎2𝑛 𝑥𝑛 (1)


1

− 𝑎𝑛2 𝑥2 1 − ⋯ −𝑎𝑛𝑛−1 𝑥𝑛−1 (1) 𝑎𝑛𝑛

dst...... 43

𝑥𝑛

(2)

=

𝑏1 − 𝑎12 𝑥2

Rumus umum 𝑛 (𝑘) 𝑥𝑖

= − 𝑗=1 𝑖≠1

𝑎𝑖𝑗 𝑏𝑖 𝑘−1 𝑥𝑗 + 𝑎𝑖𝑖 𝑎𝑖𝑖

(1 ≤ 𝑖 ≤ 𝑛)

Syarat Kekonvergenan :

1.

𝒂𝒊,𝒊 > 𝒂𝒊,𝟏 + … + 𝒂𝒊,𝒊−𝟏 + … + | 𝒂𝒊,𝒏 |



44

2. 𝒎𝒂𝒙 𝒙𝒊 < 𝟏

Contoh soal Tentukan banyaknya iterasi dengan menggunakan Iterasi Jacoby 𝟐 −𝟏 𝑨 = −𝟏 𝟑 𝟎 −𝟏

Dengan nilai awal

𝑥1

𝟎 −𝟏 𝟐

0

𝟏 𝒃= 𝟖 −𝟓 0

0

, 𝑥2 , 𝑥3

= (0,0,0).



45

(4 angka di belakang koma).

Penyelesaian : Konvergen jika : 𝒂𝒊,𝒊 > 𝒂𝒊,𝟏 + … + 𝒂𝒊,𝒊−𝟏 + … + | 𝒂𝒊,𝒏 |

Untuk 𝑖 = 1 2 > −1 + 0


46

Berlaku pula untuk 𝑖 = 2 dan 𝑖 = 3.

Metode iterasi Jacobi. Persamaan iterasinya :

𝑘 𝑥1 𝑘

𝑥2

𝑘

𝑥3

1 𝑘−1 1 = 𝑥2 + 2 2 1 𝑘−1 1 𝑘−1 8 = 𝑥1 + 𝑥3 + 3 3 3 1 𝑘−1 5 = 𝑥2 − 2 2

Iterasinya :


= 0,0,0

𝑇

𝑥

1

= 0.5000, 2.6667, −2.5000

𝑇

𝑥

2

= 1.8333,2.0000, −1.1667 ⋮

𝑇

21

= 2.0000, 3.0000, −1.0000

𝑥 23/03/2016

0

𝑇

47

𝑥

SCILAB PROGRAM : ITERASI JACOBI Input + Output

𝑥

𝑥 23/03/2016 Matematika FMIPA IPB

21

21

Hasil secara analitik : = 2.0000, 3.0000, −1.0000

𝑇

:

Hasil secara komputasi = 1.9999915, 2.9999492, −1.0000085

𝑇

48

Program

METODE ITERASI GAUSS – SEIDEL

Kecepatan konvergen pada iterasi Jacobi dapat dipercepat bila setiap harga 𝑥𝑖 yang baru dihasilkan segera dipakai pada persamaan berikutnya untuk menentukan harga 𝑥𝑖+1 yang



49

lainnya.

Iterasi pertama :

𝑥2 (1) = 𝑥3 (1) =

𝑥4 (1) =


0

− 𝑎13 𝑥3 𝑎11

0

− 𝑎14 𝑥4

𝑏2 − 𝑎21 𝑥1

1

− 𝑎23 𝑥3 𝑎22

0

− 𝑎24 𝑥4

𝑏3 − 𝑎31 𝑥1

1

− 𝑎32 𝑥2 𝑎33

1

− 𝑎34 𝑥4

𝑏4 − 𝑎41 𝑥1

1

− 𝑎42 𝑥2 𝑎44

1

− 𝑎43 𝑥3

(0)

(0)

(1)

50

𝑥1 (1) =

(0)

𝑏1 − 𝑎12 𝑥2

Iterasi kedua :

𝑥1 (2) =

𝑥2 (2) = 𝑥3 (2) = 𝑥4 (2) =

(1)

𝑏1 − 𝑎12 𝑥2

1

− 𝑎13 𝑥3 𝑎11

1

− 𝑎14 𝑥4

𝑏2 − 𝑎21 𝑥1

2

− 𝑎23 𝑥3 𝑎22

1

− 𝑎24 𝑥4

𝑏3 − 𝑎31 𝑥1

2

− 𝑎32 𝑥2 𝑎33

2

− 𝑎34 𝑥4

𝑏4 − 𝑎41 𝑥1

2

− 𝑎42 𝑥2 𝑎44

2

− 𝑎43 𝑥3

(1)

(1)

(2)


51

dan seterusnya .......

Rumus umum (𝑘) 𝑥𝑖

= − 𝑗=1 𝑗<𝑖


𝑎𝑖𝑗 𝑘 𝑥𝑗 − 𝑎𝑖𝑖

𝑛

𝑗=1 𝑗>𝑖

𝑎𝑖𝑗 𝑏𝑖 𝑘−1 𝑥𝑗 + 𝑎𝑖𝑖 𝑎𝑖𝑖


52

𝑛

Contoh soal Tentukan banyaknya iterasi dengan menggunakan Iterasi Gauss – Seidel 𝟐 −𝟏 𝑨 = −𝟏 𝟑 𝟎 −𝟏

Dengan nilai awal

𝑥1

𝟎 −𝟏 𝟐

0

𝟏 𝒃= 𝟖 −𝟓 0

0

, 𝑥2 , 𝑥3

= (0,0,0).



53


Penyelesaian : Metode iterasi Gauss – Seidel . Persamaan iterasinya : 1 𝑘−1 1 𝑘 𝑥1 = 𝑥2 + 2 2 𝑘

= 𝑥1

1 3

𝑘

+ 𝑥3

𝑘

= 𝑥2 −

1 2

𝑘

5 2

𝑥2

𝑥3

1 3

𝑘−1

+

8 3

Iterasinya :


0

= 0,0,0

𝑇

𝑥

1

= 0.5000, 2.8333, −1.0833

𝑇

𝑥

2

= 1.9167,2.9444, −1.0278 ⋮

𝑇

𝑥

9

= 2.0000, 3.0000, −1.0000

𝑇

54

𝑥

SCILAB PROGRAM : ITERASI GAUSS – SEIDEL Input + Output

𝑥

𝑥 23/03/2016 Matematika FMIPA IPB

9

9

Hasil secara analitik : = 2.0000, 3.0000, −1.0000 𝑇 :

Hasil secara komputasi = 1.9998857, 2.9999238, −1.0000385

𝑇

55

Program

Succesive Over-Relaxation (SOR)


56

Formula SOR :

Contoh soal Tentukan banyaknya iterasi dengan menggunakan iterasi SOR 𝟐 −𝟏 𝑨 = −𝟏 𝟑 𝟎 −𝟏

Dengan nilai awal

𝑥1

𝟎 −𝟏 𝟐

0

𝟏 𝒃= 𝟖 −𝟓 0

0

, 𝑥2 , 𝑥3

= (0,0,0).


57


Penyelesaian : Masukkan kedalam formula :

dengan


58

Banyaknya iterasi :

Iterasi jacobi :

Iterasi Gauss – Seidel :


59

SOR :

3. NILAI EIGEN DAN VEKTOR EIGEN

D3

SIFAT – SIFAT NILAI EIGEN

TEOREMA GERSHGORIN


60

SINGULAR VALUE DECOMPOSITION

Definisi Misalkan 𝐴 adalah matriks 𝑛 × 𝑛, maka vektor yang tak nol 𝑥 di 𝑅𝑛 disebut vektor eigen dari 𝐴 jika 𝐴𝑥 adalah kelipatan skalar dari 𝑥, yaitu 𝐴𝑥 = 𝜆𝑥 untuk suatu skalar 𝜆. Skalar 𝜆 dinamakan nilai eigen 𝐴. Untuk menentukan nilai eigen dari matriks 𝑨 dapat menggunakan persamaan karakteristik dari matriks 𝑨 yaitu :


61

det(𝐴 − 𝜆𝐼) = 0

Contoh soal Tentukan nilai eigen dan vektor eigen dari matriks berikut


2 4

62

3 𝐴= 1

Penyelesaian :

3−𝜆 2 =0 1 4−𝜆 ⟺ 3−𝜆 4−𝜆 −2=0 ⟺ 𝜆2 −7𝜆 + 10 = 0 ⟺ 5−𝜆 2−𝜆 =0

𝑝 𝜆 = det 𝐴 − 𝜆𝐼 =

- Dari polinomial karakteristik diperoleh nilai eigen 5 dan 2. - Untuk nilai eigen 5, maka vektor eigennya x =

1 . 1


63

2 - Untuk nilai eigen 2, maka vektor eigennya x = . −1

SIFAT – SIFAT NILAI EIGEN

1. Jika 𝜆 nilai eigen 𝐴 →𝑝(𝜆) adalah nilai eigen dari 𝑝(𝐴) untuk suatu polinomial 𝑃. Khususnya 𝜆𝑘 nilai eigen dari 𝐴𝑘 . 2. Jika 𝐴 nonsingular dan 𝜆 nilai eigen 𝐴 → 𝑝(𝜆−1 ) adalah nilai eigen dari 𝑃(𝐴−1 ) untuk suatu polinomial 𝑃. Khususnya 𝜆−1 nilai eigen dari 𝐴−1 . 3. Jika 𝐴 matriks real dan simetrik maka nilai eigennya real. 4. Jika 𝐴 kompleks dan hermitian nilai eigennya real.

5. Jika 𝐴 hermitian dan definit positif maka nilai eigennya positif.


64

6. Jika 𝑃 nonsingular maka 𝐴 dan 𝑃𝐴𝑃−1 ( similar ) mempunyai nilai eigen yang sama.

TEOREMA GERSHGORIN


65

Semua nilai eigen dari suatu matriks 𝐴 ∈ ℂ𝑛×𝑛 termuat dalam 𝑛 cakram 𝐶𝑖 = 𝐶𝑖 (𝑎𝑖𝑖 , 𝑟𝑖 ) dalam bidang kompleks dengan pusat 𝑎𝑖𝑖 dan jari-jari 𝑟𝑖 yang didapat dari penjumlahan besaran entri – entri tak diagonal di baris ke - 𝑖.

Region yang memuat Nilai Eigen Matriks 𝐴 : 𝑛

𝑛

𝐶𝑖 = 𝑖=1

𝒛 ∈ ℂ ∶ 𝒛 − 𝑎𝑖𝑖 ≦ 𝑟𝑖 𝑖=1

dimana jari – jarinya adalah


𝒏 𝒋=𝟏 𝒋≠𝒊

𝒂𝒊𝒋

66

𝒓𝒊 =

Akibat


67

Semua nilai eigen dari suatu matriks A ∈ ℂ𝑛×𝑛 termuat dalam 𝑛 cakram 𝐷𝑖 = 𝐷𝑖 (𝑎𝑖𝑖 , 𝑠𝑖 ) dalam bidang kompleks dengan pusat 𝑎𝑖𝑖 dan jari-jari 𝑠𝑖 yang didapat dari penjumlahan besaran entri-entri tak diagonal di kolom matriks 𝐴.

Region yang memuat Nilai Eigen Matriks A: 𝑛 𝑖=1 𝐷𝑖

𝑛 𝑖=1

=

𝒛 ∈ ℂ ∶ 𝒛 − 𝑎𝑖𝑖 ≦ 𝑠𝑖

dimana Jari-jarinya adalah

𝑠𝑖 =

𝑛 𝒊=1 𝒊≠𝒋

𝑎𝑖𝑗

Akibatnya, Region yang memuat Nilai Eigen Matriks

A=

𝐶𝑖 𝑖=1


𝑛

𝐷𝑖 𝑖=1

68

𝑛

Contoh soal Misalkan matriks


𝒊 𝟐 −𝟓

69

𝟒−𝒊 𝟐 𝑨 = −𝟏 𝟐𝒊 𝟏 −𝟏

Penyelesaian :

𝟒−𝒊 𝟐 𝒊 𝑨 = −𝟏 𝟐𝒊 𝟐 𝟏 −𝟏 −𝟓 Di lihat dari baris 𝐴, kita peroleh region cakram Gershgorin sbb: 𝐶1 (4 − 𝑖, 3) , 𝐶2 (2𝑖, 3) , dan 𝐶3 (−5, 2). Dilihat

dari

kolom

𝐴 ,

kita

peroleh

region

cakram

Gershgorin sbb: 𝐷1 (4 − 𝑖, 2) , 𝐷2 (2𝑖, 3) , dan 𝐷3 (−5, 3).


𝐷1 (4 − 𝑖, 2 ), 𝐶2 (2𝑖, 3) , dan 𝐶3 (−5, 2).

70

Irisan (Intersection) dari kedua region cakram sbb:

Jari-jari

𝐶1 (4 − 𝑖, 3) , 𝐶2 (2𝑖, 3) , dan 𝐶3 (−5, 2).

𝐷1 (4 − 𝑖, 2) , 𝐷2 (2𝑖, 3) , dan 𝐷3 (−5, 3).

𝐶2

𝐷2

𝐶3

𝐷3

𝐶1


𝐷1

71

Pusat


Pusat Cakram: • Nilai Eigen: ∗

72

𝝀𝟏 = 𝟑, 𝟕𝟐𝟎𝟖 − 𝟏. 𝟎𝟓𝟒𝟔𝟏𝒊 , 𝝀𝟐 = −𝟎, 𝟏𝟔𝟎𝟓 + 𝟐. 𝟑𝟑𝟗𝟓𝒊 𝝀𝟑 = −𝟒, 𝟓𝟔𝟎𝟐 − 𝟎. 𝟐𝟖𝟒𝟗𝒊 ,


73

1. Dapatkah matriks 𝑚 × 𝑛 didekomposisikan? 2. Bagaimanakah dekomposisi dari matriks real yang berukuran 𝑚 × 𝑛 ? 3. Bagaimanakah dekomposisi dari matriks kompleks yang berukuran 𝑚 × 𝑛? 4. Bagaimanakah tingkahlaku dan karakteristik yang ada di dalamnya? 5. Apakah matriks 𝑚 × 𝑛 masih mempunyai invers?

SINGULAR VALUE DECOMPOSITION

Definisi Diketahui Matriks A ∈ ℂ𝑚×𝑛 dengan 𝑟𝑎𝑛𝑘(𝐴) = 𝑟.

Diketahui juga nilai eigen dari matriks 𝐴∗ 𝐴 adalah sebagai berikut: 𝜆1 ≥ 𝜆2 ≥ ⋯ ≥ 𝜆𝑟 > 𝜆𝑟+1 = ⋯ = 𝜆𝑛 = 0


74

Bilangan 𝜎𝑖 = 2 𝜆𝑖 untuk setiap 1 ≤ 𝑖 ≤ 𝑛 disebut nilai singular dari matriks 𝐴.

Contoh soal 1 1 𝐴= 0 1 1 0 𝐴∗ 𝐴 =


𝜆2

𝐴∗ =

1 1 0 0 1

1 1

0 1 1 0

1 2 1 1 = 1 2 0 2

− 𝜆𝐼 = + 4𝜆 − 3 = 0 𝜎1 = 3 = 3 2 𝜆1 = 3, 𝜆2 = 1 𝜎2 = 1 = 1 75

𝐴∗ 𝐴

1 0 1 1

𝑚𝑎𝑘𝑎

SVD

𝑨

Karakteristik matriks menentukan karakteristik dari sebuah matriks transformasi linear. Hubungan antara prapeta dan petanya, ditentukan oleh karakteristik matriks transformasi linear.


76

𝑨

𝐴𝑣𝑖 = 𝜎𝑖 𝑢𝑖 , 1 ≤ 𝑖 ≤ 𝑛 𝐴𝑉 = 𝑈 Σ 𝐴 = 𝑈 Σ 𝑉∗

1.

Dengan 𝑉 matriks uniter yang dibentuk oleh vektor eigen normal matriks 𝑨∗ 𝑨

2.

Dengan Σ matriks diagonal yang entri-entrinya adalah nilai singular matriks 𝑨.

3.

Dengan 𝑈 matriks uniter yang dibentuk oleh vektor eigen normal matriks 𝑨𝑨∗ .


77

SVD dari matriks 𝐴 berukuran 𝑚 × 𝑛 𝑨 = 𝑼 𝜮 𝑽∗

Langkah – Langkah SVD 𝐴 = 𝑈Σ𝑉 ∗ Input : Matriks 𝐴 ∈ ℂ𝑚×𝑛 dengan 𝑟𝑎𝑛𝑘 𝐴 = 𝑟. 1.Dibentuk matriks 𝐴∗ 𝐴 dan tentukan sejumlah nilai eigen dan vektor eigen ortonormalnya. 2.Bentuk matriks uniter 𝑉 dari vektor eigen ortonormalnya. 3.Tentukan Nilai Singular tak-nol 𝜎𝑖 dan Matriks Diagonal 𝛴. 4.Tentukan vektor eigen ortonormal 𝐴𝐴∗ atau dengan 𝑢𝑖 = 𝜎𝑖−1 𝐴𝑣𝑖 . Jika 𝑟 < 𝑛 , maka gunakan proses gramschmidt untuk menententukan 𝑢𝑟+1 sampai 𝑢𝑛 . 5.Bentuk matriks uniter 𝑈 dari vektor eigen ortonormalnya.


78

Output: Matriks uniter 𝑈, 𝑉 dan matriks 𝛴 sehingga 𝑨 = 𝑼𝜮𝑽∗ .

Contoh soal


79

1 1 Misalkan 𝐴 = 0 1 . Tentukan SVD matriks A. 1 0

Penyelesaian 1 1 𝐴= 0 1 1 0

𝑚𝑎𝑘𝑎

𝐴∗ 𝐴

2 = 1

1 2

𝑛𝑖𝑙𝑎𝑖 𝑒𝑖𝑔𝑒𝑛

𝜆1 =3 𝜆2 = 1 1

maka 𝑉 =


1 2 1 2

𝑁𝑜𝑟𝑚𝑎𝑙𝑖𝑠𝑎𝑠𝑖

1 2 1 − 2

2 1 𝑣2 = −

2 1 2

80

1 𝑣𝑒𝑘𝑡𝑜𝑟 𝑒𝑖𝑔𝑒𝑛 𝑣′1 = 1 1 𝑣′2 = −1

2 1

𝑣1 =

𝜎1 𝛴= 0 0


0 𝜎2 = 0

𝜎1 = 3 𝜎2 = 1

3 0 0

0 1 0

81

𝜆1 = 3 𝑛𝑖𝑙𝑎𝑖 𝑠𝑖𝑛𝑔𝑢𝑙𝑎𝑟 𝜆2 = 1

1 1 𝑢2 = 𝜎2−1 𝐴𝑣2 = 0 1 1 0


2

2

82

1 1 𝑢1 = 𝜎1−1 𝐴𝑣1 = 3 0 3 1

1 6 1 3 1 2 1 2 = 1 1 6 6 0 2 1 2 6 6 0 1 1 2 − 2 2 = 2 1 1 − 2 2

𝑢′3 = 𝑒1 − 𝑢1∗ 𝑒1 𝑢1 − 𝑢1∗ 𝑒2 𝑢2

−


1 6 3

1 1 6 6 3 6

1 6 6

1 1 6 0 6 0

0 1 6 1 6 0

1 0 3 1 − 2 1 = − 2 3 1 1 2 − 2 3

83

1 = 0 − 0

1 6 3 1 6 6 1 6 6

1 3 1 𝑢′3 = − 3 1 − 3

1 3 3 𝑁𝑜𝑟𝑚𝑎𝑙𝑖𝑠𝑎𝑠𝑖 1 𝑢3 = − 3 3 1 − 3 3

Sehingga didapatkan Matriks Uniter


6

1 3

0

6

−

6

1 2

1 2

2 2

1 3 1 − 3

−

3 3 3 84

U=

1 3 1 6 1 6

Output : A=U𝛴𝑉 ∗


0 1 − 2 2 1 2 2

1 3 1 − 3 1 − 3

1 3 0 0

0 1 0

2 1 2

1 −

2 1 2

85

1 6 3 1 1 1 0 1 = 6 6 1 0 1 6 6


86

23/03/2016

4. POWER METHOD

PERCEPATAN AITKEN

D4

INVERS POWER METHOD

SHIFTED POWER METHOD


87

SHIFTED INVERS POWER METHOD

Persamaan karakteristik : det 𝐴 − 𝜆Ι = 0 Dari persamaan karakteristik di atas, diperoleh nilai eigen

dominan dan tak dominan.

Nilai eigen tak dominan


power method

invers power method

88

Nilai eigen dominan

Power Method

Salah satu metode iteratif yang digunakan untuk menentukan nilai eigen dominan. Nilai Eigen Dominan

Nilai eigen yang nilai mutlaknya paling besar dibandingkan mutlak nilai eigen lainnya. 𝜆1 > 𝜆2 ≥ ⋯ ≥ 𝜆𝑛 Vektor Eigen Dominan


89

Vektor eigen yang berpadanan dengan nilai eigen dominan.


90

Bagaimana menentukan pendekatan nilai eigen dengan menggunakan power method ?

Langkah – langkah Power Method 1. Pilih sebuah vektor hampiran awal 𝑥 (0) tak nol 2. Tetapkan fungsional linear 𝜑

3. Hitung 𝑥 (𝑘+1) = 𝐴 𝑥 (𝑘) ; 4. Hitung 𝜆𝑘 = 𝑟𝑘 ≈

𝜑 𝑥 (𝑘+1) 𝜑 𝑥 (𝑘)

𝑘 = 0,1,2, … ;

𝑘 = 0,1,2, …


91

5. Ulangi langkah 3 – 4 sampai 𝑟 konvergen ke solusi eksak

PERCEPATAN AITKEN

Proses iteratif yang digunakan untuk menghampiri nilai eigen dengan lebih cepat.

Rumus umum percepatan Aitken :


;𝑘 ≥ 3

92

𝑟𝑘 − 𝑟𝑘−1 2 𝑠𝑘 = 𝑟𝑘 − 𝑟𝑘 − 2𝑟𝑘−1 + 𝑟𝑘−2

Contoh Soal

Tentukan nilai eigen dominan dari matriks 𝑨 berikut dengan menggunakan power method dan percepatan Aitken.


93

6 5 −5 𝑨 = 2 6 −2 2 5 −1

Penyelesaian : Diperoleh solusi eksak : 𝜆1 = 6, 𝜆2= 4, 𝜆3= 1 Langkah ke-1 : 𝑥(0)

−1 = 1 1

Langkah ke-2 :

𝜑 𝒙 = 𝑥2 Langkah ke-3 :

𝑥(𝑘+1)= 𝐴 𝑥(𝑘) ;


𝐴𝑥(0)

−6 6 5 −5 −1 = 2 6 −2 1 = 2 2 5 −1 1 2

94

𝑥(1)=

𝑘 = 0,1,2, …

𝑥 (2) = 𝐴𝑥 (1)

−36 6 5 −5 −6 = 2 6 −2 2 = −4 2 5 −1 2 −4 ⋮

𝑥 (14) = 𝐴𝑥 (13) 6 5 = 2 6 2 5

−5 −13060694016 −2 −12926476288 −1 −12926476288

−78364164096 = −77827293184 −77827293184


95

⋮

Langkah ke-4 :

𝜆𝑘 = 𝑟𝑘 ≈

𝜑 𝑥 𝑘+1 𝜑 𝑥𝑘

; 𝑘 = 0,1,2, …

𝑥2 (1) 2 𝑟0 = (0) = = 2 1 𝑥2

𝑥2 (2) −4 𝑟1 = (1) = = −2 2 𝑥2 ⋮ 𝑟13

𝑥2 (14) −77827293184 = (13) = = 6.021 −12926476288 𝑥2


96

⋮

Solusi hampiran dengan percepatan Aitken : 𝑟3 − 𝑟2 2 𝑠3 = 𝑟3 − 𝑟3 − 2𝑟2 + 𝑟1 8.9091 − 22 2 = 8.9091 − = 13.5294 8.9091 − 2 22 + (−2) 𝑟4 − 𝑟3 2 𝑠4 = 𝑟4 − 𝑟4 − 2𝑟3 + 𝑟2 7.3061 − 8.9091 2 = 7.3061 − = 7.0825 7.3061 − 2.8.9091 + 22


97

⋮

Hasil Iterasi Power Method

k 0

X1 -1.0000

X2 1.0000

X3 1.0000

rk 2.0000

1

-1.0000

0.3333

0.3333

-2.0000

2

-1.0000

-0.1111

-0.1111

22.0000

3

-1.0000

-0.4074

-0.4074

8.9091

13.5294

4

-1.0000

-0.6049

-0.6049

7.3061

7.0825

... 14

... -1.0000

... -0.9931

... -0.9931

... 6.0208

... 6.0138

15

-1.0000

-0.9954

-0.9954

6.0092

6.0001

16

-1.0000

-0.9969

-0.9969

6.0061

6.0000

...

...


...

...

... 98

23/03/2016

...

sk

Nilai eigen dominan = 𝒓 = 𝒔 = 𝟔 Vektor eigen hampiran yang bersesuaian


99

𝒙𝟏 𝟏 𝒙𝟐 = 0.9969 𝒙𝟑 0.9969

INVERS POWER METHOD

• Metode untuk mencari nilai eigen terkecil secara iteratif. • Memiliki konsep yang sama seperti power method dengan syarat matriks 𝑨 memiliki invers. 𝟏 𝝀


100

𝑨𝒙 = 𝝀𝒙 ↔ 𝒙 = 𝑨−𝟏 (𝝀𝒙) ↔ 𝑨−𝟏 𝒙 = 𝒙

Langkah - Langkah Invers Power Method 1.

Tetapkan vektor eigen awal 𝑥0 tak nol.

2.

Tetapkan fungsional linear 𝜑.

3.

Hitung matriks 𝑨−1 , atau tentukan dekomposisi 𝐿𝑈 dari 𝑨.

4.

Hitung 𝒙 invers.

5.

Hitung 𝑳𝒙 𝒌+𝟏 = 𝑼−𝟏 𝒙 𝒌 ; 𝑘 = 1,2, … Jika menggunakan dekomposisi 𝐿𝑈.

= 𝑨−1 𝒙 𝒌 ; 𝑘 = 1,2, … Jika menggunakan

𝜑 𝒙 𝒌+𝟏

6.

Hitung 𝑟𝑘 =

7.

Ulangi langkah ke – 4 sampai ke – 6 sampai 𝑟 konvergen ke solusi eksak.


𝜑(𝒙𝒌 )

; 𝑘 = 1,2, …

101

𝒌+𝟏

CONTOH


102

Misalkan diberikan matriks, nilai awal, dan fungsional linear sebagai berikut −154 528 407 𝑨 = 55 −144 −121 318 −132 396 1 𝒙0 = 2 3 𝜑 𝒙 = 𝑥2

Penyelesaian : Dengan matriks invers : 59 11

40 3 341 𝐴−1 = 23 −12 − 36 6 52 −7 22 3 59 40 − 17 11 3 1 68.63 341 −1 𝒙1 = 𝐴 𝒙0 = 23 −12 − 2 = −48.58 36 3 89 6 52 −7 22 3 59 40 − 17 11 3 68.63 −7.39 341 𝒙2 = 𝐴−1 𝒙1 = 23 −12 − −48.58 = 3.07 36 89 −6.62 6 52 −7 22 3 23/03/2016 Matematika FMIPA IPB

17

103

−

Hasil Iterasi Inverse Power Method k

X1

X2

X3

r

1

1

- 0.7078366

1.2966887

- 24.291667

2

1

- 0.4165191

0.8959090

- 0.0633609

..

...

10

1

- 0.6101062

1.1601095

- 0.2458083

...

...

...

...

...

29

1

- 0.6162430

1.1684148

- 0.2610306

30

1

- 0.6161851

1.1683364

- 0.2608796


104

23/03/2016

...

𝒓=

𝝀∗

𝟏 = = − 0.2608796 𝝀

𝟏 𝟏 𝝀= ∗= = −3.83319 𝝀 − 0.2608796


105

𝝀𝒆𝒌𝒔𝒂𝒌 = −3.83229

SHIFTED POWER METHOD

Metode untuk mencari nilai eigen terjauh dari suatu nilai 𝜇 𝑨𝒙 = 𝝀𝒙 𝑨 − 𝝁𝑰 𝒙 = 𝝀 − 𝝁 𝒙

Langkah-langkah Shifted Power Method Sama seperti power method. Hasil yang didapat adalah nilai 𝜆′ = 𝜆 − 𝜇 terbesar.


106

Nilai 𝜆 dapat dicari menggunakan 𝜆 = 𝜆′ + 𝜇.

CONTOH Tentukan nilai eigen yang paling jauh dari 4 1 3 7 𝑨 = 2 −4 5 3 4 −6 −3 3 7 𝑨 − 4𝑰 = = 2 −8 5 3 4 −10


107

terapkan iterasi power method.

Hasil Iterasi Shifted Power Method k 1 2 .. 10

X1 1 1 ... 1

X2 X3 r 0.0416667 - 0.7916667 0.5 0.2722772 - 1.3168317 - 55. ... ... ... 1.47269 - 2.1989031 - 14.14407

... 29

... 1

... 1.5068126

30

1

1.5068359 - 2.2253031 - 14.056775


108

23/03/2016

... ... - 2.225285 - 14.056833

𝒓 = 𝝀∗ = 𝝀 − 𝝁 = − 14.056775 𝝀 = 𝝀∗ + 𝝁 = − 14.056775+4=−10.056775


109

𝝀𝒆𝒌𝒔𝒂𝒌

−10.0567 = 5.28779 −4.2311

SHIFTED INVERS POWER METHOD

Metode untuk mencari nilai eigen terdekat dari suatu nilai 𝜇


110

𝑨𝒙 = 𝝀𝒙 𝑨 − 𝝁𝑰 𝒙 = 𝝀 − 𝝁 𝒙 𝟏 −𝟏 𝑨 − 𝝁𝑰 𝒙 = 𝒙 𝝀−𝝁

Langkah-langkah Shifted Inverse Power Method Sama seperti Inverse power method. 1 𝜆−𝜇

Nilai 𝜆 dapat dicari menggunakan 𝜆 =


1 𝜆′

terkecil. + 𝜇.

111

Hasil yang didapat adalah nilai 𝜆′ =

CONTOH Tentukan nilai eigen yang paling dekat dari 4 1 3 7 𝑨 = 2 −4 5 3 4 −6

−3 𝑨 − 4𝑰 = 2 3

60 149 35 (𝑨 − 4𝑰) −𝟏 = 149 32 149

58 149 9 149 21 149

3 7 −8 5 4 −10 71 149 29 149 18 149


112

terapkan iterasi inverse power method.

k

X1

X2

X3

r

1

1

0.3598972

0.3290488

0.4697987

2

1

0.4583950

0.4363224

0.8910355

3

1

0.4404249

0.4208715

0.7581004

4

1

0.4433045

0.4229930

0.7797397

5

1

0.4428434

0.4226845

0.7759984

6

1

0.4429164

0.4227306

0.7766080


113

Hasil Iterasi Shifted Inverse Power Method

𝒓=

𝝀∗

𝟏 = = 0.7766080 𝝀−𝝁

𝟏 𝝀= + 𝟒 = 5.28765 0.7766080


114

𝝀𝒆𝒌𝒔𝒂𝒌

−10.0567 = 5.28779 −4.2311

DAFTAR PUSTAKA 1) W. Cheney, D. Kincaid. 2008. Numerical Mathematics and Computing 6th Ed. Thomson Brooks/Cole. 2) R. Munir. 2003. Metode Numerik pada Penerbit Informatika Bandung. 3) //staff.uny.ac.id/sites/default/files/131930136/KomputasiNumerikBa b2.pdf


115

4) https://www.academia.edu/7730008/Nilai_Eigen_dan_Ruang_Eigen

SISTEM PERSAMAAN LINEAR ( BAGIAN II )

Recommend Documents