TEOREMA KETERBATASAN UNTUK METODE RELAKSASI

TEOREMA KETERBATASAN UNTUK METODE RELAKSASI

TESIS

Oleh

TOGI PARSAORAN SOALOON PASARIBU 067021031/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008

Togi Parsaoran Soaloon Pasaribu : Teorema Keterbatasan Untuk Metode Relaksasi, 2008 USU e-Repository © 2008

TEOREMA KETERBATASAN UNTUK METODE RELAKSASI

TESIS

Untuk Memperoleh Gelar Magister Sains Dalam Program Studi Magister Matematika Pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh

TOGI PARSAORAN SOALOON PASARIBU 067021031/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008


Judul Tesis Nama Mahasiswa Nomor Pokok Program Studi

: TEOREMA KETERBATASAN UNTUK METODE RELAKSASI : Togi Parsaoran Soaloon Pasaribu : 067021031 : Matematika

Menyetujui, Komisi Pembimbing

(Dr. Saib Suwilo, M.Sc) Ketua

( Prof. Dr. Herman Mawengkang) Anggota

Ketua Program Studi

Direktur

(Prof. Dr. Herman Mawengkang)

(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)

Tanggal lulus: 6 Juni 2008


Telah diuji pada Tanggal 6 Juni 2008

PANITIA PENGUJI TESIS Ketua

:

Dr. Saib Suwilo, M.Sc

Anggota

:

Prof. Dr. Herman Mawengkang Drs. Opim Salim S, MIkom, PhD Drs. Marihat Situmorang, M.Kom


ABSTRAK Teorema Klasik Block dan Levin menyatakan bahwa varian tertentu dari metode relaksasi untuk penyelesaian sistem pertidaksamaan-pertidaksamaan linier menghasilkan barisan terbatas dari penyelesaian-penyelesaian antara sekalipun bekerja atas data input yang tidak konsisten. Dengan menggunakan pendekatan baru, dibuktikan versi yang lebih umum dari teorema ini dan menjawab soal terbuka penentuan batas yang lama sebagai fungsi dari data input. Kata kunci: Metode relaksasi, Keterbatasan perceptron, Condition number, Teorema klasik Block dan Levin, Pertidaksamaan linier.

i Togi Parsaoran Soaloon Pasaribu : Teorema Keterbatasan Untuk Metode Relaksasi, 2008 USU e-Repository © 2008

ABSTRACT A classical theorem Block and Levin says that certain variants of the relaxation method for solving of systems of linear inequalities produce bounded sequences of intermediate solutions even when running on inconsistent input data. Using a new approach, be proved a more general version of this result and answer an old of quantifying the bounds as a function of the input data. Keyword: Relaxation method, Perceptron boundedness, Condition number, Block and Levin classical Theorem, Linear inequalities.

ii Togi Parsaoran Soaloon Pasaribu : Teorema Keterbatasan Untuk Metode Relaksasi, 2008 USU e-Repository © 2008

KATA PENGANTAR Dengan rendah hati, penulis mengucapkan puji syukur kehadirat Tuhan Yang Maha Esa atas anugerah dan berkat-Nya yang telah diberikan, sehingga penulis dapat menyelesaikan tesis dengan judul : Teorema Keterbatasan Untuk Metode Relaksasi. Tesis ini merupakan salah satu persyaratan penyelesaian studi pada Program Studi Magister Matematika SPs Universitas Sumatera Utara. Pada kesempatan ini penulis menyamaikan terima kasih sebesar-besarnya kepada: Prof. Dr. dr. Chairuddin P. Lubis, DTM&H, Sp. AK selaku Rektor Universitas Sumatera Utara. Prof.

Dr.

Ir.

T. Chairun Nisa selaku Direktur Sekolah Pascasar-

jana Universitas Sumatera Utara yang telah memberi kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara Medan. Prof. Dr. Herman Mawengkang selaku Ketua Program Studi Magister Matematika SPs Universitas Sumatera Utara, dan juga sebagai Pembimbing II, yang telah banyak membantu dalam penulisan Tesis ini. Dr. Saib Suwilo, MSc selaku Sekretaris Program Studi Magister Matematika SPs Universitas Sumatera Utara, dan juga selaku Pembimbing I yang selalu memberi motivasi kepada penulis. Kepala Bappeda Pemerintah Propinsi Sumatera Utara yang telah memberikan beasiswa kepada penulis dan Kepala Dinas Pendidikan Kota Medan yang telah memberikan izin untuk mengikuti Program Studi Magister iii Togi Parsaoran Soaloon Pasaribu : Teorema Keterbatasan Untuk Metode Relaksasi, 2008 USU e-Repository © 2008

Matematika di Sekolah Pascasarjana Universitas Sumtera Utara Medan. Drs. Ramses Aritonang, selaku Kepala Sekolah SMA Negeri 20 Medan yang telah merekomendasikan dan memberikan izin kepada penulis dalam mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara Medan. Seluruh Staf Pengajar pada Program Studi Magister Matematika SPs Universitas Sumatera Utara, yang telah memberikan ilmunya selama masa perkuliahan. Saudari Misiani, A.Md selaku Staf Administrasi Program Studi Magister Matematika SPs Universitas Sumatera Utara yang telah memberi pelayanan yang baik kepada penulis. Semua rekan-rekan Mahasiswa Program Studi Magister Matematika SPs Universitas Sumatera Utara yang telah memberi bantuan moril dan materil serta dorongan kepada penulis dalam penulisan Tesis ini. Keluarga Besar Pasaribu, Mama tercinta D br. Pohan, Kakak dan Adik-adikku di Helvetia yang selalu mendorong dan mendoakan penulis serta membantu penulis dalam hal materi. Terakhir penulis mengucapkan terima kasih sebesar-besarnya kepada Keluarga, Istri tercinta Ernawaty Oktavia Sihombing, A.Md dan anak-anakku yang tersayang Pascal Martinus Tona Pasaribu dan Abel Christophel Cantona Pasaribu serta Op. Martin (P. Br. Rajagukguk) yang tidak kenal lelah menjaga buah hati kami.

iv Togi Parsaoran Soaloon Pasaribu : Teorema Keterbatasan Untuk Metode Relaksasi, 2008 USU e-Repository © 2008

Akhir kata penulis mengucapkan terima kasih kepada Bapak / Ibu / Saudara / i dan rekan sekalian yang telah membantu penulis baik secara langsung maupun tidak langsung semoga Tuhan Yang Maha Esa memberkati kita semua.

Medan, 23 Juni 2008 Penulis,

Togi Parsaoran S. Pasaribu

v Togi Parsaoran Soaloon Pasaribu : Teorema Keterbatasan Untuk Metode Relaksasi, 2008 USU e-Repository © 2008

RIWAYAT HIDUP Togi Parsaoran Soaloon Pasaribu dilahirkan di Medan pada tanggal 22 April 1970 dan merupakan anak kedua dari 8 bersaudara dari ayah Dahlan Pandapotan Pasaribu dan ibu Darlia br Pohan. Menamatkan Sekolah Dasar (SD) Negeri 4 (060921) di Medan pada tahun 1982, Sekolah Menengah Pertama (SMP) Karya Bhakti di Medan pada tahun 1985 dan Sekolah Menengah Atas (SMA) Negeri 3 Jurusan Ilmu-Ilmu Fisika (A1) pada tahun 1988 di Medan. Pada tahun 1988 kuliah di FMIPA USU Prodi Matematika D-III dan memperoleh gelar A.Md pada tahun 1991. Tahun 1992 s/d 1999 bekerja sebagai guru di SMA Negeri 1 Kuta Binjai kab. Aceh Timur dan pada tahun 1995 kuliah di UT (Universitas terbuka) dan memperoleh gelar S.Pd pada tahun 1997 dengan predikat Lulusan terbaik. Pada tahun 2000 pindah tugas ke Medan dan mengajar di SMA Negeri 5 Medan hingga pertengahan tahun 2004 kemudian pindah tugas dan mengajar di SMA Negeri 20 Medan sampai sekarang.

vi Togi Parsaoran Soaloon Pasaribu : Teorema Keterbatasan Untuk Metode Relaksasi, 2008 USU e-Repository © 2008

DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .

iii

RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . .

ix

BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .

1

1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . .

3

1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .

5

1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . .

5

1.5 Metodologi Penelitian . . . . . . . . . . . . . . . . . . .

5

BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . .

6

BAB 3 LANDASAN TEORI . . . . . . . . . . . . . . . . . . . . .

8

3.1 Sistem Persamaan Linear . . . . . . . . . . . . . . . . .

8

3.1.1 Pengertian . . . . . . . . . . . . . . . . . . . . .

8

3.1.2 Sistem persamaan linear homogen . . . . . . . . . .

9

3.2 Matriks . . . . . . . . . . . . . . . . . . . . . . . . . .

10

3.2.1 Pengertian . . . . . . . . . . . . . . . . . . . . .

10

3.2.2 Transpose

. . . . . . . . . . . . . . . . . . . . .

11

. . . . . . . . . . . . . . . . . . . . . . .

11

3.2.3 Invers

vii Togi Parsaoran Soaloon Pasaribu : Teorema Keterbatasan Untuk Metode Relaksasi, 2008 USU e-Repository © 2008

3.3 Ruang Vektor . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Vektor yang bebas linier dan tak bebas linier

12

. . . .

13

3.3.2 Kombinasi Linier . . . . . . . . . . . . . . . . . .

14

3.3.3 Dimensi dan basis

. . . . . . . . . . . . . . . . .

14

3.4 Himpunan Konveks . . . . . . . . . . . . . . . . . . . .

14

3.5 Sekam konveks (Convex Hull) . . . . . . . . . . . . . . .

22

3.6 Teorema pada hiperplane-hiperplane terpisah (separating) .

27

3.7 Hasil dasar dalam program linear . . . . . . . . . . . . .

34

3.8 Inner Product (Perkalian Dalam) dan Ortogonalitas . . . .

37

3.9 Kronecker Product dan Stack of Matrices . . . . . . . . .

39

3.10 Transformasi linier dan grup matriks

. . . . . . . . . . .

40

3.11 Gram-Schmidt dan dekomposisi QR . . . . . . . . . . . .

46

BAB 4 TEOREMA KETERBATASAN UNTUK SUATU METODE RELAKSASI . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

4.1 Gagasan Geometrik Utama . . . . . . . . . . . . . . . .

48

4.2 Jumlah Syarat untuk Menentukan Batas . . . . . . . . . .

54

4.3 Memilih Potongan Konveks untuk Konstruksi Ukuran . . .

59

4.4 Bola Satuan Ukuran dan Sifat-sifatnya . . . . . . . . . . .

63

4.5 Keterbatasan Relaksasi untuk Sistem Homogen

. . . . . .

68

4.6 Perluasan pada Sistem Nonhomogen . . . . . . . . . . . .

71

BAB 5 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . .

75

5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . .

75

DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .

76

viii Togi Parsaoran Soaloon Pasaribu : Teorema Keterbatasan Untuk Metode Relaksasi, 2008 USU e-Repository © 2008

DAFTAR GAMBAR

Nomor

Judul

Halaman

3.1

Bukan himpunan konveks dan Himpunan konveks . . . . . .

17

3.2

Polihedron Kompleks . . . . . . . . . . . . . . . . . . . .

23

3.3

Himpunan Konveks Tak Terbatas . . . . . . . . . . . . . .

26

3.4

Hiperplane Penyangga . . . . . . . . . . . . . . . . . . . .

29

3.5

Hiperplane penyangga pada suatu titik batas w

. . . . . . .

33

4.1

Interpretasi Geometri dari C{a}⊥ (r)

. . . . . . . . . . . . .

49

4.2

Pergerakan oleh δ sepanjang ai dalam bola satuan meter . . .

50

4.3

Potongan Potongan dalam R3 . . . . . . . . . . . . . . . .

52

4.4

Interferensi Potongan-Potongan dalam Daerah Berbentuk Intan

53

ix Togi Parsaoran Soaloon Pasaribu : Teorema Keterbatasan Untuk Metode Relaksasi, 2008 USU e-Repository © 2008

BAB 1 PENDAHULUAN

1.1 Latar Belakang Metode relaksasi dari Agmon (1954), Motzkin dan Schonberg (1954), untuk penentuan suatu titik dalam himpunan konveks (cembung) terbuka K dari ruang inner product riil (V, h·, ·i) adalah algoritma konseptual yang didasarkan pada kaidah pemisahan: diberikan xi ∈ V , kaidah memberikan ai ∈ V, bi ∈ R sedemikian sehingga hai , xi > bi

∀x ∈ C,

hai , xii ≤ bi ,

(1.1) (1.2)

Atau ketentuan bahwa xi ∈ C. Diberikan titik awal x0 , metode bekerja dengan memutakhirkan xi menjadi xi+1 = xi +ηai pada kasus pertama dan berhenti bila ketentuan keanggotaan ditemukan. Kadang-kadang K diasumsikan tertutup, di mana dalam kasus ini > diganti dengan ≤ dalam (1.1) dan ≤ diganti dengan < dalam (1.2), tetapi mengasumsikan bahwa K terbuka lebih mudah untuk tujuan penelitian ini. Dalam situasi di mana K digambarkan secara implisit sebagai irisan himpunan paroh-bidang ( halfplanes) K=

\

{x ∈ V : ha, xi > b}

(1.3)

(a,b)∈A

Ide relaksasi biasanya dapat diubah menjadi algoritma praktis dengan membangun kaidah bahwa mensampling pertidaksamaan-pertidaksamaan linier dalam 1 Togi Parsaoran Soaloon Pasaribu : Teorema Keterbatasan Untuk Metode Relaksasi, 2008 USU e-Repository © 2008

2 A. Khususnya, polihedron yang memegang peranan dalam linear programming biasanya dinyatakan dengan pertidaksamaan linier. Dalam perencanaan terapi radiasi sejumlah besar pertidaksamaan linier terjadi secara alami dalam rumusan matematika untuk masalah penyaluran dosis maksimum sinar-X di dalam tumor yang harus memenuhi batasan menjaga keterpaparan jaringan sekitarnya tetap di bawah ambang batas (Censor dan Zenios, 1997). Situasinya serupa dalam pendekatan tertentu terhadap jaringan saraf yang didasarkan pada penentuan klasifikator linier yang akan mengklasifikasikan himpunan titik-titik pelatihan dengan tepat ( Rosenblatt, 1962). Banyak versi metode relaksasi yang berbeda diajukan, tergantung pada bagaimana ukuran tahap ηi dan titik-titik (ai, bi ) yang mendefinisikan bidang pemisah yang dipilih. Algoritma perceptron pada jaringan saraf ( Rosenblatt, 1962) didasarkan pada pemilihan ηi ≡ 1, algoritma proyeksi siklik (Bauschke dkk, 1997) memeriksa semua pertidaksamaan dalam A dengan cara siklik dan mengambil panjang tahap ηi = (bi − hai , xii)/ hai , aii. Yang juga terkait adalah metode Cimmino (1938) , metode proyeksi Bregman (1997) acak dan berbagai jenis algoritma subgradient ( Shor, 1964) seperti metode buntela (Hiriart dkk, 1991) Bila metode relaksasi diaplikasikan pada himpunan data layak berhingga A (himpunan yang menghasilkan K 6= ∅), maka xi menjadi suatu anggota K setelah sejumlah hingga iterasi untuk semua varian yang menarik. Hasil konvergensi yang biasa adalah hasil metode perceptron yang mencari titik layak dengan sejumlah iterasi yang sebanding dengan jumlah syarat Goffin (1980). Bila data input rasional, jumlah iterasi kasus-terburuk yang dibutuhkan hingga berakhir


3 eksponensial dalam ukuran input. Metode relaksasi bisa sangat meningkat dengan menetapkan kembali skala ruang utama pada masing-masing iterasi ( Shor, 1970). Gagasan ini menghasilkan perkembangan metode ellipsoid (Yudin dan Nemirovskii, 1976) yang menjadi algoritma pertama untuk linear programming yang terbukti berakhir pada waktu polinomial ( Khachiyan, 1979) Situasi khusus terjadi bila K = ∅ tetapi A 6= ∅ (dikatakan bahwa A adalah kasus masalah tak layak): dalam kasus ini algoritma tidak akan pernah berhenti, karena kaidah akan selalu menentukan pertidaksamaan yang dilanggar. Dalam tulisan ini akan diselidiki situasi ini untuk kasus di mana A merupakan himpunan berhingga. Walaupun masalah penentuan suatu titik dalam himpunan kosong adalah pekerjaan yang tidak mungkin, aplikasi metode relaksasi pada data input yang tidak layak memang menarik dalam konteks dimana ingin dipenuhi sebanyak mungkin pertidaksamaan tetapi dimana untuk memenuhi semua pertidaksamaan tersebut biasanya tidak mungkin, seperti kasus yang umum dalam perencanaan terapi radiasi, belajar komputer dan jaringan saraf. Dalam situasi ini biasanya ingin diperoleh informasi tentang distribusi ruang dari titik-titik xi yang dibangun oleh algoritma.

1.2 Perumusan Masalah Misalkan A ⊂ Rn \{0} himpunan berhingga dari vektor vektor tak nol, x0 ⊂ Rn titik awal yang diberikan, (ηi )N0 ∈ R+ barisan bilangan-bilangan nonnegatip dan (ai )N0 ⊆ A barisan tak hingga dari vektor-vektor dari A. Andaikan bahwa barisan titik-titik yang didefinisikan secara iteratif oleh xi+1 = xi + ηi ai memenuhi syarat aTi xi ≤ 0


(1.4)

4 untuk semua i ∈ N0. Situasi ini terjadi bila metode relaksasi dengan panjang tahap ηi diaplikasikan pada sistem pertidaksamaan-pertidaksamaan linier homogen tak layak AT x > 0. Di sini, diidentifikasi himpunan A dengan matriks yang diperoleh dengan mengkoleksi elemen-elemennya sebagai vektor kolom dengan urutan tertentu. Nilson dan Beyer (1964) memperkirakan bahwa pada kasus di mana ηi ≡ 1 (yang bersesuaian dengan algoritma perceptron) barisan iterat - iterat (xi )N0 tetap terbatas dalam norm. Bukti perkiraan ini, yang dewasa ini dikenal sebagai Teorema Keterbatasan Perceptron, dikembangkan dalam serangkaian tulisan Effron (1964), Minsky dan Papert (1969) dan Block dan Levin (1970). Bukti mereka didasarkan pada gagasan rantai-F murni sebagai alat analitik dasar untuk memungkinkan induksi atas dimensi masalah. Dengan menggunakan teknik yang sama, dapat dengan mudah dipastikan bahwa hasil meluas pada kasus di mana ada konstanta L, U sedemikian sehingga 0 < L < ηi < U

∀i ∈ N0

(1.5)

Sejauh manakah keumuman asumsi-asumsi ini? Yang jelas, tanpa adanya batas atas pada ηi , (xi )N0 tidak harus tetap terbatas. Karenanya, batas atas memang perlu. Di lain pihak, persyaratan bahwa batas atas harus positif kelihatannya secara teknis kurang penting , dan mengakibatkan adanya kemungkinan untuk mengganti (1.5) dengan syarat yang tidak begitu ketat 0 ≤ ηi < U

∀i ∈ N0


(1.6)

5 1.3 Tujuan Penelitian Membahas teorema keterbatasan klasik Block dan Levin dan pembuktian versi yang lebih umum dengan suatu metode relaksasi

1.4 Kontribusi Penelitian Penelitian ini diharapkan memberikan sumbangan teoritis dalam bidang matematika secara umum khususnya dalam bidang metode relaksasi penentuan suatu titik dalam himpunan konveks terbuka.

1.5 Metodologi Penelitian Metodologi penelitian bersifat literature dengan langkah-langkah sebagai berikut :

1. Menjelaskan ide-ide geometri utama yang memandu pendekatan pada R2 dan R3 2. Membahas sistem homogen AT x > 0 3. Menentukan sejumlah syarat untuk batas atas pada teorema (1.6) 4. Memilih potongan konveks untuk kontruksi ukuran 5. Bola satuan ukuran dan sifat-sifatnya 6. Keterbatasan relaksasi untuk sistem homogen AT x > b. 7. Perluasan pada sistem Nonhomogen


BAB 2 TINJAUAN PUSTAKA

Metode relaksasi klasik dari Agmon (1954) dan Motzkin dan Schonberg (1954), sangat berkaitan erat dengan metode iterasi untuk sistem persamaan linear , yang sangat diminati di tahun 1950-an, sebagian karena setiap iterasi memerlukan perhitungan minimal, yaitu hanya beberapa pergandaan matriks vektor. Untuk menentukan suatu titik dalam Y := y : AT y ≤ c , pada setiap iterasi titik yang ada diproyeksikan pada suatu hyperplane yang didefinisikan oleh suatu batasan yang dilanggar (sebenarnya, satu ukuran langkah λ ∈ (0, 2] biasanya sudah termasuk, dimana λ = 1 ( masing-masing , 2) bersesuaian dengan proyeksi pada (masing - masing, pencerminan pada ) hyperplane ). Metode ini terkait erat dengan metode iterasi klasik Gauss-Seidel dan metode iterasi Jacobi untuk ”menyelesaikan” sistem persamaan- persamaan linear AT Av = c. (Di sini, pada setiap iterasi, satu komponen dari v diganti untuk memenuhi persamaan yang bersesuaian, dan lagi-lagi biasanya dengan parameter relaksasi untuk mempercepat pemusatan (konvergensi)) . Akan tetapi , hal ini tidak berjalan dengan baik pada percobaan perhitungan oleh Hoffman (1953) disebabkan konvergensinya yang sangat lambat. Penemuan metode ellipsoid (yang dapat dipandang sebagai bentuk ukuran variabel dari metode relaksasi) membutuhkan studi lebih lanjut (Goffin, 1980).

6 Togi Parsaoran Soaloon Pasaribu : Teorema Keterbatasan Untuk Metode Relaksasi, 2008 USU e-Repository © 2008

7 Yang jauh lebih berhasil adalah varian teknik over-relaksasi berturutan (SOR) yang diaplikasikan pada bentuk masalah komplementer linier atau pada masalah dual Lagrange yang ditambahkan. Tentu saja De Leone dan Mangasarian (1980) melaporkan hasil yang sangat membesarkan hati untuk metode ini yang diaplikasikan pada masalah program linear jarang acak berukuran mulai dari 25.000 × 100.000 hingga 125.000 × 500.000. Sekali lagi , setiap iterasi hanya membutuhkan beberapa pergandaan matriks-vektor dengan matriks koefisien jarang origin. Akan tetapi, dengan memilih parameter-parameter hukuman Lagrange yang ditambahkan menimbulkan beberapa permasalahan.


BAB 3 LANDASAN TEORI

3.1 Sistem Persamaan Linear

3.1.1 Pengertian Suatu himpunan berhingga dari persamaan-persamaan linear dalam peubahpeubah x1, x2 , · · · , xn dinamakan Sistem Persamaan Linear. Sebuah sistem sebarang yang terdiri dari m persamaan linear dengan n bilangan yang tidak diketahui dapat dinyatakan sebagai berikut : a11x1 + a12x2 + · · · + a1n xn = b1 a21x1 + a22x2 + · · · + a2n xn = b2 ······ am1 x1 + am2 x2 + · · · + amn xn = bm Dalam menentukan himpunan jawab (solusi) dari suatu SPL seperti yang sudah dikenal adalah menggunakan cara gabungan antara substitusi dan eliminasi. Namun hal ini hanya akan mudah untuk diterapkan pada SPL bilamana jumlah peubah dua atau tiga buah sedangkan bila jumlah peubah besar (n > 3) tentu akan mengalami kesulitan karena terlalu memakan waktu dan ketelitian. Bila diberikan suatu SPL maka akan ada dua kemungkinan terhadap keberadaan solusinya, yaitu SPL tidak mempunyai solusi disebut SPL tidak konsisten dan SPL mempunyai solusi disebut SPL konsisten. Bila suatu SPL konsisten maka solusi dari SPL dibedakan lagi menjadi dua yaitu ada satu solusi (solusi tunggal) 8 Togi Parsaoran Soaloon Pasaribu : Teorema Keterbatasan Untuk Metode Relaksasi, 2008 USU e-Repository © 2008

9 dan ada banyak solusi (solusi tak hingga). Untuk menentukan solusi dari SPL dilakukan dengan cara membentuk matriks yang diperluas / diperbesar (augmented matrix) dari SPL dan melakukan operasi baris elementer (OBE) pada matriks yang diperbesar tersebut. Dari bentuk umum SPL dengan n peubah dan m persamaan , dapat dituliskan dalam notasi matriks : AX = B, dengan : Matriks A berukuran m × n mempunyai baris sebanyak m buah dan kolom sebanyak n buah dan banyak unsur / elemen sebanyak m x n buah disebut matriks koefisien dari SPL, matriks X berukuran n × 1 dan matriks B berukuran m × 1. Perkalian matriks A dan X, yaitu AX dapat dilakukan karena banyak kolom matriks A sama dengan banyak baris matriks X. Bentuk matriks yang diperbesar dari SPL merupakan gabungan dari matriks koefisien A dan matriks B, yaitu :       a11 a12 · · · a1n   x1   b1      a  21 a22 · · · a2n   x2  =  b2  · · · · · · · · · · · ·  · · · · · ·      an1 an2 · · · ann xn bn

3.1.2 Sistem persamaan linear homogen Sebuah sistem persamaan linear dikatakan homogen jika pada persamaan di atas nilai bi = 0 untuk setiap i = 1, 2, · · · , m . Setiap sistem persamaan linear homogen adalah sistem yang konsisten, karena x1 = x2 = · · · = 0 selalu merupakan penyelesaian. Penyelesaian ini dinamakan penyelesaian trivial. Jika ada penyelesaian lain yang memenuhi persamaan homogen tersebut, maka penyelesaian tersebut dinamakan penyelesaian tak trivial.


10 3.2 Matriks

3.2.1 Pengertian Matriks adalah suatu susunan dari banjar (array) bilangan-bilangan dalam bentuk segi empat, dengan jumlah baris sebanyak m dan jumlah kolom sebanyak n dan dinotasikan sebagai A = A = (aij )mxn i = 1, · · · , m dan j = 1, · · · , n serta aij adalah elemen dari matriks A pada baris ke-i kolom ke-j

1. Matriks A dikatakan berukuran m × n (berdimensi m × n) 2. Matriks A dengan dimensi 1×n disebut sebagi vektor baris, sedangkan yang berdimensi m × 1 disebut sebagai vektor kolom 3. Jika jumlah baris sama dengan jumlah kolom, yaitu m = n, maka matriks A dikatakan sebagai matriks bujur sangkar dengan orde n. 4. Pada suatu matriks A jika m = n,maka elemen aii disebut sebagai elemen diagonal dari A, elemen-elemen lain merupakan elemen di luar diagonal dari A 5. Pada suatu matriks A dengan m = n, bila aii 6= 0 sedangkan elemen di luar diagonal dari A sama dengan nol, yaitu, aij = 0 untuk i 6= j, maka matriks A disebut sebagai matriks diagonal 6. Jika pada matriks diagonal di atas nilai aii = c untuk setiap i = 1, · · · , n maka matriks tersebut dikatakan sebagai matriks skalar. Dengan kata lain matriks skalar adalah matriks diagonal dengan seluruh diagonalnya bernilai sama.


11 7. Jika pada matriks diagonal di atas nilai aii = 1 untuk setiap i = 1, · · · , n maka matriks tersebut dikatakan sebagai matriks identitas (dinotasikan dengan In). 8. Jika pada matriks diagonal di atas nilai aii = 0 untuk setiap i = 1, · · · , n maka matriks tersebut dikatakan sebagai matriks Null (dinotasikan dengan On×n ). Secara umum untuk sebarang matriks Am×n , bila seluruh elemennya bernilai 0 maka matriks tersebut dinotasikan dengan Om×n

3.2.2 Transpose Transpose matriks A dinotasikan AT atau A didapatkan dengan cara menukar elemen baris ke i matriks A menjadi elemen kolom ke i. Bila matriks A berukuran m × n, maka A berukuran n × m dan elemen A yang ke (i, j) adalah aji ; dapat pula dinyatakan (A)ij = (A)ji .

3.2.3 Invers Matriks A berukuran m × m disebut matriks nonsingular bila det A tidak nol. Matriks mempunyai invers tunggal, dinotasikan A−1 , dan memenuhi sifat berikut, AA−1 = A−1 A = I Bila α skalar, sedang A dan B matriks nonsingular berukuran m × m, maka berlaku : (a) (αA)−1 = α−1 A−1 (b) (A)−1 = (A−1)


12 (c) (A−1 )−1 = A (d) |A−1 | = |A|−1 −1 −1 (e) Bila A = diag(a11, a22, · · · , amm ), maka A−1 = diag(a−1 11 , a22 , · · · , amm ).

(f) Bila A = A, maka A−1 = (A−1 ) (g) (AB)−1 = B −1 A−1

3.3 Ruang Vektor Misalkan V sebarang himpunan benda yang dua operasinya didefinisikan yaitu penjumlahan dan perkalian dengan skalar (bilangan riil). Penjumlahan tersebut dipahami untuk mengasosiasikan sebuah aturan dengan setiap pasang benda u dan v dalam V , yang mengandung elemen u + v, yang dinamakan jumlah u dan v, dengan perkalian skalar diartikan setiap benda u pada V yang mengandung elemen u, yang dinamakan perkalian skalar u oleh k. Jika semua aksioma berikut dipenuhi oleh semua benda u, v, w pada V dan oleh semua skalar k dan l, maka dinamakan V sebuah ruang vektor dan benda-benda pada V dinamakan vektor :

(1) Jika u dan v adalah benda-benda pada V dinamakan vektor (2) u + v = v + u (3) u + (v + w) = (u + v) + w (4) Ada vektor 0 di V sehingga 0 + u = u + 0 = u untuk semua u di V (5) Untuk setiap u di V , terdapat u sehingga u + (-u) = (-u) + u = 0


13 (6) Jika k adalah sebarang skalar dan u adalah sebarang vektor di V , maka k u berada di V . (7) k(u + v)= ku+ kv (8) (k + l)u= ku+ lu (9) k(lu) = l(ku) (10) 1u = u

3.3.1 Vektor yang bebas linier dan tak bebas linier Himpunan m buah vektor (u1, u2, · · · um ) disebut tak bebas linier (linearly dependent) bila terdapat skalar-skalar λ1 , λ2 , · · · , λm yang tidak semuanya nol sedemikian hingga (u1, u2 , · · · um ) , sebaliknya himpunan (u1 , u2, · · · um ) disebut bebas linier (linearly independent) jika λ1 u1 +λ2 u2 +· · ·+λm um = 0 hanya dipenuhi oleh λ1 = λ2 = · · · = λm = 0. Catatan :

1. Jika m = 1, maka : (a) Bila u = 0 (vektor nol), akan tak bebas linier, karena λu = 0 maka λ0 = 0 terpenuhi juga untuk λ 6= 0 (b) Bila λ 6= 0, akan bebas linier karena λu = 0 hanya dipenuhi oleh λ = 0 2. Jika dalam himpunan terdapat vektor 0, misalnya {u1 , u2, · · · , 0, · · · um ) maka himpunan itu tak bebas linier, λ1 u1 + λ2 u2 + · · · + λi 0 + · · · + λm um = 0 dipenuhi juga oleh λI 6= 0


14 3. Jika u dan v adalah 2 vektor yang berkelipatan, u = αv, maka mereka tak bebas linier. Sebab u = αv 7→ 1uαv = 0, artinya terdapat α 6= 0 pada λ1 v + λ2 u = 0

3.3.2 Kombinasi Linier Suatu vektor v dikatakan kombinasi linier dari vektor vektor (u1, u2, · · · um ) bila terdapat skalar-skalar λ1 , λ2 , λ3 · · · , λm sedemikian hingga v = λ1 u1 + λ2 u2 + · · · + λm um

3.3.3 Dimensi dan basis Jika V adalah sebarang ruang vektor dan S = {v1, v2, · · · , vr } merupakan himpunan berhingga dari vektor-vektor pada S, maka S disebut basis untuk V jika : (i) S bebas linier (ii) S merentang V Dimensi sebuah ruang vektor V yang berdimensi berhingga didefinisikan sebagai banyaknya vektor pada basis untuk V .

3.4 Himpunan Konveks Himpunan X adalah konveks, jika untuk setiap titik x1 , x2 dalam himpunan, maka segmen garis yang menghubungkan titik-titik ini adalah juga dalam himpunan.


15 Definisi ini mengakibatkan, bahwa jika x1, x2 ∈ X, maka setiap titik x = λx2 + (1 − λ)x1 , 0 ≤ λ ≤ 1 harus juga di dalam himpunan. Jadi jelas bahwa suatu himpunan konveks adalah bersambung, sebab lintasan poligon yang menghubungkan titik-titik adalah garis yang menghubungkan titik-titik. Jadi suatu himpunan konveks adalah suatu daerah. Dengan konvensi, dikatakan bahwa setiap himpunan yang memuat hanya satu titik adalah konveks. Ungkapan (1 − λ)x1 + λx2 , 0 ≤ λ ≤ 1, sering berkenaan dengan suatu kombinasi konveks dari x1 , x2 (untuk suatu λ). Suatu himpunan adalah konveks, jika setiap kombinasi konveks dari setiap dua titik dalam himpunan juga dalam himpunan. Secara intuisi, suatu himpunan konveks tidak dapat mempunyai suatu ”lobang” di dalamnya, jadi, himpunan tersebut adalah ”padat” dan tidak ”termasuki”, yaitu, batasnya selalu ”rata” atau ”benjol” dari himpunan. Ide intuisi ini, tentunya, semuanya secara cermat diungkapkan dalam definisi dari suatu himpunan konveks. Titik Ekstrem : Suatu titik x adalah titik ekstrem dari suatu himpunan konveks, jika dan hanya jika tidak ada titik x1 , x2(x1 6= x2 ) dalam himpunan sedemikian x = (1 − λ)x1 + λx2 , 0 < λ < 1 Perhatikan bahwa pertidaksamaan langsung dibebankan pada λ. Definisi menetapkan bahwa suatu titik ekstrem tidak dapat ”di antara” setiap dua titik lain dalam himpunan, yaitu, tak dapat terletak pada segmen garis yang meng-


16 hubungkan titik titik (0 < λ < 1). Jelasnya , suatu titik ekstrem adalah titik batas dari himpunan. Untuk membuktikan ini, dimisalkan bahwa x0 suatu titik dalam dari X. Maka ada suatu ∈> 0, sehingga setiap titik dalam tetangga ∈ dari x0 berada dalam himpunan. Misalkan x1 6= x0 adalah titik dalam tetangga ∈. Tinjau titik tersebut x2 = −x1 + 2x0,

|x2 − x0| = |x1 − x0|

maka x2 ada dalam tetangga ∈. Selanjutnya 1 x0 = (x1 + x2) 2 dan karenanya x0 bukan suatu titik ekstrem. Tidak semua titik-batas dari suatu himpunan konveks perlu titik-titik ekstrem. Beberapa titik batas dapat terletak di antara dua titik batas yang lain. Jika suatu himpunan konveks hanya memuat suatu titik tunggal, maka titik ini akan dipandang sebagai titik ekstrem. Contoh : (1) Suatu segitiga dan bagian dalamnya membentuk suatu himpunan konveks. Titik-titik sudut dari segitiga adalah satu-satunya titik-titik ekstremnya, karena mereka tidak terletak di antara dua titik lain dari himpunan. Titik-titik lain pada sisi segitiga bukan titik-titik ekstrem, sebab mereka terletak antara titik-titik sudut. (2) Himpunan X = {[x1, x2]|x21 + x22 ≤ 1} adalah konveks. Setiap titik pada keliling adalah titik ekstrem. (3) Himpunan pada gambar 3.1. tidak konveks, karena garis yang menghubungkan x1 dan x2 tidak terletak di dalam himpunan. Himpunan tersebut ialah


17 ”re-entrant”. (4) Keempat himpunan pada gambar 3.2. adalah konveks dan titik-titik ekstrem adalah titik-titik sudutnya. Titik x1 bukan suatu titik ekstrim, sebab itu dapat dinyatakan sebagai suatu kombinasi konveks dari x2 , x3 dengan 0 < λ < 1.

Gambar 3.1 : Bukan himpunan konveks dan Himpunan konveks

Suatu hiperplane adalah himpunan konveks : Jika x1, x2 pada hiperplane, yaitu cx1 = z dan cx2 = z, maka x = λx2 + (1 − λ)x1 pada hiperplane, karena cx = c[λx2 + (1 − λ)x1 ] = λcx2 + (1 − λ)cx1 = λz + (1 − λ)z = z

Dengan cara yang sama, suatu setengah ruang tertutup adalah juga suatu himpunan konveks. Misalkan x1, x2 ada dalam setengah ruang tutup cx ≤ z ; jika x = λx2 + (1 − λ)x1 , (0 ≤ λ ≤ 1), maka cx = λcx2 + (1 − λ)x1 ≤ λ2 + (1 − λ)z = z, dan x dalam setengah ruang. Argumen-argumen yang sama akan dibuktikan, bahwa suatu setengah ruang terbuka adalah himpunan konveks. Irisan dari dua himpunan konveks adalah juga himpunan konveks. Diketahui himpunan konveks X1 , X2 , misalkan x1, x2 adalah dua titik dalam X3 = X1 ∩ X2 (jika hanya ada satu titik dalam x3 , maka x3 sendiri adalah konveks). Jadi λx2 + (1 − λ)x1 ∈ X1 sebab 0 ≤ λ ≤ 1,


18 λx2 + (1 − λ)x1 ∈ X2 sebab 0 ≤ λ ≤ 1, Akibatnya λx2 + (1 − λ)x1 ∈ X1 ∩ X2 = X3 dan X3 konveks. Jika Xi (i = 1, · · · , m) konveks, maka X =

m T

Xi juga konveks.

i=1

Jika X1 , X2 himpunan-himpunan tertutup, maka X3 = X1 ∩ X2 juga tertutup. Sehingga dapat jelas dilihat bahwa suatu titik dalam dari X1 dan X2 juga akan menjadi titik dalam dari X3 . Dengan cara yang sama, suatu titik yang tidak di dalam X1 dan/atau tidak dalam X2 tidak mungkin menjadi suatu titik batas dari X3 , karena itu setiap titik batas dari X3 adalah suatu titik batas dari X1 atau X2 . Akan tetapi X1 , X2 dan karenanya X3 memuat semua titik batas mereka, jadi X3 adalah tertutup. Hal yang sama benar untuk irisan dari sebanyak hingga himpunan tertutup . Telah ditunjukkan, bahwa hiperplane dan setengah ruang adalah himpunan konveks. Karena irisan dari sebanyak hingga himpunan konveks adalah konveks, maka irisan dari sebanyak hingga hiperplane atau setengah ruang atau keduanya adalah juga himpunan konveks. Selanjutnya, irisan dari dari sebanyak hingga hiperplane atau setengah ruang tertutup atau keduanya adalah himpunan konveks tertutup.


19 Ini mempunyai penerapan langsung pada program linear. Kendala pada masalah program linear dapat ditulis sebagai r X

aij xi {≤=≥}bi,

i = 1, · · · , m

(3.1)

j=1

Dimana satu dari tanda-tanda ≥, =≤, berlaku untuk setiap i. Tambahan lagi, ada pembatasan pembatasan tak negatif xj ≥ 0,

j = 1, · · · , r

(3.2)

Jika didefinisikan vektor baris dengan ai = (ai1, · · · , air ),

(3.3)

Persamaan (3.1) menjadi ai x{≤=≥}bi,

i = 1, · · · , m

(3.4)

Setiap satu dari kendala memerlukan, bahwa x yang diperkenankan dalam suatu setengah ruang tertutup yang diberikan dalam E r atau jika kesamaan langsung berlaku, terletak pada suatu hiperplane yang diberikan. Pembatasan-pembatasan tak negatif dapat juga ditulis dalam bentuk (3.4). Jika ditulis am+j = ej

(3.5)

maka xj ≥ 0 menjadi am+j x = ej x ≥ 0,

j = 1, · · · , r

(3.6)

Masing-masing pembatasan-pembatasan tak negatif juga memerlukan, bahwa x yang diperkenankan ada dalam suatu setengah ruang tertutup. Daerah E n


20 didefinisikan dengan xj ≥ 0, j = 1, · · · , n disebut ortan (orthant) taknegatif dari En. Sekarang dapat dilihat, bahwa suatu penyelesaian nyata x harus serempak menjadi suatu unsur dari setiap himpunan berikut [(3.4) dan (3.6)] Xi = {x|aix(≤=≥)bi},

i = 1, · · · , m + r,

(3.7)

dimana bi = 0, i = m + 1, · · · , m + r. Ini setara dengan mengatakan bahwa himpunan penyelesaian nyata X adalah irisan dari himpunan-himpunan Xi . X=

m+r \

xi

(3.8)

i=1

Karena itu, himpunan penyelesaian nyata pada suatu masalah program linear (jika suatu penyelesaian nyata ada) adalah suatu himpunan konveks tertutup. Dari analisis diatas ditunjukkan, bahwa himpunan penyelesaian pada suatu sistem dari m persamaan linear dalam n variabel, Ax = b adalah himpunan konveks tertutup . Untuk melihat ini, himpunan persamaan tersebut dapat ditulis dengan. ai x = bi ,

i = 1, · · · , m

(3.9)

dimana ai adalah baris ke-i dari A. Himpunan titik yang memenuhi persamaan ke−i terdiri dari hiperplane aix = b. Himpunan titik yang secara simultan memenuhi semua m persamaan adalah irisan dari m hiperplane (3.9); karena itu suatu himpunan konveks tertutup menetapkan, bahwa ada suatu penyelesaian. Selanjutnya, himpunan penyelesaian taknegatif pada Ax = b, yaitu himpunan penyelesaian dengan x ≥ 0, adalah juga himpunan konveks tertutup.


21 Telah didefinisikan bahwa suatu kombinasi konveks dari dua titik x1 , x2, sebagai λx2 +(1−λ)x1, 0 ≤ λ ≤ 1. Definisi ini dapat dengan mudah disamaratakan pada konsep kombinasi konveks dari m titik. Kombinasi Konveks : Suatu kombinasi konveks dari sebanyak hingga titik x1 , · · · , xn didefinisi sebagai suatu titik. x=

m X

µ i xi

µ ≥ 0, i = 1, · · · , m,

m X

i=1

µi = 1

(3.10)

i=1

Suatu kombinasi konveks dari m titik dapat ditafsirkan secara fisik. Misalkan dirangkaikan suatu massa mi dengan titik xi . Pusat massa dari ke-m titik diberikan dengan x=

m m X 1 X m 1 x1 , M = mi M i=1 i=1

(3.11)

Jika µI = mi /M, pusat massa diperoleh dari (3.10). Jadi suatu kombinasi konveks dari m titik dapat dibayangkan sebagai pusat massa dari titik-titik, dengan massa yang diberikan pada xi , menjadi suatu pecahan µi dari jumlah massa. Himpunan semua kombinasi konveks dari sebanyak hingga titik x1, · · · , xm adalah suatu himpunan konveks, yaitu himpunan ( ) m m X X X = x|x = µi xi , semua µi ≥ 0, µi = 1 i=1

(3.12)

i=1

adalah konveks. Untuk membuktikan ini, misalkan v, w titik-titik sedemikian sehingga v=

m X

µi xi, µi ≥ 0,

X

µi = 1

i=1

w=

m X

µi ”xi , µi ” ≥ 0,

X

µi ” = 1

i=1


22 Himpunan tersebut akan konveks, jika λw + (1 − λ)v adalah juga dalam himpunan untuk suatu λ(0 ≤ λ ≤ 1). Sekarang λw + (1 − λ)v =

m X

[λµi ” + (1 − λ)µi ]xi

(3.13)

i=1

Tetapi λµi ” + (1 − λ)µi ≥ 0 Dan m X

[λµi ” + (1 − λ)µi ] = λ

X

X µi ” + 1 − λ µi = 1

i=1

Jadi λw+(1−λ)v adalah juga suatu kombinasi konveks dari xi dan himpunan adalah konveks. Contoh: Gambar 3.3 menunjukkan himpunan dari semua kombinasi konveks dari titik-titik x1 , · · · , x7 =, · · · . Dalam E 2 ditemukan semua kombinasi konveks dari m titik dengan menyambung semua titik dengan garis-garis lurus. Poligon yang dihasilkan dan bagian dalamnya adalah himpunan yang diinginkan.

3.5 Sekam konveks (Convex Hull) Suatu himpunan A yang tidak konveks, adalah mungkin untuk memasukkan A dalam himpunan lain X yang konveks, sehingga setiap titik dalam A juga dalam X. Sering ingin ditemukan himpunan konveks ”terkecil” yang memuat A. Himpunan konveks terkecil yang memuat A ini disebut sekam konveks dari A. Contoh : (1) Sekam konveks dari himpunan A = [x1, x2 ]|x21 + x22 = 1] adalah X = [(x1, x2 )|x21 + x22 ≤ 1]. Sekam konveks dari titik-titik pada keliling dari suatu


23 lingkaran adalah keliling tambah bagian dalam dari lingkaran. Ini adalah himpunan konveks terkecil yang memuat keliling.

Gambar 3.2 : Polihedron Kompleks

(2) Sekam konveks dari dua titik x1, x2 adalah himpunan dari semua kombinasi konveks dari titik-titik ini X = [x|x = λx2 + (1 − λ)x1 , semua λ, 0 ≤ λ ≤ 1]. Ini adalah himpunan konveks terkecil yang memuat x1, x2 Sejauh ini belum didefinisikan dengan jelas arti kata ”terkecil” dalam E n . Untuk membuang penafsiran intuisi, para ahli matematika mendefinisikan sekam konveks sebagai berikut : Sekam Konveks : Sekam konveks dari suatu himpunan A adalah irisan dari semua himpunan konveks yang memuat A. Irisan semua himpunan konveks yang memuat A haruslah himpunan konveks terkecil yang memuat A. Jadi definisi ini hanya suatu perumusan yang cermat dan luwes dari ide intuisi ”terkecil”. Harus diingat bahwa irisan dari himpunanhimpunan sekam konveks adalah juga konveks.


24 Sekam konveks dari sebanyak hingga titik x1, · · · , xm adalah himpunan dari semua kombinasi dari x1, · · · , xm. Dalil ini menyatakan bahwa sekam konveks dari x1, · · · , xm adalah himpunan ) ( m m X X µi xi semua ≥ 0, µi = 1 X = x|x = i=1

(3.14)

i=1

Di atas telah ditunjukkan, bahwa X adalah konveks. Bukti akan dibuat dengan induksi pada sejumlah titik, yaitu pada m. Harus ditunjukkan, bahwa setiap himpunan konveks yang memuat x1, · · · , xm , juga memuat X. Jelasnya, dalil benar untuk m = 1, karena hanya ada satu titik dan µI = 1. Telah didefinisikan suatu himpunan dengan satu titik sebagai konveks. Dalil sama jelasnya untuk m = 2, tetapi tidak perlu dibuat pemakaian ini secara langsung. Sekarang dimisalkan, bahwa dalil benar m1, jadi, sekam konveks dari x1, · · · , xm−1 adalah himpunan. X1 =

(

x|x =

m−1 X

βi xi , semua βi ≥ 0,

i=1

m−1 X

βi xi, semua βi = 1

)

(3.15)

i=1

Kemudian, ditinjau sekam konveks X dari x1, · · · , xm. Sudah jelas, xm haruslah suatu elemen dari sekam konveks. Dengan cara yang sama, setiap titik dalam X1 adalah elemen dari X sebab X1 dapat diasumsikan sebagai sekam konveks dari x1 , · · · , xm−1 . Tambahan lagi, X harus memuat semua titik pada potongan garis yang menghubungkan titik-titik dalam X1 ke xm , yaitu semua titik x=λ

m−1 X

βi xi + (1 − λ)xm , 0 ≤ i ≤ 1

i=1

Jika µi = λβi , i = 1, · · · , m − 1, µm = (1 − λ), maka semua ui ≥ 0 dan m X i=1

µi =

m−1 X

λβi + (1 − λ) = λ + (1 − λ) = 1

i=1


(3.16)

25 Selanjutnya, karena setiap βi dan λ dapat berubah nilainya antara 0 dan 1, setiap µi dapat dianggap suatu nilai antara 0 dan 1, pembatasan satu-satunya P adalah µi = 1. Jadi, himpunan yang didefinisikan dengan (3.16) adalah himpunan dari semua kombinasi konveks dari x1, · · · , xm dan menyatakan sekam konveks dari x1 , · · · , xm , jika X1 adalah sekam konveks dari x1, · · · , xm−1 karena itu adalah himpunan konveks terkecil yang memuat x1 dan xm . Dengan induksi sekam konveks dari m adalah himpunan dari semua kombinasi konveks dari m titik. Dengan catatan bahwa sekam konveks dari m titik adalah juga himpunan tertutup. Definisi berikut adalah suatu penyamarataan langsung dari E 2 , E 3, dimana sekam konveks dari m titik adalah suatu polihedron (bidang banyak). Polihedron Konveks: Sekam konveks dari sebanyak hingga titik disebut polihedron konveks yang dijangkau oleh titik-titik ini. Sudah jelas bahwa polihedron konveks yang dijangkau oleh m titik dapat mempunyai lebih dari m titik ekstrem karena itu adalah himpunan dari semua kombinasi konveks dari m titik. Semua elemen himpunan, kecuali x1, · · · , xm terletak diantara satu atau lebih titik-titik ini mungkin merupakan titik-titik dalam dari polihedron konveks (lihat gambar 3.3) Hal ini memberi kesan, bahwa suatu titik dalam suatu polihedron konveks dapat dinyatakan sebagai suatu kombinasi konveks dari titik-titik dalam polihedron, yaitu, suatu x dapat ditulis X X µi = 1 x= µi x∗i , µi ≥ 0,

(3.17)

dimana x∗i adalah titik-titik ekstrem. Akan dibuktikan pernyataan ini nanti. Akan tetapi tidak setiap himpunan konveks dengan sebanyak hingga titik-titik ekstrem mempunyai sifat, bahwa suatu titik dalam himpunan dapat dinyatakan sebagai


26 suatu kombinasi konveks dari titik-titik ekstrem. Misalnya: Tidaklah benar, bahwa suatu titik dalam himpunan konveks yang ditunjukkan pada gambar 3.4 dapat dinyatakan sebagai suatu kombinasi konveks dari titik-titik ekstrem 1, 2, 3. Secara intuisi, dapat dilihat alasan untuk ini himpunan tak terbatas. Akan dibuktikan dalam satu dari bagian berikut, bahwa suatu himpunan konveks terbatas dengan sebanyak hingga titik-titik ekstrem adalah sekam konveks dari titik-titik ekstrem.

Gambar 3.3 : Himpunan Konveks Tak Terbatas

Simpleks:Sekam konveks dari suatu himpunan dari n + 1 titik dari E n yang tidak terletak pada suatu hiperplane dalam E n disebut suatu simpleks Suatu simpleks adalah suatu hal khusus dari suatu polihedron konveks. Karena ke n + 1 titik tidak terletak pada suatu hiperplane; n titik haruslah bebas linear, sebab kalau semua titik akan terletak pada suatu hiperplane yang melalui titik asal. Dalam E 2 suatu segitiga dan bagian dalamnya membentu suatu simpleks. Ketiga titik yang membentuk simpleks adalah titik-titik sudut dari segitiga.


27 3.6 Teorema pada hiperplane-hiperplane terpisah (separating) Pada bagian ini dan dua bagian berikut akan dibuktikan tiga teorema penting yang sangat berarti untuk suatu range yang luas dari masalah dalam program linear, teori keputusan dan teori game.

Teorema 3.6.1 Diketahui suatu himpunan konveks tertutup X. suatu titik y salah satu dari yang termasuk ke dalam himpunan X atau ada suatu hiperplane yang memuat y, sehingga semua dari X termuat dalam satu setengah ruang terbuka yang dihasilkan oleh hiperplane tersebut.

Ini adalah teorema dari hiperplane-hiperplane terpisah. Sebelum meninjau bukti, perlu dicatat bahwa kedua bagian dari teorema adalah saling lepas. Jika y termasuk pada hiperplane, maka tidak termasuk pada setengah ruang terbuka. Akan dimulai membuktikan teorema dengan menganggap, bahwa y tidak termasuk ke dalam X. Jadinya akan dicari titik w dalam X, sehingga untuk semua u dalam X. |w − y| = min |u − y|

(3.18)

Titik w adalah titik dalam X terdekat pada y (”terdekat” berarti ”jarak terpendek”). Karena himpunan tertutup, diketahui bahwa jarak minimum sebenarnya dianggap untuk suatu w. Di sana hanya dapat satu titik seperti w, sebab jika ada dua, titik tengah antara mereka akan berada di dalam X dan juga lebih dekat ke y. Berikut, akan ditinjau suatu u ∈ X. Maka titik (1 − λ)w + λu,

0≤λ≤1


28 dalam X. Tetapi oleh (3.18) |(1 − λ)w + λu − y|2 ≥ |w − y|2, 0 ≤ λ ≤ 1

(3.19)

Atau |(w − y) + λ(u − w)|2 ≥ |w − y|2 Dengan menguraikan bagian di atas, maka diperoleh : |(w − y)|2 + 2λ(w − y)(u − w) + λ2 |u − w|2 ≥ |w − y|2 Atau 2λ(w − y)0 (u − w) + λ2 |u − w|2 ≥ 0

(3.20)

Ambillah λ ≥ 0. dengan membagi (3.20) dengan λ menghasilkan . 2(w − y)(u − w) + λ|u − w|2 ≥ 0 Misalkan λ mendekati nol. Pada limit diperoleh (w − y)0(u − w) ≥ 0

(3.21)

u − w = u − y − (w − y)

(3.22)

Meskipun

Dengan menggantikan (3.21) ke (3.22), diperoleh (w − y)(u − y) ≥ |w − y|2 Tetapi |w − y|2 > 0, sebab w ∈ X dan y ∈ X karena itu (w − y)(u − y) > 0

(3.23)

(w − y)0u > (w − y)y

(3.24)

Atau


29 Definisikan c = (w − y), z = (w − y)0y = cy

(3.25)

Tinjau hiperplane cx = z. karena cy = z, y ada pada hiperplane. Akan tetapi, sesuai dengan (3.24). Suatu u ∈ X memenuhi cu > z

(3.26)

Jadi suatu titik dalam adalah setengah ruang *cx > z. Dalil terbukti.

Gambar 3.4 : Hiperplane Penyangga

Penafsiran geometri teorema dalam E 2, E 3 sangat sederhana. Pengujian dari Gambar 3.5 menunjukkan, bahwa bila y tidak dalam X, diambil untuk hiperplane dari teorema garis melalui y tegak lurus pada garis yang menyatakan jarak terdekat dari y ke X. Jadi untuk E n telah dibuktikan secara cermat dengan metode-metode aljabar. Teorema 3.6.1 menyatakan, bahwa suatu y ∈ X (tanpa memperhatikan betapa dekat y pada himpunan X) ada suatu hiperplane cx = z yang memuat y, sehingga cu > z untuk semua u ∈ X. Kenyataan ini memberi kesan, bahwa jika w suatu titik batas dari X, ada suatu hiperplane cx = z yang memuat w,


30 sehingga cu ≥ z untuk semua u ∈ X: ini benar, seperti yang akan dibuktikan kemudian. Hiperplane yang memuat titik batas disebut suatu hiperplane penyangga (supporting) pada himpunan konveks X. Hiperplane Penyangga: Diketahui suatu titik batas w dari suatu himpunan konveks X; maka cx = z disebut suatu hiperplane penyangga di w, jika cw = z dan jika semua dari X terletak dalam satu setengah ruang tertutup yang dihasilkan oleh hiperplane, yaitu cu ≥ z untuk semua u ∈ X atau cu ≤ z untuk semua u ∈ X.

Teorema 3.6.2 Jiwa w suatu titik batas dari suatu himpunan konveks tertutup, maka ada sedikitnya satu hiperplane penyangga dari w.

Teorema 3.6.1 sebenarnya tidak menunjukkan, bahwa titik w terdekat ke y adalah suatu titik batas dari X. Jelasnya, ini yang menjadi masalah, kalau tidak, maka akan ada suatu s ∈ X pada garis yang menghubungkan w, y dengan s = λw + (1 − λ)y,

0<λ<1

sehingga |s − y| = λ|w − y| < |w − y| Dan w tidak menjadi yang terdekat ke y. Jadi w suatu titik batas dari X. Dengan memakai (3.25) pada (3.21), diperoleh c(u − w) ≥ 0 atau cu ≥ cw


(3.27)

31 Jika kita tinjau hiperplane cx = cw = z

(3.28)

maka w ada pada hiperplane dan oleh (3.1) cu ≥ z untuk semua u ∈ X. Jadi titik batas w mempunyai suatu hiperplane penyangga. Akan tetapi kenyataan ini tidak membuktikan Teorema 3.6.2, karena pada Teorema 3.6.1, w bukan suatu titik batas sembarang, tetapi ditetapkan dengan pilihan dari y. Teorema 3.6.2 dapat dibuktikan, jika untuk suatu titik batas yang diberikan w, dapat ditemukan suatu titik y ∈ x, sehingga w titik terdekat dalam himpunan ke y. Sudah jelas, bagaimana mengerjakan ini secara geometri dalam E 2 dan E 3 Suatu normal pada himpunan di w dibangun dan suatu titik pada normal ini, tetapi di luar himpunan akan memenuhi syarat. Suatu pendekatan seperti itu tak dapat dengan mudah disamaratakan pada E n (nyatanya itu sulit dirumuskan dalam E 2 dan E 3 ) dan karenanya akan dimulai dalam suatu cara yang sedikit lain. Pilihlah suatu titik batas w dari X. Tinjaulah suatu tetangga ∈ sekitar w. untuk setiap ∈> 0, betapun kecilnya, ada titik-titik sebelah dalam hiperplane yang tidak dalam X. Pilihlah suatu ∈ (∈k ) yang diketahui dan cari dari tetangga suatu yk yang tidak dalam X. Maka suatu titik batas wk dari X akan merupakan titik terdekat dalam X ke yk . Telah ditunjukkan, bahwa ada suatu hiperplane penyangga ck x = ck wk = zk di wk berikut, dipilih suatu barisan dari ∈k , sehingga ∈k 7→ 0 untuk k 7→ ∞, dengan pertidaksamaan segitiga. |wk − w| = |wk − yk + yk − w| ≤ |wy − yk | + |yk − w|


(3.29)

32 Pemilihan yk memerlukan bahwa |yk − w| <∈k dan karena itu |yk − w| 7→ 0 untuk k 7→ ∞. Karena |wy − yk | adalah jarak terpendek antara yk dan X, maka |wk − yk | ≤ |yk − w| dan karenanya |yk − wk | 7→ 0 untuk k 7→ ∞. Disimpulkan bahwa |wk − w| 7→ 0 untuk k 7→ ∞, atau wk 7→ w. Untuk setiap wk ada suatu hiperplane penyangga ck x = zk . Dengan membaginya dengan |ck |, diperoleh nk x = bk ,

nk = ck /|ck |,

bk = zk /|ck |

(3.30)

dan |nk | = 1. Dengan pertidaksamaan Schwartz |bk | ≤ |nk ||wk | = |wk |,

(3.31)

Sebab wk ada pada hiperplane (6.29). Untuk k yang cukup besar ada suatu r > 0, sehingga |wk | < r tidak tergantung dari k. ini dipenuhi karena |wk | = |wk − w + w| ≤ |w| + |wk − w| Dan |wk − w| 7→ 0. suatu r yang memenuhi syarat di atas adalah r = 2|w|. Persamaan (3.30) jadinya dapat ditulis dalam bentuk −r < −|wk | ≤ bk ≤ |wk | < r

(3.32)

Jadi bk membentuk suatu barisan takhingga yang terbatas. Secara sama, komponen komponen dari nk membentuk barisanbarisan takhingga yang terbatas, sebab |nk | = 1


33

Gambar 3.5 : Hiperplane penyangga pada suatu titik batas w

Suatu Teorema pada barisan-barisan menyatakan bahwa barisan-barisan takhingga yang terbatas memiliki sedikitnya satu titik limit. Jadi, ada suatu barisan bagian dari titik-titik yk untuk mana nk 7→ n dan bk 7→ b untuk wk 7→ w. Selanjutnya, untuk setiap k, nk wk − bk = 0 dan pada limit, nw = b. Jadi telah ditunjukkan, bahwa untuk w ada suatu hiperplane nx = b untuk mana. nw = b,

nu ≥ b, semua

u∈X

dan ini adalah hiperplane penyangga. Teorema 3.6.2 telah terbukti Tetapi dalam membuktikan teorema, harus digunakan ide limit dan barisanbarisan terbatas. Hal ini tidak diuraikan di sini. Akan tetapi konsep-konsep ini harus diperkenalkan, karena tidak dapat dipastikan, bahwa nk , bk mendekati nilainilai tunggal bila dipilih barisan titik-titik yk dalam suatu cara khusus. Untuk barisan-barisan sembarang yk tidak selalu benar, bahwa nk , bk mendekati nilainilai tunggal. Teorema pada barisan-barisan terbatas menjamin bahwa ada suatu barisan yk untuk mana nk dan bk mendekati limit-limit tunggal. Meskipun hiperplane penyangga di w tidak perlu tunggal. Gambar 3.6 menggambarkan, bahwa setiap satu dari hiperplane adalah suatu hiperplane penyangga di w. Jadi, sua-


34 tu barisan titik sembarang yk tidak dapat dipakai untuk memperoleh nilai-nilai tunggal. Sehingga jelas bahwa Teorema 3.6.2 berlaku juga, jika X tidak tertutup, yaitu ada sedikitnya satu hiperplane penyangga pada suatu titik batas w, tanpa memperhatikan apakah w ∈ X atau tidak.

3.7 Hasil dasar dalam program linear Telah ditunjukkan, bahwa himpunan penyelesaian nyata pada suatu masalah program linear adalah himpunan konveks tertutup dan bahwa fungsi yang dioptimasi adalah suatu hiperplane. Hiperplane ini digerakkan sejajar dengan dirinya pada himpunan konveks dari penyelesaiannya sampai z dibuat sebesar mungkin (jika z dimaksimalkan), selagi masih mempunyai sedikitnya satu titik x pada hiperplane dalam himpunan konveks dari penyelesaian-penyelesaian nyata. Jadi, jika suatu hiperplane yang diketahui berpasangan dengan nilai optimal dan dari z. maka tidak ada titik pada hiperplane yang menjadi suatu titik dalam dari himpunan konveks+ dari penyelesaian-penyelesaian nyata X. untuk melihat ini, dimisalkan bahwa z = cx adalah suatu hiperplane optimal dan bahwa satu dari titik-titiknya x0 adalah titik dalam dari himpunan. Andai dipilih suatu ∈> 0 1 sehingga setiap titik dalam tetangga ∈ dari x0 ada dalam X. Titik x1 = x0 + ∈ 2 1 (c/|c|) ada dalam X dan cx1 = z + ∈ |c| > z. Ini menentang kenyataan, bahwa z 2 nilai maksimum. Jadi setiap titik dari X pada hiperplane optimal harus menjadi suatu titik batas. Karena itu, jika x0 adalah penyelesaian optimal pada masalah program linear, maka z = cx0 dan cu ≤ z untuk semua u ∈ x (dianggap bahwa z dimaksimalkan). Jadi, suatu hiperplane optimal adalah hiperplane penyangga


35 pada himpunan konveks dari penyelesaian nyata pada suatu penyelesaian optimal x0 .

Teorema 3.7.1 Suatu himpunan konveks tertutup yang terbatas dari bawah mempunyai titik-titik ujung dalam setiap hiperplane penyangga.

Himpunan konveks dari penyelesaian nyata pada suatu masalah program linear adalah tertutup dan terbatas dari bawah dengan 0, sebab xj ≥ 0 untuk semua j. Jadi, teorema menyatakan, bahwa jika ada suatu penyelesaian optimal, sedikitnya satu dari titik-titik ekstrem himpunan konveks dari penyelesaian nyata menjadi suatu penyelesaian optimal. Dalam E n , seperti E 2 , E 3, himpunan konveks dari penyelesaian nyata hanya akan mempunyai sebanyak hingga titik-titik ekstrem. Jadi kita mempunyai alat memilih titik-titik ekstrem dari himpunan konveks dari penyelesaian nyata, hanya sebanyak hingga titik-titik yang akan dicoba untuk menemukan penyelesaian optimal pada masalah. Dan malahan, adalah mungkin untuk menetapkan titik-titik ekstrem secara analitik. Inilah dasar dari metode simpleks. Sekarang akan dibuktikan Teorema 3.6.3. Hiperplane cx = z akan dianggap menjadi suatu hiperplane penyangga di x0 ke himpunan konveks tertutup X, yang terbatas di bawah. Irisan dari X dan himpunan S = [x|cx = z] akan dinyatakan dengan T . Irisannya tidak kosong, sebab x0 ∈ T ; selanjutnya, karena X dan S adalah himpunan konveks tertutup, begitu juga T ; maka T juga terbatas dari bawah karena X. Akan ditunjukkan, bahwa suatu titik ekstrem dari T adalah juga titik ekstrem dari X. jika t adalah titik dalam T , dan jika t = λx2 + (1 − λ)x1 ,

0<λ<1


36 di mana x1 , x2 ∈ x, maka x1, x2 ∈ T . ini dipenuhi dari kenyataan, bahwa ct = λcx2 + (1 − λ)cx1 = z

(3.33)

dan cx2 ≥ z, cx1 ≥ z, sebab cx = z adalah hiperplane penyangga. Dengan mencatat λ, (1 − λ) > 0, dapat dilihat bahwa (3.31) akan berlaku, jika dan hanya jika cx2 = z, cx1 = z, yaitu, jika dan hanya jika x1, x2 ∈ T . Jadi suatu titik ekstrem dari T tak dapat dinyatakan sebagai suatu kombinasi konveks dari dua titik dalam X dengan 0 < λ < 1. jadi suatu titik ekstrem dari T adalah suatu titik ekstrem dari X. Masih harus dibuktikan, bahwa T sebenarnya mempunyai suatu titik ekstrem, ini akan disempurnakan dengan menemukan suatu titik ekstrem. Dari semua titik dalam T , pilih salah satu dengan komponen pertama terkecil (secara aljabar). Ada sedikitnya satu titik seperti itu, karena T adalah tertutup dan terbatas dari bawah. Jika ada lebih dari satu titik dengan suatu komponen pertama terkecil, pilihlah titik atau titik-titik dengan komponen pertama dan kedua yang terkecil. Jika seandainya ada lebih dari satu titik dengan komponen pertama dan kedua terkecil, carilah titik atau titik-titik dengan komponen-komponen pertama, kedua, dan ketiga, dan seterusnya. Akhirnya, akan diperoleh suatu titik tunggal karena hanya satu titik yang dapat mempunyai semua komponennya dari nilai aljabar minimum. Titik tunggal t∗ yang tunggal ditetapkan dengan proses di atas adalah suatu titik ekstrem. Jika t∗ bukan titik ekstrem, dapat ditulis t∗ = λt1 + (1 − λ)t2 ,

0 < λ < 1;


t1 6= t2 ∈ T

(3.34)

37 Misalkan t∗ yang tunggal ditetapkan dengan meminimumkan komponen kej. Jika tj1 , tj2 komponen-komponen ke-j dari t1, t2, maka komponen ke-j dari (3.32) adalah t∗ = λtj1 + (1 − λ)tj2

0 < λ < 1,

(3.35)

Akibatnya : t∗ = ti1 = ti2

(i = 1, · · · , j − 1)

Tetapi kemudian (3.33) membuktikan, bahwa t∗j = tj1 = tj2, sebab kalau tidak t∗j > min[tj1, tj2]. Akan tetapi hasil ini bertantangan dengan kenyataan, bahwa hanya ada satu titik dengan t∗j , ini bila semua komponen-komponen 1, · · · , j−1 ada pada nilai minimum Akibatnya, t∗ tak dapat dinyatakan sebagai suatu kombinasi konveks dari dua titik lain dalam T (0 < λ < 1). Jadi t∗ adalah suatu titik ekstrem dan teorema telah terbukti. Bukti di atas juga memperagakan, bahwa suatu himpunan konveks terbatas tegas mempunyai titik-titik ekstrem dalam setiap hiperplane penyangga.

3.8 Inner Product (Perkalian Dalam) dan Ortogonalitas Suatu fungsi h·, ·i : Rn × Rm 7→ R adalah inner product jika:

1. hu, αv + βwi = α hu, vi , ∀α, β ∈ R 2. hu, vi = hv, ui. 3. hv, vi ≥ 0, dan hv, vi = 0 ⇔ v = 0

Untuk setiap vektorv,

p hu, vi disebut norm-nya.


38 Inner product (perkalian dalam) juga disebut metrik, karena dapat digunakan untuk mengukur panjang dan sudut. Untuk penyederhanaan, basis standar kerapkali dipilih untuk ruang vektor Rn sebagai himpunan dari vektor-vektor e1 = [1, 0, 0, · · · , 0]T , e2 = [0, 1, 0, · · · , 0]T , en = [0, 0, · · · , 0, 1]T

(3.36)

Matriks I = [e1, e2, · · · , en ] dengan vektor-vektor ini sebagai kolom-kolom tepatnya sama dengan matriks identitas n × n. Setiap diberikan dua vektor x = [x1, x2 , · · · , xn ]T dan y2 = [y1 , y2, · · · , yn ]T ∈ Rn , didefinisikan Inner product kanonik sebagai hx, yi = xT y = x1y1 + x2y2 + · · · + xn yn

(3.37)

Inner product ini menghasilkan 2-norm standar, atau norm Euclidean, || · ||2, yang mengukur panjang setiap vektor sebagai √ ||x||2 =

xT x

q = x21 + x22 + · · · + x2n

(3.38)

Perhatikan bahwa jika dipilih basis lain B yang terkait dengan basis standar I di atas sebagai I = BA, maka koordinat vektor x, y yang terkait dengan basis baru masing-masing adalah x dan y, dan ini mempunyai hubungan dengan x, y dengan x = Ax dan y = Ay. Inner product dalam bentuk koordinat baru menjadi hx, yi = xT y = (A−1 x)T (A−1 y) = (x)T A−T A−1 (y).

(3.39)

Rumus inner product ini dinyatakan berkenaan dengan basis baru dengan hx, yiA−T A−1 = (x)T A−T A−1 (y)


(3.40)

39 Ini disebut Inner product induksi dari matriks A. Dengan mengetahui matriks A−T A−1 , dapatlah dihitung inner product kanonik secara langsung dengan menggunakan koordinat atas basis nonstandar B 0. Dua vektor x, y disebut ortogonal jika inner product-nya sama dengan nol: hx, yi = 0 dan sering dituliskan sebagai x⊥y.

3.9 Kronecker Product dan Stack of Matrices Diberikan dua matriks A ∈ Rm×n dan B ∈ Rk×1 , Kronecker product-nya, yang dinotasikan dengan A ⊗ B, adalah matriks baru   a11B a12B · · · a1n B  a21B a22B · · · a2n B A⊗B = .. .. ..  ... . . .  am1 B am2B · · · amn B



   ∈ Rmk×nl  

(3.41)

Jika A dan B adalah dua vektor, yaitu n = l = 1, maka pergandaan A ⊗ B juga merupakan vektor tetapi dengan dimensi mk. Diberikan suatu matriks n×nA ∈ Rm×n , stack of matrix A adalah suatu vektor, yang dinotasikan dengan As, dalam Rm×n yang diperoleh dengan penumpukan ke n vektor kolomnya, misalnya a1, a2, · · · , an ∈ Rn , agar supaya:    a1  .  a2  mn  As =   ...  ∈ R   an

(3.42)

Sebagai operasi-operasi yang saling invers, As disebut A ”ditumpuk”, dan A disebut As ”tak ditumpuk”.


40 Kronecker product dan stack of matrices secara bersama-sama memungkinkan dapat menulis ulang persamaan-persamaan aljabar yang melibatkan vektor dan matriks ganda dengan banyak cara yang berbeda namun ekuivalen. Sebagai contoh misalnya, persamaan uT Av = 0

(3.43)

untuk dua vektor u, v dan suatu matriks A dengan dimensi yang tepat dapat ditulis ulang sebagai (v ⊗ u)T As = 0

(3.44)

Persamaan kedua sangat berguna bila A merupakan satu-satunya yang diketahui dalam persamaan.

3.10 Transformasi linier dan grup matriks Aljabar linier mengkaji sifat-sifat dari transformasi linier atau peta linier, antara ruang-ruang linier yang berbeda. Karena transformasi sedemikian dapat dinyatakan sebagai matriks, maka aljabar linier sampai tingkat yang berarti mengkaji sifat-sifat matriks. Transformasi linier dari ruang (vektor) linier Rn ke Rm didefinisikan sebagai peta L : Rn 7→ Rm sedemikian sehingga L(x + y) = L(x) + L(y), ∀x, y ∈ Rn , L(αx) = αL(x), ∀x ∈ Rn , α ∈ R Berkenaan dengan basis standar Rn dan Rm , peta L dapat dinyatakan dengan matriks A ∈ Rm×n sedemikian sehingga L(x) = Ax, ∀x ∈ Rn


(3.45)

41 Maka kolom ke-i dari matriks A tiada lain adalah bayangan dari vektor basis standar ei ∈ Rn dengan pemetaan L, yaitu A = [L(e1), L(e2), · · · , L(en )] ∈ Rm×n

Himpunan semua matriks (riil) m × n dinotasikan dengan M(m, n). Bila dipandang sebagai ruang linier, M(m, n) dapat diidentifikasi sebagai ruang Rmn . Bila ada sedikit keraguan, disebutkan peta linier L menurut representasi matriks. nya A. Jika n = m, maka himpunan M(n, n) = M(n) membentuk struktur aljabar yang disebut ring (atas field R). Yaitu, matriks di dalam M(n) tertutup dengan pergandaan dan perjumlahan matriks: Jika A, B adalah dua matriks n × n, maka demikian juga dengan C = AB dan D = A + B. Peta atau matriks linier yang ditemukan dalam visi komputer kerapkali mempunyai struktur aljabar khusus yang disebut grup. Grup adalah suatu himpunan G dengan operasi ”◦” atas elemen-elemen G yang:

1. tertutup: Jika g1 , g2 ∈ G, maka juga g1 ◦ g2 ∈ G; 2. asosiatif: (g1 ◦ g2 ) ◦ g3 = g1 ◦ (g2 ◦ g3 ), untuk semua g1 , g2 , g3 ∈ G; 3. mempunyai elemen satuan e : e ◦ g = g ◦ e = g, untuk semua g ∈ G; 4. mempunyai invers: Untuk setiap elemen g ∈ G, terdapat elemen g −1 ∈ G sedemikian hingga g ◦ g −1 = g −1 ◦ g = e.

Himpunan semua matriks (riil) nonsinguler n × n dengan pergandaan matriks membentuk suatu grup. Grup matriks sedemikian biasanya disebut grup linier


42 umum dan dinotasikan dengan GL(n). Suatu grup G mempunyai representasi matriks atau bisa direalisasikan sebagai suatu grup matriks jika terdapat suatu pemetaan injektif R : G 7→ GL(n); g 7→ R(g), yang tidak mengubah struktur grup dari G. Yaitu, invers dan komposisi elemen-elemen dalam G tidak berubah karena pemetaan dengan cara berikut: R(e) = In×n , R(g ◦ h) = R(g)R(h), ∀g, h ∈ G

(3.46)

Di bawah ini, diidentifikasi beberapa himpunan bagian penting dari M(n) yang memiliki struktur aljabar khusus (sebagai contoh grup matriks) dan sifatsifat yang menarik. Grup GL(n) itu sendiri dapat diidentifikasi sebagai himpunan semua transformasi linier yang memiliki invers dari Rn ke Rn dalam artian bahwa untuk setiap A ∈ GL(n), diperoleh peta linier L : Rn 7→ Rn ; x 7→ Ax

(3.47)

Perhatikan bahwa jika A ∈ GL(n), maka demikian pula halnya dengan inversnya: A−1 ∈ GL(n). Telah diketahui bahwa matriks An×n mempunyai invers jika dan hanya jika determinannya tidak nol. Karena itu, diperoleh, det(A) 6= 0, ∀A ∈ GL(n)

(3.48)

Grup linier umum, bila matriks dianggap diketahui hanya sampai suatu faktor skalar, GL(n)/R, disebut sebagai grup transformasi proyektif, yang elemenelemennya disebut matriks proyektif atau homografi.


43 Matriks dalam GL(n) dengan determinan +1 membentuk suatu subgrup yang disebut grup linier khusus, yang dinotasikan dengan SL(n). Yaitu, det(A) = +1 untuk semua A ∈ SL(n). Tidak sulit dibuktikan bahwa jika A ∈ SL(n), maka demikian pula halnya dengan A−1 = det(A)−1. Suatu transformasi affine L dari Rn ke Rn didefinisikan bersama oleh matriks A ∈ GL(n) dan vektor b ∈ Rn sedemikian sehingga L : Rn 7→ Rn ; x 7→ Ax + b

(3.49)

Himpunan semua transformasi affine sedemikian disebut grup affine berdimensi n dan dinotasikan dengan A(n). Perhatikan bahwa peta L yang didefinisikan sedemikian bukanlah peta linier dari Rn ke Rn kecuali b = 0. Namun demikian, dapat di ”tanamkan” peta ini ke dalam ruang yang satu dimensi lebih tinggi sehingga tetap dapat direpresentasikan " # dengan matrisk tunggal. Jika diidentifikasi suatu elemen x ∈ Rn dengan

Rn+1 , maka L menjadi peta dari Rn+1 ke Rn+1 dalam artian berikut ini: " # " #" # x A b x n+1 n+1 7→ R ; 7→ L:R 1 0 1 1 Dengan demikian, matriks berbentuk " # A b ∈ R(n+1)×(n+1) , A ∈ GL(n), b ∈ Rn 0 1

x 1

∈

(3.50)

(3.51)

menggambarkan peta affine sepenuhnya, dan disebut matriks affine. Matriks ini merupakan elemen dalam grup linier umum GL(n + 1). Dengan cara ini, A(n) diidentifikasi sebagai himpunan bagian (dan ternyata subgrup) dari GL(n + 1).


44 Perkalian dua matriks affine dalam himpunan A(n) adalah " #" # " # A1 b1 A2 b2 = A1A2 A1b2 + b1 ∈ R(n+1)×(n+1) 0 1 0 1 0 1

(3.52)

yang juga merupakan matriks affine dalam A(n) dan merepresentasikan komposisi dari dua transformasi affine. Diberikan Rn dan struktur inner product standarnya, hx, yi = xT y, ∀x, y ∈ Rn , dan akan ditinjau himpunan transformasi-transformasi (atau matriks-matriks) linier yang tidak mengubah inner product. Suatu matriks An×n (yang merepresentasikan peta linier dari Rn ke dirinya sendiri) disebut ortogonal jika tidak mengubah inner product, yaitu hAx, Ayi = hx, yi , ∀x, y ∈ Rn

(3.53)

Himpunan semua matriks ortogonal n × n membentuk grup ortogonal berdimensi n, dan dinotasikan dengan O(n). Yang jelas, O(n) adalah himpunan bagian (dan ternyata subgrup) dari GL(n). Jika R adalah suatu matriks ortogonal, harus diperoleh RT R = RRT = I. Karena itu, grup ortogonal O(n) dapat dicirikan sebagai O(n) = {R ∈ GL(n)|RT R = I}

(3.54)

Determinan det(R) dari matriks ortogonal R bisa sama dengan +1 atau −1. Subgrup dari O(n) dengan determinan +1 disebut grup ortogonal khusus dan dinotasikan dengan SO(n). Yaitu, untuk setiap R ∈ SO(n), diperoleh det(R) = +1. Ekuivalen dengan hal ini, dapat didefinisikan SO(n) sebagai irisan SO(n) = O(n) ∩ SL(n). Dalam kasus n = 3, matriks ortogonal khusus tepatnya adalah matriks rotasi 3 × 3.


45 Grup ortogonal versi affine memberikan grup (transformasi) Euclidean : Transformasi Euclidean L dari Rn ke Rn didefinisikan secara bersama oleh matriks R ∈ O(n) dan vektor T ∈ Rn sedemikian sehingga L : Rn 7→ Rn ; x 7→ Rx + T

(3.55)

Himpunan semua transformasi sedemikian disebut grup Euclidean berdimensi n dan dinotasikan dengan E(n). Yang jelas, E(n) adalah subgrup dari A(n). Karena itu, ini juga dapat ditanamkan ke dalam ruang yang satu-dimensi lebih tinggi dan mempunyai representasi matriks "

# R T ∈ R(n+1)×(n+1) , R ∈ O(n), T ∈ Rn 0 1

(3.56)

Jika R lebih lanjut merupakan anggota SO(n), maka transformasi sedemikian membentuk grup Euclidean khusus, yang secara tradisi dinotasikan dengan SE(n). Bila n = 3, maka SE(3) merupakan gerakan benda-kaku konvensional dalam R3 , di mana R adalah rotasi benda kaku dan T adalah translasi (atas kerangka koordinat rujukan yang dipilih). Karena semua grup transformasi yang diperkenalkan sampai sejauh ini mempunyai representasi matriks natural, maka grup tersebut adalah grup matriks. Untuk merangkumkan hubungannya, diperoleh SO(n) ⊂ O(n) ⊂ GL(n), SE(n) ⊂ E(n) ⊂ A(n) ⊂ GL(n + 1)


(3.57)

46 3.11 Gram-Schmidt dan dekomposisi QR Suatu matriks dalam GL(n) mempunyai n baris (atau kolom) yang saling bebas. Suatu matriks dalam O(n) mempunyai baris-baris (atau kolom-kolom) ortonormal. Prosedur Gram-Schmidt dapat dipandang sebagai suatu peta dari GL(n) ke O(n), karena mentransformasikan matriks nonsinguler ke matriks ortogonal. Sebut L+ (n) himpunan bagian dari GL(n) yang terdiri dari matriksmatriks segitiga bawah dengan elemen-elemen positip sepanjang diagonal. Matriks sedemikian membentuk subgrup dari GL(n). Untuk setiap A ∈ GL(n), terdapat suatu matriks segitiga bawah L ∈ Rn×n dan suatu matriks ortogonal E ∈ O(n) sedemikian sehingga A = LE

(3.58)

Bukti. Berbeda dengan konvensi buku, untuk penyederhanaan dalam bukti ini semua vektor mengindikasikan vektor baris. Yaitu, jika v adalah vektor baris n-dimensi, vektor tersebut berbentuk: v = [v1, v2, · · · , vn ] ∈ Rn . Notasikan vektor baris ke-i dari matriks tertentu A dengan ai untuk i = 1, 2, · · · , n. Bukti terdiri dari pembentukan L dan E secara iteratif dari vektor-vektor baris ai : l1 = a1

→ e1 = l1/ kl1k2 ,

l2 = a2 − ha2, e2i e1 ...... ... P ln = an − n−1 i=1 ha1+1 , ei iei

→ e2 = l2/ kl2k2 , .... .. → en = ln / kln k2 ,


47 Maka E = [eT1 , · · · , eTn ]T dan matriks L diperoleh sebagai   0 ··· 0   kl1k2  ha2 , e1i kl2k ··· 0  L= .. ..  .. 2 ..  . . . .    ha2 , e1i · · · han , en−1 i kln k2 Berdasarkan konstruksi E adalah ortogonal, yaitu EE T = E T E = I. Prosedur Gram-Schmidt memiliki keunikan karena bersifat sebab-akibat, dalam artian bahwa baris ke-i dari matriks hasil transformasi E hanya tergantung pada baris dengan indeks j ≤ i dari matriks awal A. Pemilihan nama E untuk matriks ortogonal di atas bukanlah kebetulan. Ternyata, akan digunakan filter Kalman sebagai cara untuk melaksanakan ortonormalisasi Gram-Schmidt dalam ruang Hilbert khusus, dan hasil E dari prosedur secara tradisi disebut inovasi. Ada sedikit variasi yang berguna untuk prosedur Gram-Schmidt. Dengan . mentranspose A = LE, diperoleh AT = E T LT = QR. Perhatikan bahwa R = LT adalah matriks segitiga atas. Dengan demikian, dengan mengaplikasikan prosedur Gram-Schmidt pada transpose suatu matriks, sehingga dapat didekomposisi menjadi bentuk QR di mana Q adalah matriks ortogonal dan R adalah matriks segitiga atas. Dekomposisi sedemikian disebut dekomposisi QR. Lebih jauh lagi, dengan menginversikan AT = E T LT , diperoleh A−T = L−T E = KE. Perhatikan bahwa K = L−T tetap merupakan matriks segitiga atas. Dengan demikian, dapat mendekomposisikan setiap matriks menjadi bentuk matriks segitiga atas yang diikuti dengan matriks ortogonal.


BAB 4 TEOREMA KETERBATASAN UNTUK SUATU METODE RELAKSASI

4.1 Gagasan Geometrik Utama Sebelum menganalisa kasus umum, ada baiknya diuraikan ide-ide geometrik yang menggerakkan pendekatan dalam R2 dan R3 . Untuk selanjutnya hingga awal bagian 4.6 dikaji sistem homogen AT x > 0. Pada bagian ini dan beberapa bagian lainnya akan diasumsikan bahwa ||a|| = 1 untuk semua a ∈ A. Ini mengisyaratkan tidak mengurangi keumuman, karena ηi dapat diganti dengan ηi ||ai ||, U diganti dengan U. maxa∈A ||a|| dan ai diganti dengan ai /||ai||. ¯ Dimulai dengan membahas kasus n = 2. Misalkan B(0) cakram satuan ter¯ 1(0) lingkaran satuan mengelilingi titik asal. Akan dihilangkan tutup dan S 1 = ∂ B himpunan M := {x ∈ S 1 : ∃a ∈ A dengan memenuhi a⊥x} ¯ 1 (0) melalui sejumlah hingga potongan konveks. Untuk a ∈ A dan r ≥ 0 dari B misalkan

C{a}⊥ (r) := x ∈ R2 : π{a}⊥ x ≤ r , Dimana π{a}⊥ x = x − (a.x)a adalah proyeksi x ke dalam span ({a})⊥ = {y ∈ R2 : a.y = 0} sepanjang a. Dengan demikian, C{a}⊥ (r) adalah sandwich dengan ketebalan 2r paralel dengan a. Dengan mengadopsi notasi yang sedikit menyusahkan ini dan mencamkan keumuman kemudian.


49

Gambar 4.1 : Interpretasi Geometri dari C{a}⊥ (r) Karena M terdiri dari titik-titik terasing yang banyaknya berhingga pada S 1 , dimungkinkan untuk memilih jari-jari r{a} ∈ (0, 1) yang cukup dekat dengan 1 untuk semua a ∈ A sedemikian hingga ¯1 (0) ∩ C c ⊥ (r{a}⊥ ) ∩ C c ⊥ (r{¯a}⊥ ) = θ B {a} {¯ a}

∀a, ¯a ∈ A with a 6= a ¯

(4.1)

lihat Gambar 4.1. Sebagai contoh misalnya, cukup dipilih r{a}⊥ = cos θ/2 untuk semua a ∈ A, di mana cos θ = max{|a.¯ a| : a, ¯a ∈ A, a 6= a ¯}

Sekarang akan diperhatikan himpunan ¯ 1 (0) ∩ C=B

\

2 C{a}⊥ (r{a} ⊥)

a∈A

yang diperoleh dari bola satuan tertutup dengan menghilangkan M melalui potongan - potongan konveks yang didefinisikan oleh sandwich C{a}⊥ (r{a}⊥ ), lihat Gambar 4.2. Perlu dicatat bahwa 2

1

r{a}⊥ := (1 − r{a}⊥ ) 2 > 0


50 Persamaan (4.1) mengisyaratkan bahwa terdapat sejumlah δ = min{r{a} : a ∈ A > 0 sedemikian sehingga a ∈ A, x ∈ C, aT x ≤ 0, 0 ≤ η ≤ δ ⇒ x + ηa ∈ C

(4.2)

Akan dibuktikan pernyataan ini dalam situasi yang lebih umum dari Lemma 4.4.4. Untuk sementara waktu, misalkan bahwa sifat ini berlaku dalam R2 dengan memeriksa Gambar 4.2. Himpunan C terbatas, tertutup dan konveks. C juga seimbang, yaitu x ∈ C ⇔ −x ∈ C, dan menyerap, yaitu untuk setiap x ∈ R2 terdapat aλ ≥ 0 sedemikian sehingga x ∈ λC. Digabungkan menjadi satu, sifat-sifat ini mengisyaratkan bahwa fungsi ukuran ξ : X 7→ min {λ ≥ 0 : x ∈ λC}

Gambar 4.2 : Pergerakan oleh δ sepanjang ai dalam bola satuan meter Yang terkait dengan C adalah norm pada R2 , lihat misalnya (Robertson dan Robertson, 1973). Hubungan (4.2) mengisyaratkan bahwa bilamana ξ(xi ) > U/δ diperoleh ξ(xi+1 ) ≤ ξ(xi ). Karena itu, ukuran tidak bisa tumbuh lebih besar dari O(U/δ). Karena semua norm pada R2 ekuivalen, dan karena barisan (xi )N terbatas dalam norm ξ, barisan tersebut juga terbatas dalam norm Euclidean.


51 Mengapa bukti tersebut tidak bisa berhasil dengan norm Euclidean dengan ¯1 (0) sebagai pengganti C ? Perlu dicatat menempatkan ξ dan cakram satuan B bahwa dengan penggantian ini, untuk semua x 6∈ M identitas kunci (4.2) bisa dijadikan berlaku sepanjang δ cukup kecil. Ini jelas bila x adalah titik interior ¯1 (0) syarat aT x < 0 mengisyaratkan bahwa garis x + ta cakram, dan untuk x ∈ ∂ B ¯1 (0) untuk positip kecil t. Masalahnya adalah bahwa sekarang menyayat interior B δ adalah fungsi dari x dan menjadi nol mendekati titik x ∈ M. Dengan demikian, batas U/δ besar sebarang dan pernyataan dilanggar. Tentu saja, tujuannya untuk mengeneralisir konstruksi ukuran ξ dan bola satuan tertutup terkaitnya C ke dimensi yang lebih tinggi, dan kemudian dibutuhkan potongan-potongan ekstra karena M tidak lagi terdiri dari titik-titik terasing. Dalam R3 misalnya, himpunan ini diperoleh sebagai gabungan lingkaranlingkaran grand M=

[

x ∈ S 2 : x, a = 0

a∈A

Didefinisikan C{a}⊥ (r{a}⊥ ) seperti sebelumnya, walaupun {a}⊥ sekarang meru¯1 (0) adalah bola satuan pakan komplemen ortogonal dari span ({a}) dalam R3 , B ¯ 1(0) adalah bola satuan, lihat Gambar Euclidean tertutup dalam R3 dan S 2 = ∂ B 4.3


52

Gambar 4.3 : Potongan Potongan dalam R3

Jika (4.2) ingin dipenuhi untuk dua vektor yang berbeda a, ã ∈ A, timbul masalah di dekat titik-titik perpotongan kedua lingkaran grand yang terkait dengan a dan ã: seperti yang telah diketahui di atas, kegunaan dari potonganpotongan C{a}⊥ (r{a}⊥ ) adalah untuk meratakan bola satuan ukuran C dalam arah a, sehingga dimungkinkan bergerak dengan jumlah gerakan berhingga dalam arah a dari suatu titik di dalam C di mana pertidaksamaan aT x > 0 dilanggar. Akan tetapi, dalam neighbourhood titik-titik x ∈ span ({a, ã})⊥ ∩ ∂C, perataan yang dihasilkan oleh potongan C{a}⊥ (r{a}⊥ ) dihancurkan oleh potongan C{ã}⊥ (r{ã}⊥ ) dan demikian sebaliknya, lihat daerah berbentuk ”intan” pada Gambar 4.4.


53

Gambar 4.4 : Interferensi Potongan-Potongan dalam Daerah Berbentuk Intan Masalah bisa dibuat tetap dengan mengaplikasikan lebih lanjut potonganpotongan berbentuk ˜}⊥ C{a,ã}⊥ (r{a,ã}⊥ ) := x ∈ R3 : |π{a,ã}⊥ x | ≤ r{a, a Di mana π{a,ã}⊥ x adalah proyeksi dari x pada span {a, ã}⊥ sepanjang span (a, ã), yang mengisyaratkan bahwa C{a,ã}⊥ (r{a,ã}⊥ ) adalah sandwich yang paralel dengan span (a, ã) hiperplane. Catat bahwa jika a dan a ˜ hampir segaris, maka daerah berbentuk intan menjadi sangat memanjang dan kemungkinan besar, kecuali jika r{a)⊥ dan r{ã)⊥ dipilih mendekati 1. Tambahan lagi, r{a,ã} haruslah dipilih cukup kecil agar C{a,ã}⊥ (r{a,ã}⊥ ) memotong daerah berbentuk intan, tetapi cukup besar sehingga tidak mengganggu perataan yang dihasilkan oleh jenis potonganpotongan yang sama. Terakhir, tiga vektor yang berbeda a, ã, ¯a ∈ A bisa tergantung linier, dan kemudian tiga lingkaran grand yang bersesuaian berpotongan di dua titik. Situasi ini tidak menyebabkan perlunya memasukkan jenis potongan baru, tetapi menghasilkan batasan tambahan atas kedalaman-potongan. Dalam Rn situasinya semakin diperburuk oleh fakta bahwa akan dibutuhkan n − 1 jenis potongan yang berbeda, masing-masing satu jenis potongan untuk


54 perpotongan k = 1, · · · , n − 1 dari lingkaran-lingkaran grand {x ∈ S n−1 : a.x = 0}, (a ∈ A) yang bersesuaian dengan k himpunan bagian bebas linier dari A, di ¯ 1(0) adalah bola satuan berdimensi- (n − 1) dan B ¯1 (0) bola mana S n−1 = ∂ B satuan tertutup Euclidean n-dimensi. Terdapat himpunan kombinasi terkomplikasi dari batasan-batasan yang menghubungkan kedalaman potongan-potongan yang berbeda, dan ekspresi kuantitatip untuk jari-jari tergantung pada sudut antara ruang bagian span(P ) dan span(Q) untuk himpunan bagian yang berbeda P, Q ⊂ A. Tambahan lagi, dibutuhkan generalisasi yang layak dari (4.1) agar bisa menjamin bahwa (4.2) berlaku. Untungnya, terdapat syarat aljabar sederhana atas jari-jari yang hanya melibatkan sangat sedikit dari banyak batasan kedalaman-potongan secara eksponensial dan menjamin bahwa batasan yang tersisa dipenuhi, lihat (4.5). Tambahan lagi, ketergantungan jari-jari pada sudut antara banyak ruang bagian secara eksponensial yang dibentangkan oleh vektor-vektor A bisa tertangkap dalam jumlah syarat tunggal κ(A) yang akan dikembangkan pada Bagian 4.2.

4.2 Jumlah Syarat untuk Menentukan Batas Pada bagian ini akan dibahas masalah dalam Rn dan digeneralisir beberapa konsep yang diperkenalkan di atas. Dimulai dengan objek yang akan memungkinkan didapat penentuan batas dalam teorema utama tulisan ini. Misalkan A adalah himpunan terurut berhingga dari vektor-vektor dalam Rn \{0}. Seperti telah disebutkan di muka, diidentifikasi A dan salah satu himpunan bagiannya dengan matriks yang diperoleh dengan mengkoleksi elemenelemennya sebagai vektor kolom dalam urutan yang ditetapkan. Misalkan m :=


55 rank(A), B ⊆ A dan k := #B. Misalkan B = Q(B)R(B) adalah dekomposisi QR tipis dari B. Yaitu, Q(B) ∈ Rn×k memenuhi Q(B)T Q(B) = Ik (merupakan matriks Stiefel) dan R(B) ∈ Rk×k adalah matriks segitiga atas dengan diagonal positip murni, diag (R(B)) > 0. Di tulis det(B) := det(R(B)) k

Perlu dicatat bahwa karena cara R(B) dipilih, bilangan ini selalu positip. Diberikan kepada semua ruang bagian V dari Rn batasan inner product Euclidean kanonik dari Rn ke V . Dengan keberadaan konvensi ini tampaklah bahwa |detk (B)| menyatakan volume k-dimensi standar dari paralelepipedum ( k ) X η1 b1 : η1 ∈ [0, 1](i = 1, · · · , k ⊂ span (B) i=1

di mana B = (b1 , · · · , bk ). Didefinisikan n o κ(A)−1 := min det(B) : (k = 1, · · · , m)B ⊆ A, #B = k, det(B) 6= 0 (4.3) k

k

Lemma 4.2.1 memadukan beberapa sifat sederhana dari κ(A). Bagian iv) dan buktinya diilhami oleh lemma lokalisasi untuk metode ellipsoid ( Khachiyan, 1979). Ini memberikan batas atas yang bisa dihitung secukupnya atas κ(A) bila A terdiri dari data input rasional. Ini berguna karena penghitungan langsung κ(A) melalui (4.3) umumnya tidak praktis. Akan dijelaskan bagaimana panjang-bit D yang muncul pada bagian iv) didefinisikan: setiap bilangan rasional r = ±p/q dapat direpresentasikan sebagai triplet (p, q, s), di mana p dan q adalah bilanganbilangan asli yang saling prima dan s = ±1 adalah tanda dari r. Diasumsikan bahwa p dan q dinyatakan dalam ekspansi biner terpendek yang mungkin, yaitu, jika string tidak kosong maka digit pembawa adalah 1. String kosong menyatakan


56 bilangan 0. Terakhir, s bisa direpresentasikan oleh bit tunggal informasi. Karena q 6= 0, maka representasi terpendek yang mungkin dari suatu bilangan mempunyai dua digit, yang bersesuaian dengan r = 0 yang direpresentasikan oleh (∅, 1, 0). Kemudian panjang-bit D didefinisikan sebagai jumlah panjang-bit dari semua komponen yang muncul dalam vektor A.

Lemma 4.2.1 Misalkan A ⊂ Rn \{0} adalah himpunan terurut berhingga dari rank(A) = m ≤ n. Maka pernyataan berikut berlaku:

i. K(A) tidak berubah dengan pengurutan ulang elemen-elemen A. ˆ mempunyai rank m di mana B1 = (ˆ a1, · · · , âk−1 ) ii. Jika B = (B1 B2 ) ⊆ A ¯ = (F B2) di mana F = (f1 · · · fk−1 ) adalah ak , · · · , a ˆm ) dan jika B danB2 = (ˆ basis ortogonal dari span(B1), maka det (B2 ) ≥ det(B) ¯ ≥ det(B) m−k+1 m m Khususnya, ini mengisyaratkan bahwa hanya matriks B dengan rank m yang dipertimbangkan dalam definisi κ(A). iii. Jika Aˆ := {ˆ a : a ∈ A}dimana a ˆ = a/ ||a| |, maka ˆ 6 κ(A) . min k a k−m κ(A) a∈A

iv. Jika A terdiri dari vektor input rasional dengan total panjang bit D maka κ(S) ≤ 2D .


57 Bukti. i) Misalkan B ∈ Rn×k adalah matriks dengan rank k, misalkan P ∈ Sk ˜ = BP . Yang perlu dibuktikan adalah bahwa adalah matriks permutasi k×k dan B ˜ . Misalkan G = (B G2 ) ∈ Rn×n sedemikian rupa sehingga |detk B| = detk B

ortonormal dari span(B)⊥ . # 0 , di mana Q1R11 adalah I " # ˜ := P 0 mempunyai dekomposisi QR tipis dari B. Samahalnya, matriks G 0 I " # ˜ ˜− Q ˜ 1G2 R11 0 , di mana Q1R11 adalah dekomposisi QR dekomposisi QE G 0 I tipis dari B. Karena itu, G2 mempunyai vektor kolom yang terdiri dari basis " R11 Maka dekomposisi QR dari G adalah (Q1Q2) 0

˜ ˜ ˜ det B = det R11 = det G = |det G| = det R11 = det B k

k

# " R11 R12 R R12 dan (Q1Q2 ) 11 merupakan dekomii) Misalkan (Q1Q2) 0 R22 0 R22 ¯ di mana blocking konsisten dengan posisi QR masing-masing dari B dan B, "

#

¯ 2 , R22, dan R ¯ 22 = I. Tambahan lagi, kolom ke-i dari (B1 B2 ). Maka Q2 = Q R11 adalah vektor dengan panjang kaik = 1, yang mengisyaratkan bahwa semua elemen diagonal dari R11 ≤ 1. Sekarang pertidaksamaan kedua diperoleh dari ¯ = det(R ¯ 11) det(R ¯ 22 ) > det(R ¯ 11) det(R ¯ 22) = det(B) det(B) m

m

# " ^ R11 R12 Sekarang misalkan (Q1Q2 ) merupakan dekomposisi QR dari B := 0 R22 ^

^

(B2 F ). Maka Q1 R11 adalah dekomposisi QR dari B2 , dan dengan pernyataan ^

yang sama seperti di atas, elemen-elemen diagonal dari R22 berada di dalam (0,1]. Karena itu, ^ ^ ^ ^ ¯ det (B2) = det (R11) > det (R11 ) det (R22) = det(B) = det(B) m−k+1


m

m

58 Dimana persamaan terakhir diperoleh dari bagian i) iii) Berdasarkan ii) bahwa perlu dipertimbangkan rank-m himpunan bagianˆ =Q ˆR ˆ himpunan bagian dari B = (b1, · · · , bm ) ⊂ A. Misalkan B = QR dan B ˆ = {ˆb : b ∈ B} dimana ˆb = b/ kbk adalah dekomposisi QR tipis dari B dan B ˆ dan R = R ˆ diag (kbi k),dan karena itu, menandakan normal dari b. Maka Q = Q m Y m ˆ ˆ kbi k > det B . min kak . det B = det R = det R . m

i=1

m

a∈A

Sekarang pernyataan dipenuhi dengan mudah. iv) Misalkan B = (b1 , · · · , bm ) adalah himpunan bagian dari A sehingga minimum dalam (4.3) dicapai. Maka himpunan bagian terurut F = (fm+1 , · · · , fn ) melengkapi B ke dari vektor-vektor satuan kanonik dalam Rn bisa # " dipilih untuk ¯ = (BF ) dari Rn . Jika (Q1Q2) R11 R12 adalah dekomposisi dalam basis B 0 R22 ¯ QR dari B, maka dekomposisi "tipis QR dari # B adalah Q1R11 . Tambahan lagi, R11 R12 mempunyai norm kfi k = 1 untuk karena vektor kolom ke-i dari 0 R22 (i = m + 1, · · · , n), entri-entri diagonal dari R22 semuanya ≤ 1. Karenanya ^ det(B) = det (R11) > det (R11) det (R22) = det(B) m

¯ ≥ 2−D . Untuk (i = 1, · · · , m) Karena itu cukup dibuktikan bahwa det(B) misalkan D(bi ) adalah jumlah panjang bit dari komponen-komponen bi. Misalkan scm(bi ) adalah kelipatan persekutuan terkecil dari komponen-komponen bi . Maka scm(bi ) lebih kecil dari pergandaan penyebut komponen-komponen dalam bi, dan ¯ · (diagsem(b1 ) I) adalah matriks bilangan ini lebih kecil dari 2D(bi ) . Tambahan lagi, B


59 bulat dan karenanya mempunyai determinan bilangan bulat. Karena itu, diag scm (bi ) ¯ )) det (B . (I 1 det (B) ¯ = > Pk > 2−D Qk 2 i−1 D(b1 ) i=1 scm (bi ) yang melengkapi bukti. Definisi 1 Untuk suatu himpunan takterurut A dari vektor-vektor tak nol dari Rn ditulis κ(A) untuk bilangan κ yang diperoleh dengan (4.3) untuk pengurutan sebarang dari elemen-elemen A. Bagian i) dari Lemma 4.2.1. menunjukkan bahwa gagasan ini terdefinisi dengan jelas. κ(A) memegang peranan sejumlah syarat untuk himpunan data input A dalam menentukan kuantitas batas-batas pada Bagian 4.5 dan 4.6.

4.3 Memilih Potongan Konveks untuk Konstruksi Ukuran Pada semua bagian ini diambil A sebagai himpunan vektor-vektor satuan. Untuk P ⊂ Rn misalkan πp proyeksi ortogonal dari Rn pada span(P ) sepanjang span(P )⊥ , dan misalkan πp⊥ = id − πp. Untuk r ≥ 0 didefinisikan himpunan Cp (r) := {x ∈ Rn : kπpxk ≤ r} Cp⊥ (r) := {x ∈ Rn : kπp⊥xk ≤ r} Perlu dicatat bahwa setiap vektor dalam Rn ortogonal terhadap semua elemen himpunan kosong, khususnya diperoleh π∅⊥ = id, dan karenanya dianggap π∅ = 0 merupakan proyeksi pada {0}. Sedikit penyalahgunaan notasi akan memu¯ 1 (0) dan C∅ (r) = Rn untuk semua r ≥ 0. dahkan, agar diperoleh C∅⊥ (1) = B Demikian juga, jika span(P ) = Rn maka Cp⊥ (r) = Rn untuk semua r ≥ 0. Selanjutnya akan didefinisikan algoritma yang mendefinisikan himpunan jarijari {rp : P ⊆ A} ⊂ [0, 1] yang terkait dengan himpunan lainnya {rp⊥ } ⊂ [0, 1]


60 melalui hubungan r p⊥ =

q 1 − rp2

,

∀P ⊆ A

(4.4)

Diberikan Pk (A) = {P : P ⊆ A, rank(P ) = 1}, (k = 1, · · · , m), di mana o n [k] [k] m = rank(A). Misalkan nk := #Pk (A) dan misalkan Pk = P1 , · · · , Pnk [k]

penyebutan elemen-elemen dari Pk . Juga misalkan nki := #Pi [k]

Pi

[k]

[k]

dan misalkan

[k]

= {a1 , · · · , anki } penyebutan elemen-elemen dari Pi .

Algoritma 4.3.1. m−1 S

S0 Set rφ = o, k = m and rp = 12 (p ∈ pm (A)), rQ = 1(Q ∈

Pi (A))

i=1

S1 For i = 1, · · · , nk For j = 1, · · · , nki [k]

[ki]

if rank Pi \{aj }) = k1 l rP [k] \{a[ki]} ← min(rP [k] \{a[ki]}, 2−3/2 rP [k] i

j

i

j

i

r{a[ki]} ← min(rP [k]\{a[ki]} , 2−3/2rP [k] i

i

j

i

r

2

[ki] 1 − πP [k]\a[ki]} aj i

i

2

[ki] 1 − πP [k] \a[ki]}aj

end end end S2 if k > 2,

r

k ← k1 else if k = 2

stop end.


i

i

61 Lemma 4.3.1 Misalkan A adalah himpunan berhingga dari vektor-vektor satuan dalam Rn dan misalkan himpunan jari-jari {rp : P ⊆ A} dihasilkan oleh Algoritma 4.3.1. Maka sifat-sifat berikut berlaku: i) r∅ = 0, ii) rp ∈ (0, 1] untuk semua P ⊆ A sedemikian sehingga P 6= ∅ iii) untuk semua P ⊂ A dan a ∈ A sedemikian sehingga P 6= ∅ dan a 6∈ span(P ), rP ∪(a) ≥

2 + rP2 4(r{a}

(4.5)

1 − kπpak2

Bukti. Syarat i) dipenuhi karena r∅ ditetapkan sama dengan nol pada tahap S0 dan selanjutnya tidak pernah berubah. Syarat ii) dipenuhi karena untuk semua P ⊆ A sedemikian sehingga P 6= ∅, rP himpunan dalam [ 12 , 1] pada tahap S0, dan bilamana rp selanjutnya berubah rp digantikan oleh nilai yang lebih kecil tetapi positip. Karena rp berubah hanya sejumlah berhingga kali, maka nilai akhirnya berada di dalam (0,1]. Tahap S1 menjamin bahwa syarat iii) berlaku untuk (P ∪ {a}) ∈ Pk (A) di akhir iterasi k, di mana dihitung iterasi mundur dari m hingga 2. Karena rP ∪{a} tidak mengubah penyelesaian iterasi k + 1 dan tidak pernah jika k = m, dan karena rp dan r{a} hanya bisa menurun lebih lanjut setelah nilainya ditetapkan memenuhi (4.5) dalam iterasi k, maka algoritma berhenti m S Pk . Tambahan dengan syarat iii) yang berlaku untuk semua (P ∪ {a} ∈ k=2

lagi, jika (P ∪ {a}) ∈ P1 dan a 6∈ span(P ) maka P = ∅, dan tidak perlu untuk memeriksa (4.5). Lemma 4.3.2 Misalkan A ⊂ Rn himpunan berhingga dari vektor-vektor satuan dan misalkan himpunan jari-jari {rp : P ⊆ A} dihasilkan oleh Algoritma 4.3.1.


62 untuk suatu pilihan spesifik penyebutan elemen-elemen dari Pk dan juga penyebutan elemen-elemennya untuk (k = 1, · · · , m). Maka {rp : P ⊆ A} dan himpunan jari-jari terkait {rp⊥ : P ⊆ A} memenuhi sifat-sifat berikut: 1 i) min{{rp⊥ : P ⊆ A} ≥ , 2 ii) min{rp : P ⊆ A} ≥ κ(A)−1 2−(3n+2)/2 . Bukti. i) Catat bahwa jika k < m maka setiap Q ∈ Pk (A) naik jika Q = P \{a} untuk suatu P ∈ Pk+1 (A) dan vektor a ∈ A sedemikian sehingga a 6∈ span(Q). Karena itu, jika di awal iterasi k + 1 diperoleh rp ≤ P ∈ Pk+1 maka rQ akan berubah menjadi nilai ≤ rp 2−3/2 <

1 2

1 2

untuk semua

pada iterasi k + 1.

Kemudian ini mengisyaratkan bahwa di awal iterasi k diperoleh rQ ≤ semua Q ∈ Pk . Karena di awal iterasi m diperoleh rp ≤

1 2

1 2

untuk

untuk semua P ∈ Pm ,

induksi atas k menunjukkan bahwa pada waktu algoritma berhenti dan diperoleh rp ≤

1 2

untuk semua P ⊆ A, termasuk P = ∅ untuk mana didapat rp = 0. Karena √ p 1 3 2 ≥ untuk semua P ⊆ A. itu, rp⊥ = 1 − rp ≥ 2 2 ii) Misalkan a ∈ A. Bukti dari bagian i) menunjukkan bahwa r{a} ≤

1 2

dan karenanya r{a} berubah setidak-tidaknya satu kali selama operasi Algoritma 4.3.1. Karena itu, terdapat indeks k ∈ {2, · · · , m} dan himpunan bagian P [k] ∈ Pk sedemikian sehingga a ∈ P [k] , rank(P [k] \{a}) = k1 dan di mana P [k] dan a [k]

memegang peranan Pi

[k]

dan aj bila r{a} berubah untuk terakhir kalinya. Yaitu,

diperoleh r{a} = rp[k] .

r

2

3

[k] 1 − πp[k]\{a[k]} a . 2− 2

Tambahan lagi, rp[k] ada pada nilai akhirnya pada tahap ini karena jari-jari ini tidak berubah setelah iterasi k + 1 (sekali lagi dengan menghitung mundur


63 dari m hingga 2). Kecuali jika k = m, rp[k] juga berubah setidak-tidaknya satu kali, tetapi hanya sejumlah hingga dan hanya selama iterasi k + 1. Karenanya ada terakhir kali saat jari-jari ini berubah menjadi r

2

3

rP [k] = rp[k+1] . 1 − πp[k+1]\{a[k+1]} a[k+1] . 2− 2 Untuk suatu P [k+1] ∈ Pk+1 dan vektor a[k+1] ∈ P [k+1] yang bebas linier dari P [k] dan sedemikian sehingga P [k+1] = P [k] ∪ {a[k+1]}. Dengan menulis P [k−1] untuk P [k] \a[k] dan dengan melanjutkan konstruksi ini melalui induksi, didapati bahwa terdapat himpunan P [m] ∈ Pm , dan vektor {a[k], · · · , a[m]} ⊂ A sedemikian sehingga P [m] = P [k−1] ∪ {a[k], · · · , a[m]} P [s] := P [k−1] ∪ {a[k], · · · , a[s]} ∈ Ps (s = k, · · · , m) dan r{a} = rp{m} .

m Y

q 3 2 1 − kπps−1 a[s] k .2− 2 (m−k+1)

s=k

3 1 k [m] − 2 (m−k+1) = . det (f1 , ..., fk−1 , a , ..., a ) .2 2 m > κ(A)−1 .2−

3n+2 2

di mana {f1 , · · · , fk−1 } adalah basis ortogonal dari P [k−1] .

4.4 Bola Satuan Ukuran dan Sifat-sifatnya Pada bagian ini dilanjutkan dengan mengasumsikan bahwa A adalah himpunan vektor-vektor satuan.

Lemma 4.4.1 MisalkanA adalah himpunan berhingga dari vektor-vektor satuan dalam Rn dan misalkan P ⊂ A dan a ∈ A sedemikian sehingga P 6= ∅ dan a 6∈


64 span(P ). Terakhir, misalkan r{a}, rp , r{a}∪P ∈ (0, 1] sedemikian sehingga (4.5) berlaku. Maka C{a}∪P

r{a} ∪ P √ 2

⊃ C{a} r{a} ∩ CP (rP )

Bukti. Setiap x ∈ Rn dapat ditulis sebagai x = λa + µa + x⊥ di mana x⊥ ⊥ span(P ∪ {a}), dan di mana ã ∈ span(P ) sedemikian sehingga k˜ ak = 1. Maka x ∈ C{a}(r{a}) dan x ∈ Cp (rp ) mengisyaratkan

2 2 2 λ2 + µ2 (a . ã)2 + 2λµ(a . a˜) = (a . x) = π{a}x 6 r{a} ,

2 µ2 + λ2 (a . ã)2 + 2µλ(a . a ˜) = (˜ a . x)2 = π{ã} x 6 kπP xk2 6 rP2 Dengan menjumlahkan kedua pertidaksamaan diperoleh 2 r{a} + rP2 > (λ2 + µ2 )(1 + ( a ˜.a)2 + 4λµ(a . a˜)

(4.6)

Di lain pihak,

π{a}∪P x 2 = kλa + µ˜ ak2 = λ2 + µ2 + 2λµ(a . a ˜) Karena itu,

2 2 π{a}∪P x = (λ2 + µ2 ) (1 + (˜ a . a)2 ) + 4λµ( a . a ˜) + (λ2 + µ2 ) (1 − (˜ a . a)2) (4.6)

6

2 r{a} + rP2 + (λ2 + µ2 ) (1 − (˜ a . a)2)

(4.7)

Tanpa kehilangan keumuman dapat diasumsikan bahwa 0 ≤ a ˜·a<1 Ternyata, jika a ˜ · a < 0 maka ã bisa diganti dengan −˜ a dan µ bisa diganti dengan


65 µ. Tambahan lagi, kak = k˜ ak = 1 dan pertidaksamaan Cauchy-Schwartz mensyaratkan bahwa 0 ≤ a ˜ · a ≤ 1, dan jika a ˜ · a = 1 maka a = a ˜ ∈ span(P ), yang kontradiksi dengan asumsi semula. Catat bahwa 2|λµ| ≤ λ2 + µ2 dengan penyelesaian kuadratik. Karenanya, 4 |λµ| (a . ã) 6 2(λ2 + µ2 ) (a . a ˜) dan karenanya, (4.6) menunjukkan bahwa 2 r{a} + rP2 > (λ2 + µ2 ) (1 + (˜ a . a)2 = 2(˜ a . a))

= (λ2 + µ2 ) (1 − a ˜. a)2 yaitu, 2

2

2

(λ + µ ) (1 − (˜ a . a) ) 6

2 + rP2 ) (1 − ã . a)2 (r{a}

(1 − ã . a)2

=

2 + rP2 ) (1 + a ˜ . a) (r{a}

(1 − a ˜ . a)

Sekarang (4.7) mensyaratkan 2 2 2 r{a} r{a}

+ rP2 + rP2 + rP2

2 r{a} 1 + a ˜ . a

π{a}∪P x 6 . +1 = 6 2 1 − ã . a 1−a ˜.a 1 − kπpak =

2 + rP2 ) (1 + kπp ak) (r{a}

(1 − kπp ak) (1 + kπpak) (4.5)

6

6

2 2(r{a} + rP2 )

1 − kπp ak2

rP2 ∪{a} 2

Ini membuktikan pernyataan.

Lemma 4.4.2 Misalkan A himpunan berhingga dari vektor-vektor satuan dalam Rn , misalkan P, Q ⊆ A sedemikian sehingga span(P ) ⊂ span(Q) tetapi span(P ) 6= √ span(Q) dan misalkanrp < rQ / 2. Maka rQ CQ √ ∩ CQ⊥ (rQ⊥ ) ⊂ Cp⊥ (rp⊥ ). 2


66 Bukti. Misalkan x ∈ CQ

r √Q 2

∩ CQ⊥ (CQ⊥ ) Maka

2 2 2

2 rQ rQ rQ 2 2

+ rQ⊥ = + (1 − rQ ) = 1 − kxk = kπQ xk + πQ⊥ x 6 2 2 2 2

2

Tetapi kemudian

r2

πp⊥ x 2 6 kxk2 6 1 − Q < 1 − r2 = r2⊥ p p 2 Akibat 4.4.3. Misalkan P ⊂ A dan a ∈ A sedemikian sehingga a 6∈ span(P ). Jika (4.5) berlaku danr∅ = 0 maka C{a}⊥ (r{a}⊥ ) ∩ C{a}(r{a}) ∩ CP ⊥ (rP ⊥ ) ⊇ C{a}⊥ (r{a}⊥ ) ∩ C{a} (r{a}) ∩ C({a}∪P )⊥ (r({a}∪P )⊥ )

(4.8)

Bukti. Jika P = ∅ maka ¯ 1 (0) CP ⊥ (rP ⊥ ) = Cφ⊥ (1) = B dan C({a}∪P )⊥ (r({a}∪P )⊥ ) = C{a}⊥ (r{a}⊥ ) dan karena C{a}⊥ (r{a}⊥ ) ∩ C{a}(r{a}⊥ ) ⊂ ¯1 (0), (4.8) berlaku secara trivial. Karena itu bisa diasumsikan bahwa P 6= ∅. B Misalkan x ∈ C{a}⊥ (r{a}⊥ ) ∩ C{a}(r{a}) ∩ C({a}∪P )⊥ (r({a}∪P )⊥ ) dan asumsikan kebalikan dari pernyataan diatas bahwa x 6∈ CP ⊥ (rP ⊥ )

(4.9)

¯ 1(0), diperoleh kxk ≤ 1. Karena itu, (4.9) Karena C{a}⊥ (r{a}⊥ ) ∩ C{a}(r{a}) ⊂ B mensyaratkan bahwa 2

2

2 (4.9)

1 > kxk = kπP ⊥ xk + kπP xk

2

> rP2 ⊥ = kπP xk


67 dan ini mensyaratkan bahwa kπP xk2 < 1 − rP2 ⊥ = rP2 yaitu, x ∈ CP (rP ). Karena x juga berada di dalam C{a}(r{a} dan (4.5) berlaku, √ Lemma 4.4.1. mensyaratkan bahwa x ∈ C{a}∪P (r{a}∪P / 2) Karena dipilih x dalam C({a}∪P )⊥ (r({a}∪P )⊥ ) dan 2 r{a}∪P

2

>

2 r{a} + rP2

1 − kπP ak

> rP2

Lemma 4.4.3 yang diaplikasikan pada P dan Q = {a}∪P mengisyaratkan bahwa x ∈ CP ⊥ (rP ⊥ , kontradiksi dengan asumsi (4.9).

Lemma 4.4.4 Misalkan A himpunan berhingga dari vektor-vektor satuan dalam Rn , misalkan {rP : P ⊆ A} ⊂ [0, 1] himpunan jari-jari untuk mana sifat-sifat Lemma 4.3.2. berlaku, dan misalkan C :=

\

CP ⊥ (rP ⊥ )

P ⊂A

Maka berlaku implikasi berikut: a ∈ A, x ∈ C ⇒ x(x · a)a ∈ C a ∈ A, x ∈ C, x . a 6 0, 0 6 η 6 r{a} ⇒ x + ηa ∈ C

Bukti. Perlu dibuktikan bahwa x − (x . a)a, x + µa ∈ CP ⊥ (rP ⊥ ) untuk semua P ⊆ A. Kasus 1: jika a ∈ span(P ) maka asumsikan χ ∈ Cp⊥ (rp⊥ ) mengisyaratkan

πp⊥ (x + λa) = πp⊥ x 6 rp⊥

∀λ ∈ R


68 dan karenanya, x − (x . a)a, x + ηa ∈ CP ⊥ (rP ⊥ ). Kasus 2: a 6∈ span(P ). Dari kasus 1 berlaku bahwa x − (x . a)a ∈ C{a}⊥ (r{a}⊥ ) ∩ C{a}(r{a}) ∩ C(P ∪{a})⊥ (r(P ∪{a})⊥ ) Karena itu, Persamaan (4.8) mengisyaratkan bahwa x − (x . a)a, ∈ CP ⊥ (rP ⊥ ). Bersama-sama dengan kasus 1, asumsi x · a ≤ 0 dan 0 ≤ η ≤ r{a} juga mengisyaratkan bahwa x + ηa ∈ C{a}⊥ (r{a}⊥ ) ∩ C{a}(r{a}) ∩ C(P ∪{a})⊥ (r(P ∪{a})⊥ ) dan kemudian (4.8) mengisyaratkan bahwa x + ηa ∈ CP ⊥ (rP ⊥ ) atau jika tidak (x + ηa). a < −r{a}. Tetapi kemudian diperoleh 0 ≤ η ≤ η + r{a} ≤ x · a, yang menunjukkan bahwa x+ηa adalah kombinasi konveks dari x dan x(x·a)a, di mana keduanya berada di dalam CP ⊥ (rP ⊥ ). Karena itu, konveksitas dari CP ⊥ (rP ⊥ ) mengisyaratkan bahwa χ + ηa ∈ CP ⊥ (rP ⊥ )

4.5 Keterbatasan Relaksasi untuk Sistem Homogen Akhirnya dimulai pembahasan terhadap hasil utama tulisan ini yang mengeneralisir dan menguatkan teorema keterbatasan perceptron klasik:

Teorema 4.5.1 Misalkan A himpunan berhingga dari vektor-vektor tak nol dalam Rn , diberikan x0 ∈ Rn sebagai titik awal, (ηi )N0 ∈ [0, U ] dan (ai )N0 ⊆ A sedemikian sehingga barisan titik-titik yang didefinisikan secara iteratif oleh xi+1 = xi +ηi ai memenuhi syarat xi · ai ≤ 0 untuk semua i ∈ N0 . Maka untuk semua i, kxi k dibatasi oleh



M(A) := 2 max kx0 k , U max kak . [min kak a∈A

rank (A)

a∈A




κ(A)23n/2 +1 

69 Bukti. Misalkan {rP ⊥ : P ⊆ A}, {rP : P ⊆ A} dan C dipilih seperti dalam Lemma 4.4.4. bila diaplikasikan pada A{a/ kak : a ∈ A}. Himpunan C adalah irisan berhingga dari himpunan-himpunan konveks, seimbang, penyerap, dengan jalan mana C memperoleh sifat-sifat ini. Tambahan lagi, C terbatas ¯ 1 (0) . Karena itu, ukuran karena C ⊂ Cφ⊥ (rφ⊥ ) = B ξ :→ min{λ ≥ 0 : x ∈ λC} yang terkait dengan C adalah norm atas ruang dimensi-berhingga Rn , lihat misalnya (Robertson dan Robertson, 1973). Didefinisikan As := U . max kak . max r −1 ↔ a∈A

˜ a∈A

{a}

Ai := As + U . max kak . max r −1 P1 a∈A

˜ a∈A

Andaikan ξ(xi ) ≥ As untuk i ∈ N. Catat bahwa definisi dari ξ mengisyaratkan bahwa xi ∈ ξ(xi )C. Tambahan lagi, karena xi · a ≤ 0 dan ηi . kai k 6 U . max kak . A−1 a} s 6 r{˜ a∈A ξ(xi ) Lemma 4.4.4. menunjukkan bahwa ηi . kai k xi + ãi ∈ ξ(xi ) C xi + ηi ai = ξ(xi ) ξ(xi ) ξ(xi ) dan karenanya, ξ(xi + ηi ai ) 6 ξ(xi ). Yaitu, sepanjang ξ(xi ) ≥ As , nilai ukuran hanya bisa menurun pada iterasi-iterasi selanjutnya. Di lain pihak, jika ξ(xi ) ≤ As maka kπP ⊥ xi k 6 As rP ⊥ untuk semua P ⊆ A, dan karenanya kπP ⊥ (xi + ηi ai k 6 kπP ⊥ xi k + ηi kπP ⊥ aik 6 AirP ⊥ + U . kaik 6 AirP ⊥


70 Karena ini berlaku untuk semua P ⊆ A, diperoleh ξ(xi+1 ) ≤ A1. Sebagai rangkuman, ξ(xi+1 ) 6

   Ai

if ξ(xi ) 6 As ,

(4.10)

  ξ(xi ) if ξ(xi ) > As ,

Aplikasi iteratif (4.10) menunjukkan bahwa ξ(xi ) ≤ max(ξ(x0 , A1) untuk semua i. Tetapi perlu dicatat bahwa ξ(x) ≥ kak untuk semua x ∈ Rn , karena bola satuan ξ termuat di dalam bola satuan k·k. Karena itu, (xi )N terbatas pada norm Euclidean yang dibatasi oleh max(ξ(x0 ), A1). Tinggal menentukan kuantitas A1. Dari Lemma 4.3.3. i) diperoleh bahwa ξ(x0 ) ≤ 2 kx0k. Bagian ii) dari hasil yang sama menunjukkan bahwa As ≤ ˆ 3n+2 2 . Terakhir, aplikasi lain dari bagian i) bersama-sama U · maxa∈A kak · κ(A)2 dengan bagian iii) dari Lemma 4.2.1 menghasilkan A1 6 2U max kak . [min kakrank (A) κ(A)2 a ∈A

a ∈A

3n/2

+ 1]

Dengan menggabungkan batas-batas pada ξ(x0 ) dan A1, diperolehlah batas yang dinyatakan. Rumus eksplisit untuk M (A) sebagai fungsi dari data input A menyelesaikan masalah terbuka lama yang diajukan Block dan Levin. Karena M(A) tergantung pada A melalui κ(A), maka batas bisa sangat besar bila A memuat himpunanhimpunan bagian yang mendekati defisien-rank, tetapi tidak. Catat bahwa untuk menghitung κ(A) biasanya harus dinilai jumlah eksponensial determinan. Situasinya jauh lebih sederhana pada kasus di mana A terdiri dari data input, seperti yang ditunjukkan akibat berikut:


71 Akibat 4.5.2. Jika A terdiri dari data rasional dengan total panjang bit D maka

(n+2)D+3n/2

M(A) 6 2 max kx0k , U . max[2 a∈A

D

+2

Bukti. Dengan mengajukan pernyataan seperti dalam bukti Lemma 4.2.1., tidak sulit diketahui bahwa maxa∈A kak ≤ 2D . Dengan menggunakan m ≤ n dan bagian iv) dari Lemma 4.2.1., pernyataan sekarang merupakan akibat langsung dari Teorema 4.5.1.

4.6 Perluasan pada Sistem Nonhomogen Teorema 4.5.1. memberikan informasi tentang perilaku metode relaksasi yang diaplikasikan pada sistem pertidaksamaan-pertidaksamaan linier homogen AT x > 0. Sekarang akan diperluas hasil ini sehingga juga berlaku untuk sistem non homogen AT x > b. Ini bisa dicapai melalui proses homogenisasi standar dan konstruksi ukuran baru dengan cermat.

Teorema 4.6.1 Misalkan A = (a[1], · · · , a[k]) himpunan terurut darik vektor tak nol dari Rn , b ∈ Rn , (ηi )N0 ⊂ [0, U ] dan (ji )N0 ⊆ {1, · · · , k} sedemikian sehingga barisan titik titik yang didefinisikan secara iteratif oleh xi+1 = xi + ηi a[ji ] # " A 0 T . memenuhin syarat xi · a[ji ] ≤ bj untuk semua i ∈ N0 . Misalkan A˜ := −bT 1 Maka untuk semua i, {xik dibatasi oleh    

x0   , 1 . max k˜ ak . [ . min k˜ akrank (A) κ(A)[23(n+1)/2 + 1]  M (A, b) := 2 max 

˜ a ˜∈A ˜

1 a ˜∈A (4.11)


72 Tambahan lagi, jika A dan b terdiri dari data rasional dengan total panjang bit D maka    

x0   , 1 +U . [2(n+3)D+3(n+1)/2 + 2D ]  M (A, b) := 2 max 

1

Bukti. Catat bahwa a[i] · x > bi jika dan hanya jika (˜ a[i] )T

(4.12)

"

x 1

#

> 0

˜ = 1, · · · , k). Tambahan ladi mana a ˜[i] adalah vektor kolom ke-i dari A(i " # x = 1 > 0 selalu dipenuhi, dan ji 6= k + 1 untuk semua i. gi, (˜ a[k+1))T 1 ada korespondensi  satu-satu antara titik-titik dalam Rn dan titik-titik dalam    " #   χ x   ∈ Rn+1 : z = 1 melalui proyeksi ψ : hiperplane H := → x.   z 1

Karena kxk < kΨ−1 xk, cukup dibuktikan bahwa barisan [kΨ−1 xi k]N0 dibatasi # " x i + ˜i+1 = oleh M(A, b). Tetapi catat bahwa Ψ−1 xi+1 = φxi+1 , di mana x 1 " # " # x x → adalah proyeksi Rn+1 pada H sepanjang sumbu ηi ã[ji] dan φ : z 1 koordinat ke(n + 1). Misalkan C bola satuan ukuran yang bersesuaian dengan

˜ dengan konstruksi Lemma 4.4.4., dan misalkan ξ ukuran A˜ := {˜ a/ kãk : a ˜ ∈ A} terkait atas Rn . Misalkan di tetapkan −1 As := max(U, 1) . max k˜ ak . max r{a} , ˜ a ˜ ∈A

˜ a ∈A ˜

A1 := As + max (U, 1) . max k˜ ak . max rP−1⊥ + 2. ˜ a ∈A ˜

P ⊆A˜


73 Pernyataan yang sama dengan pernyataan yang menghasilkan (4.10) menunjukkan bahwa

ξ(˜ xi+1 ) 6

   Ai

if ξ(ψ −1 x1) 6 As ,

  ξ(ψ −1 x1 ) if ξ(ψ −1 x1) > As

(4.13)

Lemma 4.4.4. menunjukkan bahwa #! " xi+1 = ξ(˜ xi+1 − (˜ xi+1 . a ˜[k+1] ) a ˜[k+1] ) 6 ξ(˜ xi+1 ) ξ 0 "

Karena itu, jika ξ

ξ(ψ −1 xi+1 ) = ξ

"

xi+1 0

xi+1 0

#

#!

> As , maka Lemma 4.4.4. mengisyaratkan

+ 1.a ˜[k+1] ) 6 ξ

"

#!

xi+1 0

< ξ(˜ xi+1 ).

(4.14)

"

#! x i+1 Di lain pihak, jika ξ < As , maka pertidaksamaan segitiga de0 ngan norm ξ dan pertidaksamaan ξ ≤ 2 k·k - yang diperoleh berdasarkan Lemma 4.3.3. i) mengisyaratkan bahwa ξ(ψ −1 xi+1 ) 6 ξ

"

xi+1 0

#!

+ξ

"

0 1

#!

< As + 2 < A1

(4.15)

Kombinasi (4.13), (4.14) dan (4.15) sekarang menunjukkan ξ(Ψ−1 xi+1 ) ≤ max(A1, ξ(Ψ−1 xi ))

Dengan mengaplikasikan (4.16) secara iteratif, diperoleh

kxi k < Ψ−1 xi ≤ ξ(Ψ−1 xi ) ≤ max(ξ(Ψ−1 x0 ), A1)


(4.16)

74 Tinggal batas ξ(x0 ) dan A1 , yang bisa dilakukan seperti dalam bukti Teorema 4.5.1., yang menghasilkan (4.11). Terakhir, dilangsungkan seperti dalam bukti dari akibat 4.5.2. , diperolehlah (4.12).


BAB 5 KESIMPULAN

5.1 Kesimpulan Persyaratan utama dalam pernyataan - pernyataan yang didasarkan pada rantai-F dari serangkaian tulisan Effron, Minsky-Papert dan Block dan Levin adalah positivitas murni batas bawah dalam persamaan 0 < L < ηi < U ∀i ∈ N0 . (1.5), sehingga diperlukan pendekatan bebas rantai-F untuk menetapkan hasil dengan asumsi yang lebih umum 0 ≤ ηi < U ∀i ∈ N0 (1.6). Bukti atas Teorema 4.5.1. didasarkan pada pendekatan sedemikian, yang bukan hanya baru secara konseptual dan tidak begitu membatasi tetapi juga lebih mudah dipahami secara geometrik daripada rantai-F. Tambahan lagi, bukti-bukti terdahulu hanya menunjukkan eksistensi batas pada (xi)N . Teorema 4.5.1. pada tulisan ini juga menentukan secara eksplisit batas sebagai fungsi dari data input A dan ini menyelesaikan masalah terbuka lama yang pertama kali diajukan oleh Block dan Levin.


DAFTAR PUSTAKA

A.P. Robertson and W.J Robertson. Topological Vector Spaces. Cambridge University Press, 1973. B. Effron . The perceptron correction procedure in nonseparable situations, 1964. Rome Air Develovement Centre Technical Documentary Report RADCTDR-63-533. De Leone, R., Mangasarian, O.L. : Serial and parallel solution of large scale linear programs by augmented Lagrangian successive over-relaxation. 1980 D.B. Yudin and A.S. Nemirovskii. Informational complexity and efficient methods for the solution of convex extremal problems (in Russian). Ekonomika i mathematicheskie metody, 12 : 357- 369, 1976. G. Cimmino. Calcolo approssimato per soluzioni dei sistemi di equazioni lineari. La Ricerca Scientifica XVI, Series II, Anno IX, 1: 326 333, 1938. G. Hadley. Linear Algebra, University of Chicago & University of Andes, 1981 H.D. Block and S.A. Levin. On the Boundedness of an iterative procedure for solving a system of linear inequalities. Proc. Amer. Math.Soc.26 : 229-235, 1970. H.H. Bauschke and J.M. Borwein. Legendre functions and the method of random bregman projections. Journal of Konveks Analysis, 4:27-67,1997. H.H. Bauschke ,J.M. Borwein, and A. Lewis. The method of a cyclic projection for closed convex sets in Hilbert space.Contemporary Mathematics, 204 : 1 38, 1997. Hoffman, A.J., Mannos, M., Sokolowsky, D., Wiegmann, N. : Computational Experience in Solving Linear Programs. Journal of SIAM 1, 17-33, 1953 J.-B. Hiriart- Urruty and C. Lemarechal. Convex Analysis and minimization algorithms. Grundlehren der mathematicshen Wissenschaften 305,‘ SpringerVerlag, 1991. J.-L. Goffin. The relaxation method for solving system of linear inequalities. Mathematics of Operations Research, 5 : 388-414, 1980. J.-L. Goffin.Variable metric relaxation methods, Part II: The ellipsoid method. Mathematical Programming 30, 147 -162, 1980. L.G. Khachiyan. A polinomial algorithm in linear programming. Dokl. Akad. Nauk SSSR, 244 : 1093 -1096, 1979. ( In Russian, English translation in soviet Math. Dokl, 20 : 191 194, 1979.). M.L. Minsky and S.A.. Papert . Perceptron, MIT Press, 1969.


77 N.Z. Shor. On the structure of algorithms for the numerical solution of optimal planning and design problems ( in Russian). Ph.D thesis , Dissertaion, Cybernetics Institute, Academy of sciences of the Ukranian SSR, Kiev, 1964. N.Z. Shor. Utilization of the operation of space dilatation in the minimization of convex functions ( in Russian ). Kibernetika (Kiev), 1: 6-12, 1970. R. Rosenblatt. Principlesof neurodynamics: Perceptrons and the theory of brain mechanisms, Spartan Books, 1962. S. Agmon. The relaxation method for linear inequalities. Canadian Journal of Mathematics, 6:382-392,1954. T. Motztkin and I.Y. Schonberg. The relaxation method for linear inequalities. Canadian Journal of Mathematics, 6:393-404,1954. Y.Censor and S.A Zenios. Parallel Optimization : Theory, algorithms and application. Oxford University Press, 1997.


TEOREMA KETERBATASAN UNTUK METODE RELAKSASI

Recommend Documents