Polynomials, remainder theorem and Lagrange interpolation

By Olof Sisask (P3033) on Wednesday, May 16, 2001 - 11:30 pm :

I'm having a bit of trouble with a STEP question (1997 STEP II, Question 4 part ii). The question reads something like this:

Find a polynomial

P (x)

of degree

n + 1

, where

n

is a positive integer, such that when

P (x)

is divided by

(x - a)

, the remainder is

a

, for

0 \leq a \leq n

As I understand it, this means that

$P (x) = (x - a) \times Q_{m} (x) + a$

(with a different $Q$ for different $a$ ).

Is this right? If so, then

let $x = a$

$P (a) = a$

So we know that $P (0) = 0$ , $P (1) = 1$ , ..., $P (n) = n$ .

If we then let $P (x) = b x^{n + 1} + c x^{n} + \dots + y x + z$ , we find that $z = 0$ , and get the following simultaneous equations:

$P (1) = 1 = b + c + \dots + y$

$P (2) = 2 = b . 2^{n + 1} + c . 2^{n} + \dots + 2 y$

...

$P (n) = n = b n^{n + 1} + c n^{n} + \dots + n y$

$1 = b + c + \dots + y$

$1 = b . 2^{n} + c . 2^{n - 1} + \dots + y$

...

$1 = b n^{n} + c n^{n - 1} + \dots + y$

Do these equations have asolution besides $b = c = \dots = w = 0$ , and $y = 1$ ? This gives $P (x) = x$ , which isn'tterribly helpful.
I think I've made a mistake somewhere along the lines, probably something very fundamental, but I can't quite spot it at the moment. Can anyone help me spot it?

Thanks,
Olof

By Michael Doré (Md285) on Thursday, May 17, 2001 - 12:05 am :

Hi Olof,

In general if you ever find yourself tackling n horrible simultaneous equations in STEP, or indeed anything which is very algebraically messy, it probably means a different approach is required. I won't tell you how to do it, but I'll give a clue. Consider the function P(x) - x. What value does this function take for x = 0,1,...,a?

By Anonymous on Thursday, May 17, 2001 - 12:11 am :

I suppose a is integral? Consider P(x)-x...

By Olof Sisask (P3033) on Thursday, May 17, 2001 - 05:10 pm :

Thanks Michael and Anon - I'll have a look.

Olof

By Olof Sisask (P3033) on Sunday, May 20, 2001 - 01:16 pm :

I think I must be doing something wrong - I'm getting strange answers. I keep ending up with P(x) = x, which is obviously not right - any further hints?

Cheers,
Olof

By William Astle (Wja24) on Sunday, May 20, 2001 - 02:51 pm :

I think this is something you just have to see - once you know the trick you'll kick yourself.

If we divide P by a linear factor x-m then we have:

P(x) = (x-m)q_m (x) + r_m (x)

for quotient and remainder polynomials q and r respectively.

We want r(m)=m for each integral m between 0 and n, that is for each such m there exists q_m (x) with:

P(x) = (x-m)q_m (x) + m

whence for each such m:

(x-m) | P(x)-m

Can you do the rest?

By Tom Hardcastle (P2477) on Sunday, May 20, 2001 - 09:38 pm :

Can't you just do it with a Lagrange interpolation polynomial?

By Michael Doré (Michael) on Sunday, May 20, 2001 - 10:08 pm :

That's pretty much the same isn't it?

All you need to know is that the polynomial (x - a₁ )(x - a₂ )...(x - a_n ) is 0 at x = a₁ ,a₂ ,...,a_n .
Apply to P(x) - x...

By Tom Hardcastle (P2477) on Sunday, May 20, 2001 - 11:21 pm :

Yes, but it doesn't require me to have an original thought. :)

By Olof Sisask (P3033) on Sunday, May 20, 2001 - 11:25 pm :

What's a Lagrange interpolation polynomial? I'm still being pretty braindead at the moment, I'll have another think tomorrow. I think the problem lies with what the question actually means - I'm not quite sure I understand it fully.

I can see that a polynomial such as

x (x - 1) (x - 2) \dots (x - n) + x

gives

x

for

0 \leq x \leq n

(integral

x

), which was one of my first approaches, but I can't quite figure out to work it into the problem. It's probably very simple, so I'll return to that approach in the morning.
Thanks,
Olof

By William Astle (Wja24) on Monday, May 21, 2001 - 09:11 am :

But if you can see that, you have done the problem, because that's the answer :-)

It satisfies P(m) = r(m) + m for each m between 0 and n.

By Michael Doré (Michael) on Monday, May 21, 2001 - 09:23 am :

I think they're expecting you to assume a is an integer (or in William's notation, m is an integer).

By Olof Sisask (P3033) on Monday, May 21, 2001 - 09:57 am :

Is that the answer? [Runs off, kicking himself repeatedly, screaming D'oh!]
You have no idea how long this problem has been bugging me... :)

I think the problem laid with the fact that I wasn't quite sure what conditions the answer had to satisfy, and I'm afraid I'm still not sure. With the P(x) above, won't the remainder when P(x) is divided by (x-m) be x, whereas we want it to be m regardless of the value of x?

Also, if you wouldn't mind, what's a Lagrange interpolation polynomial? Sounds interesting.

Thanks,
Olof

By Olof Sisask (P3033) on Monday, May 21, 2001 - 09:58 am :

Yeah sorry Michael - I just found the question, and it specifies that a is an integer.

By Michael Doré (Michael) on Monday, May 21, 2001 - 01:27 pm :

I'm not totally sure, but I think Lagrange interpolation is something along the lines of what follows. I'm sure Tom or William will come up with a better explanation if necessary.

Suppose we want to find a polynomial $P (x)$ of degree less than $n$ which passes through $n$ points, namely $(x_{1}, y_{1})$ , $(x_{2}, y_{2})$ , ..., $(x_{n}, y_{n})$ where $x_{i}$ are all distinct.

Firstly, there can only be one such $P (x)$ . Why? Well suppose $P_{1} (x)$ and $P_{2} (x)$ are both polynomials of degree less than $n$ , passing through $(x_{1}, y_{1})$ , ..., $(x_{n}, y_{n})$ . Consider the function

$D (x) = P_{1} (x) - P_{2} (x)$

Note that $D$ is a polynomial of degree less than $n$ . It satisfies:

$D (x_{1}) = y_{1} - y_{1} = 0$

$D (x_{2}) = y_{2} - y_{2} = 0$

... $D (x_{n}) = y_{n} - y_{n} = 0$

Therefore $D (x)$ has $n$ roots, namely $x_{1}$ , $x_{2}$ , ..., $x_{n}$ . Therefore, by the factor theorem, we know:

$D (x) = A (x - x_{1}) (x - x_{2}) \dots (x - x_{n})$

for some constant $A$ . But the degreeof $D (x)$ is less than $n$ , so $A = 0$ , so $D (x) = 0$ so $P_{1} (x) = P_{2} (x)$ .

Therefore there can only be one polynomial $P (x)$ of degree less than $n$ passing through $(x_{1}, y_{1})$ , $(x_{2}, y_{2})$ , ..., $(x_{n}, y_{n})$ if $x_{i}$ are all distinct. It is just a question offinding it.

Well oneway of constructing such a polynomial would be to find polynomials $R_{1} (x)$ , $R_{2} (x)$ , ..., $R_{n} (x)$ of degree less than $n$ such that:

$R_{i} (x_{i}) = y_{i}$

$R_{i} (x_{j}) = 0$ if $i \neq j$ .

Because then if we define $P (x) = R_{1} (x) + R_{2} (x) + \dots + R_{n} (x)$ then $P$ is of degree less than $n$ and

$P (x_{1}) = R_{1} (x_{1}) + R_{2} (x_{1}) + \dots + R_{n} (x_{1}) = y_{1} + 0 + 0 + \dots + 0 = y_{1}$

$P (x_{2}) = R_{1} (x_{2}) + R_{2} (x_{2}) + \dots + R_{n} (x_{2}) = 0 + y_{2} + 0 + \dots + 0 = y_{2}$

...

$P (x_{n}) = R_{1} (x_{n}) + R_{2} (x_{n}) + \dots + R_{n} (x_{n}) = 0 + 0 + 0 + \dots + y_{n} = y_{n}$

So $P (x) = R_{1} (x) + R_{2} (x) + \dots + R_{n} (x)$ would then be what we're looking for.

The only question is how to find $R_{i} (x)$ . We want it to be a polynomial of degree less than $n$ which is zero when $x = x_{j}$ unless $i = j$ in which case $R_{i} (x_{j}) = y_{i}$ .

Well as $R_{i}$ is zero for $x = x_{j}$ ( $i \neq j$ ) we know $R_{i}$ is of the form:

$F_{i} (x) = A \underset{j \neq i}{Π} (x - x_{j})$

(which is of degree $n - 1$ as $A$ is a constant).

This is indeed 0 for $x = x_{j}$ ( $i \neq j$ ). And $R_{i} (x_{i}) = y_{i}$ if and only if:

$y_{i} = A \underset{j \neq i}{Π} (x_{i} - x_{j})$

As $x_{i} \neq x_{j}$ it is clear that we desire:

$A = y_{i} / \underset{j \neq i}{Π} (x_{i} - x_{j})$

Therefore $R_{i} (x) = y_{i} \underset{j \neq i}{Π} (x - x_{j}) / \underset{j \neq i}{Π} (x_{i} - x_{j})$ .

From there you can calculate $P (x)$ as:

$P (x) = \sum_{i = 1}^{n} y_{i} \underset{j \neq i}{Π} (x - x_{j}) / \underset{j \neq i}{Π} (x_{i} - x_{j})$

which does indeed have degree less than $n$ , and passes through $(x_{1}, y_{1})$ , ..., $(x_{n}, y_{n})$ .

By Michael Doré (Michael) on Monday, May 21, 2001 - 02:15 pm :

On the subject of the original question; the remainder when the polynomial P(x) is divided by the polynomial Q(x) is defined as S(x) where S(x) is a polynomial of degree less than that of P(x) satisfying:

Write P(x) = Q(x)R(x) + S(x)
where R(x) is a polynomial.
(Exercise: show that there is a unique S(x) satisfying this condition.)

So for example, if we want to divide

P(x) = x(x - 1)(x - 2)...(x - n) + x

by (x - 2) (say) what this means is that we write:

P(x) = (x - 2)[x(x-1)(x-3)...(x-n)] + (x - 2) + 2
P(x) = (x - 2)[x(x-1)(x-3)...(x-n) + 1] + 2

Note that 2 is now of degree less than (x - 2) so 2 is the remainder. Likewise, the remainder when P(x) is divided by (x - i) is i for any integral i in [0,n], if P(x) is chosen as x(x - 1)(x - 2)...(x - n) + x.

Another useful fact (easy to prove) is that the remainder when P(x) is divided by a linear factor (x - a) is simply P(a).

By Olof Sisask (P3033) on Monday, May 21, 2001 - 04:41 pm :

That clears it all up, thanks a lot Michael. It must have taken you a while to type all that out - I really appreciate it. I think the remainder thing you mention at the end is actually the first part of the question!

Regards,
Olof