Remez algorithm: Difference between revisions

Revision as of 22:07, 19 June 2025

Latest revision as of 00:18, 26 July 2025

(One intermediate revision by the same user not shown)

Line 65:

<math>p_2(x)</math> to the ordinates <math>(-1)^i</math>

:<math>p_1(x_i) = f(x_i), p_2(x_i) = (-1)^i, i = 0, ..., n.</math>

To this end, use each time [[Newton polynomial|Newton's interpolation formula]] with the [[divided differences]] of order <math>0, ...,n</math> and <math>O(n^2)</math> arithmetic operations.

differences of order <math>0, ...,n</math> and <math>O(n^2)</math> arithmetic operations.

The polynomial <math>p_2(x)</math> has its ''i''-th zero between <math>x_{i-1}</math> and <math>x_i,\ i=1, ...,n</math>, and thus no further zeroes between <math>x_n</math> and <math>x_{n+1}</math>: <math>p_2(x_n)</math> and <math>p_2(x_{n+1})</math> have the same sign <math>(-1)^n</math>.

Line 83 ⟶ 82:

:<math>p(x_i) - f(x_i) \ = \ -(-1)^i E,\ \ i = 0, ... , n\!+\!1. </math>

The theorem of [[Charlesequioscillation Jean de la Vallée Poussin|de La Vallée Poussintheorem]] states that under this condition no polynomial of degree ''n'' exists with error less than ''E''. Indeed, if such a polynomial existed, call it <math>\tilde p(x)</math>, then the difference

<math>p(x)-\tilde p(x) = (p(x) - f(x)) - (\tilde p(x) - f(x))</math> would still be positive/negative at the ''n''+2 nodes <math>x_i</math> and therefore have at least ''n''+1 zeros which is impossible for a polynomial of degree ''n''.

Thus, this ''E'' is a lower bound for the minimum error which can be achieved with polynomials of degree ''n''.