LİNEER DENKLEM SİSTEMLERİ

Birçok bilgisayar destekli problem çözümü lineer denklem sistemlerinin çözümünü içermektedir ve bu çözümler için geliştirilen yöntemler de bilgisayar biliminin yapı taşlarından birini oluşturmaktadır. Ax = b şeklinde ve A’nın m x n’ lik bir matris olduğu bir bilgisayar destekli çözüm sistemi şu üç şekilde sınıflandırılabilir:

• Doğrudan çözüm yöntemleri
• İterasyona dayalı çözüm yöntemleri
• Doğrudan ve iterasyona dayalı yöntemlerin bir arada kullanıldığı karma yöntemler.

Çözümleri oluştururken dikkate alınması gereken hususlar ise şöyle özetlenebilir:

• Çözümün varlığı
• Çözümlerin tekliği
• Çözümün sapmalara olan duyarlılığı
• Hesaplama yönteminin tutarlılığı
• Hesaplama yönteminin işlemsel karmaşıklığı

Aşağıda genel biçimiyle ifade edilen bir lineer denklem sistemini ele alalım:

olmak üzere

Doğrudan teknikler, belli sayıda aşamadan geçmek ve sadece yuvarlama hatalarına maruz kalmak suretiyle cevabı bulmamızı sağlayan yöntemlerdir.

Yukarıda verilen lineer denklem sistemini basite indirgemede üç değişik işlem uygulayabiliriz:

1. E_i denklemi farklı bir λ sabiti ile çarpılarak, elde edilen denklem E_i nin yerine kullanılabilir. Bu işlemi şöyle ifade edebiliriz:
2. E_j denkleminin herhangi bir λ sabitiyle çarpılıp E_i ye eklenmesi suretiyle elde edilen denklem E_i nin yerine kullanılabilir. Bu işlem de şöyle ifade edilebilir:
3. E_i ve E_j denklemlerinin yerleri değiştirilebilir. Bu işlem ise şöyle ifade edilir:

Yukarıda sıralanan işlemler yardımıyla lineer bir sistem, bize aynı sonuçları verecek fakat daha kolay çözülebilir başka bir lineer sisteme dönüştürülebilir.

ÖRNEK 1: Aşağıda verilen denklem sistemini çözelim:

Önce sırasıyla

işlemlerini yaparak E₁ denklemini kullanmak suretiyle E₂ , E₃ ve E₄ ten x₁ bilinmeyenini yok edelim. Sonuçta elde edilen denklem sistemi şöyle olacaktır:

Burada yeni elde edilen denklemler kolaylık olması amacıyla eski adları ile adlandırılmışlardır. Bu yeni sistemde ise yine sırasıyla

işlemlerini yaparak ve E₂ denklemini kullanmak suretiyle E₃ ve E₄ ten x₂ bilinmeyenini yok edelim. Sonuçta elde edilen denklem sistemi şöyle olacaktır:

Yukarıda elde edilen denklem sistemi artık üst üçgensel (veya indirgenmiş) form olup, tersine yerine koyma yöntemiyle kolayca çözülebilir.

E₄ ten başlayarak sırasıyla geri gidilecek olursa x₄ = 1 , x₃ = 0 , x₂ = 2 , x₁ = -1 olarak elde edilecektir.

Örnek 1 ‘deki hesaplamaları yaparken her seferinde tüm değişkenleri yazmamız gerekmez. Yaptığımız değişiklikler sadece değişkenlerin katsayıları ve eşitliğin sağ tarafındaki değerler üzerinde olduğundan lineer sistemler çoğunlukla bu denklem sistemine ait tüm gerekli bilgileri çok daha derli toplu bir biçimde bize veren bir matris ile ifade edilirler. Genel haliyle

şeklindeki bir lineer denklem sistemini n x (n + 1) lik bir matris ile gösterebiliriz. Öncelikle A ve b yi oluştururuz;

daha sonra da bu matrisleri birleştirerek genişletilmiş matrisi elde ederiz;

Örnek 1 deki işlemleri matris notasyonunda tekrar edecek olursak ilk genişletilmiş matrisimizi şöyle elde ederiz;

daha sonraki iki işlemimizi de aynen yapacak olursak;

Buradaki son matris tekrar karşılık gelen lineer denklem sistemine dönüştürülerek x₄ = 1 , x₃ = 0 , x₂ = 2 , x₁ = -1 sonuçları elde edilebilir. Bu işlemlerde uygulanan yöntemin adı tersine yerine koyma ile yapılan Gauss eliminasyonu yöntemidir.

Gauss eliminasyonunu aşağıda verilen, lineer denklem sisteminin genel ifadesine de aynı şekilde uygulayabiliriz;

Önce, genişletilmiş Ã matrisini oluşturalım:

Burada A katsayılar matrisini göstermektedir. (n+1)’inci sütundaki girdiler ise b değerlerini vermektedir.( a_i,n+1 = b_i her i = 1, 2,...,n için.)

dönüşümündeki işlemler yapılarak ilk satır dışındaki satırların x₁ ‘li terime karşılık gelen katsayıları yok edilir. Her ne kadar 2, 3, ..., n numaralı satırlardaki girdiler değişmiş te olsa notasyon kolaylığı bakımından i satırı ve j sütunundaki girdileri şimdilik yine a_ij olarak adlandırmaya devam edeceğiz. Bunu da gözönünde bulundurarak ve yine

işlemlerini gerçekleştiririz. Bu işlemler bizim için i ‘ninci satırın altında kalan her satırdaki x_i’lerin yok etmemizi (yani katsayılarını sıfırlamamızı) sağlar. Buradan elde edilen matris şu formdadır:

Yukarıdaki matrisin birinci satır elemanları hariç diğer elemanlar ilk à matrisindekilerle aynı olmak zorunda değildirler. Bu matris (4) orijinal sistemindeki ile aynı çözüm kümesine sahip bir lineer sistemi temsil etmektedir. Bu yeni sistem de üst üçgensel yapıda olduğundan artık tersine yerine koyma metodu ile çözülebilecektir.

n’inci denklem bize şu çözümü verecektir:

Buradan bulduğumuz x_n değerini kullanarak (n – 1)’inci denklemi çözecek olursak:

ve yine aynı süreci devam ettirecek olursak her bir değeri için şöyle bir sonuç elde ederiz:

Gauss eliminasyonu, daha karmaşık gözüken, ancak daha net bir şekilde de ifade edilebilir; Ã⁽¹⁾ , (5)’te verilen à ‘ya denk ve Ã^(k) nın elemanları her k = 2,3,...,n için a_ij^(k) olmak üzere genişletilmiş Ã⁽¹⁾, Ã⁽²⁾,..., Ã⁽ⁿ⁾ matrislerinden meydana gelen bir dizi oluştururuz, öyle ki;

Böylece şu matrisi elde etmiş oluruz:

Elde edilen bu matris E_k, E_k+1 , ..., E_n denklemlerinden x_{k -1} in yok edilmiş halini göstermektedir.

elemanlarından birinin bile sıfır olması halinde belirtilen prosedür çalışmayacaktır, çünkü bu durumda ya

işlemi yapılamayacak ya da tersine yerine koyma işlemi gerçekleştirilemeyecektir .

DİKKAT! : Bu işlemlerin yapılamaması sistemin çözümü olmadığı anlamına gelmekten ziyade, sistemin çözümünde kullanılan tekniğin gözden geçirilmesi gerektiğine işaret eder.

Ayrıca elemanları pivot elemanlar olarak adlandırılırlar.

ÖRNEK 2: Aşağıda verilen denklem sistemini çözelim:

Genişletilmiş matrisi şöyle yazabiliriz:

işlemleri yapılarak ikinci matris elde edilir:

Burada a₂₂⁽²⁾ pivot elemanı sıfır olduğundan işlemleri bu şekliyle sürdürmemiz mümkün değildir. a₃₂⁽²⁾ ve a₄₂⁽²⁾ elemanları arasından ilk sıfırdan farklı elemanı

ararız. a₃₂⁽²⁾≠ 0 olduğundan işlemini yaparak yeni matrisi elde ederiz:

Son olarak işlemlerini de yaparak üst üçgensel matrisi elde etmiş oluruz:

Buradan da tersine yerine koyma ile x₄ = 2, x₃ = 2, x₂ = 3, x₁ = -7 değerlerini buluruz.

Örnek-2 bize k = 1, 2, ..., n-1 için a_kk^(k) = 0 olduğunda ne yapılabileceğini göstermektedir:

Ã^(k-1) in k nıncı sütununda, ilk sıfırdan farklı elemanı bulana dek, k nıncı satırdan n inci satıra kadar tararız ve,

Eğer bu şekilde sıfırdan farklı bir p bulamaz isek lineer sistemin tek bir çözümü olmadığını söyler ve dururuz. Aksi takdirde daha önce yapmakta olduğumuz işlemleri aynı düzende sürdürürüz. Son olarak eğer a_nn⁽ⁿ⁾ = 0 ise yine sistemin tek çözümü olmadığı söylenebilir ve prosedür durur. Aşağıda tüm bu işlemlere ait algoritma verilmiştir:

ALGORİTMA 1:

ALIŞTIRMALAR:

1. Aşağıdaki lineer denklem sistemlerini çözüm varsa Gauss Eliminasyonu ile çözün ve satır takası gerekip gerekmediğini belirtin.

2. Aşağıdaki lineer sistem verilmiş olsun:

1. α ‘nın hangi değerleri için sistemin çözümü yoktur?
2. α ‘nın hangi değerleri için sistemin sonsuz sayıda çözümü vardır?
3. Belli bir α için tek çözümün var olduğunu kabul ederek bu çözümü bulun.

3. Aşağıda verilen işlemlerin ait oldukları lineer sistemin çözüm kümesini değiştirmeyeceklerini gösterin.