Unterbest. Gleichungssystem < Gleichungssysteme < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo zusammen,
ich erhalte aus einer Funktion [mm]D[/mm], die ich nach allen [mm] \alpha_{i} [/mm] differenziere, ein solches Gleichungssystem:
[mm]
\bruch{\partial D}{\partial\alpha_{i}}=1-\summe_{j=1}^{n}\alpha_{j}z_{ij}-\lambda y{i}=0
[/mm]
[mm]
\gdw
[/mm]
[mm]
\summe_{j=1}^{n}\alpha_{j}z_{ij}=1-\lambda y{i}:=b{i}.
[/mm]
Alle [mm] z_{ij} [/mm] und [mm] y_{i} [/mm] sind bekannt, aber kein [mm] \alpha_{j} [/mm] und auch nicht [mm] \lambda. [/mm] Damit ist das Gleichungssystem
[mm]
Z \alpha = b,
[/mm]
[mm]
Z=\pmat{ z_{11} & z_{12} & ... & z_{1n} \\ z_{21} & z_{22} & ... & z_{2n} \\ ... \\ z_{n1} & z_{n2} & ... & z_{nn} }, Z=Z^{T}, \alpha = \vektor{\alpha_{1} \\ \alpha_{2} \\ ... \\ \alpha_{n}}, b = \vektor{1-\lambda y_{1} \\ 1-\lambda y_{2} \\ ... \\ 1-\lambda y_{n}}, y_{i}=\begin{cases} -1 \\ 1\end{cases} \forall i
[/mm]
unterbestimmt und nicht lösbar. Allerdings habe ich eine weitere Information, nämlich [mm] \summe_{i=1}^{n} \alpha_{i}y_{i}=0. [/mm] Damit ist das Gleichungssystem nun lösbar ([mm]n+1[/mm] Gleichungen mit [mm]n+1[/mm] Unbekannten). Für [mm]n=2[/mm] kriege ich das auch mit den Methoden aus der Schule (umformen und einsetzen) hin, ich muss aber einen Algorithmus implementieren, der das für beliebige [mm]n[/mm] löst.
So ohne Weiteres komme ich mit der Cramer'schen Regel nicht weiter, weil ich nicht weiß, wie ich meine Zusatzinformation in das Gleichungssystem einbauen soll. Jemand 'ne Idee?
Vielen Dank im Voraus und Gruß
BAGZZlash
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:35 Do 20.11.2008 | | Autor: | zetamy |
Hallo,
du kannst die zusätzliche Gleichung in Matrix reichschreiben und alle Unbekannten in einem Vektor zusammenfassen, sprich das Lambda in den Vektor Alpha schreiben:
[mm]\pmat{ z_{11} & z_{12} & ... & z_{1n} & y_1 \\ z_{21} & z_{22} & ... & z_{2n} & y_2 \\ ... \\ z_{n1} & z_{n2} & ... & z_{nn} & y_n \\ y_1 & y_2 & ... & y_n & 0 } \cdot \vektor{\alpha_{1} \\ \alpha_{2} \\ ... \\ \alpha_{n} \\ \lambda} = \vektor{1 \\ 1 \\ ... \\ 1 \\ 0}[/mm]
Übrigens: ein unterbestimmtes System kann auch eine Lösung haben!!
Gruß, zetamy
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:27 Di 25.11.2008 | | Autor: | BAGZZlash |
Hi!
Super, vielen Dank! Hab' schon ein paar Tage nicht mehr hier 'reingeschaut. Umso mehr freue ich mich über diese elegante Lösung, tausend Dank! 
Gruß
BAGZZlash
|
|
|
| |
|
Hi!
Nochmal danke für die Antwort. Nun will ich doch nochmal eine bescheidene Frage dazu stellen: Ist es möglich, das Ganze noch ein Bißchen zu erweitern, wenn ich vorgeben will, dass [mm]\alpha_{i} \ge 0[/mm] [mm]\forall i[/mm]?
Danke und Gruß
BAGZZlash
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:35 Do 27.11.2008 | | Autor: | zetamy |
Hallo,
theoretisch ist das machbar, aber praktisch nicht sinnvoll, weil du für jedes [mm] $a_i$ [/mm] eine weitere Zeile in die Matrix einfügen musst und für [mm] $a_i$ [/mm] eine sogenannte Slackvariable einführen musst (und damit auch jeweils eine weitere Spalte in der Matrix), für die du dann die Nicht-Positivität fordern musst (um aus dem [mm] $\geq$ [/mm] ein $=$ zu machen).
Du hättest dann also eine (n+1+n) x (n+1+n) Matrix mit n nicht-positiven Slackvariablen. Das macht die Sache nur komplizierter.
Ich hoffe, ich konnte helfen.
Gruß, zetamy
> Nochmal danke für die Antwort. Nun will ich doch nochmal
> eine bescheidene Frage dazu stellen: Ist es möglich, das
> Ganze noch ein Bißchen zu erweitern, wenn ich vorgeben
> will, dass [mm]\alpha_{i} \ge 0[/mm] [mm]\forall i[/mm]?
>
> Danke und Gruß
> BAGZZlash
|
|
|
| |
|
Hi!
Super, danke für Deine Antwort. Könnest Du kurz beschreiben, wie sowas konkret gemacht wird? Vielleicht mit einer (ursprünglich) 2x2-, dann also 5x5-Matrix?
Gruß
BAGZZlash
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:32 Fr 28.11.2008 | | Autor: | zetamy |
Betrachten wir das System
[mm] $A\cdot [/mm] x = b$
[mm] $x\geq0$
[/mm]
wobei $A [mm] \in\IR^{2\times2},\ x\in\IR^2$. [/mm] Für [mm] $x=(x_1,x_2)\geq0$ [/mm] kann man schreiben:
[mm] $\pmat{ 1 & 0 \\ 0 & 1}\cdot \vektor{x_1 \\ x_2} \geq [/mm] 0$.
Damit aus dem [mm] $\geq$ [/mm] ein $=$ wird, kannst du Schlupfvariablen (Slackvariablen) [mm] $y_1, y_2 \geq [/mm] 0$ einführen:
[mm] $\pmat{ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1}\cdot \vektor{x_1 \\ x_2 \\ y_1 \\ y_2} [/mm] = 0$ mit [mm] $y\geq [/mm] 0$
Also insgesamt:
[mm] $\pmat{ a_{11} & a_{12} & 0 & 0 \\ a_{21} & a_{22} & 0 & 0 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1}\cdot \vektor{x_1 \\ x_2 \\ y_1 \\ y_2} [/mm] = [mm] \vektor{b_1 \\ b_2 \\ 0 \\ 0}$
[/mm]
[mm] $y\geq [/mm] 0$
Damit hast du die Bedingung "nicht-negativ" an die x in der Matrix untergebracht, aber musst für die y die Nicht-Negativität fordern - hast also (in der Regel) nichts gewonnen.
Gruß, zetamy
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:48 Di 02.12.2008 | | Autor: | BAGZZlash |
Hi!
Okay, alles klar. Vielen Dank für Deine Mühe und Geduld. Dann muss ich erstmal weiter überlegen.
Nochmal danke
BAGZZlash
|
|
|
|
