Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

New to MATLAB?

Solving an implicit function, fsolve vs. fzero

Asked by darius

darius (view profile)

on 4 Jul 2012

Hi,

I'm trying to solve an implicit function for x that looks like this:

A*x^q + Bx - C = 0

The solution is within (0,1). Speed is a huge issue. The solution is used to write down a new problem. (A and B both depend on the previous value of x). Both fsolve and fzero are too slow. Any ideas?

Thanks.

4 Comments

Walter Roberson

Walter Roberson (view profile)

on 5 Jul 2012

What are the knowns and unknowns ? Are you only solving for x, or for x, q, and C ? Is q a positive integer or can it be fractional ?

Richard Brown

Richard Brown (view profile)

on 5 Jul 2012

Is there known to be only one solution in the interval? Is the solution to a subsequent problem known to be close to the solution to the current one?

darius

darius (view profile)

on 5 Jul 2012

Thank you for the comments. fminsearch is also too slow.

x is the only unknown. q is a fraction for sure. The solution to the subsequent problem is known to be greater than the solution tot he current one.

darius

darius (view profile)

Products

No products are associated with this question.

2 Answers

Answer by Anton Semechko

Anton Semechko (view profile)

on 5 Jul 2012

You can try the following approach:

abc=rand(3,1); % A, B, C parameters
q=8;           % order of the polynomial
Nmax=1E3;      % maximum number of iterations
f_tol=1E-6;    % convergence tolerance
k=0.9;         % relaxation parameter, must be in the range (0,1]
x=0.5;         % starting point
f=abc(1)*x^q + abc(2)*x - abc(3); % initial function value
% search for the zero
for i=1:Nmax
    x=k*x+(1-k)*(x-f); % update x
    f=abc(1)*x^q + abc(2)*x - abc(3);
    disp([i f x])
    if abs(f)<f_tol, break; end
end
clear q Nmax f_tol k i

I tested the code given above for integer value of q in the range [1,10], and was able to find a solution in at most ~200 iterations. You can also play around with the k parameter to tune the rate of convergence. Note that setting k too low will cause the search to become unstable.

3 Comments

Richard Brown

Richard Brown (view profile)

on 5 Jul 2012

I think if you go with a derivative free approach a binary search would be quicker - it would get you 6 digits of accuracy guaranteed in 20 steps

Anton Semechko

Anton Semechko (view profile)

on 5 Jul 2012

you can get similar performance if you decrease 'k' from 0.9 to a lower value (e.g. 0.6)

Richard Brown

Richard Brown (view profile)

on 5 Jul 2012

Actually, what I said doesn't work anyway! Too early in the morning, no coffee yet :)

Anton Semechko

Anton Semechko (view profile)

Answer by Richard Brown

Richard Brown (view profile)

on 5 Jul 2012
Edited by Richard Brown

Richard Brown (view profile)

on 5 Jul 2012

How about doing a fixed number of Newton steps for each problem? (not necessarily doing a convergence check)

For example:

A, B, c, q = ...
nSteps = 5;
x = 0.5
for i = 1:nProblems
  % Use x from previous problem to update
  for i = 1:nSteps
    x = x - (A*x^q + B*x + c) / (q*A*x^(q-1) + B);
  end
    % Update A, B, c, q to next problem
end

You could always add in a convergence check, or track the errors if you need to. Of course whether or not this works depends on the parameters of your problem, but with a bit of luck it will.

0 Comments

Richard Brown

Richard Brown (view profile)

Contact us