i KATA PENGANTAR Pertama-tamatentusajasayaselakupenulismengucapkanpujidansyukurkehadirat GustiAllahSWTyangdenganrahmatdankarunianyatelahmenjadikansayasebagaiseorang (mantan)mahasiswaProdiMatematikaFMIPAUGM.Sebelumnyasayainginmemintamaaf duluapabilakalimatpadakatapengantarinitidaksepenuhnyamerupakankalimatbakudan cenderungekspresif.Maklum,penulisjugamerangkapprofesisebagaiseorangblogger(bisa dilihatdihttp://wijna.web.id).AkantetapipadapembahasanmengenaiDekomposisiMatriks, penulismenggunakanbahasabakuyangmengacukepadastandartata-kalimatTugasAkhirdi Prodi Matematika FMIPA UGM. Di tahun 2007, sembari menunggu nilai-nilai ujian akhir yang tidak kunjung terpampang di papan nilai ujian, penulis iseng-iseng membuat makalah ini. Makalah ini dibuat semata-mata sebagaijejakpeninggalankamiyangtelahsuksesmenempuhmatakuliahAljabarLinear NumerikyangpadamasakamidiasuholehPakSutopo.Mengapakami?Karenapenulistidak menggunakanreferensipribadisajadalampenyusunanmakalahini,namunjugamenggunakan makalah-makalah hasil presentasi teman-teman penulis; Noorma, Adhisti, Pipit, Ruth, dan Yoa. Terima kasih juga untuk Hening (Math 2005) atas makalahnya yang berkaitan dengan Proyeksi. BagiandayangmengambilmatakuliahAljabarLinearNumerik,semogamakalahinibisa menjadi salah satu media pembelajaran anda. Yogyakarta, Agustus 2007 Juni 2009 Wihikan "Mawi" Wijna iiHALAMAN PERSEMBAHAN Terima Kasih Sebanyak-Banyaknya Buat Genk Chubby! Dari Kiri ke Kanan: Adhisti Arie Yusanti Ruth Triaulia Napitupulu Pipit Pratiwi Rahayu Yoanita Dwi Harlandi Noorma Yulia Megawati [semuanya math 2004] iiiDAFTAR ISI KATA PENGANTAR.........................................................................................................i HALAMAN PERSEMBAHAN ..........................................................................................ii DAFTAR ISI........................................................................................................................iii DAFTAR SIMBOL .............................................................................................................iv 1. Pendahuluan.....................................................................................................................1 2. Dasar Teori.......................................................................................................................3 3. Dekomposisi Nilai Singular.............................................................................................10 4. Dekomposisi QR..............................................................................................................21 5. Dekomposisi Cholesky....................................................................................................34 6. Dekomposisi Schur..........................................................................................................46 7. Metode Least Square.......................................................................................................53 8. Proyektor.........................................................................................................................55 ivDAFTAR SIMBOL `: Himpunan seluruh bilangan asli, { } 1, 2, 3,... . ]: Himpunan seluruh bilangan bulat. _: Himpunan seluruh bilangan rasional.\: Himpunan seluruh bilangan real.^: Himpunan seluruh bilangan kompleks. mn \ : Himpunan seluruh matriks dengan entri-entrinya merupakan bilangan real, memiliki sejumlah m baris, dan sejumlah n kolom. mn ^ : Himpunan seluruh matriks dengan entri-entrinya merupakan bilangan kompleks, memiliki sejumlah m baris, dan sejumlah n kolom. m\ : Himpunan vektor dengan entri-entrinya merupakan bilangan real, berbentuk m baris dan 1 kolom.m^ : Himpunan vektor dengan entri-entrinya merupakan bilangan kompleks, berbentuk m baris dan 1 kolom.Tx : Transpose dari suatu vektor mx\ . * c : Transpose konjugat dari suatu vektor mc^ . TA : Transpose dari suatu matriks mxnA\ . * B : Transpose konjugat dari suatu matriks mxnB^ . 1A: Invers suatu matriks A terhadap operasi perkalian matriks. ( ) det A : Determinan matriks A. x : Norma vektor x. , xy : Inner-product vektor x dan y. 0 : Vektor nol. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 1BAB I PENDAHULUAN 1.1Latar Belakang Masalah Salahsatupermasalahanpadabidangaljabarlinearadalahmenyelesaikansuatu sistem persamaanAx b = , untuk suatu matriks A serta vektor x dan b. Salah satu metode yangumumdigunakanuntukmenyelesaikanpermasalahantersebutadalahdengan melakukanserangkaianoperasikolom/bariselementeruntukmembawamatriksA menjadi bentuk eselon tereduksi. Namun selain cara tersebut, dapat pula digunakan cara memfaktorkan matriks A menjadi bentukA UV =untuk suatu matriks U dan V. Dengan demikian sistem persamaan akan berubah menjadi( ) Ax UV x b = = . Sehingga cara yang digunakanuntukmenyelesaikansistempersamaantersebutadalahdenganmenghitung vektory Vx = dandiharapkansistempersamaanakanlebihmudahdiselesaikandalam bentuk Uy b = . Teknik pemfaktoran tersebut dinamakan dekomposisi matriks. 1.2Maksud dan Tujuan Padamakalahiniakandibahasmengenaijenisbesertasifatdaridekomposisi matriksberikut;DekomposisiNilaiSingular,DekomposisiQR,DekomposisiCholesky, danDekomposisiSchur.SelainitudibahaspulamengenaimetodeLeastSquareserta Proyeksi. 1.3Tinjauan Pustaka Literaturyangmenjadiacuanutamadalampenulisantugasakhirinimakalah-makalahyangdihasilkanolehkelompokdimatakuliahAljabarLinearNumerikpada SemesterGanjilditahunajaran2006/2007.Selainmakalahkelompoktersebut, St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 2ditambahkanpulaliteraturyangdiperolehdariinternetyangmayoritasbersumberdari situs Wikipedia.1.4Metode Penelitian Untukmempelajaridekomposisimatriksterlebihdahuludipelajaridasar-dasar dariAljabarLinearsepertiBasis,Rank,Null,Ortogonalitasdanlainsebagainya.Untuk memudahkanpembelajarandiharapkanpembacamenguasaidasar-dasardarimatakuliah AljabarLinearElementerdanAljabarLinear.Setelahitupembahasandilanjutkan mengenaidekomposisimatriks.Bab-babyangmenjelaskanteoridekomposisimatriks, yaitu Bab III sampai VIII masing-masing berdiri sendiri dan tidak terkait dengan bab-bab sebelumnya. 1.5Sistematika Penulisan Untuk memberikan gambaran secara menyeluruh tentang masalah yang diangkat dalam penulisan makalah ini, diberikan sistematika penulisan sebagai berikut. Bab I merupakan pendahuluan makalah, yang meliputilatar belakang masalah, maksud dan tujuan, tinjauan pustaka, metode penulisan, dan sistematika penulisan. Bab II berisi dasar teori, yang meliputi dasar-dasar dari Aljabar Linear. Pada bab III dibahas pengertian dan sifat-sifat Dekomposisi Nilai Singular. Bab IV dibahas pengertian dan sifat-sifat Dekomposisi QR. Bab V dibahas pengertian dan sifat-sifat Dekomposisi Cholesky. Bab VI dibahas pengertian dan sifat-sifat Dekomposisi Schur. Bab VII dibahas pengertian dan sifat-sifat metode Least Square. Bab VIII dibahas pengertian dan sifat-sifat Proyeksi. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 3BAB II DASAR TEORI Berikut diberikan beberapa definisi dan teorema yang digunakan dalam pembahasan dekomposisi suatu matriks. Pembahasan diawali dengan definisi mengenai himpunan bilangan kompleks. Definisi 2.1 (Himpunan Bilangan Kompleks) Himpunan { }, a bi a b = + C Rdengan 21 i= disebut sebagai himpunan bilangan kompleks. Himpunan bilangan kompleks merupakan lapangan. Lebih lanjut berlaku sifat N Z R C. Definisi 2.2 (Sekawan Bilangan Kompleks) Diketahui suatu bilangan komplesz a bi = + . Sekawan dari z adalahz a bi = . Lebih lanjut, berlaku sifat 2 2z zz a b = = + . Pada matakuliah Aljabar Linear Elementer telah dibahas mengenai ruang vektor dan basis. Berikut akan kembali dijelaskan mengenai ruang vektor, basis, dan khususnya rank suatu matriks. Definisi 2.3 (Basis Ruang Vektor) Diketahui V suatu ruang vektor atas lapangan F, basis untuk V merupakan himpunan { }1 2, ,...,nS v v v V = yang memenuhi kedua aksioma berikut: (i).Himpunan S bebas linear, yaitu 1 1 2 2... 0n nk v k v k v + + + =jika dan hanya jika 1 2... 0nk k k = = = = . (ii).Himpunan S membangun V, untuk setiapv V terdapat 1 2, ,...nk k k F sehingga 1 1 2 2...n nv k v k v k v = + + + . Teorema 2.4 Setiap ruang vektor V atas sebarang lapangan F memiliki basis. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 4Teorema 2.5 Diketahui m nAC , maka himpunan { }nV Ax x = Cmerupakan suatu ruang vektor atasC, dan menurut Teorema 2.4 berakibat V memiliki basis. Definisi 2.6 (Range dan Rank) Diketahui m nAC , maka Range Aadalah himpunan { }nV Ax x = C . Dimensi basis dari V disebut dengan Rank A. Contoh 2.7 Diketahui matriks 2 31 0 10 1 0A = R . Untuk sebarang 3ax bc = R , berlaku: 21 0 10 1 0aa cAx bbc + = = R . Dengan demikian Range A adalah 3 2aa cV bbc + = R R . Selanjutnya, akan dibuktikan bahwa 2V R . Diambil sebarang 2xy R , perhatikan bahwa dapat dipiliha x y = + ,b y = , danc y = sehingga berlaku: 21 0 1 1 0 10 1 0 0 1 0a x yxb yyc y+ = = R . Jadi terbukti bahwa xVy yang berakibat 2V R . Karena 2V Rdan 2V R , maka berlaku 2V = Rdan dengan demikian banyaknya elemen pada basis untuk V adalah 2, atau dengan kata lain Rank A adalah 2. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 5Pada matakuliah Aljabar Linear Elementer juga telah diterangkan bahwa pengertian lain dari rank suatu matriks adalah banyaknya kolom-kolom yang saling bebas linear pada matriks bentuk eselon tereduksi. Besar harapannya bahwa pembaca juga menambah wawasan mengenai definisi lain dari rank beserta sifat-sifat rank. Berikut diberikan sifat rank yang disebut dengan fullrank.Definisi 2.8 (Fullrank) Suatu matriks m nAC dikatakan fullrank jika dan hanya jika A memetakan vektor yang berbeda ke vektor yang berbeda pula, yaitu untuk setiap,nx y Cdenganx y berlaku Ax Ay . Definisi tersebut ekuivalen dengan untuk setiap,nx y CdenganAx Ay = , berakibatx y = . Matriks fullrank memiliki Rank{ } min , m n = . Contoh 2.9 Matriks A pada contoh 7 bukan merupakan matriks fullrank karena terdapat 31 21 , 10 1 R , sehingga 1 211 110 1A A = = . Teorema 2.10 Suatu matriks persegi A invertibel jika dan hanya jika A fullrank. Disamping rank, terdapat pula pengertian mengenai null suatu matriks. Teorema 2.11 Diketahui m nAC , maka himpunan { }0nW x Ax = = Cmerupakan suatu ruang vektor atasC, dan menurut teorema 4 berakibat W memiliki basis. Definisi 2.12 (Null dan Kernel) Diketahui m nAC , maka NullAadalah himpunan { }0nW x Ax = = C . Dimensi basis dari W disebut dengan Kernel A. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 6Berikut diberikan definisi mengenai transpose dan transpose konjugat. Definisi 2.13 (Transpose) Diketahui vektor 1nnkxk = . R . Transpose dari vektor x adalah vektor 1 T nxRdengan [ ]1Tnx k k =. Transpose dari matriks m nARdidefinisikan serupa, yaitu dengan memandang A sebagai matriks yang dibentuk dari vektor kolom dan melakukan transpose pada vektor kolom tersebut. Definisi 2.14 (Transpose Konjugat) Diketahui vektor 1nnzcz = . C . Transpose dari vektor c adalah vektor 1*ncCdengan [ ]1*nc z z =. Transpose konjugat dari matriks m nBCdidefinisikan serupa, yaitu dengan memandang B sebagai matriks yang dibentuk dari vektor kolom dan melakukan transpose konjugat pada vektor kolom tersebut. Contoh 2.15 Diketahui matriks 2 30 1 23 4iAi i+ = C , maka 0 3* 1 42A i ii = . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 7Berikut diberikan definisi mengenai matriks simetri, hermitian, ortogonal, dan uniter. Definisi 2.16 (Matriks Simetri) Suatu matriks persegi m mAR dikatakan simetri jika dan hanya jika TA A = . Definisi 2.17 (Matriks Hermitian) Suatu matriks persegi m mBC dikatakan hermitian jika dan hanya jika* A A = . Definisi 2.18 (Matriks Ortogonal) Suatu matriks persegi m mAR dikatakan ortogonal jika dan hanya jika 1 TA A= . Definisi 2.19 (Matriks Uniter) Suatu matriks persegi m mBC dikatakan uniter jika dan hanya jika 1* A A= . Berikut diberikan definisi mengenai matriks definit positif. Definisi 2.20 (Matriks Definit Positif) Suatu matriks hermitian m mAC dikatakan definit positif jika dan hanya jika untuk sebarang vektormxC , berlaku* 0 x Ax > . Contoh 2.21 Matriks 10iAi = bukan matriks definit positif, karena ada vektor 201 Csehingga [ ]1 00 1 00 1ii = . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 8Berikut akan diberikan definisi mengenai basis ortonormal. Sebelumnya, akan didefinisikan dulu mengenai norma, inner-product, vektor ortogonal dan vektor normal yang diberikan pada vektor-vektor di nC . Karena definisi tersebut juga berlaku pada nRkarena adanya hubungan n n R C . Definisi 2.23 (Norma Euclid Vektor Kompleks) Diketahui vektor 1nnzcz = . C , maka norma vektor c adalah 2 21 nc z z = + + dengan i i iz z z = . Definisi 2.24 (Inner-Product) Diketahui vektor,nx y C , maka inner-product vektor x dan y adalah, * x y x y = . Teorema 2.25 Diketahui vektor nxC , maka berlaku 2, x x x = . Definisi 2.26 (Vektor Ortogonal) Vektor,mx y C dikatakan saling ortogonal jika dan hanya jika, 0 x y = . Definisi 2.27 (Vektor Normal) Vektor mxC dikatakan vektor normal jika dan hanya jika1 x = . Definisi 2.28 (Basis Ortonormal)Diketahui V ruang vektor atasC, dan{ }1 2, ,...,nS v v v =merupakan basis untuk V. Basis S disebut Basis Ortonormal jika dan hanya jika: (i).Setiap ivmerupakan vektor normal, dan (ii)., 0i jv v =untuk setiap, i jdengani j . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 9Berikut akan diberikan definisi mengenai nilai eigen dan vektor eigen. Definisi 2.29 (Nilai Eigen dan Vektor Eigen) Diketahui m nAC . Bilangan kompleksdan vektor tak nol nxCyang memenuhi persamaanAx x =berturut-turut disebut nilai eigen A dan vektor eigen A. Vektor x yang merupakan vektor eigen A, disebut juga vektor eigen yang bersesuaian dengan nilai eigen . Teorema 2.30 Diketahui m nAC . Jika A merupakan matriks hermitian, maka vektor-vektor eigennya saling ortonormal. Teorema 2.31 (Diagonalisasi Matriks) Diketahui m nAC . Jika A merupakan matriks hermitian, maka terdapat matriks uniter Q sehingga berlaku* A Q Q = dengan merupakan matriks diagonal yang entri-entrinya merupakan nilai eigen matriks A. Lebih lanjut, matriks Q merupakan matriks yang dibentuk dari vektor-vektor eigen matriks A. Untuk memahami lebih jauh mengenai sifat-sifat yang telah dipaparkan pada bab ini, diharapkan pembaca juga mendalami topik mengenai aljabar linear yang terdapat pada matakuliah Aljabar Linear Elementer dan Aljabar Linear. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 10BAB III DEKOMPOSISI NILAI SINGULAR Dekomposisi Nilai Singular atau yang lebih dikenal sebagai SVD (Singular Value Decomposition) merupakan salah satu dekomposisi yang cukup terkenal. SVD berkaitan erat dengan singular value atau nilai singular dari sebuah matriks yang merupakan salah satu karakteristik matriks. Definisi 3.1 (Nilai Singular) Diketahui matriks m nAC dengan rank A =r. Diketahui juga nilai eigen dari matriks * A A adalah sebagai berikut: 1 2 1... ... 0r r n + > = = = . Bilangan 2i i = , untuk setiap 1 i n disebut nilai singular dari matriks A. Teorema 3.2 Diketahui matriks m nAC dengan rank A =r. Maka terdapat tepat sejumlah r nilai singular yang tak nol.Bukti. Misalkan nilai eigen dari matriks* A A adalah 1 2, ,...,n dengan 1 2...n . Berarti terdapat sejumlah n vektor eigen, 1, 2, 3,...,ix i n =yang bersesuaian dengan nilai-nilai eigen tersebut. Misalkan { }1 2, ,...,nx x xmerupakan himpunan n vektor eigen yang dimaksud. Diperhatikan bahwa himpunan tersebut membentuk basis ortogonal untuk nC . Jika basis ortogonal tersebut dinormalisasi akan diperoleh basis ortonormal { }1 2, ,...,np p puntuk nC , dengan iiixpx=untuk setiap 1 i n . Karena himpunan { }1 2, ,...,np p pmerupakan basis ortonormal untuk nC , maka berlaku 2, 1i i ip p p = =untuk setiap 1 i n , akibatnya St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 11( ) ( )( )( )( )2, ** ***.i i i ii ii i ii i ii iiAp Ap Ap App A App pp pp====== Menurut definisi nilai singular, berlaku 22i i iAp = = , untuk setiap1 i n . Karena diketahui rank A=r, maka berlaku 1 2... 0rAp Ap Ap = = = , dan1 2... 0r r nAp Ap Ap+ += = = = . Jadi diperoleh0i , untuk1, 2, 3,..., i r = . Lebih lanjut, karakteristik matriks juga menentukan karakteristik dari sebuah matriks transformasi linear. Hubungan antara prapeta dan petanya, ditentukan oleh karakteristik matriks transformasi linear. Diperhatikan ilustrasi berikut: Ilustrasi diatas menunjukkan bagaimana hubungan antara prapeta { }1 2, v vketika ditransformasikan menggunakan matriks m nAC , dengan petanya { }1 1 2 2, u u . Vektor , u vmasing-masing adalah vektor unit, sehingga dengan demikian apabila jumlah vektor u dan v ada sebanyak n buah, maka berlaku: i i iAv u = , 1 i n St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 12Dalam notasi matriks: 11 2 1 20... ... .0n nnV UA v v v u u u =

..

Hubungan ini dapat pula ditulis sebagai: . AV U = Karena V adalah matriks uniter, maka dengan mengkalikannya dengan* V dari kanan diperoleh : * A U V = Dengan U , matriks uniter yang dibentuk oleh vektor eigen normal matriks TAA . Dengan V , matriks uniter yang dibentuk oleh vektor eigen normal matriks TA A. Dengan , matriks diagonal yang entri-entrinya adalah nilai singular matriks A. Bentuk diatas disebut dengan bentuk dekomposisi SVD. Berikut akan dijelaskan mengenai cara untuk membentuk matriks U dan V. Misalkan diketahui matriks m nACdengan rank A= r. Kemudian dibentuk matriks * A A, dan dicari nilai-nilai eigen dan vektor-vektor eigennya. Misalkan 1 2, ,...,n merupakan nilai-nilai eigen matriks* A A dan 1 2, ,...,nv v vmerupakan vektor-vektor eigen matriks* A A dengan ivmerupakan vektor eigen yang bersesuaian dengan i . Karena * A A matriks hermitian maka vektor-vektor eigennya membentuk basis ortonormal. Dengan demikian dapat dibentuk matriks 1 2...nV v v v = yang merupakan matriks uniter. Menurut definisi nilai eigen diperoleh*i i iA Av v =untuk setiap 1 i n , sehingga diperoleh* * * ,i j i j j j i jv A Av v v v v = = . Menurut Teorema 3.2 ada sejumlah r nilai singular yang tidak nol. Dengan demikian, untuk nilai positif jdengan 1, 2,..., j r = , dapat definisikan j j =dan dibentuk vektor 1j jju Av= . Diperhatikan St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 13bahwa ( ) ( )*1 1 1, * * * ,j ji j i j i j i j i ji j i j i j i ju u Av Av v A Av v v v v = = = = dan,(i).Untuki j , diperoleh, 0i jv v =dan akibatnya , , 0 0j ji j i ji j i ju u v v = = = . (ii).Untuki j = , diperoleh, 1i jv v =dan akibatnya , , 1j ji i i ji j i ju u v v = = = . Dari (i) dan (ii), berakibat himpunan { }1 2, ,...,ru u umerupakan basis ortonormal. Dibentuk matriks uniter U, dan V yang masing-masing dibangun oleh vektor-vektor eigen u dan v, Maka diperoleh : ( )0* *,i jijj i jj rU AV u Avu u j r > = = Sehingga * U AV = atau dengan kata lain* A U V = . Secara umum berikut algoritmanya. Algoritma 3.3 (Algoritma Dekomposisi Nilai Singular) Input: Matriks m nACdengan rank A = r.Output : Matriks uniter U,V dan matriks singularsehingga* A U V = . 1.Dibentuk matriks* A A dan tentukan sejumlah r nilai singular tak nolnya. Misalkan { }1 2, ,...,r merupakan nilai-nilai singular tak nol matriks* A Adengan 1 2 1... ... 0r r n + > = = = . 2.Dibentuk matriks diagonal 100n =

..

. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 143.Dicari himpunan vektor eigen matriks* A A. Misalkan { }1 2, ,...,nv v vmerupakan vektor-vektor eigen matriks* A A dengan ivmerupakan vektor eigen yang bersesuaian dengan i . 4.Dibentuk matriks uniter 1 2...nV v v v = . 5.Dibentuk himpunan vektor{ }1 2, ,...,nu u udengan 1i iiu Av=untuk setiap 1 i n . 6.Dibentuk matriks uniter 1 2...nU u u u = . Contoh 3.4 Diketahui matriks 1 100A ii = , akan dicari bentuk dekomposisi SVD-nya. Dibentuk matriks 1 11 0 2 1* 01 0 1 20iA A iii = = . Diketahui nilai eigen matriks* A A adalah 1 23dan1 = = .Kemudian dibentuk matriks singular, 3 00 1 = . Nilai-nilai eigen 1 23, 1 = =masing-masing berkorespondensi dengan vektor eigen 12222v = dan 22222v = . Himpunan vektor-vektor eigen tersebut ortonormal sehingga dapat dibentuk matriks uniter Vsebagai berikut: [ ]1 22 22 22 22 2V v v = = St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 15 Kemudian untuk matriks U yang dibentuk dari 1i iiu Av= , diperoleh : 1636666u ii = dan 202222u ii = . Kemudian dibentuk matriks uniter U : [ ]1 26036 26 26 26 2U u u i ii i = = Sehingga bentuk SVD dari matriks A adalah : *6031 12 26 2 3 02 206 20 12 202 26 26 2VUA i i iii i = = . Diperhatikan matriks uniter 3 2 xU C , agar matriks unitary U ini menjadi matriks persegi berukuran 3x3 harus ditambah satu kolom lagi. Namun vektor yang menyusun kolom tambahan tersebut haruslah ortonormal dengan vektor kolom lainnya. Karena itu dipilih sebarang vektor yang memenuhi syarat tersebut. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 16Diambil 3333333u = , sehingga menjadikan matriks 6 630 033 36 2 6 2336 2 6 26 2 6 2336 2 6 2U i i i ii i i i = = . Namun akibatnya matriks singularharus menambah jumlah baris agar mengimbangi jumlah kolom tambahan pada matriks unitary U. Karena baris tambahan pada matriks singularharus tetap menjadikan hasil perkalian U sama seperti ketika matriks unitary U belum bertambah jumlah kolomnya, maka baris tambahan pada matriks singularharus dibentuk oleh vektor 0. Sehingga : *630331 1 3 02 26 22 230 0 136 22 20 0 02 26 2336 2VUA i i iii i = = . Bentuk ini dinamakan bentuk SVD penuh karena matriks unitary U dan V masing-masing berupa matriks persegi. Sedangkan bentuk SVD sebelumnya dinamakan bentuk SVD tereduksi. Bila diperhatikan ada perbedaan notasi bertopi yakni& U serta & U . Notasi topi digunakan untuk menandai matriks dekomposisi dalam bentuk tereduksi. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 17Berikut merupakan beberapa sifat yang ada pada SVD. Teorema 3.5 Diketahuim nACdengan rank A = r , makaRange A ={ }1 2, ,...,rspan u u u , dan Null A ={ }1 2, ,...,r r nspan v v v+ +. Bukti. Dari SVD diperoleh bentuk * U AV AV U = = . Karena rank A = r, maka terdapat tepat sejumlah r nilai singular tak nol. Sehingga, Range A adalah U . [ ] [ ]11 2 1 1 2 2... ...n n nnU u u u u u u = =

Bila terdapat n nilai singular maka 1... 0r n + = = = , berakibat 1 1... 0r r n nu u + + = = = .Sehingga [ ]1 1... 0 ... 0r rU u u =dan dengan demikian berlaku Range A ={ }1 2, ,...,rspan u u u . Sebaliknya untuk matriksAV , karena Range A ={ }1 2, ,...,rspan u u uberakibat[ ] [ ] [ ]1 2 1 1 1 1... ... ... ... 0 ... 0n r r n r rAV A v v v Av Av Av Av u u += = =Hal ini berarti0iAv = , untuk1,..., i r n = + . Sehingga dapat ditarik kesimpulan bahwa Null A ={ }1 2, ,...,r r nspan v v v+ +. Teorema 3.6 Nilai singular tak nol dari matriks m nACadalah akar pangkat dua (2) dari nilai eigen matriks* A A atau* A A (nilai eigen dari kedua matriks ini sama). Bukti Menurut SVD tereduksi, diperoleh bentuk* A U V = , sehingga dengan demikian: ( ) ( ) ( ) * * * * * * * * * A A U V U V V U U V V V = = = . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 18Diperhatikan bahwa matriks V adalah matriks uniter dan menurut teorema diagonalisasi berakibat matriks* A A dan* similar. Akibatnya matriks* A A dan* memiliki persamaan karakteristik yaitu nilai eigen yang sama. Nilai eigen matriks tak nolmatriks * tidak lain adalah 2 2 21 2, ,...,r . Hal serupa berlaku juga untuk ( )( ) ( ) * * * * * * * * * AA U V U V U V V U U U = = = . Teorema 3.7 Nilai singular dari matriks hermitian n nACadalah harga mutlak nilai eigen dari matriks A. Bukti. Menurut Teorema 2.31, diketahui bahwa matriks A dapat disajikan sebagai* A Q Q = , dengan matriks Q adalah matriks uniter yang dibentuk dari vektor-vektor eigen matriks A. Serta matriksyang merupakan matriks diagonal persegi dengan entri-entrinya nilai eigen dari matriks A. Karena nilai eigen matriks A bisa positif maupun negatif sehingga( ) ( ) * A Q sign Q = dengan matriks( ) sign adalah matriks diagonal persegi yang entri-entrinya adalah 1 atau -1, tergantung dari entri matriks yang bersesuaian dengannya. Dengan demikian matriks ( ) sign merupakan matriks uniter. Misalkan( ) ( ) * V sign Q = , maka matriks V ini masih merupakan matriks uniter karena( ) ( ) ( ) * ( ) * * ( ) * V sign Q Q sign = = , sehingga ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* ( ) * ( ) * ( ) * ( ) * * VV sign Q Q sign I Q sign sign Q V V = = = = . Jadi, diperoleh bentukA Q V = dengan( ) ( ) * V sign Q = merupakan matriks uniter. Bentuk ini tidak lain adalah bentuk SVD dan dengan demikian nilai singular matriks A adalah entri-entri matriks . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 19Teorema 3.8 Harga mutlak determinan darimatriks persegi mxmAC , yaitu( ) det A ,adalah perkalian semua nilai singular matriks A. Bukti. Jika Q merupakan matriks uniter maka* QQ I = , sehingga dengan demikian berlaku( ) ( ) ( ) ( ) det det * det * det 1 Q Q QQ I = = =atau dengan kata lain ( ) ( ) det det * 1 Q Q = = . Menurut SVD, matriks A dapat disajikan sebagai* A U V = . Karena U dan* Vmatriks uniter, maka berlaku( ) ( ) det det * 1 U V = =sehingga dengan demikian( ) ( )( ) ( ) ( )( )det det *det det det *det .A U VU V= = = Karena matriksmerupakan matriks diagonal dengan entri-entrinya merupakan nilai singular, yaitu merupakan bilangan positif atau nol, maka berlaku( ) ( ) det det = dan nilai determinannya merupakan perkalian nilai-nilai singular matriks A. Teorema 3.9 Jika matriks m nAC fullrank, maka SVD dari matriks A tunggal. Bukti. Diperhatikan bahwa jika matriks A fullrank maka setiap nilai singularnya akan bernilai positif. Sebaliknya, jika matriks A tidak fullrank maka salah satu nilai singularnya akan bernilai nol. Hal tersebut berkaitan dengan determinan* A A ataupun* AAyang bernilai nol jika matriks A tidak fullrank. Akibatnya apabila matriks A tidak fullrank, maka pada saat pembentukan matriks uniter U, vektor 1j jju Av=(untuk suatu nilai j) tidak akan terdefinisi karena jbernilai 0. Karenanya dipilih sebarang vektor yang ortonormal dengan vektor u yang lain, dan St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 20berakibat matriks U tidak tunggal. Berbeda jika matriks A fullrank, maka setiapvektor 1j jju Av= , akan selalu terdefinisi, sehingga matriks U tunggal. Akibatnya SVD dari matriks A tunggal. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 21BAB IV DEKOMPOSISI QR Untuk memulai pembahasan mengenai dekomposisi QR, terlebih dahulu dibahas mengenai eksistensi basis ortonormal dari suatu ruang vektor mC . Diperhatikan teorema berikut. Teorema 4.1 Ruang vektor mC atasC memiliki basis ortonormal. Menurut Teorema 2.4, ruang vektor mCmemiliki basis dan menggunakan algoritma Gram-Schmidt, dapat dibentuk suatu basis ortonormal dari suatu basis ruang vektor. Berikut algoritma Gram-Schmidt yang dimaksud. Algoritma 4.2 (Algoritma Gram-Schmidt 1) Input: Ruang vektor mCdengan basisnya { }1 2, ,...,nv v v .Output : Basis ortonormal { }1 2, ,...,nq q quntuk ruang vektor mC . 1.Dibentuk 111vqv= . 2.Untuk2, 3, 4,..., i n =dibentuk 1 1 2 2 1 11 1 2 2 1 1, , ... ,, , ... ,i i i i i iii i i i i iv q v q q v q q v qqv q v q q v q q v q = . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 22Contoh 4.3 Misalkan diketahui 3Cmemiliki basis 1 2 00 , 0 ,0 1iii .Misalkan 1 21 20 , 00iv vi = = dan 301v i = . i.Karena( )21 1 1* 1 0 1 0 1 2 v v v i i = = + + = + += , maka 11122022vqvi = = . ii.Karena ( ) 2 1 2 12 2 22 2 22 2 2, 0 0 , 0 0 0 2 00 0 02 2 22 2 2i i iv q v q ii i i = = 20 0 00 1 1i i i = + = dan( )22 1 2 1, 0 1 1 0 1 2 v q v q i i = + + = + += , maka 2 1 2 122 1 2 122,0,22iv q v qqv q v q = = . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 23iii.Karena 3 1 3 1 2 3 22202 22 2, , 0 02 212 222iv q v q q v q i ii = 0 02 20 01 1 1 02 2i ii i = = dan( )( )3 1 3 1 2 3 2, , 0 0 0 1 0 1 v q v q q v q i i = + + = + + = maka 3 1 3 1 2 3 233 1 3 1 2 3 20, ,, ,0v q v q q v qq iv q v q q v q = = . Dari poin i, ii, dan iii diperoleh basis ortonormal untuk 3Cadalah 2202 20 , 0 ,02 222iii . Akan tetapi algoritma Gram-Schmidt diatas terbatas dengan inputnya yang merupakan basis dari suatu ruang vektor. Bagaimanakah jika syarat basis diperlemah dengan hanya menjadi himpunan pembangun, yaitu dengan menghilangkan syarat bebas linearnya. Diperhatikan bahwa, jika syarat bebas linear dihilangkan maka dapat muncul kemungkinan 1 1 2 2 1 1, , ... , 0i i i i i iv q v q q v q q v q =untuk suatu nilai i, St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 24akibatnya vektor iqtidak dapat didefinisikan. Dengan demikian harus dicari suatu vektor lain, misalkan vektorq , yang merupakan vektor normal dan ortogonal dengan 1 2 1, ,...,iq q q vektor yang lain. Vektor q ini dapat dipilih sebagai sebarang vektor yang tidak dibangun oleh 1 2 1, ,...,iq q q pada ruang vektor yang sama yang kemudian diortonormalkan. Berikut merupakan algoritma Gram-Schmidt untuk himpunan pembangun. Algoritma 4.4 (Algoritma Gram-Schmidt 2) Input: Ruang vektor mCdengan himpunan pembangun { }1 2, ,...,nv v v .Output : Basis ortonormal { }1 2, ,...,nq q quntuk ruang vektor mC . 1.Dibentuk 111vqv= . 2.Untuk2, 3, 4,..., i n =dibentuk 1 1 2 2 1 11 1 2 2 1 1, , ... ,, , ... ,i i i i i iii i i i i iv q v q q v q q v qqv q v q q v q q v q = 3.Jika0iq = , maka pilih sebarang vektor mqCyang bukan merupakan kombinasi linear dari vektor 1 2 1, ,...,iq q q dan dibentuk 1 1 2 2 1 11 1 2 2 1 1, , ... ,, , ... ,i iii iq q q q q q q q q qqq q q q q q q q q q = . Contoh 4.5 Misalkan diketahui 3Cmemiliki himpunan pembangun 1 0 00 , 0 , 01 i i .Misalkan 1 21 00 , 01v vi = = dan 300 vi = . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 25i.Karena( )21 1 1* 1 0 1 0 1 2 v v v i i = = + + = + += , maka 11122022vqvi = = . ii.Karena 2 1 2 12 2 20 0 02 2 22, 0 0 , 0 0 0 021 1 12 2 22 2 2v q v q ii i i = = 02 20 0 01 1 12 2i i = = dan 22 1 2 11 1 1 2, 0 02 2 2 4 4 2i iv q v q = + + = + + = , maka 2 1 2 122 1 2 122,0,22iv q v qqv q v q = = . iii.Karena 3 1 3 1 2 3 22202 222, , 0 0 0222 222iv q v q q v q iii = St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 261 10 02 20 0 0 002 2i i i = = , maka harus dipilih vektor 3qCdengan q merupakan vektor normal dan ortogonal dengan 1qdan 2q . Dengan demikian dapat dipilih 300q q i = = . Dari poin i, ii, dan iii diperoleh basis ortonormal untuk 3Cadalah 2202 20 , 0 ,02 222iii . Kemdian, misalkan diketahui matriks m nAC . Diperhatikan bahwa matriks A dapat disajikan sebagai matriks yang dibentuk dari vektor-vektor kolom, yaitu 1 2...nA a a a = dengan mia C . Menurut Teorema 2.5, diketahui bahwa himpunan { }n mV Ax x = C Cmerupakan suatu ruang vektor atasC. Untuk sebarang v V , maka 0v Ax =untuk suatu 10nnzxz = . C , dengan kata lain 0 1 1 2 2 n nv Ax a z a z a z = = + + + dengan 1 2, ,...,nz z z C. Karena Vmerupakan ruang vektor bagian dari mCdan karena menurut Teorema 4.1 mCmemiliki basis ortonormal, maka V juga memiliki basis ortonormal. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 27Misalkan { }1 2, ,...,mnq q q Cmerupakan basis ortonormal untuk V. Karena 1 2, ,...,mna a a C , maka 1 2, ,...,na a adapat disajikan sebagai kombinasi linear dari basis ortonormal tersebut, yaitu: 1 1 11 2 21 12 1 12 2 22 21 1 2 2n nn nn n n n nna q r q r q ra q r q r q ra q r q r q r= + + += + + += + + +

.

,dengan ijr C. Menggunakan Algoritma Gram-Schmidt 2 (Algoritma 4.4) jumlah konstanta ijrdapat diminimalkan, yaitu dengan mendapatkan basis ortonormal { }1 2, ,...,nq q q dari himpunan pembangun{ }1 2, ,...,na a a . Dengan demikian diperoleh: 1112 1 2 122 1 2 11 1 2 2 1 11 1 2 2 1 1,,, , ... ,., , ... ,n n n n n nnn n n n n naqaa q a qqa q a qa q a q q a q q a qqa q a q q a q q a q == = . Vektor-vektor persamaan diatas dapat dipindah posisi sehingga persamaan diatas menjadi seperti berikut: 1 1 12 1 2 1 2 1 2 1 21 1 1 1 1 1 2 2 1 1, ,, , , , ... , ,n n n n n n n n n n n na a qa q a q a q a q qa q a q q a q a q a q q a q q a q q == + = + + + .

atau dengan kata lain 1 1 112 1 12 2 221 1 1 1,n n n n n n nna q ra q r q ra q r q r q r == += + + +.

St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 28dengan 1 1 2 2 1 1, ,, , ... , ,0 ,i jij j j j j j jq a i jr a q a q q a q q a q i ji j < > < = < > < > < > =>. Dalam notasi matriks: 11 11 2 1 2... ...nn nnnQ Rr rA a a a q q qr = =

.Hubungan ini dapat pula ditulis sebagai: . A QR =DenganQ, matriks uniter yang dibentuk oleh basis ortonormal { }1 2, ,...,nq q q . Dengan R, matriks segitiga atas yang dibentuk oleh nilai ijr . Secara umum berikut algoritmanya. Algoritma 4.6 (Algoritma Dekomposisi QR) Input: Matriks m nAC .Output : Matriks uniter Qdan matriks segitiga atasRsehinggaA QR = . 1.Matriks A dimisalkan sebagai matriks yang dibentuk dari vektor-vektor kolom, yaitu 1 2...nA a a a = , dengan mia C . 2.Dibentuk basis ortonormal { }1 2, ,...,nq q qdari himpunan { }1 2, ,...,na a a dengan menggunakan Algoritma Gram-Schmidt 2 (Algoritma 4.4). 3.Dibentuk matriks uniter 1 2...nQ q q q = . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 294.Dibentuk matriks segitiga atas11 1nnnr rRr =

.dengan 1 1 2 2 1 1, ,, , ... , ,0 ,i jij j j j j j jq a i jr a q a q q a q q a q i ji j < > < = < > < > < > =>. Contoh 4.7 Diketahui matriks 3 21 00 1A i i = C , akan dicari bentuk dekomposisi QR-nya. Matriks A dapat dinyatakan ke dalam bentuk matriks kolom [ ]1 2A a a = , dengan 110a i = dan 201a i = . Menurut Algoritma Gram-Schmidt 2 (Algoritma 4.4) diperoleh: i.Karena( )211 0 2 a i i = + + = , maka 11122220aq ia = = . ii.Karena 2 1 2 12 2 22 2 20 0 02 2 2 2, ,2 2 2 21 1 10 0 0a q a q i i i i i i = = 1 12 202 210 1i ii = = dan 2 1 2 11 1 3, 14 4 2a q a q = + += , St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 30maka 2 1 2 122 1 2 166,66 ,2 66a q a qq ia q a q = = . iii.Karena diperlukan satu vektor ortonormal lagi, maka dipilih vektor 3001q = Cdan vektor tersebut diortonormalkan. Karena 1 1 2 26 26 202 62 6, , 0 062 6102 66q q q q q q q i i = 6 118 306018 316 13 18ii = = dan 1 1 2 21 1 1 3, ,9 9 9 3q q q q q q q = + + =maka 1 1 2 231 1 2 233, ,33 , ,33q q q q q q qq iq q q q q q q = = . Dari poin i, ii, dan iii dapat dibentuk matriks Q, yaitu 6 3 22 6 32 6 32 6 32 6 306 3Q i i i = . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 31Karena diperoleh 12 a =1 22,2q a =2 1 2 13,2a q a q =maka dapat dibentuk matriks R, sebagai berikut 2223020 0R = . Jadi, diperoleh bentuk dekomposisi6 3 2 222 6 3 21 02 6 3 302 6 3 20 10 0 2 6 306 3AR Qi i i i i = . Bentuk dekomposisi diatas disebut sebagai bentuk QR Penuh, karena matriks Q merupakan matriks persegi. Sedangkan bentuk dekomposisi 6 22 621 0222 632 600 122 606ARQi i i i = . disebut sebagai bentuk QR Tereduksi, karena matriks Q bukan merupakan matriks persegi. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 32Berikut merupakan beberapa sifat yang ada pada Dekomposisi QR. Teorema 4.8 Setiap matriks m nACmemiliki bentuk dekomposisi QR. Bukti. Menurut Teorema 4.1 dan Algoritma Gram-Schmidt 2 (Algoritma 4.4), ruang vektor { }n mV Ax x = C Cmemiliki basis ortonormal dan dengan demikian terjamin eksistensi dari matriks Q. Sedangkan matriks R dapat dibentuk dari konstanta-konstanta dari kombinasi linear basis ortonormal terhadap vektor-vektor kolom matriks A. Teorema 4.9 Setiap matriks m nAC memiliki dekomposisi QR penuh dan tidak setiap bentuk dekomposisi QRpenuh tunggal. Bukti.Bukti merupakan akibat dari Algoritma Dekomposisi QR (Algoritma 4.6) yang selalu menghasilkan matriks Q sebagai matriks persegi, yaitu dengan penggunaan Algoritma Gram-Schmidt 2 (Algoritma 4.4). Kemungkinan tidak tunggal sebagai akibat dari langkah ke-3 pada Algoritma Gram-Schmidt 2 (Algoritma 4.4), yaitu pengambilan sebarang vektor untuk diortonormalkan. Teorema4.10 Setiap matriks m nACdenganm n yang non-singular memiliki dekomposisi QR tereduksi yang tunggal dan diagonal utamanya matriks R merupakan bilangan positif. Bukti. Karena matriks A non-singular, akibatnya matriks A fullrank, yaitu setiap vektor kolomnya bukan merupakan kombinasi linear dari vektor kolom yang lain. Sehingga kasus vektor 1 1 2 2 1 1, , ... , 0i i i i i iv q v q q v q q v q =untuk suatu nilai itidak akan terjadi. Dengan demikian tidak ada pengambilan sebarang vektor yang ortonormal pada Algoritma Gram-Schmidt 2 (Algoritma 4.4) di langkah ke-3. Karena itu bentuk QR tereduksinya adalah tunggal. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 33Terkahir, jelas diagonal utama dari matriks R adalah bilangan positif. Sebab diagonal utama matriks R adalah nilai 1 1 2 2 1 1, , ... ,j j j j j ja q a q q a q q a q < > < > < > , dimana nilainya akan selalu positif. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 34BAB V DEKOMPOSISI CHOLESKY Khusus untuk matriks hermitian yang definit positif dapat didekomposisi menjadi perkaliandariduamatrikssegitiga,dimanamasing-masingmerupakankonjugat transposeyanglain.DekomposisitersebutdinamakandekomposisiCholesky. Pembahasan dekomposisi Cholesky dimulai dengan sifat-sifat pada matriks hermitian dan matriks definit positif.Teorema5.1 Entri-entri diagonal utama suatu matriks hermitian adalah bilangan real. Bukti. Entri diagonal pada suatu matriks hermitian merupakan bilangan kompleks yang apabila dikonjugatkan tetap merupakan bilangan itu sendiri. Dengan demikian bilangan tersebut tidak boleh memiliki komponen imajiner, dan akibatnya bilangan tersebut haruslah bilangan real. Teorema5.2 Diketahui m mACmerupakan matriks hermitian yang definit positif dan m nQC merupakan matriks fullrank denganm n , maka matriks* Q AQ juga merupakan matriks hermitian yang definit positif. Bukti. Matriks* Q AQ merupakan matriks hermitian, karena( * )* * * * Q AQ Q A Q Q AQ = = . Juga definit positif, karena untuk sembarang vektor nxCdengan0 x , berlaku 0 Qx dan akibatnya*( * ) ( ) * ( ) 0 x Q AQ x Qx A Qx = > . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 35Teorema5.3 Entri-entri diagonal utama matriks hermitian yang definit positif adalah bilangan real positif. Bukti. Misalkan m mACmerupakan matriks hermitian yang definit positif. Menurut Teorema 5.1, berakibat entri-entri diagonal utama A adalah bilangan real. Sehingga tinggal dibuktikan bahwa bilangan real tersebut positif. Kemudian dipilih matriks 1 miQC , yaitu 1imaQa = .dengan0ja =untukj i dan1ja =untukj i = . Dengan demikian untuk setiap 1 i m , iQmerupakan vektor satuan baku pada mC . Matriks iQmerupakan matriks fullrank, dan menurut Teorema 5.2 berakibat* 0i i iiQ AQ a = >untuk setiap 1 i m . Jadi, terbukti bahwa entri-entri diagonal utama A adalah bilangan real positif. Proses dekomposisi Cholesky mengacu kepada proses Eliminasi Gauss. Berikut akan dibahas mengenai hal-hal terakait dengan Eliminasi Gauss. Definisi 5.4 (Matriks Elementer) Matriks persegi m mRCdisebut matriks elementer jika matriks tersebut dapat diperoleh dari matriks identitas m mICdengan melakukan operasi baris (kolom) elementer tunggal. Lemma 5.5 Setiap matriks elementer memiliki invers, dan inversnya juga merupakan matriks elementer. Hal yang serupa juga berlaku untuk transpose dari sebarang matriks elementer. Lemma 5.6 Setiap matriks elementer merupakan matriks fullrank dan hasil kali matriks-matriks elementer juga merupakan matriks fullrank. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 36Contoh 5.37 Diketahui matriks identitas 3 31 0 00 1 00 0 1I = C , maka: i.Matriks 10 1 01 0 00 0 1R = , merupakan matriks elementer karena merupakan hasil operasi baris elementer dari matriks I dengan menukar baris pertama dengan kedua. ii.Matriks 21 0 00 2 00 0 1R = , merupakan matriks elementer karena merupakan hasil operasi baris elementer dari matriks I dengan mengalikan baris kedua dengan suatu skalar, yaitu 2. iii.Matriks 31 0 00 1 00 2 1R = , merupakan matriks elementer karena merupakan hasil operasi baris elementer dari matriks I dengan menjumlahkan baris ketiga dengan kelipatan baris kedua. iv.Matriks 42 0 00 2 00 0 2R = , bukan merupakan matriks elementer karena untuk menghasilkan matriks 4Rdari matriks I menggunakan operasi baris (kolom) elementer memerlukan sekurang-kurangnya tiga kali operasi. Lemma 5.8 Diketahui matriks m nACdan matriks'm nACsebagai hasil operasi baris (kolom) elementer tunggal terhadap matriks A, maka terdapat matriks elementer, 'n nR RCsehingga' ' A R A =dan' A RA = . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 37Definisi 5.9(Matriks Bentuk Eselon Baris) Matriks persegi m mACdengan 11 11mm mma aAa a =

..

dikatakan dalam bentuk eselon baris jika dan hanya jika0ija = untuki j > . Contoh 5.10 Matriks 2 0 30 0 10 0 4A = merupakan matriks dalam bentuk eselon baris. Definisi 5.11 (Matriks Bentuk Eselon Kolom) Matriks persegi m mACdengan 11 11mm mma aAa a =

..

dikatakan dalam bentuk eselon kolom jika dan hanya jika0ija = untukj i > . Contoh 5.12 Matriks 2 0 05 00 0A ii = merupakan matriks dalam bentuk eselon kolom. Definisi 5.13 (Eliminasi Gauss) Diketahui matriks persegi m mAC . Eliminasi Gauss adalah serangkaian operasi baris (kolom) elementer yang dilakukan terhadap matriks A sehingga menghasilkan matriks dalam bentuk eselon baris (kolom). St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 38Contoh 5.14 Misalkan diketahui matriks 1 0 020 2 4A i i = yang bukan merupakan matriks dalam bentuk eselon baris. Akan dilakukan Eliminasi Gauss pada matriks A sehingga menghasilkan matriks eselon baris dengan langkah-langkah sebagai berikut: i.Baris kedua dikurangi dengan kelipatanidari baris pertama dan menghasilkan matriks 11 0 00 20 2 4A i = dan matriks elementer 11 0 01 00 0 1R i = sehingga berlaku 1 1A R A = . ii.Baris ketiga dikurangi dengan baris kedua dan menghasilkan matriks 21 0 00 20 0 4A ii = dan matriks elementer 21 0 00 1 00 1 1R = sehingga berlaku 2 2 1A R A = . Matriks 2Amerupakan matriks dalam bentuk eselon baris, sehingga diperoleh 2 2 1 2 1A R A R R A = = . Dari Contoh 5.14, Eliminasi Gauss juga menghasilkan matriks-matriks elementer 1 2, ,...,kR R Runtuk suatuk N , sehingga 1 2 1'k kA R R R R A= dengan' Amerupakan bentuk eselon baris matriks A. Hal serupa juga berlaku bagi bentuk eselon kolom. Proses dekomposisi Cholesky adalah menggunakan Elimininasi Gauss, yaitu dengan menghasilkan matriks eselon baris kemudian matriks eselon kolom berturut-turut dan berulangkali sehingga pada akhirnya akan diperoleh matriks eselon baris sekaligus eselon kolom yang berupa matriks identitas. Berikut akan dijelaskan tahapan demi tahapan dekomposisi Cholesky. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 39Misalkan 11 11mm mm mma aAa a =

.. C

merupakan matriks hermitian yang definit positif.Diperhatikan, apabila memandang nilai entri 11amaka akan muncul dua kasus, yaitu 111 a =dan 111 a . Dari dua kasus tersebut, akan diselidiki dulu untuk kasus 111 a = . Misalkan juga 11 11 * zAz K = ,dengan 21111mmaza = . Cdan ( ) ( )22 21 112mm mm mma aKa a =

.. C

. Pertama, akan dicari matriks eselon baris dari matriks A menggunakan proses Eliminasi Gauss. Menggunakan operasi baris elementer pada matriks A, dapat dibentuk matriks 1m mACdengan 111 1 1 11 *0 *zAK z z = , 11000m = . C , dan memenuhi hubungan1 11 1 1 1 1 11 * 1 00 *zAK z z z I = ... (a) dengan ( ) ( ) 1 11m mI Cmerupakan matriks identitas. Selanjutnya, menggunakan operasi kolom elementer pada matriks 1A , dapat dibentuk matriks 1'm mACdengan 111 1 1 11 0'0 *AK z z = , dan memenuhi hubungan 1 111 1 1 1 1 11 * 1 00 0 *zAI K z z = ... (b). Dari (a) dan (b) diperoleh 1 1 1 11 1 1 1 1 1 1 1 1 11 * 1 * 1 0 1 00 0 *z zAz K I z I K z z = = . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 40Untuk kasus 111 a , maka menurut Teorema 5.3 berakibat 11a R dan 110 a > , sehingga dengan demikian 111a dan 11aterdefinisi. Karena untuk 111 a =juga berlaku 111 a = , maka secara umum untuk sebarang 11a R diperoleh: 111 1 11111 111 1 1 1 1 1 11 1 1 1 111 1 1 11*0 1 0*' **00zaaa za A R A R z z zI K z Ka I a = = = . Selanjutnya akan ditunjukkan bahwa matriks 1' Amerupakan matriks hermitian yang definit positif. Diperhatikan bahwa matriks 1Rmerupakan hasil dari perkalian matriks-matriks elementer yang membentuk matriks eselon baris 1A . Menurut Teorema 5.6 berakibat 1Rfullrank, dan karena 1Rmatriks persegi berakibat 1Rmemiliki invers. Menurut Teorema 5.5, hal yang serupa juga berlaku untuk matriks 1* R . Dengan demikian diperoleh: ( )111 1 1 1 1 1' * * ' A R A R R A R A= = . Karena 1Rdan 1* Rkeduanya fullrank, maka 11R dan( )11* R juga fullrank, sehingga menurut Teorema 5.2, berakibat matriks 1' Amerupakan matriks hermitian yang definit positif. Jika dipilih matriks ( ) 1 m mQ C , dengan ( )( )( )( )11 1 121 2 131 3 11 10 01 00 00 1mmmm m ma aa aQ a aa a = = . .. . maka matriks Q tersebut merupakan matriks fullrank dan menurut Teorema 5.2 berakibat matriks 1 11 111*' *z zQA Q Ka= juga merupakan matriks hermitian yang positif definit. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 41Dengan demikian entri 11bpada matriks ( )( ) ( )( )( ) ( )11 1 11 11 11111 1 1 1*mm mm m mb bz zKab b =

.. C

menurut Teorema 5.3 merupakan bilangan real positif. Jadi, menggunakan langkah-langkah Eliminasi Gauss seperti yang dioperasikan pada matriks A, maka matriks ( ) ( ) 1 11 1111*m mz zKa Cdapat disajikan menjadi bentuk 1 11 2 2 211*' *z zK R A Ra = , dengan ( ) ( ) 1 12 2 2, ', *m mR A R C . Karena matriks A berukuranm m maka matriks 2Rdan 2' Adiperbesar ukurannya menjadi 121 21 0''0 'AA = dan 121 21 0'0RR = sehingga dengan demikian diperoleh 1 1 1 1 2 2 2 1' * ' '' * * A R A R R R A R R = = . Secara umum, matriks ( ) ( ) m k m kA Cdapat diperbesar menjadi berukuranm m , yaitu merupakan matriks 0 *'0m m k kkIAA = C , dengan kImatriks identitas di k k C , ( )0k m k C . Sifat pada matriks 2'' Aserupa dengan sifat pada matriks 1' A , yaitu 2'' Amerupakan matriks hermitian yang definit positif. Dengan demikian langkah-langkah Eliminasi Gauss dapat terus dilakukan sehingga secara umum akan diperoleh ( ) ( )1 2 1 2*k k kA R R R A R R R = . Diperhatikan bahwa ketikak m = , maka m mkA I= C , dan akibatnya ( )( )1 2 1 2* *m mA R R R I R R R RR = =dengan 1 2 mR R R R = yang merupakan matriks segitiga. Dekomposisi ini dinamakan dekomposisi Cholesky dan berikut merupakan algoritmanya. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 42Algoritma 5.15 (Algoritma Dekomposisi Cholesky) Input: Matriks hermitian yang definit positif m mAC .Output : Matriks segitiga atasRsehingga* A RR = . 1.Dibentuk matriks 1C A =dan1 k = . 2.MatrikskCdimisalkan sebagai 10 00 *0kk kk kk kIC c zz K = , dengan 1 kI matriks identitas di ( ) ( ) 1 1 k k C , kkz C , dan kK k k C . 3.Dibentuk matriks 110 00 00kk kk kkm kkkIR czIc = , Dengan kImatriks identitas di ( ) ( ) 1 1 k k C , dan 10k vektor nol di 1 kC . 4.Dibentuk matriks 11 110 00 1 0 **0 0kk kk kk kkkICz zKc+ = . 5.Jika matriks 1 k kC I+ , dengan kImerupakan matriks identitas di k k C , maka langkah 2 5 diulang dengan nilai1 k k = + . Jika 1 k kC I+ = , maka lanjutkan ke langkah 6. 6.Dibentuk matriks 1 2 1 k kR R R R R=. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 43Untuk mengecek apakah suatu matriks hermitian bersifat definit postif dapat menggunakan teorema ini. Teorema 5.16 (Kondisi Sylvester) Diketahui A matriks hermitian. Matriks A definit positif jika dan hanya jika determinan dari setiap submatriks utamanya bernilai positif. Bukti. Bukti dapat dilihat pada paper karya George T. Gilbert yang dapat didownload di alamathttp://math.huji.ac.il/~andrei/Teaching/Advanced_Infi_1/PositiveDefiniteMatricesAndSylvester_Gilbert.pdf. Contoh 5.17 Diketahui matriks hermitian 4 21 02 0 4i iA ii = . Submatriks utamanya adalah [ ]4 , 41ii , dan A itu sendiri. Karena[ ] ( )det 4 4 = , 4det 51ii = , dan( ) det 8 A = , maka matriks A definit positif. Contoh 5.18 Akan dibentuk dekomposisi Cholesky dari matriks 4 21 02 0 4i iA ii = . Menurut Contoh 5.17, matriks A merupakan matriks hermitian yang definit positif. i.Untuk1 k = , diperoleh 114 c = , 12izi = , dan 11 00 4K = . Dibentuk matriks 12 0 01 020 1iRi = . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 44Karena 1 11113 11 0 1 2* 14 20 4 2 4 1 432z zKc = = , maka 21 0 03 104 210 32C = . ii.Karena 2C I , maka langkah 2-4 pada Algoritma 5.15 diulangi dengan2 k =dan diperoleh 2234c = , 212z = , dan [ ]23 K = . Dibentuk matriks 21 0 030 0230 13R = . Karena[ ]2 2222* 4 81343 3z zKa = = , maka diperoleh 31 0 00 1 080 03C = . iii.Karena 3C I , maka langkah 2-4 pada Algoritma 5.15 diulangi dengan3 k =dan diperoleh 33113c = , dan 3z , 3Ktidak ada. Dibentuk matriks 31 0 00 1 02 20 03R = dan 41 0 00 1 00 0 1C = . Karena 4C I = , maka diperoleh matriks St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 451 2 22 0 0 2 0 0 1 0 01 0 03 31 0 0 0 0 1 0 02 22 22 23 0 1 0 03 2 2 0 13 333i iR R R Rii = = = dan memenuhi hubungan *22 0 024 23 3 31 0 0 02 2 322 0 42 23 2 2 0 03 33AR Riii iiiii = . Lemma 5.19 Setiap matriks hermitian yang definit positif memiliki dekomposisi Cholesky yang tunggal. Bukti.Ketunggalan dekomposisi Cholesky disebabkan oleh hal-hal sebagai berikut: i.Untuk setiapk , nilai kkcdipilih sebagai bilangan positif dan dengan demikian terdapat dengan tunggal kx+Rsehingga kk kc x = . ii.Vektor kkkzc tunggal dan juga matriks *k kkkkz zKc. iii.Karena ii. maka untuk setiapkmatriks kRtunggal, dan hal serupa juga berlaku bagi matriks 1 2 1 k kR R R R R=. Jadi, setiap dekomposisi Cholesky dari suatu matriks hermitian yang definit positif tunggal. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 46BAB VI DEKOMPOSISI SCHUR Menurut Teorema 2.31, setiap matriks Hermitian dapat didiagonalisasi yaitu disajikan sebagai perkalian matriks-matriks uniter dengan matriks diagonal. Akan tetapi, jika syarat matriks Hermitian diperlemah menjadi matriks persegi biasa, maka apakah proses diagonalisasi masih dapat terjadi? Secara umum tidak, akan tetapi ada proses diagonalisasi khusus yang nyaris serupa dengan proses diagonalisasi pada Teorema 2.31, yaitu menyajikan suatu matriks persegi sebagai perkalian matriks-matriks uniter dengan matriks segitiga atas. Proses diagonalisasi ini dikenal dengan nama dekomposisi Schur, dan menyatakan bahwa setiap matriks persegi m mACdapat disajikan dalam bentuk * A U TU =dengan m mUCmatriks uniter, dan m mTCmatriks segitiga atas. Proses dekomposisi ini didasari oleh teorema berikut: Teorema 6.1 Diketahui matriks persegi m mACdengan C merupakan salah satu nilai eigennya dan mxCmerupakan vektor eigen yang bersesuaian dengan . Jikam mSCmerupakan matriks non-singular dengan kolom ke-i nya adalah vektor x, maka kolomke-i dari matriks 1S AS adalah ie dengan 1mimaea = . C ,1ja =untukj i = , dan 0ja =untukj i . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 47Bukti. Misalkan [ ]1 2 1 1 i i mS s s s x s s += . Karena 1S S I=maka[ ]1 11 2 1 11 1 1 1 1 11 2 1 1

i i mi i mS S S s s s x s sS s S s S s S x S s S s I + += = = dan akibatnya 1S x = ie . Pada 1S AS, menjadi [ ][ ]1 11 2 1 111 2 1 11 1 1 1 1 11 2 1 1

i i mi i mi i mS AS S As As As Ax As AsS As As As x As AsS As S As S As S x S As S As + + +== = karena Ax=x sehingga diperoleh 1iS x e = . Teorema 6.2 Diketahui matriks persegi,m mA BC . Jika A dan B merupakan matriks uniter, maka ABjuga merupakan matriks uniter. Untuk melakukan proses dekomposisi, pertama dicari dahulu nilai-nilai eigen dari matriks A. Karena matriks A berukuranm m , maka terdapat sejumlah m nilai eigen beserta m vektor eigen yang bersesuaian dengan nilai-nilai eigen tersebut. Misalkan ivmerupakan vektor eigen yang bersesuaian dengan i dan 1 i m . Kemudian, dipilih sebarang tepat satu dari m vektor eigen tersebut sebut saja 1kvyang bersesuaian dengan nilai eigen 1kdengan 11 k m . Jika vektor eigen kvbukan merupakan vektor normal, maka vektor tersebut dinormalkan, yaitu dibentuk vektor 111'kkkvvv= . Perlu diperhatikan bahwa menormalkan vektor eigen tidak akan berpengaruh terhadap nilai eigen yang bersesuaian dengannya, karena pada dasarnya hanya mengalikan vektor eigen tersebut dengan skalar. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 48Kemudian, dibentuk himpunan ortonormal { }11', ,...,k nV v w w = . Pembentukan himpunan ortonormal tersebut dapat menggunakan Algoritma Gram-Schmidt 2 (Algoritma 4.4). Apabila dibentuk matriks yang kolom-kolomnya adalah anggota V maka matriks tersebut akan berwujud matriks uniter, misalkan 1kUmerupakan matriks yang dimaksud, maka 1 11'k k nU v w w = . Sehingga dapat dibentuk 1 11*k kU AU T =atau 1 11*k kA U TU = . Matriks uniter 1kUmerupakan matriks non-singular, dan menurut Teorema 6.1 matriks 1Takan berbentuk 111 1*0kzK , dengan 11 100 ,0mz = . Cdan ( ) ( ) 1 11m mK C . Jika submatriks 1Kbelum berbentuk matriks segitiga atas, maka dilakukan proses dekomposisi yang serupa. Misalkan 2 21 2*k kK U T U = . Karena ( ) ( )21 1 m mkU C , maka 2kUdapat diperbesar menjadi suatu matriks uniter berdimensim m , yaitu matriks 221 0*'0kkUU = , dengan 10mC . Dengan demikian akan diperoleh 12 22 212 21 22 21 1* 1 0 1 0 *' ' '*0 * 0 00kk kk kzB zT U T UU U KK = = = , dengan ( ) ( ) 122 220km mkzB = C , 2 22 20 , zC , dan ( ) ( ) 2 22m mK C . Karena 1 11*k kA U TU =dan 2 21 2' ' '*k kT U T U = maka diperoleh( ) ( )1 2 2 12 1' ' '* *k k k kA U U T U U = . Secara umum proses dekomposisi ini akan menyajikan A dalam bentuk( ) ( )1 2 2 1* * *k k k k k kn nnA U U U T U U U = St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 49dengan matriks *0n nnn nB zTK = dengan ( ) ( )10nkm n m nnkB = .C

, ( )0 , 0n m nn nz C , dan ( ) ( ) m n m nnK C . Diperhatikan bahwa matriks nBmerupakan matriks segitiga atas dengan entri-entri diagonalnya adalah nilai eigen 1 2, ,...,nk k k . Proses dekomposisi terus dilakukan sampai nTyang memiliki submatriks nKyang berbentuk matriks segitiga atas. Proses ini suatu saat akan terhenti, karena ukuran submatriks nKyang semakin mengecil, sehingga perulangan proses akan terjadi maksimal sejumlah m kali. Pada akhirnya akan terbentuk( ) ( )( ) ( )1 2 2 111 2 1 * * ** * * ** * * .k k k k k kn nk k k k k kn n nA U U U T U U UU U U T U U U == Jika diambil matriks 11* * *k k kn nU U U U =, maka menurut Teorema 6.2 matriks U juga merupakan matriks uniter karena merupakan perkalian dari matriks-matriks uniter, sehingga diperoleh bentuk * A U TU = . Teorema berikut dapat mempermudah proses dekomposisi, yaitu pada langkah mencari nilai eigen matriks 1 2, , ,...,kA T T T . Teorema 6.2 Diketahui matriks persegi,m mA BC . Jika 1B S AS= , untuk suatu matriks non-singular m mSC , maka nilai-nilai eigen matriks A dan B sama akan tetapi tidak selalu vektor-vektor eigennya juga sama. Jadi, menurut teorema tersebut nilai-nilai eigen matriks 1 2, , ,...,kA T T Tsama. Dengan demikian langkah untuk menentukan nilai eigen hanya perlu dilakukan sekali saja. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 50Secara umum berikut algoritmanya. Algoritma 6.3 (Algoritma Dekomposisi Schur) Input: Matriks persegi m mAC .Output : Matriks uniter U dan segitiga atasTsehingga* A U TU = . 1.Dicari nilai eigen matriks A, misalkan { }1 2, ,...,mE =merupakan himpunan nilai eigennya. 2.Dibentuk matriks 1C A =dan1 k = . 3.Dipilih sebarang knE , maka terdapat vektor eigen knvyang bersesuaian dengan kn. 4.Dibentuk { }knE E = . 5.Jika nkvbukan vektor normal, maka bentuk'nknknkvvv= . Jika nkvmerupakan vektor normal, maka bentuk'nk nkv v = . 6.Dibentuk himpunan ortonormal{ }1', ,...,k nk m kV v w w = dan matriks uniter [ ]'1'k nk m kU v w w =. 7.Dibentuk matriks '0 *0k kkk kIUU = ,dengan kImatriks identitas di ( ) ( ) 1 1 k k C , dan ( ) ( ) 1 10k m k +C . 8.Dibentuk matriks*k k k kT U C U = . 9.Matriks kTakan berbentuk *0k kk kB zK dengan 10knk kknB = .C

, ( )0 ,k m kk kz C , dan ( ) ( ) m k m kkK C . Matriks kBmerupakan matriks segitiga atas dengan entri-entri diagonalnya adalah nilai eigen 1 2, ,...,kn n n . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 5110. Jika matriks kKbukan merupakan matriks segitiga atas makalangkah 2-10 diulang dengan 1 k k = +dan k kC K = . Jika matriks kKmerupakan matriks segitiga, maka lanjutkan ke langkah 11. 11. Bentuk matriks uniter 2 1* * *kU U U U =. Contoh 6.4 Akan dibentuk dekomposisi Schur dari matriks 1 1 2 00 2 01 1iA ii = . Nilai-nilai eigen matriksA adalah 1i = , 22i = , dan 31 = . Dibentuk himpunan{ } { }1 2 3, , , 2 ,1 E i i = = . Dipilih 122ni = =dan himpunan E menjadi{ } { } 2 ,1 E E i i = = . Vektor eigen yang bersesuaian dengan 22i = , adalah 2110v = . Vektor 2110v = bukan vektor normal, maka dinormalkan menjadi 21 2' 1 20v = . Dibentuk himpunan ortonormal 1 2 1 201 2 , 0 , 1 20 0Vi = . Dibentuk matriks uniter 1 11 2 0 1 2' 1 2 0 1 20 0U Ui = = . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 52Dibentuk matriks1 1 1 11 2 0 1 21 2 1 2 0 1 1 2 0* 0 0 0 2 0 1 2 0 1 21 1 0 01 2 1 2 02 0 1 20 2 .0 0 1iT U CU i ii ii ii i = = = Diperoleh matriks 120 1i iK = , karena matriks 1Kmerupakan matriks segitiga atas maka proses dekomposisi berhenti dan diperoleh *1 2 0 1 2 2 0 1 21 1 2 0 1 2 1 2 00 2 0 1 2 0 1 2 0 2 0 01 1 0 0 0 0 11 2 1 2 0T UUi iiA i i i ii i = = . Lemma 6.5 Setiap matriks persegi m mACmemiliki dekomposisi Schur dan dekomposisi tersebut tidak selalu tunggal. Bukti. Algoritma Dekomposisi Schur (Algoritma 6.3) menjamin bahwa setiap matriks persegi memiliki bentuk dekomposisi. Dekomposisi tersebut tidak tunggal karena ada pembentukan himpunan ortonormal pada langkah 6, yaitu ada vektor ortormal yang dapat berbeda. Selain itu, pemilihan vektor eigen juga berpengaruh kepada bentuk dari himpunan ortonormal tersebut. Sebagai contoh,*1 1 2 0 0 1 0 1 1 0 0 10 2 0 0 0 1 0 1 1 2 1 0 01 1 1 0 0 0 0 2 0 1 0U T Ui iA i ii i = = merupakan bentuk lain dari dekomposisi Schur matriks A yang berbeda dari Contoh 6.4. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 53BAB VII METODE LEAST SQUARE Pada bidang aljabar linear, seringkali persamaanAx b =tidak memiliki solusi eksak. Salah satunya, disebabkan karena vektor b bukan merupakan elemen dari Range(A). Yaitu sistem persamaan tersebut memiliki jumlah persamaan yang lebih banyak dari jumlah peubah bebasnya. Diperhatikan sistem persamaan berikut, 1 1 71 1 01 2 7xy = . Sistem persamaan tersebut tidak memiliki solusi eksak. Karena itu solusi pada sistem persamaan tersebut dapat dipilih sebagai suatu vektor x elemen Range(A) yang jaraknya dengan vektor b paling pendek (minimal) dibandingkan vektor-vektor lain dalam Range(A). Solusi tersebut memang bukan solusi eksak, tetapi "mendekati" solusi yang memenuhi sistem persamaan tersebut.Dengan demikian dapat dibentuk vektor residualr b Ax = dan akan dicari vektor x elemen Range(A) sehingga norma vektor r minimal. Agar norma vektor r minimal, vektorr b Ax = harus ortogonal terhadap Range(A), yaitu : , 0* 0*( ) 0* * .A rA rA b AxA b A Ax= = = = Sistem permasalahan* * A Ax A b =disebut sebagai persamaan normal dari metode Least Square. Sebagai tambahan bahwa sistem permasalahan normal dapat diubah bentuk menjadi( )1* * x A A A b= . Matriks( )1* * A A A disebut dengan pseudoinverse (invers semu) dari matriks A. St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 54 Contoh 7.1 Akan dicari penyelesaian sistem persamaan 1 1 71 1 01 2 7xA bxy = menggunakan metode Least Square.Menggunakan persamaan normal, dibentuk matriks 3 2*2 6A A = . Kemudian bentuk matriks 14*7A b = . Sehingga persamaan normal* * A Ax A b =akan menjadi 3 2 142 6 7xy = . Sistem persamaan ini dengan mudah dapat diselesaikan dan diperoleh 512xy = Sedangkan elemen dari Range(A) yang memiliki jarak terpendek dengan vektor b adalah: 112 1 1591 11 221 24 = . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 55BAB VIII PROYEKTOR Pada bab ini akan dibahas mengenai sifat-sifat suatu matriks proyektor. Berikut merupakan definisi dari matriks proyektor. Definisi 8.1 (Matriks Proyektor) Diketahui matriks persegi n nAC . Matriks A disebut matriks proyektor jika dan hanya jikaA A A = . Dengan kata lain A memiliki sifat idempoten. Secara umum definisi proyektor adalahs sebagai berikut. Definisi 8.2 (Proyektor) Diketahui V ruang vektor atas lapangan F dan: P V V merupakan transformasi linear. Transformasi linear P disebut proyektor jika dan hanya jika P P P =. Lemma 8.3 Diketahui matriks proyektor n nACdan( ) x Range A , maka berlakuAx x = . Bukti. Diambil sebarang( ) x Range A , makax Av =untuk suatu nv C . Dari sifat matriks proyektor diperoleh( ) ( ) Ax A Av A A v Av x = = = = . Lemma 8.4 Diketahui matriks proyektor n nACdan( ) x Range A , maka berlaku ( ) Ax x Null A . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 56Bukti. Dari Lemma 8.3 diperolehAx x =untuk setiap( ) x Range A . Dengan demikian diperoleh,0nAx x x x = = C . Karena0 0 A = , maka( ) Ax x Null A . Teorema 8.5 (Komplemen Proyektor) Diketahui matriks proyektor n nACdan n nnICmerupakan matriks identitas, maka matriks nI A juga merupakan matriks komplemen. Lebih lanjut, matriks nI A disebut komplemen proyektor dari A. Bukti. ( ) ( ) ( ) ( )2222.n n n nnnI A I A I I A AI A AI A = += += Lemma 8.6 Diketahui matriks proyektor n nACdan n nnICmerupakan matriks identitas, maka ( ) ( )nRange I A Null A = . Bukti. Diambil sebarang( )nx Range I A , maka( )nI A v x =untuk suatu nv C . Karena ( )n nI A v I v Av v Av = = , maka( ) ( ) 0 Ax A v Av Av A A v Av Av = = = = . Dengan demikian( ) x Null A dan diperoleh( ) ( )nRange I A Null A . Diambil sebarang( ) x Null A , maka berlaku0 Ax = . Diperhatikan bahwa ( ) 0n nI A x I x Ax x x = = = . Dengan demikian( )nx Range I A dan diperoleh ( ) ( )nNull A Range I A . Jadi berlaku( ) ( )nRange I A Null A = . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 57Lemma 8.7 Diketahui matriks proyektor n nACdan n nnICmerupakan matriks identitas, maka ( ) ( )nRange A Null I A = . Bukti. Dari Lemma 8.6 dan matriks A disajikan dalam bentuk( )n nA I I A = . Teorema 8.8 Diketahui V ruang vektor atas lapangan F dan: P V V merupakan proyektor, maka berlaku( ) ( ) Range P Null P V = . Bukti. Untuk membuktikan( ) ( ) Range P Null P V =maka harus dipenuhi dua syarat berikut: 1.( ) ( ) { }0 Range P Null P =2.Untuk setiapv V , terdapat( ) x Range P dan( ) y Null P sehinggav x y = + . Pertama, akan dibuktikan( ) ( ) { }0 Range P Null P = . Dimbil sebarang ( ) ( ) x Range P Null P . Karena( ) x Range P , maka berlakuPx x = . Karena ( ) x Null P , maka berlaku0 Px = . Dengan demikian diperoleh0 x Px = = . Jadi, terbukti bahwa( ) ( ) { }0 Range P Null P = . Selanjutnya, diambil sebarangv V . Diperhatikan bahwa dapat dipilih ( ) x Pv Range P = dan( ) y v Pv Null P = . Sehingga berlaku ( ) v Pv v Pv x y = + = + . Jadi, karena syarat 1 dan 2 dipenuhi, maka terbukti bahwa ( ) ( ) Range P Null P V = . St rukt ur Al j abar Dekomposisi Mat riks Wij na 2007 2009 ht t p: / / wij na. web. ugm. ac. id 58Selanjutnya, diperhatikan matriks persegi 1 1 11 1 111 1 1n nn =

C. ..

, yaitu matriks persegi berukurann n dengan setiap entrinya bernilai 1. Diperhatikan bahwa 1 1 1n n nn = , dan dengan demikian matriks 11nnmerupakan matriks proyektor. Karena ( ) ( )2 21 1 1 1 11 1 1 1 1 1n n n n n nnn n n n n = = = . Contoh 8.9 Untuk3 n = , matriks 31 3 1 3 1 311 1 3 1 3 1 331 3 1 3 1 3E = = merupakan matriks proyektor. Dari Teorema 8.5, diperoleh matriks 32 3 1 3 1 31 3 2 3 1 31 3 1 3 2 3I E = juga merupakan matriks proyektor. Khusus untuk komplemen dari matriks proyektor 11nndiberi perhatian khusus. Definisi 8.10 (Matriks Centering) Matriks persegi n nnCC ,dengan 11n n nC In = disebut matriks centering berukuran n.