Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If $P(x)$ is a polynomial such that $P(a_{1})=b_{1}, P(a_{2})=b_{2}, \ldots , P(a_{k})=b_{k}$, how can I find the polynomial which has minimum degree and for whom the relations above are true?

share|improve this question

3 Answers 3

You can use Lagrange interpolation to find the polynomial. It will have degree at most $k-1$ It will take some work to see if the degree is less.

share|improve this answer
1  
There is no need to check what the degree is. The Lagrange interpolation formula produces the polynomial of least degree that interpolates through the $k$ points. The apparent degree is $k-1$ since $L(x)$ is the weighted sum of polynomials of degree $k-1$, but the sum can have smaller degree, and indeed has the minimal degree. –  Dilip Sarwate May 8 '13 at 20:52
    
@DilipSarwate: You are correct, but I thought OP wanted to know the exact degree of the polynomial. If not, there is no need. –  Ross Millikan May 8 '13 at 21:30

Given $k$ distinct points, from the fundamental theorem of algebra, we can find a polynomial of degree at most $k-1$ passing through these $k$ points. This polynomial is called the Lagrange polynomial and this interpolation is known as Lagrange interpolation. The Lagrange polynomial is found as follows: First compute $$L_j(a) = \dfrac{\prod_{i \neq k}(a-a_i)}{(a_j-a_i)}$$ Note that $L_j(x)$ is a polynomial in $a$ of degree $k-1$ and has the property that $L_j(a_i) = \delta_{ij}$, where $\delta_{ij}$ is the Kronecker delta. Now, the Lagrange polynomial you are after is given by $$L(a) = \sum_{j=1}^k b_j L_j(a)$$ The degree of this interpolating polynomial is nothing but the rank of the following matrix $$\begin{bmatrix}1 & a_1 & a_1^2 & \cdots a_1^{k-1} & b_1\\ 1 & a_2 & a_2^2 & \cdots a_2^{k-1} & b_2\\ 1 & a_3 & a_3^2 & \cdots a_3^{k-1} & b_3\\ \vdots & \vdots & \vdots & \ddots \vdots & \vdots\\ 1 & a_k & a_k^2 & \cdots a_k^{k-1} & b_k\\\end{bmatrix}$$

share|improve this answer
    
yes n - 1 might not be the minimum degree –  user2128547 May 8 '13 at 20:21
    
"might not be of minimum degree" Err no. The Lagrange interpolation formula does give the polynomial of least degree that interpolates through the $k$ points. Each $L_j(a)$ is of degree $k-1$ but their weighted sum $L(a)$ can have smaller degree. Indeed, if $M(a)$ is the polynomial of least degree (assumed to be smaller than $k-1$) that interpolates through the $k$ points, then $L(a)-M(a)$ of degree $k-1$ has $k$ roots $a_1, a_2, \ldots, a_k$ and so must be identically $0$. So the weighted sum $\sum_j b_jL_j(a)$ does have smaller degree than its constituent parts in this case. –  Dilip Sarwate May 8 '13 at 20:46
    
thank you...I understand now! –  user2128547 May 9 '13 at 10:09

Naively, you could construct the interpolating polynomial through the first $t$ points, and see if it passes through the others. If not, increase $t$ by one. By the time $t=k$ you will definitely have one.

share|improve this answer
1  
This is sometimes called Newtonian interpolation. –  Dilip Sarwate May 8 '13 at 20:21
    
thank you for your answer –  user2128547 May 8 '13 at 20:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.