Yazan : Şadi Evren ŞEKER

Bu yazının amacı, matrislerin determinantını (masfuf muheddedad, matrix determinant) nasıl hesaplandığını anlatmaktır.

Konuya basit matrisler ile başlayalım. Örneğin 2×2 boyutundaki bir matris için:

basitçe det(A) = ad – bc şeklinde hesaplanabilir buradaki hesap aşağıda gösterilen iki ok yönünden sağı göstereni + ve solu göstereni – alarak hatırlanabilir:

Şekilde görüldüğü üzere mavi okun üzerinden geçtiği elemanlar ad ve kırmızı okun üzerinden geçtiği elemanlar cb olmaktadır ve determinant ad-cb şeklinde hesaplanmaktadır.

Determinant hesaplanırken matrisin köşeli parantezleri yani [] sembolleri yerine düz parantezler yani || sembolleri kullanılır.

olarak yazılabilir.

3×3 boyutundaki bir matrisin determinantı yine benzer şekilde oklar kullanılarak hesaplanabilir.

Genel olarak herhangi boyuttaki bir matrisin determinantı ise aşağıdaki formül ile hesaplanabilir:

Yukarıdaki gösterimde, kısaca bir matrisin nxn boyutunda olduğu kabul edilmiş ve öncelikle y sembolü kullanılmıştır. Buradaki y sembolü yer değiştirmeyi (permutation) ifade etmektedir. Yani y_i demek, i.nci değiştirme (permütasyon) demektir. Örnek olarak elemanlarımız 1,2,3 ise ve yerdeğiştirme dizilimi aşağıdaki şekildeyse:

1,2,3

2,3,1

3,1,2

2,1,3

1,3,2

3,2,1

Bu dizilimdeki her elemana bir numara verildiğinde yi gösterimindeki i değerine göre bir gösterim ifade ediliyor demektir. Örneğin i=5 için yukarıdaki gösterimlerden 5. sıradakini anlayabiliriz ki bu da 1,3,2 gösterimidir.

Denklemde yer alan diğer bir gösterim ise yön() fonksiyonudur. Basitçe +1 veya -1 döndüren bir fonksiyondur ve aşağıdaki şekilde ifade edilebilir:

Kısacası aldığı parametrenin teklik/çiftliğine göre + veya – döndüren fonksiyondur.

Çarpım sembolü ile ifade edilen terim ise yukarıdaki 2×2 veya 3×3 boyutlu matrislerde gösterilen ve çarpılarak daha sonra toplanan veya çıkarılan her bir terim için kullanılmıştır.

Örnek olarak yukarıdaki dizilimleri ele alacak olursak aşağıdaki şekilde 3×3 boyutundaki bir matirisin determinantını hesaplayabiliriz:

Yukarıdaki yaklaşımda, ilk satırda bulunan sayılar kapatılıp kalan alandaki matrislerin determinantı ile çarpılmıştır. Ayrıca çarpma işlemi sırasında bir artı bir de eksi yönde ilerlenmiştir.

Örneğin 5 çarpanı için:

5 sayısının bulunduğu satır ve sütun kapatılıp kalan satır ve sütunlardaki matris alınmıştır. Benzer şekilde 3 sayısı için:

3 sayısının bulunduğu satır ve sütundaki sayılar kapatılır ve geri kalan sayılardan oluşan matris okunur.

Bu şekilde alt matrisler elde edilir ve bu alt matrisler ise kapanan sayı sabit çarpıma (scalar multiplication) tabi tutulur.

Neticede çıkan sonuç toplanır. Yani yukarıdaki örnekten devam edilecek olursa

5( 4 . 4 – 9 . 6 ) – 3( 2 . 4 – 9 . 3 ) + 7 ( 2 . 6 – 4 . 3)

olur Bu işlemin sonucu da

-133

olarak bulunur.

Yukarıdaki bu genel hesaplama formülüne göre kodlaması aşağıdaki şekilde yapılabilir:

Yukarıdaki kodun ekran çıktısı aşğaıdaki şekildedir:

Kabaca kodu açıklayacak olursak. Determinant fonksiyonu bir integer matris parametre olarak almaktadır. Koddaki ilk 2 if (4. ve 8. satırlardaki) özel matris determinantı için kullanılır. Yani matrisin boyutunun 1×1 veya 2×2 olması durumları içindir. Bu hesaplar doğrudan yukarıdaki yazıda anlatıldığı şekliyle yapılır. Yani 1×1 için matrisin yegane elemanı döndürülürken 2×2 için köşegen ve ters köşegendeki sayılar çarpılıp çıkarılarak döndürülür.

Şayet matrisin boyutu 2×2’den daha fazla ise (örneğin 3×3 veya 4×4 gibi) bu durumda matris, yukarıdaki örnek çözümünde olduğu gibi küçük matrislere bölünür ve her eleman için artı ve eksi şekilde sayısal değerler denkleme dahil edilerek hesaplanır.

Kodun 15. satırından başlayan döngü ilk satırı ve ilgili sütunu kapatmakta ve kalan küçük matrisi 25. satırdaki işlem ile özyineli (recursive) olarak tekrar denkleme sokmaktadır. Ayrıca -1 sayısının üstü alınarak yön fonksiyonu kodlanmıştır (-1 sayısının çift üstlerinin + ve tek üstlerinin – olduğunu hatırlayınız).

Kodu indirmek için tıklayınız.

Yorumlar

  1. yusuf

    sa hocam biz aşağıdaki programı yazmaya çalıştık ama hata veriyo ve craşş oluyo nerede hata yaptığımızı bulamadık projenin konusunu versek yardımcı olabilirmisiniz şimdiden teşekkür ederimPROJE KONUSU:
    Bir şehirde, programa girdi olarak verilecek arzu edilen maksimum yürüyüş mesafesi bilgisi gözönünde
    bulundurularak en fazla sayıda alışveriş merkezine yakınlığı bulunan bölgenin tespit edilmesi
    gerekmektedir. Şehirde bulunan alışveriş merkezlerinin konumları da girdi olarak verilecektir.
    Şehirdeki sokaklar ızgara (grid) şeklinde organize edilmiştir. x-y koordinat sisteminde (a,b) ve (c,d)
    noktalarıyla temsil edilen iki kavşak noktası arasındaki yürüyüş mesafesi |a – c| + |b – d| formülüyle
    hesaplanır.
    Aşağıdaki şekil 4×4 boyutlarındaki bir şehre ait sokakları ve sokakların kesişim noktalarındaki
    kavşakları göstermektedir.
    PROGRAM GİRDİSİ:
    Program girdisi bir metin dosyasından okunacaktır. Dosya içerisinde birden fazla test durumu
    bulunabilir. Her bir test durumu, ayrı bir şehri, bu şehirdeki alışveriş merkezlerinin konumunu ve arzu
    edilen maksimum yürüyüş mesafesini temsil etmektedir. Her bir test durumunun ilk satırı dx, dy, n, ve
    q olmak üzere 4 adet tamsayı içermektedir. dx ve dy (1 ≤ dx, dy ≤ 1000) şehrin boyutlarını, n
    (0 ≤ n ≤ 5· 105) şehirdeki alışveriş merkezlerinin toplam sayısını belirtmektedir. q (1 ≤ q ≤ 20) ise
    toplam sorgu sayısını (arzu edilen maksimum yürüyüş mesafeleri sayısı) temsil etmektedir. Takip eden
    n adet satırın her biri xi ve yi (1 ≤ xi ≤ dx+1, 1 ≤ yi ≤ dy+1) olmak üzere i. alışveriş merkezinin
    konumunu belirtmektedir. Alışveriş merkezlerinin yalnızca kavşak noktalarında konumlandığı ve her
    bir kavşakta en fazla 1 adet alışveriş merkezinin bulunabileceği varsayılmaktadır. Takip eden q adet
    satırın her biri ise bir alışveriş merkezine ulaşmak için arzu edilen maksimum yürüyüş mesafesini (m, 0
    ≤ m ≤ 106) göstermektedir. Girdi dosyasının son satırı 4 adet 0 rakamı içermektedir.
    PROGRAM ÇIKTISI:
    Programın çıktısı bir metin dosyasına kaydedilmelidir. Giriş dosyasında, verilen her bir test durumu
    için çıkış dosyasında test numarası belirtilmeli ve test durumundaki her bir sorguya karşılık gelen bir
    satır üretilmelidir. Üretilecek bu satırlar, sorguda belirtilen maksimum yürüyüş mesafesi (m) dikkate
    alındığında erişilebilecek maksimum alışveriş merkezi sayısını ve bunun için en uygun kavşak
    noktasının koordinatlarını içermelidir. Örneğin, aşağıdaki tabloda gösterilen örnek, maksimum yürüyüş
    mesafesi 1 olarak alındığında maksimum 3 adet alışveriş merkezine (3,4) koordinatlı kavşaktan
    erişilebileceğini göstermektedir. Maksimum yürüyüş mesafesi 2 olarak seçildiğinde (2,2) konumundan
    maksimum 4 alışveriş merkezine erişilebilir. Birden fazla optimal kavşak bulunduğu durumlarda bu
    kavşaklardan en güneydeki (minimum pozitif y koordinatına sahip olan) tercih edilir. En güney
    pozisyonunda birden fazla kavşak var ise bu durumda en batıdaki (minimum pozitif x koordinatına
    sahip olan) kavşak optimal çözüm olarak seçilir.
    Örnek Girdi Örnek Girdiye ait Çıktı
    4 4 5 3
    1 1
    1 2
    3 3
    4 4
    2 4
    124
    0 0 0 0
    Case 1:
    3 (3,4)
    4 (2,2)
    5 (3,1)

  2. Şadi Evren ŞEKER Article Author

    6×7 boyutlarındaki bir matrisin (masfuf) tersi yoktur. Kısaca matrisin determinantının hesaplanabilmesi için tersi alınabilir matris olması gerekir ve tersi alınabilir matrislerin tamamı kare matrisler (square matrix) için tanımlıdır. Sizin sorunuzdaki kare olmayan (non-square) matrisler için bir birim matris (Identity matrix) bulunmaz (birim matris diyagonu 1 diğer elemanları sıfır olan kare matristir) dolayısıyla tersi alınmaz ve dolayısıyla determinantı yoktur.

  3. asude

    hocam sitenizdeki “permütasyon algoritması” konu baslığı altında permütasyonu sadece zar için almışsınız ben n*n matriste nasıl kullanabilirim ? ( matrisin boyutunu ve değerlerini kullanıcı belirleyecek )

  4. Şadi Evren ŞEKER Article Author

    Bütün diziler tek boyutlu diziye indirgenebilir (zaten indirgenir de, nitekim RAM(hafıza) tek boyutludur). O anlatımda sanırım 1’den 6’ya kadar olan semboller tek bir dizi gibi kabul ediliyordu. Yapmanız gereken dizinizi (kaç boyutlu olursa olsun nxn ise iki boyutludur) tek boyutlu olarak düşünmek. ve aynı algoritmayı uygulamak.

  5. yusuf

    hocam ben bunu c# olarak visual studio da yapmayı denedim ama determinant (gecici) den sonra
    determinant diye public açtığımda orası hata veriyo hocam bide ben public Form1()
    {
    InitializeComponent();
    }
    buranın üstünde sizin gibi en üste public i public determinant(int[,] matris); bu şekilde hocam hata vermeye başladı ve bana şunu dedi
    Error CS0501 ‘Form1.determinant(int[*,*])’ must declare a body because it is not marked abstract, extern, or partial determinantmatris hocam bunu nasıl düzeltirim

Süha için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir