在 MATLAB 中求解多个非线性独立方程的最快方法？

Question

MATLAB 有两种求解非线性方程的方法：

fzero：求解单个非线性方程
fsolve: 求解非线性方程组

因此，可以采用以下方法求解n个非线性独立方程组：

使用循环分别求解方程 fzero
使用循环分别求解方程 fsolve
用fsolve一起解决

我的直觉是：

对于大型 n，循环方法比单个系统更快，因为复杂度（梯度计算）为 0(n^2)
小的循环可能会更慢n，因为循环在 MATLAB 中有很高的开销，并且可能有一些恒定的启动时间
fzero 比 fsolve 快，因为它是专门为单个非线性方程设计的。

问题：求解n非线性独立方程组的最快方法是什么？还有其他方法吗？应使用哪些选项来加快该过程？

示例问题：（可用于对不同答案进行基准测试）

x_i^2 = 1

i 介于 1 和 n

之间

相关话题

Answer 1

评估某些方法性能的最佳方法是编写基准测试。考虑四种情况：

loop fzero：使用循环分别求解方程fzero
loop fsolve：使用循环分别用fsolve
默认 fsolve：将方程作为一个方程组一起求解
独立fsolve：与默认fsolve相同，但specifies that the equations are independent

f = @(x) x.^2-1; % the set of non-linear equations
ns = 1:1:100; % the sizes for which the benchmark is performed
options=optimset('Display','off'); % disable displaying

figure
hold on
plot(ns, loopFSolve(f, ns, options), 'DisplayName', 'loop fsolve')
plot(ns, loopFZero(f, ns, options), 'DisplayName', 'loop fzero')
plot(ns, defaultFSsolve(f, ns, options), 'DisplayName', 'default fsolve')
plot(ns, independentFSolve(f, ns, options), 'DisplayName', 'independent fsolve')

legend ('Location', 'northwest')

function t = loopFZero(f, ns, options)
  t1 = timeit(@() fzero(f, rand(1), options));
  t = ns * t1;
end

function t = loopFSolve(f, ns, options)
  t1 = timeit(@() fsolve(f, rand(1), options));
  t = ns * t1;
end

function t = defaultFSsolve(f, ns, options)
  t = zeros(size(ns));
  for i=1:length(ns)
    n = ns(i);
    un = rand(n, 1);
    t(i) = timeit(@() fsolve(f, un, options));
  end
end

function t = independentFSolve(f, ns, options)
  t = zeros(size(ns));
  for i=1:length(ns)
    n = ns(i);
    un = rand(n, 1);
    options.Algorithm = 'trust-region-reflective';
    options.JacobPattern = speye(n);
    options.PrecondBandWidth = 0;

    t(i) = timeit(@() fsolve(f, un, options));
  end
end

结果

所有数字都显示了完整系统的计算时间 n，方程的数量。

前两个数字绘制 n 最多 1000，间隔为 100。最后两个数字绘制 n 最多 100，间隔为 1。对于每个，第二个图与第一个相同，但没有 loop fzero 因为它比其他的慢得多。

结论

loop fsolve: 不要使用它，启动时间太长
loop fzero：您可以将它用于小型 n（n < ~20 的最快方法）
默认fsolve：你可以用它来解决相对较小的问题n（~20 < n < ~50的最快方法，但与2和3的差异相对较小） .
independent fsolve：你应该将它用于大 n（~50 < n 的最快方法）

一般，应该使用独立fsolve，只对小的n loop fzero 可以代替使用，即使用 fsolve 和以下选项：

options.Algorithm = 'trust-region-reflective';
options.JacobPattern = speye(n);
options.PrecondBandWidth = 0;

懒惰的人可能只使用默认的fsolve，因为它对中等数量的方程具有合理的性能（n < ~200)

重要提示

Bob 指出 vectorised version of fzero 可能要快多个数量级。根据 Bob 的测试结果，他的方法是最快的方法 对于每个大小的问题，即大和小 n.

备注

注意默认fsolve的时间复杂度是O(n^2)，其他都是O(n)。
请注意，fzero 和 fsolve 在某些边界情况下可能表现不同，f.e fzero 在搜索时不会找到 x^2 的解决方案符号更改的位置。

Answer 2

我添加这个答案是为了详细说明我上面的评论。根据我的经验，目前最快的方法是使用文件交换中可用的矢量化版本的 fzero：Link to vectorized bisection code

这里有几个基准测试，将其性能与 (i) 循环 fzero 和 (ii) 独立 fsolve 进行比较。

f = @(x) x.^2-1; %the set of non-linear equations
ns = 1e5; %size of the problem

% method 1: looped fzero
t = timeit(@() fzero(f, rand(1)));
loopFZero = t*ns

% method 2: independent fsolve
options=optimset('Display','off'); % disable displaying
options.Algorithm = 'trust-region-reflective';
options.JacobPattern = speye(ns);
options.PrecondBandWidth = 0;
indepFSolve = timeit(@() fsolve(f, rand(ns,1), options))

% method 3: vectorized bisection, available here:
% https://www.mathworks.com/matlabcentral/fileexchange/28150-bisection-method-root-finding
vecBisection = timeit(@() bisection(f, zeros(ns,1), 2))

结果

%---------------
% ns = 10

loopFZero =

    0.0027


indepFSolve =

    0.0049


vecBisection =

   5.0978e-05

%---------------
% ns = 1e5

loopFZero =

   28.7574


indepFSolve =

    7.7601


vecBisection =

    0.0013

在 MATLAB 中求解多个非线性独立方程的最快方法？

Fastest method to solve multiple nonlinear independent equations in MATLAB?

performance

matlab

nonlinear-optimization

equation-solving