Varignon’scher Apparat

Varignon'scher Apparat

Der Varignon'sche Apparat, benannt nach dem französischen Mathematiker und Physiker Pierre de Varignon, ist eine einfache Anordnung, um ein Standort-Optimierungsproblem experimentell zu lösen: Auf einer Tischplatte werden mehrere Standorte maßstabsgetreu eingezeichnet. An diesen Standorten werden Löcher gebohrt, durch welche Fäden gezogen werden. Die Enden aller Fäden werden auf der Tischoberseite zusammengeknotet. Unterhalb der Tischplatte werden der Beteiligten entsprechende Gewichte an die Fäden gehängt. Als Gewicht nimmt man beispielsweise eine Personenanzahl oder Einwohneranzahl, um die Gewichtung des Standorts auszudrücken. Die Kräfte, die nun wirken, ziehen den Knotenpunkt auf der Oberfläche der Platte zum optimalen Standort.

Mechanisches Problem

Im Punkt $\mathbf {v}$ ist die Summe aller Kräfte =0

Sind die Löcher in der ebenen Platte an den Stellen $\mathbf {x} _{1}=(x_{1},y_{1}),\dots ,\mathbf {x} _{n}=(x_{n},y_{n})$ angebracht und hängen an den Fäden die Massen $m_{1},\dots ,m_{n}$ , so muss der Gleichgewichtspunkt $\mathbf {v} =(x,y)$ die Gleichgewichtsbedingung (Summe aller Kräfte im Punkt $\mathbf {v}$ ist Null) erfüllen. Der Betrag der im i-ten Faden angreifenden Kraft $\mathbf {f} _{i}$ ist $m_{i}g$ ($g$ ist die Erdbeschleunigung) und hat die Richtung ${\tfrac {\mathbf {x} _{i}-\mathbf {v} }{|\mathbf {x} _{i}-\mathbf {v} |}}$ (Einheitsvektor). Summiert man diese Kräfte auf und kürzt den gemeinsamen Faktor $g$ heraus, erhält man die Gleichung

(1):$\ \mathbf {F} (\mathbf {v} )=\sum _{i=1}^{n}m_{i}{\frac {\mathbf {x} _{i}-\mathbf {v} }{|\mathbf {x} _{i}-\mathbf {v} |}}=\mathbf {0}$.

In Komponenten bedeutet diese Vektorgleichung

$\sum _{i=1}^{n}m_{i}{\frac {x_{i}-x}{|\mathbf {x} _{i}-\mathbf {v} |}}=0$

$\sum _{i=1}^{n}m_{i}{\frac {y_{i}-y}{|\mathbf {x} _{i}-\mathbf {v} |}}=0$.

Dies ist ein nichtlineares Gleichungssystem für die Unbekannten $x,y$ und kann mit dem 2-dimensionalen Newton-Verfahren oder dem Weiszfeldverfahren gelöst werden.

Standort-Problem

Die linke Seite der Gleichung (1) lässt sich auch als Gradient der Funktion

(2):$\ D(\mathbf {x} )=\sum _{i=1}^{n}m_{i}|\mathbf {x} _{i}-\mathbf {x} |$

Varignon-Apparat: Beispiel

Beispiel mit Niveau-Kurven

auffassen. Die Funktion $D$ wiederum beschreibt die Summe der mit $m_{1},\dots ,m_{n}$ gewichteten Abstände $|\mathbf {x} _{1}-\mathbf {x} |,\dots ,|\mathbf {x} _{n}-\mathbf {x} |$ der Punkte $\mathbf {x} _{1},\dots ,\mathbf {x} _{n}$ von dem Punkt $\mathbf {x}$. Da der Gradient der Funktion $D$ im Punkt $\mathbf {v}$ gleich Null ist, besitzt $D$ in $\mathbf {v}$ ein relatives Extremum. Das heißt, der Varignon'sche Apparat liefert eine einfache Möglichkeit, das Standort-Problem (Optimierung) experimentell zu lösen und Newton- und Weiszfeld-Verfahren liefern rechnerische Lösungen.

Beispiel

Für das Beispiel (siehe Bilder) sind die Punkte

$X_{1}=(0,0),X_{2}=(40,0),X_{3}=(50,40),$

$X_{4}=(10,50),X_{5}=(-10,30)$ und die Gewichte :$m_{1}=10,m_{2}=10,m_{3}=20,m_{4}=10,m_{5}=5$.

Die Koordinaten des optimalen Punktes (rot) sind $(32{,}5;30{,}1)$ und die optimale gewichtete Längensumme ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L_\text{op} = 1679} . Das zweite Bild zu diesem Beispiel zeigt Niveau-Kurven nicht-optimaler Punkte mit derselben gewichteten Längensumme (gLS). Von innen nach außen sind die (größeren) gLS Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1680,1710,1760,1820,1900} .
Niveau-Kurven kann man dazu benutzen, um Bereiche zu beschreiben, in denen die Kosten die dem Niveau zugehörigen Kosten nicht überschreiten. Geometrisch sind sie implizite Kurven mit Gleichungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \; D(\mathbf x)-c=0, \; c>L_\text{op}\;} (siehe Formel (2)).

Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n=2, m_1=m_2=1} , die Niveau-Kurven sind konfokale Ellipsen

Die Fälle n=1 und n=2

• Im Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n=1} ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf v = \mathbf x_1} .
• Im Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n=2} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_2>m_1} ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf v = \mathbf x_2} .
• Im Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n=2} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_2=m_1} kann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf v } jeder Punkt der Strecke Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \overline{X_1X_2}} sein (siehe Bild). In diesem Fall sind die Niveau-Kurven (Punkte mit derselben nicht-optimalen Längensumme) konfokale Ellipsen mit den Punkten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf x_1,\mathbf x_2} als gemeinsamen Brennpunkten.

Berechnung mit dem Newton-Verfahren (Extremalproblem)

Bezeichnungen: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ D_i=|\mathbf x_i-\mathbf x|\ , \ D(\mathbf x)=\sum_{i=1}^n m_iD_i}

Für die Jacobi-Matrix des Newton-Verfahrens berechnet man die zweiten partiellen Ableitungen der Funktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_i} . Die Koeffizienten der für die Newton-Iteration benötigten Jacobi-Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle J(\mathbf{x}) } sind dann:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle J_{xx}=\sum_{i=1}^n m_iD_{ixx} , \quad J_{xy}=\sum_{i=1}^n m_iD_{ixy},\quad J_{xx}=\sum_{i=1}^n m_iD_{ixx}}

Iteration: Man wählt einen Startpunkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf v_0} und löst für jeden Schritt das lineare Gleichungssystem (z. B. mit der Cramerschen Regel)

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle J(\mathbf{v}_{k})\;\Delta \mathbf{v}_k = -\mathbf F(\mathbf{v}_{k})} .

Danach erhält man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ \mathbf{v}_{k+1}=\mathbf{v}_{k}+\Delta \mathbf{v}_{k}.}

Berechnung mit dem Steiner-Weber-Ansatz (Fixpunktproblem)

Iteration mit dem Fixpunkt-Verfahren für das Beispiel: Startpunkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf v_0=(25,15)} (grün), Startpunkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf v_m} (blau) ist der Massenmittelpunkt (Masse Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_i} im Punkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf x_i} )

Der folgende auf Jakob Steiner zurückgehende Algorithmus basiert auf der Idee, in Gleichung (1) im Zähler die Näherung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf v_{k+1}} und im Nenner die Näherung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf v_k} einzusetzen und diese Gleichung dann nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf v_{k+1}} aufzulösen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf v_{k+1}=\sum_{i=1}^n \frac{m_i\mathbf x_i}{|\mathbf x_i-\mathbf v_k|}\big/ \sum_{i=1}^n \frac{m_i}{|\mathbf x_i-\mathbf v_k|}}

Als Startpunkt wird der Massenmittelpunkt der Anordnung mit den Massen in den Punkten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf x_i} verwendet:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf v_0= \frac{\sum_{i=1}^n m_i \mathbf x_i}{\sum_{i=1}^n m_i}} .

Der Weiszfeld-Algorithmus benutzt diese Iterationformel.

Die Iterationsformel kann als Iteration zur Bestimmung des Fixpunktes der Funktion

(3)Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \quad G(\mathbf x)=\sum_{i=1}^n \frac{m_i\mathbf x_i}{|\mathbf x_i-\mathbf x|}\big/ \sum_{i=1}^n \frac{m_i}{|\mathbf x_i-\mathbf x|}}

mit der Fixpunktgleichung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \quad \mathbf x= G(\mathbf x)}

angesehen werden (Siehe hierzu Fixpunktsatz von Banach.)

Bemerkung zu numerischen Problemen:
Beide Iterationsverfahren in der hier beschriebenen Form haben numerische Probleme, falls ein Iterationspunkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf v_k} in der Nähe eines der gegebenen Punkte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf x_1,...\mathbf x_n} liegt.

Siehe auch

• Fermat-Punkt (Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n=3, m_1=m_2=m_3=1} )
• Webersches Standortmodell
• Weber-Problem (engl.)

Weblinks

• MathePrisma Uni Wuppertal: Lösung eines Standort-Problems mit GeoGebra

Literatur

• Uwe Götze: Risikomanagement, Physica-Verlag HD, 2013, ISBN 978-3-642-57587-7, S. 268