Is there a way to make fzero reuse values from interval search

This post is half question, half update request...

When calling fzero with only a starting point, not an interval, is there a way to make fzero reuse/recycle the values it has calculated during the initial interval search. I'm guessing not, however the function I'm finding the root of is expensive, and fzero takes ages to execute. See the example output below. At the last iteration of the interval search, fzero has come very close to having the correct answer with a=102.885 and f(a)=79.5417. However, after an interval is identified, fzero then begins the zero search in the interval [99.1788, 120.778]. Surely it would make more sense to use the interval [99.1788, 102.885] because this brackets the solution much more closely. Or is using a smaller interval not possible because the underlying numerical method uses three points.

Search for an interval around 111.831 containing a sign change:
 Func-count    a          f(a)             b          f(b)        Procedure
    1         111.831   1.48227e+06       111.831   1.48227e+06   initial interval
    3         108.668        956222       114.994   2.00547e+06   search
    5         107.358        737493       116.304   2.22137e+06   search
    7         105.505        427326       118.157   2.52586e+06   search
    9         102.885       79.5417       120.778   2.95484e+06   search
   10         99.1788       -626531       120.778   2.95484e+06   search
 
Search for a zero in the interval [99.1788, 120.778]:
 Func-count    x          f(x)             Procedure
   10         99.1788       -626531        initial
   11         102.957       12343.2        interpolation
   12         102.957       12343.2        interpolation
 
Zero found in the interval [99.1788, 120.778]
Solver terminated with area 102.9574

Answer 1

[Divyam]

Hi @men8th,

The "fzero" function does not reuse or recycle the function values calculated during the initial interval search. To improve the speed of the interval search, you can mention the interval you identified, i.e. as the initial interval when calling "fzero" again.

To reuse the function values during the initial interval search, use a "Map" and define a custom initial root interval finder. However, if the function to be evaluated is complex, the "Map" may serve more harm than good by running into memory issues as the algorithm requires more iterations depending upon the initial guess and the step size.

% Code for finding the initial root interval using Map 
function [interval, map] = rootIntervalMap(func, x0, step, maxIter)
    % Initialize variables
    a = x0;
    b = x0 + step;
    
    % Creating the Map
    map = containers.Map('KeyType', 'double', 'ValueType', 'any');
    
    % Function to get key value or compute if not cached
    fa = getMapValue(func, map, a);
    fb = getMapValue(func, map, b);
    
    % Expand interval until a sign change is found or max iterations reached
    iter = 0;
    while iter < maxIter
        if sign(fa) ~= sign(fb)
            interval = [a, b];
            return;
        end
        
        % Expand the interval
        a = b;
        fa = fb;
        b = b + step;
        fb = getMapValue(func, map, b);
        iter = iter + 1;
    end
    
    % Optional: If no interval is found
    interval = [NaN, NaN];
    warning('Failed to find a valid interval after %d iterations.', maxIter);
end

% Helper function for getting the Map value
function y = getMapValue(func, map, x)
        if isKey(map, x)
            y = map(x);
        else
            y = func(x);
            map(x) = y;
        end
end

% Define the function 
myFunction = @(x) 5*(x.^10) - x.^4 - x.^2 - 4;

% Configuring the initialGuess, stepSize and maxIterations
initialGuess = -2;          
stepSize = 0.1;               
maxIterations = 10000;        

% Using the map based interval search for the function f(x) = 5x^10 - x^4 - x^2 - 4
[interval, map] = rootIntervalMap(myFunction, initialGuess, stepSize, maxIterations);

% Finding the root using the "fzero" function
root = fzero(myFunction, interval);

fprintf('Interval found: [%.4f, %.4f]\n', interval(1), interval(2));

Interval found: [-1.1000, -1.0000]

fprintf('Root found using fzero and Map: %.4f\n', root);

Root found using fzero and Map: -1.0205

% Running fzero without finding out the interval first
rootAlt = fzero(myFunction, initialGuess);
fprintf('Root found using fzero: %.4f\n', rootAlt);

Root found using fzero: -1.0205

For more information regarding "containers.Map", refer to this documentation: https://www.mathworks.com/help/matlab/ref/containers.map.html

[men8th]

Memoizing a function is also a good way to re-use values calculated with previous function calls (as an alternative to Map or dictionary): memoize - Add memoization semantics to function handle - MATLAB - MathWorks United Kingdom

[Divyam]

Yes, this is another standard technique to cache your information.