Twitter proof: interpolating polynomials


< change language

In this post I will show the existence of a family of polynomials that are very useful for interpolation. For that I will use what are known as Lagrange polynomials.

Claim: given $n+1$ pairs $(x_i, y_i) $ with $0\leq i \leq n $ and with $x_i \neq x_j $ whenever $i\neq j $, there exists a polynomial $p(x) $ of degree at most $n $ such that $$p(x_i) = y_i,\ i = 0, \cdots, n $$
Twitter proof: consider the polynomial $$l_i(x) = \prod_{j\neq i} \frac{x - x_j}{x_i - x_j} $$ with $l_i(x_i) = 1$ and $l_i(x_j) = 0$ whenever $j \neq i$. Define $p(x) $ to be $$p(x) = \sum_{i=0}^{n} y_i l_i(x) $$ $p(x) $ has degree at most $n $ because so do the $l_i(x) $ and $p(x_k) = \sum_i y_i l_i(x_k) = y_k $.

In a future post I will show the uniqueness of the polynomial satisfying the constraints in the claim.
Neste post vou mostrar a existência de uma família interessante de polinómios, muito útil em interpolação. Para isso vou usar uns polinómios chamados polinómios de Lagrange.

Proposição: dados $n+1$ pares $(x_i, y_i) $ onde $0\leq i \leq n $ e tais que $x_i \neq x_j $ sempre que $i\neq j $, existe um polinómio $p(x) $ de grau menor ou igual a $n $ satisfazendo as igualdades $$p(x_i) = y_i,\ i = 0, \cdots, n $$
Prova num tweet: considere-se o polinómio $$l_i(x) = \prod_{j\neq i} \frac{x - x_j}{x_i - x_j} $$ que satisfaz $l_i(x_i) = 1$ e $l_i(x_j) = 0$ sempre que $j \neq i$. Definimos $p(x) $ como $$p(x) = \sum_{i=0}^{n} y_i l_i(x) $$ $p(x) $ tem grau menor ou igual a $n $ porque os $l_i(x) $ o têm e $p(x_k) = \sum_i y_i l_i(x_k) = y_k $.

Num post futuro mostrarei a unicidade do polinómio que satisfaz as restrições da proposição.

  - RGS

Popular posts from this blog

Tutorial on programming a memory card game

Image
Pt En Este post vai ser um tutorial, não muito detalhado, sobre como fazer um jogo de memória com Python e pygame. O jogo que vamos implementar é um jogo comum: viramos uma série de cartas para baixo e temos que as virar duas a duas, tentando encontrar os pares. Claro que quando viramos duas cartas que não são um par, temos de as voltar de novo para baixo. Quando estou a criar um jogo, gosto de o ir desenvolvendo por etapas funcionais: partir o processo em várias fases que representem pontos nos quais eu tenho algo que posso testar. Deste modo, não só o processo se torna muito mais interessante, como posso ir controlando o aspeto do que estou a produzir. Deixo de seguida uma lista das etapas que eu pensei para este projeto; cada ponto da lista descreve a funcionalidade que o jogo já suporta: Criar um ecrã onde mostro todas as cartas dispostas, face para baixo; Clicar em cima de uma carta faz com que ela se vire para cima; Clicar na segunda carta verifica se encontrei
Read more

Markov Decision Processes 01: the basics

Image
Pt En < change language In this post I will introduce Markov Decision Processes, a common tool used in Reinforcement Learning, a branch of Machine Learning. By the end of the post you will be able to make some sense of the figure above! I will couple the formal details, definitions and maths with an intuitive example that will accompany us throughout this post. In later posts we will make our example more complete and use other examples to explain other properties and characteristics of the MDPs. Let me introduce the context of the example: From a simplistic point of view, I only have two moods: " hungry " and " thirsty ". Thankfully, my parents taught me how to eat and how to drink, so that I can fulfill the needs I mentioned earlier. Of course that eating when I am hungry makes me happy, just as drinking when I am thirsty makes me happy! Not only that, but eating when I am hungry usually satisfies me, much like drinking when I am thirsty us
Read more

The hairy ball theorem and why there is no wind (somewhere) on Earth

Image
Pt En < change language What if I told you that right now there is a place on Earth where there is no wind blowing to the sides? None at all! How can I know that? All we need is what is usually called the Hairy Ball Theorem . In less rigorous contexts, one can phrase the Hairy Ball Theorem as such: Theorem (Hairy Ball I): if you have a hairy ball, regardless of the way you comb its hair there will always be a spot where the hair points right up. In this particular image, the hair is pointing up both on the top and on the bottom. More formally, the Hairy Ball Theorem can be formulated like so: Theorem (Hairy Ball II): every continuous vector field over $S^2$ has at least a point where the tangential component is $0$. From this theorem it is actually quite easy to establish our interesting fact! If we think of the wind at the Earth's surface as a continuous vector field, the Hairy Ball Theorem says that there must be a point where the wind isn'
Read more