Solving an implicit function, fsolve vs. fzero

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.

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.