Springer-Lehrbuch
Christiane Rousseau • Yvan Saint-Aubin Unter Mitarbeit von Hélène Antaya und Isabelle Ascah-Coallier
Mathematik und Technologie Aus dem Englischen von Manfred Stern
Christiane Rousseau Dépt. Mathématiques et Statistique Université de Montréal Montreal, Kanada
Yvan Saint-Aubin Dépt. Mathématiques et Statistique Université de Montréal Montreal, Kanada
Übersetzer Manfred Stern Kiefernweg 8, D-06120 Halle an der Saale, Deutschland
[email protected]
Translation from the English language edition: Mathematics and Technology by Christiane Rousseau and Yvan Saint-Aubin Copyright © 2008 Springer Science+Business Media, LLC All rights reserved ISSN 0937-7433 ISBN 978-3-642-30091-2 DOI 10.1007/978-3-642-30092-9
ISBN 978-3-642-30092-9 (eBook)
Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar. Mathematics Subject Classification (2010): 00-01,03-01,42-01,49-01,94-01,97-01 Springer Spektrum © Springer-Verlag Berlin Heidelberg 2012 Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung, die nicht ausdrücklich vom Urheberrechtsgesetz zugelassen ist, bedarf der vorherigen Zustimmung des Verlags. Das gilt insbesondere für Vervielfältigungen, Bearbeitungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier Springer Spektrum ist eine Marke von Springer DE. Springer DE ist Teil der Fachverlagsgruppe Springer Science+Business Media www.springer-spektrum.de
Vorwort
Welchen Nutzen hat die Mathematik? Ist in der Mathematik nicht alles schon entdeckt? Das sind ganz nat¨ urliche Fragen, die h¨ aufig von Studenten der unteren Studienjahre gestellt werden. Die Antworten der Professoren sind oft ziemlich kurz. Die meisten Universit¨atskurse sind fest strukturiert, und es besteht ein großer Zeitdruck. Deswegen bieten diese Kurse kaum Gelegenheit, echte Anwendungen zu bringen und Beispiele aus der realen Welt zu untersuchen. Sogar noch mehr Obersch¨ uler stellen die gleichen Fragen mit gr¨ oßerer Hartn¨ ackigkeit. Die Lehrer in diesen Schulen arbeiten im Allgemeinen unter noch gr¨ oßerem Druck als Universit¨atsprofessoren. Wenn die betreffenden Sch¨ uler und Studenten dazu in der Lage sind, kompetent auf diese Fragen zu antworten, dann liegt das vermutlich daran, dass sie von ihren Lehrern und Professoren gute Antworten bekommen haben. Aber wessen Fehler ist es, wenn sie nicht antworten k¨onnen? Die Entstehung dieses Textes Bevor wir eine Einf¨ uhrung in den Text geben, m¨ ussen wir zun¨ achst u ¨ber die Vorlesung sprechen, die zu diesem Buch gef¨ uhrt hat. Die Vorlesung Mathematik und Technolo” gie“ wurde an der Universit¨ at Montreal ins Leben gerufen und erstmalig im Wintersemester 2001 gehalten. Die Vorlesung entstand, weil die meisten Kurse im MathematikDepartment nicht auf die realen Anwendungen eingegangen sind. Unsere Vorlesung war von Anfang an sowohl f¨ ur Studenten der unteren Studienjahre als auch f¨ ur k¨ unftige Gymnasiallehrer konzipiert. Da es f¨ ur die Vorlesung, die wir anvisierten, kein geeignetes Lehrbuch gab, schrieben wir unsere eigenen Vorlesungstexte. Wir waren in diese Niederschriften so vertieft, dass sie bald den Umfang eines Lehrbuches annahmen und viel mehr Material enthielten, als in einem Semester geboten werden konnte. Obwohl wir beide Berufsmathematiker sind, m¨ ussen wir zugeben, dass wir von den meisten Anwendungen, die in den folgenden Kapiteln behandelt werden, wenig oder nichts wussten.
vi
Vorwort
Mathemati k und Technolog ie“ ” Das Hauptziel des Kurses besteht darin, den aktiven und lebendigen Charakter der Mathematik zu demonstrieren, ihre Allgegenwart bei der Entwicklung von Technologien aufzuzeigen und die Studenten und Obersch¨ uler in Modellierungsprozesse einzuf¨ uhren, die einen Weg zur Entwicklung verschiedener mathematischer Anwendungen darstellen. Einige der behandelten Themen geh¨ oren nicht im engeren Sinne zum Gebiet der Technologie. Dennoch hoffen wir, dass wir die N¨ utzlichkeit der Mathematik und insbesondere die Rolle deutlich gemacht haben, welche die Mathematik in den Alltagstechnologien spielt. Mehrere der in diesem Buch behandelten Themen befinden sich immer noch in einer aktiven Entwicklungsphase. Dieser Umstand erm¨ oglicht den Studenten – h¨aufig zum ersten Mal – zu erkennen, dass die Mathematik ein offenes und dynamisches Fachgebiet ist. Zu den Studenten, die unsere Vorlesung besuchen, geh¨ oren auch zuk¨ unftige Oberschullehrer. Deswegen ist es wichtig zu betonen, dass unser Ziel nicht nur darin besteht, ihnen Beispiele und Anwendungen zu vermitteln, die sie sp¨ ater an ihre eigenen Sch¨ uler weitergeben k¨onnen. Vielmehr m¨ ochten wir unseren Studenten Werkzeuge in die Hand geben, mit deren Hilfe sie dann f¨ ur ihre sp¨ ateren Sch¨ uler geeignete Beispiele aus dem wirklichen Leben formulieren und entwickeln k¨ onnen. Wir m¨ ochten unseren Studenten das Gef¨ uhl vermitteln, dass sie ein Fach unterrichten, das nicht nur an sich elegant ist, sondern dass die Anwendungen der Mathematik dazu beigetragen haben, unsere physikalische Umgebung zu verstehen und zu gestalten. Das Ziel des Kurses
Die Auswahl der Themen Bei der Auswahl der Themen haben wir folgenden Punkten eine besondere Aufmerksamkeit gewidmet: •
Die Anwendungen sollten neueren Ursprungs sein oder das Alltagsleben der Studenten beeinflussen. Außerdem sollten – im Gegensatz zu anderen Vorlesungen f¨ ur Fortgeschrittene – einige der von uns betrachteten Teilgebiete der Mathematik modern sein oder sich sogar noch im Stadium der Entwicklung befinden. • Die Mathematik sollte relativ elementar sein, und falls sie dennoch u ¨ber den typischen Lehrplan (Differential- und Integralrechnung, Lineare Algebra, Wahrscheinlichkeitstheorie) eines Studenten des ersten Studienjahres hinausgeht, dann m¨ ussen die fehlenden Teile im Rahmen des betreffenden Kapitels behandelt werden. Wir haben uns bem¨ uht, umfassenden Gebrauch von der Oberschulmathematik zu machen – inbesondere von der euklidischen Geometrie. Die Mathematik der Oberschule und der unteren Studienjahre stellt beachtliche Werkzeuge bereit, die den Studenten den Zugang zu einem großen Anwendungsbereich erm¨ oglichen und h¨ aufig zum ersten Mal das Zusammenspiel unterschiedlicher Teilgebiete vor Augen f¨ uhren. • Das Niveau der erforderlichen mathematischen Bildung sollte ein gewisses Minimum nicht u ¨berschreiten: Ideen sind das wertvollste Gut eines Wissenschaftlers, und hinter den meisten technologischen Erfolgen liegt eine geistreiche und dennoch mitunter elementare Beobachtung.
Vorwort
vii
In diesem Sinne umfasst die im vorliegenden Buch verwendete Mathematik ein sehr breites Spektrum: •
•
•
• • • •
•
Geraden und Ebenen treten in allen ihren Formen auf (Normalformen, Parametergleichungen, Unterr¨ aume), h¨ aufig auf unerwartete Weise (etwa bei der Verwendung des Schnittes mehrerer Ebenen zur Entschl¨ usselung von Nachrichten, die mit einem Reed-Solomon-Code verschl¨ usselt wurden). Eine große Anzahl von Themen macht von grundlegenden geometrischen Objekten Gebrauch: von Kreisen, Kugeln und Kegelschnitten. Der Begriff des geometrischen Ortes von Punkten in der euklidischen Geometrie tritt h¨ aufig auf, zum Beispiel bei Aufgaben, in denen wir die Position eines Objekts durch Triangulation berechnen (Kapitel 1 u ¨ber GPS und Kapitel 15 u ¨ber Science Flashes). Die verschiedenen Typen von affinen Transformationen in der Ebene oder im Raum (insbesondere Drehungen und Symmetrien) kommen mehrere Male vor: in Kapitel 11 u ¨ber Bildkompression unter Verwendung von Fraktalen, in Kapitel 2 u ¨ber Mosaike und Friese und in Kapitel 3 u ¨ber Roboterbewegungen. Endliche Gruppen erscheinen als Symmetriegruppen (Kapitel 2 u ¨ber Mosaike und Friese) und auch bei der Entwicklung von Primalit¨ atstests in der Kryptografie (Kapitel 7). Endliche K¨orper treten in Kapitel 6 u ¨ber fehlerkorrigierende Codes, in Kapitel 1 u ¨ber das GPS und in Kapitel 8 u ¨ber die Erzeugung von Zufallszahlen auf. Sowohl Kapitel 7 u ¨ber Kryptografie als auch Kapitel 8 u ¨ber die Erzeugung von Zufallszahlen verwendet die Arithmetik modulo n, w¨ ahrend Kapitel 6 u ¨ber fehlerkorrigierende Codes die Arithmetik modulo 2 verwendet. Wahrscheinlichkeitstheorie tritt an mehreren unerwarteten Stellen in Erscheinung: in Kapitel 9 u ¨ber den PageRank -Algorithmus von Google und bei der Konstruktion von großen Primzahlen in Kapitel 7. Die Wahrscheinlichkeitstheorie wird in klassischer Ausrichtung in Kapitel 8 zur Erzeugung von Zufallszahlen verwendet. Lineare Algebra ist allgegenw¨artig: in Kapitel 6 u ¨ber Hamming- und Reed-SolomonCodes, in Kapitel 9 u ¨ber den PageRank -Algorithmus, in Kapitel 3 u ¨ber Roboterbewegungen, in Kapitel 2 u ¨ber Mosaike und Friese, in Kapitel 1 u ¨ber das GPS, in Kapitel 12 u ¨ber den JPEG-Standard und so weiter.
Verwendung des Buches als Vorlesungstext Das Buch ist f¨ ur Studenten geschrieben, die mit der euklidischen Geometrie ebenso vertraut sind wie mit Funktionen mehrerer Variabler, linearer Algebra und elementarer Wahrscheinlichkeitstheorie. Wir hoffen, dass wir implizit kein anderes Hintergrundwissen vorausgesetzt haben. Das Durcharbeiten des Textes erfordert dennoch eine gewisse wissenschaftliche Reife: Es kommt auf das Zusammenwirken einer Vielfalt von mathematischen Werkzeugen an, die urspr¨ unglich in einem anderen Zusammenhang gelehrt wurden. Aus diesem Grund sind Studenten der unteren Studienjahre die ideale H¨ orerschaft f¨ ur den Kurs.
viii
Vorwort
Der Text pr¨asentiert die Anwendungen in zwei Formen: Die Kapitel (mit Ausnahme von Kapitel 15) sind lang und detailliert, w¨ ahrend die Science Flashes (die Abschnitte von Kapitel 15) knapp gehalten sind. Die Leser werden eine bestimmte Einheitlichkeit in der Form der l¨ angeren Kapitel feststellen: Die ersten Abschnitte beschreiben die Anwendung und das ihr zugrundeliegende mathematische Problem; danach folgt eine Untersuchung einfacher Fallbeispiele und, falls notwendig, eine Entwicklung der erforderlichen Mathematik. Wir bezeichnen diese Abschnitte als den grundlegenden Teil des betreffenden Kapitels. Danach k¨ onnen Abschnitte folgen, in denen wir kompliziertere Beispiele untersuchen, mehr zu den bereits diskutierten mathematischen Werkzeugen sagen oder einfach darauf aufmerksam machen, dass die Mathematik allein nicht immer ausreicht! Diese Abschnitte eines Kapitels bezeichnen wir als fortgeschrittenen Teil. Jede Anwendung wird typischerweise in f¨ unf bis sechs Vorlesungsstunden behandelt: Zwei ¨ Stunden f¨ ur die grundlegende Theorie, zwei Stunden f¨ ur Beispiele und Ubungen, und – wenn es die Zeit erlaubt – ein oder zwei Stunden f¨ ur fortgeschrittene Themen. H¨ aufig k¨onnen wir das fortgeschrittene Material nur kurz behandeln, es sei denn, eine zweite Woche wird f¨ ur das Kapitel zur Verf¨ ugung gestellt. Jeder Science Flash kann in einer ¨ Vorlesungsstunde behandelt werden, l¨ asst sich aber auch als Ubung stellen, ohne vorher die Theorie zu entwickeln. Es ist unser Ziel, im Laufe eines Semesters den Großteil von acht bis zw¨olf Kapiteln und eine Handvoll Science Flashes abzuarbeiten. Eine andere Option besteht darin, die Anzahl der zu behandelnden Kapitel signifikant zu senken, sich aber daf¨ ur mehr in die fortgeschrittenen Abschnitte der entsprechenden Kapitel zu vertiefen. Wir sind demnach gezwungen, die Themen in Abh¨ angigkeit von ihrem spezifischen Interesse oder von den mathematischen Kenntnissen der Studenten auszuw¨ ahlen. Die nicht ausgew¨ahlten Kapitel oder die fortgeschrittenen Teile von behandelten Kapiteln sind nat¨ urliche Ausgangspunkte f¨ ur Kursprojekte. Studenten, die diesen Text im Selbststudium lesen, k¨onnen nach Belieben von einem Kapitel zu einem anderen springen. Jedes Kapitel ist von den anderen (mathematisch) unabh¨ angig oder nahezu unabh¨ angig, und wir weisen auf m¨ ogliche Verbindungen explizit hin. Eine letzte Bemerkung f¨ ur Hochschullehrer, die dieses Buch als Vorlesungstext verwenden. Diese Vorlesung hat uns gezwungen, unsere u adagogischen Methoden ¨blichen p¨ zu revidieren: Keines der Themen ist Vorbedingung f¨ ur weitere Kurse, die Definitionen und S¨atze sind nicht die letztlichen Vorlesungsziele, und die Aufgaben sind nicht zum Eindrillen gedacht. Diese Faktoren k¨ onnen den Studenten Sorgen bereiten. Dar¨ uber hinaus sind wir keine Spezialisten f¨ ur die von uns diskutierten Technologien. Also mussten wir unsere Lehrmethoden revidieren. Wir versuchen, die Studenten zur aktiven Teilnahme zu ermutigen. Das erm¨ oglicht es uns, ihr Hintergrundwissen in Bezug auf die verwendeten mathematischen Werkzeuge zu u ufen. Bez¨ uglich der Pr¨ ufungen tei¨berpr¨ len wir den Studenten gleich am Anfang mit, dass die Pr¨ ufungen nicht kumulativ sind und sich auf die grundlegenden Abschnitte beschr¨ anken. Die Betonung liegt auf dem ¨ einfachen mathematischen Modellieren und dem Probleml¨ osen. Unsere Ubungen konzentrieren sich auf diese Fertigkeiten.
Vorwort
ix
Verwendung des Buches zum Selbststudium Als wir diesen Text schrieben, waren wir immer sehr bestrebt, die der Technologie zugrundeliegende Mathematik darzulegen und sowohl ihre Sch¨ onheit als auch ihre Leistungsf¨ahigkeit zu demonstrieren. Wir meinen, dass dieser Text f¨ ur jeden Leser – vom jungen Wissenschaftler bis zum erfahrenen Mathematiker – von Interesse sein wird, der die Mathematik verstehen m¨ ochte, die sich hinter technologischen Neuerungen verbirgt. Da die Kapitel gr¨oßtenteils unabh¨angig voneinander sind, kann man nach Belieben von einem Thema zum anderen springen. Wir hoffen, dass auch die vielen historischen Anmerkungen auf Interesse stoßen, die u ¨berall im Text eingestreut sind, und dass der Leser ¨ vielleicht sogar die Zeit findet, einige Ubungen durchzuarbeiten. Die Beitr¨ age von H´ el` ene Antaya und Isabelle Ascah-Coallier Der erste Entwurf von Kapitel 14 u ¨ber Variationsrechnung wurde von H´el`ene Antaya geschrieben, als sie im Sommer nach dem Abschluss des zweiten Studienjahres ein Praktikum absolvierte. Kapitel 13 u ¨ber DNA-Computing wurde im nachfolgenden Sommer von H´el`ene Antaya und Isabelle Ascah-Coallier verfasst, wobei sie vom kanadischen National Sciences and Engineering Research Council (NSERC) durch einen Undergraduate Student Research Award unterst¨ utzt wurden. Zur Lekt¨ ure der Kapitel Die Kapitel sind gr¨oßtenteils unabh¨ angig voneinander. Zu Beginn eines jeden Kapitels steht eine kurze Zusammenfassung, die auf die erforderlichen Grundkenntnisse eingeht, die Beziehung zwischen den einzelnen Abschnitten und gegebenenfalls deren relative Schwierigkeit beschreibt.
Christiane Rousseau Yvan Saint-Aubin D´epartement de math´ematiques et de statistique Universit´e de Montr´eal September 2006
Danksagungen Die Entstehung der Vorlesung Mathematik und Technologie“ und des Begleittextes ge” hen bis zum Winter 2001 zur¨ uck. Wir mussten eine Vielfalt von Themen lernen, die wir ¨ nur beil¨aufig oder u und Pro¨berhaupt nicht kannten; ebenso mussten wir auch Ubungen jekte f¨ ur die Studenten zusammenstellen. Im Laufe der vielen Jahre der Ausarbeitung dieses Textes haben wir zahlreiche Fragen aufgeworfen, die ausf¨ uhrliche Erkl¨ arungen erforderten. Wir m¨ochten uns bei allen bedanken, die uns mit ihren Erl¨ auterungen unterst¨ utzt haben. Das hat dazu beigetragen, unvermeidliche Zweideutigkeiten und Fehler
x
Vorwort
zu reduzieren. F¨ ur verbleibende M¨ angel sind wir allein verantwortlich. Wir bitten die Leser, uns auf alle noch vorhandenen Fehler aufmerksam zu machen. Wir lernten eine Menge von Jean-Claude Rizzi, Martin Vachon und Annie Boily (alle von Hydro-Qu´ebec) u ¨ber Sturm-Tracking; von St´ephane Durand und Anne Bourlioux u ¨ber die Feinheiten des GPS; von Andrew Granville u ¨ber neuere Faktorisierungsalgorithmen f¨ ur ganze Zahlen; von Mehran Sahami u ¨ber die Interna von Google; von Pierre L’Ecuyer u ¨ber Zufallszahlengeneratoren; von Val´erie Poulin und Isabelle Ascah-Coallier u ¨ber die Wirkungsweise der Quantencomputer; von Serge Robert, Jean LeTourneux und Anik Souli`ere u ¨ber die Beziehung zwischen Mathematik und Musik; von Paul Rousseau und Pierre Beaudry u ¨ber die Grundlagen der Computerarchitektur; von Mark Goresky u ¨ber lineare Schieberegister und die Eigenschaften der von ihnen erzeugten Folgen. David Austin, Robert Calderbank, Brigitte Jaumard, Jean LeTourneux, Robert Moody, Pierre Poulin, Robert Roussarie, Kaleem Siddiqi und Lo¨ıc Teyssier stellten uns Literatur zur Verf¨ ugung und gaben uns wertvolle Kommentare. Viele unserer Freunde und Kollegen lasen Teile des Manuskriptes und versorgten uns mit dem entsprechenden Feedback – insbesondere danken wir Pierre Bouchard, Michel Boyer, Raymond Elmahdaoui, Alexandre Girouard, Martin Goldstein, Jean Le-Tourneux, Francis Loranger, Marie Luquette, Robert Owens, Serge Robert und Olivier Rousseau. Nicolas Beauchemin und Andr´e Montpetit halfen uns bei mehr als einer Gelegenheit mit Grafiken und mit den Feinheiten von LATEX. Unsere Kollegen Richard Duncan, Martin Goldstein und Robert Owens halfen in Bezug auf die englische Terminologie. Seit dem ersten Entwurf haben wir unser Manuskript unter Kollegen und Freunden verteilt, von denen uns viele begleitet und ermutigt haben, darunter John Ball, Jonathan Borwein, Bill Casselman, Carmen Chicone, Karl Dilcher, Freddy Dumortier, St´ephane Durand, Ivar Ekeland, Bernard Hodgson, Nassif Ghoussoub, Fr´ed´eric Gourdeau, Jacques Hurtubise, Louis Marchildon, Odile Marcotte und Pierre Mathieu. Wir danken Manfred Stern, der viele Monate an der ausgezeichneten deutschen ¨ Ubersetzung unseres Manuskripts gearbeitet hat. Es war ein großes Vergnu ¨gen, mit ihm zusammenzuarbeiten. Wir sch¨ atzen seine umsichtigen Kommentare und Vorschl¨ age.1 Wir bedanken uns bei Ann Kostant und dem Springer-Verlag f¨ ur das große Interesse an unserem Buch – von der ersten Version bis zur Endfassung. Ebenso danken wir denjenigen, die uns am n¨ achsten standen: Manuel Gim´enez, Serge Robert, Olivier Rousseau, Val´erie Poulin, Ana¨ıgue Robert und Chi-Thanh Quach. Sie haben uns immer unterst¨ utzt und uns zugehort, wenn wir im Laufe der Jahre u ¨ber dieses Projekt gesprochen haben.
1 Der Ubersetzer ¨ bedankt sich bei R¨ udiger Achilles (Fachbereich Mathematik der Universit¨ at Bologna) f¨ ur die sorgf¨ altige Korrektur des deutschen Textes. Dank f¨ ur vielf¨ altige LATEX-Hinweise und weitere technische Hilfestellungen geht an Frank Holzwarth (SpringerVerlag) und an Gerd Richter (Fachbereich Mathematik der Universit¨ at Halle). Ebenso danke ich Ruth Allewelt und Agnes Herrmann (beide Springer-Verlag) f¨ ur ihre Begleitung ¨ beim Anfertigen der Ubersetzung. Manfred Stern, Halle a. d. Saale, M¨ arz 2012
Inhaltsverzeichnis
Vorwort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
v
1
Positionsbestimmung auf der Erde und im Raum . . . . . . . . . . . . . . . . . . 1.1 Einf¨ uhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Global Positioning System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Einige Fakten u ¨ber das GPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Die Theorie hinter GPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Die Behandlung praktischer Schwierigkeiten . . . . . . . . . . . . . . . . . . 1.3 Blitz und Donner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Die Ortung von Blitzschl¨ agen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Detektionsschwelle und Detektionsqualit¨ at . . . . . . . . . . . . . . . . . . . . 1.3.3 Langfristiges Risikomanagement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Lineare Schieberegister . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 Die Struktur des K¨orpers Fr2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2 Beweis von Satz 1.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Kartografie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¨ 1.6 Ubungen ....................................................... Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 1 2 2 3 7 13 13 17 20 21 24 26 29 39 46
2
Friese und Mosaike . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Friese und Symmetrien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Symmetriegruppen und affine Transformationen . . . . . . . . . . . . . . . . . . . . . 2.3 Der Klassifikationssatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Mosaike . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¨ 2.5 Ubungen ....................................................... Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47 50 55 62 68 72 88
xii
Inhaltsverzeichnis
3
Roboterbewegung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Einf¨ uhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Bewegung eines Festk¨ orpers in der Ebene . . . . . . . . . . . . . . . . . . . . . 3.1.2 Einige Gedanken u ¨ber die Anzahl der Freiheitsgrade . . . . . . . . . . . 3.2 L¨angen- und winkeltreue Bewegungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Eigenschaften orthogonaler Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Basiswechsel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Verschiedene Bezugssysteme f¨ ur einen Roboter . . . . . . . . . . . . . . . . . . . . . . ¨ 3.6 Ubungen ....................................................... Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89 89 92 94 95 99 108 111 117 123
4
Skelette und Gammastrahlen-Radiochirurgie . . . . . . . . . . . . . . . . . . . . . . 4.1 Einf¨ uhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Definition des Skeletts zweidimensionaler Bereiche . . . . . . . . . . . . . . . . . . . 4.3 Dreidimensionale Bereiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Der optimale chirurgische Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Ein numerischer Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.1 Erster Teil des Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.2 Zweiter Teil des Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.3 Beweis von Proposition 4.17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Weitere Anwendungen von Skeletten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Die Fundamentaleigenschaft des Skeletts . . . . . . . . . . . . . . . . . . . . . . . . . . . ¨ 4.8 Ubungen ....................................................... Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
125 125 126 137 140 142 143 147 148 150 151 156 161
5
Sparen und Kredite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Bankvokabular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Zinseszins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Ein Sparplan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Kreditaufnahme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Anhang: Tafeln zur Hypothekenzahlung . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¨ 5.6 Ubungen ....................................................... Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
163 164 164 167 170 173 176 179
6
Fehlerkorrigierende Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 Einf¨ uhrung: Digitalisieren, Erkennen und Korrigieren . . . . . . . . . . . . . . . . 6.2 Der endliche K¨ orper F2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Der (7, 4)-Hamming-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 (2k − 1, 2k − k − 1)-Hamming-Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Endliche K¨ orper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 Reed-Solomon-Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.7 Anhang: Das Skalarprodukt und endliche K¨ orper . . . . . . . . . . . . . . . . . . . . ¨ 6.8 Ubungen ....................................................... Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
181 181 186 188 191 194 203 208 210 218
Inhaltsverzeichnis
xiii
7
Kryptografie mit ¨ offentlichem Schl¨ ussel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1 Einf¨ uhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Einige Werkzeuge aus der Zahlentheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Die Idee hinter RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Konstruktion großer Primzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5 Der Shor-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¨ 7.6 Ubungen ....................................................... Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
219 219 221 224 232 243 247 252
8
Zufallszahlengeneratoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1 Einf¨ uhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Lineare Schieberegister . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Fp -lineare Generatoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.1 Der Fall p = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.2 Eine Lektion u ¨ber Spielautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.3 Der allgemeine Fall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4 Kombinierte mehrfach rekursive Generatoren . . . . . . . . . . . . . . . . . . . . . . . 8.5 Schlussfolgerung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¨ 8.6 Ubungen ....................................................... Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
253 253 258 261 261 266 267 268 271 271 278
9
Google und der PageRank -Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1 Suchmaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 Das Web und Markow-Ketten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3 Ein verbesserter PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.4 Der Satz von Frobenius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¨ 9.5 Ubungen ....................................................... Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
279 279 282 293 296 300 304
10 Warum 44 100 Abtastungen pro Sekunde? . . . . . . . . . . . . . . . . . . . . . . . . . 10.1 Einf¨ uhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2 Die Tonleiter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.3 Der letzte Ton (Eine Einf¨ uhrung in die Fourier-Analyse) . . . . . . . . . . . . . . 10.4 Die Nyquist-Frequenz und der Grund f¨ ur 44 100 . . . . . . . . . . . . . . . . . . . . . ¨ 10.5 Ubungen ....................................................... Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
305 305 306 311 323 333 340
11 Bildkompression: Iterierte Funktionensysteme . . . . . . . . . . . . . . . . . . . . . 11.1 Einf¨ uhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Affine Transformationen in der Ebene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3 Iterierte Funktionensysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.4 Iterierte Kontraktionen und Fixpunkte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.5 Der Hausdorff-Abstand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
341 341 344 347 353 358
xiv
Inhaltsverzeichnis
11.6 Fraktale Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.7 Fotos als Attraktoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¨ 11.8 Ubungen ....................................................... Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
363 370 381 386
12 Bildkompression: Der JPEG-Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.1 Einf¨ uhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.2 Vergr¨oßern eines mit JPEG komprimierten Digitalbildes . . . . . . . . . . . . . . 12.3 Der Fall der 2 × 2-Bl¨ ocke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.4 Der Fall der N × N -Bl¨ ocke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.5 Der JPEG-Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¨ 12.6 Ubungen ....................................................... Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
387 387 391 392 397 408 417 422
13 Der 13.1 13.2 13.3
DNA-Computer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Einf¨ uhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Adlemans Hamiltonpfad-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Turingmaschinen und rekursive Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . 13.3.1 Turingmaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.3.2 Primitiv-rekursive Funktionen und rekursive Funktionen . . . . . . . 13.4 Turingmaschinen und Insertion-Deletion-Systeme . . . . . . . . . . . . . . . . . . . . 13.5 NP-vollst¨andige Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.5.1 Das Hamiltonpfad-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.5.2 Erf¨ ullbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.6 Mehr u ¨ber DNA-Computer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.6.1 Das Hamiltonpfad-Problem und Insertion-Deletion-Systeme . . . . . 13.6.2 Die gegenw¨ artigen Schranken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.6.3 Einige biologische Erkl¨arungen zu Adlemans Experiment . . . . . . . ¨ 13.7 Ubungen ....................................................... Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
423 424 426 430 430 437 449 453 453 454 458 458 459 461 465 470
14 Variationsrechnung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.1 Das Fundamentalproblem der Variationsrechnung . . . . . . . . . . . . . . . . . . . . 14.2 Die Euler-Lagrange-Gleichung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.3 Das Fermat-Prinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.4 Die beste Halfpipe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.5 Der schnellste Tunnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.6 Die Tautochronen-Eigenschaft der Zykloide . . . . . . . . . . . . . . . . . . . . . . . . . 14.7 Ein isochrones Pendel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.8 Seifenblasen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.9 Das Hamilton-Prinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.10 Isoperimetrische Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.11 Fl¨ ussigspiegel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
471 472 476 480 482 485 491 494 497 501 505 513
Inhaltsverzeichnis
xv
¨ 14.12 Ubungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518 Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526 15 Science Flashes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.1 Das Reflexionsgesetz und das Brechungsgesetz . . . . . . . . . . . . . . . . . . . . . 15.2 Einige Anwendungen der Kegelschnitte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.2.1 Eine bemerkenswerte Eigenschaft der Parabel . . . . . . . . . . . . . . . . 15.2.2 Die Ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.2.3 Die Hyperbel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.2.4 Ein paar clevere Werkzeuge zum Zeichnen von Kegelschnitten . . 15.3 Quadratische Fl¨achen in der Architektur . . . . . . . . . . . . . . . . . . . . . . . . . . 15.4 Optimale Positionierung von Mobilfunkantennen . . . . . . . . . . . . . . . . . . . 15.5 Voronoi-Diagramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.6 Computer Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.7 Ein kurzer Blick auf die Computerarchitektur . . . . . . . . . . . . . . . . . . . . . . 15.8 Regul¨are F¨ unfeckparkettierung der Kugeloberfl¨ ache . . . . . . . . . . . . . . . . . 15.9 Planung einer Autobahn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¨ 15.10 Ubungen ...................................................... Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
527 527 534 534 545 547 548 549 556 560 565 567 573 580 582 597
Personen- und Sachverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599
1 Positionsbestimmung auf der Erde und im Raum
Dieses Kapitel ist das beste Beispiel im Buch, wie verschieden die Anwendungen der Mathematik auf eine einfache technische Frage sein k¨ onnen: Wie kann man Menschen oder Ereignisse auf der Erde orten? Die Vielfalt der Anwendungen ist u ¨berraschend, und aus diesem Grund ist es vielleicht eine gute Idee, mehr als eine Woche f¨ ur dieses Kapitel zu verwenden. Zwei Stunden reichen, um die Theorie zu erl¨ autern, die sich hinter GPS verbirgt (Abschnitt 1.2) und kurz darauf einzugehen, wie man GPS auf das sogenannte Sturm-Tracking (Abschnitt 1.3) anwenden kann. Sp¨ ater muss eine Auswahl erfolgen. Falls Sie bereits endliche K¨ orper in Kapitel 6 u ¨ber fehlerkorrigierende Codes oder in Kapitel 8 u uhrt haben, dann l¨ asst ¨ber Zufallszahlengeneratoren eingef¨ sich die Wirkungsweise des GPS-Signals in etwas mehr als einer Stunde behandeln, da ¨ Sie den Uberblick u orper u onnen. Ist die Zeit beschr¨ ankt ¨ber endliche K¨ ¨berspringen k¨ und sind endliche K¨ orper noch nicht eingef¨ uhrt worden, dann besteht ein vern¨ unftiger Kompromiss darin, einfach nur Satz 1.4 anzugeben und ihn anhand einiger Beispiele zu illustrieren, etwa durch Beispiel 1.5. Abschnitt 1.5 u ¨ber Kartografie erfordert ein Minimum von zwei Stunden, sofern die Studenten den Begriff der konformen (also winkeltreuen) Abbildung noch nicht kennen. Abschnitt 1.2 erfordert nur euklidische Geometrie und Grundkenntnisse in linearer Algebra, w¨ ahrend Abschnitt 1.3 elementare Begriffe der Wahrscheinlichkeitstheorie verwendet. Abschnitt 1.4 ist schwieriger, falls endliche K¨ orper noch nicht bekannt sind. Abschnitt 1.5 verwendet Funktionen in mehreren Variablen.
1.1 Einfu ¨ hrung Seit jeher haben sich die Menschen daf¨ ur interessiert, ihre Position auf der Erde zu bestimmen. Sie begannen mit primitiven Instrumenten, navigierten mit Hilfe des Magnetkompasses, verwendeten das Astrolab und sp¨ ater den Sextanten. In der j¨ ungsten Geschichte wurden bedeutend komplexere und genauere Navigationshilfen entwickelt,
C. Rousseau, Y. Saint-Aubin, Mathematik und Technologie, DOI 10.1007/978-3-642-30092-9_1, © Springer-Verlag Berlin Heidelberg 2012
2
1 Positionsbestimmung auf der Erde und im Raum
zum Beispiel das Global Positioning System (GPS). In diesem Kapitel gehen wir zeitlich r¨ uckw¨arts vor: Wir beginnen mit der Erl¨ auterung des neuzeitlichen GPS und daran ¨ schließt sich – zumeist in den Ubungen – eine kurze Diskussion alter Techniken an. Diese Navigationstechniken sind nur dann wirklich n¨ utzlich, wenn wir genaue Landkarten haben. Deswegen widmen wir der Kartografie einen Abschnitt. Da die Erde eine Kugel ist, erweist es sich als unm¨ oglich, sie auf einem Blatt Papier so darzustellen, dass Winkel, Abstandsverh¨ altnisse und Fl¨achenverh¨altnisse erhalten bleiben. Der gew¨ ahlte Kompromiss h¨angt gr¨ oßtenteils von der Anwendung ab. Der Peters-Atlas verwendet Projektionen, bei denen Fl¨ achenverh¨ altnisse erhalten bleiben [2]. Bei Seekarten werden dagegen Projektionen verwendet, bei denen Winkel erhalten bleiben.
1.2 Global Positioning System 1.2.1 Einige Fakten u ¨ ber das GPS Die GPS-Satellitenkonstellation wurde im Juli 1995 durch das Verteidigungsministerium der USA fertiggestellt, das auch den ¨ offentlichen Gebrauch genehmigte. Bei der ersten Stationierung bestand das System aus 24 Satelliten, von denen mindestens 21 mehr als 98% der Zeit funktionst¨ uchtig sein sollten. 2005 bestand das System aus 32 Satelliten, von denen mindestens 24 funktionst¨ uchtig sein sollten, w¨ ahrend die anderen f¨ ur ihren Einsatz bereitstehen, falls einer der letztgenannten Satelliten versagt. Die Satelliten befinden sich in einer Entfernung von 20200 km von der Erdoberfl¨ ache. Sie ¨ sind u um ¨ber 6 Orbitalebenen verteilt, von denen jede in Bezug auf die Aquatorialebene einen Winkel von 55 Grad geneigt ist (vgl. Abbildung 1.1). Es gibt pro Orbitalebene mindestens 4 Satelliten, die ungef¨ ahr gleich weit voneinander entfernt sind. Jeder Satellit umkreist die Erde in 11 Stunden und 58 Minuten. Die Satelliten sind so positioniert, dass wir zu jeder Zeit und an jedem Ort auf der Erde mindestens 4 Satelliten beobachten k¨onnen. Die 24 Satelliten senden ein Signal, das sich periodisch wiederholt und mit Hilfe eines speziellen Empf¨angers empfangen werden kann. Wenn wir ein Navi kaufen, dann kaufen wir in Wirklichkeit ein Ger¨ at, das wir als Empf¨ anger bezeichnen, weil es die GPS-Signale empf¨angt und die darin enthaltenen Informationen dazu verwendet, seinen Standort zu berechnen. Das Ger¨ at enth¨alt einen Almanach, der zu jedem gegebenen Zeitpunkt die absolute Position eines jeden Satelliten berechnen kann. Da jedoch geringf¨ ugige Fehler in den Umlaufbahnen unvermeidlich sind, wird f¨ ur jeden Satelliten unmittelbar in dem gesendeten Signal eine Korrekturinformation codiert (diese Korrekturinformation wird st¨ undlich aktualisiert). Jeder Satellit sendet sein Signal kontinuierlich. Die Signalperiode ist festgelegt und die Anfangszeit des Zyklus kann durch die Verwendung des Almanachs bestimmt werden. Zus¨atzlich ist jeder Satellit mit einer extrem genauen Atomuhr ausgestattet, die es erm¨oglicht, dass der Satellit zu den im Almanach enthaltenen Anfangszeiten synchronisiert bleibt. Zeichnet ein Empf¨ anger ein Signal von einem Satelliten auf, dann werden sofort die Signale der verschiedenen Satelliten erzeugt und
1.2 Global Positioning System
3
Abb. 1.1. Die 24 Satelliten auf 6 Orbitalebenen.
mit den erhaltenen Signalen verglichen. Im Allgemeinen stimmen diese Signale nicht sofort u anger die von ihm erzeugte Kopie, bis sie ¨berein. Folglich verschiebt der Empf¨ mit dem empfangenen Signal in Phase ist (das erfolgt durch Berechnung der Korrelation zwischen den beiden Signalen). Auf diese Weise ist das Ger¨ at dazu in der Lage, die Laufzeit zu berechnen, die das Signal vom Satelliten aus ben¨ otigt. Wir werden dieses System in Abschnitt 1.4 viel ausf¨ uhrlicher besprechen. Das oben beschriebene System ist das Standardpr¨ azisions-GPS. Sind keine anspruchsvolleren Bodenkorrekturen vorhanden, dann erm¨ oglicht dieses System die Berechnung der Empf¨angerposition bis zu einer Genauigkeit von ungef¨ ahr 20 Metern. Vor Mai 2000 f¨ uhrte das US-Verteidigungsministerium absichtlich Ungenauigkeiten in die Satellitensignale ein, um die Genauigkeit des Systems auf 100 Meter zu verringern. 1.2.2 Die Theorie hinter GPS Wie berechnet der Empf¨ anger seine Position? Wir beginnen mit der Annahme, dass die Uhren des Empf¨ angers und s¨ amtlicher Satelliten perfekt synchronisiert sind. Der Empf¨anger berechnet seine Position durch Triangulation. Das Grundprinzip der Triangulationsmethoden besteht in der Standortbestimmung einer Person (eines Objekts) durch die Verwendung von Informationen, welche die Position der Person (des Objekts) auf Referenzobjekte bezieht, deren Positionen bekannt sind. Im Falle des GPSEmpf¨angers wird die Entfernung zu den Satelliten berechnet, deren Positionen bekannt sind. •
Der Empf¨anger misst die Zeit t1 , die das vom Satelliten P1 gesendete Signal bis zum Empf¨anger ben¨otigt. Da das Signal mit Lichtgeschwindigkeit c u ¨bertragen wird, kann der Empf¨anger seine Entfernung vom Satelliten als r1 = ct1 berechnen. Die Menge der Punkte, die den Abstand r1 vom Satelliten P1 haben, bildet eine Kugel S1 mit Mittelpunkt P1 und Radius r1 . Wir wissen also jetzt, dass sich der Empf¨ anger auf S1 befindet. Wir denken uns diese Punkte als in einem kartesischen Koordinatensystem
4
1 Positionsbestimmung auf der Erde und im Raum
definiert. Es sei (x, y, z) die unbekannte Position des Empf¨ angers und (a1 , b1 , c1 ) die ullen, die bekannte Position des Satelliten P1 . Dann muss (x, y, z) die Gleichung erf¨ amlich Punkte auf der Kugel S1 beschreibt, n¨ (x − a1 )2 + (y − b1 )2 + (z − c1 )2 = r12 = c2 t21 . •
(1.1)
Diese Information reicht nicht aus, um die genaue Position des Empf¨ angers zu bestimmen. Deswegen zeichnet der Empf¨ anger das Signal eines zweiten Satelliten P2 auf, das heißt, er zeichnet die Laufzeit t2 des Signals auf und berechnet die Entfernung r2 = ct2 zum Satelliten. Wie zuvor muss der Empf¨ anger auf der Kugel S2 mit dem Radius r2 und dem Mittelpunkt (a2 , b2 , c2 ) liegen: (x − a2 )2 + (y − b2 )2 + (z − c2 )2 = r22 = c2 t22 .
(1.2)
Das engt unsere Suche ein, denn der Durchschnitt zweier u ¨berlappender Kugeln ist ein Kreis. Wir haben also jetzt die Position des Empf¨ angers auf einen Kreis C1,2 eingeengt, auf dem der Empf¨ anger liegen muss. Jedoch wissen wir immer noch nicht genau, wo sich der Empf¨ anger auf diesem Kreis befindet. • Damit der Empf¨ anger seine endg¨ ultige Position berechnen kann, muss er die Signale anger die eines dritten Satelliten P3 erfassen und verarbeiten. Erneut misst der Empf¨ Laufzeit t3 des Signals und berechnet den Abstand r3 = ct3 von diesem Satelliten. Wieder folgt, dass der Empf¨anger irgendwo auf der Kugel S3 mit Radius r3 und Mittelpunkt (a3 , b3 , c3 ) liegt: (x − a3 )2 + (y − b3 )2 + (z − c3 )2 = r32 = c2 t23 .
(1.3)
Der Empf¨anger befindet sich deswegen auf dem Durchschnitt des Kreises C1,2 und der Kugel S3 . Da sich eine Kugel und ein (nicht auf ihr liegender) Kreis in zwei Punkten schneiden, hat es den Anschein, dass wir uns der Position des Empf¨ angers immer noch nicht sicher sein k¨ onnen. Gl¨ ucklicherweise ist das jedoch nicht der Fall. Tats¨achlich sind die Satelliten so positioniert worden, dass eine der beiden L¨ osungen vollkommen unrealistisch ist, da der entsprechende Standort zu weit von der Erdoberfl¨ache entfernt ist. Demnach kann der Empf¨ anger seine genaue Position berechnen, indem er die beiden L¨ osungen des aus den Gleichungen (1.1), (1.2) und (1.3) bestehenden Gleichungssystems (∗) findet und anschließend die unzutreffende L¨osung eliminiert. L¨ osung des Systems (∗). Die Gleichungen des Systems (∗) sind nicht linear, sondern quadratisch, was die L¨ osung kompliziert. Vielleicht haben Sie aber Folgendes bemerkt: Subtrahieren wir eine der Gleichungen von einer anderen, dann erhalten wir eine lineare Gleichung, da sich die Terme x2 , y 2 und z 2 aufheben. Also ersetzen wir das System (∗) durch ein ¨aquivalentes System, das wir erhalten, wenn wir die erste Gleichung durch (1.1)−(1.3) und die zweite Gleichung durch (1.2)−(1.3) ersetzen und die dritte Gleichung beibehalten. Das f¨ uhrt zum System
1.2 Global Positioning System
2(a3 − a1 )x + 2(b3 − b1 )y + 2(c3 − c1 )z = A1 ,
(1.4)
2(a3 − a2 )x + 2(b3 − b2 )y + 2(c3 − c2 )z = A2 , (x − a3 ) + (y − b3 ) + (z − c3 ) = 2
2
2
r32
=
5
(1.5) c2 t23 ,
(1.6)
wobei A1 A2
c2 (t21 − t23 ) + (a23 − a21 ) + (b23 − b21 ) + (c23 − c21 ), c2 (t22 − t23 ) + (a23 − a22 ) + (b23 − b22 ) + (c23 − c22 ).
= =
(1.7)
Die Satelliten sind so positioniert worden, dass niemals drei Satelliten auf einer Geraden liegen. Diese Eigenschaft garantiert, dass mindestens eine der 2 × 2-Determinanten a3 − a1 b3 − b1 a3 − a1 c3 − c1 b3 − b1 c3 − c1 , , a3 − a2 b3 − b2 a3 − a2 c3 − c2 b3 − b2 c3 − c2 von null verschieden ist. Sind n¨ amlich alle drei Determinanten gleich null, dann sind die Vektoren (a3 −a1 , b3 −b1 , c3 −c1 ) und (a3 −a2 , b3 −b2 , c3 −c2 ) kollinear (ihr Kreuzprodukt ist null) und das impliziert, dass die drei Punkte P1 , P2 und P3 auf einer Geraden liegen. Wir nehmen an, dass die erste Determinante von null verschieden ist. Unter Verwendung der Cramer’schen Regel liefern uns die ersten beiden Gleichungen von (1.6) L¨osungen f¨ ur x und y als Funktion von z:
x
y
=
=
A1 A2
− 2(c3 − c1 )z 2(b3 − b1 ) − 2(c3 − c2 )z 2(b3 − b2 ) , 2(a3 − a1 ) 2(b3 − b1 ) 2(a3 − a2 ) 2(b3 − b2 )
2(a3 − a1 ) A1 2(a3 − a2 ) A2 2(a3 − a1 ) 2(a3 − a2 )
− 2(c3 − c1 )z − 2(c3 − c2 )z . 2(b3 − b1 ) 2(b3 − b2 )
(1.8)
Setzen wir diese Werte in die dritte Gleichung von (1.6) ein, dann erhalten wir eine quadratische Gleichung in z, die wir l¨ osen k¨ onnen, um die beiden L¨ osungen z1 und z2 zu finden. Durch R¨ ucksubstitution von z f¨ ur die Werte z1 und z2 in den beiden obigen onnten leicht Gleichungen erhalten wir die entsprechenden Werte x1 , x2 , y1 und y2 . Wir k¨ auch geschlossene Ausdr¨ ucke f¨ ur diese L¨osungen finden, aber die dabei verwendeten Formeln werden rasch zu groß und un¨ ubersichtlich, so dass sie weder verst¨ andlicher werden noch praktischer zu handhaben sind. Auswahl der Achsen unseres Koordinatensystems. In der obigen Diskussion haben wir an keiner Stelle irgendwelche Achsen f¨ ur unser Koordinatensystem gew¨ ahlt, ¨ und wir waren dazu auch nicht gezwungen. Um jedoch die Ubersetzung von absoluten Koordinaten in L¨ange, Breite und H¨ohe zu erleichtern, treffen wir folgende Wahl:
6
1 Positionsbestimmung auf der Erde und im Raum
• der Ursprung des Koordinatensystems ist der Erdmittelpunkt; • die z-Achse geht durch die beiden Pole und ist zum Nordpol gerichtet; ¨ • die x-Achse und die y-Achse liegen beide in der Aquatorialebene; • die positive x-Achse geht durch den Nullmeridian; • die positive y-Achse geht durch den Meridian von 90 Grad o ange. ¨stlicher L¨ Da der Erdradius R eine L¨ ange von ca. 6365 km hat, wird eine L¨ osung (xi , yi , zi ) als akzeptabel betrachtet, wenn x2i + yi2 + zi2 ≈ (6365 ± 50)2 . Die Unsicherheit von 50 km gestattet ein Fenster f¨ ur die H¨ ohen von Gebirgen und Flugh¨ ohen von Flugzeugen. Ein nat¨ urlicheres Koordinatensystem f¨ ur Punkte nahe der Erdoberfl¨ ache besteht aus der L¨ange L, der Breite l und dem Abstand h vom Erdmittelpunkt (die H¨ ohe u ¨ber dem Meeresspiegel ist deswegen durch h − R gegeben). L¨ange und Breite sind Winkel, die in Grad ausgedr¨ uckt werden. Liegt ein Punkt (x, y, z) genau auf einer Kugel mit Radius R (mit anderen Worten, liegt der Punkt auf der H¨ ohe null), dann kann man seine L¨ ange und Breite durch L¨ osen des folgenden Gleichungssystems finden: x y z
= R cos L cos l, = R sin L cos l, = R sin l.
(1.9)
Wegen l ∈ [−90◦ , 90◦ ] erhalten wir l = arcsin
z , R
(1.10)
was uns die Berechnung von cos l erm¨ oglicht. Die L¨ ange L folgt demnach eindeutig aus den beiden Gleichungen ⎧ x ⎪ cos L = , ⎪ ⎨ R cos l (1.11) ⎪ y ⎪ ⎩sin L = . R cos l Berechnung der Position des Empf¨ angers. Es sei (x, y, z) die Position des Empf¨ angers. Wir berechnen zun¨ achst den Abstand h des Empf¨ angers vom Erdmittelpunkt; dieser Abstand ist durch h = x2 + y 2 + z 2 gegeben. Wir haben nun zwei M¨ oglichkeiten zur Berechnung der Breite und der L¨ ange: Modifikation der Formeln (1.10) und (1.11), indem wir R u ¨berall durch h ersetzen, oder Projektion der Position (x, y, z) auf die Kugeloberfl¨ache und Verwendung dieser Werte in den Gleichungen (1.10) und (1.11): R R R . (x0 , y0 , z0 ) = x , y , z h h h Die H¨ohe des Empf¨angers ist durch h − R gegeben.
1.2 Global Positioning System
7
1.2.3 Die Behandlung praktischer Schwierigkeiten Wir haben gerade die Theorie besprochen, die hinter der Positionsberechnung steht, wobei wir aber von einer perfekten Welt ausgegangen sind. Leider ist das wirkliche Leben sehr viel komplizierter, denn die gemessenen Zeiten sind extrem kurz und m¨ ussen mit hoher Pr¨azision gemessen werden. Alle Satelliten sind mit einer hochpr¨ azisen (und teuren!) Atomuhr ausgestattet, wodurch eine (nahezu) perfekte Synchronisation m¨ oglich ist. Inzwischen ist der durchschnittliche Empf¨ anger typischerweise mit einer nur mittelm¨aßigen Uhr ausgestattet und deswegen fast f¨ ur jeden erschwinglich. Unter der Voraussetzung, dass die Uhren der Satelliten synchron sind, kann der Empf¨ anger m¨ uhelos die genauen Laufzeiten der von den Satelliten kommenden Signale berechnen. Da jedoch der Empf¨anger nicht vollkommen synchron ist, berechnet er in Wirklichkeit drei fiktive Laufzeiten T1 , T2 und T3 . Wie gehen wir mit diesen ungenauen Messungen um? Als wir drei Unbekannte x, y, z hatten, brauchten wir drei Messzeiten t1 , t2 , t3 , um die Unbekannten zu finden. Jetzt ist die vom Empf¨ anger gemessene fiktive Zeit durch Ti
=
(Eingangszeit des Signals auf der Empf¨ angeruhr) − (Ausgangszeit des Signals auf der Satellitenuhr)
gegeben. Die L¨osung besteht darin, dass der Fehler zwischen der vom Empf¨ anger beur alle Satelliten der gleiche ist. rechneten fiktiven Zeit Ti und der tats¨achlichen Zeit ti f¨ ur i = 1, 2, 3, wobei Das heißt, Ti = τ + ti f¨ ti
=
(Eingangszeit des Signals auf der Satellitenuhr) − (Ausgangszeit des Signals auf der Satellitenuhr)
und τ durch folgende Gleichung gegeben ist: τ
=
(Eingangszeit des Signals auf der Empf¨ angeruhr) − (Eingangszeit des Signals auf der Satellitenuhr).
(1.12)
Die Konstante τ ist der sogenannte Uhrenfehler (clock offset), das heißt, die Zeitdifferenz zwischen den Satellitenuhren und der Empf¨angeruhr. Das f¨ uhrt die vierte Unbekannte τ in unser urspr¨ ungliches System x, y, z von drei Unbekannten ein. Um f¨ ur das Gleichungssystem eine endliche L¨osungsmenge zu finden, m¨ ussen wir eine vierte Gleichung aufstellen. Das l¨ asst sich in unserem Kontext m¨ uhelos bewerkstelligen: Der Empf¨anger misst einfach die fiktive Signallaufzeit T4 zwischen ihm und einem vierten Satelliten P4 . Wegen ti = Ti − τ for i = 1, . . . , 4 wird unser System dann zu (x − a1 )2 + (y − b1 )2 + (z − c1 )2 (x − a2 )2 + (y − b2 )2 + (z − c2 )2 (x − a3 )2 + (y − b3 )2 + (z − c3 )2 (x − a4 )2 + (y − b4 )2 + (z − c4 )2
= = = =
c2 (T1 − τ )2 , c2 (T2 − τ )2 , c2 (T3 − τ )2 , c2 (T4 − τ )2 .
(1.13)
In diesem System haben wir die vier Unbekannten x, y, z und τ . Wie oben k¨ onnen wir mit Hilfe von elementaren Operationen drei dieser quadratischen Gleichungen durch
8
1 Positionsbestimmung auf der Erde und im Raum
lineare Gleichungen ersetzen. Hierzu subtrahieren wir die vierte Gleichung von jeder der ersten drei Gleichungen und erhalten 2(a4 − a1 )x + 2(b4 − b1 )y + 2(c4 − c1 )z 2(a4 − a2 )x + 2(b4 − b2 )y + 2(c4 − c2 )z 2(a4 − a3 )x + 2(b4 − b3 )y + 2(c4 − c3 )z (x − a4 )2 + (y − b4 )2 + (z − c4 )2
= = = =
2c2 τ (T4 − T1 ) + B1 , 2c2 τ (T4 − T2 ) + B2 , 2c2 τ (T4 − T3 ) + B3 , c2 (T4 − τ )2 ,
(1.14)
wobei B1 B2 B3
= = =
c2 (T12 − T42 ) + (a24 − a21 ) + (b24 − b21 ) + (c24 − c21 ), c2 (T22 − T42 ) + (a24 − a22 ) + (b24 − b22 ) + (c24 − c22 ), c2 (T32 − T42 ) + (a24 − a23 ) + (b24 − b23 ) + (c24 − c23 ).
(1.15)
Im Gleichungssystem (1.14) wenden wir die Cramersche Regel auf die ersten drei Gleichungen an und k¨onnen dadurch die Werte f¨ ur x, y und z als Funktion von τ bestimmen:
x
y
z
=
2c2 τ (T − T ) + 4 1 2 2c τ (T − T ) + 4 2 2 2c τ (T4 − T3 ) + 2(a4 − a1 ) 2(a − a ) 4 2 2(a4 − a3 )
=
2(a − a ) 4 1 2(a − a ) 4 2 2(a4 − a3 ) 2(a − 4 2(a − 4 2(a4 −
=
2(a 4 2(a 4 2(a4
B1 2(b4 − b1 ) 2(c4 − c1 ) B2 2(b4 − b2 ) 2(c4 − c2 ) B3 2(b4 − b3 ) 2(c4 − c3 ) , 2(b4 − b1 ) 2(c4 − c1 ) 2(b4 − b2 ) 2(c4 − c2 ) 2(b4 − b3 ) 2(c4 − c3 )
2c2 τ (T4 − T1 ) + B1 2(c4 − c1 ) 2c2 τ (T4 − T2 ) + B2 2(c4 − c2 ) 2 2c τ (T4 − T3 ) + B3 2(c4 − c3 ) , a1 ) 2(b4 − b1 ) 2(c4 − c1 ) a2 ) 2(b4 − b2 ) 2(c4 − c2 ) a3 ) 2(b4 − b3 ) 2(c4 − c3 )
− a1 ) 2(b4 − b1 ) 2c2 τ (T4 − T1 ) + B1 − a2 ) 2(b4 − b2 ) 2c2 τ (T4 − T2 ) + B2 − a3 ) 2(b4 − b3 ) 2c2 τ (T4 − T3 ) + B3 2(a − a ) 2(b − b ) 2(c − c ) 4 1 4 1 4 1 2(a − a ) 2(b − b ) 2(c − c ) 4 2 4 2 4 2 2(a4 − a3 ) 2(b4 − b3 ) 2(c4 − c3 )
(1.16)
.
Diese Ausdr¨ ucke haben nur dann einen Sinn, wenn der Nenner von null verschieden ist. Der Nenner ist aber dann und nur dann gleich null, wenn sich die vier Satelliten in der ¨ gleichen Ebene befinden (vgl. Ubung 1). Wie schon bemerkt, werden die Satelliten so positioniert, dass keine vier von ihnen, die von einem gegebenen Punkt der Erde aus sichtbar sind, in der gleichen Ebene liegen. Wir setzen die L¨ osungen der ersten drei Gleichungen in die vierte ein, was zu einer letzten quadratischen Gleichung in τ f¨ uhrt,
1.2 Global Positioning System
9
die zwei L¨osungen τ1 und τ2 hat. Die R¨ ucksubstitution dieser Werte in (1.16) liefert zwei m¨ogliche Positionen f¨ ur den Empf¨ anger, und wir wenden den gleichen Trick wie oben an, um die Nebenl¨osung zu eliminieren. Welche Satelliten sollte der Empf¨ anger w¨ ahlen, wenn er mehr als vier sehen kann? In diesem Fall hat der Empf¨ anger eine Wahlm¨ oglichkeit, welche Daten bei den Berechnungen verwendet werden k¨ onnen. Es ist sinnvoll, diejenigen Daten zu verwenden, die zu einem Minimum an Fehlern f¨ uhren. In der Realit¨ at sind alle Zeitmessungen approximativ. Grafisch k¨onnten wir den Unsicherheitsbereich durch eine Verdickung der Kugelschalen darstellen. Der Durchschnitt der verdickten Kugeln wird dann eine Menge, deren Gr¨oße zur Unsicherheit der L¨ osung in Beziehung steht. Geometrisch betrachtet k¨onnen wir uns leicht von folgender Tatsache u oßer der Winkel zwi¨berzeugen: Je gr¨ schen den Oberfl¨achen zweier sich schneidender verdickter Kugeln ist, desto kleiner ist das Volumen dieses Durchschnitts. Umgekehrt gilt: Schneiden sich die Kugeln fast tangential, dann ist das Schnittvolumen (und somit die Unsicherheit) gr¨ oßer. Also w¨ ahlen wir die Kugeln Si so, dass sie einander in einem m¨ oglichst großen Winkel schneiden (vgl. Abbildung 1.2).
Abb. 1.2. Ein kleiner Schnittwinkel links (Genauigkeitsverlust) und ein großer Schnittwinkel rechts.
Das ist die geometrische Intuition, die hinter unserer Wahl steht. Algebraisch sehen wir, dass sich die Werte von x, y und z (ausgedr¨ uckt durch τ ) ergeben, wenn man durch 2(a4 − a1 ) 2(b4 − b1 ) 2(c4 − c1 ) 2(a4 − a2 ) 2(b4 − b2 ) 2(c4 − c2 ) 2(a4 − a3 ) 2(b4 − b3 ) 2(c4 − c3 ) dividiert. Je kleiner der Nenner ist, desto gr¨ oßer ist der Fehler. Also w¨ ahlen wir diejenigen vier Satelliten, die diesen Nenner maximieren. Fortgeschrittenere Untersuchungen zu diesem Thema ließen sich leicht zu einem Kursprojekt ausbauen.
10
1 Positionsbestimmung auf der Erde und im Raum
Einige Verfeinerungen: •
•
•
•
•
Differential-GPS (DGPS): Eine Quelle der Ungenauigkeit beim GPS ist auf die Tatsache zur¨ uckzuf¨ uhren, dass Entfernungen zu den Satelliten unter Verwendung der Konstanten c berechnet werden, welche die Vakuumlichtgeschwindigkeit bezeichnet. In Wirklichkeit breitet sich das Signal aber durch die Atmosph¨ are aus und wird dort gebrochen – ein Umstand, der sowohl die Bahn des Signals verl¨ angert als auch dessen Geschwindigkeit verringert. Wir k¨ onnen ein Differential-GPS verwenden, um eine bessere Approximation an die tats¨ achliche Durchschnittsgeschwindigkeit des Signals auf dessen Weg vom Satelliten zum Empf¨anger zu erzielen. Die Idee besteht darin, den zu verwendenden Wert von c bei der Berechnung der Satellitenentfernung zu verfeinern. Wir tun das durch einen Vergleich der vom Empf¨ anger gemessenen Laufzeit mit der Laufzeit, die von einem anderen nahe gelegenen Empf¨ anger gemessen wird, dessen genaue Position bekannt ist. Das erm¨ oglicht eine genaue Berechnung der Durchschnittsgeschwindigkeit, die das Licht auf seinem Weg von einem gegebenen Satelliten zum Empf¨ anger hat. Das wiederum erm¨ oglicht seinerseits genaue Entfernungsberechnungen. Bei Unterst¨ utzung durch eine solche feste Bodenstation erreicht die GPS-Pr¨azision eine Gr¨oßenordnung von Zentimetern. Das von jedem Satelliten gesandte Signal ist ein zuf¨ alliges Signal, das sich in regelm¨aßigen bekannten Intervallen wiederholt. Die Periode des Signals ist relativ kurz, so dass die vom Signal in einer Periode u oßenordnung von ei¨berdeckte Distanz die Gr¨ nigen hundert Kilometern hat. Sieht der Empf¨ anger den Anfang einer Signalperiode, dann muss er exakt bestimmen, zu welchem Zeitpunkt diese Periode vom Satelliten ausgestrahlt wurde. A priori haben wir eine Unsicherheit von einigen ganzzahligen Periodenzahlen. Sich schnell bewegender GPS-Empf¨anger: Die Installation eines GPS-Empf¨ angers auf einem sich schnell bewegenden Objekt (zum Beispiel auf einem Flugzeug) ist eine ganz nat¨ urliche Anwendung: Muss ein Flugzeug bei unfreundlichem Wetter landen, dann muss der Pilot zu jedem Zeitpunkt die genaue Position des Flugzeugs kennen und die Zeit zur Berechnung der Position muss auf ein absolutes Minimum reduziert werden. Die Erde ist nicht wirklich rund! Tats¨ achlich ist die Erde ein Ellipsoid, das an den ¨ Polen etwas abgeflacht und am Aquator etwas ausgebaucht ist (ein an den Polen ” abgeplattetes Sph¨ aroid“). Der Erdradius hat an den Polen eine L¨ ange von ungef¨ ahr ¨ ange von 6378 km. Folglich m¨ ussen die Berechnungen 6356 km und am Aquator eine L¨ ¨ zur Ubersetzung der kartesischen Koordinaten (x, y, z) in Breite, L¨ ange und H¨ ohe verfeinert werden, um diese Tatsache zu ber¨ ucksichtigen. Relativistische Korrekturen. Die Geschwindigkeit der Satelliten ist hinreichend groß, so dass bei allen Berechnungen die Effekte der speziellen Relativit¨ at ber¨ ucksichtigt werden m¨ ussen. Tats¨ achlich bewegen sich die Uhren auf den Satelliten sehr schnell im Vergleich zu den Uhren auf der Erde. Gem¨ aß der speziellen Relativit¨atstheorie gehen die Satellitenuhren langsamer als diejenigen auf der Erde. Außerdem sind die Satelliten der Erde relativ nahe, die eine signifikante Masse hat.
1.2 Global Positioning System
11
Laut allgemeiner Relativit¨ atstheorie erfolgt bei den Uhren an Bord der Satelliten ein kleiner Geschwindigkeitszuwachs. In erster Ann¨ aherung k¨ onnen wir die Erde als eine große nicht rotierende kugelf¨ ormige Masse ohne elektrische Ladung modellieren. Der Effekt l¨ asst sich unter Verwendung der Schwarzschild-Metrik relativ leicht berechnen, welche die Auswirkungen der allgemeinen Relativit¨ at unter diesen vereinfachten Bedingungen beschreibt. Es stellt sich heraus, dass diese Vereinfachung ausreicht, um den tats¨achlichen Effekt mit hoher Pr¨ azision zu erfassen. Beide Effekte m¨ ussen ber¨ ucksichtigt werden: Zwar finden sie in zueinander entgegengesetzten Richtungen statt, aber sie annullieren einander nur teilweise. Weitere Einzelheiten findet man in [4]. Anwendungen des GPS. Das GPS hat zahlreiche Anwendungen, von denen wir hier nur einige nennen: •
Ein GPS-Empf¨anger erm¨oglicht es einem Nutzer, der sich im Freien aufh¨ alt, m¨ uhelos seine Position zu finden. Der Empf¨anger ist also f¨ ur Wanderer, Kajakfahrer, J¨ ager, Matrosen, Bootsf¨ uhrer usw. unmittelbar n¨ utzlich. Die meisten Empf¨ anger gestatten die Markierung von Wegpunkten, die gespeichert werden k¨ onnen, wenn man sich physisch am betreffenden Standort befindet (in diesem Fall hat der Empf¨ anger seine Position berechnet) oder wenn man Kartenkoordinaten manuell in den Empf¨ anger eingibt. Verbinden wir die Wegpunkte durch Strecken, dann k¨ onnen wir eine Route darstellen. Der Empf¨ anger kann uns dann unsere Position in Bezug auf einen gew¨ahlten Wegpunkt mitteilen oder uns sogar Anweisungen erteilen, wie wir unsere Route zur¨ ucklegen sollen. Anspruchsvollere Empf¨ anger k¨ onnen sogar detaillierte Karteninformationen speichern. Der Empf¨ anger kann dann unsere Position auf einem Teil der Karte anzeigen, der auf dem Display zusammen mit Kommentaren zu unseren Wegpunkten und Routen zu sehen ist. • Immer mehr Fahrzeuge (insbesondere Taxis) sind mit GPS-Navigationssystemen ausgestattet, die es ihren Fahrern erm¨oglichen, den Weg zu einer speziellen Adresse zu finden. In Westeuropa und Nordamerika gibt es mehrere Produkte, welche die genauen Wege zu fast allen Adressen angeben. • Stellen Sie sich vor, dass Sie eine alte Karte haben, auf der Sie eine von Ihnen zur¨ uckgelegte Route einzeichnen m¨ochten. Die Route kann beim Zur¨ ucklegen in das GPS gespeichert werden und sp¨ater mit einer geeigneten Software auf einen Computer hochgeladen werden. Diese Software kann dann den zur¨ uckgelegten Weg auf die digitalisierte Karte aufbringen. Falls Sie nicht bereits eine digitale Kartenversion haben, dann k¨onnen Sie die Karte zuerst einscannen und (unter Verwendung einer geeigneten Software) mit einem Koordinatensystem belegen, indem Sie einfach die ¨ Position von drei bekannten Punkten angeben (s. Ubung 5). • Der allgegenw¨artige Gebrauch des GPS in Flugzeugen erm¨ oglicht eine Einengung der Luftkorridore, wobei auch weiterhin gew¨ahrleistet ist, dass die Flugzeuge einen sicheren Abstand voneinander haben.
12
1 Positionsbestimmung auf der Erde und im Raum
•
Eine Flotte von Lieferfahrzeugen kann mit GPS-Empf¨ angern ausger¨ ustet werden, die ein gleichzeitiges Verfolgen s¨amtlicher Fahrzeuge gestatten. Ein solches System wird gegenw¨artig verwendet, um die Taxis in Paris zu leiten. Bei dieser Anwendung muss das GPS mit einem Kommunikationssystem gekoppelt werden, das es erm¨ oglicht, die Koordinaten eines jeden Fahrzeugs zu u ur ein solches ¨bertragen (ein Beispiel f¨ ¨ Systems ist das Global System for Mobile Communications, kurz GSM). Ahnliche Systeme werden in Umweltstudien f¨ ur das Nachverfolgen wild lebender Tiere verwendet. Man kann sich unschwer vorstellen, welchen Einfluss es auf unser Leben hat, wenn eine Autovermietungsfirma ihre Flotte mit einem GPS-GSM System ausr¨ usten w¨ urde, das es der Firma erm¨ oglicht, die Kunden in Bezug auf die Einhaltung der Territorialgrenzen zu u ¨berwachen, die im Mietvertrag festgelegt sind! • Das GPS kann als Blindenhilfe verwendet werden. • Geografen verwenden das GPS, um das Wachstum des Mount Everest zu messen: Dieser Berg w¨achst langsam in dem Maße, wie sich sein Gletscher, der Khumbu senkt. Ebenso besteigt alle zwei Jahre eine Expedition den Mont Blanc, um auf dem Gipfel die amtliche H¨ohe des Berges zu aktualisieren. In den neunziger Jahren stellten die Geografen mal wieder die Frage, ob der K2 h¨oher als der Mount Everest sei. Seit ihrer Expedition 1998, bei der sie das GPS verwendeten, ist die Sache eindeutig klar: Der Mount Everest ist mit 8830 m der h¨ochste Berg der Erde. 1954 hat B. L. Gulatee die H¨ohe des Everest auf 8848 m gesch¨ atzt. Damals erfolgte die Sch¨ atzung unter Verwendung von Theodolit-Messungen, die in sechs Stationen auf den nordindischen Ebenen durchgef¨ uhrt wurden (ein Theodolit ist ein optisches Winkelmessinstrument, das in der Geod¨ asie verwendet wird). • Es gibt viele milit¨arische Anwendungen – urspr¨ unglich wurde das System ja f¨ ur das amerikanische Milit¨ ar entwickelt. Eine solche Anwendung ist der Pr¨ azisionsabwurf von Bomben. Die Zukunft: GPS und Galileo. Bis jetzt hatten die Vereinigten Staaten ein Monopol auf diesem Markt. In Anbetracht dessen, dass die Amerikaner die ausschließliche Kontrolle u usseln und ¨ber das GPS haben, kann die US-Regierung das GPS-Signal verschl¨ so den Zugang blockieren oder aus milit¨ arischen Gr¨ unden (im Rahmen des NAVWARProgramms zur Navigationskriegsf¨ uhrung) die Signalgenauigkeit u ¨ber einem bestimmaische Union mit der Euroten Gebiet verringern. Im M¨ arz 2002 vereinbarte die Europ¨ pean Space Agency die Entwicklung und Stationierung von Galileo, einem System zur Positionsbestimmung, das als Alternative zu GPS entworfen wurde. Zwei Testsatelliten wurden 2005 gestartet und die 28 verbleibenden Satelliten sollen bis 2014 abheben. Die GPS-Satelliten u ¨bertragen keine Informationen zum Status des Satelliten bzw. zur Signalqualit¨at. Deswegen kann es mehrere Stunden dauern, bevor ein funktionsgest¨ orter Satellit entdeckt und abgeschossen wird; w¨ahrend dieser Zeit verschlechtert sich die Systemgenauigkeit. Das schr¨ankt die Anwendungen des GPS f¨ ur das Leiten von Flugzeugen bei schlechtem Wetter ein. Die Galileo-Satelliten sind so entworfen, dass sie st¨andig Signalqualit¨ atsinformationen senden, die es den Empf¨ angern erm¨ oglichen, das Signal funktionsgest¨orter Satelliten zu ignorieren. Das erfolgt durch ein System
1.3 Blitz und Donner
13
von Bodenstationen, welche die tats¨ achliche Position des Satelliten exakt messen und mit der berechneten Satellitenposition vergleichen. Diese Informationen werden an den funktionsgest¨orten Satelliten u uck an die Empf¨ anger leitet. Die ¨bermittelt, der sie zur¨ US-Regierung plant f¨ ur das GPS eine ¨ ahnliche Verbesserung.
1.3 Wie Hydro-Qu´ ebec mit Blitzschl¨ agen umgeht Neue L¨osungen zu vorhandenen Problemen werden h¨ aufig offensichtlich, wenn neue Technologien bereitgestellt werden. Hydro-Qu´ebec1 verwendet das GPS als Teil seines Ansatzes f¨ ur den Umgang mit Blitzschl¨ agen. Mathematik kommt an mehreren Stellen des betrieblichen Blitzschlag¨ uberwachungssystems zum Einsatz. In diesem Abschnitt konzentrieren wir uns nicht nur auf die Anwendung des GPS auf das Blitzschlagmanagement, sondern auch auf die Mathematik, die bei Hydro-Qu´ebec an anderen Stellen eingesetzt wird. 1.3.1 Die Ortung von Blitzschl¨ agen Hydro-Qu´ebec installierte 1992 in seinem Netz ein Blitzschlagortungssystem. Das Grundproblem ist die Bestimmung der Grenzen der Gebiete, die von Gewittern betroffen sind: Man m¨ochte den Strom reduzieren, der durch die betroffenen Leitungen fließt, indem man ihn u ¨ber Hochspannungsleitungen umleitet, die außerhalb des Gewittergebietes liegen. Dadurch werden die potentiellen Auswirkungen eines Blitzschlags auf eine Hochspannungsleitung minimiert: Der durch Blitzschlag verursachte Schaden wird lokal eingeschr¨ankt, wodurch die Anzahl der betroffenen Kunden minimiert und gleichzeitig die Gesamtzuverl¨assigkeit des Stromversorgungsnetzes erh¨ oht wird. Um dieses Ziel zu erreichen, verwendet Hydro-Qu´ebec ein System von 13 Detektoren, die in den niedriger gelegenen zwei Dritteln der Provinz Qu´ebec (¨ uber das von Hochspannungsleitungen u ¨berdeckte Territorium) verteilt sind. Die Positionen der Detektoren sind genau bekannt, aber da das System auf exakten Zeitmessungen beruht, m¨ ussen die Uhren in den Detektoren perfekt synchronisiert sein. Hierzu hat jeder Detektor einen GPS-Empf¨ anger. Verwendung eines GPS-Empf¨ angers als Zeitreferenz. Es mag etwas u ¨berraschend erscheinen, dass man einen GPS-Empf¨ anger zur Zeitmessung verwenden kann. Wir haben gerade bemerkt, dass GPS-Empf¨anger typischerweise mit billigen und relativ ungenauen Uhren ausgestattet sind. Wir haben jedoch auch erw¨ ahnt, dass der Empf¨ anger bei der Bestimmung seiner Position den Uhrenfehler, das heißt, die Zeitdifferenz τ zwischen seiner Uhr und derjenigen an Bord der GPS-Satelliten berechnet. Folglich berechnet der Empf¨anger tats¨achlich die genaue Zeit, wie sie von den Uhren an Bord der Satelliten 1 Hydro-Qu´ebec ist der gr¨ oßte Erzeuger, Transporteur und Verteiler von Elektrizit¨ at in der Provinz Qu´ebec. Der Name ist darauf zur¨ uckzuf¨ uhren, dass 95% seiner Stromerzeugung hydroelektrisch ist.
14
1 Positionsbestimmung auf der Erde und im Raum
gemessen wird. Wird eine hohe Pr¨azision gew¨ unscht und ist der Empf¨ anger station¨ ar, dann ist es besser, die berechneten Werte von x, y, z und τ durch den Durchschnitt von zu verschiedenen Zeiten berechneten Werten (xi , yi , zi , τi )N i=1 zu ersetzen. Tats¨achlich tritt in jeder Berechnung (xi , yi , zi , τi ) ein Fehler auf. Die Fehler in Bezug auf den Raum k¨onnen in jeder beliebigen Richtung rund um die wahre Empf¨ angerposition auftreten und diese Fehler gehorchen einem sch¨onen statistischen Gesetz (sie sind gleichf¨ormig verteilt und Gauß’sch). In a¨hnlicher Weise kann der Fehler bei der Berechnung der Zeitdifferenz positiv oder negativ
N sein. Somit
N werden
Ndie Position
N des Empf¨angers und die Zeitdifferenz durch ( N1 i=1 xi , N1 i=1 yi , N1 i=1 zi , N1 i=1 τi ) besser approximiert. Auf diese Weise ist ein GPS-Empf¨anger dazu in der Lage, seine Uhr in Bezug auf die Satelliten mit einer Pr¨azision von ungef¨ahr 100 Nanosekunden (eine Nanosekunde ist 1 Milliardstel einer Sekunde) zu synchronisieren. Eine solche Methode wird bei den Detektoren von Hydro-Qu´ebec verwendet. Tats¨ achlich erm¨ oglicht das GPS, dass die 13 Detektoren ihre Uhren bis auf 100 Nanosekunden synchronisieren. Sobald der Empf¨anger mit den Satellitenuhren synchronisiert ist, kann er auch die Sekunde schla” gen“, das heißt, in jeder Sekunde einen Impuls senden. Das wird f¨ ur andere Messungen verwendet. Ortung von Blitzschl¨ agen. Zus¨atzlich zur Aufrechterhaltung einer synchronisierten Uhr sind die 13 Detektoren auch daf¨ ur zust¨andig, alle ungew¨ ohnlichen elektromagnetischen Aktivit¨aten zu u aten zu identifizieren, die ¨berwachen und diejenigen Aktivit¨ durch Blitzschl¨age verursacht worden sind. Hydro-Qu´ebec hat die Detektoren ziemlich weit weg von den Hochspannungsleitungen aufgestellt, da die von Hochspannungsleitungen verursachten elektromagnetischen Felder eine exakte Signalentdeckung st¨ oren w¨ urden. Die Detektoren befinden sich typischerweise auf den D¨ achern von HydroQu´ebec-Verwaltungsgeb¨auden und sind in dem zu u aßig ¨berwachenden Gebiet so gleichm¨ wie m¨oglich verteilt. Schl¨ agt ein Blitz in dieses Gebiet mit einer Energie ein, die zur Gef¨ahrdung des Netzes ausreicht, dann wird er typischerweise von mindestens f¨ unf Detektoren registriert. Tats¨ achlich sind die Detektoren hinreichend empfindlich, um bis zur Entfernung von Mexiko ¨ außerst starke Blitzschl¨ age zu orten, wenn auch mit geringerer Pr¨azision. Der Blitzschlag erzeugt eine elektromagnetische Welle, die sich mit Lichtgeschwindigkeit durch den Raum ausbreitet. Jeder Detektor zeichnet die genaue Zeit auf, wenn er die Welle wahrnimmt. Hierzu verwenden die Detektoren einen schnellen Oszillator (zum Beispiel ein Quarzkristall), der mit der GPS-Zeitquelle synchronisiert ist. Die Frequenz dieser Oszillatoren variiert typischerweise von 4 bis 16 Megahertz (ein Megahertz, abgek¨ urzt MHz, ist die Frequenz von einer Million Schwingungen pro Sekunde). Die Detektoren u ¨bermitteln diese Informationen an einen Zentralcomputer, sobald sie die Welle gemessen haben. Das System berechnet dann die Position des Blitzschlags durch Triangulation (mit anderen Worten unter Verwendung der Zeitdifferenzen, mit ¨ denen die einzelnen Detektoren die Welle registriert haben, vgl. Ubung 2).
1.3 Blitz und Donner
15
Identifizierung von Blitzschl¨ agen. Es gibt drei Typen von Blitzschl¨ agen: •
Blitzschl¨age zwischen den Wolken. Die Mehrzahl der Blitzschl¨ age ist von diesem Typ. Sie werden nicht erfasst, aber sie wirken sich auch nicht auf das Netz aus, da sie nicht in den Boden einschlagen. • Negative Blitzschl¨ age. In diesem Fall ist die Wolke negativ geladen und der Blitzschlag besteht aus einem Fluss von Elektronen, die sich von der Wolke zum Boden bewegen. • Positive Blitzschl¨age. In diesem Fall ist die Wolke positiv geladen und der Blitzschlag besteht aus einem Fluss von Elektronen, die sich vom Boden zur Wolke bewegen. Wie Sie vielleicht vermutet haben, ist die Welle eines positiven Schlages das Spiegelbild der Welle des negativen Schlages.
Beschr¨anken wir uns auf Blitzschl¨ age zwischen dem Boden und den Wolken, dann sind 90% dieser Schl¨age negativ. Bei einem starken Gewitter dreht sich dieser Prozentsatz aber um, und 90% der Bodenblitzschl¨ age sind positiv. Die Detektoren k¨ onnen zwischen einem negativen und einem positiven Blitzschlag unterscheiden: der eine ist das Spiegelbild des anderen. W¨ urde ein Detektor eine Welle mit einem positiven Blitzschlag registrieren und ein anderer Detektor einen negativen Blitzschlag, dann leuchtet es ein, dass die beiden Wellen nicht durch ein und denselben Schlag erzeugt werden konnten. Leider sind die Dinge etwas komplizierter. Eine Welle, die sich mehr als 300 km von ihrer Quelle ausgebreitet hat, kann durch die Ionosph¨ are reflektiert werden, wobei das Signal invertiert wird. Folglich ist es m¨ oglich, dass ein weit genug entfernter Detektor in Wirklichkeit ein reflektiertes Signal misst. Um zwischen den Blitzschl¨agen und anderen elektromagnetischen Signalen zu unterscheiden, analysiert der Detektor die Form der Welle, indem er das Signal filtert und nach der spezifischen Signatur eines Blitzschlages sucht. Insbesondere registriert der Detektor den Signalanfang, die maximale Amplitude, die Anzahl der Spitzenamplituden sowie den Anstieg, und sendet diese Informationen an den Zentralcomputer. Die Signalverarbeitung ist ein sch¨ ones Thema der angewandten Mathematik, aber wir werden dieses Thema hier nicht diskutieren. Von der Theorie zur Praxis. Es gibt mehrere zus¨ atzliche Tricks, um empfangene Signale korrekt zu identifizieren. •
Es seien P und Q die zwei Detektoren, die am weitesten voneinander entfernt sind, und es sei T die Zeit, die das (sich mit Lichtgeschwindigkeit ausbreitende) Signal ben¨otigt, um den Weg zwischen P und Q zur¨ uckzulegen. Wir k¨ onnen sicher sein, dass die Zeitdifferenz zwischen den beiden entdeckten Signalen f¨ ur ein und denselben Blitzschlag nicht gr¨oßer als T ist. Wenn also zwei Detektoren einen Schlag zu den Zeiten t1 and t2 registrieren und |t1 − t2 | > T , dann k¨ onnen diese Signale nicht von demselben Blitzschlag kommen. • Die Amplitude der durch den Blitzschlag erzeugten Welle ist umgekehrt proportional zum Quadrat der Entfernung zu ihrer Quelle. Damit also zwei entdeckte Signale dem
16
•
1 Positionsbestimmung auf der Erde und im Raum
gleichen Blitz entsprechen, m¨ ussen die Amplituden der gemessenen Signale mit der berechneten Position kompatibel sein. Schl¨agt der Blitz innerhalb einer Entfernung von 20 km von einem Detektor ein, dann werden die Ablesungen des Detektors aus der Rechnung eliminiert. Der Grund daf¨ ur ist, dass die gemessene Amplitude zu groß und der Detektor nicht dazu in der Lage ist, den Unterschied zwischen dem Signal eines einzelnen Blitzschlags und dem u age zu erkennen. ¨berlagerten Signal zweier Blitzschl¨
Mit diesen Methoden ist Hydro-Qu´ebec imstande, Blitzschl¨ age mit einer Genauigkeit von bis zu 500 m zu lokalisieren, wenn sie innerhalb des Gebietes niedergehen, das von den Detektoren u ¨berwacht wird. Lokalisierung von St¨ orungen in Starkstromleitungen. Eine ¨ ahnliche Methode wird bei der Lokalisierung von St¨ orungen im Transportnetz verwendet: Hat zum Beispiel ein Blitzschlag eine Starkstromleitung besch¨adigt, dann m¨ ussen die Techniker wissen, wohin sie gehen sollen, um die Leitung zu reparieren. An beiden Enden jeder zu sch¨ utzenden Starkstromleitung wird ein Oszilloperturbograph (St¨ orschwingungsaufzeichnungsger¨at) installiert und durch das GPS synchronisiert. Dieses Ger¨ at misst die Form des 60-Hz-Signals, das sich durch die Leitung ausbreitet. In Abh¨ angigkeit vom Fehler beobachtet man verschiedene Typen von St¨ orungen. Eine St¨ orung breitet sich mit Lichtgeschwindigkeit durch die Leitung aus. Die beiden Detektoren messen die Zeiten t1 und t2 , bei denen die St¨ orung beobachtet wird, und unter Verwendung der Differenz t1 − t2 l¨asst sich die Position des Fehlers berechnen. Diese Techniken haben eine Pr¨azision von nur einigen hundert Metern, aber das reicht im Allgemeinen aus. In Quebec sind die Starkstromleitungen h¨aufig sehr lang und verlaufen durch riesige unbewohnte Gebiete; somit erm¨ oglicht das System einen schnellen Einsatz des Reparaturteams im St¨orungsgebiet. Umverteilung der Energie¨ ubertragung. Die Blitzschlagerkennung kann dazu verwendet werden, die Gr¨ oße und den Standort eines Gewitters zu bestimmen. Blitzschl¨ age treten innerhalb eines Gebietes zuf¨ allig auf und deswegen kann man statistische Modelle verwenden. Hierzu teilt man das betreffende Gebiet in ein regelm¨ aßiges Gitter auf und berechnet die raumzeitliche Dichte der Blitzschl¨ age. Zum Beispiel ist ein Gewitter mit zwei Blitzschl¨agen pro km2 innerhalb von 10 Minuten sehr stark. Unter Verwendung der Modellinformationen wird das sogenannte Auge berechnet, das heißt, das Zentrum des Gewitters. Die Berechnung wird alle f¨ unf Minuten wiederholt, und die Verschiebung des berechneten Zentrums wird zur Ermittlung der Geschwindigkeit und der Richtung des Gewitters verwendet (die Geschwindigkeit kann irgendwo zwischen 0 und 200 km/h liegen). Man kann diese Informationen ihrerseits verwenden, um vorherzusagen, welche Bereiche des Leitungsnetzes als n¨ achstes betroffen sein werden. Eines der schwierigeren Probleme ergibt sich, wenn zwei Gewitter nahe beieinander sind: Das System muss entscheiden, ob es sich tats¨achlich um zwei verschiedene Gewitter oder um ein einziges gr¨oßeres Gewitter handelt. Das ist ein interessantes Problem f¨ ur Ingenieure! Ausgestattet mit diesen Informationen st¨ utzt sich der Großh¨ andler auf seine Erfahrungen und entscheidet, ob die Strommenge, die u ahrdete Stark¨ber eine potentiell gef¨
1.3 Blitz und Donner
17
stromleitung u ¨bertragen wird, gesenkt werden muss. Es ist eine sehr heikle Angelegenheit, ein Starkstromnetz im Gleichgewicht zu halten. Es muss immer ein Gleichgewicht zwischen der erzeugten Strommenge, der u ¨bertragenen Strommenge und der genutzten Strommenge bestehen. Um die Strommenge zu verringern, die durch eine Leitung ¨ u at in einer oder mehreren anderen Leitungen ¨bertragen wird, muss es eine Uberkapazit¨ geben. Um also solche Entscheidungen zu treffen, muss der Verteiler einen bestimmten Handlungsspielraum haben. Jede Leitung hat eine maximale Kapazit¨ at, aber in der Regel werden Starkstromnetze immer etwas unterhalb der Kapazit¨ at gefahren, so dass das System zu jedem beliebigen Zeitpunkt den Ausfall einer gesamten Leitung auffangen kann. 1.3.2 Detektionsschwelle und Detektionsqualit¨ at bei Blitzschl¨ agen Die Detektorausr¨ ustung wird so eingerichtet, dass sie den Minimalstandards f¨ ur die entsprechende Erkennung gen¨ ugt, aber im Allgemeinen besser ist. Es lohnt sich also, die tats¨achlichen F¨ahigkeiten der Ausr¨ ustung genau zu beurteilen – ein Prozess, der sich haupts¨achlich auf statistische Methoden st¨ utzt. Zu diesem Zweck werden wir ein empirisches Wahrscheinlichkeitsgesetz f¨ ur die Zufallsvariable X heranziehen, die die Intensit¨ at eines Blitzschlags angibt. Anstelle der Dichtefunktion f (I) von Blitzschl¨ agen verwenden wir die Verteilungsfunktion P (I) = Prob(X > I) = 1+
1 I K .
(1.17)
M
Wir haben P (0) = Prob(X > 0) = 1. Die zu verwendenden Werte von M und K h¨angen von der geografischen Zone sowie von den Besonderheiten ihrer Umgebung ab und werden empirisch bestimmt. Der Wert von I ist in kA (Kiloampere) gegeben. Bestimmte Werte werden h¨aufig verwendet und haben deswegen einen eigenen Namen. So wird beispielsweise die Funktion P von (1.17) als Popolansky-Funktion bezeichnet, wenn M = 25 und K = 2. Sie heißt Anderson-Erikson-Funktion, wenn M = 31 und K = 2, 6. Abbildung 1.3 zeigt die Popolansky-Funktion und Abbildung 1.4 die Dichte∞ funktion f (I) der zugeh¨ origen Variablen X. Man beachte, dass P (I) = I f (J)dJ und deswegen f (I) = −P (I). Wir zeigen, wie dieses empirische Gesetz in der Praxis verwendet werden kann. Beispiel 1.1 Die Popolansky-Funktion 1. Die Wahrscheinlichkeit daf¨ ur, dass ein zuf¨ alliger Blitzschlag eine Stromst¨ arke von mehr als 50 kA hat, ist P (50) =
1 1 50 2 = = 0, 2. 5 1+ 25
(1.18)
18
1 Positionsbestimmung auf der Erde und im Raum
, , , ,
Abb. 1.3. Die Popolansky-Funktion. , , , , ,
Abb. 1.4. Die zur Popolansky-Funktion geh¨ orende Dichtefunktion.
2. Der Median dieser Verteilung ist derjenige Wert Im von I, f¨ ur den Prob(X > Im ) = P (Im ) =
1 . 2
1 Das liefert uns die Gleichung = 12 . Demnach ist 1 + m 2 1+( I25 ) 2 m anderen Worten I25 = 1. Hieraus ergibt sich Im = 25.
(1.19) I 2 m
25
= 2, oder mit
Berechnung der Blitzschlagerkennungsrate. In der Praxis entdecken wir nicht alle Blitzschl¨age, sondern nur diejenigen, deren Energie eine bestimmte Schwelle u ¨berschreitet. Diese Schwelle h¨angt ab von der Position des Blitzschlags in Bezug auf die Detektoren sowie von verschiedenen Interferenzquellen, welche die Empfangsqualit¨ at der Detektoren zu jedem gegebenen Zeitpunkt verringern kann. Wir untersuchen jetzt, wie man den Prozentsatz der Blitzschl¨ age bestimmt, die entdeckt werden. In unserem Beispiel
1.3 Blitz und Donner
19
haben wir festgelegt, dass 50% der Blitzschl¨ age eine Stromst¨ arke von mehr als 25 kA haben. Nehmen wir nun f¨ ur den Moment an, dass wir in einer Stichprobe von entdeckten Blitzsschl¨agen beobachtet haben, dass 60% eine Stromst¨ arke von mehr als 25 kA hatten. Es sei E das Ereignis der Blitzschlag wird entdeckt“. Dann m¨ ochten wir Prob(E) be” rechnen. Wir kennen die Wahrscheinlichkeit daf¨ ur, dass ein entdeckter Blitzschlag (also das stattgefundene Ereignis E ) eine Stromst¨ arke von mehr als 25 kA hatte. Das ist eine bedingte Wahrscheinlichkeit, weil wir angenommen haben, dass der Blitzschlag entdeckt wurde, und wir k¨onnen das in folgender Form schreiben: Prob(X > 25|E) = 0, 6.
(1.20)
Andererseits wissen wir, dass sich die Wahrscheinlichkeit von X > 25 (unter der Bedingung, dass E eingetreten ist) durch Prob(X > 25|E) =
Prob(X > 25 und E) Prob(E)
(1.21)
ausdr¨ ucken l¨asst. In dieser Form k¨ onnen wir nicht viel mit diesem Ausdruck anfangen, da sowohl der Z¨ahler als auch der Nenner unbekannt sind. Wir wollen aber nun annehmen, dass alle Blitzschl¨age entdeckt werden, die eine Stromst¨ arke von mehr als 25 kA haben. Dann wird das Ereignis X > 25 und E“ einfach zu X > 25, dessen Wahrscheinlichkeit ” bekannt ist. Somit liefert (1.21) das Ergebnis Prob(E) =
0, 5 5 Prob(X > 25) = = = 0, 83. Prob(X > 25|E) 0, 6 6
(1.22)
Wir setzen nun f¨ ur ein beschr¨ anktes geografisches Gebiet voraus, dass die einzigen nicht entdeckten Blitzschl¨ age (mit einer akzeptablen Fehlertoleranzgrenze) diejenigen sind, die eine geringere Stromst¨arke haben. Wir wollen die Schwellenstromst¨ arke I0 bestimmen, unterhalb der keine Blitzschl¨ age entdeckt werden. Bei dieser Berechnung wird das Ereignis E zu X > I0 . Wir haben gesehen, dass Prob(E) = 65 = 0, 83. Wegen Prob(E) = Prob(X > I0 ) = P (I0 ) liefert das die Gleichung P (I0 ) =
5 0, 5 = , 0, 6 6
I 2 1 5 0 die darauf hinausl¨auft, aquivalent 1 + 25 = I0 2 = 6 oder ¨ 1+( 25 ) I0 2 ullt, und hieraus folgt I0 der Wert, der 25 = 15 = 0, 2 erf¨ I0 = 25
0, 2 = 11, 18.
(1.23) 6 5
zu l¨ osen. Daher ist
(1.24)
Wir k¨onnen demnach f¨ ur das gegebene Gebiet schließen, dass die Detektionsschwelle den Wert I0 = 11, 18 kA hat und dass Blitzschl¨ age mit Stromst¨ arken, die unter diesem Wert liegen, nicht entdeckt werden.
20
1 Positionsbestimmung auf der Erde und im Raum
1.3.3 Langfristiges Risikomanagement Die Verwaltung von Blitzschl¨ agen ist nicht darauf beschr¨ ankt, Gewitter zu ermitteln und zu lokalisieren. Hydro-Qu´ebec verf¨ ugt u ¨ber detaillierte langfristige statistische Daten, die zum Erstellen isokeraunischer Karten verwendet werden, welche die Dichte von Blitzschl¨agen u unf Jahren enthalten. Diese Karten k¨ onnen ¨ber einen Zeitraum von f¨ ihrerseits dazu verwendet werden, gef¨ahrdetere Zonen zu identifizieren. Im Falle von Starkstromleitungen, die bereits errichtet worden sind, kann man diese Informationen verwenden um zu entscheiden, welche Abschnitte besser gesch¨ utzt werden sollten. Auf ¨ahnliche Weise kann man diese Karten auch zur Identifizierung von Wegen nutzen, um die Errichtung neuer Starkstromleitungen zu planen. Diese Auswahlm¨ oglichkeiten lassen sich unter dem Stichwort Risikomanagement formulieren. Gefahren aufgrund von heftigen Unwettern sind nur eines der vielen Risiken f¨ ur Firmen, die Elektrizit¨ at erzeugen, transportieren und verteilen. Folglich lassen sich alle Aufgaben der Lokalisierung von Blitzschl¨agen, der Verfolgung von St¨ urmen und Gewittern sowie der Identifizierung von Risikozonen unter dem Stichwort des allgemeinen Risikomanagements einordnen. Das Problem besteht darin, das Verteilungsnetz so zuverl¨assig wie m¨oglich zu machen. Die einzelnen Investitionen in das Netz m¨ ussen also in Bezug auf ihre Rentabilit¨ at bewertet werden. Je gef¨ahrlicher ein gegebenes Ereignis ist und je gr¨oßer seine finanziellen Auswirkungen sind, desto eher sind wir geneigt, das System vor dem Ereignis zu sch¨ utzen oder dessen Auswirkungen zu begrenzen. Nat¨ urlich gilt all das immer unter der Bedingung, dass die Kosten f¨ ur den Schutz nicht zu hoch sind! Zur Formalisierung eines solchen Systems f¨ uhren wir drei Variablen ein: • die Wahrscheinlichkeit p des Ereignisses, das dem Risiko unterliegt; • die f¨ ur die Auswirkungen veranschlagten Kosten Ci , das heißt, der Betrag, den man zahlen muss, falls das Ereignis eintritt und man keine Schutzvorkehrungen getroffen hat; • die D¨ampfungskosten Ca , die gezahlt werden m¨ ussen, um die Ausr¨ ustung zu sch¨ utzen und die Auswirkungen des eintretenden Ereignisses zu begrenzen. Wir f¨ uhren den Index pCi Ca
(1.25)
ein. Wir sehen, dass der Z¨ahler die erwarteten Reparaturkosten und der Nenner die Kosten f¨ ur den Schutz darstellt. Dieses Verh¨altnis muss mindestens 1 sein, damit sich die Investition in den Schutz rentiert. Jedoch gibt es mehrere andere Faktoren, die in der Praxis ins Spiel kommen. Wir werden eher einen Schutz kaufen, wenn er bei mehreren Ereignissen anwendbar ist. In ¨ahnlicher Weise ¨ andert sich die Situation, falls es sich nur um einen teilweisen Schutz handelt, das heißt, wir tragen nicht die Gesamtkosten, sondern niedrigere Reparaturkosten, falls das Ereignis eintritt.
1.4 Lineare Schieberegister
21
1.4 Lineare Schieberegister und das GPS-Signal Lineare Schieberegister erm¨oglichen die Erzeugung von Folgen, mit denen sich ein Empf¨anger ausgezeichnet synchronisieren kann. Diese einfach herzustellenden Ger¨ ate (man kann ein lineares Schieberegister aus einigen elementaren elektrischen Komponenten zusammenbauen) erzeugen Pseudozufallssignale. Das heißt, sie erzeugen Signale, die weitgehend zuf¨ allig zu sein scheinen, obwohl sie durch deterministische Algorithmen erzeugt werden. Wir werden ein lineares Schieberegister konstruieren, das ein periodisches Signal mit einer Periode 2r −1 erzeugt. Dieses Register hat die Eigenschaft, dass es extrem schlecht mit allen Verschiebungen von sich selbst sowie mit anderen Signalen korreliert, die von dem gleichen Register unter Verwendung verschiedener Koeffizienten erzeugt werden. Die Eigenschaft, ein Signal zu haben, das schlecht mit seinen Verschiebungen und mit anderen ¨ahnlichen Signalen korreliert, erm¨ oglicht es den GPS-Empf¨ angern, m¨ uhelos die Signale von einzelnen GPS-Satelliten zu identifizieren und mit diesen Signalen synchron zu laufen. Man kann sich das von einem linearen Schieberegister erzeugte Signal als eine Folge von Nullen und Einsen vorstellen. Das Register selbst kann man sich als ein Band von r Boxen vorstellen, welche die Eintr¨ age an−1 , . . . , an−r enthalten, von denen jeder den Wert 0 oder 1 hat (vgl. Abbildung 1.5).
Abb. 1.5. Ein lineares Schieberegister.
Jeder Box wird eine Zahl qi ∈ {0, 1} zugeordnet. Die r Werte qi sind fest und f¨ ur alle Satelliten voneinander verschieden. Wir erzeugen folgendermaßen eine Pseudozufallsfolge:
• Wir geben uns eine Menge von Anfangsbedingungen a0 , . . . , ar−1 ∈ {0, 1} vor, die nicht alle gleich null sind. achste Element in der • F¨ ur gegebene an−r , . . . , an−1 berechnet das Register das n¨ Folge als
22
1 Positionsbestimmung auf der Erde und im Raum
an ≡ an−r q0 + an−r+1 q1 + · · · + an−1 qr−1 =
r−1
an−r+i qi (mod 2).
(1.26)
i=0
(Zur Berechnung modulo 2 f¨ uhren wir die normale Rechnung durch. Das Endergebnis ist 0, falls die Zahl gerade ist; andernfalls ist das Endergebnis 1. Dementsprechend schreiben wir a ≡ 0 (mod 2), falls a gerade ist, und a ≡ 1 (mod 2), falls a ungerade ist.) • Wir verschieben jeden Eintrag nach rechts und vergessen an−r . Der berechnete Wert an wird in die ganz links stehende Box eingetragen. • Wir iterieren das oben beschriebene Verfahren. Da das oben beschriebene Verfahren vollkommen deterministisch ist und die Anzahl der Anfangsbedingungen endlich ist, erzeugen wir eine Folge, die periodisch werden muss. Auf ¨ahnliche Weise k¨ onnen wir sehen, dass die Periode der Folge h¨ ochstens 2r sein achlich k¨ onnen wir uns kann, da es nur 2r verschiedene Folgen der L¨ange r gibt. Tats¨ von folgender Tatsache u ¨berzeugen: Haben wir in einem bestimmten Moment an−r = ur alle m ≥ n die Gleichheit am = 0. Folglich darf eine · · · = an−1 = 0, dann gilt f¨ interessante“ periodische Folge nie eine Folge von r Nullen enthalten, weswegen ihre ” maximale Periode die L¨ ange 2r − 1 hat. Zur Erzeugung einer Folge mit interessanten Eigenschaften m¨ ussen wir nur sorgf¨ altig die Koeffizienten q0 , . . . , qr−1 ∈ {0, 1} und die Anfangsbedingungen a0 , . . . , ar−1 ∈ {0, 1} ausw¨ahlen. Wir sehen nie die ganze Folge, sondern immer nur ein Fenster M = 2r − 1 von auf−1 , die wir mit B = {b1 , . . . , bM } etikettieren. einanderfolgenden Eintr¨ agen {an }n=m+M n=m −1 Wir m¨ochten das mit einem anderen Fenster C = {c1 , . . . , cM } der Form {an }n=p+M n=p vergleichen. Zum Beispiel wird die Folge B vom Satelliten gesendet und die Folge C ist eine vom GPS-Empf¨ anger erzeugte zyklische Verschiebung derselben Folge. Zur Bestimmung der Verschiebung zwischen den zwei Folgen verschiebt der Empf¨ anger seine Folge wiederholt um eine Einheit (durch Bilden von p → p + 1), bis die Folge mit B identisch ist. Definition 1.2 Die Korrelation zwischen zwei Folgen B und C der L¨ ange M ist die age i, f¨ ur welche Anzahl der Eintr¨age i, f¨ ur welche bi = ci , minus der Anzahl der Eintr¨ bi = ci . Wir bezeichnen die Korrelation (zwischen den beiden Folgen B und C) mit Cor(B, C). Bemerkung: Besteht das Register aus r Eintr¨ agen, dann muss die Korrelation zwischen einem beliebigen Paar von Folgen B und C der Bedingung −M ≤ Cor(B, C) ≤ +M gen¨ ugen, wobei M = 2r − 1. Wir sagen, dass die Folgen schlecht korreliert sind, wenn Cor(B, C) nahe null liegt. Proposition 1.3 Die Korrelation zwischen zwei Folgen B und C betr¨ agt Cor(B, C) =
M i=1
(−1)bi (−1)ci .
(1.27)
1.4 Lineare Schieberegister
23
Beweis. Die Zahl Cor(B, C) wird folgendermaßen berechnet: jedesmal, wenn bi = ci , m¨ ussen wir 1 addieren. Analog m¨ ussen wird jedesmal, wenn bi = ci , eine 1 subtrahieren. onnen. Ist also bi = ci , Man beachte, dass bi und ci nur die Werte 0 oder 1 annehmen k¨ dann haben wir entweder (−1)bi = (−1)ci = 1 oder (−1)bi = (−1)ci = −1. In beiden ¨ F¨allen sehen wir, dass (−1)bi (−1)ci = 1. Ahnlich folgt: Ist bi = ci , dann nimmt genau einer der Ausdr¨ ucke (−1)bi und (−1)ci den Wert 1 an, w¨ ahrend der andere Ausdruck den Wert −1 annimmt. Daher gilt (−1)bi (−1)ci = −1. Der folgende Satz zeigt, dass wir ein lineares Schieberegister so initialisieren k¨ onnen, dass es eine Folge erzeugt, die mit jeder Verschiebung von sich selbst schlecht korreliert. Satz 1.4 Ist ein lineares Schieberegister so wie in Abbildung 1.5 gegeben, dann existieren Koeffizienten q0 , . . . , qr−1 ∈ {0, 1} und Anfangsbedingungen a0 , . . . , ar−1 ∈ {0, 1} derart, dass die vom Register erzeugte Folge eine Periode der L¨ ange 2r − 1 hat. Wir betrachten in dieser Folge zwei Fenster B und C der L¨ ange M = 2r − 1, wobei −1 −1 und C = {an }n=p+M mit p > m. Ist M kein Teiler von p − m, B = {an }n=m+M n=m n=p dann gilt Cor(B, C) = −1. (1.28) Mit anderen Worten: Die Anzahl der nicht u ¨bereinstimmenden Bits ist immer um eins gr¨ oßer als die Anzahl der u ¨bereinstimmenden Bits. Beim Beweis dieses Satzes verwenden wir endliche K¨ orper. Wir beginnen mit der Diskussion eines Beispiels, das den Satz illustriert. Der Beweis folgt in Abschnitt 1.4.2. Beispiel 1.5 In diesem Beispiel nehmen wir r = 4, (q0 , q1 , q2 , q3 ) = (1, 1, 0, 0) und ¨ (a0 , a1 , a2 , a3 ) = (0, 0, 0, 1). Wir u ufung dessen, dass ¨berlassen dem Leser die Uberpr¨ diese Werte eine Folge der Periode 24 − 1 = 15 erzeugen, wobei der folgende Block von Symbolen wiederholt wird: 0
0 0 1 0 0 1 1 0 1 0 1
1 1
1 .
Verschieben wir die Folge um ein Symbol nach links, dann schicken wir die erste 0 an das Ende und erhalten 0
0
1 0 0 1 1 0 1 0 1
1 1
1 0 .
Wir sehen, dass sich die beiden Bl¨ocke von Symbolen an den Positionen 3, 4, 6, 8, 9, 10, 11 und 15 voneinander unterscheiden. Sie unterscheiden sich demnach an acht Positionen und stimmen an sieben Positionen u ¨berein, was eine Korrelation von −1 ergibt. Um die Korrelation mit den anderen 14 Verschiebungen der Folge zu berechnen, schreiben wir explizit alle m¨ oglichen Verschiebungen auf. Eine Inspektion zeigt, dass zwei beliebige der nachstehenden Folgen an genau sieben Stellen u ¨bereinstimmen und sich an den acht verbleibenden Stellen voneinander unterscheiden. Wir u ¨berlassen es dem Leser, diesen Sachverhalt nachzupr¨ ufen:
24
1 Positionsbestimmung auf der Erde und im Raum
0 0 0 1 0 0 1 1 0 1 0 1 1 1 1
0 0 1 0 0 1 1 0 1 0 1 1 1 1 0
0 1 0 0 1 1 0 1 0 1 1 1 1 0 0
1 0 0 1 1 0 1 0 1 1 1 1 0 0 0
0 0 1 1 0 1 0 1 1 1 1 0 0 0 1
0 1 1 0 1 0 1 1 1 1 0 0 0 1 0
1 1 0 1 0 1 1 1 1 0 0 0 1 0 0
1 0 1 0 1 1 1 1 0 0 0 1 0 0 1
0 1 0 1 1 1 1 0 0 0 1 0 0 1 1
1 0 1 1 1 1 0 0 0 1 0 0 1 1 0
0 1 1 1 1 0 0 0 1 0 0 1 1 0 1
1 1 1 1 0 0 0 1 0 0 1 1 0 1 0
1 1 1 0 0 0 1 0 0 1 1 0 1 0 1
1 1 0 0 0 1 0 0 1 1 0 1 0 1 1
1 0 0 0 1 0 0 1 1 0 1 0 1 1 1
Im vorhergehenden Beispiel haben wir nicht explizit erl¨ autert, warum wir die speahlt haben. Um das zu zeigen und um ziellen Werte f¨ ur q0 , . . . , q3 und a0 , . . . , a3 gew¨ Satz 1.4 zu beweisen, werden wir die Theorie der endlichen K¨ orper verwenden. Insbealt. Im Fall r = 1 sondere werden wir den K¨ orper F2r verwenden, der 2r Elemente enth¨ ist der K¨orper F2 der aus 2 Elementen bestehende K¨ orper {0, 1} mit der Addition und Multiplikation modulo 2. 1.4.1 Die Struktur des K¨ orpers Fr2 Die Struktur und die Konstruktion endlicher K¨ orper der Ordnung pn (mit einer Primzahl p) werden in den Abschnitten 6.2 und 6.5 von Kapitel 6 untersucht. Diese Abschnitte sind in sich geschlossen und k¨ onnen gelesen werden, ohne den Rest von Kapitel 6 zu kennen. Im jetzt folgenden Teil des vorliegenden Kapitels setzen wir voraus, dass der Leser das Material der beiden genannten Abschnitte kennt. Die Elemente von Fr2 sind die r-Tupel (b0 , . . . , br−1 ), bei denen bi ∈ {0, 1}. Die Addition zweier solcher r-Tupel ist einfach die Addition modulo 2, die Eintrag f¨ ur Eintrag durchgef¨ uhrt wird, das heißt, (b0 , . . . , br−1 ) + (c0 , . . . , cr−1 ) = (d0 , . . . , dr−1 ),
(1.29)
wobei di ≡ bi + ci (mod 2). Zur Definition eines Multiplikationsoperators beginnen wir mit der Wahl eines Polynoms P (x) = xr + pr−1 xr−1 + · · · + p1 x + p0 ,
(1.30)
das u ¨ber dem K¨orper F2 irreduzibel ist. Wir interpretieren jedes r-Tupel (b0 , . . . , br−1 ) als ein Polynom vom Grad kleiner oder gleich r − 1: br−1 xr−1 + · · · + b1 x + b0 .
(1.31)
1.4 Lineare Schieberegister
25
Um die beiden r-Tupel zu multiplizieren, multiplizieren wir die beiden dazugeh¨ origen Polynome. Das Produkt ist ein Polynom vom Grad kleiner oder gleich 2(r − 1). Dieses Polynom wird dann zu einem Polynom in x vom Grad r −1 reduziert, indem man seinen Rest nach Division durch P nimmt (ein Verfahren analog zur schriftlichen Division von ganzen Zahlen). Das ist a¨quivalent zur Regel P (x) = 0, das heißt, xr = pr−1 xr−1 + · · · + p1 x + p0 (wegen der in F2 geltenden Beziehung −pi = pi ) und anschließender Iteration. Danach interpretieren wir die Koeffizienten des resultierenden Polynoms vom Grad (r − 1) als die Eintr¨age eines r-Tupels. Das folgende Ergebnis ist ein klassischer ¨ Satz aus der Theorie der endlichen K¨ orper. Wir geben nur einen Uberblick u ¨ber den Beweis, ohne zu sehr auf die zugrundeliegende Algebra einzugehen. Falls Sie mit dem Material der nachstehenden Diskussion nicht vertraut sind, dann k¨ onnen Sie es ohne weiteres u ¨berspringen. Die obige Diskussion hat explizit gezeigt, dass die Vektorelemente Fr2 als Polynome interpretiert werden k¨onnen. Satz 1.6 1. Die Menge F2r ist in Bezug auf die oben definierte Addition und Multiplikation ein K¨ orper. 2. Es existiert ein Element α derart, dass die von null verschiedenen Elemente von ur i = 0, . . . , 2r − 2 sind. Mit anderen Worten: F2r genau die Elemente αi f¨ F2r \ {0} = {1, α, α2 , . . . , α2
r
−2
}.
(1.32)
Ein Element α, das diese Eigenschaft hat, wird primitive Wurzel genannt und erf¨ ullt r die Relation α2 −1 = 1. angig, wenn man sie als Elemente 3. Die Elemente {1, α, . . . , αr−1 } sind linear unabh¨ des Vektorraumes Fr2 u orper F2r ist). ¨ber F2 interpretiert (der isomorph zum K¨ 4. Ist α eine primitive Wurzel des K¨ orpers F2r , der mit Hilfe eines irreduziblen Polynoms P u ¨ber F2 konstruiert wurde, dann ist α eine Nullstelle eines Polynoms Q(x) = xr + qr−1 xr−1 + · · · + q1 x + q0 vom Grad r, das u ¨ber F2 irreduzibel ist. Der K¨orper, der unter Verwendung des Polynoms Q in der Definition der Multiplikation konstruiert wurde, ist isomorph zum K¨ orper, der unter Verwendung des Polynoms P konstruiert wurde. Definition 1.7 Ein Polynom Q(x) mit Koeffizienten in F2 heißt primitiv, wenn es irreduzibel ist und wenn das Polynom x eine primitive Wurzel des K¨ orpers F2r ist, der mit Hilfe des Polynoms Q(x) konstruiert wurde. Beweisskizze von Satz 1.6 1. Der Beweis ist identisch mit dem Beweis, dass Fp (auch mit Zp bezeichnet) ein ¨ K¨orper ist, falls p eine Primzahl ist (s. Ubung 24 von Kapitel 6). Der Beweis verwendet den euklidischen Algorithmus f¨ ur Polynome, mit dem man den gr¨ oßten gemeinsamen Teiler zweier gegebener Polynome findet.
26
1 Positionsbestimmung auf der Erde und im Raum
2. Die von null verschiedenen Elemente von F2r bilden eine multiplikative Gruppe G mit 2r − 1 Elementen. Jedes von null verschiedene Element y erzeugt eine endliche Untergruppe H = {y i , i ∈ N}. Der Satz von Lagrange (Satz 7.18) besagt, dass die Anzahl der Elemente von H ein Teiler der Anzahl der Elemente von G sein muss. Da H endlich ist, muss es dar¨ uber hinaus ein minimales s mit der Eigenschaft y s = 1 geben. Dieses s, das die Ordnung des Elements y genannt wird, ist gleich der Anzahl der Elemente von H. Demnach ist y eine Wurzel des Polynoms xs + 1 = 0. Wegen r ¨ s | 2r −1 ist y eine Nullstelle von R(x) = x2 −1 +1. (Ubung: warum?) Wir haben also r gezeigt, dass alle Elemente von G Nullstellen des Polynoms R(x) = x2 −1 + 1 sind. r Angenommen es gibt einen echten Teiler m von 2 − 1, so dass die Ordnung aller Elemente von G ein Teiler von m ist. Dann m¨ ussen alle Elemente von G Nullstellen des Polynoms xm +1 sein. Das ist ein Widerspruch, da dieses Polynom nur m < 2r −1 Nullstellen hat. Es existieren also Elemente yi mit Ordnungen mi (f¨ ur i = 1, . . . , n) derart, dass das kleinste gemeinsame Vielfache der mi gleich 2r − 1 ist. Demnach ist die Ordnung des Produktes y1 · · · yn = α gleich 2r − 1. 3. Wir setzen einfach voraus, dass die Elemente {1, α, . . . , αr−1 } linear unabh¨ angig sind, wenn man sie als Vektoren im Raum Fr2 interpretiert. 4. Die Vektoren {1, α, . . . , αr } sind linear abh¨angig, da in einem Vektorraum der Dimension r beliebige r + 1 Vektoren linear abh¨ angig sind. Da die Vektoren angig sind, gibt es Koeffizienten qi derart, dass αr = {1, α, . . . , αr−1 } linear unabh¨ q0 + q1 α + · · · + qr−1 αr−1 . Demnach ist α eine Wurzel des Polynoms Q(x) = xr + qr−1 xr−1 + · · · + q1 x + q0 . Dieses Polynom muss irreduzibel u ¨ber F2 sein, denn andernfalls w¨are α die Wurzel eines Polynoms mit einem Grad, der kleiner als r ist – im Widerspruch zu der Tatsache, dass die Elemente von {1, α, . . . , αr−1 } linear unabh¨angig in Fr2 sind. Bemerkung: Wir h¨ atten F2r mit dem Polynom Q(x) anstelle des Polynoms P (x) schreiben k¨onnen. Der Vorteil der letztgenannten Beschreibung besteht darin, dass wir dann immer α = x als primitive Wurzel nehmen k¨onnen. Achtung: Die Folge der αi ist bei der Berechnung modulo Q(x) nicht dieselbe wie bei der Berechnung modulo P (x)! Definition 1.8 Die Spurfunktion ist die Funktion T : F2r → F2 , die durch T (br−1 xr−1 + · · · + b1 x + b0 ) = br−1 gegeben ist. Proposition 1.9 Die Funktion T ist linear und surjektiv. Sie hat den Wert 0 auf genau alfte. der H¨alfte der Elemente von F2r und 1 auf der verbleibenden H¨ ¨ Beweis: Ubung! 1.4.2 Beweis von Satz 1.4 Wir w¨ahlen ein primitives Polynom P (x) u ¨ber F2 ,
1.4 Lineare Schieberegister
27
P (x) = xr + qr−1 xr−1 + · · · + q1 x + q0 , das es uns erm¨oglicht, den K¨ orper F2r zu konstruieren. Die qi des linearen Schieberegisters sind die Koeffizienten des Polynoms P (x). Um gute Anfangsbedingungen zu haben, w¨ ahlen wir irgendein von null verschiedenes Polynom b = br−1 xr−1 + · · · + b1 x + b0 aus F2r . Wir definieren die Anfangsbedingungen als a0 a1
= = .. .
T (b) T (xb),
ar−1
=
T (xr−1 b).
=
br−1 , (1.33)
Wir sehen uns nun an, wie der Wert von a1 berechnet wird: a1 = T (bx)
= = = =
T (br−1 xr + br−2 xr−1 + · · · + b0 x) T (br−1 (qr−1 xr−1 + · · · + q1 x + q0 ) + br−2 xr−1 + · · · + b0 x) T ((br−1 qr−1 + br−2 )xr−1 + · · · ) br−1 qr−1 + br−2 .
(1.34)
Eine ¨ahnliche Rechnung erm¨ oglicht die Bestimmung der Werte a2 , . . . , ar−1 . Die Formeln werden schnell groß, aber die Rechnungen lassen sich in der Praxis sehr schnell durchf¨ uhren, wenn die qi und bi durch Nullen und Einsen ersetzt werden. Beispiel 1.10 In Beispiel 1.5 hatten wir das Polynom P (x) = x4 + x + 1 verwendet. ¨ (Ubung: Verifizieren Sie, dass das Polynom irreduzibel und primitiv ist.) Das gew¨ ahlte Polynom b war einfach b = 1. Das f¨ uhrt zu den Anfangsbedingungen a0 = T (1) = 0, a1 = T (x) = 0, a2 = T (x2 ) = 0 und a3 = T (x3 ) = 1. Proposition 1.11 Wir w¨ ahlen die Koeffizienten q0 , . . . , qr−1 eines Schieberegisters als diejenigen eines primitiven Polynoms P (x) = xr + qr−1 xr−1 + · · · + q1 x + q0 . Es sei b = br−1 xr−1 + · · · + b1 x + b0 . Wir w¨ahlen die Anfangselemente a0 , . . . , ar−1 so wie in (1.33). Dann ist die durch das Schieberegister erzeugte Folge {an }n≥0 durch an = T (xn b) gegeben und sie wiederholt sich mit einer Periode, die 2r − 1 teilt. Beweis. Wir verwenden die Tatsache, dass P (x) = 0, das heißt, xr = qr−1 xr−1 + · · · + q1 x + q0 . Dann haben wir T (xr b) = T ((qr−1 xr−1 + · · · + q1 x + q0 )b) = qr−1 T (xr−1 b) + · · · + q1 T (xb) + q0 T (b) = qr−1 ar−1 + · · · + q1 a1 + q0 a0 = ar .
(1.35)
28
1 Positionsbestimmung auf der Erde und im Raum
Wir wenden vollst¨andige Induktion an. Wir nehmen an, dass die Elemente der Folge die ur i ≤ n − 1 erf¨ ullen. Dann ergibt sich Bedingung ai = T (xi b) f¨ T (xn b) = T (xr xn−r b) = T ((qr−1 xr−1 + · · · + q1 x + q0 )xn−r b) = qr−1 T (xn−1 b) + · · · + q1 T (xn−r+1 b) + q0 T (xn−r b) = qr−1 an−1 + · · · + q1 an−r+1 + q0 an−r = an .
(1.36)
Folglich entspricht die Multiplikation mit x genau der mit dem Schieberegister durchgef¨ uhrten Rechnung und deswegen gilt an = T (xn b) f¨ ur alle n. Wir sehen sofort, dass r die minimale Periode eine L¨ange von h¨ ochstens 2r − 1 hat, denn x2 −1 = 1. Wir k¨onnen uns fragen, was die minimale Periode dieser Folge ist. Zun¨ achst einmal ¨ muss sie ein Teiler von 2r − 1 sein (s. Ubung 11). Wir zeigen, dass die minimale Periode uhrt. W¨ are die genau 2r − 1 ist, wenn P primitiv ist. Der Beweis wird indirekt gef¨ Periode durch s ∈ N so gegeben, dass 2r − 1 = sm und 1 < s < 2r − 1, dann m¨ usste die unendliche Folge {an }n≥0 mit der Folge {an+s }n≥0 identisch sein. Wir zeigen, dass das nicht sein kann. Vergessen Sie nicht unsere urspr¨ ungliche Absicht, Folgen zu erzeugen, die mit Verschiebungen von sich selbst schlecht korrelieren. Wir berechnen gleichzeitig die Korrelation zwischen zwei beliebigen Fenstern B und C der L¨ ange M = 2r − 1, −1 n=p+M −1 wobei B = {an }n=m+M und C = {a } . n n=p n=m n=m+M −1 −1 Proposition 1.12 Ist B = {an }n=m und C = {an }n=p+M , dann gilt Cor(B, C) = n=p −1, falls M kein Teiler von p − m ist.
Beweis. Wir k¨onnen m ≤ p voraussetzen. Dann gilt Cor(B, C)
= = = = = =
M −1 (−1)am+i (−1)ap+i
i=0 m+i p+i M −1 (−1)T (x b) (−1)T (x b)
i=0 m+i p+i M −1 (−1)T (x b)+T (x b)
i=0 m+i p+i M −1 (−1)T (x b+x b)
i=0 i+m p−m M −1 )) (−1)T (bx (1+x
i=0 i+m M −1 T (x β) , i=0 (−1)
(1.37)
wobei β = b(1 + xp−m ). Aufgrund unserer Wahl von P wissen wir, dass x eine primitive Wurzel unseres K¨orpers ist. Deswegen gilt xM = 1 und xN = 1, falls 1 ≤ N < M . Wir schließen, dass xN = 1 dann und nur dann gilt, wenn M ein Teiler von N ist. Ist M ein Teiler von p − m, dann haben wir xp−m = 1 und β = b(1 + 1) = b · 0 = 0, und in diesem Fall ist Cor(B, C) = M . Ist M kein Teiler von p − m, dann ist das Polynom (1 + xp−m ) nicht das Nullpolynom; also ist β = b(1 + xp−m ) ebenfalls von null verschieden, denn es ist das Produkt zweier von null verschiedener Elemente. Somit hat β die Form xk , wobei k ∈ {0, . . . , 2r − 2}. Das impliziert, dass die Menge {βxi+m , 0 ≤ i ≤ M − 1} eine r Permutation der Elemente von F2r \ {0} = {1, x, . . . , x2 −2 } ist. Die Spurfunktion T
1.5 Kartografie
29
nimmt den Wert 1 auf der H¨alfte der Elemente von F2r an und den Wert 0 auf den verbleibenden Elementen. Da sie den Wert 0 auf dem Nullelement annimmt, nimmt sie den Wert 1 auf 2r−1 der Elemente von F2r \ {0} und den Wert 0 auf den verbleibenden 2r−1 − 1 Elementen an. Demnach gilt Cor(B, C) = −1. Korollar 1.13 Die Periode der vom linearen Schieberegister erzeugten Pseudozufallsfolge ist genau M = 2r − 1. Beweis. W¨are die Periode gleich K < M , dann w¨ urde die Folge mit ihrer Verschiebung um K Elemente u atten eine Korrelation ¨bereinstimmen, und die beiden Folgen h¨ gleich M . Das ist ein Widerspruch zu Proposition 1.12. M¨ochten wir jetzt andere Pseudozufallsfolgen derselben L¨ ange erzeugen, dann k¨ onnen wir das gleiche Prinzip anwenden, dabei aber das Polynom P (x) ¨ andern. (Wir wollen f¨ ur jeden Satelliten eine andere Folge haben.) Mit Hilfe der Galoistheorie k¨ onnen wir (in bestimmten F¨allen) die Korrelation dieser neuen Folge mit der ersten Folge und deren Verschiebungen berechnen. Die Ingenieure begn¨ ugen sich jedoch damit, diese Korrelationswerte in vorberechneten Tabellen nachzusehen.
1.5 Kartografie Wie in der Einf¨ uhrung erw¨ahnt, begegnet man auf dem Gebiet der Kartografie gewissen nichttrivialen Problemen, wenn man versucht, eine treue Darstellung der Erdoberfl¨ ache zu geben. Karten werden allgemein verwendet, damit wir uns orientieren k¨ onnen. In Abh¨angigkeit von der Anwendung kann f¨ ur uns wichtig sein, dass auf der Karte die Abst¨ande erhalten bleiben, zum Beispiel wenn wir wollen, dass der k¨ urzeste Weg zwischen zwei Punkten auf der Karte dem k¨ urzesten Weg zwischen zwei realen Punkten entspricht. Diese Bedingung ist im Allgemeinen nicht wichtig f¨ ur Landkarten, denn wenn wir mit dem Auto fahren, dann fahren wir gezwungenermaßen auf ¨ offentlichen Straßen, und wenn wir zu Fuß gehen, dann sind die auftretenden Entfernungen so klein, dass jede Abweichung vom tats¨ achlichen k¨ urzesten Weg vernachl¨ assigt werden kann. Im Gegensatz hierzu wird das Problem wahrnehmbar bei der Wahl einer Flugzeugroute oder einer Schiffsroute. Außerdem reicht es f¨ ur jemanden, der ein Segelboot oder ein kleines Flugzeug mit relativ rudiment¨ arer Ausr¨ ustung steuert, bei weitem nicht aus, die Route auf einer Karte einzuzeichnen. Es muss auch m¨ oglich sein, dass der Pilot den Kurs einhalten kann. Vor der Erfindung des GPS benutzte man in den meisten F¨allen einen Magnetkompass als wichtigstes Navigationsger¨ at. Mit einem Magnetkompass k¨onnen wir uns davon u ¨berzeugen, dass wir eine Flugbahn einhalten, die einen konstanten Winkel in Bezug auf das Magnetfeld der Erde aufrecht erh¨ alt. Eine solche Flugbahn ist nicht notwendigerweise der k¨ urzeste Weg zwischen zwei Punkten; aber es ist ein leicht einzuhaltender Weg und deswegen w¨aren Karten zweckm¨ aßig, auf denen diese Wege durch Geraden dargestellt sind. Seekarten und einige aeronautische Karten haben diese Eigenschaft. Jedoch werden auf diesen Karten einander entsprechende
30
1 Positionsbestimmung auf der Erde und im Raum
Fl¨achen nicht treu abgebildet: Zwei fl¨achengleiche Gebiete der Erdkugel werden auf der Karte im Allgemeinen nicht durch fl¨ achengleiche Gebiete dargestellt. Wir beginnen mit einer Erkl¨ arung der Spielregeln. Ein Satz der Differentialgeometrie besagt, dass es unm¨ oglich ist, einen Teil einer Kugeloberfl¨ ache so auf die Ebene abzubilden, dass sowohl Abst¨ ande als auch Winkel erhalten bleiben. (F¨ ur diejenigen, die mit der Terminologie vertraut sind: Eine solche Transformation heißt Isometrie“ und die” se erh¨alt die Gauß’sche Kr¨ ummung“ der Oberfl¨ache. Die Gauß’sche Kr¨ ummung einer ” 2 ummung einer Ebene und Kugel mit dem Radius R ist 1/R , w¨ahrend die Gauß’sche Kr¨ eines Zylinders null ist.) Wir m¨ ussen also einen Kompromiss schließen. Der jeweilige Kompromiss h¨angt von der Anwendung ab. Kartografie hat haupts¨ achlich mit Projektionen zu tun und davon gibt es viele verschiedene Typen. Projektion auf eine Tangentialebene einer Kugel. Das ist der elementarste Typ von Projektionen. Es gibt mehrere Variationen dieses Projektionstyps: Die Projektion geht durch den Kugelmittelpunkt (gnomonische Projektion); die Projektion geht durch den Punkt, der diametral entgegengesetzt zum Tangentialpunkt liegt (stereografische Projektion); die Projektion verl¨ auft l¨ angs der Geraden, die orthogonal zur Projektionsebene sind (orthografische Projektion). (Vgl. Abbildung 1.6.) Diese Familie von Projektionen liefert akzeptable Ergebnisse, wenn wir nur einen kleinen Teil der Kugel kartografisch darstellen m¨ochten, der sich in der Umgebung“ des Ber¨ uhrungspunktes befindet. ” Die Verzerrungen werden umso gr¨oßer, je weiter wir uns von diesem Ber¨ uhrungspunkt entfernen. Vom mathematischen Standpunkt sind diese Projektionen (mit Ausnahme ¨ der stereografischen Projektion, die wir in Ubung 24 diskutieren) nicht besonders interessant und wir werden sie nicht weiter behandeln. Im verbleibenden Teil dieses Abschnitts beschr¨anken wir unsere Diskussion auf Zylinderprojektionen. Nach der Projektion kann der Zylinder abgerollt werden, so dass sich eine Ebene ergibt. Wir erkennen sofort die Vorz¨ uge: Anstelle eines Ber¨ uhrungspunktes (an dem die Karte am genauesten ist) haben wir einen ganzen Ber¨ uhrungskreis rund um die Kugel. Es gibt jedoch umso st¨ arkere Verzerrungen, je weiter wir uns in Richtung der Kugelpole bewegen. Es gibt wieder mehrere Variationen dieser Projektion: In Abh¨angigkeit von der gew¨ ahlten Methode hat die resultierende Karte unterschiedliche Eigenschaften. Im Allgemeinen u ¨berwiegt der Wunsch, Breitenkreise (Breitenparallele) auf horizontale Geraden und L¨ angenkreise (Meridiane) auf vertikale Geraden abzubilden. Eine solche Projektion bedeutet, dass es eine einfache Abbildung zwischen den kartesischen Koordinaten auf der Karte und L¨ ange und Breite auf Erdkugel gibt (wobei es aber Abstandsverzerrungen zwischen unterschiedlichen Parallelen gibt). Projektion auf den Zylinder vom Kugelmittelpunkt als Projektionszentrum. Bei dieser Projektion wird die Kugeloberfl¨ache auf einen unendlichen Zylinder abgebildet, wobei die Pole auf die unendlich ferne Grund- und Deckfl¨ ache des Zylinders abgebildet werden. Diese Projektion ist von geringem Nutzen bzw. Interesse – außer der Tatsache, dass sie eine einfache Formel hat.
1.5 Kartografie
(a) Gnomonische Projektion
(b) Stereografische jektion
Pro-
31
(c) Orthografische Projektion
Abb. 1.6. Drei Typen von Projektionen auf eine Tangentialebene.
Horizontale Zylinderprojektion. Diese Projektion ist den Geografen als Lambertsche Zylinderprojektion bekannt, aber sie wurde bereits von Archimedes ausf¨ uhrlich untersucht. Es sei S eine Kugel mit Radius R, deren Oberfl¨ ache die Gleichung x2 +y 2 +z 2 = ullt. Wir m¨ ochten die Kugeloberfl¨ ache auf den Zylinder C projizieren, der die R2 erf¨ Gleichung x2 + y 2 = R2 erf¨ ullt. Die Projektion P : S → C ist durch die Formel Ry Rx , ,z (1.38) P (x, y, z) = x2 + y 2 x2 + y 2 (s. Abbildung 1.7) gegeben. Der Punkt P (x0 , y0 , z0 ) ist also der Schnittpunkt des Zylinders und der horizontalen Halbgeraden, die vom Punkt (0, 0, z0 ) (auf der vertikalen Achse) ausgeht und durch den Punkt (x0 , y0 , z0 ) geht. Zwar hat Lamberts Zylinderprojektion weniger Verzerrungen als die Zylinderprojektion mit dem Kugelmittelpunkt als Projektionszentrum, aber sie verzerrt die Abst¨ ande, ¨ wenn wir uns vom Aquator entfernen. Jedoch hat Lamberts Projektion eine bemerkenswerte Eigenschaft: sie ist fl¨ achentreu. Diese Eigenschaft wurde erstmalig von Archimedes entdeckt. Diese Projektion wurde deswegen bei der Herstellung des Peters-Atlasses gew¨ahlt (s. Abbildung 1.8). Bei Atlanten mit anderen Projektionen sind die im Norden liegenden Staaten u oßen dieser ¨bertrieben groß. Auf dem Peters-Atlas [2] sind die Gr¨ L¨ander fl¨achentreu abgebildet, obwohl sie weniger groß und breiter erscheinen. Wir beweisen jetzt diese bemerkenswerte Eigenschaft der Lambert’schen Zylinderprojektion. Satz 1.14 Die durch die Gleichung (1.38) gegebene Projektion P : S → C ist fl¨ achentreu. (In der Geografie und in der Kartografie sagt man, dass die Projektion ¨ aquivalent ist.)
32
1 Positionsbestimmung auf der Erde und im Raum
Abb. 1.7. Horizontale Zylinderprojektion.
Abb. 1.8. Die Weltkarte entsprechend Lamberts Zylinderprojektion.
Beweis. Zur Vereinfachung des Beweises ¨ andern wir zuerst unser Koordinatensystem. Wir parametrisieren die Kugel mit Hilfe zweier Winkelkoordinaten θ und φ, die unter Verwendung der folgenden Abbildungen zur¨ uck in kartesische Koordinaten abgebildet werden k¨onnen: π F : (−π, π] × [ −π 2 , 2 ] → S, (θ, φ) → F (θ, φ) = (x, y, z) = (R cos θ cos φ, R sin θ cos φ, R sin φ).
(1.39)
1.5 Kartografie
33
Das sind die sph¨arischen Koordinaten. Wir k¨onnen θ als L¨ ange interpretieren, die nicht in Grad, sondern in Bogenmaß ausgedr¨ uckt wird, wobei θ = 0 dem Nullmeridian, θ > 0 den ¨ostlichen L¨angen und θ < 0 den westlichen L¨ angen entspricht. Analog ist φ die Breite, und positive Werte von φ entsprechen den n¨ ordlichen Breiten. Auf ¨ ahnliche Weise und unter Verwendung der gleichen Parameter k¨onnen wir den Zylinder folgendermaßen parametrisieren: G : (−π, π] × [− π2 , π2 ] → C, (θ, φ) → G(θ, φ) = (x, y, z) = (R cos θ, R sin θ, R sin φ).
(1.40)
In diesen Koordinatensystemen l¨asst sich die Projektion P als Abbildung (θ, φ) → (θ, φ) schreiben. Es sei A ein Gebiet auf der Kugel und P (A) das zugeh¨ orige projizierte Gebiet auf dem Zylinder. Beide Gebiete sind Bilder ein und derselben Menge B mit π π . B ⊂ (−π, π] × − , 2 2 Die Fl¨ache von A auf der Kugel ist durch die folgende Formel gegeben (die wir in K¨ urze begr¨ unden werden): ∂F ∂F (1.41) Area(A) = ∂θ ∧ ∂φ dθ dφ, B
wobei v ∧ w das Kreuzprodukt (Vektorprodukt) von v und w bezeichnet und |v ∧ w| dessen L¨ange darstellt (s. [1] oder ein anderes Lehrbuch u ¨ber Funktionen mehrerer Ver¨anderlicher). Damit ergibt sich ∂F ∂θ ∂F ∂φ ∂F ∂F ∂θ ∧ ∂φ ∂F ∂F ∂θ ∧ ∂φ
= = =
(−R sin θ cos φ, R cos θ cos φ, 0), (−R cos θ sin φ, −R sin θ sin φ, R cos φ), (R2 cos θ cos2 φ, R2 sin θ cos2 φ, R2 sin φ cos φ),
=
R2 | cos φ|.
Analog ist f¨ ur den Zylinder die Fl¨ache von Area(P (A)) =
P (A) durch ∂G ∂G dθ dφ ∧ ∂φ B ∂θ
(1.42)
gegeben. Hier sehen wir, dass ∂G ∂θ ∂G ∂φ ∂G ∂G ∂θ ∧ ∂φ ∂G ∂G ∂θ ∧ ∂φ
= = =
(−R sin θ, R cos θ, 0), (0, 0, R cos φ), (R2 cos θ cos φ, R2 sin θ cos φ, 0),
=
R2 | cos φ|.
Man sieht leicht, dass die Integrale f¨ ur die Fl¨ achen von A und P (A) u ¨ber dem gleichen Definitionsbereich B berechnet werden m¨ ussen. Da die beiden Integranden identisch
34
1 Positionsbestimmung auf der Erde und im Raum
sind, zeigen die obigen Ausf¨ uhrungen, dass die beiden betrachteten Fl¨ achen tats¨ achlich gleich sind. Begr¨ undung der Gleichungen (1.41) und (1.42). Wir frischen hier kurz auf, wie man die entsprechenden Fl¨ achen berechnet. Wir zerschneiden B in infinitesimal kleine Rechtecke mit den Seitenl¨ angen dθ und dφ. Die Fl¨ache von A (beziehungsweise P (A)) ist gegeben durch die Summe der Fl¨achen der Bilder der Rechtecke unter der Abbildung F (beziehungsweise G). Wir betrachten die Fl¨ ache von A. Wir k¨ onnen uns dθ und dφ als kleine Strecken denken, die tangential an den Kurven φ = constant und θ = constant liegen. Demnach sind die entsprechenden Bilder kleine Strecken, die tangential an den Bildern der beiden Kurven liegen: es handelt sich um die Vektoren ∂F ∂θ dθ dφ. Diese Vektoren erzeugen im Allgemeinen ein Parallelogramm, dessen Fl¨ ache und ∂F ∂φ ∂F ∂F angen der Vektoren multipliziert durch ∂θ ∧ ∂φ dθ dφ gegeben ist (das Produkt der L¨ mit dem Sinus des Winkels zwischen den beiden Vektoren). In unserem Beweis ¨ ahnelt unter der Abbildung F dieser Teil von B einem kleinen Rechteck mit den Seitenl¨ angen R dθ| cos φ| und R dφ. Analog ist das Bild dieses Teils unter der Abbildung G ein kleines Rechteck mit den Seitenl¨ angen R dθ und R| cos φ| dφ. In beiden F¨allen haben die Bilder eine Fl¨ ache von R2 | cos φ| dθ dφ. Mercatorprojektion. Lamberts Projektion ist fl¨achentreu, aber nicht winkeltreu. Bei der Herstellung von Seekarten bevorzugt man winkeltreue Projektionen, denn diese erm¨oglichen ein leichtes Verfolgen des Kurses mit Hilfe eines Magnetkompasses. Die Mercatorprojektion M : S → C leistet genau das. Diese Projektion u ¨berdeckt den ganzen unendlich langen Zylinder. Wir verwenden hier wieder die sph¨ arischen Koordinaten (1.39) zur Darstellung eines auf der Kugel liegenden Punktes Q, der durch F (θ, φ) gegeben ist. Sein Bild unter M ist M (Q) = M (F (θ, φ)) = R cos θ, R sin θ, R log tan 12 (φ + π2 ) .
(1.43)
Wie zuvor ergibt sich die Projektion dann durch Abrollen des Zylinders. Es bezeichne θ die horizontale Koordinate (Abszisse) auf dem abgewickelten Zylinder und z die vertikale Koordinate (Ordinate). Damit erhalten wir eine Abbildung N : S → R2 der Kugel auf die Ebene. Sind (θ, φ) die sph¨ arischen Koordinaten eines Punktes Q, dann bilden wir diesen Punkt auf (1.44) N (F (θ, φ)) = θ, log tan 12 (φ + π2 ) ab (s. Abbildungen 1.9 und 1.10). ache S1 auf eine OberDefinition 1.15 Eine Abbildung N : S1 → S2 von einer Oberfl¨ fl¨ache S2 heißt konform, wenn sie winkeltreu ist. Das bedeutet: Schneiden sich zwei Kurven auf S1 im Punkt Q unter einem Winkel α, dann schneiden sich die Bilder dieser beiden Kurven auf S2 im Punkt N (Q) unter dem gleichen Winkel α.
1.5 Kartografie
35
Äquator
Abb. 1.9. Mercatorprojektion: Man projiziert auf einen Zylinder und rollt diesen ab. Eine ¨ l¨ angs eines Meridians gegebene Entfernung erscheint um so l¨ anger, je weiter sie vom Aquator weg ist.
Abb. 1.10. Eine Weltkarte unter Verwendung der Mercatorprojektion. Da die gesamte Karte eine unendliche H¨ ohe hat, zeigen wir hier nur den Teil zwischen 85◦ S und 85◦ N.
36
1 Positionsbestimmung auf der Erde und im Raum
Satz 1.16 Die in den Gleichungen (1.43) und (1.44) definierten Abbildungen M und N sind konform. Beweis. Wir begn¨ ugen uns damit, den Beweis f¨ ur die Abbildung N zu geben. Hieraus folgt die Konformit¨at von M , wenn wir uns davon u ¨berzeugen, dass das Aufrollen oder Abrollen eines Zylinders den Schnittwinkel von Kurven, die sich auf der Zylinderfl¨ ache befinden, nicht ¨andern kann. Zwei einander ber¨ uhrende Kurven werden auf zwei einander ber¨ uhrende Kurven abgebildet; deswegen gen¨ ugt es, sehr kleine Strecken zu betrachten, die tangential zum Schnittpunkt der urspr¨ unglichen Kurven verlaufen. Man betrachte einen Punkt (θ0 , φ0 ) und zwei durch diesen Punkt gehende kleine Strecken, die folgendermaßen geschrieben werden k¨onnen: v(t) w(t)
= =
(θ0 + t cos α, φ0 + t sin α), (θ0 + t cos β, φ0 + t sin β).
Wir betrachten die Tangentenvektoren F ◦ v = v1 und F ◦ w = w1 in Q = F (θ0 , φ0 ) und zeigen, dass sie den gleichen Winkel einschließen wie die Vektoren N ◦ F ◦ v = v2 und N ◦ F ◦ w = w2 in N (Q). Die Tangentenvektoren k¨ onnen mit Hilfe der Kettenregel berechnet werden und sind durch v1 (0)
R(− sin θ0 cos φ0 cos α − cos θ0 sin φ0 sin α, cos θ0 cos φ0 cos α − sin θ0 sin φ0 sin α, cos φ0 sin α), w1 (0) = R(− sin θ0 cos φ0 cos β − cos θ0 sin φ0 sin β, cos θ0 cos φ0 cos β − sin θ0 sin φ0 sin β, cos φ0 sin β), sin α v2 (0) = (cos α, cos φ0 ), sin β w2 (0) = (cos β, cos φ0 ) =
gegeben. Um zu zeigen, dass die Abbildung konform ist, verwenden wir die folgenden Kriterien: Lemma 1.17 Die Abbildung ist konform, wenn es f¨ ur alle θ0 , φ0 eine positive Konstanur alle α und β die folgende Relation f¨ ur das Skalarprodukt te λ(θ0 , φ0 ) derart gibt, dass f¨ von vi (0) und wi (0) gilt: v1 (0), w1 (0) = λ(θ0 , φ0 )v2 (0), w2 (0). vi (0)
wi (0)
(1.45)
Beweis. Es sei ψi der Winkel zwischen und f¨ ur i = 1, 2. Wir m¨ ochten zeigen, dass cos ψ1 = cos ψ2 . Ist (1.45) erf¨ ullt, dann sehen wir, dass cos ψ1
= = = = = =
v1 (0),w1 (0) |v1 (0)| |w1 (0)| v1 (0),w1 (0) v1 (0),v1 (0)1/2 w1 (0),w1 (0)1/2 λ(θ0 ,φ0 )v2 (0),w2 (0) (λ(θ0 ,φ0 )v2 (0),v2 (0))1/2 (λ(θ0 ,φ0 )w2 (0),w2 (0))1/2 v2 (0),w2 (0) v2 (0),v2 (0)1/2 w2 (0),w2 (0)1/2 v2 (0),w2 (0) |v2 (0)| |w2 (0)|
cos ψ2 .
1.5 Kartografie
37
(Die Forderung, dass λ(θ0 , φ0 ) positiv ist, gew¨ ahrleistet, dass keine Division durch null auftritt und dass die Quadratwurzeln reell sind.) Die Verifizierung von (1.45) f¨ ur die Mercatorprojektion ist etwas langwierig, vereinfacht sich aber schnell. Wir erhalten v1 (0), w1 (0) v2 (0), w2 (0)
= =
R2 (cos2 φ0 cos α cos β + sin α sin β), α sin β cos α cos β + sin cos2 φ0 .
Hieraus folgt, dass λ(θ0 , φ0 ) = R2 cos2 φ0 .
Der k¨ urzeste Weg zwischen zwei Punkten auf einer Kugel. Wir betrachten zwei Punkte Q1 und Q2 auf der Oberfl¨ache einer Kugel. Sind die Punkte nicht diametral entgegengesetzt, dann k¨onnen sie nicht kollinear mit dem Kugelmittelpunkt sein. Die beiden Punkte bestimmen also zusammen mit dem Kugelmittelpunkt eine Ebene. Die Schnittfigur der Ebene und der Kugel ist ein Großkreis, auf dem die beiden Punkte ogen, deren k¨ urzerer auf Q1 und Q2 liegen. Die Punkte teilen den Kreis in zwei Kreisb¨ der Kugeloberfl¨ache der k¨ urzeste Weg zwischen Q1 und Q2 ist. Es sei O der Kugelmittelpunkt. Dann ist die L¨ ange dieses Weges gleich Rα, wobei α ∈ [0, π) den Winkel zwischen OQ1 und OQ2 bezeichnet und R der Radius der Kugel ist. In der Seenavigation wird der k¨ urzeste Weg zwischen zwei Punkten als Orthodrome bezeichnet. In der Mathematik heißt der k¨ urzeste Weg zwischen zwei Punkten auf einer Oberfl¨ ache u ¨blicherweise Geod¨atische. Die Geod¨ atischen einer Kugel sind die Großkreise. Betrachten wir eine Karte in Mercatorprojektion, dann entspricht die Orthodrome zwischen zwei Punkten Q1 und Q2 keiner geraden Linie auf der Karte – es sei denn, die Punkte liegen auf dem gleichen L¨angenkreis. Im Vokabular der Seenavigation ist die Loxodrome zwischen zwei Punkten die Kurve, welche die beiden Punkte verbindet und s¨ amtliche Meridianlinien unter dem gleichen Winkel schneidet (deswegen wird diese Kurve auch Winkelgleiche genannt). Bei der Mercatorprojektion entspricht diese Route einer geraden Strecke, die beide Punkte verbindet, und das beweist, dass ein solcher Weg immer existiert. Eine Loxodrome ist u anger und jedenfalls nie k¨ urzer als eine Orthodrome. Bei ¨blicherweise l¨ einer Mercatorprojection der Kugel wird diese Beziehung jedoch umgekehrt (s. Abbildung 1.11). Wie man einer Trajektorie folgt. Wenn wir nur mit Hilfe der traditionellen Navigationstechniken (mit anderen Worten: ohne GPS) von Punkt A zu Punkt B gelangen wollen, dann ist es leichter, der loxodromischen Route zu folgen (die bei einer Mercatorprojektion als Strecke erscheint). Diese Trajektorie schneidet jede Meridianlinie unter einem konstanten Winkel. Das traditionelle Navigationswerkzeug ist ein einfacher Magnetkompass, der die Richtung zum magnetischen Norden anzeigt. Die Linien des Magnetfeldes, das die Erde umgibt, ¨ ahneln den Meridianlinien. Die Feldlinien gehen vom magnetischen Nordpol aus und enden am magnetischen S¨ udpol. Der magnetische Nordpol bzw. der magnetische S¨ udpol stimmt jedoch nicht vollst¨ andig mit dem Nordpol bzw. S¨ udpol der Erde u ¨berein. Außerdem sind die magnetischen Pole nicht statisch, sondern wandern langsam. Somit schneiden in der Praxis die Magnetfeldlinien die Meridianlinien in einem Winkel, und dieser Winkel ist nicht an jeder Stelle auf der Erde gleich;
38
1 Positionsbestimmung auf der Erde und im Raum
Abb. 1.11. Orthodromischer und loxodromischer Weg zwischen zwei Punkten A und B.
dar¨ uber hinaus ¨andert sich der Winkel an einem gegebenen Ort von einem Jahr zum n¨achsten. Der exakte Wert der Schwankung zwischen dem Nordpol und dem magnetische n Nordpol kann m¨ uhelos in Tabellen nachgesehen werden und wird u ¨blicherweise auf Seekarten und aeronautischen Karten angegeben. Alternativ k¨ onnen wir den Winkel auch berechnen, wenn wir unseren Standort und den Standort eines oder mehrerer nahe gelegener Orientierungspunkte kennen. Navigieren wir in einer hinreichend großen Entfernung von den Polen, dann k¨onnen wir voraussetzen, dass die Schwankung nahezu konstant ist. Um also einer loxodromischen Route zu folgen, reicht es aus, einen Kompass auf den gew¨ unschten Winkel gerichtet zu halten, der sich aus dem Winkel zwischen den Magnetfeldlinien und den Meridianlinien an der aktuellen Position errechnet. Kartografie in der N¨ ahe der Pole. M¨ ochten wir Karten von den Polargebieten machen, dann erweisen sich die oben diskutierten Projektionen als nicht sehr praktisch. An deren Stelle betrachten wir Projektionen auf schiefe Zylinder oder Kegel. Wollen wir eine winkeltreue Projektion haben, dann k¨ onnen wir die Mercatorprojektion auf einen schiefen Zylinder verwenden. In diesem Fall geht jedoch die Eigenschaft verloren, dass L¨angen- und Breitenkreise auf Geraden abgebildet werden. Wir k¨ onnen auch winkeltreue Projektionen auf die Oberfl¨ ache eines Kegels betrachten. Diese Projektionen heißen ¨ Lambert’sche Projektionen (s. zum Beispiel Ubung 26). Das UTM-Koordinatensystem. M¨ ochten wir einen Wegpunkt in einen GPS-Empf¨ anger eingeben, dann m¨ ussen wir die Koordinaten des Punktes auf einer Karte berechnen. Viele Karten benutzen das UTM-Koordinatensystem (UTM = Universal Transverse Mercator), bei dem 60 Projektionen vom gleichen Typ wie die Mercatorprojektion verwendet werden: Der Unterschied besteht darin, dass der Zylinder nicht mehr vertikal, sondern horizontal ist, und daher die Erde l¨ angs eines Meridians tangential ber¨ uhrt. Die entsprechende Projektion heißt transversale Mercatorprojektion. Eine L¨ angenzone u angenzonen im UTM-System ¨berdeckt ein 6 Grad breites L¨angenintervall. Jede der 60 L¨ beruht auf einer transversalen Mercatorprojektion. Das erm¨ oglicht es uns, ein Gebiet von einer großen Nord-S¨ ud-Ausdehnung mit einer geringf¨ ugigen Verzerrung abzubilden. Dieses System wurde urspr¨ unglich von der North Atlantic Treaty Organization (NATO) im Jahr 1947 entworfen.
¨ 1.6 Ubungen
39
¨ 1.6 Ubungen GPS (Global Positioning System) 1.
Zeigen Sie, dass der Nenner von Gleichung (1.16) dann und nur dann gleich null ist, wenn die vier Satelliten in ein und derselben Ebene liegen.
2.
Das Navigationssystem Loran (f¨ ur LOng RANge“) wurde viele Jahre lang f¨ ur die ” Meeresnavigation verwendet, insbesondere an den nordamerikanischen K¨ usten. Viele Schiffe sind immer noch mit Loran-Empf¨angern ausgestattet, weswegen das System nicht außer Dienst gestellt worden ist, obwohl sich das GPS zunehmender Beliebtheit erfreut. Loran-Sender sind in Ketten von drei bis f¨ unf Sendern angeordnet, von denen einer als Master-Station M und die anderen als Slave-Stationen W , X, Y und Z fungieren. • •
Die Master-Station sendet ein Signal. Die Slave-Station W empf¨angt das Signal, f¨ uhrt eine Zeitverz¨ ogerung von vorher festgelegter L¨ange durch und sendet dann das gleiche Signal weiter. • Die Slave-Station X empf¨angt das Signal, f¨ uhrt eine Zeitverz¨ ogerung von vorher festgelegter L¨ange durch und sendet dann das gleiche Signal weiter. • usw. Die von jeder Slave-Station durchgef¨ uhrten Verz¨ogerungen werden so gew¨ ahlt, dass keinerlei Zweifel in Bezug auf den Ursprung eines Signals aufkommen k¨ onnen, das irgendwo im Dienstbereich der Senderkette empfangen wird. Die Idee hinter dem System ist, dass der Loran-Empf¨anger (auf dem Schiff) die Phasenverschiebung zwischen den empfangenen Signalen misst. Da zwischen drei und f¨ unf Signale empfangen werden, gibt es mindestens zwei Phasenverschiebungen, die unabh¨angig sind. (a) Erkl¨aren Sie, wie wir unsere Position bestimmen k¨ onnen, wenn wir zwei Phasenverschiebungen kennen. (b) In der Praxis erm¨oglicht die Phasenverschiebung zwischen der ersten Antenne und der zweiten Antenne, dass sich der Empf¨anger auf einem Hyperbelast lokalisieren kann. Warum? Kommentar: Diese hyperbolischen Positionierungskurven werden auf den Seekarten eingezeichnet. Eine Position auf einer Seekarte l¨asst sich also als Schnittpunkt zweier hyperbolischer Kartenkurven identifizieren.
3.
Um seine Position zu berechnen, muss ein GPS-Empf¨ anger die Signallaufzeit f¨ ur vier Satelliten kennen. Wir schr¨ anken das Problem ein, indem wir voraussetzen, dass sich der Empf¨anger auf der H¨ ohe null befindet (also in Meeresh¨ ohe). Zeigen Sie, dass in diesem Fall nur drei Satelliten erforderlich sind, um die Position des Empf¨ angers zu berechnen. Erl¨autern Sie die Details der durchzuf¨ uhrenden Rechnungen.
4.
Meteoriten dringen regelm¨aßig in die Atmosph¨ are ein, erhitzen sich schnell, zerfallen und explodieren schließlich, bevor sie auf der Erdoberfl¨ ache einschlagen. Diese Explosion erzeugt eine Schockwelle, die sich mit Schallgeschwindigkeit in alle Richtungen
40
1 Positionsbestimmung auf der Erde und im Raum
ausbreitet. Die Schockwelle wird von Seismographen registriert, die an verschiedenen Standorten auf der Erdoberfl¨ ache installiert worden sind. Wir setzen voraus, dass vier Stationen (die mit perfekt synchronisierten Uhren ausgestattet sind) den Zeitpunkt registrieren, an dem die Schockwelle ankommt. Erkl¨ aren Sie, wie man sowohl den Ort als auch die Zeit der Explosion berechnet. 5.
Man betrachte eine Karte, auf der weder die L¨ angen, noch die Breiten, noch die Richtung Norden angegeben sind. Erkl¨ aren Sie, wie man aus der Kenntnis dreier Orientierungspunkte auf der Karte, die nicht auf einer Geraden liegen, die Position eines beliebigen Kartenpunktes berechnen kann. Was muss vorausgesetzt werden, damit diese Erkl¨arung funktioniert? Blitzschl¨ age und Gewitter
6.
Welches ist die Minimalzahl von Detektoren, die einen Blitzschlag registrieren m¨ ussen, damit dieser lokalisiert werden kann? Geben Sie das Gleichungssystem an, das der Zentralrechner l¨osen muss, um diese Position zu berechnen.
7.
Gegeben seien die zwei Zeiten t1 und t2 , die von den Oszilloperturbographen an beiden Enden einer Starkstromleitung der L¨ange L gemessen wurden. Berechnen Sie die Position der Leitungsst¨orung.
8.
Eine Nanosekunde ist ein Milliardstel einer Sekunde: 10−9 s. Berechnen Sie die Entfernung, die das Licht in 100 Nanosekunden zur¨ ucklegt. Leiten Sie hieraus die Genauigkeit der Position ab, die von einem System berechnet wird, das die Lichtdurchgangszeiten mit einer Genauigkeit von 100 Nanosekunden misst.
9.
Es sei P (I) die Popolansky-Funktion, und die Zufallsvariable X, welche die Stromst¨ arke von Blitzschl¨agen misst, sei gem¨aß P (I) verteilt. Berechnen Sie die Dichtefunktion f (I) von X. Was ist der Modus (der Wert von I, f¨ ur den die Dichte ihr Maximum annimmt) dieser Verteilung?
10. In anderen Gegenden wird typischerweise die in (1.17) gegebene Anderson-EriksonFunktion P verwendet, wobei M = 31 und K = 2, 6. Im Gegensatz zur PopolanskyFunktion muss man hier numerische Methoden anwenden. (a) Berechnen Sie den Median dieser Verteilung. (b) Berechnen Sie das 90. Perzentil dieser Verteilung. Mit anderen Worten, finden Sie den Wert I, f¨ ur den Prob(X ≤ I) = 0, 9. (c) Es sei vorausgesetzt, dass 58% der entdeckten Blitzschl¨ age eine Stromst¨ arke haben, die h¨oher als der Median ist. Berechnen Sie den Prozentsatz der Blitzschl¨ age, die nicht entdeckt werden. Es sei weiterhin vorausgesetzt, dass nur die schw¨ achsten Blitzschl¨ age nicht entdeckt werden. Berechnen Sie den Schwellenwert der Stromst¨ arke I0 , unter dem die Blitzschl¨age nicht entdeckt werden. (d) Berechnen Sie den Modus dieser Verteilung.
¨ 1.6 Ubungen
41
Lineare Schieberegister 11. Man betrachte eine Folge {an }, die eine Periode der L¨ ange N hat, das heißt, an+N = an f¨ ur alle n. Zeigen Sie, dass die minimale Periode dieser Folge (also die kleinste ganze ur alle n) ein Teiler von N sein muss. Zahl M mit an+M = an f¨ 12. (a) Zeigen Sie, dass das Polynom x4 + x3 + 1 primitiv u ¨ber F2 ist. (b) Berechnen Sie die Folge, die durch das lineare Schieberegister erzeugt wird, bei dem (q0 , q1 , q2 , q3 ) = (1, 0, 0, 1) und die Anfangsbedingungen durch (a0 , a1 , a2 , a3 ) = (T (b), T (xb), T (x2 b), T (x3 b)) mit b = 1 gegeben sind. Beweisen Sie, dass diese Folge eine minimale Periode der L¨ange 15 hat. (c) Zeigen Sie, dass diese Folge nicht dieselbe ist wie in Beispiel 1.5. (d) Berechnen Sie die Korrelation zwischen dieser Folge und den verschiedenen Verschiebungen der Folge von Beispiel 1.5. 13. Zeigen Sie, dass das Polynom x4 +x3 +x2 +x+1 nicht primitiv u ¨ber F2 ist. Berechnen Sie die Folge, die durch das lineare Schieberegister mit (q0 , q1 , q2 , q3 ) = (1, 1, 1, 1) und den Anfangsbedingungen (a0 , a1 , a2 , a3 ) = (T (b), T (xb), T (x2 b), T (x3 b)) mit b = 1 erzeugt wird. Beweisen Sie, dass diese Folge eine minimale Periode mit einer L¨ ange hat, die kleiner als 15 ist. Einige elementare Methoden der Positionsberechnung Vor der Erfindung des GPS verwendete die Menschheit mehrere andere (mathematische!) Methoden und geniale Instrumente zur Positionsberechnung: die Position des Polarsterns, die Position der Sonne zur Mittagszeit, den Sextanten usw. Einige dieser Techniken sind auch heute noch in Gebrauch. Auch wenn das GPS viel genauer und einfach zu bedienen ist, k¨ onnen wir nicht garantieren, dass das System niemals versagt, oder dass wir immer einen Satz von neuen Batterien zur Hand haben. Daher sind diese einfacheren Techniken auch weiterhin wichtig und werden eingesetzt. 14. Der Polarstern befindet sich ziemlich nahe an der Rotationsachse der Erde und ist nur von der n¨ordlichen Halbkugel aus sichtbar. (a) Unter welchem Winkel u ¨ber dem Horizont sehen wir den Polarstern, wenn wir uns auf dem 45. Breitenkreis befinden? Und was ist, wenn wir uns auf dem 60. Breitenkreis befinden? (b) Angenommen, Sie sehen den Polarstern unter dem Winkel θ u ¨ber dem Horizont. Auf welcher Breite befinden Sie sich? 15. Die Rotationsachse der Erde bildet einen Winkel von 23,5 Grad mit der Normalen zur ekliptischen Ebene (also der Ebene, in der sich die Erde um die Sonne bewegt). (a) Der n¨ordliche Polarkreis liegt bei 66,5 Grad n¨ ordlicher Breite. Unter welchem Winkel u ahrend der Tagundnachtgleiche, ¨ber dem Horizont sehen Sie mittags die Sonne w¨ wenn Sie sich auf dem n¨ordlichen Polarkreis befinden. Und wie groß ist der Winkel
42
1 Positionsbestimmung auf der Erde und im Raum
w¨ahrend der Sommersonnenwende? W¨ ahrend der Wintersonnenwende? (Die letztere Eigenschaft f¨ uhrte zum Namen dieses speziellen Breitenkreises.) (b) Beantworten Sie die gleiche Frage unter der Annahme, dass Sie sich auf dem ¨ Aquator befinden. (c) Beantworten Sie die gleiche Frage unter der Annahme, dass Sie sich auf 45 Grad n¨ordlicher Breite befinden. (d) Der Wendekreis des Krebses befindet sich auf 23,5 Grad n¨ ordlicher Breite. Zeigen Sie, dass die Sonne w¨ahrend der Sommersonnenwende mittags senkrecht u ¨ber dem Wendekreis des Krebses steht. ¨ (e) Uber welchen Punkten der Erdoberfl¨ache steht die Sonne mittags an mindestens einem Tag des Jahres senkrecht? 16. Wir k¨onnen auch die Mittagsh¨ ohe der Sonne verwenden, um die Breite zu berechnen. Berechnen Sie die Breite Ihres Standorts, wenn die Sonne w¨ ahrend der Sommersonnenwende mittags unter einem Winkel θ u ¨ber dem Horizont steht. Beantworten Sie dieselbe Frage, wenn es sich um die Tagundnachtgleiche und um die Wintersonnenwende handelt.
17.
Zur Bestimmung der ungef¨ ahren L¨ ange Ihres Standorts k¨ onnen Sie folgende Technik anwenden. Stellen Sie Ihre Uhr auf die Ortszeit des Greenwich-Meridians (also des Nullmeridians). Registrieren Sie die angezeigte Zeit, wenn die Sonne im Zenit steht. Wie k¨onnen Sie diese Information nutzen, um die L¨ange Ihres Standorts zu berechnen? Diese Methode ist nicht u ¨bertrieben genau, da es ziemlich schwierig ist festzustellen, dass die Sonne im Zenit steht. Deswegen interpolieren Navigatoren zur See typischerweise die Ergebnisse zweier Messungen, von denen die eine vor dem Zenit und die andere danach durchgef¨ uhrt worden ist.
¨ 18. Die Funktionsweise eines Sextanten: Wie in den Ubungen 14 und 17 gezeigt, k¨onnen wir L¨ange und Breite dadurch bestimmen, dass wir den Winkel der Sonne oder des Polarsterns u on, aber ¨ber dem Horizont messen. Das ist in der Theorie gut und sch¨ wie f¨ uhren wir in der Praxis eine genaue Messung durch, wenn wir auf einem schaukelnden Boot stehen? Das ist der Augenblick, in dem sich der Sextant als n¨ utzlich erweist. Sextanten benutzen ein System von zwei Spiegeln. Der Navigator reguliert den Winkel zwischen den zwei Spiegeln so lange, bis er das Spiegelbild der Sonne oder des Polarsterns auf der Horizontlinie sieht, wie in Abbildung 1.12 gezeigt wird. (a) Zeigen Sie: Ist θ der Winkel zwischen den zwei Spiegeln, dann ist 2θ der Winkel, den die Sonne oder der Polarstern u ¨ber dem Horizont bildet. (b) Erkl¨aren Sie, warum die Messung durch das Schaukeln des Bootes nicht u aßig ¨berm¨ beeinflusst wird. Kartografie ache 19. Man betrachte zwei Punkte Q1 = (x1 , y1 , z1 ) und Q2 = (x2 , y2 , z2 ) auf der Oberfl¨ einer idealisierten kugelf¨ormigen Erde mit Radius R. Die L¨ angen dieser beiden Punkte
¨ 1.6 Ubungen
43
Sonne
großer Spiegel
kleiner Spiegel reflektierte Sonne
Beobachter
¨ Abb. 1.12. Die Funktionsweise eines Sextanten (Ubung 18).
seien θ1 und θ2 und die Breiten seien φ1 bzw. φ2 . Berechnen Sie die minimale Entfernung, die diese beiden Punkte l¨ angs der Erdoberfl¨ache haben. 20. Gegeben sei eine Karte, die mit Hilfe der standardm¨ aßigen Mercatorprojektion hergestellt wurde. Berechnen Sie die Gleichung der Orthodrome zwischen dem Punkt der L¨ange 0◦ und der Breite 0◦ sowie dem Punkt der L¨ ange 90◦ W und der Breite 60◦ N. 21. Gegeben sei eine Karte, die mit Hilfe der horizontalen Zylinderprojektion hergestellt wurde. Berechnen Sie die Gleichung der Orthodrome zwischen dem Punkt der L¨ ange 0◦ ◦ ◦ ◦ und der Breite 0 sowie dem Punkt der L¨ ange 90 W und der Breite 60 N. 22. Man betrachte die Projektion einer Kugel auf einen senkrechten Zylinder, wobei der Kugelmittelpunkt das Projektionszentrum sei. (a) Geben Sie die Formel an, mit der die Projektion beschrieben wird. (b) Worauf werden die Meridiane abgebildet? Worauf die Breitenkreise? (c) Was ist das Bild eines Großkreises? 23. Kegelprojektionen verwenden Kegel, die eine Kugel ber¨ uhren oder schneiden, wobei der Kugelmittelpunkt das Projektionszentrum ist. Stellen Sie sich eine Kegelprojektion vor
44
1 Positionsbestimmung auf der Erde und im Raum
und zeichnen Sie das Gitter der Meridiane und der Breitenkreise auf den abgewickelten Kegel. 24. Stereografische Projektion: Man betrachte die Projektion einer Kugel auf eine Ebene, welche die Kugel tangential in einem Punkt P ber¨ uhrt. Es sei P derjenige Punkt auf der Kugel, der diametral entgegengesetzt zum Punkt P liegt. Die Projektion wird wie folgt durchgef¨ uhrt: Ist Q ein Punkt auf der Kugel, dann ist seine Projektion der Schnittpunkt der Geraden P Q mit der Ebene, welche die Kugel in P ber¨ uhrt. (a) Geben Sie die Formel dieser Projektion f¨ ur den Fall an, dass P der S¨ udpol ist und die Kugel den Radius 1 hat. (In diesem Fall ist der Punkt P der Nordpol und die Tangentialebene wird durch die Gleichung z = −1 beschrieben.) (b) Zeigen Sie, dass diese Projektion winkeltreu ist. 25. Zur genauen Darstellung der Erde m¨ ussen wir als Modell ein Rotationsellipsoid 2
y a2
2
x2 a2
+
+ zb2 = 1 nehmen. Die sph¨ arischen Koordinaten eines Ellipsoids lassen sich in der Form (x, y, z) = (a cos θ cos φ, a sin θ cos φ, b sin φ) schreiben. Der L¨angenbegriff ist der gleiche wie im Fall einer Kugel, aber die meisten Geografen tendieren zur Verwendung der geod¨ atischen Breite, die folgendermaßen definiert ist: Die geod¨ atische Breite eines Punktes P auf einem Ellipsoid ist der Winkel ¨ zwischen dem Normalvektor im Punkt P und der Aquatorebene (d. h. der Ebene z = 0). Berechnen Sie die geod¨atische Breite als Funktion von φ. 26. Lamberts winkeltreue Kegelprojektion: Man betrachte die Kugel x2 + y 2 + z 2 = 1 und einen Kegel mit Spitze u ¨ber dem Nordpol in einem Punkt der z-Achse. (a) Welches sind die Koordinaten der Kegelspitze, wenn der Kegel die Kugel l¨ angs des Breitenkreises φ0 ber¨ uhrt? (b) Zerschneiden wir den Kegel entlang dem Meridian θ = π und wickeln wir den Kegel anschließend ab, dann erhalten wir einen Kreissektor. Zeigen Sie, dass der Winkel an der Spitze dieses Sektors gleich 2π sin φ0 ist. (c) Zeigen Sie, dass der Abstand ρ0 zwischen der Kegelspitze und s¨ amtlichen Punkten, an denen sich der Kegel und die Kugel ber¨ uhren, gleich ρ0 = cot φ0 ist. (d) Schwieriger! Wir nehmen an, dass der Sektor so abgewickelt und ausgerichtet ist, wie in Abbildung 1.13 dargestellt. Die Lambert’sche Projektion der Kugel auf diesen abgewickelten Sektor ist folgendermaßen definiert. Es sei (x, y, z) = (cos θ cos φ, sin θ cos φ, sin φ) ein Punkt auf der Kugel. Man bilde diesen Punkt auf den Punkt X = ρ sin ψ, Y = ρ0 − ρ cos ψ ab, wobei
¨ 1.6 Ubungen
45
Berührungsbreitenkreis
¨ Abb. 1.13. Abwickeln des Kegels f¨ ur Ubung 26: Ist P ein Punkt, dann bilden ρ = |AP | und . ψ den Winkel OAP
⎧ ⎨
ρ = ρ0
tan 12 ( π 2 −φ) tan 12 ( π 2 −φ0 )
sin φ0
,
⎩ψ = θ sin φ . 0
Beweisen Sie, dass die durch (x, y, z) → (X, Y ) gegebene Projektion der Kugel auf den Kegel winkeltreu ist.
46
1 Positionsbestimmung auf der Erde und im Raum
Literaturverzeichnis [1] [2] [3] [4]
M. Do Carmo, Differential Geometry of Curves and Surfaces. Prentice Hall, 1976. A. Peters (Herausgeber), Peters World Atlas. Turnaround Distribution, 2002. P. Richardus und R. K. Adler, Map Projections. North-Holland, 1972. E. F. Taylor und J. A. Wheeler, Exploring Black Holes: Introduction to General Relativity. Addison Wesley Longman, New York, 2000. (Kapitel 1 und 2 sowie Projekt u ¨ber GPS.)
2 Friese und Mosaike
In diesem Kapitel diskutieren wir die Klassifikation von Friesen sowie einige Begriffe, die mit Mosaiken zusammenh¨ angen. Im ersten Abschnitt f¨ uhren wir Operationen ein, bei denen ein Fries unver¨ andert bleibt; dabei st¨ utzen wir uns nur auf elementare Geometrie und auf unsere Intuition. Wir beschreiben auch die Hauptschritte des Klassifikationssatzes. Abschnitt 2.2 definiert affine Transformationen, deren Matrizendarstellung und Isometrien. Der H¨ ohepunkt dieses Kapitels ist der Klassifikationssatz, der in Abschnitt 2.3 bewiesen wird. Weniger ausf¨ uhrlich werden im letzten Abschnitt Mosaike diskutiert. Das vorliegende Kapitel enth¨ alt keine fortgeschrittenen Abschnitte – der Beweis des Klassifikationssatzes ist der schwierigste Teil. Die Abschnitte 2.1 und 2.4 lassen sich in drei Vorlesungsstunden behandeln. Die Werkzeuge sind rein geometrisch und wir erl¨ autern die M¨ oglichkeit der Klassifizierung. Ist der Klassifikationssatz das Ziel, dann sollten den ersten drei Abschnitten vier Vorlesungsstunden gewidmet werden. In allen F¨ allen sollte der Dozent Folien der Abbildung 2.2 mitbringen. Das Vorf¨ uhren der Folien mit einem Projektor hilft den Studenten, den Begriff der Symmetrie schnell zu verstehen. Zum Verst¨ andnis des vorliegenden Kapitels werden nur Grundkenntnisse der linearen Algebra und der euklidischen Geometrie vorausgesetzt. Der Beweis des Klassifikationssatzes erfordert Vertrautheit mit dem abstrakten Denken. Dieses Thema bietet mehrere interessante Richtungen f¨ ur weitere Untersuchungen: Die aperiodischen Parkettierungen (Ende von Abschnitt 2.4) sind eine solche Richtung, ¨ w¨ ahrend die Ubungen 13, 14, 15 und 16 verschiedene andere aufzeigen.
Friese und Mosaike werden seit mehreren Jahrtausenden als Dekoration verwendet. ¨ In der Antike wurden sie von den Zivilisationen der Sumerer, Agypter und Mayas effektvoll eingesetzt. Es w¨ are jedoch falsch zu behaupten, dass die damalige Mathematik die Technik“ entwickelt hat, die der Kunst zugrundeliegt. Die formal mathematische ” Untersuchung von Parkettierungen ist relativ neuen Ursprungs und begann vor nicht mehr als zwei Jahrhunderten. Die Arbeit von Bravais [1], einem franz¨ osischen Physiker, geh¨ort zu den ersten wissenschaftlichen Untersuchungen des Gegenstandes. Die Mathematik verf¨ ugt u oglichkeit zur systematischen Klassifizierung der ¨ber die M¨ Friese und Mosaike, die man u ¨blicherweise in der Architektur und in der Kunst sieht.
C. Rousseau, Y. Saint-Aubin, Mathematik und Technologie, DOI 10.1007/978-3-642-30092-9_2, © Springer-Verlag Berlin Heidelberg 2012
48
2 Friese und Mosaike
Abb. 2.1. Sieben Friese. (Jedes der Muster der obigen Friese ist in vereinfachter Form in Abbildung 2.2 dargestellt.)
2 Friese und Mosaike
49
Abb. 2.2. Sieben vereinfachte Friese. (Jeder der obigen Friese ist eine vereinfachte Form des entsprechenden Frieses von Abbildung 2.1.)
50
2 Friese und Mosaike
Diese Klassifikationen gestatten es den Mathematikern, die dahinter stehenden Regeln besser zu verstehen und durch Verletzung einiger dieser Regeln neue Muster zu schaffen. Die Klassifizierung von Objekten ist eine ziemlich verbreitete mathematische T¨ atigkeit. Der Leser, der eine Vorlesung u ort hat, ¨ber Funktionen mit mehreren Variablen geh¨ erinnert sich an die Klassifikation der station¨aren Werte einer Funktion zweier Variabler unter Verwendung des Testes der zweiten partiellen Ableitung. Ist die Matrix der zweiten Ableitungen (die Hesse’sche Matrix) nicht singul¨ar, dann kann der station¨ are Wert entweder als lokales Minimum oder als lokales Maximum oder als Sattelpunkt klassifiziert werden. Dem Leser ist vielleicht auch die Klassifikation der Kegelschnitte in einem fortgeschrittenen Kurs u ¨ber lineare Algebra oder euklidische Geometrie begegnet. Und f¨ ur diejenigen, die Kapitel 6 u ¨ber fehlerkorrigierende Codes gelesen haben, bemerken wir: Die S¨atze 6.17 und 6.18 klassifizieren die endlichen K¨ orper. Das alles sind Beispiele f¨ ur Klassifikationen von abstrakten Objekten. Es mag u ¨berraschend sein zu erfahren, dass die Mathematik dazu in der Lage ist, so konkrete Objekte wie architektonische Muster zu klassifizieren. Das geschieht folgendermaßen.
2.1 Friese und Symmetrien Ein Fries oder Bandornament bezeichnet in der Architektur einen schmalen Streifen, der einen Teil eines Bauwerks abgrenzt und dekoriert. Oft dienen sie dazu, eine Fassade zu gliedern. Friese werden auch als streifenf¨ormige, sich wiederholende Ornamente definiert. Abbildung 2.1 zeigt sieben Friese aus der Architektur. Um diese Objekte mathematisch zu diskutieren, modifizieren wir die Definition, damit sie folgende Bestandteile enth¨alt: (i) ein Fries hat eine konstante und endliche Breite (die H¨ ohe des Frieses in Abbildung 2.1) und ist in der senkrechten Richtung (die horizontale Richtung in unseren Beispielen) unendlich lang; und (ii) er ist periodisch, das heißt, es gibt einen minimalen Abstand L > 0 derart, dass eine Translation des Frieses um einen Abstand L l¨ angs der Richtung, in der er unendlich ist, den Fries invariant l¨ asst. Die L¨ ange L heißt Periode des Frieses. Diese Definition passt nicht perfekt zu Friesen der realen Welt (insbesondere nicht zu denjenigen von Abbildung 2.1), weil diese nicht unendlich lang sind. Wir k¨onnen uns jedoch leicht vorstellen, die real existierenden Friese durch eine einfache Fortsetzung des Musters in beide Richtungen unendlich zu erweitern. In Abbildung 2.2 sind sieben weitere Friese zu sehen. Sie sind weitaus weniger detailliert dargestellt, aber viel einfacher zu untersuchen. Jeder dieser sieben Friese hat die gleiche Periode L, die gleich dem Abstand zwischen zwei benachbarten vertikalen Strichen ist. In der weiteren Diskussion stellen wir uns vor, dass diese vertikalen Striche im Friesmuster nicht auftreten, denn wir haben sie nur eingezeichnet, um die Periode explizit darzustellen. Einige dieser Friese sind nicht nur gegen¨ uber Translationen invariant, sondern auch gegen¨ uber anderen geometrischen Transformationen. Zum Beispiel bleiben der dritte und der siebente Fries sogar dann unver¨ andert, wenn wir sie so umdrehen, dass wir oben und unten vertauschen. In diesem Fall sagen wir, dass sie invariant gegen¨ uber Spiegelungen an einem horizontalen Spiegel sind. Der zweite, sechste und sie-
2.1 Friese und Symmetrien
51
bente Fries bleiben unver¨andert, wenn sie von links nach rechts umgedreht werden; wir sagen, dass sie invariant gegen¨ uber Spiegelungen an einem vertikalen Spiegel sind. Diese Unterscheidungen zwischen verschiedenen Friesen werfen eine nat¨ urliche Frage auf: Ist es m¨oglich, alle Friese zu klassifizieren, indem man die Menge der Operationen betrachtet, gegen¨ uber denen sie invariant sind? Zum Beispiel geh¨ oren weder die horizontalen noch die vertikalen Spiegelungen, die wir gerade erw¨ ahnt haben, zu derjenigen Menge von Operationen, die den ersten Fries unver¨andert lassen. Diese Menge von Operationen unterscheidet sich von derjenigen, die den dritten Fries charakterisieren, der horizontal gespiegelt werden kann. Beachten Sie, dass die Friese der Abbildungen 2.1 und 2.2 so angeordnet worden sind, dass sie die jeweils gleichen Symmetrien aufweisen. Einander entsprechende Paare bleiben also bei den gleichen Operationen unver¨ andert. Zum Beispiel ist bei beiden Abbildungen der dritte Fries invariant gegen¨ uber Translationen und horizontalen Spiegelungen. Wenn eine l¨angentreue geometrische Transformation (wie etwa eine Translation oder eine Spiegelung) einen Fries unver¨andert l¨ asst, dann bezeichnet man sie als Symmetrieoperation des Frieses oder einfach als Symmetrie. Die vollst¨ andige Liste der Symmetrien eines Frieses ist unendlich. Wir m¨ochten in dieser Liste die Translationen um einen Abstand der Periode L von Translationen um Abst¨ ande der Perioden 2L, 3L usw. unterscheiden, und diese stellen bereits f¨ ur sich eine unendliche Anzahl von Symmetrieoperationen dar. Außerdem sollte die Liste auch die Inverse einer jeden Symmetrieoperation enthalten. Die Inverse einer Symmetrieoperation ist die gew¨ ohnliche Inverse einer Funktion: Die Zusammensetzung einer Funktion und ihrer Inversen ist die identische Abbildung (kurz: Identit¨ at) in der Ebene (oder – wie im vorliegenden Fall – auf der von den Friesen definierten Teilmenge). Die Inverse einer Translation um einen Ab¨ stand L nach rechts ist die Translation um denselben Abstand nach links. (Ubung: Was ist die Inverse einer Spiegelung an einem gegebenen Spiegel? Und was ist die Inverse einer Drehung um einen Winkel θ?) Werden Translationen nach rechts (beziehungsweise nach links) positive Abst¨ande (beziehungsweise negative Abst¨ ande) zugeordnet, dann sollte die Liste der Symmetrien eines Frieses der Periode L alle Translationen um einen Abstand nL mit n ∈ Z enthalten. Anstelle einer Auflistung aller Symmetrien eines Frieses gibt man u ¨blicherweise nur eine Teilmenge von Elementen an, deren Zusammensetzungen und Inverse die ganze Liste liefern. Eine solche Teilmenge heißt Menge von Erzeugenden (oder Erzeugendenmenge). Ab jetzt werden wir mit diesen Mengen arbeiten. (Die Mathematiker geben gew¨ohnlich eine m¨ oglichst kleine Erzeugendenmenge an. Eine Erzeugendenmenge heißt minimal, falls nach Weglassen eines ihrer Elemente die Teilmenge der restlichen Elemente nicht mehr alle Symmetrien erzeugt.) Im verbleibenden Teil dieses Abschnitts haben wir das Ziel, die geometrische Intuition f¨ ur die Schl¨ usselideen zu entwickeln, die zum Klassifikationssatz f¨ uhren (Satz 2.12). Dieser Satz gibt alle m¨oglichen Listen von Symmetrie-Erzeugenden f¨ ur Friese einer gegebenen Periode an. Vor dem Weiterlesen raten wir dem Leser, sich auf einer Folie eine Kopie der Abbildung 2.2 zu machen und sie in sieben Streifen zu zerschneiden, einen f¨ ur jeden Fries. Experimentieren ist ein ideales Mittel, um die Intuition zu entwickeln!
52
2 Friese und Mosaike
Die drei Erzeugenden tL , rh und rv . Wir haben bereits einige m¨ ogliche Symmetrieoperationen eingef¨ uhrt: Translationen (um ein beliebiges ganzzahliges Vielfaches der Periode) sowie Spiegelungen an einem horizontalen und einem vertikalen Spiegel. Wir verwenden f¨ ur die beiden letztgenannten Operationen die Symbole rh und rv .1 Die Menge der Translationen eines Frieses ist durch die eindeutig definierte Translation tL um eine Periode L gegeben. (Die zu tL inverse Translation ist t−L . Die Zusammensetzung von n Operationen tL liefert tL ◦ tL ◦ · · · ◦ tL = tnL .) Eine Feinheit sollte gleich gekl¨art werden. Damit die Spiegelung rh den Fries unver¨andert l¨asst, muss der horizontale Spiegel l¨angs der Mittellinie des Frieses (gestrichelte Linien in Abbildung 2.2) aufgestellt werden. Seine Position ist also durch die Forderung vollst¨andig bestimmt, dass es sich um eine Symmetrie handelt. Das ist nicht der Fall bei Spiegelungen an einem vertikalen Spiegel. Die Positionen von vertikalen Spiegeln m¨ ussen entsprechend dem Muster gew¨ ahlt werden. Der Fries 2 (in Abbildung 2.2 der zweite Fries von oben) hat eine unendliche Menge von vertikalen Spiegeln. Alle kleinen vertikalen Linien definieren eine Position f¨ ur einen vertikalen Spiegel. Aber diese sind nicht die einzigen. Ein Spiegel, der sich in der Mitte zwischen zwei benachbarten ¨ vertikalen Strichen befindet, definiert ebenfalls eine Symmetrie dieses Frieses. Ubung 7 zeigt: Bleibt ein Fries der Periode L bei einem gegebenen vertikalen Spiegel unver¨ andert, dann bleibt dieser Fries auch bei einer unendlichen Anzahl von Spiegeln invariant, von denen jeder einen Abstand n L2 (n ∈ Z) vom erstgenannten Spiegel hat. Die Notation rv beinhaltet deswegen die Auswahl der Position eines Spiegels sowie aller anderen vertikalen Spiegel, die vom ersten Spiegel einen Abstand haben, der ein ganzzahliges Vielfaches ¨ von L2 ist. (Ubung: Welche anderen Friese der Abbildung haben eine Symmetrie rv ?) Notation. Wir werden die Zusammensetzung von Symmetrieoperationen im Weiteren h¨aufig verwenden und dabei das Symbol ◦“ weglassen. Zum Beispiel schreiben wir ” anstelle von rh ◦ rv einfach rh rv . Bald wird es sich auch als notwendig herausstellen, die Reihenfolge der Operationen zu unterscheiden. Es ist wichtig zu beachten, dass die Operationen von rechts nach links angegeben werden. Die zusammengesetzte Operation rh rv steht also f¨ ur die Operation rv gefolgt von rh . Die Drehung rh rv . Der Fries 5 macht uns mit einem neuen erzeugenden Element bekannt. Dieser Fries hat weder rh noch rv als Symmetrie, aber wenn zuerst rv und danach rh angewendet wird, dann bleibt der Fries unver¨ andert. (Der vertikale Spiegel befindet ¨ sich l¨angs des vertikalen Strichs.) (Ubung: Beweisen Sie diese Behauptung!) Es kann vorkommen, dass weder rh noch rv eine Symmetrie ist, wohl aber ihre Zusammensetzung rh rv . Das Endresultat rh rv dieser beiden Spiegelungen ist eine Drehung um den Winkel 180◦ . Um das einzusehen, beachte man, dass rh rv oben und unten sowie links und rechts vertauscht, ohne dabei die Abst¨ ande zu ver¨andern. Das ist genau die Wirkung einer Drehung um 180◦ . (In Bezug auf ein Koordinatensystem, dessen Ursprung auf einem vertikalen Strich liegt, wird bei dieser Transformation ein auf dem Fries liegender Punkt (x, y) in (−x, −y) u uhrt. Deswegen wird diese Operation auch als Symmetrie ¨berf¨ 1
Der Buchstabe r steht als Abk¨ urzung f¨ ur reflection (Spiegelung).
2.1 Friese und Symmetrien
53
¨ in Bezug auf den Ursprung bezeichnet.) In Ubung 8 geht es um einen geometrischen Beweis dieser Eigenschaft. Die folgenden Eigenschaften der drei Erzeugenden rh , rv und rh rv lassen sich leicht u ufen – geometrisch oder mit Hilfe der Folie, die Sie von der Abbildung angefer¨berpr¨ tigt haben. Die Eigenschaften k¨ onnen auch unter Verwendung der Matrizendarstellung ¨ bewiesen werden, die wir in Abschnitt 2.2 einf¨ uhren. (Vgl. Ubung 6.) Proposition 2.1 1. Die Operationen rh und rv sind kommutativ, das heißt, die beiden Zusammensetzungen rh rv und rv rh sind gleich. 2. Die Inverse von rh ist rh , die von rv ist rv und die von rh rv ist rh rv . 3. Die Zusammensetzung von rh und rh rv ergibt rv . Die Zusammensetzung von rv und rh rv ergibt rh . (Das erm¨ oglicht uns die Schlussfolgerung: Sind bei einem Fries irgend zwei der drei Operationen rh , rv , rh rv Symmetrien, dann ist automatisch auch die dritte Operation eine Symmetrie.) Mit diesen Eigenschaften sollte der Beweis leicht sein, welche der Operationen rh , ¨ F¨ uhren rv und rh rv Symmetrien der in Abbildung 2.2 gegebenen Friese sind. (Ubung: Sie das f¨ ur alle dortigen Friese durch!)
Abb. 2.3. Eine Gleitspiegelung. Der Fries 4 wie er in Abbildung 2.2 auftritt (obere Zeile), der gleiche Fries nach der Operation rh (mittlere Zeile) und nach einer Translation um eine Halbperiode (untere Zeile).
Die Gleitspiegelungssymmetrie sg = tL/2 rh . Gem¨ aß der vorhergehenden Proposition besteht die Liste der m¨ oglichen Erzeugenden aus tL , rh , rv und rh rv . Jede der Operationen rh , rv und rh rv ist eine Symmetrie von mindestens einem der Friese von Abbildung 2.2 und keine Symmetrie von mindestens einem anderen Fries. Aber der Fries 4 zeigt, dass diese Liste noch nicht vollst¨ andig ist. Keine der Operationen rh , rv , rh rv ist
54
2 Friese und Mosaike
eine Symmetrie dieses Frieses. Aber eine Spiegelung rh und eine anschließende Translatiandert. (Vgl. Abbildung 2.3. Denken Sie on um eine Halbperiode L2 l¨asst den Fries unver¨ daran, dass die vertikalen Striche nicht Bestandteil des Musters ist.) Wir nennen diese Operation eine Gleitspiegelung und bezeichnen sie mit sg . Mit Hilfe der Zusammenset¨ zung k¨onnen wir sie in der Form sg = tL/2 rh schreiben. (Ubung: Nur ein weiterer der anderen Friese von Abbildung 2.2 hat sg unter seinen Symmetrien. Um welchen Fries handelt es sich?) Der Weg in Richtung Klassifikationssatz. Die Liste der m¨ oglichen Erzeugenden enth¨alt jetzt f¨ unf Operationen (tL , rh , rv , rh rv , sg ). Die Liste entstand durch eine Untersuchung von Abbildung 2.2. Um die vollst¨ andige Liste der Symmetriemengen von Friesen zu erhalten, ben¨otigen wir s¨ amtliche m¨oglichen Symmetrieoperationen von Friesen. Woher wissen wir, dass die Liste der obigen f¨ unf Operationen vollst¨ andig ist? K¨ onnte es nicht einen anderen Fries geben, der eine Symmetrie hat, die sich nicht aus diesen f¨ unf ableiten l¨asst? Das sind die ersten Fragen, die wie beantworten m¨ ussen, um den Klassifikationssatz zu beweisen. Wir wollen f¨ ur den Moment annehmen, dass diese Liste vollst¨ andig ist. Wir k¨ onnen dann die potentiellen Symmetriemengen f¨ ur Friese der Periode L aufz¨ ahlen. Wie oben erw¨ahnt, machen wir das durch die Identifikation einer Erzeugendenmenge . Definitionsgem¨aß enthalten alle Mengen die Translation tL um einen Abstand L und keine k¨ urzeren Translationen. Jede Menge enth¨alt entweder null oder eine oder zwei der drei alt sie automaErzeugenden rh , rv , rh rv . (Enth¨alt die Liste zwei Erzeugende, dann enth¨ tisch auch die dritte Erzeugende.) Diese Feststellungen f¨ uhren zur folgenden Liste. 1. tL 2. tL , rv 3. tL , rh 4. tL , sg 5. tL , rh rv 6. tL , sg , rh rv 7. tL , rh , rv 8. tL , sg , rh 9. tL , sg , rv 10. tL , sg , rh , rv Alle diese Mengen enthalten tL . Die Mengen 1 und 4 enthalten keine der Operationen rh , rv , rh rv . Die Menge 4 enth¨ alt sg , aber die Menge 1 enth¨ alt diese Operation nicht. Die Mengen 2, 3, 5, 6, 8 und 9 enthalten eine und nur eine der Operationen rh , rv , rh rv ; die Mengen 6, 8, 9 enthalten auch die Gleitspiegelung sg , aber die Mengen 2, 3, 5 enthalten die Gleitspiegelung nicht. Die Mengen 7 und 10 enthalten zwei der Operationen rh , rv , rh rv (und deswegen auch alle drei). Die Menge 10 enth¨ alt dar¨ uber hinaus sg . Der Klassifikationssatz muss noch zwei weitere Fragen l¨ osen. Die erste Frage ist, ob unsere Liste Wiederholungen enth¨ alt. Da wir nur die Erzeugenden auflisten, k¨ onnten zwei von ihnen ein und dieselbe Liste von Symmetrien liefern. Die zweite Frage ist,
2.2 Symmetriegruppen und affine Transformationen
55
ob einige der Mengen keine Symmetrien von Friesen der Periode L erzeugen. Diese Frage klingt vielleicht u uhelos, dass die Menge 8 von ¨berraschend. Aber man erkennt m¨ der Liste gestrichen werden muss, da diese Menge keine Symmetrien eines Frieses der Periode L erzeugt. Um das einzusehen, muss man unbedingt daran denken, dass die Gleitspiegelung sg die Zusammensetzung von rh und tL/2 ist. Man erkennt aber, dass die Menge der Erzeugenden eines Frieses der Periode L nicht sowohl sg als auch rh enthalten kann. Warum? Wir haben festgestellt, dass die Inverse von rh mit rh zusammenf¨ allt. Dann aber ist die Zusammensetzung von rh und sg gleich sg rh = tL/2 rh rh = tL/2 (Id) = tL/2 . Da die Zusammensetzungen von Symmetrien ebenfalls Symmetrien sind, sollte auch die Translation tL/2 eine Symmetrie des Frieses sein. Wir haben jedoch vorausgesetzt, dass die Periode des Frieses gleich L ist, und definitionsgem¨ aß geh¨ ort diese Periode zur kleinsten Translation, die den Fries invariant l¨asst. Die Translation tL/2 kann nicht auftreten und deswegen k¨onnen sg und rh nicht gleichzeitig die Erzeugenden ein und desselben Frieses sein. Die Menge 8 muss also gestrichen werden. (Man beachte, dass diese Menge eine Menge von Symmetrien eines Frieses erzeugt. Aber dieser Fries hat die Periode L2 und ¨ Im Klassifikationssatz bleiben ist demnach die Menge 3, das heißt, tL/2 , rh .) (Ubung: nur sieben der obigen zehn Mengen u ur angegeben, ¨brig. Wir haben die Argumente daf¨ dass 8 gestrichen werden muss. K¨ onnen Sie eine Vermutung aussprechen, welche beiden anderen Mengen weggelassen werden m¨ ussen?) Wir werden den Beweis des Klassifikationssatzes vervollst¨ andigen, nachdem wir ein leistungsstarkes algebraisches Werkzeug zur Untersuchung dieser geometrischen Operationen diskutiert haben: die Matrizendarstellung affiner Transformationen.2
2.2 Symmetriegruppen und affine Transformationen Wir verwenden affine Transformationen als mathematische Grundlage zur Beschreibung invarianter Operationen auf Friesen. (Wenn Sie Kapitel 3 oder 11 gelesen haben, sind Sie diesen Transformationen bereits begegnet.) Definition 2.2 Eine affine Transformation in der Ebene ist eine Transformation R2 → R2 der Form (x, y) → (x , y ), wobei x = ax + by + p, y = cx + dy + q. Eine affine Transformation heißt eigentlich, wenn sie bijektiv ist. Eine solche Transformation l¨asst sich in Matrizenform folgendermaßen beschreiben: 2 Es ist m¨ oglich, einen rein geometrischen Beweis dieses Satzes zu geben. Vgl. zum Beispiel [2] und [5].
56
2 Friese und Mosaike
x a = y c
b d
x p + . y q
(2.1)
Die Matrix ac db repr¨ asentiert eine lineare Transformation, w¨ ahrend p und q eine Translation in der Ebene darstellen. Im verbleibenden Teil dieses Kapitels betrachten wir nur eigentliche (oder regul¨ are) affine Transformationen, das heißt, umkehrbar eindeutige affine Transformationen. Wir werden bald sehen, dass diese zus¨ atzliche Bedingung ¨aquivalent zur Invertierbarkeit der linearen Transformationsmatrix ac db ist. Beachten Sie, dass die folgende Gleichung dieselbe affine Transformation beschreibt: ⎛ ⎞ ⎛ ⎞⎛ ⎞ x a b p x ⎝y ⎠ = ⎝ c d q ⎠ ⎝y ⎠ . (2.2) 1 0 0 1 1 In dieser modifizierten Form erfolgt eine umkehrbar eindeutige Zuordnung zwischen den Elementen (x, y) der Ebene R2 und den Elementen (x, y, 1)t der Ebene z = 1 von R3 . Die Abbildung zwischen den affinen Transformationen der Form (2.1) und den 3 × 3Matrizen ⎛ ⎞ a b p ⎝c d q⎠ , 0 0 1 deren letzte Zeile (0 0 1) ist, ist ebenfalls umkehrbar eindeutig. Setzen wir zwei affine Transformationen (x, y) → (x , y ) und (x , y ) → (x , y ) zusammen, die durch x = a1 x + b1 y + p1 , y = c 1 x + d1 y + q 1 , und x = a2 x + b2 y + p2 , y = c2 x + d2 y + q2 gegeben sind, dann k¨ onnen wir (x , y ) in folgender Form schreiben: x = a2 x + b2 y + p2 = a2 (a1 x + b1 y + p1 ) + b2 (c1 x + d1 y + q1 ) + p2 = (a2 a1 + b2 c1 )x + (a2 b1 + b2 d1 )y + (a2 p1 + b2 q1 + p2 ) und y = c2 x + d2 y + q2 = c2 (a1 x + b1 y + p1 ) + d2 (c1 x + d1 y + q1 ) + q2 = (c2 a1 + d2 c1 )x + (c2 b1 + d2 d1 )y + (c2 p1 + d2 q1 + q2 ).
2.2 Symmetriegruppen und affine Transformationen
57
Man beachte, dass sich diese zusammengesetzte Transformation durch eine 3 × 3-Matrix beschreiben l¨asst: ⎛ ⎞ ⎛ ⎞⎛ ⎞ x a 2 a 1 + b 2 c 1 a 2 b 1 + b 2 d 1 a 2 p1 + b 2 q 1 + p 2 x ⎝ y ⎠ = ⎝ c 2 a 1 + d 2 c 1 c 2 b 1 + d 2 d 1 c 2 p1 + d 2 q 1 + q 2 ⎠ ⎝ y ⎠ . 1 0 0 1 1 Das letztgenannte Beispiel demonstriert die N¨ utzlichkeit der Schreibweise in Form einer 3 × 3-Matrix, denn zusammengesetzte Transformationen lassen sich als Produkt der Matrizen der entsprechenden individuellen Transformationen ausdr¨ ucken: ⎛
a2 ⎝ c2 0
b2 d2 0
⎞⎛ a1 p2 q2 ⎠ ⎝ c 1 1 0
b1 d1 0
⎞ ⎛ a 2 a 1 + b2 c 1 p1 q1 ⎠ = ⎝ c 2 a1 + d2 c 1 1 0
a 2 b1 + b 2 d 1 c 2 b1 + d 2 d 1 0
⎞ a 2 p 1 + b2 q 1 + p2 c 2 p1 + d 2 q 1 + q 2 ⎠ . 1
Diese Eigenschaft erm¨ oglicht es uns, affine Transformationen und ihre Zusammensetzungen zu untersuchen, indem wir diese 3 × 3-Darstellung und die gew¨ ohnliche Matrizenmultiplikation verwenden. Das geometrische Problem wird dadurch auf ein Problem der linearen Algebra zur¨ uckgef¨ uhrt. Wegen dieser Zuordnung verwenden wir h¨ aufig die Matrizendarstellung zur Beschreibung einer affinen Transformation. Wir betonen, dass eine affine Transformation ohne Verwendung eines Koordinatensystems definiert werden kann, aber die genannte Matrizendarstellung existiert nur, wenn man ein Koordinatensystem gew¨ahlt hat. Um die St¨arke dieser Notation zu zeigen, berechnen wir jetzt die Inverse einer eigentlichen affinen Transformation. Die Inverse ist diejenige Zuordnung (x , y ) → (x, y), bei der x = ax + by + p und y = cx + dy + q. Da die Zusammensetzung von affinen Transformationen durch die Matrizenmultiplikation dargestellt wird, muss diejenige Matrix, welche die Inverse beschreibt, gleich der Inversen derjenigen Matrix sein, welche die urspr¨ ungliche Transformation beschreibt. Man rechnet m¨ uhelos aus, dass diese inverse Matrix durch ⎛ ⎞ d/D −b/D (−dp + bq)/D ⎝−c/D a/D (cp − aq)/D ⎠ 0 0 1 a b gegeben ist, wobei D = det c d = ad − bc. Das ist ebenfalls eine Matrix, die ei¨ ne eigentliche affine Transformation beschreibt. (Ubung: Was m¨ ussen Sie tun, um zu gew¨ahrleisten, dass diese Matrix tats¨ achlich eine eigentliche Transformation beschreibt? ¨ Tun Sie das. Diese Ubung best¨ atigt die Behauptung, dass eine affine Transformation dann und nur dann eigentlich ist, wenn die Matrix ac db invertierbar ist.) Schreiben wir die Matrix, welche die urspr¨ ungliche Transformation beschreibt, in der Form A t B= , 0 1
58
2 Friese und Mosaike
wobei A=
a c
b , d
0= 0
0
und
t=
p , q
dann l¨asst sich ihre Inverse als B −1 =
A 0
−1 −1 t A = 0 1
−A−1 t 1
schreiben. Man beachte, dass B −1 die gleiche Form wie B hat: die dritte Zeile ist (0 0 1). Außerdem beachte man, dass die lineare Transformation A−1 ebenfalls invertierbar ist. Die Menge aller eigentlichen affinen Transformationen bildet eine Gruppe. Definition 2.3 Eine Menge E mit einer Multiplikationsoperation E × E → E ist eine Gruppe, wenn sie folgende Eigenschaften hat: 1. Assoziativit¨at: (ab)c = a(bc), ∀a, b, c ∈ E; 2. Existenz eines neutralen Elements3 : es existiert ein Element e ∈ E so, dass ea = ae = a, ∀a ∈ E; 3. Existenz von Inversen: ∀a ∈ E, ∃b ∈ E so, dass ab = ba = e. Das Inverse eines Elements a wird u ¨blicherweise mit a−1 bezeichnet. Gruppen spielen eine wichtige Rolle in mehreren anderen Kapiteln. Vgl. zum Beispiel Abschnitt 1.4 und Abschnitt 7.4. Man kann leicht u ufen, dass die Menge derjenigen Matrizen, die eigentliche af¨berpr¨ fine Transformationen darstellen, eine Gruppe bilden. Demnach bildet auch die Menge der eigentlichen affinen Transformationen eine Gruppe. Wir sehen uns diesen Sachverhalt jetzt genauer an. Proposition 2.4 Die Menge derjenigen Matrizen, die eigentliche affine Transformationen darstellen, bildet in Bezug auf die Matrizenmultiplikation eine Gruppe. Die Menge der eigentlichen affinen Transformationen bildet in Bezug auf die Zusammensetzung ebenfalls eine Gruppe, die man als affine Gruppe bezeichnet. Beweis. Man betrachte die Matrix B=
A 0
t , 1
die eine eigentliche affine Transformation darstellt. Da die affine Transformation eigentlich ist, ist A eine invertierbare 2 × 2-Matrix und deswegen ist auch die Matrix B invertierbar. Die Matrix B −1 hat die gleiche Form wie B und stellt deswegen ebenfalls eine eigentliche affine Transformation dar, das heißt, Bedingung 3 ist erf¨ ullt. Bedingung 1 ist erf¨ ullt, da die Matrizenmultiplikation assoziativ ist, und Bedingung 2 wird durch die 3 × 3-Einheitsmatrix erf¨ ullt, welche die affine Transformation 3
Auch als Einselement oder als Identit¨ at bezeichnet.
2.2 Symmetriegruppen und affine Transformationen
⎛
⎞ 1 0 0 ⎝0 1 0⎠ 0 0 1
←→
59
x = x, y = y.
darstellt.4 Deswegen bildet die Menge derjenigen Matrizen, die eigentliche affine Transformationen darstellen, eine Gruppe. Wir haben gesehen, dass es eine umkehrbar eindeutige Zuordnung zwischen Matrizen (mit der letzten Zeile (0 0 1)) und affinen Transformationen gibt. Außerdem entspricht bei dieser Zuordnung die Zusammensetzung affiner Transformationen der Matrizenmultiplikation. Der obige Beweis gilt also automatisch auch f¨ ur die eigentlichen affinen Transformationen.
Abb. 2.4. Das Koordinatensystem.
Fr¨ uher hatten wir Spiegelungen an horizontalen und vertikalen Spiegeln eingef¨ uhrt. Als Beispiele geben wir jetzt die Matrizendarstellungen dieser Spiegelungen an. Um diese Darstellungen zu bekommen, m¨ ussen wir den Koordinatenursprung festlegen. Wir legen diesen so, dass er den gleichen Abstand von der oberen Linie und von der unteren Linie des Frieses hat. (Vgl. Abbildung 2.4.) Das l¨ asst uns noch etwas Freiheit, da jeder Punkt auf der horizontalen Achse in der Mitte des Frieses gew¨ ahlt werden kann. (Wir haben diese Freiheit bereits hervorgehoben, als wir die Position der vertikalen Spiegel diskutierten. Wir werden diese Freiheit auch im Beweis von Lemma 2.10 nutzen.) F¨ ur eine gegebene Auswahl l¨angs der horizontalen Achse wird die Spiegelung rh , die oben und unten vertauscht (die also die positive vertikale Achse mit der negativen vertauscht), durch die Matrix ⎛ ⎞ 0 1 0 r h ⎝ 0⎠ mit rh = 0 −1 0 0 1 dargestellt, und die Spiegelung rv , die links und rechts vertauscht, ist
4
Die Einheitsmatrix wird auch als Identit¨ atsmatrix bezeichnet.
60
2 Friese und Mosaike
⎛ ⎝ rv 0 0
⎞ 0 −1 0⎠ mit rv = 0 1
0 , 1
¨ falls der Ursprung auf dem Spiegel liegt. (Ubung: Beweisen Sie diese Behauptungen.) Beachten Sie, dass 1 0 −1 0 −1 0 rh rv = = . 0 −1 0 1 0 −1 Wir bemerken noch einmal, dass man die Drehung um einen Winkel von 180◦ (oder π) durch Spiegelung an einem vertikalen Spiegel und anschließende Spiegelung an einem ¨ horizontalen Spiegel gewinnen kann. (Ubung: Bestimmen Sie die 3 × 3-Matrizen, welche die Translation tL und die Gleitspiegelung sg darstellen.) Die Definition der affinen Transformation macht diese zu einer Funktion von R2 in 2 R . Die Voraussetzung, dass diese Funktionen einen Fries invariant lassen, schr¨ ankt die Menge der affinen Transformationen ein, die wir betrachten m¨ ussen. Wir machen aber auch eine zweite, noch gravierendere Einschr¨ankung der affinen Transformationen. Definition 2.5 Eine Isometrie der Ebene (oder eines Bereiches der Ebene) ist eine l¨angentreue Funktion T : R2 → R2 (oder T : F ⊂ R2 → R2 ). Sind also (x1 , y1 ) und (x2 , y2 ) zwei Punkte, dann ist ihr Abstand gleich dem Abstand ihrer Bilder T (x1 , y1 ) und T (x2 , y2 ). Definition 2.6 Eine Symmetrie eines Frieses ist eine Isometrie, die den Fries auf sich selbst abbildet. ¨ Ubung 9 zeigt, dass eine Isometrie eine affine Transformation ist. Lemma 2.7 lehrt, dass diese Beschr¨ankung auf isometrische affine Transformationen die m¨ oglichen linearen Transformationen A, die eine Rolle spielen k¨ onnen, wesentlich einschr¨ ankt. Lemma 2.7 Die Isometrie, die durch die Matrix A 0 0 1 dargestellt wird, sei eine Symmetrie eines Frieses. Dann ist der 2 × 2-Block eine der vier Matrizen 1 0 1 0 −1 0 −1 0 , rh = , rv = oder rh rv = . (2.3) 0 1 0 −1 0 1 0 −1 Beweis. Eine lineare Transformation ist vollst¨andig durch die Werte einer Basis bestimmt. Wir verwenden die Basis {u, v}, wobei u und v ein horizontaler bzw. ein vertikaler Vektor ist, dessen L¨ange jeweils die H¨alfte der Breite des Frieses ist. Unter diesen Voraussetzungen hat ein beliebiger Punkt des Frieses die Form (x, y) = αu + βv mit
2.2 Symmetriegruppen und affine Transformationen
61
α ∈ R und β ∈ [−1, 1]. (Die Einschr¨ ankung β ∈ [−1, 1] gew¨ ahrleistet, dass der Punkt (x, y) innerhalb des Frieses liegt.) Die beiden Basisvektoren stehen senkrecht aufeinander (u ⊥ v), das heißt, ihr inneres Produkt5 verschwindet: (u, v) = 0. 0 Um zu pr¨ ufen, ob ( A 0 1 ) eine Isometrie darstellt, reicht der Nachweis aus, dass |Au| = |u|,
|Av| = |v|
und
Au ⊥ Av.
(2.4)
Sind n¨amlich P und Q zwei Punkte auf dem Fries und ist Q − P = αu + βv der Vektor zwischen ihnen, dann ist das Bild von Q − P gleich A(αu + βv) und das Quadrat der L¨ange dieses Vektors ist durch |A(αu + βv)|2 = (αAu + βAv, αAu + βAv) = α2 |Au|2 + 2αβ(Au, Av) + β 2 |Av|2 = α2 |u|2 + β 2 |v|2 = (αu + βv, αu + βv) = |αu + βv|2 gegeben. Hierbei haben wir, um die dritte Gleichung zu bekommen, die drei Relationen von (2.4) verwendet, w¨ ahrend wir f¨ ur die vierte Gleichung die Tatsache benutzt haben, dass die Basisvektoren zueinander senkrecht sind. Also bleibt der Abstand zwischen beliebigen Punkten P und Q bei der Transformation A erhalten, falls die Relationen ¨ (2.4) erf¨ ullt sind. (Ubung: Zeigen Sie, dass diese Relationen auch notwendig sind.) Es sei Au = γu + δv das Bild von u unter A. Da die Transformation linear ist, haben wir A(βu) = β(γu + δv). Ist δ von null verschieden, dann ist es m¨ oglich, β ∈ R so zu w¨ahlen, dass |βδ| > 1. Das bedeutet, dass sich der Punkt A(βu) außerhalb des Frieses befindet. Dieser Fall muss jedoch ausgeschlossen werden, das heißt, wir m¨ ussen δ gleich null setzen. (Mit anderen Worten: Eine Transformation A mit der Eigenschaft, dass δ von null verschieden ist, ist eine lineare Transformation, die den Fries aus der Horizontalen kippt.) Demnach gilt Au = γu, und falls |Au| = |u| erf¨ ullt sein soll, dann muss γ = ±1 gelten. Es sei jetzt Av = ρu + σv das Bild von v unter A. Da Au senkrecht auf Av stehen muss, folgt 0 = (Au, Av) = (γu, ρu + σv) = γρ|u|2 . Da weder γ noch |u| gleich null ist, muss ρ gleich 0 gesetzt werden. Wieder f¨ uhrt die letzte Bedingung |Av| = |v| dazu, dass σ gleich ±1 sein muss. Die Matrix A, welche die Transformation in der Basis {u, v} darstellt, hat demnach die Form γ0 σ0 . Es gibt jeweils zwei Wahlm¨oglichkeiten f¨ ur γ und σ und damit vier M¨ oglichkeiten f¨ ur die Matrix A, n¨amlich genau diejenigen, die in der Formulierung des Lemmas auftreten. Die Zusammensetzung zweier Isometrien und die Inverse einer Isometrie sind selbst wieder Isometrien. Demnach bildet die Untermenge der isometrischen Transformationen der affinen Gruppe selbst eine Gruppe, die als Gruppe der Isometrien bezeichnet 5
Das innere Produkt wird auch Skalarprodukt genannt.
62
2 Friese und Mosaike
wird. Und schließlich bildet die Zusammensetzung zweier Isometrien, die einen Fries unver¨andert lassen, wieder eine Isometrie, die diesen Fries unver¨ andert l¨ asst. In der Gruppe der Isometrien bildet demnach die Untermenge, die einen Fries invariant lassen, f¨ ur sich eine Gruppe. Das f¨ uhrt uns zu der folgenden Definition. Definition 2.8 Die Symmetriegruppe eines Frieses ist die Gruppe aller Isometrien, die den Fries invariant lassen.
2.3 Der Klassifikationssatz Die formale Theorie der Isometrien und affinen Transformationen erm¨ oglicht es uns, eine Liste derjenigen Transformationen zu erstellen, die einen Fries unver¨ andert lassen k¨onnten. In diesem Abschnitt stellen wir zuerst eine vollst¨ andige Liste von m¨ oglichen Symmetrie-Erzeugenden auf. Im zweiten Teil des Abschnitts verwenden wir diese Liste von Transformationen, um alle m¨oglichen Typen von Gruppen von Friessymmetrien aufzuz¨ahlen und zu klassifizieren. Es gibt viele affine Transformationen, die nicht in der Symmetriegruppe eines Frieses auftreten k¨onnen. Lemma 2.7 hat bereits diejenigen linearen Transformationen ausgesondert, die den Fries aus seinem Bereich herauskippen (die Einschr¨ ankung δ = 0 schließt diese Transformationen aus). Die folgenden Lemmas charakterisieren diejenigen Transformationen, die in den Symmetriegruppen von Friesen auftreten k¨ onnen. Das erste Lemma beschreibt Translationen l¨angs der unendlichen Achse des Frieses. Lemma 2.9 Die Symmetriegruppe Translationen ⎛ 1 ⎝0 0
eines beliebigen Frieses der Periode L enth¨alt die ⎞ 0 nL 1 0 ⎠ , n ∈ Z. 0 1
Das sind die einzigen Translationen, die in der Symmetriegruppe auftreten. Beweis. Die Translation
⎛
⎞ 1 0 L tL = ⎝0 1 0 ⎠ 0 0 1
l¨asst einen beliebigen Fries der Periode L unver¨ andert. Man beachte, dass die Inverse dieser Translation durch ⎛ ⎞ 1 0 −L t−L = ⎝0 1 0 ⎠ 0 0 1 gegeben ist und dass die n-fache Zusammensetzung
2.3 Der Klassifikationssatz
⎛
1 tnL = ⎝0 0
63
⎞
0 nL 1 0⎠ 0 1
¨ ergibt. (Ubung!) Die Translation tnL muss demnach f¨ ur alle n ∈ Z in der Symmetriegruppe liegen. Keine Translation der Form ⎛ ⎞ 1 0 a ⎝0 1 b ⎠ 0 0 1 mit b = 0 kann einen Fries unver¨andert lassen, da der vertikale Anteil der Translation gewisse Punkte des Frieses auf Punkte abbildet, die außerhalb der urspr¨ unglichen vertikalen Ausdehnung des Frieses liegen. Es bleiben m¨ ogliche Translationen der Form ⎛ ⎞ 1 0 a ⎝0 1 0⎠ 0 0 1 u uhrung einer sol- ¨brig, wobei a kein ganzzahliges Vielfaches von L ist. Nach Durchf¨ −L L chen Translation um ( a0 ) kann man wiederholt eine Translation 0 um ( 0 ) oder um alt, wobei a die Undurchf¨ uhren, bis man als Ergebnis eine Translation um a0 erh¨ gleichungen 0 ≤ a < L erf¨ ullt. Falls 0 < a < L, dann haben wir eine Translation um eine Konstante a , die kleiner als die Periode L ist, was der Definition der Periode ungliche a ein ganzzahliges Vielfaches widerspricht. Und im Falle a = 0 war das urspr¨ der Periode L. Es bleiben also nur die Translationen tnL , n ∈ Z, u ¨brig. Gibt es irgendwelche anderen Transformationen der Form A t , 0 1 wobei A nicht die Einheitsmatrix ist und t von null verschieden ist? Das folgende Lemma beantwortet diese Frage. t Lemma 2.10 Man betrachte Isometrien der Form ( A 0 1 ), wobei t von ist. Durch Neudefinition des Koordinatenursprungs ist es m¨ oglich, jede mation auf eine Transformation zu reduzieren, die eine der Formen ⎛ ⎞ ⎛ ⎞ ⎛ nL 1 0 L/2 + nL −1 A ⎠ oder (iii) ⎝ 0 0 ⎠ , (ii) ⎝0 −1 0 (i) ⎝ 0 0 1 0 0 1 0
null verschieden solche Transfor0 1 0
⎞ L/2 + nL ⎠ 0 1
hat, wobei n ∈ Z und A eine der vier Formen ist, die gem¨ aß Lemma 2.7 zul¨ assig sind. Form (iii) kann nur dann auftreten, wenn auch die Drehung rh rv eine Symmetrie ist.
64
2 Friese und Mosaike
Beweis. Gem¨aß Definition bleiben bei einer Isometrie die L¨ angen erhalten. Da der Abstand zweier Punkte bei einer beliebigen Translation der beiden Punkte erhalten bleibt, muss die Matrix A eine der vier Formen haben, die in (2.3) gegeben sind. Ist dar¨ uber hinaus ty = 0 in ⎛ ⎞ a b tx ⎝ c d ty ⎠ , 0 0 1 ur gewisse Werte von x und y außerhalb des Frieses. In dann liegt y = cx + dy + ty f¨ der Tat f¨allt f¨ ur die vier m¨ oglichen Matrizen A das Bild des Quadrates [−1, 1] × [−1, 1] mit dem Quadrat selbst zusammen. Jede Translation, bei der ty = 0 ist, bewegt das Quadrat vertikal und u uhrt gewisse Punkte dieses Quadrats in Punkte, die außerhalb ¨berf¨ des Frieses liegen. Demnach muss ty gleich null sein. Da die Symmetriegruppe eines Frieses alle horizontalen Translationen um ganzzahlige Vielfache von L enth¨alt, impliziert das Vorhandensein von ⎞ ⎛ a 0 tx ⎝0 d 0 ⎠ 0 0 1 in der Gruppe auch das ⎛ 1 ⎝0 0
Vorhandensein von ⎞ ⎛ ⎞⎛ a 0 nL a 0 tx 1 0 ⎠ ⎝0 d 0 ⎠ = ⎝0 0 0 1 0 0 1
0 d 0
⎞ tx + nL 0 ⎠ 1
f¨ ur alle n ∈ Z. In der Menge aller solcher Transformationen gibt es eine, f¨ ur die 0 ≤ tx = tx + nL < L. Wir betrachten jetzt die vier M¨ oglichkeiten f¨ ur A. Ist A die Einheitsmatrix, dann muss gem¨aß Lemma 2.9 der Wert tx gleich null sein und die resultierende Matrix hat die Form (i). Es sei A = rh . Dann muss das Quadrat von ⎞ ⎛ tx r ⎝ h 0⎠ 0 0 1 ebenfalls in der Symmetriegruppe des Frieses liegen. Jedoch ist ⎞2 ⎛ ⎞ ⎛ 1 0 2tx 1 0 tx ⎝0 −1 0 ⎠ = ⎝0 1 0 ⎠ 0 0 1 0 0 1 eine Translation. Demnach existiert m ∈ Z derart, dass 2tx = mL. Aus 0 ≤ tx < L folgt 0 ≤ 2tx < 2L. Ist tx = 0, dann ist die Translation trivial. Andernfalls gilt notwendigerweise tx = L/2 und die affine Transformation wird zu
2.3 Der Klassifikationssatz
⎛
1 ⎝0 0
65
⎞
0 L/2 −1 0 ⎠. (2.5) 0 1 −1 0 0 Wir m¨ ussen noch die zwei F¨alle A = −1 0 −1 und 0 1 betrachten. Wir nutzen unsere Freiheit bei der Wahl des Ursprungs. (Vgl. Bemerkungen nach dem Beweis von Proposition 2.9.) Wir verschieben den Ursprung l¨angs der x-Achse um einen Abstand a. Die Matrix, die den Koordinatenwechsel beschreibt, ist durch ⎛ ⎞ 1 0 −a S = ⎝0 1 0 ⎠ 0 0 1 gegeben. Ist T die Matrix, die eine affine Transformation darstellt, und S die Matrix, die das Koordinatensystem (x, y) in ein neues Koordinatensystem (x , y ) u uhrt, dann ¨berf¨ wird die gleiche affine Transformation im neuen System durch die Matrix ST S −1 dargestellt. Um das einzusehen, lesen wir das Matrizenprodukt wie u ¨blich von rechts nach links. Dieser Ausdruck transformiert zuerst die Koordinaten (x , y ) eines Punktes mit Hilfe von S −1 in die entsprechenden Koordinaten (x, y) im alten System; danach wird die affine Transformation angewendet, die in den alten Koordinaten durch die Matrix T gegeben ist, und schließlich erfolgt unter Anwendung von S eine R¨ ucktransformation des Ergebnisses in das neue Koordinatensystem. Die affine Transformation, die durch ⎛ ⎞ −1 0 tx ⎝ 0 ±1 0 ⎠ (2.6) 0 0 1 gegeben ist, wird demnach im neuen System durch ⎛ ⎞⎛ ⎞⎛ ⎞ 1 0 −a −1 0 tx 1 0 a ⎝0 1 0 ⎠ ⎝ 0 ±1 0 ⎠ ⎝0 1 0⎠ 0 0 1 0 0 1 0 0 1 ⎛ ⎞⎛ −1 0 tx − a 1 0 0 ⎠ ⎝0 1 = ⎝ 0 ±1 0 0 1 0 0
die Matrix
⎞ ⎛ a −1 0 0⎠ = ⎝ 0 ±1 1 0 0
⎞ tx − 2a 0 ⎠ 1
¨ dargestellt. (Ubung: Es ist wesentlich, sich davon zu u ¨berzeugen, dass dieser Koordinatenwechsel nicht die Form der anderen Symmetrieoperationen zerst¨ ort. Zeigen Sie, dass t ) gegebenen Transformationen, wobei A gleich ( 1 0 ) oder r ist, nach die durch ( A h 01 0 1 einer horizontalen Translation des Ursprungs die gleiche Matrizendarstellung haben.) Somit wird die durch (2.6) gegebene affine Transformation durch ⎛ ⎞ −1 0 0 ⎝ 0 ±1 0⎠ (2.7) 0 0 1
66
2 Friese und Mosaike
dargestellt, falls wir den Ursprung um genau a = tx /2 verschieben. Man beachte: Enth¨ alt die Symmetriegruppe zwei Transformationen der Form (2.6) mit unterschiedlichen tx1 , tx2 ∈ [0, L), dann garantiert uns eine Bewegung des Urasst. Die sprungs, dass sich die Transformation mit tx1 in der Form (2.7) schreiben l¨ zweite bleibt von der Form (2.6), wobei tx2 durch tx2 = tx2 − tx1 ersetzt wird. Haben beide Transformationen das gleiche A, dann ist ihre Zusammensetzung eine Translation um tx2 , weswegen tx2 die Form nL mit einer ganzen Zahl n haben muss. In diesem Fall nehmen beide Transformationen die Form (i) an, wenn man den Ursprung ¨ andert. Haben jedoch beide Transformationen verschiedene Matrizen A, dann k¨ o nnen wir vor 0 aussetzen, dass bei der ersten A = −1 0 −1 ist und es sich folglich um eine Drehung rh rv um 180◦ handelt. Die Zusammensetzung der beiden Transformationen ist dann ⎛ ⎞ 1 0 tx2 ⎝0 −1 0 ⎠ , 0 0 1 ¨ ur und gem¨aß fr¨ uher angef¨ uhrter Uberlegungen muss tx2 entweder nL oder nL + L2 f¨ eine ganze Zahl n ein. Die zweite Transformation hat dann die Form (i), falls tx2 ein ganzzahliges Vielfaches von L ist, oder andernfalls die Form (iii). Die ersten beiden Formen der durch Lemma 2.10 zugelassenen Isometrien sind dann (i) die Zusammensetzung einer der linearen Transformationen von Lemma 2.7 und einer Translation tnL um ein ganzzahliges Vielfaches der Periode L sowie (ii) die Zusammensetzung einer Gleitspiegelung sg und einer Translation tnL . Die dritte Form (iii) kann nur dann auftreten, wenn auch rh rv vorkommt, und in diesem Fall kann man rh rv und die Isometrie der Form (ii) (mit n = 0) als Erzeugende verwenden. Demnach zeigen die drei Lemmas zusammen, dass die Symmetriegruppe eines Frieses durch eine Untermenge von {tL , rh , rv , rh rv , sg } erzeugt werden kann. Das beantwortet die Frage nach der Liste der m¨oglichen Erzeugenden (diese Frage war am Schluss von Abschnitt 2.1 offen geblieben). Die Lemmas werden es uns nun erm¨ oglichen, unseren Klassifikationssatz der Symmetriegruppen von Friesen abzuschließen und damit eine positive Antwort auf unsere fr¨ uhere Frage zu geben: Ist es m¨ oglich, Friese auf der Grundlage einer Menge von geometrischen Operationen zu klassifizieren, unter denen sie invariant sind? Bei der Beschreibung der verschiedenen m¨oglichen Symmetriegruppen werden wir einfach die erzeugenden Elemente einer jeden Gruppe angeben. Wir rufen uns im Folgenden die Definition einer solchen Liste von Erzeugenden ins Ged¨ achtnis. Definition 2.11 Es sei {a, b, . . . , c} eine Untermenge einer Gruppe G. Diese Menge ist ein Erzeugendensystem von G und wir schreiben G = a, b, . . . , c, falls die Menge aller Zusammensetzungen einer endlichen Anzahl von Elementen von {a, b, . . . , c} und deren Inversen gleich G ist. Satz 2.12 (Klassifikation der Friesgruppen) Die Symmetriegruppe eines beliebigen Frieses ist eine der folgenden sieben Gruppen:
2.3 Der Klassifikationssatz
1. 2. 3. 4. 5. 6. 7.
67
tL tL , rv tL , rh tL , tL/2 rh tL , rh rv tL , tL/2 rh , rh rv tL , rh , rv
Jede dieser Gruppen wird durch ein Erzeugendensystem beschrieben und sie sind in der gleichen Reihenfolge aufgef¨ uhrt wie jene in den Abbildungen 2.1 und 2.2. Beweis. Es sei tL eine Translation um einen Abstand L l¨ angs der horizontalen Achse. Alle Gruppen enthalten Translationen um ganzzahlige Vielfache von L, die Periode des Frieses, und das Erzeugendensystem muss tL enthalten. Durch geeignete Wahl des Ursprungs sieht man, dass die einzigen anderen erzeugenden Elemente der Symmetriegruppen die mit A = rh , rv oder rh rv bezeichneten linearen Transformationen sind sowie die in Lemma 2.10 beschriebene Gleitspiegelung. Man beachte: Enth¨ alt eine Symmetriegruppe irgendzwei Elemente der Mengen rh , rv und rh rv , dann muss sie automatisch alle drei Elemente enthalten. Die Liste aller m¨ oglichen Kombinationen von erzeugenden Elementen besteht demnach aus den sieben Erzeugenden, die in der Formulierung des Satzes angegeben sind, sowie aus 8. tL , tL/2 rh , rh 9. tL , tL/2 rh , rv 10. tL , tL/2 rh , rh , rv (Vgl. die Diskussion am Ende von Abschnitt 2.1, wo diese Liste erstmalig konstruiert wurde.) Wir wiederholen hier das Argument, das uns dazu zwingt, den Fall 8 auszuschließen. Das Vorhandensein von sg = tL/2 rh und rh impliziert, dass die Gruppe auch deren Produkt (tL/2 rh )rh = tL/2 (rh2 ) = tL/2 enthalten muss, bei dem es sich um eine Translation um L/2 handelt (weil rh2 = Id). Das widerspricht der Tatsache, dass es sich um einen periodischen Fries mit einer minimalen Periode L handelt, und deshalb muss diese Menge ausgeschlossen werden. Im Fall 9 ist zu beachten, dass das Produkt von sg und rv die Form tL/2 rh rv hat, die in Lemma 2.10 diskutiert wurde. Durch eine Translation des Koordinatenursprungs (um a = L4 ) kann dieses Produkt in der Form (2.7) mit A = rh rv geschrieben werden. Eine einfache Rechnung zeigt, dass die Erzeugenden tL und sg bei dieser Translation unge¨andert bleiben, aber rv zu sg = tL/2 rv wird. Somit wird die Untergruppe 9 gleichermaßen auch durch das Erzeugendensystem tL , tL/2 rh , tL/2 rv , rh rv beschrieben. Drei der erzeugenden Elemente geh¨ oren zu 6, w¨ahrend das vierte, (tL/2 rv ), einfach das Produkt von tL/2 rh und rh rv ist. Fall 9 ist also tats¨ achlich identisch mit Fall 6 und kann deswegen weggelassen werden. Und schließlich enth¨ alt Fall 10 die erzeugenden Elemente von Fall 8 und kann deswegen aus dem gleichen Grund eliminiert werden.
68
2 Friese und Mosaike
Demnach muss die Symmetriegruppe eines beliebigen Frieses eine der sieben oben aufgelisteten Gruppen sein. Gibt es in dieser Liste irgendwelche Redundanzen? Nein! Mit Hilfe von Abbildung 2.2 k¨ onnen wir uns leicht von dieser Tatsache u ¨berzeugen. Die vollst¨andige Beweisf¨ uhrung ist ziemlich weitschweifig, weswegen wir uns auf Fries 4 beschr¨anken, dessen Symmetriegruppe durch das Erzeugendensystem tL , sg bestimmt war. Wir stellen zun¨ achst fest, dass die zwei Erzeugenden tL und sg Symmetrien dieses Frieses sind. Die von ihnen erzeugte Gruppe muss deswegen eine Untergruppe der tats¨achlichen Symmetriegruppe des Frieses sein. K¨ onnen wir zu den obigen zwei Erzeugenden weitere Erzeugende hinzuf¨ ugen? Man u ¨berzeugt sich schnell davon, dass man (von den verbleibenden M¨ oglichkeiten rh , rv , rh rv ) keine weiteren hinzunehmen kann. Deswegen ist tL , sg in der Tat die vollst¨andige Symmetriegruppe von Fries 4. Und schließlich stellen wir fest: Gruppe 1 ist verschieden von 4 und jede der verbleibenden Gruppen enth¨alt wenigstens eines der Elemente rh , rv und rh rv , die nicht in Gruppe 4 enthalten sind; daher ist Gruppe 4 tats¨ achlich verschieden von den anderen sechs Grup¨ pen. Ahnliche Argumente f¨ ur die verbleibenden Friese und Symmetriegruppen zeigen, dass die obige Liste alle M¨oglichkeiten aussch¨ opft und nicht redundant ist.
2.4 Mosaike In der Architektur sind Mosaike genauso beliebt wie Friese, wenn nicht noch beliebter. F¨ ur uns ist ein Mosaik ein Muster, das zum Auff¨ ullen der Ebene wiederholt werden kann und periodisch in zwei linear unabh¨ angigen Richtungen ist. Ein Mosaik hat also zwei linear unabh¨angige Vektoren t1 und t2 , l¨angs denen es verschoben werden kann, ohne dass sich etwas ¨ andert. Wie bei Friesen kann man auch Mosaike in Bezug auf die Symmetrieoperationen untersuchen, unter denen sie invariant bleiben. Und wie Friese k¨ onnen auch Mosaike durch ihre Symmetriegruppen klassifiziert werden. Aufgrund ihrer Wichtigkeit in der Kristallphysik und in der Kristallchemie bezeichnet man diese Gruppen als kristallografische Gruppen. Es gibt 17 kristallografische Gruppen. Wir werden diese Klassifizierung nicht ableiten. Wir beschr¨anken uns darauf, die Drehungen aufzuz¨ ahlen, die in den Symmetriegruppen von Mosaiken auftreten k¨onnen, sowie darauf, das Wesen der Klassifizierung zu erfassen. Lemma 2.13 Eine beliebige Drehung, die ein Mosaik invariant l¨ asst, muss einen der π π folgenden Winkel haben: π, 2π , , . 3 2 3 Beweis. Es sei O das Zentrum einer Drehung, die das Mosaik invariant l¨ asst. Es sei θ = 2π n der kleinste Winkel, der die Drehung um diesen Punkt beschreibt. Das Mosaik ist periodisch in zwei linear unabh¨ angigen Richtungen und deswegen gibt es unendlich viele solche Punkte. Es sei f ein Vektor, der O mit einem Bild A verbindet, das sich unter den n¨achstgelegenen Bildern befindet, die man aus O durch Translationen erh¨ alt. Dann geh¨ort die Translation l¨angs des Vektors f zur Symmetriegruppe des Mosaiks.
2.4 Mosaike
69
Abb. 2.5. Der Punkt O und zwei seiner Bilder A, B bei einer Translation.
Dreht man das Mosaik um O um einen Winkel θ, dann wird der Punkt A auf B abgebildet. Der Vektor f , der O mit B verbindet, beschreibt auch eine Translation, bei der das Mosaik invariant bleibt (vgl. Abbildung 2.5). Der Abstand zwischen A und B ist die L¨ange des Vektors f − f , und da f − f ebenfalls eine Translation ist, die das Mosaik invariant l¨asst, muss dieser Abstand nach Voraussetzung gr¨ oßer oder gleich der L¨ange von f sein. (A war eines der n¨achstgelegenen Bilder von O.) Da f und f die π ◦ oßer oder gleich 2π gleiche L¨ange haben, muss der Winkel θ = 2π n gr¨ 6 = 3 (also 60 ) sein. π ur den f , f und f − f alle die gleiche L¨ ange haben. Tats¨achlich ist 3 exakt der Winkel, f¨ 2π 2π π 2π ¨ = π, , = Diese erste Uberlegung beschr¨ ankt die M¨oglichkeiten auf 2π 2 3 4 2 , 5 und 2π π = . 6 3 Jedoch kann kein Mosaik nach einer Drehung um einen Winkel von 2π 5 invariant bleiben. Abbildung 2.6 zeigt den Vektor f und sein Bild f nach einer Drehung um 4π 5 . Die Translation l¨angs f + f muss ebenfalls eine invariante Operation sein, aber die betreffende L¨ange ist kleiner als die L¨ange von f , womit wir einen Widerspruch erhalten haben. Wir k¨onnen diesen Winkel also auf jeden Fall ausschließen. Die Elemente der kristallografischen Gruppen sind denen ¨ ahnlich, die wir bei den Friessymmetriegruppen gefunden haben: Translationen, Spiegelungen, Spiegelungen mit anschließenden Translationen (das heißt, Gleitspiegelungen wie bei Friesen) und Drehungen. Anstatt eine vollst¨ andige Liste der Erzeugenden s¨ amtlicher 17 kristallografischen Gruppen anzugeben, greifen wir f¨ ur jeden Typ ein Beispiel heraus und heben dessen Symmetrien hervor (vgl. Abbildungen 2.17 bis 2.22, wobei wir auf Seite 82 beginnen). F¨ ur jede Klasse illustrieren wir die Grundform des Mosaiks auf der linken Seite mit jeweils einem schattierten Parallelogramm, dessen Seiten die zwei linear unabh¨ angigen Richtungen anzeigen, in denen das Mosaik verschoben werden kann. Diese Vektoren sind so gew¨ahlt worden, dass das Parallelogramm die kleinstm¨ ogliche Fl¨ ache einschließt, die
70
2 Friese und Mosaike
Abb. 2.6. Drehung um einen Winkel
2π . 5
notwendig ist, um die Ebene durch Translationen l¨angs der betreffenden Vektoren zu u ur dieses Parallelogramm. ¨berdecken. Es gibt normalerweise mehr als eine M¨oglichkeit f¨ Auf der rechten Seite der jeweiligen Abbildung steht das gleiche Mosaik mit den entsprechenden Achsen der Spiegelung oder Gleitspiegelung und den Drehpunkten. Und schließlich findet man in der Legende einer jeden dieser grafischen Darstellungen die internationalen Symbole, die im Allgemeinen f¨ ur die jeweiligen kristallografischen Gruppen verwendet werden [5]. Volle Linien geben an, dass eine einfache Spiegelung an der Achse eine Symmetrie ist. Gestrichelte Linien weisen auf Gleitspiegelungen hin; die erforderlichen Translationen werden nicht explizit gezeigt, sind aber dennoch leicht zu erkennen. Verschiedene Symbole werden verwendet, um Punkte anzugeben, um die das Mosaik gedreht werden kann. F¨allt das Rotationszentrum nicht auf eine Spiegelungsachse, dann verwendet man folgende Symbole: f¨ ur Drehungen um den Winkel π, f¨ ur Drehungen um den Winkel 2π 3 , f¨ ur Drehungen um den Winkel π2 , und Sechsecke f¨ ur Drehungen um den Winkel
π 3.
Liegt der Drehpunkt auf einer Spiegelungsachse, dann verwenden wir vollschwarze Versionen der gleichen Symbole (, usw.). In der alten Stadt Alhambra, dem Sitz der maurischen Regierung von Granada im S¨ uden des heutigen Spaniens, findet man erstaunlich viele Mosaike von u ¨berraschender Komplexit¨at. Lange wurde dar¨ uber diskutiert, ob die Alhambra-Mosaike alle 17 kristallografischen Gruppen repr¨asentieren. Gr¨ unbaum, Gr¨ unbaum und Shephard [4] behaupten, dass das nicht der Fall ist, sondern dass nur 13 Gruppen repr¨ asentiert sind. Sogar angesichts dieser negativen Antwort ist es eine nat¨ urliche Frage, ob sich die damaligen maurischen K¨ unstler eines Klassifizierungssystems bewusst waren.
2.4 Mosaike
71
Abb. 2.7. Penrose-Kacheln.
Abb. 2.8. Eine aperiodische Penrose-Parkettierung.
Die exakte mathematische Formalisierung der Friese und der Mosaike erm¨ oglichte es den Mathematikern, durch das Lockern gewisser Regeln in der Definition neue verallgemeinerte Strukturen zu untersuchen. Aperiodische Parkettierungen sind eine solche Struktur. Alle Mosaike m¨ ussen die Ebene ausf¨ ullen, das heißt, eine Fortsetzung des Musters in alle Richtungen u uckenlos s¨amtliche Punkte des R2 . Diese Bedin¨berdeckt l¨ gung wird auch durch aperiodische Parkettierungen erf¨ ullt. Zum Beispiel ist es m¨ oglich, die Ebene R2 mit den zwei in Abbildung 2.7 [5] zu sehenden Penrose-Kacheln (die als Penrose-Rauten bezeichnet werden) zu u oglich ist, die Ebe¨berdecken. Selbst wenn es m¨ ne mit diesen Kacheln periodisch zu parkettieren, ist es auch m¨ oglich, die Kacheln so anzuordnen, dass keine Translationssymmetrie auftritt; das heißt, sie k¨ onnen dazu ver-
72
2 Friese und Mosaike
wendet werden, die Ebene aperiodisch zu u ¨berdecken. Abbildung 2.8 zeigt einen Teil einer aperiodischen Parkettierung. M¨ oglicherweise finden diese neuen verallgemeinerten Strukturen in der Architektur Verwendung . . . (Penrose und andere haben weitere Mengen von Kacheln konstruiert, mit denen man nur aperiodische Parkettierungen ausf¨ uhren kann!)
¨ 2.5 Ubungen 1.
2.
Man sagt, dass zwei Operationen a, b ∈ E kommutieren, falls ab = ba. (a) Kommutieren die Translationsoperationen miteinander? (b) Kommutieren die Operationen rh , rv und rh rv jeweils miteinander? (c) Kommutieren die Spiegelungen rh , rv und rh rv mit den Translationen? Finden Sie die Bedingungen, unter denen ⎛ a ⎝c 0 und eine Translation
eine lineare Transformation ⎞ b 0 d 0⎠ 0 1
⎛ ⎞ 1 0 p ⎝0 1 q ⎠ 0 0 1
miteinander kommutieren.
¨ Abb. 2.9. Der Fries von Ubung 3.
3.
(a) Bestimmen Sie die Periode L des Frieses von Abbildung 2.9. Geben Sie die Periode direkt auf der Abbildung oder auf einer Kopie derselben an. (b) Unter welcher der Transformationen tL , rh , sg , rv , rh rv ist der Fries invariant? (c) Zu welcher der sieben Symmetriegruppen geh¨ ort der Fries? (d) Zeichnen Sie einen einzigen Punkt pro Periode derart in den Fries ein, dass sich seine Symmetriegruppe auf tL reduziert, ohne dabei die Periodenl¨ ange zu ¨ andern.
4.
(a) Friese werden h¨ aufig in der Architektur verwendet; in [3] findet man mehrere bemerkenswerte Beispiele. W¨ahlen Sie einige dieser Beispiele aus und bestimmen Sie, zu welchen Symmetriegruppen sie geh¨oren.
¨ 2.5 Ubungen
73
(b) Der K¨ unstler M. C. Escher schuf mehrere bemerkenswerte Mosaike; viele dieser Mosaike findet man in [6]. W¨ ahlen Sie einige von Eschers Mosaiken aus und bestimmen Sie, zu welchen der 17 kristallografischen Gruppen sie geh¨ oren. 5.
(a) Identifizieren Sie die Symmetriegruppe des in Abbildung 2.10 dargestellten Frieses.
¨ Abb. 2.10. Fries zu Ubung 5.
(b) Durch Entfernen zweier Dreiecke aus jeder Periode dieses Frieses konstruiere man einen Fries, der zur Symmetriegruppe 5 geh¨ort. 6.
Beweisen Sie die drei Aussagen von Proposition 2.1. Hinweis: Diese Eigenschaften lassen sich beweisen, indem man nur die euklidische Geometrie oder die Matrizendarstellung der affinen Transformationen verwendet. Untersuchen Sie beide Ans¨ atze.
7.
(a) Es seien m1 und m2 parallele Geraden mit dem Abstand d und es seien rm1 und rm2 die Spiegelungen an diesen Geraden. Zeigen Sie, dass die Zusammensetzung angs einer Richtung ist, die senkrecht zu rm2 rm1 eine Translation um den Abstand 2d l¨ den Geraden (Spiegeln) m1 und m2 verl¨ auft. Hinweis: Beweisen Sie diese Aussage unter ausschließlicher Verwendung der euklidischen Geometrie, das heißt, ohne Verwendung eines Koordinatensystems. Sie k¨onnen den Begriff des Abstands oder der L¨ ange einer Strecke verwenden. (b) Ein Fries der Periode L sei invariant gegen¨ uber der Spiegelung rv . Zeigen Sie, dass dieser Fries invariant gegen¨ uber einer Spiegelung an einem vertikalen Spiegel ist, der den Abstand L2 vom erstgenannten Spiegel hat. Hinweis: Untersuchen Sie die Zusammensetzung von rv und der Translation tL .
8.
Es seien m1 und m2 zwei Geraden, die sich im Punkt P schneiden und es seien rm1 und rm2 die Spiegelungen an diesen Geraden. Zeigen Sie, dass die Zusammensetzung rm2 rm1 eine Drehung um den Mittelpunkt P um das Doppelte des Winkels zwischen den beiden Geraden (Spiegeln) m1 und m2 ist. Hinweis: Zeigen Sie zuerst, dass die Bilder rm1 Q und Q = rm2 rm1 Q auf einem Kreis mit dem Mittelpunkt P und dem Radius |P Q| liegen. Untersuchen Sie danach die Winkel, den die Strecken P Q und P Q mit einer gegebenen Geraden, etwa mit m1 , bilden.
9.
¨ Das Ziel dieser Ubung ist der Nachweis, dass eine Isometrie die Zusammensetzung einer linearen Transformation und einer Translation ist, und dass es sich deswegen um eine
74
2 Friese und Mosaike
affine Transformation handelt. (Entweder die lineare Transformation oder die Translation k¨onnte die Identit¨ at sein.) Wir rufen in Erinnerung, dass eine lineare Transformation ugt: der Ebene eine Funktion T : R2 → R2 ist, die den beiden folgenden Bedingungen gen¨ (i) T (u + v) = T (u) + T (v) und (ii) T (cu) = cT (u) f¨ ur alle Punkte u, v ∈ R2 und Konstanten c ∈ R. (a) Zeigen Sie, dass eine Isometrie T : R2 → R2 winkeltreu ist. Hinweis: W¨ ahlen Sie drei (nichtkollineare) Punkte P, Q, R und betrachten Sie deren Bilder P , Q , R unter T ; zeigen Sie, dass die Dreiecke P QR und P Q R kongruent sind. (b) Zeigen Sie, dass eine Translation eine Isometrie ist. (c) Angenommen eine Isometrie S hat keinen Fixpunkt und S(P ) = Q. Zeigen Sie, dass die Zusammensetzung T S, bei der T die Translation ist, die Q auf P abbildet, mindestens einen Fixpunkt hat. (d) Es sei S eine Isometrie, die (mindestens) einen Fixpunkt O hat. Die Punkte P, Q, R seien so gew¨ahlt. dass OP QR ein Parallelogramm ist. Es bezeichnen P , Q , R ihre Bilder unter S. Zeigen Sie, dass die Summe der Vektoren OP und OR gleich OQ ist. (Das ist gleichbedeutend mit dem Nachweis, dass S(OP + OR) = S(OP ) + S(OR).) (e) Es sei S eine Isometrie, die (mindestens) einen Fixpunkt O hat und es seien P und Q zwei Punkte, die voneinander und von O verschieden sind, so dass O, P, Q kollinear sind. Zeigen Sie, dass |OP | S(OQ). S(OP ) = |OQ| (f ) Schlussfolgern Sie, dass eine Isometrie eine lineare Transformation ist, an die sich eine Translation anschließt, das heißt, eine Isometrie ist eine affine Transformation. (Eine der beiden Operationen k¨ onnte die Identit¨at sein.) 10. (a) Das Muster der Abbildung 2.11 besteht aus einer Reihe von Ellipsen, die l¨ angs der x-Achse in den Punkten (2i , 0) mit Hauptachsen rx = 2i−2 , ry = 1 zentriert sind. Somit erstreckt sich dieses Muster u ¨ber den unendlichen Halbstreifen (0, ∞) × [− 12 , 12 ]. Dieses Muster ist kein Fries, weil es nicht periodisch ist. Ersetzen Sie die Periodizit¨ atsbedingung durch eine andere Invarianzbedingung, durch die dieses Muster ein Fries“ wird. ” (b) Beschreiben Sie die Transformation, die eine Ellipse auf die erste links von ihr stehende Ellipse abbildet. Ist diese Transformation linear? Bildet die Menge derartiger Transformationen eine Gruppe?
¨ Abb. 2.11. Ein nichtperiodisches Muster. (F¨ ur Ubung 10.)
11. Es sei r > 1 eine reelle Zahl und
¨ 2.5 Ubungen
Ar =
1 (x, y) ∈ R2 ≤ x2 + y 2 ≤ r r
75
der Ring, dessen Mittelpunkt der Koordinatenursprung der Ebene ist und der von Kreisen mit den Radien r und 1r begrenzt wird. (a) Zeigen Sie, dass die Menge Ar bei Drehungen der Form cos θ − sin θ sin θ cos θ f¨ ur alle θ ∈ [0, 2π) invariant ist. (Die Invarianz von Ar bedeutet, dass die Transformation allt.) invertierbar ist und dass das Bild von Ar mit Ar zusammenf¨ (b) Gegeben sei die Transformation R2 \ {(0, 0)} → R2 \ {(0, 0)}, die durch x , x2 + y 2 y y = 2 x + y2
x =
definiert ist. Diese Transformation wird als Inversion bezeichnet. Zeigen Sie, dass Ar bei dieser Transformation invariant ist. Zeigen Sie, dass A2r die identische Transformation ist. Ist diese Transformation linear? (c) Abbildung 2.12 stellt einen kreisf¨ ormigen Fries dar, der auf einen Ring Ar gezeichnet ist. Die gestrichelte Linie stellt den Kreis mit dem Radius 1 dar. Im Gegensatz zu den fr¨ uher diskutierten Bandfriesen sind kreisf¨ormige Friese begrenzt. Es ist leicht, eine Zuordnung zwischen den Symmetrien eines Bandfrieses (vgl. Abschnitt 2.2) und den Symmetrien eines kreisf¨ormigen Frieses zu konstruieren. Translationen werden Drehungen und die Spiegelung rh an der horizontalen Achse wird zu einer Inversion (wie
¨ Abb. 2.12. Ein kreisf¨ ormiger Fries. (Vgl. Ubung 11.)
76
2 Friese und Mosaike
in (b) definiert). Definieren Sie die Transformation, die der Spiegelung rv an einer vertikalen Achse entspricht. Wir bezeichnen die letztgenannte Transformation ebenfalls als Spiegelung. Ist diese Spiegelung eine lineare Transformation? (Wie zuvor kann diese Transformation nur definiert werden, nachdem ein geeigneter Ursprung gew¨ ahlt worden ist. Das heißt, Sie m¨ ussen mit der entsprechenden Sorgfalt einen speziellen Punkt von Ar ausw¨ahlen, durch den der Spiegel“ geht.) ” (d) Konstruieren Sie – ausgehend von den drei Operationen der Drehung, Inversion und Spiegelung – eine Erzeugendenmenge f¨ ur die Symmetriegruppe des kreisf¨ ormigen Frieses von Abbildung 2.12. ¨ 12. (a) Diese Ubung setzt die vorhergehende fort. Es sei n die gr¨ oßte ganze Zahl, f¨ ur die ein invariant ist. Wir nehmen an, dass n ≥ 2. kreisf¨ormiger Fries bei einer Drehung von 2π n Klassifizieren Sie die Symmetriegruppen eines kreisf¨ormigen Frieses f¨ ur ein gegebenes n. H¨angt die Klassifizierung in irgendeiner Weise von n ab? (b) Die Ordnung einer Gruppe ist die Anzahl der Elemente der Gruppe. Die Ordnungen der Symmetriegruppen von regul¨ aren Friesen sind unendlich, aber die Ordnungen von kreisf¨ormigen Friesen sind endlich. Berechnen Sie die Ordnungen der Gruppen, die Sie in (a) konstruiert haben. 13. Bestimmen Sie f¨ ur jede der in Abbildung 2.13 dargestellten archimedischen Parkettierungen, zu welcher der 17 kristallografischen Gruppen sie geh¨ ort (manche der Parkettierungen m¨ ussen zu ein und derselben Gruppe geh¨ oren). Eine archimedische Parkettierung ist eine aus regul¨ aren Polygonen6 bestehende Parkettierung der Ebene, wobei die Polygone so beschaffen sind, dass jede Ecke vom gleichen Typ ist. Damit zwei Ecken vom gleichen Typ sind, m¨ ussen sie bei ¨ahnlichen Polygonen u ¨bereinstimmen, und die Polygone m¨ ussen in derselben Reihenfolge auftreten, wenn man sich um den Punkt in einer gegebenen Richtung dreht (zum Beispiel im Uhrzeigersinn). Es ist m¨ oglich, dass man das Spiegelbild einer solchen Parkettierung nicht mit Hilfe von Drehungen und Translationen herstellen kann. Setzen wir voraus, dass solche Parkettierungen bis auf ihr Spiegelbild eindeutig sind (wenn ein derartiges Bild von der urspr¨ unglichen Parkettierung verschieden ist), dann gibt es genau 11 Familien von archimedischen Parkettierungen. Das Spiegelbild ist bei genau einer dieser Parkettierungen von der urspr¨ unglichen Parkettierung verschieden. Identifizieren Sie diese Parkettierung. 14. Eine kleine Herausforderung: Klassifizieren Sie die archimedischen Parkettierungen (vgl. ¨ Ubung 13). (a) Es bezeichne n das regul¨ are Polygon mit n Seiten. Seine Innenwinkel sind alle gleich (n−2)π . (Beweisen Sie das!) Man betrachte eine archimedische Parkettierung und es sei n (n1 , n2 , . . . , nm ) die Liste der m Polygone, die sich in den Ecken dieser Parkettierung treffen. Die Summe der Winkel in einer gegebenen Ecke muss 2π sein, und deswegen gilt 6
Regul¨ are Polygone werden auch regelm¨ aßige Vielecke genannt.
¨ 2.5 Ubungen
¨ Abb. 2.13. Archimedische Parkettierungen. (Vgl. Ubung 13.)
77
78
2 Friese und Mosaike
(n1 − 2)π (n2 − 2)π (nm − 2)π + + ··· + . n1 n2 nm Zum Beispiel sind bei der archimedischen Parkettierung von Abbildung 2.14 die Polygone, die sich in einer Ecke treffen, durch die Liste (4, 3, 3, 4, 3) aufgez¨ ahlt, wobei wie gefordert die Beziehung 2π =
(4 − 2)π (3 − 2)π (3 − 2)π (4 − 2)π (3 − 2)π + + + + = 2π 4 3 3 4 3 gilt. Z¨ahlen Sie alle m¨oglichen Listen (n1 , n2 , . . . , nm ) von Polygonen auf, die sich in einer Ecke treffen k¨ onnen. Hinweis: Es gibt 17 derartige Listen, falls wir die ni nur nach ihrer Gr¨oße unterscheiden und nicht nach ihrer Reihenfolge. (b) Warum entspricht die Liste (5, 5, 10) keiner archimedischen Parkettierung der Ebene? (c) Verifizieren Sie f¨ ur jede der in (a) bestimmten Listen, ob die Menge der Polygone (n1 , n2 , . . . , nm ), die sich in einer Ecke treffen, tats¨ achlich eine Parkettierung der Ebene beschreiben. Achtung: Die Reihenfolge der Elemente der Liste (n1 , n2 , . . . , nm ) ist wichtig!
¨ Abb. 2.14. Ein n¨ aherer Blick auf eine archimedische Parkettierung (vgl. Ubung 14). Die Liste der Polygone, die sich in einer Ecke treffen, ist (4, 3, 3, 4, 3).
15. Ein schwieriges Problem: Klassifizieren Sie die archimedischen Parkettierungen der Kugel. In Abschnitt 15.8 sehen wir, dass jedes regul¨are Polyeder (Tetraeder, W¨ urfel, Oktaeder, Ikosaeder und Dodekaeder) einer regul¨aren Parkettierung der Kugel entspricht. Diese Zuordnung wird folgendermaßen konstruiert: •
Als Mittelpunkt des Polyeders wird der Koordinatenursprung genommen. Der Abstand zwischen dem Ursprung und jeder der Ecken ist also ein und derselbe. Nun
¨ 2.5 Ubungen
79
¨ Abb. 2.15. Ein Ikosaeder und die entsprechende Parkettierung der Kugel (vgl. Ubung 15).
wird dem Polyeder eine Kugel mit diesem Radius so umbeschrieben, dass sie durch alle Ecken geht; • F¨ ur jede Kante des Polyeders verbinden wir die Ecken durch einen Bogen des Großkreises zwischen ihnen. Das Endergebnis ist die gew¨ unschte Parkettierung der Kugel. Abbildung 2.15 zeigt eine solche Konstruktion f¨ ur ein Ikosaeder. Die Konstruktion kann f¨ ur jedes Polyeder wiederholt werden, dessen s¨ amtliche Ecken auf der Oberfl¨ ache einer Kugel liegen. Das ist der Fall bei archimedischen Polyeder: S¨ amtliche Fl¨ achen sind regelm¨ aßige Polygone mit derselben Seitenl¨ ange und alle ihre Ecken liegen auf denselben Polygonen. Obwohl regul¨are Polyeder (auch platonische K¨ orper genannt) diese Anforderungen erf¨ ullen, reservieren wir das Adjektiv ,,archimedisch“ f¨ ur Polyeder, deren Fl¨ achen aus mindestens zwei verschiedenen Arten von Polygonen bestehen. Ein Beispiel f¨ ur ein archimedisches Polyeder ist die bekannte Form eines Fußballs, formal als abgestumpftes Ikosaeder bekannt (vgl. Abbildung 2.16). Jede Ecke inzidiert mit zwei Sechsecken und einem F¨ unfeck. Wir kennzeichnen das abgestumpfte Ikosaeder durch die Liste (5, 6, 6). Archimedische
Abb. 2.16. Ein abgestumpftes Ikosaeder und die zugeh¨ orige Parkettierung der Kugel (vgl. ¨ Ubung 15).
80
2 Friese und Mosaike
Parkettierungen der Kugel werden wie folgt klassifiziert: Prismen, Antiprismen und 13 exzeptionelle Parkettierungen. (Manche Mathematiker ziehen es vor, die Prismen und Antiprismen nicht zu den archimedischen Parkettierungen zu z¨ ahlen, und verwenden diesen Begriff nur f¨ ur die 13 verbleibenden Parkettierungen.) (a) Die Liste (n1 , n2 , . . . , nm ) der Polygone, die sich in einer Ecke treffen, m¨ ussen zwei einfache Bedingungen erf¨ ullen. Damit jede Ecke konvex (und nicht planar) ist, muss die Summe der Innenwinkel, die an der Ecke liegen, kleiner als 2π sein:
π
m ni − 2 i=0
ni
< 2π.
Dieser Sachverhalt muss als erstes getestet werden. Die zweite Bedingung st¨ utzt sich auf den Satz von Descartes. Jeder Ecke des Polyeders wird ein Winkeldefekt zugeord
net, der als Δ = 2π − π i (ni − 2)/ni definiert wird. Der Satz von Descartes besagt, dass die Summe der Defekte u ¨ber alle Ecken eines Polyeders gleich 4π sein muss. Da alle Ecken eines archimedischen K¨ orpers identisch sind, muss 4π/Δ eine ganze Zahl sein, ¨ die gleich der Anzahl der Ecken ist. Dieser Sachverhalt ist der zweite Test. Uberzeugen Sie sich davon, dass der Fußball beide Bedingungen erf¨ ullt. (Wir werden bei (d) sehen, dass diese beiden Tests alleine nicht ausreichen, um die archimedischen K¨ orper zu charakterisieren.) (b) Ein Prisma ist ein Polyeder, das aus zwei identischen polygonalen Fl¨ achen besteht, die parallel sind. Jede Kante dieser beiden Fl¨ achen ist durch ein Quadrat verbunden. Sie bilden eine unendliche Familie von K¨ orpern, die mit (4, 4, n) f¨ ur n ≥ 3 bezeichnet ¨ werden. Uberzeugen Sie sich davon, dass Ecken eines solchen K¨ orpers identisch sind und durch die Liste (4, 4, n) exakt beschrieben werden. Zeichnen Sie ein Beispiel f¨ ur ein solches Prisma, zum Beispiel (4, 4, 5). Verifizieren Sie, dass die Liste (4, 4, n) unabh¨ angig von n die beiden in (a) beschriebenen Tests besteht. (Ist n hinreichend groß, dann beginnen diese K¨orper dicken Zylindern zu ¨ahneln.) (c) Ein Antiprisma besteht ebenfalls aus zwei parallelen identischen Polygonen mit n Ecken (n ≥ 4). Jedoch wird eines der Polygone in Bezug auf das andere um einen Winkel von nπ gedreht und die Ecken werden durch gleichseitige Dreiecke verbunden. Die Antiprismen bilden eine unendliche Familie von K¨ orpern, und sie werden durch die Liste (3, 3, 3, n) f¨ ur n ≥ 4 gekennzeichnet. Beantworten Sie dieselben Fragen wie f¨ ur Prismen. (d) Zeigen Sie, dass die Liste (3, 4, 12) die beiden in (a) beschriebenen Tests besteht. Es ist jedoch nicht m¨oglich, auf der Grundlage dieser Liste ein regul¨ ares Polyeder zu konstruieren. Warum? Hinweis: Beginnen Sie, ausgehend von einer einzigen Ecke, ein Dreieck, ein Quadrat und ein Polygon mit zw¨ olf Seiten (ein Zw¨ olfeck) zusammenzusetzen. Betrachten Sie die anderen Ecken dieser drei Fl¨ achen. Ist es m¨ oglich, dass diese Ecken die Konfiguration haben, die durch die Liste (3, 4, 12) beschrieben wird? (Das ist der schwierigste Teil dieser Frage!)
¨ 2.5 Ubungen
81
(e) Zeigen Sie, dass es 13 archimedische Parkettierungen der Kugel (oder ¨ aquivalent 13 archimedische Polyeder) gibt, die weder Prismen noch Antiprismen sind. (Der Fußball ist einer dieser 13 K¨orper.) 16. Eine schwere Aufgabe: Leiten Sie die kristallografischen Gruppen ab (diese sind in den Abbildungen 2.17–2.22 dargestellt).
82
2 Friese und Mosaike
Abb. 2.17. Die 17 kristallografischen Gruppen. Von oben nach unten: die Gruppen p1, pg, pm.
¨ 2.5 Ubungen
83
Abb. 2.18. Die 17 kristallografischen Gruppen (Fortsetzung). Von oben nach unten: die Gruppen cm, p2, pgg.
84
2 Friese und Mosaike
Abb. 2.19. Die 17 kristallografischen Gruppen (Fortsetzung). Von oben nach unten: die Gruppen pmg, pmm, cmm.
¨ 2.5 Ubungen
85
Abb. 2.20. Die 17 kristallografischen Gruppen (Fortsetzung). Von oben nach unten: die Gruppen p3, p31m, p3m1.
86
2 Friese und Mosaike
Abb. 2.21. Die 17 kristallografischen Gruppen (Fortsetzung). Von oben nach unten: die Gruppen p4, p4g, p4m.
¨ 2.5 Ubungen
87
Abb. 2.22. Die 17 kristallografischen Gruppen (Fortsetzung). Von oben nach unten: die Gruppen p6, p6m.
88
2 Friese und Mosaike
Literaturverzeichnis [1] A. Bravais, M´emoire sur les syst`emes form´es par des points distribu´es r´eguli`erement sur ´ un plan ou dans l’espace. Journal de l’Ecole Polytechnique, 19 (1850), 1–128. [2] H. S. M. Coxeter, Introduction to Geometry. Wiley, New York, 1969. [3] E. Prisse d’Avennes (Herausgeber), Arabic Art in Color. Dover, 1978. (In diesem Buch sind einige Ausz¨ uge aus Prisse d’Avennes’ monumentalem Werk L’art arabe d’apr`es les ” monuments du Kaire depuis le VIIe si`ecle jusqu’` a la fin du XVIIe si`ecle“ zusammengestellt. Er stellte diese Sammlung zwischen 1869 und 1877 zusammen. Die Originalausgabe wurde 1877 in Paris von Morel ver¨ offentlicht.) [4] B. Gr¨ unbaum, Z. Gr¨ unbaum und G. C. Shephard, Symmetry in Moorish and other ornaments. Computers and Mathematics with Applications, 12 (1985), 641–653. [5] B. Gr¨ unbaum und G. C. Shephard, Tilings and Patterns. W. H. Freeman, New York, 1987. [6] D. Schattschneider, Visions of Symmetry: Notebooks, Periodic Drawings, and Related Work of M. C. Escher. W. H. Freeman, New York, 1992.
3 Roboterbewegung
Dieses Kapitel kann in einer Vorlesungswoche abgedeckt werden. In der ersten Stunde wird der Roboter von Abbildung 3.1 beschrieben. Es ist wichtig, sich durch die Diskussion mehrerer einfacher Beispielen zu vergewissern, dass die Studenten den Begriff der Dimension“ (Anzahl der Freiheitsgrade) richtig verstanden haben. Danach werden die ” Drehungen im 3-dimensionalen Raum mit ihren Darstellungen als orthogonale Matrizen (Formulierung und Diskussion der Hauptergebnisse in Abschnitt 3.3) besprochen. In der letzten Stunde geht es um die sieben Bezugsrahmen, die dem Roboter von Abbildung 3.1 zugeordnet sind sowie um die Berechnung der Positionen der verschiedenen Artikulationen in jedem Bezugsrahmen (vgl. Abschnitt 3.5). Da diese Diskussion eine volle Stunde erfordert, ist es weder m¨ oglich, die ganze Diskussion u ¨ber orthogonale Transformationen noch alle Details des Fundamentalsatzes (Satz 3.20) zu behandeln, der besagt, dass alle orthogonalen Transformationen im R3 mit Determinante 1 Drehungen sind. Aus diesen Gr¨ unden werden die Hauptergebnisse nur formuliert und kurz erl¨ autert. Die wichtige Lehre aus den orthogonalen Transformationen besteht darin, dass die Wahl einer geeigneten Basis das Verst¨ andnis und die Veranschaulichung der Transformation erleichtert. Eine exakte Diskussion der orthogonalen Transformationen h¨ angt davon ab, welche Kenntnisse die Studenten aus der linearen Algebra mitbringen. Es ist m¨ oglich, einfach einige Beispiele durchzuarbeiten oder stattdessen einige Beweise durchzugehen.
3.1 Einfu ¨ hrung Man betrachte den dreidimensionalen Roboter in Abbildung 3.1. Er besteht aus drei Gelenken und einem Greifer. Auf der Abbildung haben wir sechs Drehungen angegeben, die der Roboter ausf¨ uhren kann; diese Drehungen sind mit 1 bis 6 durchnummeriert. Der Roboter ist an eine Wand montiert, sein erstes Segment ist senkrecht zur Wand. Dieses Segment ist jedoch nicht fixiert, sondern kann sich frei um seine Mittelachse drehen, was durch die Bewegung 1 angedeutet ist. Am Ende des ersten Segments befindet sich
C. Rousseau, Y. Saint-Aubin, Mathematik und Technologie, DOI 10.1007/978-3-642-30092-9_3, © Springer-Verlag Berlin Heidelberg 2012
90
3 Roboterbewegung
ein zweites Segment. Das Gelenk zwischen den zwei Segmenten ¨ ahnelt einem Ellenbogen darin, dass die Bewegung auf eine Ebene eingeschr¨ ankt ist (wie durch Bewegung 2 angedeutet). Kombinieren wir jedoch diese zul¨ assige Drehung mit der von 1, dann sehen wir, dass die Rotationsebene von 2 selbst l¨ angs des ersten Segments rotiert. Auf diese Weise erm¨oglicht uns die Zusammensetzung dieser beiden Drehungen, das zweite Segment in jeder m¨ oglichen Richtung zu positionieren. Wir sehen uns jetzt das dritte Segment an. Die Drehung 3 erm¨ oglicht dem Segment, sich in einer Ebene zu drehen (wie bei der Drehung 2), w¨ ahrend es die Drehung 4 gestattet, dass sich das Segment um seine Achse dreht. Man kann dieses Segment mit einer Schulter vergleichen: Wir k¨onnen unseren Arm heben (was zur Drehung 3 ¨ aquivalent ist) und wir k¨ onnen unseren Arm um seine Achse drehen (was zur Drehung 4 ¨ aquivalent ist). (In Wirklichkeit ist eine Schulter nicht gezwungen, den Arm in einer einzigen Ebene zu heben, das heißt, sie hat im Vergleich zu diesem Segment noch einen weiteren Freiheitsgrad, da wir unseren Arm – unter Beibehaltung eines festen Winkels mit der Vertikalen – um unseren K¨orper drehen k¨onnen.) Und schließlich befindet sich ein Greifer am Ende des dritten Segments. Dieser Greifer hat ebenfalls zwei zugeordnete Drehungen: Drehung 5 erfolgt in einer Ebene und variiert den Winkel zwischen dem dritten Segment und dem Greifer, w¨ahrend es die Drehung 6 dem Greifer erm¨ oglicht, sich um seine Achse zu drehen. Warum wurde dieser Roboter mit sechs Drehbewegungen ausgestattet? Wir werden sehen, dass das kein Zufall war und dass die Bewegungen des Roboters stark eingeschr¨ankt w¨aren, wenn er auch nur eine einzige Drehung weniger machen k¨ onnte. Wir beginnen mit einem einfachen Beispiel, bei dem Translationen betrachtet werden: Beispiel 3.1 Es sei P = (x0 , y0 , z0 ) ein Ausgangspunkt im R3 . Wir m¨ ochten bestimmen, welche Positionen Q wir erreichen k¨onnen, wenn wir Translationen l¨ angs der Einheitsrichtungen v1 = (a1 , b1 , c1 ) und v2 = (a2 , b2 , c2 ) zulassen. Die Menge der erreichbaren Punkte ist {Q = P + t1 v1 + t2 v2 | t1 , t2 ∈ R}. ¨ Diese Menge beschreibt eine Ebene durch P falls v1 = ±v2 . (Ubung: Beweisen Sie das!) angig sind, Geben wir eine dritte Richtung v3 so dazu, dass {v1 , v2 , v3 } linear unabh¨ dann ist die Menge der Positionen Q, die erreicht werden k¨ onnen, der ganze Raum R3 . Warum brauchten wir drei Translationsrichtungen, um den ganzen Raum erreichbar zu machen? Weil die Dimension des Raumes drei ist, was aus der Tatsache hervorgeht, dass wir drei Koordinaten ben¨otigen, um eine Position im R3 anzugeben. Wir sagen, dass das Problem drei Freiheitsgrade hat. Versuchen Sie, diesen Ansatz auf unseren Roboter zu u ¨bertragen: Wieviele Zahlen sind erforderlich, um dessen exakte Position vollst¨ andig zu beschreiben? F¨ ur einen Arbeiter, der den Roboter verwendet, um ein Objekt zu greifen, ist die exakte Positionierung des Greifers außerordentlich wichtig. Dieser Arbeiter spezifiziert folgende Angaben:
3.1 Einf¨ uhrung
91
Abb. 3.1. Ein dreidimensionaler Roboter mit sechs Freiheitsgraden.
•
Die Position von P : diese wird durch die drei Koordinaten (x, y, z) von P im Raum definiert. • Die Richtung der Greiferachse. Eine Richtung kann durch einen Vektor so spezifiziert werden, dass drei Zahlen notwendig zu sein scheinen. Es gibt jedoch unendlich viele Vektoren, die in dieselbe Richtung zeigen. Eine effizientere Art und Weise der Richtungsangabe besteht darin, sich eine Einheitskugel mit dem Mittelpunkt P vorzustellen und einen Punkt Q auf der Kugeloberfl¨ ache anzugeben. Der von P ausgehende und durch Q verlaufende Strahl gibt eine eindeutige Richtung an. Wenn wir uns selbst eine Richtung vorgeben, das heißt, einen von P ausgehenden Strahl, dann schneidet dieser die Kugel in genau einem Punkt. Es gibt also eine Bijektion zwischen den Punkten der Kugeloberfl¨ ache und den Richtungen. Die Angabe eines Punktes auf der Kugel reicht deswegen aus, um auf eindeutige Weise eine Richtung zu identifizieren. Am besten verwendet man hierzu sph¨arische Koordinaten. Die Punkte auf einer Kugel mit dem Radius 1 sind (a, b, c) = (cos θ cos φ, sin θ cos φ, sin φ) mit θ ∈ [0, 2π) und φ ∈ [− π2 , π2 ]. Demnach reichen die beiden Zahlen θ und φ aus, um die Richtung des Greifers zu beschreiben. • Der Greifer kann sich um seine Achse durch eine Drehung um einen Winkel drehen, dessen Gr¨oße durch einen einzigen Parameter α angegeben wird. Insgesamt ben¨otigten wir die sechs Zahlen (x, y, z, θ, φ, α), um die Position und die Orientierung des Greifers anzugeben. Analog zu Beispiel 3.1 sagen wir, dass der Roboter von Abbildung 3.1 sechs Freiheitsgrade hat. Die Drehungen 1, 2 und 3 werden verwendet, um P in die gew¨ unschte Position (x, y, z) zu bringen. Die Drehungen 4 und 5 werden verwendet, um die Achse des Greifers korrekt zu orientieren, w¨ ahrend die Drehung 6 den Greifer um den gew¨ unschten Winkel um seine Achse dreht. Diese sechs Bewegungen entsprechen den sechs Freiheitsgraden.
92
3 Roboterbewegung
Man beachte den Unterschied zwischen dem Punkt Q von Beispiel 3.1 und dem Greifer unseres Roboters. Wir ben¨ otigten nur drei Zahlen, um die Position von Q anzugeben, w¨ahrend wir sechs Zahlen brauchten, um die Position des Greifers anzugeben. Der Greifer ist ein Beispiel f¨ ur ein sogenanntes massives“ Objekt (etwa einen Festk¨ orper) im ” R3 und wir werden sehen, dass man immer sechs Zahlen ben¨ otigt, um die Position eines Festk¨orpers im Raum anzugeben. Um unsere Intuition zu entwickeln, beginnen wir mit der Untersuchung eines festen Objekts in der Ebene. 3.1.1 Bewegung eines Festk¨ orpers in der Ebene Schneiden Sie ein Dreieck aus Pappe derart, dass alle drei Winkel voneinander verschieden sind (so dass das Dreieck keine Symmetrien hat).
Abb. 3.2. Bewegung eines Festk¨ orpers in der Ebene.
Angenommen, das Dreieck l¨ asst sich nicht deformieren und muss ausschließlich in der Ebene bleiben; dann kann es in der Ebene lediglich gleiten. Wir m¨ ochten alle m¨ oglichen Positionen beschreiben, die das Dreieck einnehmen kann (s. Abbildung 3.2). Um das zu tun, w¨ahlen wir irgendeine Ecke des Dreiecks aus und beschriften sie mit A (wir h¨ atten ¨ dieselbe Uberlegung aber auch mit jedem anderen Punkt machen k¨ onnen).
3.1 Einf¨ uhrung
93
•
Wir beginnen mit der Angabe der Position von A. Dies erfordert die beiden Koordinaten (x, y) von A in der Ebene. • Danach geben wir die Orientierung des Dreiecks in Bezug auf den Punkt A an. Ist A fest, dann ist die einzig m¨ogliche Bewegung des Dreiecks eine Drehung um A. Ist B eine zweite Ecke des Dreiecks, dann wird die Position des Dreiecks durch den −−→ Winkel α bestimmt, der von dem Vektor AB und irgendeiner fest vorgegebenen Richtung eingeschlossen wird, zum Beispiel dem horizontalen Strahl, der sich von A nach rechts erstreckt.
Wir ben¨otigen also die drei Zahlen (x, y, α) zur vollst¨ andigen Angabe der Position des Dreiecks (und jedes anderen asymmetrischen Festk¨ orpers) in der Ebene. Wir betrachten Abbildung 3.2 und nehmen an, dass sich A im Koordinatenursprung −−→ befindet und der Vektor AB horizontal nach rechts zeigt. Um das Dreieck in die Position (x, y, α) zu bewegen, k¨onnen wir eine Translation um (x, 0) in Richtung e1 = (1, 0) durchf¨ uhren, danach eine Translation um (0, y) in Richtung e2 = (0, 1) und schließlich eine Drehung um den Winkel α um (x, y). ¨ Wir haben eine Aquivalenz zwischen den Zahlen (x, y, α), welche die Position des Dreiecks bestimmen, und den Bewegungen hergestellt, die das Dreieck – aus einer Position von (0, 0, 0) – in diese Position bringen. Wir geben folgenden Satz ohne Beweis an: Satz 3.2 Die Bewegungen eines Festk¨ orpers in der Ebene sind Zusammensetzungen von Translationen und Drehungen. Bei diesen Bewegungen bleiben L¨ angen, Winkel und die Orientierung erhalten. Beispiel 3.3 Stellen Sie sich einen Roboter vor, der in der Lage ist, die Bewegungen umzusetzen, die wir gerade beschrieben haben. Ein derartiger Roboter ist in Abbildung 3.3 dargestellt. Am Ende des zweiten Segments befindet sich ein Greifer, der senkrecht zur Bewegungsebene des Roboters gedreht werden kann. Wird ein Dreieck an der mit A beschrifteten Ecke an den Greifer geh¨ angt, dann entspricht die Drehung des Greifers der Drehung des Dreiecks um den Punkt A (vgl. Abbildung 3.4). Welches sind die Positionen, die vom ¨außersten Ende des zweiten Segments erreicht werden k¨ onnen? Es ist offensichtlich, dass wir nicht alle Punkte der Ebene erreichen k¨ onnen, da uns sowohl die L¨ange der Arme als auch das Vorhandensein der Wand Beschr¨ ankungen auferlegen. Aber wir k¨onnen viele Positionen erreichen, die durch eine 2-dimensionale Teilmenge der Ebene beschrieben werden. H¨ atte der Roboter nur ein einziges Segment, dann w¨aren wir auf eine 1-dimensionale Teilmenge der Ebene beschr¨ ankt, n¨ amlich auf einen Kreisbogen. Die exakte Bestimmung der Menge der durch A erreichbaren Positio¨ nen ist Gegenstand von Ubung 13. Dieses Beispiel verdeutlicht, dass drei Freiheitsgrade erforderlich sind, um einen Festk¨ orper durch die Ebene zu bewegen, und stellt einen Roboter dar, der diese Bewegungen umsetzen kann.
94
3 Roboterbewegung
Abb. 3.3. Ein Roboter in der Ebene.
(a) Anfangsposition
(b) Position nach Greiferdrehung um
π 3
Abb. 3.4. Bewegung l¨ angs des dritten Freiheitsgrades des Roboters aus Abbildung 3.3.
3.1.2 Einige Gedanken u ¨ ber die Anzahl der Freiheitsgrade Es gibt viele M¨oglichkeiten, einen Roboter im dreidimensionalen Raum zu bauen, aber sechs Freiheitsgrade (und somit mindestens sechs unabh¨ angige Bewegungen) sind notwendig, um jede m¨ogliche Position mit jeder m¨ oglichen Orientierung zu erreichen. Folglich sind sechs Freiheitsgrade auch in dem Steuersystem erforderlich, das den Roboter manipuliert. Man kann sich vorstellen, dem Roboterarm zus¨atzliche Segmente hinzuzuf¨ ugen und den Roboter auf einer F¨ uhrungsschiene zu installieren. Das vergr¨ oßert m¨ oglicherweise die Gr¨oße und ¨andert vielleicht die Form des Bereiches, der erreicht werden kann, aber
3.2 L¨ angen- und winkeltreue Bewegungen
95
es wird nichts an seiner Dimension“ ¨andern. Derartige Modifikationen k¨ onnen andere ” Vorteile bieten, die wir etwas sp¨ ater diskutieren werden. Andererseits kann man auch daran denken, einen Roboter zu bauen, der nur f¨ unf Freiheitsgrade hat. Ganz egal, wie man diese unabh¨angigen Bewegungen realisiert und miteinander verkn¨ upft: Es wird immer gewisse Positionen geben, die f¨ ur den Greifer unerreichbar sind. Tats¨ achlich gibt es nur eine kleine Menge von erreichbaren Positionen – im Gegensatz zur u ¨berw¨altigenden Mehrheit der unerreichbaren Positionen. Der Roboter von Abbildung 3.1 verwendet nur Drehungen. Diese Drehungen lassen sich leicht durch andere Bewegungen ersetzen, etwa durch Translationen l¨ angs einer F¨ uhrungsschiene oder durch Teleskoparme (das heißt, durch Segmente, deren L¨ ange sich ¨andern kann). Versuchen Sie, sich einige andere Roboterarme mit sechs Freiheitsgraden zu u ¨berlegen. Die zugrundeliegende Mathematik: Wenn wir die Bewegungen eines Roboters beschreiben m¨ochten, m¨ ussen wir die Bewegung eines Festk¨ orpers im R3 diskutieren. Wie in der Ebene sind diese Bewegungen Zusammensetzungen von Translationen und Drehungen. Im Allgemeinen haben unterschiedliche Drehungen auch verschiedene Drehachsen. • W¨ahlen wir ein Koordinatensystem, dessen Ursprung sich auf der Drehachse befindet, dann ist die Drehung in diesem Bezugsrahmen eine lineare Transformation. Ihre Matrix ist einfacher, wenn die Drehachse eine der Koordinatenachsen ist. ¨ • Da die Drehachsen voneinander verschieden sind, m¨ ussen wir Anderungen des Koordinatensystems ber¨ ucksichtigen. Wenn wir die Koordinaten eines Punktes Q in einem Koordinatensystem kennen, dann erm¨ oglichen es uns derartige Abbildungen, die Koordinaten des gleichen Punkts in einem neuen Koordinatensystem zu berechnen. • In unserem Beispiel von Abbildung 3.1 erm¨oglichen uns diese Transformationen die Berechnung der Endposition des Greifers nach Anwendung der Drehungen Ri (θi ) um die Winkel θi f¨ ur i ∈ {1, 2, 3, 4, 5, 6}.
3.2 L¨ angen- und winkeltreue Bewegungen in der Ebene und im Raum Wir beginnen mit linearen Transformationen, bei denen Abst¨ ande und Winkel erhalten bleiben: Das sind genau diejenigen Transformationen, deren Matrizen orthogon