Minimax Approximation and the Exchange Algorithm

In this video we'll discuss minimax approximation. This is a method of approximating functions by minimisation of the infinity (uniform) norm. The exchange algorithm is an iterative method of finding the approximation which minimises the infinity norm.
FAQ : How do you make these animations?
Animations are mostly made in Apple Keynote which has lots of functionality for animating shapes, lines, curves and text (as well as really good LaTeX). For some of the more complex animations, I use the Manim library. Editing and voiceover work in DaVinci Resolve.
Supporting the Channel.
If you would like to support me in making free mathematics tutorials then you can make a small donation over at
www.buymeacoff...
Thank you so much, I hope you find the content useful.

[@EdToml]

Years ago, in my first real job, I need to approximate some experimentally derived curves. These curves were used to figure out if an turbine was performing as designed. So the error in the approximations needed to be predicable. I first tried least squared, but quickly realized, that even though this algorithm minimized the total error it did not minimize the maximum error. Hence it would sometimes pass engines that should have been rejected. I then tried min max. It was 'fun' determining the coefficients. This was in the late 1970s and computer power was quite limited. Min max ended up working quite well. its a very good solution when errors mater.

[@emrekisi]

Best explanations ever, it takes just 12 minutes and worth for every second. Thank you👍

[@Darkev77]

Beautifully and elegantly presented!

[@tuongnguyen9391]

this algorithm is used in filter design for electrical engineering, something call Remez algorithm

[@The-Martian73]

Dude can't imagine how this did help me a lot, big thanks ❤

[@yuankunzhu7230]

First of all, i like this videos.🙂 because, your video is almost the only one which talking about remez algo that i have found. And, because, this "only one that i found" is very detailed, professional and with good examples. However, as a foreigner, more references(like slids or pdf file) are welcomed, and that will help me a lot.

[@conando025]

Lovely

[@francescomazzoli389]

Your videos are fantastic, thanks a lot for putting these out.

[@DrWillWood]

thanks , i appreciate that!

[@johnteran8889]

Beautiful video.

[@kodirovsshik]

That is very useful, thank you for sharing. Lovely video!

[@DrWillWood]

Thanks!

[@user-kf9xf9nd5s]

Your vedio is very claer, and the examples provided helps me to understand the whole algorithm and min max approximation. Excellent.Thanks for your sharing.

[@martinasdf4056]

Awesome!

[@General12th]

Hi Dr. Wood! This is nifty.

[@andrasferencz7948]

Thanks

[@DrWillWood]

thank you so much! Appreciate the support!

[@Focke42]

0:41 nom nom nomnom 😜Im sorry. The video was very informative👍

[@Noissimsarm]

Is there a proof of the first theorem? Why should the minimal generate error terms like that?

[@DrWillWood]

there are proofs for everything here in MJD Powell's "Approximation theory and methods" including the characterisation theorem, the inequality for the bound on |h|, proof of convergence of the exchange algorithm etc. The characterisation theorem actually applies not just to polynomials but a wider class of functions which satisfy a set of conditions called the "Haar conditions", but didn't want to complicate the video too much! As for why the error terms behave like that I don't have a great intuition beyond a straight line where it's easy to verify by playing around a bit. I feel like it has something to do with the number of minima and maxima of a polynomial increasing with its degree but can't say much beyond that i'm afraid!

[@hellomoto131313]

I got lost when at 3:05 he called it a 4th order polynomial P(x), but you can see from the visual that P(x) must be at least a 5th degree polynomial, due to P'(x) = 0 for 4 different x values in the given interval (or you can notice that the end behaviors are approaching opposite infinities, i.e. odd degree =/= 4th degree). Am i missing something? I'm assuming "order" and "degree" mean the same thing for this polynomial context

[@fork8972]

@DrWillWood 10:34 Should be 0.073, instead of 0.73.

[@albertmagician8613]

Once you realise that there is a background music, I can no longer follow the mathematics. I try to follow the music. Why do they that?

[@user-pr6ed3ri2k]

5:53 power of interpolation

[@user-pr6ed3ri2k]

1:13 idk like y=1/2 or smth

[@pabloealvarez]

manim? regards from Chile!

[@DrWillWood]

Well spotted! Manim is used for the repeated iterations of the exchange algorithm. the rest is done in keynote!