Pivot eleman

Pivot ya da pivot element algoritmaların bir matris, dizi veya bir tür içinden, bir hesaplamada (ör. Gauss eliminasyonu, Hızlı Sıralama, Simpleks algoritması vb.) kullanılmak üzere seçtiği ilk elemandır. Matris algoritmaları için pivotun en azından sıfırdan farklı olması istenir ve genellikle sıfırdan uzak bir değer seçilir. Bu durumda algoritmanın düzgün çalışması için uygun pivot seçiminde satır veya sütunlar aralarında yer değiştirtilebilir.

Hızlı Sıralamada pivot eleman bölümleme için seçilen sınır değeridir. Algoritma tüm elemanları pivota göre özyineleme yaparak sıralar.

Pivot seçimi algoritmaya daha fazla işlem ekler ve hesaplama maliyetini artırır. Eklenen bu işlemler bazı durumlarda algoritmanın çalışması için olmazsa olmazdır. Diğer durumlarda da eklemeler, ulaşılan sonuçlarda sağladığı için değerlidir.

Pivot seçimi gerektiren sistem örnekleri

Gauss eliminasyonunda algoritma sıfırdan farklı bir pivot elemana ihtiyaç duyar. Pivotun sıfıra eşit olmasını engellemek için satır ve sütunlarda yer değişimi gerekli hale gelebilir. Örneğin aşağıdaki sistem eliminasyonun yapılabilmesi için 2. ve 3. satırların birbiriyle değiştirmesini gerektirmektedir.

${\displaystyle \left[{\begin{array}{ccc|c}1&-1&2&8\\0&0&-1&-11\\0&2&-1&-3\end{array}}\right]}$

Değişimden sonra oluşan sistem eliminasyon algoritmasının çalışmasına ve ters alma işleminin sonuca ulaşmasına olanak tanır. Satır değişiminden sonra sistem aşağıdaki hali alır.

${\displaystyle \left[{\begin{array}{ccc|c}1&-1&2&8\\0&2&-1&-3\\0&0&-1&-11\end{array}}\right]}$

Bunlara ek olarak, Gauss eliminasyonunda genellikle pivot elemanının mutlak değerinin büyük olması istenir. Bu artırır. Örneğin aşağıdaki sisteme Gauss eliminasyonu ve oranlama uygulandığında büyük yuvarlama hataları alınmaktadır.

${\displaystyle \left[{\begin{array}{cc|c}0,00300&59,14&59,17\\5,291&-6,130&46,78\\\end{array}}\right]}$

Bu sistemin tam çözümleri x₁ = 10,00 and x₂ = 1,000'dir; fakat dört basamakla eliminasyon ve geri oranlama yapıldığında a₁₁'in küçük olması yuvarlama hatalarını ortaya çıkarır. Uygun pivot seçimi yapılmadan algoritmanın ulaştığı sonuçlar x₁ ≈ 9873,3 and x₂ ≈ 4'tür. Bu durumda iki satır yer değiştirilerek a₂₁'in pivot pozisyonuna gelmesi tercih edilir.

${\displaystyle \left[{\begin{array}{cc|c}5,291&-6,130&46,78\\0,00300&59,14&59,17\\\end{array}}\right].}$

Değişim sonucu oluşan sistem ele alındığında, dört değerle algoritma uygulandığında doğru sonuçlar olan x₁ = 10,00 ve x₂ = 1,000 elde edilmektedir.

Kısmi ve tam pivot seçimi

Kısmi pivot seçiminde algoritma matrisin sütunundaki en yüksek mutlak değere sahip girişi pivot eleman olarak belirler. Bu tür seçim yuvarlama hatalarının kabul edilebilir düzeye düşürülmesinde genellikle yeterli olur. Ancak bazı sistemler ve algoritmalarda gerekli değerlere ulaşabilmek için tam pivot seçimi (ya da maksimum pivot seçimi) kullanılmak zorunda kalınabilir. Bu seçimde ise matrisin tüm elemanları değerlendirilir, satır ve sütunlar gerekirse değiştirilerek en yüksek doğruluğu verecek değer pivot olarak seçilmeye çalışılır. Çoğu zaman sonuçlarda kararlılığı sağlamak tam pivot seçimine gerek yoktur. Tam seçim daha fazla işlem gerektirdiğinden her durumda kullanılması gereken bir strateji değildir.

Ölçekli pivot seçimi

Kısmi seçimin bir türüne ölçekli pivot seçimi denir. Bu yaklaşımda algoritma, girişler içinde satırdaki diğer elemanlara kıyasla en büyük elemanı pivot olarak seçer. Bu metot girişlerin büyüklükleri arasında yuvarlama hatalarına yol açacak büyük farklar varsa tercih edilir. Ölçekli seçim aşağıdaki gibi satır girişleri arasında ciddi farklar olan sistemlerde kullanılmalıdır. Örnekte 30 girişi 5,291'den büyüktür ama iki satırın yer değiştirmesi istenir. Çünkü 5,291 değeri ölçekli seçime uygun şekilde satırdaki diğer elemanlara göre daha büyük farklar yaratır. Satırlar değiştirilmeden seçim yapılırsa önceki sistem gibi yuvarlama hataları görülecektir.

${\displaystyle \left[{\begin{array}{cc|c}30&591400&591700\\5,291&-6,130&46,78\\\end{array}}\right]}$

Kaynakça

Bu makale PlanetMath'deki Pivoting maddesinden lisansıyla faydalanmaktadır.

• R. L. Burden, J. D. Faires, Numerical Analysis, 8th edition, Thomson Brooks/Cole, 2005.
• G. H. Golub, C. F. Loan, Matrix Computations, 3rd edition, Johns Hopkins, 1996. .
• Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling and Dominique de Werra (Ed.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming: Series B. 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997). Amsterdam: North-Holland Publishing Co. ss. 369—395. doi:10.1016/S0025-5610(97)00062-2. MR 1464775. Postscript preprint. KB1 bakım: Editörler parametresini kullanan ()
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research. 46–47 (Degeneracy in optimization problems). Springer Netherlands. ss. 203-233. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. PDF file of (1991) preprint.