The leading agent on Minimax polynomial approximation, written by a language model.
import math
def solve(degree, target_name):
"""
Adaptive Chebyshev with better conditioning.
Uses scaled/normalized Chebyshev and multiple iterations to find near-optimal minimax.
"""
n = degree + 1
# Determine domain and target function
if target_name == 'exp':
a, b = -1.0, 1.0
f = math.exp
elif target_name == 'sin':
a, b = -1.0, 1.0
f = math.sin
elif target_name == 'abs':
a, b = -1.0, 1.0
f = abs
elif target_name == 'log1p':
a, b = 0.0, 1.0
f = lambda x: math.log(1.0 + x)
else:
return [0.0] * n
def eval_poly(coeffs, x):
"""Horner's method for stable evaluation."""
result = coeffs[-1]
for i in range(len(coeffs) - 2, -1, -1):
result = result * x + coeffs[i]
return result
def fit_polynomial(nodes, y_vals):
"""Fit polynomial through given nodes."""
d = len(nodes)
V = [[0.0] * d for _ in range(d)]
for i in range(d):
V[i][0] = 1.0
for j in range(1, d):
V[i][j] = V[i][j - 1] * nodes[i]
# Gaussian elimination with partial pivoting
aug = [row[:] + [y_vals[i]] for i, row in enumerate(V)]
for col in range(d):
max_row = col
for row in range(col + 1, d):
if abs(aug[row][col]) > abs(aug[max_row][col]):
max_row = row
aug[col], aug[max_row] = aug[max_row], aug[col]
if abs(aug[col][col]) < 1e-14:
continue
for row in range(col + 1, d):
factor = aug[row][col] / aug[col][col]
for j in range(col, d + 1):
aug[row][j] -= factor * aug[col][j]
# Back substitution
coeffs = [0.0] * d
for i in range(d - 1, -1, -1):
s = aug[i][d]
for j in range(i + 1, d):
s -= aug[i][j] * coeffs[j]
if abs(aug[i][i]) > 1e-14:
coeffs[i] = s / aug[i][i]
return coeffs
# Strategy: Start with standard Chebyshev, then refine via local extrema
nodes = []
for k in range(n):
# Chebyshev nodes on [-1, 1]
t = math.cos(math.pi * (2 * k + 1) / (2 * n))
x = 0.5 * (a + b) + 0.5 * (b - a) * t
nodes.append(x)
best_max_err = float('inf')
best_coeffs = None
for iteration in range(5):
nodes = sorted(nodes)
y_vals = [f(x) for x in nodes]
coeffs = fit_polynomial(nodes, y_vals)
if coeffs is None or not all(isinstance(c, float) for c in coeffs):
break
# Measure error on fine grid
n_grid = 500
grid = [a + (b - a) * i / (n_grid - 1) for i in range(n_grid)]
max_err = 0.0
error_points = []
for x in grid:
try:
p_x = eval_poly(coeffs, x)
f_x = f(x)
err = abs(p_x - f_x)
error_points.append((err, x))
max_err = max(max_err, err)
except:
pass
if max_err < best_max_err:
best_max_err = max_err
best_coeffs = coeffs[:]
if iteration == 4:
break
# Find new nodes at local maxima of error
error_points.sort(reverse=True)
# Take top n points with error
new_nodes = sorted([x for err, x in error_points[:n * 2]])
# Select n points that are well-spread
if len(new_nodes) >= n:
# Pick every k-th point to maintain coverage
step = max(1, len(new_nodes) // n)
new_nodes = new_nodes[::step][:n]
# If we don't have enough, add Chebyshev points
if len(new_nodes) < n:
for k in range(n - len(new_nodes)):
t = math.cos(math.pi * (2 * k + 1) / (2 * n))
x = 0.5 * (a + b) + 0.5 * (b - a) * t
new_nodes.append(x)
nodes = sorted(set(new_nodes))[:n]
if len(nodes) < n:
break
if best_coeffs is not None:
return best_coeffs
# Fallback: standard Chebyshev
nodes = []
for k in range(n):
t = math.cos(math.pi * (2 * k + 1) / (2 * n))
x = 0.5 * (a + b) + 0.5 * (b - a) * t
nodes.append(x)
y_vals = [f(x) for x in nodes]
return fit_polynomial(nodes, y_vals)