Lokal optimale Schranken bei Randwertaufgaben

Zusammenfassung Bei der Berechnung von unteren und oberen Schranken für Lösungen von Randwertaufgaben mit elliptischer Differentialgleichung kann der Randmaximumsatz verwendet werden. In diesem Beitrag werden zwei Prinzipien verglichen: Ein bekanntes Verfahren derTschebyscheff-Approximation für gleichmäßig optimale Schranken und ein neues Optimierungsverfahren für lokal optimale Schranken. Für das zweite Prinzip wird ein Existenzsatz bewiesen und die Erweiterung auf zusammengesetzte Bereiche und die Anwendung desNewton-Verfahrens besprochen.

---

Summary The computation of lower and upper bounds for solutions of boundary value problems with elliptic differential equation is possible by the application of the boundary maximum theorem. In the present paper we compare two principles: A known method ofChebyshev-approximation for uniformly optimal bounds and a new method of optimization for locally optimal bounds. For the second principle we prove an existence theorem and discuss the extension to composite regions and the application ofNewtons method.

     

Eine Methode zur Bestimmung günstiger Konvergenzfaktoren für asymptotische Entwicklungen

Zusammenfassung Wir befassen uns mit der numerischen Lösung einer Differentialgleichung, bei der eine asymptotische Potenzreihe zur Verfügung steht. Besonders interessieren wir uns für Argumente aus dem kritischen Bereich. Dabei tritt das Problem der Bestimmung günstiger Konvergenzfaktoren auf.Es wird für den Formelfehler in Abhängigkeit von den verwendeten Konvergenzfaktoren eine recht genaue Abschätzung sowohl nach oben wie auch nach unten angegeben. Zur Herleitung der Fehlerschranken wird die Theorie der singulärenVolterraschen Integralgleichungen benützt. Die Minimierung der Fehlerschranken liefert dann sehr günstige Konvergenzfaktoren, bei denen der zugehörige Fehler nur wenig über dem Fehler der theoretisch optimalen Lösung liegt. Ferner ergeben sich Aussagen über die Konvergenzgeschwindigkeit der Approximationsfolge. Ein Beispiel zeigt die Wirksamkeit des Verfahrens.

---

Summary We are concerned with the numerical solution of a differential equation which possesses an asymptotic power series. Especially we are interested in arguments from the critical domain. This leads us to the determination of nearly-optimal converging factors.Using the theory of singularVolterra integral equations we obtain for the remainder terms as functions of the converging factors rather good lower and upper bounds.Minimizing these bounds we gain nearly-optimal converging factors, with an error only little greater than the error of the exact optimal converging factors. Moreover we give an estimate of the rapidity of convergence of the approximation sequence. An example shows the effectiveness of our method.

---

---

Mit 3 Textabbildungen     

Numerical stability of a quadratic method for solving systems of non linear equations

In this paper the numerical stability of a recent method to solve systems of nonlinear equations is studied. This method, based on the -algorithm, has a quadratic convergence without calculating any derivatives and under quite benevolent conditions. The numerical stability of this algorithm is studied using the theory of theA-stability for the propagation of round-off errors in the numerical integration of differential equations.

---

Numerische Stabilität einer quadratisch konvergenten Methode zur Lösung von Systemen nicht-linearer Gleichungen

Zusammenfassung In diesem Artikel wird die numerische Stabilität einer neuen Methode zur Lösung von Systemen nicht-linearer Gleichungen studiert. Diese Methode, sie basiert auf dem -Algorithmus, ist unter schwachen Voraussetzungen und ohne Verwendung von Ableitungen quadratisch konvergent. Die Stabilität dieses Algorithmus wird unter Verwendung der Theorie derA-Stabilität bezüglich der Fortpflanzung von Rundungsfehlern bei der numerischen Integration von Differentiagleichungen studiert.

     

Über das Transportproblem mit beliebigen zusätzlichen linearen Nebenbedingungen

Zusammenfassung Das klassische Transportproblem wurde durch zusätzliche Bedingungen ergänzt, die in Form beliebiger linearer Gleichungen oder Ungleichungen vorgegeben sind und allenfalls auch zusätzliche Variable beinhalten können. Für das so entstandene lineare Programm wurde ein rationeller Speicherraum sparender Algorithmus entwickelt. Es wird allerdings angenommen, daß die Anzahl der Zusatzbedingungen verhältnismäßig klein ist. Das Verfahren wurde an einer IBM 7040 (16 K) erprobt. Ein in Fortran IV abgefaßtes Rechenprogramm ist im Anhang wiedergegeben.

---

Summary The classical transportation problem is augmented by a set of additional constraints, which are arbitrary linear equalities or inequalities and may contain also some additional variables. A special algorithm for this linear program is described. The method is thought to be efficient, if the number of the additional constraints is comparitively small. The algorithm has been tested on a IBM 7040 (16 K) Computer. A Fortran IV program is included in the appendix.

     

Generating test programs from syntax

Summary The many faces of programming and systems development demand an immense amount of mechanical routine work. The present paper tries to explain some areas where automation of many tasks may be of great help. One special area, where progress seems to lag behind unduly, can be found in debugging, testing, and diagnosing systems. Here we attempted the generation of programs automatically from a definition of a problem and the characteristics of programs for its solution by a software system, which has been specially designed for this purpose. It has been indicated how the ideas underlying this project may be applied successfully to other areas.

---

Zusammenfassung Bei der Programmierung und Systementwicklung wird zu einem erheblichen Umfang mechanische Routinearbeit erfordert. Der vorliegende Beitrag grenzt verschiedene Gebiete ab, wo mehrere Aufgabenlösungen automatisiert werden können. Ein Spezialgebiet, in welchem die Techniken auf niedrigem Stand zurückgeblieben scheinen, findet sich im Analysieren und Ausprüfen von Systemprogrammen. Hier haben wir versucht, Programme durch ein System automatisch zu erzeugen, ausgehend von einer Definition des Problems und den Charakteristiken seiner Lösung. Dieses System war zu diesem Zweck entwickelt worden. Ferner wird angedeutet, wie die Ideen, auf denen dieser Beitrag beruht, auf andere Gebiete erfolgreich angewendet werden können.

---

---

With 18 Figures     

Über die Approximation asymptotischer Entwicklungen I

Zusammenfassung Für einige Typen linearer homogener Differentialgleichungen werden an Stelle der asymptotischen Entwicklungen für große Werte der unabhängigen Variablenx Approximationen im gleichmäßigen Sinne aus der Differentialgleichung heraus entwickelt. Im vorliegenden ersten Teil werden Lösungen mit exponentiellem Abklingen untersucht. Man erhält exakte Aussagen über die Abweichung von der besten Approximation durch Polynome inx ^–1 und numerisch günstige Näherungen, die zur Aufstellung von Unterprogrammen benutzt werden können. Am Beispiel der Gaußschen Normalverteilung wird das Verfahren explizit durchgeführt.

---

Summary For some types of linear homogeneous differential equations approximations in the uniform sense (instead of asymptotic expansions) for large values of the independent variable are derived. In this first part only solutions with a decreasing exponential factor are considered. Exact statements concerning the deviation from the best approximation by polynomials inx ^–1 and good numerical approximations as to be used in setting up subroutines for digital computers are obtained. As an example serves the normal distribution of Gauss.

---

---

Mit 1 Textabbildung     

A note on polychotomy

Previous analyses on bounds for the growth of solutions of BVP were dealing either with two point or multipoint conditions. For BVP where some of the two point boundary conditions are separated from the rest one could only give a cruder polychotomy result for a multipoint case as such. In this note we show that such a (decoupled) two point condition actually induces a dichotomic subspace. This is done by reconsidering the notions of dichotomy and polychotomy and deriving appropriate projection mappings which describe the solution space structure.

---

Eine Bemerkung zur Polychotomie

Zusammenfassung Bisher haben sich Untersuchungen über Wachstumsschranken für Lösungen von Randwertproblemen entweder mit 2-Punkt-oder mit Mehrpunkt-Bedingungen beschäftigt. Wenn jedoch einige der 2-Punkt-Bedingungen unabhängig von den übrigen Bedingungen sind, dann konnte man nur ein gröberes Polychotomie-Resultat angeben. In dieser Note wird gezeigt, daß eine solche (entkoppelte) 2-Punkt-Bedingung tatsächlich einen dichotomen Unterraum induziert. Dazu werden die Begriffe Dichotomie und Polychotomie genauer untersucht und es werden geeignete Projektionen zur Beschreibung der Struktur des Lösungsraumes hergeleitet.

---

---

Dedicated to Professor Hans J. Stetter on the occasion of his 60th birthday

---

Supported in Part by a grant from the Netherlands Organisation for Scientific Research (NWO).     

Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken

Zusammenfassung In der vorliegenden Arbeit werden zunächst Definitionen und Eigenschaften von Intervall-Normen und-Spannen behandelt. Sodann werden einigeNewton-Algorithmen zur Bestimmung von Nullstellen einer Funktion mit einer Veränderlichen angegeben. Diese Algorithmen liefern mit Hilfe einer Intervallarithmetik als Ergebnis ein Intervall, in dem die exakte Nullstelle liegt. Eine Verallgemeinerung der Algorithmen zur Lösung eines Gleichungssystems wird ebenfalls hergeleitet.

---

Newton-algorithms for evaluation of roots with error bounds

Summary In this paper some definitions and properties of interval-norms and spans are treated. Then severalNewton-algorithms for finding roots of functions with one variable are given. The algorithms use interval-arithmetics and yield an interval-result containing the exact root. The algorithms then are generalized to solve systems of equations.

     

Die Regula falsi in Banach-Räumen

Zusammenfassung In Abschnitt 1 werden Eindeutigkeits- und Stabilitätsaussagen für die Regula falsi (RF) aufgestellt. Teil 2 zeigt, wie man mit Hilfe der RF ein gegebenes Problem lösen kann, wenn man eine Lösung eines benachbarten Problems kennt. Schließlich wird in 3. gezeigt, daß die RF Monotonieeigenschaften besitzt, die denen desNewton-Verfahrens überlegen sind: sie ermöglichen Einschließungen der Lösung eines Vorgelegten Problems und garantieren in einem Spezialfall sogar deren Existenz.

---

The regula falsi in banach spaces

Summary At first this paper presents uniqueness- and stability statements. Furthermore it is shown how to solve a problem with the aid of the Regula falsi using a solution of a neighbouring problem. Finally the paper contains monotonicity principles for the Regula falsi. These are superior to those forNewton's method: they offer the possibility of bracketing a solution of a given problem. In a special case they even ensure the existence of a solution.

     

Ableitungsfreie Verfahren mit höherer Konvergenzgeschwindigkeit

Zusammenfassung Für Gleichungen in mehrdimensionalen Räumen werden Klassen von ableitungsfreien Verfahren angegeben, welche in der Durchführung allein Steigungen erster Ordnung benötigen. Ein Iterationsschritt besteht ausk Stufen, wobei die einzelnen Stufen die Anwendung der vereinfachten Regula falsi bedeuten. Es ergibt sich, daß sich das Maximum des Wirkungsgrades mit wachsender Dimension zu den größerenk-Werten hin verschiebt. Die Konvergenz der Verfahren wird für einfache Nullstellen und hinreichend gute Startwerte nachgewiesen.

---

Summary For equations in spaces of several dimensions classes of methods not involving derivatives are given which require only first-order divided differences. One interation step consists ofk stages each of them meaning the application of the modified regula falsi. The maximum of the efficiency index is shown to shift to greater values ofk with increasing dimension. The convergence of the methods is proved for simple zeros and sufficiently good initial values.

---

---

Herr Prof. Dr.H. Heinrich hat in Vorträgen an den Technischen Hochschulen Wien und Graz im Dezember 1967 über den Gegenstand der Arbeit berichtet. Wir möchten ihm an dieser Stelle dafür unseren herzlichen Dank aussprechen.     

Über Matrixnormen,Gerschgorinkreise und Jacobi-Rotation

Zusammenfassung Für endliche Matrizen wird ein allgemeines Prinzip gezeigt, das jeder Matrixnorm einen Einschließungssatz für eigenwerte zuordnet. Für die Norm der maximalen Zeilenbetragssumme ergibt sich speziell der Satz vonGerschcorin. Ein anderer Einschließungssatz wird dazu benutzt, für die Abweichungen der Eigenwerte von den Diagonalelementen Schranken aufzustellen, die von der Ordnung der Matrix, dem Maximalbetrag der Nichtdiagonalelemente und den Abständen der Diagonalelemente abhängen. Diese Schranken liefern Fehlerabschätzungen für dasJacobi-Verfahren zur Bestimmung der Eigenwerte symmetrischer Matrizen.

---

Summary There exists a general principle for finite matrices, according to which to every matrix norm corresponds an inclusion theorem for eigenvalues. If the norm is the row-sum norm, we have theGershgorin theorem. Another inclusion theorem is used for obtaining bounds for the deviations of the eigenvalues from the diagonal elements, involving the order of the matrix, the maximal modulus of the off-diagonal elements and the distances of the diagonal elements. These bounds yield estimates for theJacobi method for determination of eigenvalues of symmetric matrices.

     

Schnelle Berechnung von Kettenbruchentwicklungen

Zusammenfassung Ein von D. E. Knuth angegebenes Verfahren, für ganze Zahlen u, v den größten gemeinsamen Teiler und den Kettenbruch für u/v zu berechnen, wird so modifiziert, daß für n-stellige Zahlen nur O(n(lg n)² (lglg n)) elementare Schritte gebraucht werden.

---

Summary A method, given by D. E. Knuth for the computation of the greatest common divisor of two integers u, v and of the continued fraction for u/v is modified in such a way that only O(n(lg n)²(lglg n)) elementary steps are used for u,v<.2 ⁿ.

     

A storage scheme for extendible arrays

Conventional methods of storing aK-dimensional array allow easy extension only along one dimension. We present a technique of allocating a linear sequence of contiguous storage locations for aK-dimensional extendible array by adjoining blocks of (K–1)-dimensional subarrays. Element access is by determination of the block header location and then the displacement within the block. For cubical and all practical cases of rectangular arrays considered, the storage requirement isO (N) whereN is the array size. The element access cost isO (K) for the 2-step computed access function used.

---

Ein Speicherschema für erweiterbare Felder

Zusammenfassung Konventionelle Methoden der SpeicherungK-dimensionaler Felder lassen eine einfache Erweiterung lediglich entlang einer Dimension zu. Wir beschreiben eine Technik der Zuweisung einer linearen Folge von zusammenhängenden Speicherzellen fürK-dimensional erweiterbare Felder durch Hinzufügen von Blöcken aus (K–1)-dimensionierten Teilfeldern. Der Elementzugriff erfolgt durch Bestimmung des Headers und des Displacements innerhalb des Blockes. Für kubische und alle praktische Fälle rechteckiger Felder ist der SpeicherbedarfO (N) wobeiN die Feldgröße ist. Die Kosten eines Elementzugriffs betragenO (K) für die in zwei Schritten berechnete Zugriffsfunktion.

     

Bestimmung der Automorphismengruppe spezieller Klassen von Graphen

Zusammenfassung In dieser Arbeit wird eine Methode behandelt, die involutorischen Automorphismen von Graphen allein aus den Eigenschaften der Inzidenzmatrix ohne Anwendung von Permutationen aufzustellen. Hat ein Graph die Eigenschaft, daß jeder seiner Punkte mit höchstens einem anderen vertauscht werden kann, so besteht seine Automorphismengruppe aus lauter Involutionen. In diesem Falle erhält man die ganze Automorphismengruppe. Abschließend wird eine ALGOL-Prozedur zur Ermittlung der Involutionen angegeben, wenn für jeden Punkt sein möglicher Bildpunkt bekannt ist.

---

Summary In this article there will be treated a method to get the involutoric automorphisms of a graph without the execution of any permutation. If a graph has the property that each of it's vertices can be permuted with not more than one other vertex, all automorphisms of the graph are involutoric. In that case the result is the whole group of automorphisms. At the end an ALGOL-procedure is given which computes the involutions if for each vertex the possible image is known.

     

Mehrdimensionale Zuordnungsprobleme und Netzwerkflüsse mit vorgegebenen Wertemengen

Zusammenfassung Es wird eine Klasse von mehrdimensionalen Zuordnungsproblemen beschrieben, die in der Praxis häufig auftreten und wesentlich allgemeiner sind als das klassische Zuordnungsproblem. Die Probleme lassen sich auf die Bestimmung zulässiger Netzwerkflüsse mit vorgebenenen Wertemengen zurückführen. Der beschriebene Lösungsalgorithmus beruht auf einem Dekompositionsverfahren.

---

Optimal assignment problems and network flows with given sets of values

Summary A class of optimal assignment problems is defined. These problems often occur in practice and are essentially more general than the classical assignment problem. The problems may be reduced to the task of finding feasible network flows with given sets of values. The described algorithm is based on a decomposition procedure.

     

Über die Herstellung von Höhenkarten und perspektivischen Reliefdarstellungen von Funktionen einer komplexen Veränderlichen mittels elektronischer Rechenanlagen

Zusammenfassung Es wird eine Methode beschrieben, die es ermöglicht, Höhenkarten und perspektivische Reliefdarstellungen von Funktionen einer komplexen Veränderlichen mit Hilfe elektronischer Rechenanlagen automatisch herzustellen. Als Anwendung wird die analytische Fortsetzung der periodischen Lösung derVan der Pol-Gleichung ins Komplexe behandelt. Zur Berechnung der Funktionswerte wurde die Rechenanlage IBM 7090/1410, zur Zeichnung der magnetbandgesteuerte Dataplotter EAI 3440 des Rheinisch-Westfälischen Institutes für Instrumentelle Mathematik in Bonn, benutzt.

---

Summary A method is described which permits the automatic preparation on computers of altitude charts and of perspective reliefs of functions of a complex variable. As an example, the analytic continuation of the periodic solution ofVan Der Pol's equation into the complex domain is treated. For calculating the function data and for carrying out the drawing work, use was made of the computer IBM 7090/1410 and the magnetic tape controlled data plotter EAI 3440 respectively, both at Rheinisch-Westfälisches Institut für Instrumentelle Mathematik in Bonn (Germany).

     

Adaptive control via quasilinearization and differential approximation

Summary Suppose that a system undergoes a process described by a set of differential equations. The equations contain some unknown parameters and not all the initial conditions are known. Observations are made on some of the state variables during the course of the process. We wish to determine the system parameters and initial conditions which lead to best agreement with the observations.Inverse problems of the type sketched, which are important throughout mathematical physics and engineering, are cast in mathematical form as nonlinear multipoint boundary value problems. Then computational solutions via quasilinearization and differential approximation are suggested.

---

Zusammenfassung Angenommen, ein System werde einem Prozeß unterworfen, der durch ein System von Differentialgleichungen beschrieben wird. Die Gleichungen enthalten einige unbekannte Parameter und weiters sind nicht alle Anfangsbedingungen bekannt. Das Verhalten einiger Zustandsvariablen wird während des Prozesses beobachtet. Wir möchten nun die Parameter des Systems und die Anfangsbedingungen bestimmen, die die beste Übereinstimmung mit den Beobachtungen liefern.Dei zu dem skizzierten Typ inversen Probleme, die in der mathematischen Physik und im Ingenieurwesen wichtig sind, werden als nichtlineare Randwertaufgaben mit Bedingungen an mehreren Stellen mathematisch formuliert. Schließlich werden für rechnerische Lösungen Quasilinearisierung und Differentialapproximation vorgeschlagen.

---

---

With 2 Figures

---

This research is sponsored by the United States Air Force under Project RAND-contract No. AF 49 (638)-700.     

Bestimmung minimaler Wege in endlichen,gerichteten, bewerteten Graphen

Zusammenfassung Betrachtet wird das Problem, in einem allgemeinen, endlichen, gerichteten, bewerteten Graphen Wege mit minimaler Bewertung von einem Knotenk ₀ zu den Knoteny einer MengeY zu finden, so daß die Anzahl der benötigten Rechenoperationen möglichst gering ist. Auf dieses Problem können einige weitere Probleme reduziert werden. Es werden einige theoretische Überlegungen sowie kritische Betrachtungen zu den Algorithmen vonMoore undMinty durchgeführt. Verallgemeinerte und modifizierte Fassungen dieser Algorithmen werden sodann beschrieben und erläutert.

---

Summary Considered is the problem to find paths from a nodek ₀ to the nodesy of a setY with minimum evaluation in a general, finite, directed, evaluated graph in such a way that the number of arithmetic operations is as small as possible. Further problems can be reduced to this problem. Some theoretical investigations and critical remarks concerning the algorithms ofMoore andMinty are made. Generalized and modified versions of these algorithms are then described and discussed.

---

---

Diese Arbeit wurde durch einen Bundeszuschuß aus Mitteln des Bundesministeriums für Handel, Gewerbe und Industrie an das Rechenzentrum Graz gefördert.     

Ein Estimationsproblem der linearen Approximationstheorie beim Ausgleich statisticher Meßwerte

Zusammenfassung Die Aufgabe, eine Regressionsfunktion nicht vorgegebener funktionaler Gestalt zu bestimmen, die die Likelihoodfunktion der statistischen Daten zu einem Maximum und ein gegebenes Funktional zu einem Minimum macht, wird als lineares Approximationsproblem formuliert. Für gewisse Statistiken und quadratische Funktionale wird die Existenz und Eindeutigkeit der Lösung gezeigt und die Herleitung der Lösung beschrieben. Für eine reelle Veränderliche und gewisse Funktionale ergeben sich als Lösungen Spline-Polynome, für die ein numerisches Ausgleichsverfahren angegeben wird, das die polynomiale Regression als Spezialfall enthält.

---

Summary The problem, to find a regression curve whose functional form is not a priori given, and which maximizes the likelihood function and minimizes a given functional, will be formulated as a problem of linear approximation theory. For certain statistics and quadratic functionals the existence and uniqueness of the solution is proved, and the solution derived. In case of one real variable and certain functionals spline polynomials are found as solutions. In this case a procedure is given to fit the regressions curve. This procedure is a generalisation of polynomial regression.

---

---

Mit 2 Textabbildungen

---

Diese Veröffentlichung entstand in Zusammenarbeit mit Herrn Prof. Dr.R. Albrecht, Graz, dem ich hierfür sehr zu Dank verpflichtet bin.     

Ein algorithmisches Planaritätskriterium

Zusammenfassung Es wird ein lokales und ein globales Planaritätskriterium für Graphen angegeben. Auf der lokalen Ebenheitsbedingung läßt sich ein Algorithmus aufbauen, mit welchem ein Graph gegebenenfalls Schritt für Schritt in die Ebene abgebildet werden kann.Der Algorithmus beruht auf der Rechnung mit Symbolen aus einer freien, kommutativen, nicht-assozitativen Algebra und auf der algebraischen Auswertung derartiger Formeln. Ein Beispiel zeigt die Anwendung des Algorithmus.

---

Summary A local and a global criterion for a graph to be planar is given. On these criteria, a step-by-step procedure is based for mapping the graph in the plane.This algorithm works by manipulating formulas in a free commutative non associative algebra. An example at the end of the paper illustrates the functioning of the algorithm.

---

---

Mit 6 Textabbildungen.

---

Die Arbeit stellt einen Teil der Habilitationsschrift dar, die der Mathematisch-Naturwissenschaftlichen Fakultät der Freien Universität Berlin von Verfasser vorgelegt wurde.