6 Lineer Dönüşümler ve Konveks Kümeler
Bu hafta iki iş yapıyoruz. Önce lineer dönüşümleri tanımlayıp her birinin bir matris olduğunu ve sürekli olduğunu gösteriyoruz; bu süreklilik, hiperdüzlemlerin ve yarı uzayların kapalılığını daha bu hafta içinde kullanmamızı sağlayacak. Ardından dersin asıl nesnesini tanımlıyoruz: konveks kümeler. Afin kümelerden tek farkları, doğrunun tamamı yerine yalnızca doğru parçasını istemeleridir.
6.1 Lineer Dönüşümler
Afin ve konveks kümelerin yapısını koruyan dönüşümlerin en basiti lineer dönüşümlerdir; afin dönüşümleri, konveksliğin korunmasını incelediğimiz gelecek haftaya bırakıyoruz.
Tanım 6.1 (Lineer Dönüşüm) \(T : \mathbb{R}^n \to \mathbb{R}^m\) olmak üzere
her \(x, y \in \mathbb{R}^n\) için \(T(x + y) = T(x) + T(y)\),
her \(x \in \mathbb{R}^n\), \(\lambda \in \mathbb{R}\) için \(T(\lambda x) = \lambda T(x)\)
koşullarını — veya eşdeğer olarak her \(x, y \in \mathbb{R}^n\), \(\alpha, \beta \in \mathbb{R}\) için \(T(\alpha x + \beta y) = \alpha T(x) + \beta T(y)\) koşulunu — sağlayan \(T\) fonksiyonuna \(\mathbb{R}^n\)’den \(\mathbb{R}^m\)’e bir lineer dönüşüm denir. Eğer bir lineer dönüşüm \(\mathbb{R}^n\)’den \(\mathbb{R}\)’ye tanımlanmış ise özel olarak bu dönüşüm lineer fonksiyonel olarak adlandırılır.
Teorem 6.1 (Her Lineer Dönüşüm Bir Matristir) \(T : \mathbb{R}^n \to \mathbb{R}^m\) bir lineer dönüşüm olsun. Bu durumda \(T(x) = Ax\) gerçekleyen bir \(A_{m \times n}\) matrisi vardır.
İspat
\(x \in \mathbb{R}^n\) olsun. \(e_1, e_2, \dots, e_n\) vektörleri \(\mathbb{R}^n\)’in standart tabanı olmak üzere bir \(x \in \mathbb{R}^n\) vektörü standart taban cinsinden
\[x = [x_1, x_2, \dots, x_n]^T = x_1 e_1 + x_2 e_2 + \dots + x_n e_n\]
şeklinde yazılır. Dolayısıyla lineerlik ile
\[T(x) = T(x_1 e_1 + \dots + x_n e_n) = x_1 T(e_1) + x_2 T(e_2) + \dots + x_n T(e_n) \tag{1}\]
geçerlidir. Bu yazılışta \(T(x)\) vektörünü belirleyebilmek için \(T(e_1), \dots, T(e_n)\) vektörlerini bilmek yeterlidir. \(j = 1, \dots, n\) için \(T(e_j) \in \mathbb{R}^m\) vektörünün \(i\). bileşenini \(a_{ij}\) ile gösterirsek \((1)\) nedeniyle
\[T(x) = x_1 \begin{bmatrix} a_{11} \\ \vdots \\ a_{m1} \end{bmatrix} + \dots + x_n \begin{bmatrix} a_{1n} \\ \vdots \\ a_{mn} \end{bmatrix} = \begin{bmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mn} \end{bmatrix} \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix} = Ax\]
olur; buradaki \(A\) matrisi aranan matristir.
\(\blacksquare\)
\(T : \mathbb{R}^n \to \mathbb{R}\) lineer fonksiyoneli için \(T(x) = \langle a, x \rangle\) gerçekleyen bir \(a \in \mathbb{R}^n\) vardır. Kısacası her lineer fonksiyonel, uygun bir \(a \in \mathbb{R}^n\) yardımıyla \(\langle a, x \rangle\) biçiminde ifade edilebilir.
Lemma 6.1 (Lineer Dönüşümler Süreklidir) Herhangi bir \(T : \mathbb{R}^n \to \mathbb{R}^m\) lineer dönüşümü süreklidir.
İspat
\(\{e_1, \dots, e_n\}\) kümesi \(\mathbb{R}^n\)’in standart tabanı ve \(v_i := T(e_i)\), \(i = 1, \dots, n\) olsun. \(x = (x_1, \dots, x_n)\) olmak üzere herhangi bir \(x \in \mathbb{R}^n\) için
\[T(x) = T\left( \sum_{i=1}^{n} x_i e_i \right) = \sum_{i=1}^{n} x_i T(e_i) = \sum_{i=1}^{n} x_i v_i\]
eşitlikleri geçerlidir. Bu durumda üçgen eşitsizliği ve Cauchy-Schwarz eşitsizliği yardımıyla
\[\|T(x)\| = \left\| \sum_{i=1}^{n} x_i v_i \right\| \le \sum_{i=1}^{n} |x_i| \cdot \|v_i\| \le \sqrt{\sum_{i=1}^{n} |x_i|^2} \cdot \underbrace{\sqrt{\sum_{i=1}^{n} \|v_i\|^2}}_{=: \, M > 0} = M \|x\|\]
kısacası, \(M > 0\) sabit bir sayı olmak üzere her \(x \in \mathbb{R}^n\) için \(\|T(x)\| \le M\|x\|\) eşitsizliği geçerlidir. Böylece her \(p, k \in \mathbb{R}^n\) için
\[\|T(p) - T(k)\| = \|T(p - k)\| \le M\|p - k\|\]
eşitsizliği gerçeklenir; bu ise \(T\) dönüşümünün bir Lipschitz fonksiyonu, dolayısıyla da düzgün sürekli ve sonuçta sürekli olması demektir.
\(\blacksquare\)
Özel olarak \(\mathbb{R}^n\)’de tanımlı her lineer fonksiyonel süreklidir; bu, birazdan hiperdüzlemlerin kapalı, yarı uzayların ise kapalı veya açık olduğunu söylerken kullanacağımız gözlemdir.
6.2 Konveks Kümeler
Tanım 6.2 (Konveks Kombinasyon ve Doğru Parçası) \(x_1, \dots, x_m \in \mathbb{R}^n\), \(\lambda_1, \dots, \lambda_m \ge 0\) ve \(\lambda_1 + \dots + \lambda_m = 1\) olmak üzere \(\lambda_1 x_1 + \dots + \lambda_m x_m\) toplamına \(x_1, \dots, x_m\) noktalarının bir konveks kombinasyonu denir.
Özel olarak \(x\) ve \(y\) gibi iki noktanın bir konveks kombinasyonunu \(0 \le \lambda \le 1\) olmak üzere \((1 - \lambda)x + \lambda y\) yazılışı ile ifade etmek mümkündür. \(x, y \in \mathbb{R}^n\) olmak üzere
\[\{(1 - \lambda)x + \lambda y : 0 \le \lambda \le 1\}\]
kümesine \(x\) ve \(y\) noktalarını birleştiren doğru parçası denir.
Konveks kombinasyonun afin kombinasyondan (Tanım 4.3) tek farkı, katsayıların negatif olmamasıdır.
Tanım 6.3 (Yıldız Biçimli Küme) Sabit bir \(x_0 \in C \subseteq \mathbb{R}^n\) olmak üzere, eğer her \(y \in C\) ve her \(0 \le \lambda \le 1\) için \((1 - \lambda)x_0 + \lambda y \in C\) gerçekleniyor ise \(C\) kümesi \(x_0\) noktasına göre yıldız biçimli bir kümedir denir.
Tanım 6.4 (Konveks Küme) \(C \subseteq \mathbb{R}^n\) olmak üzere, eğer
\[\forall x, y \in C,\ 0 \le \lambda \le 1 \ \text{ için } \ (1 - \lambda)x + \lambda y \in C\]
içermesi gerçekleniyor ise \(C\) kümesine bir konveks küme denir.
Yukarıdaki tanıma eşdeğer olarak, konveks bir küme aşağıdaki ifadelerden herhangi biri ile de tanımlanabilir:
- herhangi iki noktasını birleştiren doğru parçasını içeren küme,
- herhangi iki elemanının konveks kombinasyonlarını içeren küme,
- her bir elemanına göre yıldız biçimli olan küme.
Son ifade, konvekslik ile yıldız biçimlilik arasındaki farkı tam olarak yakalar: yıldız biçimlilik bir noktadan bütün kümenin görülmesini, konvekslik ise her noktadan bütün kümenin görülmesini ister.
Teorem 6.2 (Konveks Kümelerin Kesişimi) \(I\) herhangi bir indis kümesi olmak üzere her \(i \in I\) için \(C_i \subseteq \mathbb{R}^n\) kümeleri konveks ise \(\bigcap_{i \in I} C_i\) kesişim kümesi de konvekstir.
İspat
\(x_1, x_2 \in \bigcap_{i \in I} C_i\) ve \(0 \le \lambda \le 1\) olsun. Bu durumda her \(i \in I\) için \(x_1 \in C_i\) ve \(x_2 \in C_i\) geçerlidir. Her \(C_i\) konveks olduğundan \((1 - \lambda)x_1 + \lambda x_2 \in C_i\) ve dolayısıyla \((1 - \lambda)x_1 + \lambda x_2 \in \bigcap_{i \in I} C_i\) gerçeklenir.
\(\blacksquare\)
Bu basit sonuç, bu bölümün en çok kullanılan aracıdır: konveks olduğunu bildiğimiz kümelerin kesişimi olarak yazabildiğimiz her küme konvekstir.
Konveks Küme Örnekleri
Örnek 6.1 (Temel Konveks Kümeler) Aşağıdaki kümelerin konveks olduğunu gösteriniz: (1) \(\mathbb{R}^n\), \(\varnothing\) ve tek nokta kümeleri; (2) kapalı birim yuvar \(\overline{B(0,1)}\); (3) hiperdüzlemler; (4) yarı uzaylar; (5) polihedral kümeler.
Çözüm
1. \(\mathbb{R}^n\) ve tek nokta kümesi için koşul aşikâr biçimde sağlanır; \(\varnothing\) için de sağlanır, çünkü kontrol edilecek nokta çifti yoktur.
2. \(x_1, x_2 \in \overline{B(0,1)}\) ve \(0 \le \lambda \le 1\) olmak üzere üçgen eşitsizliği ve normun homojenliği ile
\[\|(1 - \lambda)x_1 + \lambda x_2\| \le |1 - \lambda| \cdot \|x_1\| + |\lambda| \cdot \|x_2\| \le (1 - \lambda) + \lambda = 1,\]
yani \((1 - \lambda)x_1 + \lambda x_2 \in \overline{B(0,1)}\) geçerlidir.
3. Teorem 5.1 nedeniyle herhangi bir hiperdüzlem \(H = \{x : \langle a, x \rangle = b\}\) ile gösterilebilir. \(x_1, x_2 \in H\) ve \(0 \le \lambda \le 1\) için
\[\langle a, (1 - \lambda)x_1 + \lambda x_2 \rangle = (1 - \lambda)\langle a, x_1 \rangle + \lambda \langle a, x_2 \rangle = (1 - \lambda)b + \lambda b = b\]
olacağından \((1 - \lambda)x_1 + \lambda x_2 \in H\) elde edilir.
4. Yarı uzaylar için aynı hesap, eşitlik yerine eşitsizlikle tekrarlanır: \(\langle a, x_1 \rangle \le b\) ve \(\langle a, x_2 \rangle \le b\) ise ağırlıklı ortalama da \(b\)’yi aşmaz. Kesin eşitsizlik için de aynısı geçerlidir.
5. Polihedral küme, sonlu sayıda kapalı yarı uzayın kesişimidir; her biri konveks olduğundan Teorem 6.2 gereği kesişim de konvekstir. Ayrıca lineer fonksiyoneller sürekli olduğundan (Lemma 6.1) her \(\{x : \langle a_i, x \rangle \le b_i\}\) kümesi kapalıdır ve kapalı kümelerin kesişimi kapalı olduğundan polihedral kümeler kapalıdır.
Tanım 6.5 (Yarı Uzaylar) Bir \(H = \{x \in \mathbb{R}^n : \langle a, x \rangle = b\}\) hiperdüzlemi \(\mathbb{R}^n\) uzayını
\[H^{\le} = \{x : \langle a, x \rangle \le b\} \quad \text{ya da} \quad H^{<} = \{x : \langle a, x \rangle < b\}\]
ve
\[H^{\ge} = \{x : \langle a, x \rangle \ge b\} \quad \text{ya da} \quad H^{>} = \{x : \langle a, x \rangle > b\}\]
olmak üzere iki yarı uzaya ayırır. \(H^{\le}\) ve \(H^{\ge}\) uzaylarına \(H\) hiperdüzleminin belirlediği kapalı yarı uzaylar, \(H^{<}\) ve \(H^{>}\) uzaylarına da açık yarı uzaylar denir.
Tanım 6.6 (Polihedral Küme) \(A_{m \times n}\) bir matris, \(b \in \mathbb{R}^m\), \(x \in \mathbb{R}^n\) olmak üzere \(Ax \le b\) şeklinde verilen \(n\) bilinmeyenli \(m\) tane sonlu eşitsizlik sisteminin çözüm kümesi olan
\[P = \{x \in \mathbb{R}^n : Ax \le b\} = \{x \in \mathbb{R}^n : \langle a_i, x \rangle \le b_i,\ i = 1, \dots, m\}\]
kümesine bir polihedral küme veya bir çok yüzlü küme denir.
Her hiperdüzlem aynı zamanda bir polihedral kümedir: \(\langle a, x \rangle = b\) koşulu, \(\langle a, x \rangle \le b\) ve \(\langle -a, x \rangle \le -b\) eşitsizlik çiftine denktir.
Tanım 6.7 (Konveks Kümenin Boyutu) Bir \(C \subseteq \mathbb{R}^n\) konveks kümesinin boyutu, \(C\) kümesinin afin örtüsü olan \(\operatorname{aff}(C)\) afin kümesinin paralel olduğu lineer alt uzayın boyutudur ve \(\dim(C)\) ile gösterilir.
Konveks kümenin tanımı ve ilk örnekleri elimizde. Bir sonraki hafta bu özelliğin hangi işlemler altında korunduğunu sistematik olarak inceleyeceğiz.