edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Guy Merlin Mbakop
Titel: Effiziente Lösung reeller Polynomialer Gleichungssysteme
Gutachter: B. Bank; Luis Miguel Pardo; Werner Kleinert
Erscheinungsdatum: 24.09.1999
Volltext: pdf (urn:nbn:de:kobv:11-1009162)
ps (urn:nbn:de:kobv:11-1009172)
Fachgebiet(e): Mathematik
Schlagwörter (ger): affiner (geometrischer) Grad, geometrischer Algorithmus, Straight--Line Programm und arithmetisches Netzwerk, polare Varietät
Schlagwörter (eng): affine (geometric) degree, geometric algorithm, straight--line program and arithmetic network, polar variety
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Zitationshinweis: Mbakop, Guy Merlin: Effiziente Lösung reeller Polynomialer Gleichungssysteme; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 24.09.1999, urn:nbn:de:kobv:11-1009172
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.
Diese Seite taggen: Diese Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer ansehen können.
  • connotea
  • del.icio.us
  • Furl
  • RawSugar

Abstract (ger):
Diese Arbeit beinhaltet {\it geometrische Algorithmen} zur L\"osung reeller polynomialer Gleichungssysteme mit rationalen Koeffizienten, wobei die Polynome eine reduzierte regul\"are Folge bilden (vgl. Abschnitt \ref{abschgeo}). Unter reellem L\"osen verstehen wir hier die Bestimmung eines Punktes in jeder Zusammenhangskomponente einer kompakten glatten reellen Variet\"at $V:=W \cap \R^n$.\\ Im Mittelpunkt steht die Anwendung des f\"ur den algebraisch abgeschlossenen Fall ver\"offentlichten symbolischen geometrischen Algorithmus nach \cite{gh2} und \cite{gh3}. Die Berechenungsmodelle sind {\em Straight--Line Programme} und {arithmetische Netzwerke} mit Parametern in $\; \Q$. Die Input--Polynome sind durch ein Straight--Line Programm der Gr\"o{\ss}e $L$ gegeben. Eine geometrische L\"osung des Input--Glei\-chungs\-sys\-tems besteht aus einem primitiven Element der Ringerweiterung, welche durch die Nullstellen des Systems beschrieben ist, aus einem mininalen Polynom dieses primitiven Elements, und aus den Parametrisierungen der Koordinaten. Diese Darstellung der L\"osung hat eine lange Geschichte und geht mindestens auf Leopold Kronecker \cite{kron} zur\"uck. Die Komplexit\"at des in dieser Arbeit begr\"undeten Algorithmus erweist sich als linear in $L$ und polynomial bez\"uglich $n, d, \delta$ bzw. $\delta \;'$, wobei $n$ die Anzahl der Variablen und $d$ eine Gradschranke der Polynome im System ist. Die Gr\"o{\ss}en $\delta$ und $\delta \; '$ sind geometrische Invarianten, die das Maximum der {\em Grade des Inputsystems} und geeigneter {\em polarer Variet\"aten} repr\"asentieren (bzgl. des ({\em geometrischen}) Grades vgl. \cite{he}). Die Anwendung eines Algorithmus \"uber den komplexen Zahlen auf das L\"osen von polynomialen Gleichungen im Reellen wird durch die Einf\"urung polarer Variet\"aten m\"oglich (vgl. \cite{bank}). Die polaren Variet\"aten sind das Kernst\"uck und das vorbereitende Werzeug zur effizienten Nutzung des oben erw\"ahnten geometrischen Algorithmus. Es wird ein inkrementelles Verfahren zur Auffindung reeller Punkte in jeder Zusammenhangskomponente der Nullstellenmenge des Inputsystems abgeleitet, welches einen beschr\"ankten glatten (lokalen) vollst\"andigen Durchschnitt in $\R^n$ beschreibt. Das Inkrement des Algorithmus ist die Kodimension der polaren Variet\"aten. Die Haupts\"atze sind Satz $\ref{theorem12}$ auf Seite $\pageref{theorem12}$ f\"ur den Hyperfl\"achenfall, und Satz $\ref{theoresult}$ auf Seite $\pageref{theoresult}$, sowie die Aussage in der Einf\"uhrung dieser Arbeit, Seite $\pageref{vollres}$ f\"ur den vollst\"andigen Durchschnitt.
Abstract (eng):
This dissertation deals with {\em geometric algorithms} for solving real multivariate polynomial equation systems, that define a reduced regular sequence (cf. subsection $\ref{abschgeo}$). Real solving means that one has to find at least one real point in each connected component of a real compact and smooth variety $V := W \cap \R^n$. \\ The main point of this thesis is the use of a complex symbolic geometric algorithm, which is designed for an algebraically closed field and was published in the papers \cite{gh2} and \cite{gh3}. The models of computation are {\em straight--line programms} and {\em arithmetic Networks} with parameters in $\; \Q$. Let the polynomials be given by a division--free straight--line programm of size $L$. A geometric solution for the system of equations given by the regular sequence consists in a {\em primitiv element} of the ring extension associated with the system, a minimal polynomial of this primitive element and a parametrization of the coordinates. This representation has a long history going back to {\em Leopold Kronecker} \cite{kron}. The time--complexity of our algorithms turns out to be linear in $L$ and polynomial with respect to $n, d, \delta$ or $\delta '$, respectively. Here $n$ denotes the number of variables, $d$ is an upper bound of the degrees of the polynomials involved in the system, $\delta$ and $\delta '$ are geometric invariants representing the maximum of the {\em affine (geometric) degree} of the system under consideration and the affine (geometric) degree of suitable {\em polar varieties} (cf. \cite{he} for the ({\em geometric}) degree). The application of an algorithm running in the complex numbers to solve polynomial equations in the real case becomes possible by the introduction of polar varieties (cf. \cite{bank}). The polar varieties introduced for this purpose prove to be the corner--stone and the preliminary tool for the efficient use of the geometric algorithm mentioned above. An incremental algorithm is designed to find at least one real point on each connected component of the zero set defined by the input under the assumption that the given semialgebraic set $V = W \cap \R^n$ is a bounded, smooth (local) complete intersection manifold in $\R^n$. The increment of the new algorithm is the codimension of the polar varieties under consideration. The main theorems are Theorem $\ref{theorem12}$ on page $\pageref{theorem12}$ for the hypersurface case, and Theorem $\ref{theoresult}$ on page $\pageref{theoresult}$ for the complete intersection as well as the statement in the introduction of this thesis on page $\pageref{vollres}$.
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
Startseite: 4 Zugriffe PDF: 2 Zugriffe Startseite: 2 Zugriffe PDF: 9 Zugriffe Startseite: 7 Zugriffe PDF: 7 Zugriffe PDF: 10 Zugriffe Startseite: 5 Zugriffe PDF: 22 Zugriffe Startseite: 1 Zugriffe PDF: 13 Zugriffe Startseite: 1 Zugriffe PDF: 75 Zugriffe PDF: 16 Zugriffe PDF: 20 Zugriffe Startseite: 3 Zugriffe PDF: 31 Zugriffe Startseite: 5 Zugriffe PDF: 11 Zugriffe Startseite: 1 Zugriffe PDF: 6 Zugriffe PDF: 21 Zugriffe PDF: 13 Zugriffe PDF: 11 Zugriffe PDF: 10 Zugriffe Startseite: 4 Zugriffe PDF: 30 Zugriffe Startseite: 3 Zugriffe PDF: 34 Zugriffe Startseite: 1 Zugriffe PDF: 35 Zugriffe Startseite: 2 Zugriffe PDF: 20 Zugriffe Startseite: 1 Zugriffe PDF: 28 Zugriffe Startseite: 1 Zugriffe PDF: 13 Zugriffe Startseite: 1 Zugriffe PDF: 27 Zugriffe Startseite: 2 Zugriffe PDF: 5 Zugriffe Startseite: 4 Zugriffe PDF: 12 Zugriffe Startseite: 3 Zugriffe PDF: 22 Zugriffe Startseite: 2 Zugriffe PDF: 5 Zugriffe Startseite: 1 Zugriffe PDF: 16 Zugriffe Startseite: 1 Zugriffe PDF: 18 Zugriffe Startseite: 2 Zugriffe PDF: 30 Zugriffe Startseite: 3 Zugriffe PDF: 26 Zugriffe Startseite: 2 Zugriffe PDF: 35 Zugriffe Startseite: 2 Zugriffe PDF: 30 Zugriffe Startseite: 2 Zugriffe PDF: 18 Zugriffe PDF: 28 Zugriffe Startseite: 3 Zugriffe PDF: 11 Zugriffe Startseite: 5 Zugriffe PDF: 26 Zugriffe
Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Monat Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Startseite 4 2 7   5 1 1     3 5 1         4 3 1 2 1 1 1 2 4 3 2 1 1 2 3 2 2 2   3 5
PDF 2 9 7 10 22 13 75 16 20 31 11 6 21 13 11 10 30 34 35 20 28 13 27 5 12 22 5 16 18 30 26 35 30 18 28 11 26

Gesamtzahl der Zugriffe seit Jul 2011:

  • Startseite – 74 (2 pro Monat)
  • PDF – 746 (20.16 pro Monat)
 
 
Generiert am 31.10.2014, 09:00:45