Prev: Set a selection of a uibutton group element (Changing users choice)
Next: USB & FTDI & Compiler
From: Jim Rockford on 13 Aug 2010 19:20
What I have is a function f(N) that accepts integer arguments only (it
happens to be monotonic, but that's not particularly important). What
I'd like to do is find an integer k such that f(k) and f(k+1) have
opposite signs. Meaning, an actual root of the function f(N),
pretending N is real, lies somewhere between the successive integers k
and k+1. Also, I will note that using "fzero" is out of the question,
as my function f(N) simply does not accept non-integer values.

SUMMARY
I need the integer k such that f(k)*f(k+1) < 0

Is there some sort of bracketing algorithm in Matlab to do this?

I know this can be done in a stupid way by calculating the function
for a large range of integers and using "find" or something like that,
but I'd like something that converges faster.

Thanks,
Jim
From: Walter Roberson on 13 Aug 2010 19:35
Jim Rockford wrote:
> What I have is a function f(N) that accepts integer arguments only (it
> happens to be monotonic, but that's not particularly important).

It is important: it allows you to know that if the sign is the same on two
ends of an interval, then it is not because the sign changed twice on the
interval.

> What
> I'd like to do is find an integer k such that f(k) and f(k+1) have
> opposite signs. Meaning, an actual root of the function f(N),
> pretending N is real, lies somewhere between the successive integers k
> and k+1.

You can use a bisection method, also known as a binary search. The time
required would be proportional to log2 of the search range.
From: Ross W on 13 Aug 2010 19:36
Jim Rockford <jim.rockford1(a)gmail.com> wrote in message <7f595b8e-b1e1-43bc-a03b-e037f21c754b(a)l20g2000yqm.googlegroups.com>...
> What I have is a function f(N) that accepts integer arguments only (it
> happens to be monotonic, but that's not particularly important). What
> I'd like to do is find an integer k such that f(k) and f(k+1) have
> opposite signs. Meaning, an actual root of the function f(N),
> pretending N is real, lies somewhere between the successive integers k
> and k+1. Also, I will note that using "fzero" is out of the question,
> as my function f(N) simply does not accept non-integer values.
>
> SUMMARY
> I need the integer k such that f(k)*f(k+1) < 0
>
> Is there some sort of bracketing algorithm in Matlab to do this?
>
> I know this can be done in a stupid way by calculating the function
> for a large range of integers and using "find" or something like that,
> but I'd like something that converges faster.
>
> Thanks,
> Jim

Hi

Can you write a wrapper around f(N) which does accept non-integer values?

function val=fwrap(x);
val=f(round(x));
end

and now use fzero on fwrap, with the tolerance on x set so that when x is changing by less than 0.5 you stop?

Ross
From: James Tursa on 13 Aug 2010 19:37
Jim Rockford <jim.rockford1(a)gmail.com> wrote in message <7f595b8e-b1e1-43bc-a03b-e037f21c754b(a)l20g2000yqm.googlegroups.com>...
> What I have is a function f(N) that accepts integer arguments only (it
> happens to be monotonic, but that's not particularly important). What
> I'd like to do is find an integer k such that f(k) and f(k+1) have
> opposite signs. Meaning, an actual root of the function f(N),
> pretending N is real, lies somewhere between the successive integers k
> and k+1. Also, I will note that using "fzero" is out of the question,
> as my function f(N) simply does not accept non-integer values.
>
> SUMMARY
> I need the integer k such that f(k)*f(k+1) < 0
>
> Is there some sort of bracketing algorithm in Matlab to do this?
>
> I know this can be done in a stupid way by calculating the function
> for a large range of integers and using "find" or something like that,
> but I'd like something that converges faster.

Why don't you write a wrapper function that accepts a double input, say x, and internally calls f(floor(x)) and f(ceil(x)) and returns an interpolated result. Then find the root of that wrapper function.

James Tursa
From: John D'Errico on 13 Aug 2010 19:52
Jim Rockford <jim.rockford1(a)gmail.com> wrote in message <7f595b8e-b1e1-43bc-a03b-e037f21c754b(a)l20g2000yqm.googlegroups.com>...
> What I have is a function f(N) that accepts integer arguments only (it
> happens to be monotonic, but that's not particularly important). What
> I'd like to do is find an integer k such that f(k) and f(k+1) have
> opposite signs. Meaning, an actual root of the function f(N),
> pretending N is real, lies somewhere between the successive integers k
> and k+1. Also, I will note that using "fzero" is out of the question,
> as my function f(N) simply does not accept non-integer values.
>
> SUMMARY
> I need the integer k such that f(k)*f(k+1) < 0
>
> Is there some sort of bracketing algorithm in Matlab to do this?
>
> I know this can be done in a stupid way by calculating the function
> for a large range of integers and using "find" or something like that,
> but I'd like something that converges faster.
>
> Thanks,
> Jim

Why won't bisection work, until the interval is reduced
to 1 unit in length?

If you don't have a bracket on the interval, then you
can extrapolate two points until you do have a bracket
on the "root", then apply bisection.

For example, find x such that sqrt(x) - 37 = 0

fofx = @(x) sqrt(x) - 37;

fofx(1)
ans =
-36

fofx(2)
ans =
-35.5857864376269

fofx(4)
ans =
-35

Keep going, until you reach these points...

fofx(1024)
ans =
-5

fofx(2048)
ans =
8.25483399593904

So we have a bracket. Now use bisection.

fofx(1536)
ans =
2.19183588453085

Eventually, we will arrive at fofx(1369) == 0.

John
 | 
Pages: 1
Prev: Set a selection of a uibutton group element (Changing users choice)
Next: USB & FTDI & Compiler