Namespaces
Variants
Actions

Difference between revisions of "Diliberto-Straus algorithm"

From Encyclopedia of Mathematics
Jump to: navigation, search
 
Line 22: Line 22:
 
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 _{\ell} ( S ) \otimes C ( T )$. Here, $\pi _ { k } ( T )$ is the subspace of $C ( T )$ consisting of all polynomials of degree at most $k$, and $\pi_{\ell}(S)$ 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 [[#References|[a3]]], who showed that convergence cannot be guaranteed. In fact, if $k , \ell \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_{\ell}( S ) \otimes C ( T ) )$.
 
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 _{\ell} ( S ) \otimes C ( T )$. Here, $\pi _ { k } ( T )$ is the subspace of $C ( T )$ consisting of all polynomials of degree at most $k$, and $\pi_{\ell}(S)$ 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 [[#References|[a3]]], who showed that convergence cannot be guaranteed. In fact, if $k , \ell \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_{\ell}( 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 [[#References|[a4]]], [[#References|[a5]]].
+
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 [[#References|[a4]]], [[#References|[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 [[#References|[a7]]].
 
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 [[#References|[a7]]].
  
 
====References====
 
====References====
<table><tr><td valign="top">[a1]</td> <td valign="top">  G. Aumann,  "Uber approximative nomographie II"  ''Bayer. Akad. Math. Natur. Kl. Sitzungsber.''  (1959)  pp. 103–109</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  N. Dyn,  "A straightforward generalization of Diliberto and Straus' algorithm does not work"  ''J. Approx. Th.'' , '''30''' :  4  (1980)  pp. 247–250</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  W.A. Light,  "The Diliberto–Straus algorithm in $L _ { 1 } ( X \times Y )$"  ''J. Approx. Th.'' , '''38''' :  1  (1983)  pp. 1–8</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  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</td></tr></table>
+
<table>
 +
<tr><td valign="top">[a1]</td> <td valign="top">  G. Aumann,  "Uber approximative nomographie II"  ''Bayer. Akad. Math. Natur. Kl. Sitzungsber.''  (1959)  pp. 103–109</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  N. Dyn,  "A straightforward generalization of Diliberto and Straus' algorithm does not work"  ''J. Approx. Th.'' , '''30''' :  4  (1980)  pp. 247–250</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  W.A. Light,  "The Diliberto–Straus algorithm in $L _ { 1 } ( X \times Y )$"  ''J. Approx. Th.'' , '''38''' :  1  (1983)  pp. 1–8</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  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</td></tr>
 +
</table>

Latest revision as of 07:35, 8 February 2024

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 _{\ell} ( S ) \otimes C ( T )$. Here, $\pi _ { k } ( T )$ is the subspace of $C ( T )$ consisting of all polynomials of degree at most $k$, and $\pi_{\ell}(S)$ 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 , \ell \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_{\ell}( 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=55400
This article was adapted from an original article by W. Light (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article