Diansusanti09's Blog

Just another WordPress.com weblog

APROKSIMASI TERBAIK ; KUADRAT TERKECIL Desember 29, 2010

Filed under: Uncategorized — diansusanti09 @ 9:32 am

Tujuan kali ini adalah kita akan menunjukkan bagaimana proyeksi ortogonal dapat digunakan untuk menyelesaikan soal-soal tertentu mengenai aproksimasi. Hasil-hasil yang diperoleh pada subbab ini dapat diterapkan pada ragam aplikasi yang sangat luas, baik dalam matematika sains.

Proyeksi ortogonal dipandang sebagai aproksimasi

Jika  p adalah sebuah titik di dalam ruang berdimensi 3 biasa dan W adalah sebuah bidang yang jaraknya terdekat dengan P dapat diperoleh dengan memproyeksikan  P secara tegak lurus terhadap W.

Sehingga,jika

dengan kata lain, di antara semua vektor w pada W , vektor w = projwu meminimalkan jarak ll u – w ll.

Ada cara lain untuk memahami gagasan ini. Pandanglah u sebagai sebuah vector tetap yang hendak kita aproksimasikan dengan menggunakan sebuah sektor pada W.setiap aproksimasi w semacam ini akan menghasilkan sebuah “vektor kesalahan” (error vector “)

uw

yang tidak dapat dijadikan sama dengan 0, terkecuali jika u terletak pada W.akan tetapi, dengan memilih

w = projw u

kita dapat menjadikan panjang vektor kesalahan

sekecil mungkin. Sehingga, kita dapat mendeskripsikan projw u sebagai “aproksimasi terbaik” bagi u relatif  terhadap vektor – vektor pada W. Teorema berikut ini akan membakuka gagasan intuitif di atas.

Teorema 6.4.1 Teorema Aproksimasi Terbaik

Jika W adalah sebuah subruang berdimensi terhingga dari suatu ruang hasil kali dalam V, dan jika u adalah sebuah vektor pada V, maka projw u adalah aproksimasi terbaik bagi u pada W, dalam pengertian bahwa

Untuk setiap vektor w pada W yang bukan projw u.

Bukti :

Untuk setiap vektor w pada W kita dapat menuliskan

u – w = (u – projw u) +  ( projw uw)                            (1)

namun projw uw, karena merupakan selisih dari dua buah vektor pada W, terletak pada W; dan u – projw u orthogonal terhadap W, sehingga kedua suku pada sisi kanan (1) saling orthogonal. Dengan demikian, melalui teorema pytagoras (6.2.4),

Jika w projw u, maka suku kedua dari penjumlahan di atas akan bernilai positif, sehingga

Atau secara ekuivalen,

Solusi Kuadrat Terkecil dari Sistem Linear

Masalah kuadrat terkecil.

Jika diberikan sebuah sistem linear Ax = b yang terdiri dari m persamaan dengan n nilai  merujuk pada hasilkali dalam Euclidean pada Rm. vektor semacam ini di sebut sebagai solusi kuadrat terkecil ( least square solution) dari Ax = b.

Catatan :

Untuk memahami asal mula istilah kuadrat terkecil, umpamakanlah bahwa e =Ax – b, yang dapat di pandang sebagai vektor kesalahan yang dihasilkan oleh aproksimasi terhadap x. jika e = (e1,e2,. . .,em) maka sebuah solusi kuadrat terkecil akan meminimalkan   dan oleh karenanya juga meminimalkan  sehingga dari sinilah istilah kuadrat terkecil muncul.

Untuk menyelesaikanpermasalahan kuadrat terkecil, misalkan W adalah ruang kolom dari . untuk setiap matriks x, n x 1, hasil kali Ax adalah seebuah kombinasi linear dari vektor – vektor kolom dari A. sehingga, dengan bervariasinya nilai x di dalam Rn, vektor Ax juga akan bervariasi  pada berbagai kombinasi linear yang mungkin dari vetor – vektor kolom dari A; jelasnya, Ax bervariasi di seluruh ruang kolom  W. secara geometrik , menyelesaikan persoalan kuadart terkecil berarti menentukan sebuah vektor x pada Rn, sedemikian rupa sehingga Ax merupakan vektor terdekat ke b di  dalam W.

Berdasarkan Teorema Aproksimasi Terbaik (6.4.1) bahwa vektor terdekat dari b di dalam W adalah proyeksi orthogonal b pada W. sehingga, agar sebuah vektor x dapat menjadi solusi kuadrat terkecil dai Ax = b, vektor ini harus memenuhi

Ax = projw b (2)

Kita dapat saja mencoba untuk menemukan solusi kuadrat terkecil dari Ax= b dengan cara terlebih dahulu menghitung vektor projw b dan kemudian menyelesaikan (2); namun demikian, ada satu pendekatan yang lebih baik : Dari Teorema proyeksi (6.3.4) yang menyatakan bahwa  jika W  adalah subruang berdimensi terhingga dari suatu hasil kali dalam V, maka setiap vektor u di dalam V dapat dinyatakan dengan tepat satu cara sebagai

u = w1 + w2

dimana w1 terletak pada W dan w2 terletak pada .

kita dapat menyatakan rumus diatas sebagai

u = projw u + projw u

karena w2 = u – w1, kita memperoleh

u = projw u + ( u – projw u )                                  (5)

sehingga kita mengetahui bahwa

b – Ax = b – projw b

orthogonal terhadap W. namun W adalah ruang kolom dari A, sehingga dari Teorema 6.2.6, b – Ax terletak pada ruang nul dari matriks AT. oleh karena itu, sebuah solusi kuadrat terecil dari Ax = b harus memenuhi

AT( b – Ax ) = 0

Atau secara ekuivalen,

ATA x = ATb (3)

Sistem persamaan ini disebut sebagai sistem normal yang di asosiasikan dengan A x = b, dan tiap – tiap persamaan di dalam sistem ini disebut persamaan normal yang diasosiasikan dengan Ax = b. sehingga, permaalahan penetuan solusi kuadrat terkecil dari Ax = b dapat disederhanakan menjadi permasalahan penentuan solusi eksak dari sistem normal yang terkait,

Perhatikan fakta – fakta berikut ini mengenai sistem normal :

  • Sistem normal melibatkan n persamaan dengan n factor yang tidak diketahui.
  • Sistem normal bersifat konsisten, karena dipenuhi oleh sebuah solusi kuadrat terkecil dari Ax = b.
  • Sistem normal dapat memiliki jumlah solusi yang taktethingga banyaknya, yang dalam kasus semacam ini semua solusi tersebut adalah solusi kuadrat terkecil dari Ax = b.

Dari fakta – fakta ini dan Rumus (2) kita dapat menurunkan teorema berikut ini.

Teorema 6.4.2

Untuk system linear

sebarang Ax = b, sistem normal terkait

ATAx = ATb

Bersifat konsisten, dan semua solusi dari sistem normal adalah solusi kuadrat terkecil dari Ax = b. selanjutnya, jika W adalah ruang kolom dari A, dan x adalah solusikuadrat terkecil sebarang dari Ax =b,maka proyeksi orthogonal b pada W adalah

Projw b = Ax

Contoh soal :

Tentukan sistem norma yang terkait dengan system linear berikut ini

Penyelesaian.

Untuk sistem linear sembarang Ax = b, system normal yang terkait

ATAx = ATb

Perhitungannya sebagai berikut : Ax = b


Sehingga

Dan

Sistem normal  ATA x = ATb dalam kasus ini adalah

Keunikan Solusi Kuadrat Terkecil

sebelum kita menelaah beberapa contoh numerik, kita akan menetapkan syarat-syarat yang menjamin suatu sistem linier memiliki sebuah solusi kuadrat terkecil yang unik .kita akan membutuhkan teorema berikut ini.

Teorema 6.4.3

Jika A adalah sebuah matriks m x n, maka pernyataan-pernyataan berikut ini

adalah ekuivalen

(a)   A memiliki vektor-vektor kolom yang bebas linier .

(b) ATA dapat dibalik

Bukti. kita akan membuktikan bahwa (a)   (b) dan menyerahkan kepada anda pembuktian (b)  (a)sebagai latihan .

(a)  (b) . Asumsikan bahwa A memiliki vektor-vektor klom yang bebas linier.

Matriks ATA memiliki n x n, sehingga kita dapat membuktikan bahwa matriks ini dibalik dengan menunjukkan bahwa sistem linear ATAx = 0 hanya memiliki solusi trivial. Akan tetapi ,jika x adalah sebuah solusi dari sistem ini, maka Ax terletak pada ruang nul dari AT dan juga ruang kolom dari A. berdasarkan teorema 6.2.6 ruang-ruang ini adalah komplemen-komplemen ortogonal sehingga bagian (b) Teorema 6.2.5.mengimplikasikan bahwa Ax = 0. Namun A memiliki vector-vektor kolom yang bebas linier , sehingga x = 0 berdasarkan teorema 5.6.8 .

Teorema berikutnya adalah konsekuensi langsung dari Teorema 6.4.2 dan Teorema 6.4.3. kita akan mengabaikan detil – detil uraiannya.

Teorema 6.4.4

Jika A adalah sebuah matriks m x n yang memiliki vector – vector kolom yang bebas linear, maka untuk setiap matriks b, m x 1, system liear Ax = b memiliki sebuah solusi kuadrat terkecil yang unik. Solusi ini diberikan oleh

X = ( ATA)-1ATb (4)

Selanjutnya, jika W adalahruang kolom dari A, maka proyeksi orthogonal b pada W adalah

Projwb = Ax = ( ATA)-1ATb (5)

Catatan. Pada Rumus (4) dan (5) dapat diterapkan dalam berbagai aplikasi teoretis, namun keduannya tidak efisien dan apabila diterapkan untuk perhitungan numeric. Solusi kuadrat terkecil dari Ax = b paling baik dihitung dengan menggunakan eliminasi Gauss atau eliminasi Gauss-Jordan untuk menyelesaikan persamaan – persamaan normalnya, dan proyeksi orthogonal b pada ruang kolom dai A paling baik didapatkan dengan cara menghitung Ax, dimana x adalah solusi kuadrat terkecil dari Ax = b.

Contoh soal 1 Solusi Kuadrat Terkecil

Tentukan solusi kuadrat terkecil dari system linear Ax = b , dan tentukan proyeksi orthogonal b pada ruang kolom matriks A.

Penyelesaian.

Perhatikan bahwa A memiliki vektor – vektor kolom yang bebas linear, sehingga kita dapat mengetahui sejak awal bahwa terdapat sebuah solusi kuadrat terkecil yang unik bagi sistem ini. Kita memperoleh

Sehingga sistem normal ATAx = ATb dalam kasus ini adalah

Dengan menyelesaikan system ini kita akan memperoleh solusi kuadrat terkecil

Dari (5), proyeksi orthogonal b pada ruang kolom dari A  adalah

Contoh soal 2 Proyeksi Ortogonal pada sebuah Subruang

Tentukan proyeksi orthogonal u = (2,1,3)

pada subruang dari R3 yang direntang oleh vektor – vektor v1 = (1,1,0)

dan v2 = (1,2,1).

Penyelesaian.

Kita dapt menyelesaikan soal ini dengan terlebih dahulu menggunakan poses Gram Schmidt untuk mengkonveksikan  menjadi sebuah basis ortonormal.

Subruang  W dari R3 yang direntang oleh  adalah ruang kolom dari matriks

Dengan demikian , jika v dinyatakan sebagai sebuah vector kolom, kita dapat menentukan proyeksi orthogonal u pada W dengan cara menentukan sebuah solusi kuadrat terkecil dari system Ax = u dan kemudian menghitung  projw u = Ax dari solusi kuadrat terkecil yang telah didapatkan. Perhitungannya adalah sebagai berikut : system Ax = u adalah

Sehingga

System normal ATAx = ATu dalam kasus ini adalah

Dengan menyelesaikan sistem ini akan menghasilkan solusi kuadrat terkecil dari Ax = u

Sehingga

atau  dalam notasi horizontalnya, 

Kita telah membahas  beberapa operator proyeksi orthogonal dasar pada R2 dan R3. Konsep sebuah operator proyeksi orthogonal dapat diperluas hingga mencakup ruang Euclidean yang berdimensi lebih tinggi, sebagaimana yang diperlihatkan berikut ini.

Definisi

Jika W adlah sebuah sub ruang dari Rm, maka transformasi P: RmW yang memetakan setiap vector x pada Rm menjadi proyeksi ortogonalnya projw x padaW disebut sebagai proyeksi ortogonalnya Rm pada W.

Dari rumus (5) kita memperoleh matriks standar untuk proyeksi ortogonalnya Rm pada W adalah

(ATA)-1AT (6)

Dimana A dibentuk dengan menggunakan basis sembarang untuk W sebagai vector- vector kolomnya.

Contoh soal Membuktikan rumus [P]= A(ATA)-1AT

Tentukan matriks standar untuk proyeksi orthogonal P : R3 R3 pada bidang xz.

Sebagaimana telah dibuktikan pada subbab sebelumnya kita telah menunjukkan bahwa matriks standar untuk proyeksi orthogonal R3 pada bidang xz adalah

Untuk mengetahui bahwa matriks ini konsisten dengan rumus [P]= A (ATA)-1AT, ambillah vector – vector satuan di sepanjang sunbu x dan sumbu z positif sebagai sebuah basis untuk bidang xz, sehingga

Kami menyerahkan kepada Anda untuk membuktikan bahwa ATA adalah matriks 2 x 2; sehingga rumus [P] =A(ATA)-1AT dapat disederhanakan menjadi

Yang konsisten dengan (7).                                                              ∎


RANGKUMAN

Teorema 6.4.3 memungkinkan kita untuk mencantumkan hasil tambahan ke dalam Teorema 6.2.7.

Teorema 6.4.5

# Pernyataan – pernyataan yang ekuivalen #

Jika A adalah sebuah matriks n x n, dan jika TA Rn Rn adalah perkalian dengan A, maka pernyataan – penyataan berikutini adalah ekuivalen.

(a)   A dapat dibalik.

(b)  A x = 0 hanya memiliki solusi trivial.

(c)   Bentuk eselon baris tereduksi dari A adlah In.

(d)  A dapat dinyatakan sebagai hasil kali dri matriks – matriks elementer.

(e)  A x = b konsisten untuk setiap matriks b, n x 1.

(f)   A x = b memiliki tepat satu solusi  untuk setiap matriks b, n x 1.

(g)   Det (A)  0.

(h)  Range dari TA adalah Rn.

(i)    TA adalah satu ke satu.

(j)    Vektor – vektor kolom dari A bebas linear.

(k) Vektor – vektor baris dari A bebas linear.

(l)    Vektor – vektor kolom dari A merntang Rn.

(m)                       Vektor – vektor baris dari A merntang Rn.

(n) Vektor – vektor kolom dari A membentuk basis untuk ruang Rn .

(o)  Vektor – vektor baris dari A membentuk basis untuk ruang Rn .

(p)  A memiliki rank n.

(q)  A memiliki nulitas 0.

(r)   Komplemen orthogonal ruang nul dari A adalah Rn.

(s)   Komplemen orthogonal ruang basis dari A adalah .

(t)   ATA dapat dibalik.

Keterangan :

Definisi rank dan nulitas

Dimensi umum dari ruang basis dan ruang kolom dari suatu matriks A disebut rank dari A dan dinyatakan sebagai rank (A); dimensi ruang nul dari A disebut sebagai nulitas dari A dan dinyatakan sebagai nulitas (A).

Teorema – teorema diatas akan menghubungkan semua topik utama yang telah kita pelajari hingga saat ini.

Sekian persembahan dari saya, TERIMA KASIH karena anda telah membaca blog ini. ^_^

About these ads
 

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Logout / Ubah )

Twitter picture

You are commenting using your Twitter account. Logout / Ubah )

Facebook photo

You are commenting using your Facebook account. Logout / Ubah )

Google+ photo

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

 
Ikuti

Get every new post delivered to your Inbox.