 \(\begingroup\)
Beweglichkeit eines Streichholzgraphen bestimmen 3 plus 4 ist 7, plus 5 ist 12, 8 minus 12 geht nicht, also 1 borgen, 18-12 ist 6. So haben meine Großeltern immer den Einkauf vorgerechnet, extra ausführlich, damit ich etwas lerne dabei. Es war auch ein besonderer Moment, wenn dann die geborgte 1 in der Zehnerspalte eingetragen und dort im nächsten Durchlauf mit dazugezählt wurde. Also wenn es nicht weitergeht, 1 borgen und dazuzählen. Mit dieser Methode möchte ich nun ein Gleichungssystem lösen und darauf aufbauend die Beweglichkeit eines Streichholzgraphen bestimmen. Verwendet werden die Begriffe inverse, reguläre, singuläre, transponierte Matrix, Lösungsmenge von homogenen und inhomogenen Gleichungssystemen, Basis, linear abhängige Zeilen und Spalten, Determinante sowie aus der Mechanik der Begriff Freiheitsgrad.
Es geht los mit dem singulären Gleichungssystem (7,1,13,-11;18,12,6,18;21,15,4,26;9,6,3,9) (x_1;x_2;x_3;x_4) = (1;8;3;4). Invertieren der Koeffizientenmatrix geht nicht, wie WolframAlpha: [[7,1,13,-11], [18,12,6,18], [21,15,4,26], [9,6,3,9 ]]^-1 bestätigt, also borge ich eine 1 und addiere sie irgendwo mit in die Matrix (7,1,13,-11;18,12,6+\big\1\normal\ ,18;21,15,4,26;9,6,3,9)^(-1)=(7,0,25, -191\/3;-15, -2,-54,425\/3;0,\big\1\normal\ ,0,-2;3,1, 11, -30) Fertig.
Gut, das ist erst mal keine große Kunst, vor dem Lösen die Aufgabe ändern. Doch unter bestimmten Voraussetzungen kann man tatsächlich einen Zusammenhang zur Lösung der Ausgangsaufgabe herstellen. Die Voraussetzungen sind wichtig, deshalb beginne ich gleich mit der ersten, die anderen werden noch nicht gebraucht. In der invertierten Matrix, an der transponierten Position der addierten 1, also wo Zeilen- Spaltenindex vertauscht sind, muss die geborgte 1 wieder erscheinen (.,.,.,.;.,.,a_23+\big\ 1\normal,.;.,.,.,.;.,.,.,.)^(-1) = (.,.,.,.;.,.,.,.;.,\big\ 1\normal,.,.;.,.,.,.) Das ist das unverwechselbare Zeichen dafür, dass die Ausgangsmatrix wirklich singulär war. Sonst würden die weiteren Überlegungen nicht stimmen. Der Beweis ist nicht schwer, für eine invertierbare Matrix (a_11 ,a_12 , a_13 ,a_14 ;a_21 ,a_22 , a_23 ,a_24 ;a_31 ,a_32 , a_33 ,a_34 ;a_41 ,a_42 , a_43 ,a_44)^(-1) = (b_11 ,b_12 , b_13 ,b_14 ;b_21 ,b_22 , b_23 ,b_24 ;b_31 ,b_32 , b_33 ,b_34 ;b_41 ,b_42 , b_43 ,b_44) gibt der Kehrwert von bji an, wie weit aij von dem Zahlenwert entfernt ist, an dem die Matrix A singulär wird. Das ist der bekannten Effekt, dass bei fast singulären Matrizen die Inverse immer so große Koeffizienten hat. Denn (a_11 ,a_12 , a_13 ,a_14 ;a_21 ,a_22 , a_23-\big\ 1\normal\ /b_32 ,a_24 ;a_31 ,a_32 , a_33 ,a_34 ;a_41 ,a_42 , a_43 ,a_44) (b_11 ,b_12 , b_13 ,b_14 ;b_21 ,b_22 , b_23 ,b_24 ;b_31 ,b_32 , b_33 ,b_34 ;b_41 ,b_42 , b_43 ,b_44) = (1,0,0,0;-b_31/b_32 , 0, b_33/b_32 , b_34/b_32 ; 0,0,1,0;0,0,0,1) und wegen det(X)det(Y)=det(XY) folgt aus det(Y)≠0 und det(XY)=0 die Behauptung det(X)=0. bji=1 ist nachträglich eine nochmalige Bestätigung, dass die Ausgangsmatrix vor dem Addieren der 1 wirklich singulär war, und es kann weitergehen.
Die Nichtnullelemente in der Zeile von bji=1 sind die Linearfaktoren dafür, welche Zeilen der Ausgangsmatrix linear abhängig sind. (.,.,.,.;.,.,.,.;.,\big\ 1\normal,.,-2;.,.,.,.) bedeutet \big\ 1\normal*(18,12,6,18) - 2*(9,6,3,9) = 0 Die inverse Matrix war (7,0,25, -191\/3;-15, -2,-54,425\/3;0,\big\ 1\normal,0,-2;3,1, 11, -30) und die Ausgangsmatrix (7,1,13,-11;18,12,6,18;21,15,4,26;9,6,3,9) . Analog sind die Nichtnullelemente der Spalte von bji=1 die Linearfaktoren für linear abhängige Spalten der Ausgangsmatrix. (.,.,.,.;.,-2,.,.;.,\big\ 1\normal,.,.;.,1,.,.) bedeutet (-2)*(1;12;15;6) + \big\ 1\normal*(13;6;4;3) + 1*(-11;18;26;9) = 0 Die gesamte Spalte (.,0,.,.;.,-2,.,.;.,\big\ 1\normal,.,.;.,1,.,.) ist Basisvektor für die Lösungsmenge L des homogenen Gleichungssystems L=menge(x|x=\lambda*(0;-2;1;1), \lambda\el\ \IR) und mit (7,1,13,-11;18,12,6+\big\1\normal\ ,18;21,15,4,26;9,6,3,9)^(-1) * (1;8;3;4) = (7,0,25, -191\/3;-15, -2,-54,425\/3;0,1,0,-2;3,1, 11, -30) * (1;8;3;4) = ( -518\/3 ; 1157\/3 ; 0 ; -76) erhält man schließlich noch eine partikuläre Lösung der inhomogenen Gleichung. Allerdings ist hier unbedingt die Probe erforderlich, um festzustellen, dass die rechte Seite die Lösbarkeitsbedingung erfüllt. Sonst wäre das Gleichungssystem unlösbar. (7,1,13,-11;18,12,6,18;21,15,4,26;9,6,3,9)( -518\/3 ; 1157\/3 ; 0 ; -76) = (1;8;3;4) stimmt. Die Beweise für diese Aussagen sind alle ähnlich zum ersten Beweis.
Für die weiteren Aussagen gilt das mit den Beweisen nicht mehr. Sie sind teilweise nur Vermutungen, die ich für richtig halte, weil sie bei deren Anwendung das gewünschte Ergebnis liefern (und sich ab und zu ändern, wenn nicht das richtige Ergebnis herauskommt).
Es kann passieren, dass nach dem Addieren der 1 die Matrix immer noch nicht invertierbar ist. Das ist ein Zeichen dafür, dass man den Bereich der linear abhängigen Zeilen und Spalten nicht getroffen hat oder dass es noch weitere Basiselemente gibt. Dann muss man an weiteren Matrixpositionen eine 1 addieren, entweder zufällig gewählt oder man weiß aus dem Zusammenhang heraus die richtige Position oder man modifiziert die bekannten Lösungsverfahren. Solange, bis eine invertierbare Matrix herauskommt. Dann aber noch nicht gleich die Lösung ablesen, vorher erst die Voraussetzungen überprüfen. Die erste Voraussetzung war, dass zu jedem aij+1 das zugehörige bji gleich 1 ist. Wenn nicht, kann man die zugehörige Additionen aij+1 rückgängig machen und die Matrix bleibt trotzdem invertierbar. Neu ist die zweite Voraussetzung: Zu je zwei zu agh+1 und akl+1 gehörende bhg=1 und blk=1 müssen bhk=0 und blg=0 sein. Bei bhk≠0 können die beiden agh+1 und akl+1 durch ein einziges akh+1 ersetzt werden und bei blg≠0 durch ein einziges agl+1. Wenn beide bhk≠0 und blg≠0, dann können agh+1 und akl+1 ohne Ersatz rückgängig gemacht werden. Schließlich noch die dritte Voraussetzung: Nach jeder dieser Korrekturen müssen die ersten beiden Voraussetzungen komplett neu für alle aij+1 nachgeprüft werden. Das sieht alles kompliziert aus, die Prüfung auf gleich oder ungleich Null ist aber schnell erledigt. Am Ende ergeben die verbleibenden bji=1 ein solches Muster (,\vdots,,\vdots,,\vdots,;\cdots,0,\cdots,0,\cdots,\big\1\normal\ ,\cdots;,\vdots,,\vdots,,\vdots,;\cdots,\big\1\normal\ ,\cdots,0,\cdots,0,\cdots;,\vdots,,\vdots,,\vdots,;\cdots,0,\cdots,\big\1\normal\ ,\cdots,0,\cdots;,\vdots,,\vdots,,\vdots,), also eine Teilmatrix bestehend aus je einem bji=1 in jeder Zeile und Spalte und sonst nur Nullen. Dann kann wieder wie anfangs die Lösung abgelesen werden. Jede komplette Spalte zu einem bji=1 ist ein Basiselement der Lösungsmenge und die Nichtnullelemente in jeder zu bji=1 gehörenden Zeile/Spalte sind die Faktoren für die entsprechenden linear abhängigen Zeilen/Spalten der Ausgangsmatrix.
Nun möchte ich mit dieser Methode die Beweglichkeit eines Streichholzgraphen bestimmen. Wie ich die Gleichungssystem aufstelle, siehe im Thread Streichholzgraphen 4-regulär und 4/n-regulär (n>4) und 2/5 den Beitrag No.251. Dann fülle ich die Koeffizientenmatrix mit Nullspalten und Nullzeilen zu einer quadratischen Matrix auf. Dann addiere ich beginnend bei a11 von links oben nach rechts unten zu jedem aii eine 1, wenn die Teilmatrix von a11 bis aii (führende Hauptminoren) noch nicht invertierbar ist, und überprüfe die drei Voraussetzungen. Dadurch ändern sich manche der aii+1 in andere akl+1 oder entfallen wieder. Die unterstrichenen 0 und 0 geben solche Positionen an, wo ich ursprünglich 0+1 und 0+1 eingesetzt hatte, diese nach dem Überprüfen der Voraussetzungen aber nicht geblieben und auch nicht entfallen sind, sondern aus je zwei ein einziges aij+1 geworden ist, verschoben innerhalb der gleichen Zeile/Spalte. Damit möchte ich wenigstens etwas verdeutlichen, wie diese Ersetzungen mit der Veränderung der Beweglichkeit einhergehen. Genauere Gedanken habe ich mir darüber nicht gemacht. Die neu hinzukommenden Kante und deren Koordinatendifferenzen sind gleichfarbig hervorgehoben. Ganz rechts in der Tabelle bedeuten Spaltenbezeichnung A = Anzahl der aij+1, F = Anzahl der Freiheitsgrade des Graphen. | Graph | Gleichungssystem | A | F |
|---|
| | 3 | 3 | | | 4 | 4 | | | 5 | 5 | | | 4 | 4 | | | 3 | 3 | | | 3 | 3 | Es ist absehbar, auf welche Vermutung das hinauslaufen soll. Die Anzahl der aij+1 stimmt mit der Anzahl der Freiheitsgrade überein (Ausnahme siehe nächsten Absatz) und wenn man davon die 3 Freiheitsgrade für den gesamten Graph abzieht, bleibt ein Ergebnis >0 übrig, wenn der Graph in sich beweglich ist und 0 bei einem starren Graph. Ausnahme: Wenn der Graph mehr als doppelt so viele Kanten wie Punkte enthält (zum Beispiel diese 4-regulären Streichholzgraphen mit 60 Knoten und 121 Kanten), dann müssen Nullzeilen an die Koeffizientenmatrix angefügt werden, um sie quadratisch zu machen. In dem Fall zähle ich die aij+1 aus diesen angefügten Nullzeilen nicht mit. Für den ehemalig zweitkleinsten 4-regulären Streichholzgraph mit 60 Knoten und 120 Kanten im Artikel Ein 4-regulärer Streichholzgraph mit 114 Kanten unter Punkt "3." erhalte ich als Ergebnis 4 Freiheitsgrade. Abzüglich der 3 Freiheitsgrade für den gesamten Graph bleibt 1 Freiheitsgrad übrig, der Graph ist in sich einfach beweglich. Die Eingabe des Graphen erfolgte mit Streichholzgraph_zum_Artikel.htm und die Berechnung mit dem extra (GAP-)Programm. Nachfolgend einige Bewegungsphasen, in der Mitte der Originalgraph:
Einige Details zur Ausführung der Berechnung: Wegen der ständig wechselnden aij+1 muss man die Matrix nicht jedes Mal neu invertieren, die Woodbury-Matrix-Identität bietet eine Fülle an Korrekturmöglichkeiten der invertierten Matrix. Auch das Auffinden der benötigten aij+1 muss man nicht dem Zufall überlassen, das kann systematisch während des Gauß-Algorithmus (Version zur Matrixinvertierung) erfolgen. Wenn man auf eine zu invertierende 0 trifft, einfach mit 0+1 weiterrechnen und ein aij+1 merken. Am Schluss dann wieder anhand der drei Voraussetzungen auf die notwendigen aij+1 korrigieren. Es ist auch von Vorteil, die Berechnung ganzzahlig zu halten, siehe hier, dann muss man aber statt der 1 den aktuellen Nenner addieren. Ich bevorzuge den Invertierungsschritt aus (Wikipedia) Pivotverfahren#Eine_direkte_Umsetzung und führe bereits nach jedem solchen Invertierungsschritt die Korrektur der aij+1 aus. Auch die ganzzahlige Rechnung ist gleich mit dabei, ich habe mir daraufhin eine entsprechende Variante für die Woodbury-Matrix-Identität gebastelt, hat A x = b die Lösung \delta\ x = B b , dann hat (A+ST) x = b die Lösung p x = (pB-BSXTB)\/\delta b , X,p aus (\delta\.I+TBS)^(-1) = X\/p, I=Einheitsmatrix , mit A,B\el\ \IZ^(n\cross\ n); b\el \IZ^n ; \delta,p\el\IZ; S\el\ \IZ^(n\cross\ m) ; T\el\ \IZ^(m\cross\ n) ; I,X\el\ \IZ^(m\cross\ m). Ich habe keinen Beweis, dass die Division durch \delta wirklich ganzzahlig aufgeht. Doch das ist nicht weiter schlimm, da ich das GAP-Programm verwende, welches automatisch mit rationalen Zahlen weiterrechnen würde, was aber noch nie aufgetreten ist.
Anmerkungen zur Genauigkeit der Eingabegrößen xj-xi: Man muss dafür sorgen, dass Gleichungen wie (xj-xi)=(xj-xk)+(xk-xi) erhalten bleiben, sonst geht die lineare Abhängigkeit verloren. Ich hatte zur Vereinfachung die (xj-xi) auf weniger Stellen gerundet, doch da gilt diese Gleichheit nicht mehr. Deshalb erst die xi, xj, xk runden und dann xj-xi bilden. Doch auch beim Runden der xi geht in manchen Fällen lineare Abhängigkeit und damit Beweglichkeit verloren. Als Beispiel folgender Graph, in dem die drei oberen Dreiecke beweglich sind, wenn die drei unteren Dreiecke festgehalten werden. Die vertikalen y-Koordinaten der Knotenpunkte sind Vielfache der Höhe h im gleichseitigen Dreieck, also irrational. Beim Runden von h, 2h, 3h bleibt das Verhältnis 1:2:3 nicht erhalten, so dass sich in jeder "Etage" unterschiedliche Kantenlängen ergeben, dargestellt durch unterschiedliche Farben Dieser Graph ist noch genauso beweglich. Liegt der Graph anfangs um 60° gedreht vor, dann lautet nach dem Runden der y-Koordinaten das Ergebnis völlig korrekt "unbeweglich". Da habe ich für die Bestimmung der Beweglichkeit vor dem Runden nur den Hinweis, dass die inverse Matrix sehr große Koeffizienten hat, in der Größenordnung vom Kehrwert der Abweichung, welche durch das Runden der y-Koordinate verursacht wurde.
Schluss. Ich bedanke mich bei Slash fürs Mitlesen und natürlich für die Aufgabe. Es macht viel Spaß, sowas auszurechnen. Viele Grüße, Stefan
\(\endgroup\)
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
