---
tag: H129B6DA0F
kind: concept
name: Remez algorithm
msc: [65D15, 41A50, 41A10]
sources:
  - url: https://en.wikipedia.org/wiki/Remez_algorithm
same_as:
  wikidata: Q2835816
  wikipedia: Remez algorithm
---

## Summary

The Remez algorithm is an iterative method that computes the [[minimax approximation|ASWF03X5AM]] of a continuous function by polynomials of a given degree.
Each round has two steps.
First it fits a polynomial whose error has equal size and alternating signs on $n + 2$ reference points.
Then it moves the reference points to the places where the error is largest.
It was introduced by Evgeny Remez in 1934 and is a standard way to design polynomial and rational approximations in numerical libraries.

## Explanations

### L1 human

The best uniform approximation has an error curve that wiggles up and down with equal height at $n + 2$ places.
The algorithm guesses those places, forces the error to have equal height there, and then looks where the error is really largest.
It moves the guessed places there and repeats.
For a straight-line approximation of $x^2$ on $[-1, 1]$, starting from the points $-1, 0, 1$ already gives the answer $1/2$ in one step.