Unbestimmtes System - Underdetermined system
In der Mathematik wird ein lineares Gleichungssystem oder ein System von Polynomgleichungen als unterbestimmt angesehen, wenn weniger Gleichungen als Unbekannte vorhanden sind (im Gegensatz zu einem überbestimmten System , bei dem es mehr Gleichungen als Unbekannte gibt). Die Terminologie kann mit dem Konzept der Constraint-Zählung erklärt werden . Jedes Unbekannte kann als verfügbarer Freiheitsgrad angesehen werden . Jede in das System eingeführte Gleichung kann als Einschränkung angesehen werden , die einen Freiheitsgrad einschränkt.
Daher tritt der kritische Fall (zwischen überbestimmt und unterbestimmt) auf, wenn die Anzahl der Gleichungen und die Anzahl der freien Variablen gleich sind. Für jede Variable, die einen Freiheitsgrad angibt, gibt es eine entsprechende Einschränkung, die einen Freiheitsgrad entfernt. Der unterbestimmte Fall tritt dagegen auf, wenn das System unterbeschränkt wurde , dh wenn die Unbekannten die Gleichungen übersteigen.
Lösungen von unbestimmten Systemen
Ein unterbestimmtes lineares System hat entweder keine Lösung oder unendlich viele Lösungen.
Zum Beispiel,
ist ein unterbestimmtes System ohne Lösung; Jedes Gleichungssystem ohne Lösung gilt als inkonsistent . Auf der anderen Seite das System
ist konsistent und hat eine Unendlichkeit von Lösungen, wie ( x , y , z ) = (1, –2, 2) , (2, –3, 2) und (3, –4, 2) . Alle diese Lösungen können charakterisiert werden, indem zuerst die erste Gleichung von der zweiten subtrahiert wird, um zu zeigen, dass alle Lösungen z = 2 gehorchen ; Die Verwendung in beiden Gleichungen zeigt, dass jeder Wert von y mit x = −1 - y möglich ist .
Insbesondere ist nach dem Rouché-Capelli-Theorem jedes System linearer Gleichungen (unterbestimmt oder auf andere Weise) inkonsistent, wenn der Rang der erweiterten Matrix größer als der Rang der Koeffizientenmatrix ist . Wenn andererseits die Ränge dieser beiden Matrizen gleich sind, muss das System mindestens eine Lösung haben; Da in einem unterbestimmten System dieser Rang notwendigerweise kleiner als die Anzahl der Unbekannten ist, gibt es tatsächlich eine Unendlichkeit von Lösungen, wobei die allgemeine Lösung k freie Parameter aufweist, wobei k die Differenz zwischen der Anzahl von Variablen und dem Rang ist.
Es gibt Algorithmen , um zu entscheiden, ob ein unterbestimmtes System Lösungen hat, und um gegebenenfalls alle Lösungen als lineare Funktionen von k der Variablen auszudrücken (dasselbe k wie oben). Die einfachste ist die Gaußsche Eliminierung . Weitere Informationen finden Sie unter System linearer Gleichungen .
Homogener Fall
Das homogene (mit allen konstanten Termen gleich Null) unterbestimmte lineare System hat immer nicht triviale Lösungen (zusätzlich zu der trivialen Lösung, bei der alle Unbekannten Null sind). Es gibt unendlich viele solcher Lösungen, die einen Vektorraum bilden , dessen Dimension die Differenz zwischen der Anzahl der Unbekannten und dem Rang der Matrix des Systems ist.
Unterbestimmte Polynomsysteme
Die Haupteigenschaft linearer unterbestimmter Systeme, entweder keine Lösung oder unendlich viele zu haben, erstreckt sich auf folgende Weise auf Systeme von Polynomgleichungen .
Ein System von Polynomgleichungen, das weniger Gleichungen als Unbekannte enthält, soll unterbestimmt sein . Es hat entweder unendlich viele komplexe Lösungen (oder allgemeiner Lösungen in einem algebraisch geschlossenen Feld ) oder ist inkonsistent. Es ist genau dann inkonsistent, wenn 0 = 1 eine lineare Kombination (mit Polynomkoeffizienten) der Gleichungen ist (dies ist Hilberts Nullstellensatz ). Wenn ein unterbestimmtes System von t Gleichungen in n Variablen ( t < n ) Lösungen hat, dann ist die Menge aller komplexen Lösungen eine algebraische Menge von Dimensionen von mindestens n - t . Wenn das unterbestimmte System zufällig ausgewählt wird, ist die Dimension mit der Wahrscheinlichkeit eins gleich n - t .
Unterbestimmte Systeme mit anderen Einschränkungen und Optimierungsproblemen
Im Allgemeinen hat ein unterbestimmtes lineares Gleichungssystem eine unendliche Anzahl von Lösungen, falls vorhanden. Bei Optimierungsproblemen , die linearen Gleichheitsbeschränkungen unterliegen, ist jedoch nur eine der Lösungen relevant, nämlich diejenige, die den höchsten oder niedrigsten Wert einer Zielfunktion ergibt .
Einige Probleme geben an, dass eine oder mehrere der Variablen nur ganzzahlige Werte annehmen dürfen. Eine Ganzzahlbeschränkung führt zu Problemen bei der Ganzzahlprogrammierung und bei diophantinischen Gleichungen , die möglicherweise nur eine begrenzte Anzahl von Lösungen haben.
Eine andere Art von Einschränkung, die in der Codierungstheorie auftritt , insbesondere bei Fehlerkorrekturcodes und der Signalverarbeitung (z. B. komprimierte Erfassung ), besteht in einer Obergrenze für die Anzahl der Variablen, die von Null abweichen können. Bei Fehlerkorrekturcodes entspricht diese Grenze der maximalen Anzahl von Fehlern, die gleichzeitig korrigiert werden können.