寻求Matlab/Python实现：用分段线性函数低估f(x)

Matlab实现代码 #

% 生成x轴数据
x = 0.000000001:0.001:1;
y = abs(f(x)); % 替换f(x)为你的目标函数

% 设置分段数量
numOfSections = 5;
totalRange = max(x) - min(x);
sectionSize = totalRange / numOfSections;

% 自适应节点生成（基于导数的逆，曲线变化剧烈处节点更密）
dy = diff(y) ./ diff(x);
dy = [dy(1); dy]; % 补全导数数组长度
weights = 1./(abs(dy) + eps); % 导数越大，权重越小（区间越密）
cdf = cumsum(weights) / sum(weights); % 计算累积分布函数
xNodes = interp1(cdf, x, linspace(0, 1, numOfSections + 1)); % 生成自适应节点

% 初始化节点y坐标，用于构造低估函数
yNodes = zeros(size(xNodes));

% 逐个区间处理，确保分段线性函数满足g(x) ≤ |f(x)|
for i = 1:numOfSections
    % 筛选当前区间内的x和y数据
    xInterval = x(x >= xNodes(i) & x <= xNodes(i+1));
    yInterval = y(x >= xNodes(i) & x <= xNodes(i+1));
    
    % 尝试用区间端点构造线性插值
    y1_candidate = yInterval(1);
    y2_candidate = yInterval(end);
    lineY = linspace(y1_candidate, y2_candidate, length(xInterval));
    
    % 检查插值线是否完全低于原曲线（加小epsilon避免浮点误差）
    if all(lineY <= yInterval + 1e-10)
        yNodes(i) = y1_candidate;
        yNodes(i+1) = y2_candidate;
    else
        % 若插值线会高估，取区间内y的最小值构造水平下界（保守但可靠）
        minY = min(yInterval);
        yNodes(i) = minY;
        yNodes(i+1) = minY;
    end
end

% 生成低估函数g(x)的完整y值
g_y = interp1(xNodes, yNodes, x, 'linear');

% 绘图对比
figure;
plot(x, y, 'b', 'LineWidth', 1.5);
hold on;
plot(x, g_y, 'r--', 'LineWidth', 1.5);
scatter(xNodes, yNodes, 50, 'r', 'filled');
legend('|f(x)|', '低估分段线性函数g(x)');
xlabel('x');
ylabel('y');
title('分段线性函数低估|f(x)|');
hold off;

Python实现代码 #

import numpy as np
import matplotlib.pyplot as plt

def f(x):
    # 替换为你的目标函数，示例为f(x) = sin(1/x)
    return np.sin(1/x)

# 生成x轴数据
x = np.linspace(1e-9, 1, 1000)
y = np.abs(f(x))

# 设置分段数量
num_of_sections = 5
total_range = x.max() - x.min()

# 自适应节点生成（基于导数的逆）
dy = np.diff(y) / np.diff(x)
dy = np.concatenate([[dy[0]], dy])  # 补全导数数组长度
weights = 1 / (np.abs(dy) + 1e-10)
cdf = np.cumsum(weights) / weights.sum()
x_nodes = np.interp(np.linspace(0, 1, num_of_sections + 1), cdf, x)

# 初始化节点y坐标
y_nodes = np.zeros_like(x_nodes)

# 逐个区间构造低估函数
for i in range(num_of_sections):
    mask = (x >= x_nodes[i]) & (x <= x_nodes[i+1])
    x_interval = x[mask]
    y_interval = y[mask]
    
    # 尝试端点插值
    y1_candidate = y_interval[0]
    y2_candidate = y_interval[-1]
    line_y = np.linspace(y1_candidate, y2_candidate, len(x_interval))
    
    if np.all(line_y <= y_interval + 1e-10):
        y_nodes[i] = y1_candidate
        y_nodes[i+1] = y2_candidate
    else:
        # 取区间最小值构造水平下界
        min_y = y_interval.min()
        y_nodes[i] = min_y
        y_nodes[i+1] = min_y

# 生成低估函数g(x)的y值
g_y = np.interp(x, x_nodes, y_nodes)

# 绘图展示
plt.figure(figsize=(10, 6))
plt.plot(x, y, 'b', linewidth=1.5, label='|f(x)|')
plt.plot(x, g_y, 'r--', linewidth=1.5, label='低估分段线性函数g(x)')
plt.scatter(x_nodes, y_nodes, s=50, c='r', marker='o', label='节点')
plt.legend()
plt.xlabel('x')
plt.ylabel('y')
plt.title('分段线性函数低估|f(x)|')
plt.show()

关键改动说明 #

1. 补全节点生成逻辑：原代码未定义sectionSize，这里补充了自适应节点生成方式——在曲线变化剧烈（导数大）的地方设置更密集的节点，让低估函数更贴近原曲线。
2. 低估校验与调整：新增区间遍历逻辑，先尝试用端点构造线性插值，若插值线存在高于原曲线的点，则调整为区间最小值的水平直线，确保g(x) ≤ |f(x)|对所有x成立。
3. 完整函数生成：通过插值生成低估函数的完整数据，方便绘图对比原曲线与低估效果。

内容的提问来源于stack exchange，提问作者Juan