We know that the monic Chebyshev polynomial of degree n, T_n(x), has the least deviation from the origin among all polynomials of degree n. What about the polynomial of degree n that has the least deviation from the origin that also satisfies boundary conditions, continuity at both end points, for example?
The problem can be explained for a particular case as follows:
Suppose that we are interested in approximating a polynomial f of degree >n on [-1,1] by a polynomial p of degree n so that they meet at the endpoints.
Minimize Maximum |f(x)-p(x)| on [-1,1].
Dear Demetris,
Thanks for the link. Unfortunately, it didn't work for me.
Dear Dmitrii
"If you mean value at points, then you can use a classical polynomial interpolation, which will give you exactly that you want."
I am not sure what you mean. If constraints come under the form of n nodes imposed in the approximation interval, then the classical polynomial interpolation will not be the answer to the question. This case is considered in the following reference (in French)
S. Paszkowski, "Sur l'approximation uniforme avec des noeuds." Ann. Polon. Math. 2.1 (1955), 118-135
Dear Abdellah,
Perhaps you should add that the least-deviation property of the monic Chebyshev polynomial holds in the interval [-1; +1]
The following references could be interesting depending on which type of constraints you are considering.
E Kimchi, N Richter-Dyn, "Properties of best approximation with interpolatory and restricted range side conditions", J. Approximation Theory, 15 (1975), 101–115
E Kimchi, N Richter-Dyn, "Best uniform approximation with Hermite-Birkhoff interpolatory side conditions",J. Approximation Theory, 15 (1975), 85–100
Hope this helps.
All polynomials are globally continuous. So this is not the best example of boundary condition... Maybe you think about beig 0 in +1 and -1, or something like this?
Perhaps this work has something to present:
http://www.math.bgu.ac.il/~pakovich/Publications/opz.pdf
The following article may have some interest to followers of this thread:
L.N. Trefethen, Near-circularity of the error curve in complex Chebyshev approximation, J. of Approximation Theory 31, 1981, 344-367
http://ac.els-cdn.com/0021904581901027/1-s2.0-0021904581901027-main.pdf?_tid=41b2df26-2e10-11e4-b618-00000aab0f6b&acdnat=1409160988_8fe46a8a15d0cb82327cfb99307e8615
The approximation problem is nicely characterized geometrically on page 344.
The basic approach in this article is to consider nearby problems with exactly circular error curves.(see Sections 3 and 4). Sample error curves are shown in the attached image, p. 347.
A more recent paper considers a sequence of polynomials as a best approximation:
http://localwww.math.unipd.it/~novati/dati/final_preprints/fpm2.pdf
Dear Demetris,
Thanks for the link. Unfortunately, it didn't work for me.
Dear Dmitrii
"If you mean value at points, then you can use a classical polynomial interpolation, which will give you exactly that you want."
I am not sure what you mean. If constraints come under the form of n nodes imposed in the approximation interval, then the classical polynomial interpolation will not be the answer to the question. This case is considered in the following reference (in French)
S. Paszkowski, "Sur l'approximation uniforme avec des noeuds." Ann. Polon. Math. 2.1 (1955), 118-135
Dear Abdellah,
Perhaps you should add that the least-deviation property of the monic Chebyshev polynomial holds in the interval [-1; +1]
The following references could be interesting depending on which type of constraints you are considering.
E Kimchi, N Richter-Dyn, "Properties of best approximation with interpolatory and restricted range side conditions", J. Approximation Theory, 15 (1975), 101–115
E Kimchi, N Richter-Dyn, "Best uniform approximation with Hermite-Birkhoff interpolatory side conditions",J. Approximation Theory, 15 (1975), 85–100
Hope this helps.
Dear Demitrii,
You are most welcome. I agree that the constraints need to be better specified in the question. Moreover, as already noted by @Mihai, this notion of "continuity at both end points" is not clear.
Visit the following link:
http://authors.library.caltech.edu/25061/5/NumMethChE84-Ch3-BVPforODE-FEM.pdf
Dear @M. A. Zaky sent me his contribution in a private communication that I want to share with you: "You can use this function
f(x)=L[N,x]-L[N+2,x], where L[N,x] is the Legendre polynomials
and that satisfy boundary conditions at -1 and 1
It can satisfy the boundary conditions at the points 0 and 1 using the shifted Legendre polynomials."
Dears @Dmitrii and @Mihai , I did add some more details to the problem that explains the problem.
Dears @Demetris and @James, thank you for the articles and the links; they are very helpful to solve a similar issue for the complex case.
Dear @H.E. Lehtihet, yes indeed, classical Chebyshev polynomials work well on [-1,1], and the shifted Chebyshev can be defined on any other interval [a,b]. Thank you for the papers that discuss an alternation property of polynomials of best uniform approximation to a function ϵC[a, b] having restricted ranges of some of their derivatives. The problem of best uniform approximation to continuous functions by polynomials having restricted ranges and satisfying interpolatory conditions on their derivatives is discussed.
Dear @Dmitrii, thank you for the book L.N. Trefethen: Approximation theory and approximation practice that discusses the issue of polynomials of best approximation.
Dears @Rihab and @Costas, thank you for your kind answers.
Dear @Praveen, thank you for the file at the link:
http://authors.library.caltech.edu/25061/5/NumMethChE84-Ch3-BVPforODE-FEM.pdf
It deals with the numerical techniques outlined in this chapter produce approximate solutions that, in contrast to those produced by finite difference methods, are continuous over the interval. The approximate solutions are piecewise polynomials, thus qualifying the techniques to be classified as finite element methods.
Dear @M. A. Zaky, thank you for your contribution to use the Legendre polynomials.
May be you can use Legendre Poly or Jacobi , and use some interpolation points as much as your degree of poly , and certainly matching endpoints to obtain a linear system and then solve. If you are lucky, then your system may have some special features making it easy to solve.
The following picture shows, for various polynomials p of degree n = 3, the absolute deviation |f(x) - p(x)| over the interval [-1; +1], where f is the exponential function.
The unconstrained minimax solution (red) exhibits its well-known equi-oscillatory behavior, reaching its maximum (~ 5.53x10-3) on n + 2 points. The classical interpolation on the Chebyshev nodes is given (in yellow) for comparison.
The constrained minimax solution (green) is, of course, also equi-oscillating. However, because of the additional constraints imposed at the boundaries, the maximum deviation is now higher (~ 7.60x10-3) and is now reached on only n points. The classical interpolation on equidistant abscissa is given (in blue) for comparison.
The best uniform fit is like the min/max problem, which is solved by an exact fit at some subset of the data. You don't have to try every possible combination, which can be enormous. Just include the end points in the selection every time.
- Badges
- Science topic