Belirsiz sistem - Underdetermined system

İçinde matematik, bir doğrusal denklem sistemi veya a polinom denklem sistemi düşünülmektedir az belirlenmiş bilinmeyenlerden daha az denklem varsa^[1] (bir üst belirlenmiş sistem bilinmeyenlerden daha fazla denklemin olduğu yerde). Terminoloji kavramı kullanılarak açıklanabilir kısıtlama sayımı. Her biri Bilinmeyen mevcut olarak görülebilir özgürlük derecesi. Sisteme dahil edilen her denklem bir kısıtlama bu bir dereceye kadar özgürlüğü kısıtlar.

Bu nedenle, kritik durum (üst belirlenmiş ve az belirlenmiş arasında) denklemlerin sayısı ve serbest değişkenlerin sayısı eşit olduğunda ortaya çıkar. Bir derece özgürlük veren her değişken için, belirli bir serbestlik derecesini ortadan kaldıran karşılık gelen bir kısıt vardır. az belirlenmiş durum ise, tersine, sistem yetersiz kısıtlandığında, yani bilinmeyenlerin sayısı denklemlerden fazla olduğunda ortaya çıkar.

Belirsiz sistemlerin çözümleri

Belirsiz bir doğrusal sistemin ya çözümü yoktur ya da sonsuz sayıda çözümü vardır.

Örneğin,

{displaystyle {egin {hizalı} x + y + z & = 1 x + y + z & = 0son {hizalı}}}

çözümsüz bir sistemdir; Çözümü olmayan herhangi bir denklem sisteminin olduğu söylenir tutarsız. Öte yandan, sistem

{displaystyle {egin {hizalı} x + y + z & = 1 x + y + 2z & = 3 uç {hizalı}}}

tutarlıdır ve sonsuz sayıda çözüme sahiptir, örneğin (x, y, z) = (1, −2, 2), (2, −3, 2) ve (3, −4, 2). Bu çözümlerin tümü, tüm çözümlerin uyduğunu göstermek için ilk denklemin ikinciden çıkarılmasıyla karakterize edilebilir. z= 2; bunu her iki denklemde kullanmak, herhangi bir değerin y ile mümkündür x=–1–y.

Daha spesifik olarak, Rouché-Capelli teoremi, herhangi bir doğrusal denklem sistemi (az belirlenmiş veya başka türlü), eğer sıra of artırılmış matris sırasından daha büyük katsayı matrisi. Öte yandan, bu iki matrisin sıralamaları eşitse, sistemin en az bir çözümü olmalıdır; Belirsiz bir sistemde bu sıra bilinmeyenlerin sayısından zorunlu olarak daha az olduğundan, gerçekten de sonsuz sayıda çözüm vardır ve genel çözüm k ücretsiz parametreler nerede k değişkenlerin sayısı ile sıra arasındaki farktır.

Var algoritmalar az belirlenmiş bir sistemin çözümleri olup olmadığına karar vermek ve eğer varsa, tüm çözümleri doğrusal fonksiyonları olarak ifade etmek k değişkenlerin (aynı k yukarıdaki gibi). En basit olanı Gauss elimine etme. Görmek Doğrusal denklem sistemi daha fazla ayrıntı için.

Homojen durum

Homojen (tüm sabit terimler sıfıra eşittir), eksik belirlenmiş doğrusal sistem her zaman önemsiz olmayan çözümlere sahiptir (tüm bilinmeyenlerin sıfır olduğu önemsiz çözüme ek olarak). Bir oluşturan bu tür çözümlerin sonsuzluğu vardır. vektör alanı, kimin boyutu bilinmeyenlerin sayısı ile bilinmeyenlerin sayısı arasındaki farktır sıra Sistemin matrisinin.

Belirsiz polinom sistemler

Doğrusal olarak belirlenmemiş sistemlerin temel özelliği, çözümü olmayan ya da sonsuz sayıda olması, polinom denklem sistemleri Aşağıdaki şekilde.

Bilinmeyenlerden daha az denklem içeren bir polinom denklem sistemi olduğu söylenir. az belirlenmiş. Ya sonsuz sayıda karmaşık çözüme (ya da daha genel olarak, bir cebirsel olarak kapalı alan ) veya tutarsız. Tutarsızdır ancak ve ancak 0 = 1 denklemlerin doğrusal bir kombinasyonudur (polinom katsayıları ile) (bu Hilbert's Nullstellensatz ). Az belirlenmiş bir sistem t denklemler n değişkenler (t < n) çözümlere sahipse, tüm karmaşık çözümler kümesi bir cebirsel küme nın-nin boyut en azından n - t. Belirsiz sistem rastgele seçilirse, boyut şuna eşittir: n - t olasılıkla bir.

Diğer kısıtlamalara sahip ve optimizasyon problemlerinde eksik belirlenmiş sistemler

Genel olarak, eksik belirlenmiş bir doğrusal denklem sistemi, varsa sonsuz sayıda çözüme sahiptir. Ancak optimizasyon sorunları Doğrusal eşitlik kısıtlamalarına tabi olan, çözümlerden yalnızca biri ilgilidir, yani en yüksek veya en düşük değerini veren çözüm amaç fonksiyonu.

Bazı problemler, bir veya daha fazla değişkenin tamsayı değerleri alacak şekilde kısıtlandığını belirtir. Bir tamsayı kısıtlaması, Tamsayılı programlama ve Diofant denklemleri sadece sınırlı sayıda çözümü olabilen sorunlar.

Başka bir tür kısıtlama, kodlama teorisi özellikle hata düzeltme kodları ve sinyal işleme (Örneğin sıkıştırılmış algılama ), sıfırdan farklı olabilen değişken sayısı üzerinde bir üst sınır içerir. Hata düzeltme kodlarında bu sınır, aynı anda düzeltilebilen maksimum hata sayısına karşılık gelir.

Ayrıca bakınız

Referanslar

^ Biswa Nath Datta (4 Şubat 2010). Sayısal Doğrusal Cebir ve Uygulamalar, İkinci Baskı. SIAM. s. 263–. ISBN 978-0-89871-685-6.

[Datta2010-1] Biswa Nath Datta (4 Şubat 2010). Sayısal Doğrusal Cebir ve Uygulamalar, İkinci Baskı. SIAM. s. 263–. ISBN 978-0-89871-685-6.

[1]