CS 70 Discrete Mathematics for CSSpring 2008 David Wagner Note 10PolynomialsRecall from your high school math that a polynomial in a single variable is of the form p(x) = adxd+ad−1xd−1+ ... + a0. Here the variable x and the coefficients aiare usually real numbers. For example,p(x) = 5x3+ 2x+ 1, is a polynomial of degree d = 3. Its coefficients are a3= 5, a2= 0, a1= 2, and a0= 1.Polynomials have some remarkably simple, elegant and powerful properties, which we will explore in thisnote.First, a definition: we say that a is a root of the polynomial p(x) if p(a) = 0. For example, the degree2 polynomial p(x) = x2− 4 has two roots, namely 2 and −2, since p(2) = p(−2) = 0. If we plot thepolynomial p(x) in the x-y plane, then the roots of the polynomial are just the places where the curve crossesthe x axis:We now state two fundamental properties of polynomials that we will prove in due course.Property 1: A non-zero polynomial of degree d has at most d roots.Property 2: Given d + 1 pairs (x1,y1),...,(xd+1,yd+1), with all the xidistinct, there is a unique polynomialp(x) of degree (at most) d such that p(xi) = yifor i = 1, 2, . . .,d + 1.Let us consider what these two properties say in the case that d = 1. A graph of a linear (degree 1) polynomialy = a1x+ a0is a line. Property 1 says that if a line is not the x-axis (i.e. if the polynomial is not y = 0), thenit can intersect the x-axis in at most one point.CS 70, Spring 2008, Note 10 1Property 2 says that two points uniquely determine a line.Polynomial InterpolationProperty 2 says that two points uniquely determine a degree 1 polynomial (a line), three points uniquelydetermine a degree 2 polynomial, four points uniquely determine a degree 3 polynomial, and so on. Givend +1 pairs (x1,y1),...,(xd+1,yd+1), how do we determine the polynomial p(x) = adxd+... + a1x+ a0suchthat p(xi) = yifor i = 1 to d + 1? We will give two different efficient algorithms for reconstructing thecoefficients a0,...,ad, and therefore the polynomial p(x). Because these algorithms always work, this willtake us partway towards proving that Property 2 is true.In the first method, we write a system of d + 1 linear equations in d + 1 variables: the coefficients of thepolynomial a0,...,ad. The ith equation is: adxdi+ ad−1xd−1i+ ...+ a0= yi.Since xiand yiare constants, this is a linear equation in the d + 1 unknowns a0,...,ad. Now solving theseequations gives the coefficients of the polynomial p(x). For example, given the 3 pairs (−1, 2), (0, 1), and(2,5), we will construct the degree 2 polynomial p(x) which goes through these points. The first equationsays a2(−1)2+ a1(−1) + a0= 2. Simplifying, we get a2− a1+ a0= 2. Applying the same technique to thesecond and third equations, we get the following system of equations:a2− a1+ a0= 2a0= 14a2+ 2a1+ a0= 5Substituting for a0and multiplying the first equation by 2 we get:2a2− 2a1= 24a2+ 2a1= 4CS 70, Spring 2008, Note 10 2Then, adding down we find that 6a2= 6, so a2= 1, and plugging back in we find that a1= 0. Thus, we havedetermined the polynomial p(x) = x2+1. To do this method more carefully, we must show that the equationsdo have a solution and that it is unique. This involves showing that a certain determinant is non-zero. Wewill leave that as an exercise, and turn to the second method.The second method is called Lagrange interpolation: Let us start by solving an easier problem. Supposethat we are told that y1= 1 and yj= 0 for 2 ≤ j ≤ d + 1. Now can we reconstruct p(x)? Yes, this is easy!Consider q(x) = (x− x2)(x− x3)···(x− xd+1). This is a polynomial of degree d (the xi’s are constants, andx appears d times). It’s easy to see that q(xj) = 0 for 2 ≤ j ≤ d + 1. But what is q(x1)? Well, q(x1) =(x1−x2)(x1−x3)···(x1−xd+1), which is some constant that’s different from 0 (since the xiare all distinct).Thus if we let p(x) = q(x)/q(x1) (dividing is ok since q(x1) 6= 0), we have the polynomial we are lookingfor. For example, suppose you were given the pairs (1, 1), (2,0), and (3, 0). Then we can construct thedegree d = 2 polynomial p(x) by letting q(x) = (x − 2)(x − 3) = x2− 5x+ 6, and q(x1) = q(1) = 2. Thus,we can now construct p(x) = q(x)/q(x1) = (x2− 5x+ 6)/2.Of course the problem is no harder if we single out some arbitrary index i instead of 1. In other words, ifwe want to find a polynomial such that yi= 1 and yj= 0 for j 6= i, we can do that. Let us introduce somenotation: let us denote by ∆i(x) the degree d polynomial that goes through these d+ 1 points, i.e., ∆i(xi) = 1and ∆i(xj) = 0 when j 6= i. Then∆i(x) =∏j6=i(x− xj)∏j6=i(xi− xj).Let us now return to the original problem. Given d + 1 pairs (x1,y1),...,(xd+1,yd+1), we first construct thed + 1 polynomials ∆1(x),...,∆d+1(x). Now the polynomial we are looking for isp(x) =d+1∑i=1yi∆i(x).Why does this work? First notice that p(x) is a polynomial of degree d as required, since it is the sum ofpolynomials of degree d. And when it is evaluated at xi, d of the d + 1 terms in the sum evaluate to 0 andthe ith term evaluates to yitimes 1 as required.For instance, suppose d = 2 and x1= 1, x2= 2, x3= 3. Then∆1(x) =(x− 2)(x− 3)(1− 2)(1− 3)=(x− 2)(x− 3)2∆2(x) =(x− 1)(x− 3)(2− 1)(2− 3)=(x− 1)(x− 3)−1∆3(x) =(x− 1)(x− 2)(3− 1)(3− 2)=(x− 1)(x− 2)2.Consequently the polynomial p(x) we are looking for can be expressed as p(x) = y1∆1(x) + y2∆2(x) +y3∆3(x).Property 2 and UniquenessWe have shown how to find a polynomial p(x) through any given d+1 points. This proves part of Property 2(the existence of the polynomial). How do we prove the second part, that the polynomial is unique? Supposefor contradiction that there is another polynomial q(x) that also passes through the d + 1 points. NowCS 70, Spring 2008, Note 10 3consider the polynomial r(x) = p(x) − q(x). This is a non-zero polynomial of degree at most d. So byProperty 1 it can have at most d roots. But on the other hand r(xi) = p(xi)− q(xi) = 0 for i = 1, . . . , d + 1, sor(x) has d + 1 distinct roots. Contradiction. Therefore p(x) is the unique polynomial that satisfies the d + 1conditions.Property 1Now let us turn to Property 1. We will prove this property in two steps.Theorem: a is a root of p(x) if and only if the polynomial x− a divides p(x).Proof: Dividing p(x) by the polynomial x− a yieldsp(x) = (x− a)q(x) + r(x)for some polynomials q(x) and r(x), where q(x) is the quotient and r(x) is the
View Full Document
Unlocking...