Namespaces
Variants
Actions

Diliberto-Straus algorithm

From Encyclopedia of Mathematics
Revision as of 17:47, 1 July 2020 by Maximilian Janisch (talk | contribs) (Automatically changed introduction)
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

An algorithm first proposed in 1951 by S.P. Diliberto and E.G. Straus [a2]. It is concerned with the problem of finding a best approximation to $f \in C ( S \times T )$ from the subspace $C ( S ) + C ( T )$. In the original paper, $S$ and $T$ were closed, bounded intervals in $\mathbf{R}$, but there is no difficulty in thinking of them as compact Hausdorff spaces, and then giving $C ( S \times T )$ the usual supremum norm (cf. also Approximation theory). The subspace $C ( S ) + C ( T )$ might be more properly written as $C ( S ) \otimes \pi _ { 0 } ( T ) + \pi _ { 0 } ( S ) \otimes C ( T )$, where $\pi_{ 0} ( S )$ is the subspace of $C ( S )$ consisting of functions that are constant on $S$. For $f \in C ( S \times T )$, one defines

\begin{equation*} ( \mathcal{M} _ { s } f ) ( t ) = \frac { 1 } { 2 } \operatorname { sup } _ { s } f ( s , t ) + \frac { 1 } { 2 } \operatorname { inf } _ { s } f ( s , t ) \end{equation*}

and

\begin{equation*} ( M _ { t } f ) ( s ) = \frac { 1 } { 2 } \operatorname { sup } _ { t } f ( s , t ) + \frac { 1 } { 2 } \operatorname { inf } _ { t } f ( s , t ). \end{equation*}

The algorithm is then given by $f _ { 1 } = f$, $f _ { 2 n } = f _ { 2 n - 1 } - g _ { n }$ and $f _ { 2 n + 1 } = f _ { 2 n } - h _ { n }$, where $g _ { n } = \mathcal{M} _ { t }\, f _ { 2 n - 1}$ and $h _ { n } = \mathcal{M} _ { s }\, f _ { 2n }$.

Diliberto and Straus showed that $\{ f _ { n } \}$ is an equicontinuous family of functions (cf. also Equicontinuity) and that $\| f _ { n } \| \downarrow \text { dist } ( f , C ( S ) + C ( T ) )$. These two facts may be used to deduce, via the Ascoli theorem, that the sequence $\{ f _ { n } \}$ has cluster points (cf. also Cluster set), and that any such cluster point $f ^ { * }$ has the property that $f ^ { * } - f$ is a closest point to $f$ from $C ( S ) + C ( T )$. These results are interesting, because they establish that every $f \in C ( S \times T )$ has a best approximation in the infinite-dimensional subspace $C ( S ) + C ( T )$. Diliberto and Straus could not establish that the sequence $\{ f _ { n } \}$ is convergent. However, they came intriguingly near to such a proof when they apparently verified that in the algorithm the incremental functions $g _ { n }$ and $h_{n}$ satisfy $\| g _ { n } \| \rightarrow 0$ and $\| h _ { n } \| \rightarrow 0$ as $n \rightarrow \infty$. Unfortunately, a referee demanded that the paper be shortened prior to publication, so the sequence of lemmas needed to establish this result appears without proof. Up till now (1998), no-one has been able to reproduce the series of arguments needed to support some of these lemmas. However, later work by G. Aumann [a1] established that $\| g _ { n } \| \rightarrow 0$ and $\| h _ { n } \| \rightarrow 0$ as $n \rightarrow \infty$ independently of the methods of Diliberto and Straus. Armed with this knowledge, Aumann was able to prove that the Diliberto–Straus algorithm converges. A relatively simple proof of the convergence of the algorithm, which contains Aumann's result on $\| g _ { n } \|$ and $\| h_n \|$, can be found in [a6].

Generalizations.

There are two natural generalizations of the Diliberto–Straus algorithm. First, one can continue working in the space $C ( S \times T )$ but increase the complexity of the subspace from $C ( S ) \otimes \pi _ { 0 } ( T ) + \pi _ { 0 } ( S ) \otimes C ( T )$ to $C ( S ) \otimes \pi _ { k } ( T ) + \pi _{\text{l}} ( S ) \otimes C ( T )$. Here, $\pi _ { k } ( T )$ is the subspace of $C ( T )$ consisting of all polynomials of degree at most $k$, and has a similar definition. One has to notice now that the operator ${\cal M} _ { s }$ as defined above has the property that, for each $t \in T$, the number $( \mathcal{M} _ { s } f ) ( t )$ is the best approximation to $f (\, \cdot\, , t )$ from $\pi_{ 0} ( S )$. In the present scenario, the correct generalization is to take the mapping $s \mapsto ( \mathcal{M} _ { s } f ) ( t )$ to be the polynomial of degree $k$ which is the best approximation to $f (\, \cdot\, , t )$ from $\pi _ { k } ( S )$. One can then examine the convergence of the algorithm as before. This was done by N. Dyn [a3], who showed that convergence cannot be guaranteed. In fact, if $k , \text{l} \geq 1$, then there exists a function $f \in C ( S \times T )$ such that the algorithm is stationary, that is, $f _ { n } = f$ for all $n \geq 1$, but $\| f \| \neq \operatorname { dist } ( f , C ( S ) \otimes \pi _ { k } ( T ) + \pi_{\text{l}}( S ) \otimes C ( T ) )$.

Another very natural generalization is to consider the algorithm in different spaces. For example, one could examine the behaviour of the analogous algorithm in $L _ { p } ( S \times T )$, with the subspace $L _ { p } ( S ) + L _ { p } ( T )$, where $1 \leq p \leq \infty$. In the case $p = 2$, the algorithm takes place in a Hilbert space, and becomes the alternating algorithm of von Neumann. Because of the uniform convexity of $L _ { p } ( S \times T )$ for $1 < p < \infty$, the analysis of the algorithm can be carried out in considerable generality. The case $p = 1$ is more delicate. As with the case studied by Dyn, there exist functions $f \in L _ { 1 } ( S \times T )$ for which the algorithm is stationary, but $\| f \| \neq \operatorname { dist } ( f , L _ { 1 } ( S ) + L _ { 1 } ( T ) )$. However, a class of functions $\mathcal F \subset L _ { 1 } ( S \times T )$ can be identified on which the algorithm can be shown to converge. When working within this set of functions, the task of verifying that the incremental functions satisfy that $\| g _ { n } \|$ and $\| h_n \|$ tend to $0$ is actually easier than the original problem tackled by Aumann. These results can be found in [a4], [a5].

Finally, it was the intention of Diliberto and Straus to consider approximation of multivariate functions by sums of univariate functions, and their paper gives a number of such results. Other generalizations in $L _ { 1 } ( S \times T )$ are given in [a7].

References

[a1] G. Aumann, "Uber approximative nomographie II" Bayer. Akad. Math. Natur. Kl. Sitzungsber. (1959) pp. 103–109
[a2] S.P. Diliberto, E.G. Straus, "On the approximation of a function of several variables by the sum of functions of fewer variables" Pacific J. Math. , 1 (1951) pp. 195–210
[a3] N. Dyn, "A straightforward generalization of Diliberto and Straus' algorithm does not work" J. Approx. Th. , 30 : 4 (1980) pp. 247–250
[a4] W.A. Light, "Convergence of the Diliberto–Straus algorithm in $L _ { 1 } ( X \times Y )$" Numer. Funct. Anal. Optim. , 3 : 2 (1981) pp. 137–146
[a5] W.A. Light, "The Diliberto–Straus algorithm in $L _ { 1 } ( X \times Y )$" J. Approx. Th. , 38 : 1 (1983) pp. 1–8
[a6] W.A. Light, E.W. Cheney, "On the approximation of a bivariate function by the sum of univariate functions" J. Approx. Th. , 29 : 4 (1980) pp. 305–322
[a7] W.A. Light, S.M. Holland, "The $L_1$-version of the Diliberto–Straus algorithm in $C ( T \times S )$" Proc. Edinburgh Math. Soc. , 27 (1984) pp. 31–45
How to Cite This Entry:
Diliberto-Straus algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Diliberto-Straus_algorithm&oldid=50840
This article was adapted from an original article by W. Light (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article