Content

9. Lineare Gleichungssysteme und Gauß-Algorithmus in:

Michael Merz, Mario V. Wüthrich

Mathematik für Wirtschaftswissenschaftler, page 229 - 242

Die Einführung mit vielen ökonomischen Beispielen

1. Edition 2012, ISBN print: 978-3-8006-4482-7, ISBN online: 978-3-8006-4483-4, https://doi.org/10.15358/9783800644834_229

Bibliographic information
Kapitel9 Lineare Gleichungssysteme und Gauß-Algorithmus Kapitel 9 Lineare Gleichungssysteme und Gauß-Algorithmus 9.1 Eigenschaften linearer Gleichungssysteme Lineare Gleichungssysteme wurden bereits in Abschnitt 7.4 eingeführt und in Abschnitt 8.4 wurde der enge Zusammenhang zwischen linearen Gleichungssystemen und Matrizen aufgezeigt. In diesem Abschnitt werden nun mit Hilfe der in Kapitel 8 ermittelten Erkenntnisse über Matrizen allgemeine lineare Gleichungssysteme bezüglich ihrer Eigenschaften untersucht. Dabei wird insbesondere analysiert, wann lineare Gleichungssysteme eine Lösung besitzen und unter welchen Voraussetzungen diese Lösung eindeutig ist. Der Lösungsbereich L eines homogenen linearen Gleichungssystems A x = 0 der Ordnung m× n stimmt offensichtlich mit dem Kern der Koeffizientenmatrix A, also dem linearen Unterraum Kern(A) = {x ∈ Rn : A x = 0} , überein (vgl. (8.30)). Der Lösungsbereich L eines homogenen linearen Gleichungssystems ist somit ebenfalls ein linearer Unterraum des Rn. Daraus folgt zum einen, dass der Nullvektor 0 ∈ Rn eine triviale Lösung des homogenen linearen Gleichungssystems A x = 0 ist, und zum anderen, dass der Lösungsbereich L von A x = 0 die Dimension n−rang(A) besitzt (vgl. Satz 8.34b)). Das heißt, im Falle von rang(A) < n besitzt das homogene lineare Gleichungssystem unendlich viele Lösungen und im Falle von rang(A) = n genau eine Lösung, nämlich den Nullvektor 0 ∈ Rn. Bei einem inhomogenen linearen Gleichungssystem A x = b der Ordnung m×n ist dagegen der Nullvektor 0 niemals eine Lösung. Da jedoch ein linearer Unterraum des Rn stets den Nullvektor 0 enthält (vgl. Seite 154), kann der Lösungsbereich L = {x ∈ Rn : A x = b} eines inhomogenen linearen Gleichungssystems kein linearer Unterraum des Rn sein. Das heißt, bei inhomogenen linearen Gleichungssystemen kann im Gegensatz zu homogenen linearen Gleichungssystemen der Lösungsbereich L auch leer sein und es stellt sich somit die Frage, wann eine Lösung existiert und wann nicht. Rangkriterium Die Frage nach der Existenz einer Lösung bei einem allgemeinen linearen Gleichungssystem A x = b wird durch den F. G. Frobenius folgenden Existenzsatz vollständig beantwortet. Dieses Ergebnis ist in der linearen Algebra unter der Bezeichnung Rangkriterium bekannt und wurde in den Jahren 1875/1876 von den beiden französischen Mathematikern Georges Fontené (1848–1923) und Eugène Rouché (1832–1910) sowie dem deutschen Mathematiker Ferdinand Georg Frobenius (1849–1917) entwickelt. In einem seiner wissenschaftlichen Aufsätze hat jedoch Frobenius im Jahre 1905 dieses Kriterium seinen beiden Kollegen Fontené und Rouché zugeschrieben. Zur Formulierung des Rangkriteriums wird die sogenannte erweiterte Koeffizientenmatrix (A, b) := ⎛ ⎜ ⎝ a11 · · · a1n b1 ... . . . ... ... am1 · · · amn bm ⎞ ⎟ ⎠ benötigt. Sie geht aus der Koeffizientenmatrix A ∈ M(m, n) dadurch hervor, dass diese um die rechte Seite b des linearen Gleichungssystems als zusätzliche Spalte erweitert wird. In der erweiterten Koeffizientenmatrix sind alle Informationen über das lineare Gleichungssystem A x = b enthalten. Die erweiterte Koeffizientenmatrix (A, b) ist von der Ordnung m× (n+ 1). Da der Rang einer Matrix die Anzahl der linear unabhängigen Spaltenvektoren angibt (vgl. Abschnitt 8.6) und die Matrix (A, b) eine Spalte mehr als die Matrix A besitzt, folgt unmittelbar rang(A) = dim (Bild(A)) (9.1) ≤ dim (Bild(A, b)) = rang(A, b). Das folgende Rangkriterium besagt nun, dass ein allgemeines lineares Gleichungssystem A x = b genau dann lösbar ist, wenn die beiden Koeffizientenmatrizen A und (A, b) den gleichen Rang haben: Satz 9.1 (Rangkriterium) Ein lineares Gleichungssystem A x = b der Ordnung m× n ist genau dann lösbar, wenn gilt rang(A) = rang(A, b). (9.2) 222 Kapitel 99.1 Eigenschaften linearer Gleichungssysteme Beweis: Bezeichnen a1, . . . , an ∈ Rm die Spaltenvektoren der Matrix A, dann gilt Bild(A) = Lin {a1, . . . , an} ⊆ Bild(A, b) = Lin {a1, . . . , an, b} (vgl. (8.32)). Folglich gilt Bild(A) = Bild(A, b) und damit b ∈ Bild(A) genau dann, wenn (9.2) erfüllt ist. Da jedoch b ∈ Bild(A) zur Existenz eines Vektors x ∈ Rn mit A x = b äquivalent ist (vgl. (8.31)), folgt daraus die Behauptung. Struktur des Lösungsbereichs L Der folgende Satz gibt weitere Auskunft über die Struktur des Lösungsbereichs L eines allgemeinen linearen Gleichungssystems A x = b. Er besagt unter anderem, dass die Anzahl der Lösungen eines linearen Gleichungssystems maßgeblich von der Größe des Kerns der Matrix A abhängt. Satz 9.2 (Eigenschaften des Lösungsbereichs L) Für ein lineares Gleichungssystem A x = b der Ordnung m× n mit dem Lösungsbereich L = {x ∈ Rn : A x = b} gilt: a) x1, x2 ∈ L und λ1, λ2 ∈ R mit λ1 + λ2 = 1 ⇒ λ1x1 + λ2x2 ∈ L b) x1, x2 ∈ L ⇒ A (x1 − x2) = 0, also x1 − x2 ∈ Kern(A) c) xp ∈ L ⇒ L = {x ∈ Rn : x = xp + z mit z ∈ Kern(A)} Beweis: Zu a): Wegen λ1 + λ2 = 1 gilt A (λ1x1 + λ2x2) = λ1A x1 + λ2A x2 = λ1b + λ2b = (λ1 + λ2)b = b. Das heißt, es gilt λ1x1 + λ2x2 ∈ L. Zu b): Es gilt A (x1 − x2) = A x1 − A x2 = b − b = 0 und somit auch x1 − x2 ∈ Kern(A). Zu c): Es gilt {x ∈ Rn : x = xp + z mit z ∈ Kern(A)} ⊆ L. Denn z ∈ Kern(A) impliziert A (xp + z) = A xp + A z = b + 0 = b und somit xp + z ∈ L für alle z ∈ Kern(A). Umgekehrt gilt L ⊆ {x ∈ Rn : x = xp + z mit z ∈ Kern(A)}. Denn für x ∈ L folgt aus Aussage b) z := x − xp ∈ Kern(A). Dies impliziert x = xp + z ∈ {x ∈ Rn : x = xp + z mit z ∈ Kern(A)}. Somit gilt insgesamt L = {x ∈ Rn : x = xp + z mit z ∈ Kern(A)}. Aus Satz 9.2a) folgt, dass ein lineares Gleichungssystem A x = b der Ordnung m × n mit zwei verschiedenen Lösungen x1 und x2 stets unendlich viele verschiedene Lösungen besitzt. Ein lineares Gleichungssystem kann somit keine Lösung, genau eine Lösung oder unendlich viele Lösungen besitzen. Es ist dagegen nicht möglich, dass ein lineares Gleichungssystem genau zwei Lösungen, genau drei Lösungen usw. besitzt. Der Satz 9.2c) besagt, dass sich bei einem nichtleeren Lösungsbereich L jede Lösung x von A x = b zusammensetzt aus einer beliebigen speziellen Lösung xp des inhomogenen linearen Gleichungssystems A x = b und einer Lösung z ∈ Kern(A) des zugehörigen homogenen linearen Gleichungssystems A x=0. Die Lösung des linearen Gleichungssystems A x = b ist somit eindeutig, wenn Kern(A) = {0} gilt. Gemäß Satz 8.34d) ist dies jedoch äquivalent zu rang(A) = n. Insgesamt erhält man somit den folgenden Existenz- und Eindeutigkeitssatz: Satz 9.3 (Existenz- und Eindeutigkeitssatz) Für den Lösungsbereich eines linearen Gleichungssystems A x = b der Ordnung m× n gilt genau einer der folgenden drei Fälle: 1. Fall: Keine Lösung ⇐⇒ rang(A) < rang(A,b) 2. Fall: Genau eine Lösung ⇐⇒ rang(A) = rang(A, b) und rang(A) = n 3. Fall: Unendlich viele Lösungen ⇐⇒ rang(A) = rang(A, b) und rang(A) < n Beweis: Die Aussagen für die drei verschiedenen Fälle folgen aus Satz 9.1 und den Erläuterungen vor diesem Satz. Die gewonnenen Erkenntnisse zur Existenz und Eindeutigkeit von Lösungen bei linearen Gleichungssystemen A x = b sind in Abbildung 9.1 übersichtlich dargestellt. Die Aussagen von Satz 9.3 werden im folgenden Beispiel anhand dreier linearer Gleichungssysteme der Ordnung 2 × 2 mit einer, keiner bzw. unendlich vielen Lösungen verdeutlicht: 223 Kapitel 9 Lineare Gleichungssysteme und Gauß-Algorithmus Lineares Gleichungssystem Ax = b homogen: b = 0 inhomogen: b ≠ 0 lösbar, da stets rang(A) = rang(A, 0) lösbar, falls rang(A) = rang(A, b) unlösbar, falls rang(A) < rang(A, b) eindeutig, falls rang(A) = n mehrdeutig, falls rang(A) < n eindeutig, falls rang(A) = n mehrdeutig, falls rang(A) < n Abb. 9.1: Die verschiedenen möglichen Fälle bei der Lösung eines linearen Gleichungssystems A x = b der Ordnung m× n Beispiel 9.4 (Lösungsbereich bei linearen Gleichungssystemen) Betrachtet werden die folgenden drei linearen Gleichungssysteme der Ordnung 2 × 2: a) 3x + 4y = 2 b) x + y = 5 c) x − y = 0 6x + 8y = 24 x − y = −1 2x − 2y = 0 (vgl. Abbildung 9.2). In Matrixschreibweise erhält man für diese drei linearen Gleichungssysteme die folgenden Darstellungen: Zu a): Es gilt ( 3 4 6 8 )( x y ) = ( 2 24 ) . Die beiden Spaltenvektoren von A sind linear abhängig. Es gilt daher rang(A) = 1. Die rechte Seite b ist jedoch linear unabhängig von den beiden Spaltenvektoren von A und es gilt somit rang(A) < rang(A, b) = 2. Das heißt, gemäß Satz 9.3 besitzt das lineare Gleichungssystem keine Lösung, also ist L = ∅. Zu b): Es gilt ( 1 1 1 −1 )( x y ) = ( 5 −1 ) . Die beiden Spaltenvektoren von A sind linear unabhängig. Es gilt somit rang(A) = 2. Daraus folgt zusammen mit rang(A) ≤ rang(A, b) (vgl. (9.1)) und rang(A, b) ≤ min {2, 3} = 2 (vgl. Satz 8.34a)), dass rang(A)= rang(A, b) = 2 gilt. Gemäß Satz 9.3 existiert daher genau eine Lösung und der Lösungsbereich ist gegeben durch L = {(2, 3)T }. Zu c): Es gilt ( 1 −1 2 −2 )( x y ) = ( 0 0 ) . Die beiden Spaltenvektoren von A und die rechte Seite b sind jeweils Vielfache voneinander. Es gilt daher rang(A) = rang(A, b) = 1. Gemäß Satz 9.3 gibt es somit unendlich viele Lösungen. Der Lösungsbereich ist gegeben durch L = {(x, y)T ∈ R2 : x = y}. 9.2 Elementare Zeilenumformungen und Zeilenstufenform In Abschnitt 9.3 wird der bekannte Gauß-Algorithmus vorgestellt, mit dem es möglich ist, lineare Gleichungssysteme A x = b beliebiger Ordnung m×n zu lösen. Er basiert auf sogenannten elementaren Zeilenumformungen der erweiterten Koeffizientenmatrix (A, b) = ⎛ ⎜ ⎝ a11 · · · a1n b1 ... . . . ... ... am1 · · · amn bm ⎞ ⎟ ⎠ . (9.3) 224 Kapitel 99.2 Elementare Zeilenumformungen und Zeilenstufenform −6 −4 −2 2 4 6 −4 −2 2 4 6 8 l −6 −4 −2 2 4 6 −4 −2 2 4 6 8 −6 −4 −2 2 4 6 −4 −2 2 4 6 8 Abb. 9.2: Graphische Veranschaulichung des Lösungsbereichs L eines linearen Gleichungssystems A x = b der Ordnung 2× 2 mit genau einer Lösung (links), keiner Lösung (Mitte) und unendlich vielen Lösungen (rechts) Elementare Zeilenumformungen Unter elementaren Zeilenumformungen versteht man die folgenden drei Arten von Operationen: a) Vertauschen zweier Zeilen b) Multiplikation einer Zeile (d. h. jedes Elements der Zeile) mit einer Konstanten λ = 0 c) Addition des λ-fachen einer Zeile (d. h. das λ-fache jedes Elements der Zeile) zu einer anderen Zeile Diese Umformungen sind dadurch gerechtfertigt, dass sie das lineare Gleichungssystem A x = b in ein äquivalentes lineares Gleichungssystem à x = b̃ der gleichen Ordnung m× n mit dem gleichen Lösungsbereich L überführen. Satz 9.5 (Erhaltung des Lösungsbereichs bei element. Zeilenumformungen) Es seien (A, b) die erweiterte Koeffizientenmatrix des linearen Gleichungssystems A x = b der Ordnung m× n und (Ã, b̃) die aus (A, b) durch endlich viele elementare Zeilenumformungen entstandene erweiterte Koeffizientenmatrix des linearen Gleichungssystems à x = b̃. Dann besitzen A x = b und à x = b̃ den gleichen Lösungsbereich L. Das heißt, es gilt {x ∈ Rn : A x = b} = {x ∈ Rn : à x = b̃} . Beweis: Es kann ohne Beschränkung der Allgemeinheit angenommen werden, dass (Ã, b̃) aus (A, b) durch eine elementare Zeilenumformung hervorgegangen ist. Denn verändert sich der Lösungsbereich L bei Anwendung einer der drei elementaren Zeilenumformungen a), b) und c) nicht, dann verändert er sich auch durch wiederholte Anwendung von elementaren Zeilenumformungen nicht. Zeilenumformung vom Typ a): Da alle m linearen Gleichungen von A x = b simultan erfüllt sein müssen, verändert sich durch Vertauschen von Zeilen der Lösungsbereich L nicht. Zeilenumformungen vom Typ b) und c): Die lineare Gleichung ai1x1+. . .+ainxn = bi ist offensichtlich genau dann für ein x = (x1, . . . , xn) T ∈ Rn erfüllt, wenn λai1x1 + . . .+ λainxn = λbi für eine Konstante λ = 0 erfüllt ist. Analog gilt, dass die beiden linearen Gleichungen ai1x1+. . .+ainxn = bi und ak1x1+. . .+ aknxn = bk genau dann für ein x = (x1, . . . , xn)T ∈ Rn erfüllt sind, wenn die beiden linearen Gleichungen (ai1 + λak1)x1 + . . .+ (ain + λakn)xn = bi + λbk und ak1x1 + . . .+ aknxn = bk gelten. Dies bedeutet, dass auch Zeilenumformungen vom Typ b) und c), den Lösungsbereich L nicht verändern. Zu beachten ist, dass Spaltenumformungen eine gänzlich andere Wirkung auf die erweiterte Koeffizientenmatrix haben als Zeilenumformungen. Da es durch Spaltenumformungen zu Vermischungen von Variablen kommt, sollten sie bei der Lösung eines linearen Gleichungssystems nicht durchgeführt werden. Unproblematisch ist dagegen das Vertauschen zweier Spalten ai und aj der Matrix A, wenn auch die Bezeichnungen der zugehörigen Variablen xi und xj entsprechend vertauscht werden. 225 Kapitel 9 Lineare Gleichungssysteme und Gauß-Algorithmus Zeilenstufenform Der Gauß-Algorithmus zur Lösung eines linearen Gleichungssystems A x = b basiert nun auf der Idee, die zugehörige erweiterte Koeffizientenmatrix (A, b) durch geeignete elementare Zeilenumformungen auf eine Form zu bringen, aus der die Lösung möglichst einfach abgelesen werden kann. Eine solche Form ist durch die sogenannte Zeilenstufenform gegeben. Definition 9.6 (Zeilenstufenform) Eine m × n-Matrix A ist in Zeilenstufenform, wenn sie gleich der Nullmatrix Om×n ist oder wenn sie die folgenden vier Bedingungen erfüllt: a) Eine Zeile, die nicht nur aus Nullen besteht, hat – von links nach rechts betrachtet – als ersten von 0 verschiedenen Eintrag eine 1, der als führende Eins bezeichnet wird. b) In zwei aufeinander folgenden Zeilen, die beide von 0 verschiedene Einträge enthalten, steht die führende Eins der oberen Zeile links von der führenden Eins der unteren Zeile. c) Alle Zeilen, die nur Nullen enthalten, stehen am Ende der Matrix. d) Eine Spalte, die eine führende Eins enthält, besitzt keine weiteren von 0 verschiedenen Einträge. Variablen, die zu führenden Einsen gehören, werden als führende Variablen bezeichnet, und die anderen Variablen heißen freie Variablen. Das folgende Beispiel verdeutlicht, wie einfach sich die Lösung eines linearen Gleichungssystems ablesen lässt, wenn die erweiterte Koeffizientenmatrix (A, b) in Zeilenstufenform vorliegt: Beispiel 9.7 (Erweiterte Koeffizientenmatrizen in Zeilenstufenform) a) Die erweiterte Koeffizientenmatrix des linearen Gleichungssystems x1 = 3 x2 = 1 x3 = −1 ist in Zeilenstufenform und gegeben durch (A, b) = ⎛ ⎝ 1 0 0 3 0 1 0 1 0 0 1 −1 ⎞ ⎠ . Es lässt sich leicht ablesen, dass rang(A) = rang(A, b) = 3 = n gilt. Gemäß Satz 9.3 gibt es somit genau eine Lösung und der Lösungsbereich ist offensichtlich L = {(3, 1,−1)T }. b) Das lineare Gleichungssystem x1 = 0 x2 + 2x3 = 0 0 = 1 besitzt offensichtlich keine Lösung, da die letzte Gleichung stets falsch ist. Dieses Ergebnis lässt sich auch leicht aus der zugehörigen erweiterten Koeffizientenmatrix ablesen. Diese ist ebenfalls in Zeilenstufenform und gegeben durch (A, b) = ⎛ ⎝ 1 0 0 0 0 1 2 0 0 0 0 1 ⎞ ⎠ . Aus dieser Darstellung ist gut zu erkennen, dass rang(A) < rang(A, b) = 3 = n gilt. Gemäß Satz 9.3 existiert somit keine Lösung. c) Zum linearen Gleichungssystem x1 + 4x3 + 5x5 = 3 x2 + 3x3 = 1 x4 + x5 = 2 gehört die folgende erweiterte Koeffizientenmatrix in Zeilenstufenform: (A, b) = ⎛ ⎝ 1 0 4 0 5 3 0 1 3 0 0 1 0 0 0 1 1 2 ⎞ ⎠ Aus dieser Darstellung ist zu erkennen, dass rang(A) = rang(A, b) = 3 < n = 5 gilt. Gemäß Satz 9.3 gibt es somit unendlich viele Lösungen. Wird das lineare Gleichungssystem von unten nach 226 Kapitel 99.3 Gauß-Algorithmus oben nach den führenden Variablen x1, x2, x4 aufgelöst, dann erhält man: x4 = 2 − x5 x2 = 1 − 3x3 x1 = 3 − 4x3 − 5x5 Wird den freien Variablen x3 und x5 jeweils ein Parameter λ1 bzw. λ2 zugewiesen, dann erhält man für den unendlichen Lösungsbereich die folgende Parametrisierung L= ⎧ ⎪⎪⎪⎪⎨ ⎪⎪⎪⎪⎩ x ∈ R5 : ⎛ ⎜⎜⎜⎜ ⎝ x1 x2 x3 x4 x5 ⎞ ⎟⎟⎟⎟ ⎠ = ⎛ ⎜⎜⎜⎜ ⎝ 3 1 0 2 0 ⎞ ⎟⎟⎟⎟ ⎠ + λ1 ⎛ ⎜⎜⎜⎜ ⎝ −4 −3 1 0 0 ⎞ ⎟⎟⎟⎟ ⎠ +λ2 ⎛ ⎜⎜⎜⎜ ⎝ −5 0 0 −1 1 ⎞ ⎟⎟⎟⎟ ⎠ mit λ1, λ2 ∈ R ⎫ ⎪⎪⎪⎪⎬ ⎪⎪⎪⎪⎭ . 9.3 Gauß-Algorithmus C. F. Gauß auf einer deutschen Briefmarke Im letzten Abschnitt wurde gezeigt, dass die Lösung eines linearen Gleichungssystems A x = b, dessen erweiterte Koeffizientenmatrix (A, b) in Zeilenstufenform vorliegt, sehr einfach aus dem linearen Gleichungssystem abgelesen werden kann. Das Verfahren, bei dem durch elementare Zeilenumformungen die erweiterte Koeffizientenmatrix solange umgeformt wird, bis sie in Zeilenstufenform vorliegt, ist nach dem deutschen Mathematiker Carl Friedrich Gauß (1777–1855) als Gauß-Algorithmus oder auch Gaußsches Eliminationsverfahren benannt. Der Gauß- Algorithmus ist damit ein leistungsfähiges Verfahren, mit dem prinzipiell lineare Gleichungssysteme beliebiger Ordnung gelöst werden können. Die erste Veröffentlichung in Europa zu einem Verfahren, das die wesentlichen Elemente des Gauß-Algorithmus aufweist, wurde im Jahre 1759 jedoch nicht von Gauß selbst, sondern von dem italienischen Mathematiker Joseph-Louis Lagrange (1736–1813) publiziert. Da der Algorithmus aber erst 1810 durch die von Gauß veröffentlichte wissenschaftliche Abhandlung „Disquisitio de elementis ellipticis Palladis“ richtig bekannt wurde, trägt der Algorithmus heute seinen Namen. Seite aus dem Buch Jiu Zhang Suanshu Bemerkenswert ist auch, dass eine Demonstration des Algorithmus anhand der Lösung eines linearen Gleichungssystems mit drei Variablen bereits im chinesischen Mathematikbuch Jiu Zhang Suanshu zu finden ist. Dieses bedeutende wissenschaftliche Werk wurde zwischen 200 v. Chr. und 100 n. Chr. verfasst und ist damit eines der ältesten erhaltenen Mathematikbücher. Es zeigt den Stand der chinesischen Mathematik im 1. Jahrhundert n. Chr. anhand verschiedener praktischer Anwendungsgebiete wie der Bautechnik, der Landvermessung, dem Steuerwesen usw. Bei der Durchführung des Gauß-Algorithmus zur Lösung eines linearen Gleichungssystems A x = b der Ordnung m × n ist es zweckmäßig, wenn die einzelnen elementaren Zeilenumformungen nacheinander und übersichtlich in einem Tableau dargestellt werden und die Zeilen dabei durchnummeriert werden. Der Gauß-Algorithmus läuft dann in den folgenden Schritten ab: 1) Die erweiterte Koeffizientenmatrix (A, b) des linearen Gleichungssystems A x = b wird in einem Ausgangstableau dargestellt: A x1 x2 . . . xn b a11 a12 . . . a1n b1 a21 a22 . . . a2n b2 ... ... . . . ... ... am1 am2 . . . amn bm (9.4) 2) Durch elementare Zeilenumformungen und Spaltenvertauschungen wird die erweiterte Koeffizientenmatrix, d. h. 227 Kapitel 9 Lineare Gleichungssysteme und Gauß-Algorithmus das Ausgangstableau, solange umgeformt, bis ein Endableau in der folgenden Zeilenstufenform vorliegt: à x̃1 x̃2 x̃3 . . . . . . x̃k x̃k+1 x̃k+2 . . . x̃n b̃ 1 0 0 . . . . . . 0 ã1k+1 ã1k+2 . . . ã1n b̃1 0 1 0 . . . . . . 0 ã2k+1 ã2k+2 . . . ã2n b̃2 0 0 1 0 . . . 0 ã3k+1 ã3k+2 . . . ã3n b̃3 ... ... ... . . . ... ... ... ... . . . ... ... 0 0 0 . . . 1 0 ãk−1k+1 ãk−1k+2 . . . ãk−1n b̃k−1 0 0 0 . . . 0 1 ãkk+1 ãkk+2 . . . ãkn b̃k 0 . . . . . . . . . . . . 0 0 . . . . . . 0 b̃k+1 0 . . . . . . . . . . . . 0 0 . . . . . . 0 b̃k+2 ... ... ... ... ... ... ... ... ... ... ... 0 . . . . . . . . . . . . 0 0 . . . . . . 0 b̃m (9.5) Für die Zahl k gilt dabei 0 ≤ k ≤ n und der Vektor x̃ = (̃x1, . . . , x̃n)T entsteht aus x durch eventuell notwendige Komponentenvertauschungen. Das Tableau (9.5) ist äquivalent zum linearen Gleichungssystem à x̃ = b̃, also: x̃1 + ã1k+1x̃k+1 . . . + ã1nx̃n = b̃1 x̃2 + ã2k+1x̃k+1 . . . + ã2nx̃n = b̃2 . . . ... ... = ... x̃k + ãkk+1x̃k+1 . . . + ãknx̃n = b̃k 0 = b̃k+1 ... ... ... 0 = b̃m Der folgende Satz besagt, dass es bei einem linearen Gleichungssystem A x = b stets möglich ist, durch elementare Zeilenumformungen und Spaltenvertauschungen die zugehörige erweiterte Koeffizientenmatrix (A, b), also das Ausgangstableau (9.4), in die Zeilenstufenform (9.5) zu überführen. Darüber hinaus gibt er Auskunft darüber, wann das zu (9.5) gehörige lineare Gleichungssystem à x̃ = b̃ eine Lösung besitzt und wie aus (9.5) der Lösungsbereich L von à x̃ = b̃ – und damit auch von A x = b – ermittelt werden kann. Satz 9.8 (Gauß-Algorithmus) Die erweiterte Koeffizientenmatrix (A, b) eines linearen Gleichungssystems A x = b der Ordnung m × n kann durch endlich viele elementare Zeilenumformungen und Spaltenvertauschungen auf die Zeilenstufenform (9.5) gebracht werden. Das zu (9.5) gehörende lineare Gleichungssystem à x̃ = b̃ ist genau dann lösbar, wenn b̃k+1 = . . . = b̃m = 0 erfüllt ist. Im Falle der Existenz einer Lösung ist zu unterscheiden: a) Gilt k = n, dann ist x̃ = ⎛ ⎜ ⎝ b̃1 ... b̃n ⎞ ⎟ ⎠ die eindeutige Lösung von à x̃ = b̃. b) Gilt k < n, dann besitzt à x̃ = b̃ unendlich viele Lösungen. Werden den n − k freien Variablen x̃k+1, . . . , x̃n die Parameter λ1, . . . , λn−k zugewiesen, dann sind die Lösungen von à x̃ = b̃ gegeben durch die Parametrisierung x̃= ⎛ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜ ⎝ x̃1 ... x̃k x̃k+1 x̃k+2 ... x̃n ⎞ ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟ ⎠ = ⎛ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜ ⎝ b̃1 ... b̃k 0 0 ... 0 ⎞ ⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎠ −λ1 ⎛ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜ ⎝ ã1k+1 ... ãkk+1 −1 0 ... 0 ⎞ ⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎠ −. . .−λn−k ⎛ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜ ⎝ ã1n ... ãkn 0 ... 0 −1 ⎞ ⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎠ . (9.6) Der Lösungsbereich L von à x̃ = b̃ stimmt bis auf eventuell durchgeführte Variablenvertauschungen (d. h. Spaltenvertauschungen) mit dem von A x = b überein. Beweis: Der Beweis ist konstruktiv. Das heißt, er zeigt, wie mittels Gauß-Algorithmus die Zeilenstufenform (9.5) erzeugt werden kann. Schritt 1: Die erweiterte Koeffizientenmatrix (A, b) wird in einem Ausgangstableau der Form (9.4) dargestellt. Schritt 2: Es wird die am weitesten links stehende Spalte bestimmt, die einen von Null verschiedenen Eintrag besitzt. Das heißt, es wird der kleinste Index j ∈ {1, . . . , n} bestimmt, für den es ein i ∈ {1, . . . , m} mit aij = 0 gibt. Existiert keine Spalte 228 Kapitel 99.3 Gauß-Algorithmus mit dieser Eigenschaft, dann ist das Tableau bereits in der Zeilenstufenform (9.5) und das Verfahren ist beendet. Schritt 3: Es sei j der in Schritt 2 bestimmte Spaltenindex. Gilt a1j = 0, dann wird die erste Zeile mit a−11j multipliziert. Dadurch entsteht eine führende Eins. Gilt dagegen a1j = 0, dann wird vorher die erste Zeile mit einer anderen Zeile, die in der j -ten Spalte einen von Null verschiedenen Eintrag besitzt, vertauscht. Schritt 4: Durch Addition von geeigneten Vielfachen der ersten Zeile zu den darunterliegenden Zeilen werden unter der führenden Eins Nullen erzeugt. Schritt 5: Die Schritte 2 bis 4 werden auf das Tableau angewendet, das sich durch Streichen der ersten Zeile ergibt. Dieses Vorgehen bricht spätestens dann ab, wenn die letzte Zeile bearbeitet worden ist. Durch Addition von geeigneten Vielfachen einer Zeile zu den darüberliegenden Zeilen werden anschließend auch über der führenden Eins Nullen erzeugt. Zum Schluss müssen eventuell noch Spaltenvertauschungen durchgeführt werden, so dass schließlich die Zeilenstufenform (9.5) resultiert. Aus (9.5) ist zu erkennen, dass rang(Ã) = k und rang(Ã) = rang(Ã, b̃) ⇐⇒ b̃k+1 = . . . = b̃m = 0 gilt. Mit Satz 9.3 folgt somit, dass à x = b̃ genau dann eine Lösung besitzt, wenn b̃k+1 = . . . = b̃m = 0 gilt. Ferner folgt, dass diese Lösung für k = n eindeutig und für k < n nicht eindeutig ist. Die Parametrisierung (9.6) ergibt sich aus (9.5) durch Auflösen nach den führenden Variablen x̃1, . . . , x̃k und Zuweisung von Parametern λ1, . . . , λn−k zu den freien Variablen x̃k+1, . . . , x̃n. Mit Satz 9.5 erhält man schließlich, dass der Lösungsbereich L von à x̃ = b̃ bis auf eventuell durchgeführte Variablenvertauschungen (verursacht durch eventuell durchgeführte Spaltenvertauschungen) mit dem von A x = b übereinstimmt. Aus dem Endtableau (9.5) können die Lösungen des linearen Gleichungssystems à x̃ = b̃ durch Auflösen der ersten k Gleichungen nach den führenden Variablen x̃1, . . . , x̃k bestimmt werden. Wenn keine freien Variablen existieren, ist die Lösung eindeutig und andernfalls werden die freien Variablen x̃k+1, . . . , x̃n durch Parameter λ1, . . . , λn−k ersetzt. Man erhält dann eine Parametrisierung der unendlich vielen Lösungen im Lösungsbereich L. Es wurde bereits gezeigt, dass ein quadratisches lineares Gleichungssystem A x = b mit invertierbarer Koeffizientenmatrix A ∈ M(n, n) auch mit Hilfe der inversen Matrix A−1 (vgl. Abschnitt 8.7) und der Cramerschen Regel (vgl. Abschnitt 8.10) gelöst werden kann. Der Gauß-Algorithmus besitzt jedoch den großen Vorteil, dass er deutlich schneller ist und auf lineare Gleichungssysteme beliebiger Ordnung angewendet werden kann. Darüber hinaus können mit dem Gauß- Algorithmus auf einfache und schnelle Weise die Inverse und der Rang einer Matrix berechnet werden (siehe Abschnitte 9.5 und 9.6). Im folgenden Beispiel wird ein übersichtliches Vorgehen bei der Anwendung des Gauß-Algorithmus demonstriert. Dabei werden die Zeilen durchnummeriert und die durchgeführten elementaren Zeilenumformungen rechts in blauer Schrift angegeben. Das Beispiel verdeutlicht, wie einfach aus der am Ende resultierenden Zeilenstufenform (9.5) die Lösungen abgelesen werden können: Beispiel 9.9 (Gauß-Algorithmus) a) Gegeben sei das folgende lineare Gleichungssystem der Ordnung 3 × 2: 4x1 + 2x2 = 10 3x1 + 8x2 = 1 5x1 + x2 = 20 Für die erweiterte Koeffizientenmatrix (A, b) erhält man durch elementare Zeilenumformungen: x1 x2 b (1) 4 2 10 (2) 3 8 1 (3) 5 1 20 (1′) 1 12 5 2 1/4 · (1) (2′) 0 132 − 132 (2)− 3 · (1′) (3′) 0 − 32 152 (3)− 5 · (1′) (1′′) 1 0 3 (1′)− 1/2 · (2′′) (2′′) 0 1 −1 2/13 · (2′) (3′′) 0 0 6 (3′)+ 3/2 · (2′′) Aus dem Endtableau ist zu erkennen, dass b̃3 = 0 gilt. Das heißt, das lineare Gleichungssystem besitzt keine Lösung. b) Betrachtet wird das folgende lineare Gleichungssystem der Ordnung 3 × 3: x1 + 3x2 + 4x3 = 8 2x1 + 9x2 + 14x3 = 25 5x1 + 12x2 + 18x3 = 39 Für die erweiterte Koeffizientenmatrix (A, b) erhält man durch elementare Zeilenumformungen: 229 Kapitel 9 Lineare Gleichungssysteme und Gauß-Algorithmus x1 x2 x3 b (1) 1 3 4 8 (2) 2 9 14 25 (3) 5 12 18 39 (1) 1 3 4 8 (2′) 0 3 6 9 (2)− 2 · (1) (3′) 0 −3 −2 −1 (3)− 5 · (1) (1′) 1 0 −2 −1 (1)− (2′) (2′′) 0 1 2 3 1/3 · (2′) (3′′) 0 0 4 8 (3′)+ (2′) (1′′) 1 0 0 3 (1′)+ 2 · (3′′) (2′′′) 0 1 0 −1 (2′′)− 2 · (3′′′) (3′′′) 0 0 1 2 1/4 · (3′′) Aus dem Endtableau ist zu erkennen, dass das lineare Gleichungssystem genau eine Lösung besitzt und diese durch x = (3,−1, 2)T gegeben ist. c) Gegeben sei das folgende lineare Gleichungssystem der Ordnung 4 × 4: x1 − 3x2 + x3 − x4 = 4 −2x1 + 6x2 − x3 + 4x4 = −7 4x1 − 12x2 + 7x3 + 2x4 = 19 −3x1 + 9x2 − x3 + 7x4 = −10 Für die erweiterte Koeffizientenmatrix (A, b) erhält man durch elementare Zeilenumformungen und Vertauschung der 2. und 3. Spalte im dritten Zwischentableau: x1 x2 x3 x4 b (1) 1 −3 1 −1 4 (2) −2 6 −1 4 −7 (3) 4 −12 7 2 19 (4) −3 9 −1 7 −10 (1) 1 −3 1 −1 4 (2′) 0 0 1 2 1 (2)+ 2 · (1) (3′) 0 0 3 6 3 (3)− 4 · (1) (4′) 0 0 2 4 2 (4)+ 3 · (1) x1 x3 x2 x4 (1′) 1 1 −3 −1 4 Spaltenver- (2′′) 0 1 0 2 1 tauschung (3′′) 0 3 0 6 3 x2 ↔ x3 (4′′) 0 2 0 4 2 (1′′) 1 0 −3 −3 3 (1′)− (2′′) (2′′) 0 1 0 2 1 (3′′′) 0 0 0 0 0 (3′′)− 3 · (2′′) (4′′′) 0 0 0 0 0 (4′′)− 2 · (2′′) Aus dem Endtableau ist zu erkennen, dass das lineare Gleichungssystem unendlich viele Lösungen besitzt. Durch Auflösen nach den beiden führenden Variablen x1 und x3 (beachte den Variablentausch) und mit der Zuweisung λ1 = x2 und λ2 = x4 erhält man die Parametrisierung x = ⎛ ⎜⎜ ⎝ x1 x2 x3 x4 ⎞ ⎟⎟ ⎠ = ⎛ ⎜⎜ ⎝ 3 0 1 0 ⎞ ⎟⎟ ⎠− λ1 ⎛ ⎜⎜ ⎝ −3 −1 0 0 ⎞ ⎟⎟ ⎠− λ2 ⎛ ⎜⎜ ⎝ −3 0 2 −1 ⎞ ⎟⎟ ⎠ mit λ1, λ2 ∈ R und damit den Lösungsbereich L = {x ∈ R4 : x = (3 + 3λ1 + 3λ2, λ1, 1 − 2λ2, λ2)T mit λ1, λ2 ∈ R } . 9.4 Matrizengleichungen Es seien A ∈ M(m, n) und B ∈ M(m,p) zwei bekannte Matrizen und X ∈ M(n, p) eine unbekannte Matrix. Dann wird die Gleichung A X = B (9.7) als Matrizengleichung mit der Lösung X bezeichnet. Matrizengleichungen sind bereits bei der Definition inverser Matrizen aufgetreten. Dort war die Matrix B eine Einheitsmatrix E und die Lösung X war durch die Inverse von A gegeben (vgl. Definition 8.39). Bezeichnet man die Spaltenvektoren von X mit x1, . . . , xp ∈Rn und diejenigen von B mit b1, . . . , bp ∈ Rm, dann ist die Lösung der Matrizengleichung (9.7) äquivalent zur Lösung der p linearen Gleichungssysteme A x1 = b1, A x2 = b2, . . . ,A xp = bp (9.8) (vgl. Abbildung 9.3). Da diese linearen Gleichungssysteme dieselbe Koeffizientenmatrix A besitzen, bedeutet dies, dass zur Lösung der Matrizengleichung (9.7) der Gauß- Algorithmus aus Abschnitt 9.3 herangezogen werden kann, indem er simultan auf diep linearen Gleichungssysteme (9.8) angewendet wird. Darüber hinaus erhält man die folgende Existenz- und Eindeutigkeitsaussage: 230 Kapitel 99.4 Matrizengleichungen Satz 9.10 (Existenz- und Eindeutigkeitsaussage für Matrizengleichungen) Für eine Matrizengleichung A X = B mit A ∈ M(m, n), B ∈ M(m,p) und X ∈ M(n, p) gilt: a) Sie besitzt genau dann eine Lösung X, wenn jedes der p linearen Gleichungssysteme A xi = bi mit i = 1, . . . , p mindestens eine Lösung besitzt. b) Sie besitzt genau eine Lösung X, wenn jedes der p linearen Gleichungssysteme A xi = bi mit i = 1, . . . , p genau eine Lösung besitzt. Beweis: Die Aussagen a) und b) folgen unmittelbar aus dem vor dem Satz geschilderten Zusammenhang zwischen der Matrizengleichung A X = B und den p linearen Gleichungssystemen A xi = bi mit i = 1, . . . , p. A B Xxi bim n n p Abb. 9.3: Simultane Lösung von p linearen Gleichungssystemen mittels einer Matrizengleichung Die konkrete Vorgehensweise bei der gleichzeitigen Lösung mehrerer linearer Gleichungssysteme wird im folgenden Beispiel verdeutlicht: Beispiel 9.11 (Wirtschaftswissenschaftliche Anwendung) Betrachtet wird ein Unternehmen, das drei Produkte P1, P2 und P3 mit Hilfe von drei Produktionsfaktoren F1, F2 und F3 in den kommenden drei Monaten produziert. Dabei unterscheidet sich der vorhandene Bestand an Produktionsfaktoren in den drei kommenden Monaten M1,M2 und M3. Die folgende Tabelle enthält die Produktionskoeffizienten sowie den Bestand an Produktionsfaktoren für die kommenden drei Monate: Produktions- Produkte Bestand faktoren P1 P2 P3 M1 M2 M3 F1 4 2 5 290 320 360 F2 3 5 7 365 495 575 F3 5 1 3 225 235 245 Zu berechnen ist die Anzahl an Einheiten xij , die von Produkt Pi (für i = 1, 2, 3) im j -ten Monat (für j = 1, 2, 3) produziert werden kann. Dabei soll der vorhandene Bestand an Produktionsfaktoren vollständig aufgebraucht werden. Mit den Bezeichnungen A := ⎛ ⎝ 4 2 5 3 5 7 5 1 3 ⎞ ⎠ , b1 := ⎛ ⎝ 290 365 225 ⎞ ⎠ , b2 := ⎛ ⎝ 320 495 235 ⎞ ⎠ und b3 := ⎛ ⎝ 360 575 245 ⎞ ⎠ sowie x1 := ⎛ ⎝ x11 x21 x31 ⎞ ⎠ , x2 := ⎛ ⎝ x12 x22 x32 ⎞ ⎠ und x3 := ⎛ ⎝ x13 x23 x33 ⎞ ⎠ ist dies gleichbedeutend damit, dass die drei linearen Gleichungssysteme A x1 = b1, A x2 = b2 und A x3 = b3 (9.9) simultan gelöst werden. Werden die Spaltenvektoren x1, x2, x3 und b1, b2, b3 jeweils zu einer Matrix X := (x1, x2, x3) bzw. B := (b1, b2, b3) zusammengefasst, können die drei linearen Gleichungssysteme (9.9) auch als Matrizengleichung A X = B (9.10) geschrieben werden. Mit dem Gauß-Algorithmus lassen sich die drei linearen Gleichungssysteme (9.9) simultan lösen. Das Ergebnis ist dann auch eine Lösung der Matrizengleichung (9.10): 231 Kapitel 9 Lineare Gleichungssysteme und Gauß-Algorithmus x1i x2i x3i b1 b2 b3 (1) 4 2 5 290 320 360 (2) 3 5 7 365 495 575 (3) 5 1 3 225 235 245 (1′) 1 12 5 4 145 2 80 90 1/4 · (1) (2′) 0 72 13 4 295 2 255 305 (2)− 3 · (1′) (3′) 0 − 32 − 134 − 2752 −165 −205 (3)− 5 · (1′) (1′) 1 12 5 4 145 2 80 90 (2′′) 0 1 1314 295 7 510 7 610 7 2/7 · (2′) (3′′) 0 0 − 137 − 5207 − 3907 − 5207 (3′)+ 3/2 · (2′′) (1′′) 1 0 1114 360 7 305 7 325 7 (1 ′)− 1/2 · (2′′) (2′′) 0 1 1314 295 7 510 7 610 7 (3′′′) 0 0 1 40 30 40 −7/13 · (3′′) (1′′′) 1 0 0 20 20 15 (1′′)− 11/14 · (3′′′) (2′′′) 0 1 0 5 45 50 (2′′)− 13/14 · (3′′′) (3′′′) 0 0 1 40 30 40 Die gesuchten Produktionsmengen für die Produkte in den drei Monaten sind somit gegeben durch x1 = ⎛ ⎝ 20 5 40 ⎞ ⎠ , x2 = ⎛ ⎝ 20 45 30 ⎞ ⎠ und x3 = ⎛ ⎝ 15 50 40 ⎞ ⎠ . Die Lösung der Matrizengleichung (9.10) lautet somit X = ⎛ ⎝ 20 20 15 5 45 50 40 30 40 ⎞ ⎠ . 9.5 Bestimmung der Inversen mittels Gauß-Algorithmus Es sei A ∈ M(n, n) eine invertierbare Matrix, deren Inverse durch A−1 = (b1, . . . , bn) mit den Spaltenvektoren b1, . . . , bn ∈ Rn gegeben sei. In Abschnitt 8.10 wurde bereits gezeigt, dass die Spaltenvektoren b1, . . . , bn von A−1 durch Bestimmung der Lösungen x1, . . . , xn der n linearen Gleichungssysteme A x1 = e1, . . . ,A xn = en (9.11) berechnet werden können und die Inverse A−1 dann durch X := (x1, . . . , xn) gegeben ist (vgl. (8.57)–(8.59)). Da jedoch die n linearen Gleichungssysteme (9.11) dieselbe Koeffizientenmatrix A besitzen, können ihre Lösungen simultan mit dem Gauß- Algorithmus berechnet werden (vgl. Abschnitt 9.4). Ausgangspunkt ist dabei ein Tableau, auf dessen linker Seite die Matrix A ∈ M(n, n) und auf dessen rechter Seite die Einheitsmatrix E ∈ M(n, n) steht: x1i . . . xni e1 . . . en a11 . . . a1n 1 . . . 0 ... . . . ... ... . . . ... an1 . . . ann 0 . . . 1 Dieses Tableau wird solange mit Hilfe von elementaren Zeilenumformungen bearbeitet, bis auf der linken Seite die Einheitsmatrix E steht: x1i . . . xni A−1 1 . . . 0 b11 . . . b1n ... . . . ... ... . . . ... 0 . . . 1 bn1 . . . bnn Die Matrix A ist dann invertierbar und auf der rechten Seite des Tableaus steht die Inverse von A. Denn durch dieses Vorgehen wird die Matrix X ∈ M(n, n) berechnet, welche die Matrizengleichung A X = E erfüllt (vgl. Abschnitt 9.4). Eine Matrix X mit dieser Eigenschaft ist jedoch die Inverse von A (vgl. Definition 8.39). Bei der Anwendung des Gauß- Algorithmus muss zuvor nicht untersucht werden, ob die Matrix eine Inverse besitzt. Denn falls die Matrix nicht invertierbar ist, resultiert auf der linken Seite des Tableaus eine Nullzeile. Die Matrizengleichung A X = E besitzt dann keine Lösung, was äquivalent dazu ist, dass keine Inverse existiert. Im Folgenden wird die Anwendung des Gauß-Algorithmus zur Berechnung von Inversen demonstriert. Dabei werden die Zeilen wieder durchnummeriert und die durchgeführten elementaren Zeilenumformungen rechts in blauer Schrift angegeben: Beispiel 9.12 (Bestimmung der Inversen mittels Gauß-Algorithmus) a) Gesucht ist die Inverse der 3 × 3-Matrix A = ⎛ ⎝ 1 2 1 2 3 6 4 7 8 ⎞ ⎠ . 232 Kapitel 99.6 Bestimmung des Rangs mittels Gauß-Algorithmus Mit Hilfe des Gauß-Algorithmus erhält man: x1i x2i x3i e1 e2 e3 (1) 1 2 1 1 0 0 (2) 2 3 6 0 1 0 (3) 4 7 8 0 0 1 (1) 1 2 1 1 0 0 (2′) 0 −1 4 −2 1 0 (2)− 2 · (1) (3′) 0 −1 4 −4 0 1 (3)− 4 · (1) (1) 1 2 1 1 0 0 (2′′) 0 1 −4 2 −1 0 −1 · (2′) (3′′) 0 0 0 −2 −1 1 (3′)+ (2′′) Auf der linken Seite resultiert ein Nullvektor und die Matrix A ist damit nicht invertierbar. b) Gesucht ist die Inverse der 3 × 3-Matrix A = ⎛ ⎝ 1 1 0 1 1 1 0 −1 0 ⎞ ⎠ . Der Gauß-Algorithmus liefert: x1i x2i x3i e1 e2 e3 (1) 1 1 0 1 0 0 (2) 1 1 1 0 1 0 (3) 0 −1 0 0 0 1 (1) 1 1 0 1 0 0 (2′) 0 0 1 −1 1 0 (2)− (1) (3) 0 −1 0 0 0 1 (1′) 1 0 0 1 0 1 (1)+ (3) (3) 0 −1 0 0 0 1 (2′) ↔ (3) (2′) 0 0 1 −1 1 0 (3) ↔ (2′) (1′) 1 0 0 1 0 1 (3′) 0 1 0 0 0 −1 −1 · (3) (2′′) 0 0 1 −1 1 0 Die Matrix A ist somit invertierbar und besitzt die Inverse A−1 = ⎛ ⎝ 1 0 1 0 0 −1 −1 1 0 ⎞ ⎠ . Es sei nun das lineare Gleichungssystem A x = b mit der rechten Seite b = (4,−2, 3)T zu lösen. Dann erhält man mit der Inversen A−1 die Lösung x = A−1 b = ⎛ ⎝ 1 0 1 0 0 −1 −1 1 0 ⎞ ⎠ ⎛ ⎝ 4 −2 3 ⎞ ⎠ = ⎛ ⎝ 7 −3 −6 ⎞ ⎠ . 9.6 Bestimmung des Rangs mittels Gauß-Algorithmus Neben der Inversen kann auch der Rang einer Matrix A mit Hilfe des Gauß-Algorithmus ermittelt werden. Hierfür ist der folgende Satz zentral: Satz 9.13 (Rangbestimmung mittels Gauß- Algorithmus) Eine m×n-Matrix A kann durch endlich viele elementare Zeilenumformungen und Spaltenvertauschungen auf die Form à = ⎛ ⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜ ⎝ 1 a12 . . . a1k . . . a1n 0 1 . . . a2k . . . a2n ... . . . ... . . . ... 0 0 . . . 1 . . . akn 0 0 . . . 0 . . . 0 ... ... . . . ... . . . ... 0 0 . . . 0 . . . 0 ⎞ ⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟ ⎠ (9.12) gebracht werden und es gilt dann rang(A) = k. Beweis: Der Beweis dafür, dass eine m × n-Matrix A durch endlich viele elementare Zeilenumformungen und Spaltenvertauschungen auf die Form (9.12) gebracht werden kann, verläuft ähnlich wie der Nachweis, dass eine erweiterte Koeffizientenmatrix (A, b) stets auf die Zeilenstufenform (9.5) gebracht werden kann (vgl. hierzu Beweis von Satz 9.8). Gemäß Satz 7.32 verändern elementare Zeilenumformungen die Anzahl linear unabhängiger Zeilenvektoren von A nicht und Spaltenvertauschungen haben offensichtlich keinen Einfluss auf die Anzahl linear unabhängiger Spaltenvektoren. Da jedoch der Rang einer Matrix mit der Anzahl ihrer linear unabhängigen Zeilenvektoren und mit der Anzahl ihrer linear unabhängigen Spaltenvektoren übereinstimmt (vgl. Folgerung 8.36) bedeutet dies, dass rang(Ã) = rang(A) gilt. Ferner ist aus (9.12) leicht zu erkennen, dass die ersten k Zeilenvektoren von à linear unabhängig sind. Es gilt somit rang(A) = rang(Ã) = k. Bei der Bestimmung des Rangs einer Matrix A kann somit wie bei der Lösung eines linearen Gleichungssystems und der Bestimmung der Inversen mittels Gauß-Algorithmus vorgegangen werden. Hat man nach endlich vielen elementaren Zeilenumformungen und Spaltenvertauschungen die Matrix A auf die Form (9.12) gebracht, dann ergibt sich der Rang von A als die Anzahl der Zeilen, die ungleich dem Nullvektor sind. 233 Kapitel 9 Lineare Gleichungssysteme und Gauß-Algorithmus Das folgende Beispiel zeigt das konkrete Vorgehen: Beispiel 9.14 (Bestimmung des Rangs mittels Gauß-Algorithmus) a) Gegeben sei die 4 × 4-Matrix A = ⎛ ⎜⎜ ⎝ 1 5 2 3 4 9 1 7 3 4 −1 4 0 11 7 5 ⎞ ⎟⎟ ⎠ . Mit dem Gauß-Algorithmus erhält man: x1 x2 x3 x4 (1) 1 5 2 3 (2) 4 9 1 7 (3) 3 4 −1 4 (4) 0 11 7 5 (1) 1 5 2 3 (2′) 0 −11 −7 −5 (2)− 4 · (1) (3′) 0 −11 −7 −5 (3)− 3 · (1) (4) 0 11 7 5 (1) 1 5 2 3 (2′) 0 −11 −7 −5 (3′′) 0 0 0 0 (3′)− (2′) (4′) 0 0 0 0 (4)+ (2′) (1) 1 5 2 3 (2′′) 0 1 711 5 11 −1/11 · (2′) (3′′) 0 0 0 0 (4′) 0 0 0 0 Es gilt somit rang(A) = 2. b) Betrachtet wird die 4 × 4-Matrix A = ⎛ ⎜⎜ ⎝ 2 4 −6 2 3 4 9 4 8 12 12 10 3 2 4 5 ⎞ ⎟⎟ ⎠ . Der Gauß-Algorithmus liefert: x1 x2 x3 x4 (1) 2 4 −6 2 (2) 3 4 9 4 (3) 8 12 12 10 (4) 3 2 4 5 (1′) 1 2 −3 1 1/2 · (1) (2′) 0 −2 18 1 (2)− 3 · (1′) (3′) 0 −4 36 2 (3)− 8 · (1′) (4′) 0 −4 13 2 (4)− 3 · (1′) (1′) 1 2 −3 1 (2′′) 0 1 −9 − 12 −1/2 · (2′) (3′′) 0 0 0 0 (3′)+ 4 · (2′′) (4′′) 0 0 −23 0 (4′)+ 4 · (2′′) (1′) 1 2 −3 1 (2′′) 0 1 −9 − 12 (4′′) 0 0 −23 0 (3′′) ↔ (4′′) (3′′) 0 0 0 0 (4′′) ↔ (3′′) (1′) 1 2 −3 1 (2′′) 0 1 −9 − 12 (4′′′) 0 0 1 0 −1/23 · (4′′) (3′′) 0 0 0 0 Es gilt somit rang(A) = 3. 234

Chapter Preview

References

Zusammenfassung

"uneingeschränkt zu empfehlen, [...] insbesondere als Einstiegslektüre im Bachelor-Studium". In: Studium, 2013.

So zentral die Rolle der Mathematik in der Ökonomie ist, so schwer tun sich die Studierenden mit mathematischen Methoden und Konzepten. Umso wichtiger ist es, die Studierenden bei ihrem aktuellen Wissensstand abzuholen und vorsichtig an den Stoff heranzuführen. Diesem Ziel verschreibt sich dieses Lehrbuch. Es führt mit vielen interessanten Beispielen aus der Ökonomie, kurzen Anekdoten und einem modernen mehrfarbigen Design in die zentralen mathematischen Methoden für ein erfolgreiches Wirtschaftsstudium ein, ohne dabei auf mathematische Klarheit sowie die notwendige Formalität und Stringenz zu verzichten. Auch nach dem Studium ist dieses Buch ein wertvoller Begleiter bei der mathematischen Lösung wirtschaftswissenschaftlicher Problemstellungen.

Aus dem Inhalt:

* Mathematische Grundlagen

* Lineare Algebra

* Matrizentheorie

* Folgen und Reihen

* Reellwertige Funktionen in einer und mehreren Variablen

* Differential- und Integralrechnung

* Optimierung mit und ohne Nebenbedingungen

* Numerische Verfahren

Dozenten finden auf der Website zum Buch unter www.vahlen.de zusätzliche Materialien zum Download.

"Indem Sie den Lehrstoff schrittweise aufbereiten und den Leser bei seinem aktuellen Wissenstand abholen, gelingt es ihnen [den Autoren], auch komplexe Zusammenhänge leicht nachvollziehbar zu vermitteln. Geschickt bauen sie immer wieder kurze Anekdoten, historische Ereignisse und überraschende Erkenntnisse in den Text ein". In: Studium, 2013.

Prof. Dr. Michael Merz ist Inhaber des Lehrstuhls für Mathematik und Statistik in den Wirtschaftswissenschaften an der Universität Hamburg. Prof. Dr. Mario V. Wüthrich forscht und lehrt am Department für Mathematik der ETH Zürich.