algorithm - 为未知函数建立线性近似

Question

我有一些未知函数 f(x)，我正在使用 matlab 计算函数图上的 2000 个点。我需要一个包含 20 到 30 段的分段线性函数 g，它最适合原始函数，我怎样才能以可接受的方式做到这一点？可能的解空间是无法遍历的，也想不出好的启发式函数来有效地缩小它。

这是派生函数的代码:

x = sym('x', 'real'); 
inventory = sym('inventory', 'real'); 
demand = sym('demand', 'real'); 
f1 = 1/(sqrt(2*pi))*(-x)*exp(-(x - (demand - inventory)).^2./2); 
f2 = 20/(sqrt(2*pi))*(x)*exp(-(x - (demand - inventory)).^2./2);
expectation_expression = int(f1, x, -inf, 0) + int(f2, x, 0, inf);

Answer 1

根据您对好的近似的想法，可能有一个动态规划解决方案。

例如，给定 2000 个点和相应的值，我们希望找到具有 20 段的分段线性逼近，使每个点的真实值与线性逼近的结果之间的偏差平方和最小。

从左到右沿着 2000 个点工作，并在每个点计算 i=1 到 20 从最左边到该点的总误差，以获得使用 i 段的最佳分段线性逼近。

您可以使用为该位置左侧的点(点 1..n)计算的值来计算位置 n+1 处的值。对于 i 的每个值，考虑其左侧的所有点 - 例如点 j < n+1。计算从点 j 到点 n+1 的直线段产生的误差贡献。再加上您使用 i-1 段在 j 点(或可能是 j-1 点，具体取决于您定义分段线性近似值)计算出的最佳可能误差的值。如果您现在对所有可能的 j 取最小值，则您已经使用前 n+1 个点的 i 段计算了最佳分段线性近似的误差。

当您使用 20 个分段计算出前 2000 个点的最佳值时，您就解决了问题，您可以沿着此表返回以找出分段的位置 - 或者，如果这样做不方便，您可以在进行过程中保存额外的信息，使这更容易。

我相信类似的方法将最小化绝对偏差的总和，或最小化任何点的最大偏差，前提是您能够解决单条线的相应问题。我隐含地假设你可以拟合一条直线来最小化误差平方和，这当然是标准的平方和线拟合。最小化与直线的绝对偏差是凸优化的一个练习，我会通过重复加权最小二乘法来尝试。最小化最大绝对偏差是线性规划。