Editing Approximation theory (section)

==Optimal polynomials==
Once the domain (typically an interval) and degree of the polynomial are chosen, the polynomial itself is chosen in such a way as to minimize the worst-case error. That is, the goal is to minimize the maximum value of <math>\mid P(x) - f(x)\mid</math>, where ''P''(''x'') is the approximating polynomial, ''f''(''x'') is the actual function, and ''x'' varies over the chosen interval. For well-behaved functions, there exists an ''N''<span style="padding-left:0.1em;">th</span>-degree polynomial that will lead to an error curve that oscillates back and forth between <math>+\varepsilon</math> and <math>-\varepsilon</math> a total of ''N''+2 times, giving a worst-case error of <math>\varepsilon</math>. It is seen that there exists an ''N''<span style="padding-left:0.1em;">th</span>-degree polynomial that can interpolate ''N''+1 points in a curve. That such a polynomial is always optimal is asserted by the [[equioscillation theorem]]. It is possible to make contrived functions ''f''(''x'') for which no such polynomial exists, but these occur rarely in practice.

For example, the graphs shown to the right show the error in approximating log(x) and exp(x) for ''N''&nbsp;=&nbsp;4. The red curves, for the optimal polynomial, are '''level''', that is, they oscillate between <math>+\varepsilon</math> and <math>-\varepsilon</math> exactly. In each case, the number of extrema is ''N''+2, that is, 6. Two of the extrema are at the end points of the interval, at the left and right edges of the graphs.

[[Image:Impossibleerror.png|thumb|right|300px|Error ''P''(''x'')&nbsp;&minus;&nbsp;''f''(''x'') for level polynomial (red), and for purported better polynomial (blue)]] To prove this is true in general, suppose ''P'' is a polynomial of degree ''N'' having the property described, that is, it gives rise to an error function that has ''N''&nbsp;+&nbsp;2 extrema, of alternating signs and equal magnitudes. The red graph to the right shows what this error function might look like for ''N''&nbsp;=&nbsp;4. Suppose ''Q''(''x'') (whose error function is shown in blue to the right) is another ''N''-degree polynomial that is a better approximation to ''f'' than ''P''. In particular, ''Q'' is closer to ''f'' than ''P'' for each value ''x<sub>i</sub>'' where an extreme of ''P''−''f'' occurs, so
:<math>|Q(x_i)-f(x_i)|<|P(x_i)-f(x_i)|.</math>
When a maximum of ''P''−''f'' occurs at ''x<sub>i</sub>'', then
:<math>Q(x_i)-f(x_i)\le|Q(x_i)-f(x_i)|<|P(x_i)-f(x_i)|=P(x_i)-f(x_i),</math>
And when a minimum of ''P''−''f'' occurs at ''x<sub>i</sub>'', then
:<math>f(x_i)-Q(x_i)\le|Q(x_i)-f(x_i)|<|P(x_i)-f(x_i)|=f(x_i)-P(x_i).</math>
So, as can be seen in the graph, [''P''(''x'')&nbsp;−&nbsp;''f''(''x'')]&nbsp;−&nbsp;[''Q''(''x'')&nbsp;−&nbsp;''f''(''x'')] must alternate in sign for the ''N''&nbsp;+&nbsp;2 values of ''x<sub>i</sub>''. But [''P''(''x'')&nbsp;−&nbsp;''f''(''x'')]&nbsp;−&nbsp;[''Q''(''x'')&nbsp;−&nbsp;''f''(''x'')] reduces to ''P''(''x'')&nbsp;−&nbsp;''Q''(''x'') which is a polynomial of degree ''N''. This function changes sign at least ''N''+1 times so, by the [[Intermediate value theorem]], it has ''N''+1 zeroes, which is impossible for a polynomial of degree ''N''.