best polynomial approximation

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

best polynomial approximation

Patrizio Frederic
Dear R-users,
I learned today that there exists an interesting topic in numerical
analysis names "best polynomial approximation" (BSA). Given a function
f  the BSA of degree k, say pk, is the polynomial such that

pk=arginf sup(|f-pk|)

Although given some regularity condition of f, pk is unique, pk IS NOT
calculated with least square. A quick google tour show a rich field of
research and many algorithms proposed for computing such a task.

I was wondered if some of you knows about some R implementations
(packages) for computing BSA.

Many thanks in advance,

Patrizio

as usual I apologize for my fragmented English

--
+-------------------------------------------------
| Patrizio Frederic, PhD
| Assistant Professor,
| Department of Economics,
| University of Modena and Reggio Emilia,
| Via Berengario 51,
| 41100 Modena, Italy
|
| tel:  +39 059 205 6727
| fax:  +39 059 205 6947
| mail: [hidden email]
+-------------------------------------------------

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: best polynomial approximation

Ravi Varadhan
Hi,

My understanding is that Chebyshev polynomials solve the minimax
approximation problem.  If this correct, what you need is an algorithm to
compute Chebyshev polynomial approximation. I have written an R function to
do this.  See the attached code that contains the function and an example.

Is this helpful?

I am not sure if there are better algorithms in some R packages.

Ravi.

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On
Behalf Of Patrizio Frederic
Sent: Monday, May 17, 2010 5:53 PM
To: [hidden email]
Subject: [R] best polynomial approximation

Dear R-users,
I learned today that there exists an interesting topic in numerical
analysis names "best polynomial approximation" (BSA). Given a function
f  the BSA of degree k, say pk, is the polynomial such that

pk=arginf sup(|f-pk|)

Although given some regularity condition of f, pk is unique, pk IS NOT
calculated with least square. A quick google tour show a rich field of
research and many algorithms proposed for computing such a task.

I was wondered if some of you knows about some R implementations
(packages) for computing BSA.

Many thanks in advance,

Patrizio

as usual I apologize for my fragmented English

--
+-------------------------------------------------
| Patrizio Frederic, PhD
| Assistant Professor,
| Department of Economics,
| University of Modena and Reggio Emilia,
| Via Berengario 51,
| 41100 Modena, Italy
|
| tel:  +39 059 205 6727
| fax:  +39 059 205 6947
| mail: [hidden email]
+-------------------------------------------------

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: best polynomial approximation

Hans W Borchers
In reply to this post by Patrizio Frederic
I guess you may be looking for the Remez algorithm. AFAIK there is no implementation in one of the R packages. You can find FORTRAN code in the Collected Algorithms of the ACM (no. 604) which probably could be called from R.

There appears to exist a discrete, equi-distant(?) version as function 'remez' in the signal package, if that is of any help to you. I have never used it.

Regards,  Hans Werner

P.S.: The Chebyshev polynomials do not compute the "best polynomial approximation", but they provide a nice way to estimate the maximal distance to this best approximating polynomial.


Patrizio Frederic wrote
Dear R-users,
I learned today that there exists an interesting topic in numerical
analysis names "best polynomial approximation" (BSA). Given a function
f  the BSA of degree k, say pk, is the polynomial such that

pk=arginf sup(|f-pk|)

Although given some regularity condition of f, pk is unique, pk IS NOT
calculated with least square. A quick google tour show a rich field of
research and many algorithms proposed for computing such a task.

I was wondered if some of you knows about some R implementations
(packages) for computing BSA.

Many thanks in advance,

Patrizio

as usual I apologize for my fragmented English

--
+-------------------------------------------------
| Patrizio Frederic, PhD
| Assistant Professor,
| Department of Economics,
| University of Modena and Reggio Emilia,
| Via Berengario 51,
| 41100 Modena, Italy
|
| tel:  +39 059 205 6727
| fax:  +39 059 205 6947
| mail: patrizio.frederic@unimore.it
+-------------------------------------------------

______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: best polynomial approximation

Patrizio Frederic
Dear colleagues,
thank you so much for your help.
Hans, I think the Remez algorithm is what I need. I will brush up on
fortran language.
Ravi, thanks anyway, I appreciated.

All the best,

Patrizio



On Tue, May 18, 2010 at 12:10 PM, Hans W Borchers
<[hidden email]> wrote:

>
> I guess you may be looking for the Remez algorithm. AFAIK there is no
> implementation in one of the R packages. You can find FORTRAN code in the
> Collected Algorithms of the ACM (no. 604) which probably could be called
> from R.
>
> There appears to exist a discrete, equi-distant(?) version as function
> 'remez' in the signal package, if that is of any help to you. I have never
> used it.
>
> Regards,  Hans Werner
>
> P.S.: The Chebyshev polynomials do not compute the "best polynomial
> approximation", but they provide a nice way to estimate the maximal distance
> to this best approximating polynomial.
>
>
>
> Patrizio Frederic wrote:
>>
>> Dear R-users,
>> I learned today that there exists an interesting topic in numerical
>> analysis names "best polynomial approximation" (BSA). Given a function
>> f  the BSA of degree k, say pk, is the polynomial such that
>>
>> pk=arginf sup(|f-pk|)
>>
>> Although given some regularity condition of f, pk is unique, pk IS NOT
>> calculated with least square. A quick google tour show a rich field of
>> research and many algorithms proposed for computing such a task.
>>
>> I was wondered if some of you knows about some R implementations
>> (packages) for computing BSA.
>>
>> Many thanks in advance,
>>
>> Patrizio
>>
>> as usual I apologize for my fragmented English
>>
>> --
>> +-------------------------------------------------
>> | Patrizio Frederic, PhD
>> | Assistant Professor,
>> | Department of Economics,
>> | University of Modena and Reggio Emilia,
>> | Via Berengario 51,
>> | 41100 Modena, Italy
>> |
>> | tel:  +39 059 205 6727
>> | fax:  +39 059 205 6947
>> | mail: [hidden email]
>> +-------------------------------------------------
>>
>> ______________________________________________
>> [hidden email] mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-help
>> PLEASE do read the posting guide
>> http://www.R-project.org/posting-guide.html
>> and provide commented, minimal, self-contained, reproducible code.
>>
>>
> --
> View this message in context: http://r.789695.n4.nabble.com/best-polynomial-approximation-tp2220439p2221042.html
> Sent from the R help mailing list archive at Nabble.com.
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>



--
+-------------------------------------------------
| Patrizio Frederic, PhD
| Assistant Professor,
| Department of Economics,
| University of Modena and Reggio Emilia,
| Via Berengario 51,
| 41100 Modena, Italy
|
| tel:  +39 059 205 6727
| fax:  +39 059 205 6947
| mail: [hidden email]
+-------------------------------------------------

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.