best way to approximating a non-smooth function using polynomials...
Luna Moon
Suppose I am looking at a non-smooth function which is
max(x - c, 0),
is there a way to approximate it by polynomials of x or other
functionals of x?
Of course, Taylor expansion may have some trouble here...
But are there ways out of this swamp from math and physics
literature?
Thanks!
robert bristow-johnson
>
> Suppose I am looking at a non-smooth function which is
>
>
> is there a way to approximate it by polynomials of x or other
>
> Of course, Taylor expansion may have some trouble here...
>
> But are there ways out of this swamp from math and physics
> literature?
i presume that "c" is a specified (or otherwise known) constant.
right?
also, you want to approximate it within a specified domain:
xmin <= x <= xmax ,
right? do you know the xmin and xmax?
also, since you included the possibility of "other" functions of x
(non-polynomials), and since your f(x) is a piecewise-linear function,
there is a function that asymptotically approximates your piecewise
linear function.
f(x) = max(x-c, 0)
we approximate it with
g(x) = (1/alpha)*log(1 + exp(alpha*(x-c)))
alpha > 0 and the larger alpha is, the tighter this smooth function
approximates your originally specified one. a tighter corner when x
is close to c. (BTW, all of this was motivated by the piecewise-
linear "Bode plots" we used to do back in school. just in case
someone wonders where it came from.)
if, for computational reasons, you want g(x) to be a polynomial, then
you have to fit it to f(x) (over the domain, xmin <= x <= xmax) and
then you have to define how you measure the goodness of fit. if the
goodness of fit is measured in terms of mean square error, then there
is a straight-forward way to get the polynomial coefficients ("least
square fit"). if the goodness of fit is measured in terms of the
maximum error, then you have to use what is called the Remes Exchange
Algorithm (with the basis functions defined to be powers of x). i
have MATLAB/Octave code for that if you want.
r b-j
Dave L. Renfro
I don't know if this will help, but since
max{x,y} = (1/2)(x + y + |x-y|),
your function is continuous and hence it can be uniformly
approximated by polynomials on any compact set (such as
a closed and bounded interval), and there are specific
methods for obtaining such polynomials (e.g. by using
Bernstein polynomials -- see the URL just below).
http://en.wikipedia.org/wiki/Bernstein_polynomial
Also, if x and y are non-negative, then max{x,y} is
equal to the limit as n --> infinity of (x^n + y^n)^(1/n),
but I don't know if this will be of use.
Dave L. Renfro
Dave
Questions:
1. Why do you want to do this? Is it an exercise, or do you have a use
for it?
2. Is the approximation on a finite interval, a <= x <= b, where a < c
< b?
3. What other functions are you willing to use?
Dave
Vladimir Vassilevsky
Luna Moon wrote:
You can invent any sort of parametric limit approximation, kinda:
(c - x)
F(x) = ------------- + (x - c), where p -> infinity
1 + (x/c)^p
BUT, what are you trying to do, really? Trying to estimate the nonlinear
effects produced by a hard knee?
Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com
Jon Slaughter
"Luna Moon" <lunamo...@gmail.com> wrote in message
news:9c813742-e132-4ecc...@d36g2000prf.googlegroups.com...
> Hi all,
>
> Suppose I am looking at a non-smooth function which is
>
> max(x - c, 0),
i.e., when x < c then then x - c < 0 and max(x - c, 0) = 0
when x > c then x - c > 0 and max(x - c, 0) = x - c
hence we simply have a ramp at x = c
f_c(x) = 0 if x < c
x - c else
= (x - c)*Heaviside(x - c)
> is there a way to approximate it by polynomials of x or other
> functionals of x?
>
functionals?
> Of course, Taylor expansion may have some trouble here...
>
> But are there ways out of this swamp from math and physics
> literature?
>
I'm not sure what your getting at. The ramp function given is a perfectly
good function. If you want to approximate it with more complex things then
that is your right.
Luna Moon
Yeah, I am trying to look at my computational problem from different
perspectives... Expanding and approximating it will add more
perspectives. Yes, it's in a finite interval, a<=x<=b, and a<c<b. I am
willing to explore all possible functionals...
Luna Moon
Yeah, x is in a finite interval, let's say (0, 1000). c is a constant
in this interval also.
So your method adds an additional parameter, alpha?
Yes, that's one possible thought, any other such forms?
I will still expand those approximation forms further out to get a
series expansion...
Luna Moon
wrote:
> "Luna Moon" <lunamoonm...@gmail.com> wrote in message
Yep, one possible direction of my question can be formulated as:
Give an approximation of the ramp function, so that I could further
expand it out into series form...
My end goal is a series expansion... but it's probably hard to get a
direct series expansion from the ramp function itself. Maybe the first
step is find an approximation to the ramp function itself, then do a
series expansion on top of that...
This is one possible approach for attacking the overall problem. If we
adopt this approach, then there are two approximation step here.
What's the best way to choose the best overall approximation when the
two approximation steps are combined?
Luna Moon
hmm, I don't know how to convert my function into Bernstein
polynomial. And how does it compare with a Taylor polynomial
expansion?
robert bristow-johnson
> On Feb 13, 10:09 am, robert bristow-johnson
>
> <r...@audioimagination.com> wrote:
>
> > f(x) = max(x-c, 0)
>
> > we approximate it with
>
> > g(x) = (1/alpha)*log(1 + exp(alpha*(x-c)))
>
>
yes, it represents how sharp the corner of g(x) is. the corner of
your piecewise linear function, f(x), is infinitely sharp. as alpha>0
gets larger and larger, the more closely g(x) approximates f(x); the
sharper the corner of g(x) gets.
your corner is at x=c and there f(x)=0 and g(x) = log(2)/alpha .
> Yes, that's one possible thought, any other such forms?
possibly, but not likely as pretty.
r b-j
Jon Slaughter
-------
I'm not sure why you want to expand it but it doesn't have a taylor. A
taylor series is sum(f^(k)(c)/k!*(x - c)^k)
f^k(c) = 0 for all x <= c so your taylor series would be 0.
A taylor series the function must be continuous.
Since it is not periodic it doesn't have a fourier series.
I think you gotta make it clear what you want and how you want to
approximate it. If you just want a sequence of functions such that the limit
is the function under question then there are an infinite number of them..
(x-c)/(1 + e^(-k(x - c)))
Is one such sequence. It is continuous and the sequence approaches f
uniformly. (the 1/(1 + e^(-k(x-c))) is the unit step or heaviside function
approximation)
Dave
If you are willing to consider a least squares polynomial fit, then
the Legendre polynomials shifted to the interval [a, b] by the afine
transformation
x --> 2 (x - a) / (b - a) - 1
form an orthogonal basis for L_2[a, b]. Thus, your function can be
written as an expansion in Legendre polynomials P_n(x)
f(x) = sum_{n=0}^infinity a_n * P_n(2 (x - a) / (b - a) - 1).
If the sum is truncated to sum_{n=0}^N, then the result is the least
squares fit to f by polynomials of degree N. The a_n are given by the
integrals
a_n = (b - a)/(2n + 1) * integral_a^b f(x) * P_n(2 (x - a) / (b - a) -
1) dx
= (b - a)/(2n + 1) * integral_c^b (x - c) * P_n(2 (x - a) / (b -
a) - 1) dx.
These integrals can be evaluated exactly, to determine any number of
coefficients of the sum.
Dave
W^3
<9c813742-e132-4ecc...@d36g2000prf.googlegroups.com>,
Luna Moon <lunamo...@gmail.com> wrote:
Take c = 0 for convenience and call your function f. On [-Pi, Pi] f =
0 to the left of 0, = x to the right. The Fourier series of f on this
interval is easy to compute, and it will converge uniformly to f on
[-Pi + eps, Pi - eps] for all small eps > 0.
Axel Vogt
I bet: it is for integrating against a density and the range
is, where the density 'lives'.
Justintruth
Its a function and it matches exactly.
robert bristow-johnson
> Why can't you just use "If x>=c, y=x-c else y=0".
>
> Its a function and it matches exactly.
i know that in audio and music synthesis, you might want to have the
general effect of the piece-wise linear function; let's say that you
want to subtract the output of this function from the input to
(virtually) hard-limit it. sure you could just hard clip it at c
(which is just like subtracting the OP's function), but that generates
harmonics up to infinity. at least potentially. so maybe instead of
subtracting the original f(x), he subtracts g(x) which is an Nth-order
polynomial approximation. that generates frequency components up to a
finite ceiling which is N times higher.
or, alternately, if for some reason that you know the input signal is
bandlimited to about Nyquist/N, you can use this approximation instead
of the exact function and know that you don't have any foldover or
aliasing.
r b-j
Martin Eisenberg
> max(x - c, 0)
Another limit form, with k -> 0:
g(x+c) = 1/2 (x + sqrt(k^2 + x^2))
= k/2 exp(arcsinh(x/k))
Martin
--
Dare to think!
--Paracelsus
Martin Eisenberg
>> > max(x - c, 0)
> Give an approximation of the ramp function, so that I could
> further expand it out into series form...
>
> My end goal is a series expansion... but it's probably hard to
> get a direct series expansion from the ramp function itself.
> Maybe the first step is find an approximation to the ramp
> function itself, then do a series expansion on top of that...
>
> This is one possible approach for attacking the overall problem.
> If we adopt this approach, then there are two approximation step
> here. What's the best way to choose the best overall
> approximation when the two approximation steps are combined?
It obviously depends on how the result is used. Why do you want to
end up with a series expansion; so that you have something to
truncate, or to enable further analytic treatment? In the latter case
any of the polynomial expansions is as good as the next, although
you may find some particular basis easiest to grok. Meanwhile, in
analytic work with a limit form, you could look at how the terms of
your second series expansion scale with the kink parameter and select
the form with tamest scaling -- this will be beneficial even when you
don't truncate the series.
In case you do mean to truncate the series for calculation, the same
comment applies: look at the truncation error's growth order in the
kink parameter of different forms. But I'd hazard a guess that in
this case, a direct polynomial expansion is preferable because its
behavior under truncation is designed in and easy to understand.
Which error measure/basis set is for you again depends on context.
There is also the question of negative values in the approximation.
Even if the next step in your overall process swallows negative
numbers, are the results still meaningful?
Martin
--
Yes, I'm reinventing the wheel. Others' have sharp ridges.
tadchem
The art of numerical approximation is complicated.
You must consider the range over which the function needs to be
approximated. If you are only interested in values of x>c, then a
straight line will do nicely). For x<c, the constant valu 0 is all
you need.
If you are interested in the inflection point arounc x = c, thin there
are more things to consider.
What KIND of function do you want to use? The options here are almost
unlimited. Poluynomials are OK for interpolation in soime cases, but
treacherous for extrapolation. Fourier series are excellent in
modelling periodic or noisy signals, but I don't think this is the
case with your problem. Orthogonal polynomials are often discussed in
Numerical Analysis classes, but thet are far from trivial or obvious.
My suggestion would be a rational expression - a ratio between two
functions F(x) and G(x) tailored such that it becomes asymptotic to
the the requirements. In your case, this means that for x < c, F(x)/G
(x) approaches 0, and for x>c, F(x)/G(x) approaches x-c.
Let me build a simple example using exponential functions for your
problem:
F(x) = A*exp(x-c) + B*exp(c-x)
G(x) = C*exp(x-c) + D*exp(c-x)
with A, B, C, and D to be determined.
For x>>c, the first term of each will dominate, so F(x)/G(x) ~= A/C
Similarly, for x<<c, F(x)/G(x) ~= B/D
So we can set B = 0 to approach the asymptote as x << c, and A = (x-c)
to approach the asymptote as x >> c.
Then with c = d = 1, we have an approximation.
F(x) = (x-c)*exp(x-c)
G(x) = exp(x-c) + exp(c-x)
and f(x) ~= F(x)/G(x) = (x-c)*exp(x-c) / [exp(x-c) + exp(c-x)]
If you wish you may simplify this to
f(x) ~= (x-c) / {1 + exp[2*(c-x)]}
How much precision do you need is another question. The more you need
the more complex the equation required to model the data. In this
case, the precision can be improved by simple rescaling.
BTW: Your function seems like a response curve for an electronic
component such as a rectifier. True?
Tom Davidson
Richmond, VA
iwannafly
Thanks Tom. I did a plot of your function. The fit seems to be very
bad... is there a parameter to control the goodness-of-fit? Thanks
again!
hagman
Series expansion describes local behaviour.
Away from c, the local behaviour is just that of a linear function, so
no
need to investigate any series.
At c itself, it is essentially like |x| near 0, expansions here
are not very useful.
here