Failure of Loeb's method for rational L1 approximation

An algorithm for rational L₁ approximation on an interval is obtained by adapting Loeb's weighted minimax algorithm for rational Chebyshev approximation on an interval. Sufficient conditions for the algorithm to fail are given.

---

Versagen der Loebschen Methode für rationelle L₁-Annäherungen

Zusammenfassung Entwickelt wird ein Algorithmus für rationelle L₁-Annäherungen an einem Intervall durch Anpassung des Loebschen gewogenen Minimax-Algorithmus für rationale Chebyshev-Annäherungen an einem Intervall. Hinreichende Bedingungen für das Versagen des Algorithmus werden gegeben.

     

Verallgemeinerung funktionentherotischer Verfahren für Analogrechner auf allgemeinere Funktionentheorien

Zusammenfassung Zur Untersuchung der Abbildungseigenschaften analytischer Funktionen gibt es bekannte Verfahren für einen Analogrechner. Diese Verfahren werden in der vorliegenden Arbeit auf den Fall einer allgemeineren Funktionentheorie übertragen und an Beispielen illustriert.

---

Summary There are well known methods to investigate the mappings-properties of Analytic Functions on Analog Computers. In the present paper these methoextended to a more general Function Theory and illustrated by examples.

---

---

Mit 1 Textabbildung.

---

Auszug aus der von der Fakultät für Allgemeine Wissenschaften der Technischen Hochschule München genehmigten Dissertatin des Dipl-Math.Nikolaos Apostolatos, Institut für Angewandte Matheamtik der TH München, Dir. o. Prof. Dr.J. Heinhold.     

Über die Charakterisierung von Minimallösungen bei nichtlinearen Approximationsproblemen

Zusammenfassung Approximiert man bezüglich eines gewissen Abstandsbegriffes in einem linearen RaumX ein Elementf ausX durch Elemente eines linearen UnterraumesV, so lassen sich für die Elemente ausV, die vonf den kleinsten Abstand haben, Charakterisierungssätze beweisen, die für normierte Räume bekannt sind und sich dort als bedeutsam für Anwendungen erwiesen haben. Es wird nun die Frage untersucht, für welche TeilmengenV vonX die für lineare Unterräume geltenden Charakterisierungssätze auch noch gelten.

---

On the characterization of minimal solutions to nonlinear approximation problems

Summary If, referring to a certain definition of distance in a linear space X, you approximate an elementf ofX by elements of a linear subspaceV, characterization theorems can be found for elements ofV, which have the shortest distance fromf. These theorems of characterization are known for linear normed spaces and have turned out to be of a certain importance for applications. This paper intends to clear the question, to which subsetsV ofX the theorems of characterization for linear subspaces apply as well.

     

Automation of program speed-up on parallel-processor computers

Summary The present paper tries to define automatic procedures for detecting inherent paralellism during the compilation of programs in procedural language for parallel-processor computers. This parallelism should be used on a static and a dynamic basis. During compilation several independent paths are detected, generated and properly identified for parallel execution. Also, a scheme is described for an executive routine in this environment.

---

Zusammenfassung Der vorliegende Beitrag versucht automatische Methoden für die Auffindung innewohnender Gleichzeitigkeit in Programmen während der Übersetzung für Parallel-Rechner abzugrenzen. Solche Gleichzeitigkeit sollte auf statische und auf dynamische Weise verwendet werden. Während der Übersetzung werden mehrere unabhängige Rechenwege erzeugt und für parallele Ausführung entsprechend gekennzeichnet. In diesem Zusammenhang wird ein Schema für ein Kontrollprogramm angegeben.

---

---

With 5 Figures     

Ableitungsfreie Schranken für die numerische Integration

Zusammenfassung Für den Fehler, der bei der numerischen Integration einer holomorphen Funktion entsteht, werden ableitungsfreie Schranken hergeleitet und diskutiert. Gegenüber früheren Ergebnissen ergeben sich zum Teil bessere Abschätzungen.

---

Summary This paper shows the estimation of errors which arise when quadrature rules are applied to analytic functions. We derive error bounds and discuss the results.

     

Ü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.

     

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.

     

Ein Modell desP =N P-problems mit einer positiven Lösung

Zusammenfassung Wir diskutieren die Sprachmittel, die zur Formalisierung des P = N P-Problems in einer naiven Mengenlehre benötigt werden. Die Kategorie der kommutativen, idempotenten Semigruppen verfügt über genügend Struktur, daß diese Formalisierung in ihr vorgenommen werden kann. Sie besitzt also ihr eigenes P = N P-Problem. Für dieses Problem gilt P = N P.

---

A model of the P = N P-problem with a positive solution

Summary We discuss the language necessary to give a formalization of the P = N P-question in a Cantor's style set-theory. The internal structure of the category of idempotent, commutative semigroups is rich enough, to carry out this constructions. Hence this category has its own P = N P-question. The answer to this question is: P = N P.

     

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.

     

An augmenting path method for solving Linear Bottleneck Assignment problems

An efficient method for solving Linear Bottleneck Assignment problems is described. The method starts with a heuristically determined partial assignment. Then shortest augmenting paths are constructed with the aid of a modification of the algorithm of Dijkstra. Comprehensive numerical investigations are reported and discussed. A FORTRAN IV subroutine can be found in the appendix.

---

Ein Lösungsverfahren für lineare Engpaßzuordnungsprobleme mittels erweiternder Wege

Zusammenfassung Ein effizientes Verfahren zur Lösung linearer Engpaßzuordnungsprobleme wird beschrieben. Dabei wird von einer heuristisch bestimmten Teilzuordnung ausgegangen. Anschließend werden kürzeste erweiternde Wege mit Hilfe einer Modifikation des Algorithmus von Dijkstra bestimmt. Ausführliche numerische Untersuchungen sind dargestellt und diskutiert. Eine FORTRAN IV Subroutine findet sich im Anhang.

     

Vier Entscheidbarkeitsprobleme für kontextsensitive Sprachen

Zusammenfassung Die kontextsensitiven Sprachen bilden nicht die allgemeinste Klasse algorithmisch erzeugbarer Sprachen. Dennoch lassen sich vielfältige Probleme (FERMAT) in Entscheidbarkeitsfragen über kontextsensitive Sprachen einbetten. Die hier behandelten Probleme sind sowohl von algebraischem Interesse, als auch für die Umformung von Sprachen durch Homomorphismen und damit für die Analyse wichtig. Leider sind alle gestellten Probleme nicht entscheidbar.

---

Summary The context-sensitive languages do not constitute the total class of languages generated by algorithms. Nevertheless various problems (FERMAT) can be embedded in problems of decidability on context-sensitive grammars. The problems here considered are not only of algebraic interest but treat the transformation of languages by homomorphisms and so concern the simplification of language analysing. Unfortunately the questions examined here are undecidable.

     

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.     

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.     

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 ⁿ.

     

Grundlagen einer Maschinenintervallarithmetik

Zusammenfassung In der vorliegenden Arbeit wird eine in [1] angegebene Intervallarithmetik so erweitert, daß sie auch für Intervallfunktionen die exakten Ergebnisintervalle liefert. Es wird ferner die dieser Intervallarithmetik zugeordnete Maschinenintervallarithmetik angegeben, und es werden Eigenschaften dieser Arithmetik untersucht.

---

Summary In the present paper we give an interval arithmetic, which is an extension of that given in [1]. It is one of the essential features of this new interval arithmetic, that in the case of interval functions we get the exact range of interval values. Further on we give a machine interval arithmetic corresponding to the new interval arithmetic and study properties of these arithmetics.

---

---

Wir danken Herrn Prof.Nickel für zahlreiche Anregungen.     

Reconstructing pictures from projections: On the convergence of the ART algorithm with relaxation

The convergence of the additive and linear ART algorithm with relaxation is proved in a new way and under weaker assumptions on the sequence of the relaation parameters than in earlier works. These algorithms are iterative methods for the reconstruction of digitized pictures from one-dimesional views. A second proof using elementary matrix algebra shows the geometric convergence of the linear ART algorithm with relaxation.

---

Über die Konvergenz des ART-Algorithmus für die Rekonstruktion von Bildern

Zusammenfassung ART-Algorithmen sind iterative Methoden zur Rekonstruktion von digitalen Bildern aus ihren Projektionen. Die Konvergenz des additiven und linearen (nicht restringierten) ART-Algorithmus mit Relaxation wird unter weit schwächeren Voraussetzungen über die Relaxationsparameter als bei bisher bekannten Resultaten bewiesen. Ein anderer Beweis zeigt die geometrisch schnelle Konvergenz des linearen relaxierten ART-Algorithmus.

     

Ü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     

Direkte Verfahren zur Berechnung der Nullstellen von Polynomen

Zusammenfassung Wenn hinreichend genaue Näherungen für die Nullstellen eines Polynoms vorliegen, liefern numerische Iterationsverfahren Folgen von Näherungswerten, für welche die zugehörigen Folgen der Beträge der Funktionswerte monoton fallen. Es wird ein mit Spiralisierung bezeichneter zweidimensionaler Suchprozeß angegeben, mit dem man derartige Folgen für beliebige Ausgangsnäherungen erhält. Auf diese Weise gewinnt man direkte, d. h. für beliebige Näherungen konvergente Verfahren. Die Folgen der Näherungswerte werden durch Extrapolation verbessert. ALGOL-Prozeduren und numerische Ergebnisse für ein direktesNewton-Verfahren sowie für ein direktes Verfahren 3. Ordnung, das derMullerschen Methode verwandt ist, werden angegeben. Die Methoden lassen sich auch zur Berechnung der Nullstellen analytischer Funktionen verwenden.

---

Direct methods for evaluation of zeroes of polynomials

Summary If sufficiently exact approximations for the zeroes of polynomials are present then numerical iterative methods yield sets of approximations for which the corresponding sets of absolute values of the functional values are monotonous decreasing. It is described by a twodimensional searching process, named method of spiral course, how to get such sets for arbitrary starting approaches. In this way we get direct methods, that is to say convergent methods for arbitrary approaches. The sets of approaching values are improved by extrapolation. ALGOL procedures and numerical results are given for a directNewton method and a direct third order method, which has a relationship to theMuller method. The treated methods also can be used for the evaluation of the zeroes of analytical functions.

     

Approximation mit Exponentialsummen

Zusammenfassung Für die Approximation mit Exponentialsummen ist die beste Approximation imTschebyscheffschen Sinne eindeutig, abgesehen von bisher nicht erkannten Ausnahmen. Eindeutigkeit liegt dagegen immer bei der Anpassung mit positiven Exponentialsummen vor. Daß diese Familie eine andere Struktur hat als die bekannten Verallgemeinerungen linearer Funktionenfamilien, zeigt sich am Charakter des Alternantenkriteriums.

---

Summary In this paper we investigate the approximation by sums of exponentials in the sense ofChebyshev. The best approximation is shown to be unique apart from exceptions not previously recognized. However, there is always uniqueness, when only sums of positive exponentials are considered. This family has a structure which is different from that of other generalizations of linear families of functions. This feature is reflected in the criterion on the alternations of the error curve.

---

---

Kernforschungszentrum Karlsruhe, Institut für Neutronenphysik und Reaktortechnik     

Quadraturverfahren mit Fehlerschranken

Zusammenfassung Mit Hilfe einer Fehlerschrankenarithmetik (vgl. [4]) werden Formeln zur Berechnung von Näherungswertenplus Fehlerschranken für bestimmte Integrale angegeben. Im einfachsten Fall werdenkeine weiteren Informationen über den Integranden gefordert (wie etwa Schranken für Ableitungen, etc.). Die Formeln lassen sich für jede Genauigkeitsordnung aufstellen, die Ordnung für den Näherungswert ist i. a. um Eins höher als für die Fehlerschranken. Beispiele zeigen, daß die Schranken sehr scharf sind. Man kann die durch die Schranken vermittelte Information zum vollautomatischen Abbrechen der Quadratur an der günstigsten Stelle benutzen.

---

Summary With the aid of an errorbound arithmetic (see [4]), formulas are given for the computation of approximate valuesplus errorbounds for integrals. In the simplest case,no further information is required about the integrand (e. g. bounds for derivatives, etc.). The formulas can be given for each order of exactitude, the order for the approximate value being, in general, one higher than the order of the errorbounds. Examples show that the errorbounds are generally very sharp. It is possible to use the information given by the errorbounds for the fully automatic ending of the quadrature at the optimal point.

---

---

Mit 9 Textabbildungen