Transcript Polynomials - University of California, Berkeley

Polynomials
UC Berkeley
Fall 2004, E77
http://jagger.me.berkeley.edu/~pack/e77
Copyright 2005, Andy Packard. This work is licensed under the Creative Commons Attribution-ShareAlike
License. To view a copy of this license, visit http://creativecommons.org/licenses/by-sa/2.0/ or send a letter to
Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.
Polynomials
An nth order polynomial in variable x is written as
p( x)  a1 x  a2 x
n
n 1
   an x  an1
It is natural to associate a row vector Ap with p, namely
Ap  a1 a2  an an1 
A few examples: Row vector representations of
p ( x)  6 x  5 x  3 x  7
3
2
q ( x)  9 x 2  2 x  4
are
>> Ap = [ 6 5 -3 7 ];
“leading zeros”
>> Aq = [ 9 -2 4 ];
But [ 0 0 0 9 -2 4 ] also represents q…
Functions operating on polynomials
Let’s spend the lecture writing several useful functions for
polynomial manipulation, including
– Polynomial addition
– Polynomial subtraction
– Polynomial multiplication
– Polynomial evaluation (use polyval)
– Plotting the graph of a polynomial
– Roots of a polynomial (use roots)
The inputs to the functions will be row vectors, representing
polynomials.
Polynomial Addition
Adding two polynomials requires adding their coefficients.
The sum of
a1 x  a2 x
n
n 1
   an x  an1
b1 x n  b2 x n1    bn x  bn1
is simply
(a1  b1 ) x n  (a2  b2 ) x n1    (an  bn ) x  (an1  bn1 )
In terms of the row-vector representation of the polynomials,
we simply add them, element-by-element.
But the row vectors may be different lengths, and we need
to “align” them.
Polynomial Addition
The row vector representations of
a ( x)  6 x 3  5 x 2  3 x  7
b( x)  9 x 2  2 x  4
are
>> A = [ 6
>> B = [ 9
5
2
-3 7 ];
-4 ];
but obviously
>> C = A + B
will give an error. We need to “pad” B with a zero
>> C = A + [ 0
B ];
or add B only to the correct elements of A.
>> C = A;
>> C(2:end) = C(2:end) + B;
addpoly.m
function C = addpoly(A,B)
% This adds two row vectors, interpreting
% them as polynomials.
% Should check that A and B are row vectors
lenA = length(A);
lenB = length(B);
Inserting the right number of
if lenA==lenB
leading zeros to A
C = A+B;
elseif lenA<lenB
C = [zeros(1,lenB-lenA) A] + B;
else
C = A + [zeros(1,lenA-lenB) B];
end
subpoly.m
function C = subpoly(A,B)
% This subtracts two row vectors,
% interpreting them as polynomials.
% Should check that A and B are row vectors
C = addpoly(A,-B);
Polynomial Multiplication
Multiplying
a(x) = 6x3 + 5x2 – 3x + 7
b(x) = 3x2 + 2x – 4
Express the product as
(6x3 + 5x2 – 3x + 7)(3x2 + 2x – 4) =
(6x3 + 5x2 – 3x + 7)*3x2
+ (6x3 + 5x2 – 3x + 7)*2x
+ (6x3 + 5x2 – 3x + 7)*(-4)
The result is 5th order, so we need a 1-by-6 array for the result
C = [
0
0
0
0
0
0 ]
Polynomial Multiplication
Multiplying
a(x) = 6x3 + 5x2 – 3x + 7
b(x) = 3x2 + 2x – 4
A = [6 5 -3 7]
B = [3 2 -4]
Express the product as
(6x3 + 5x2 – 3x + 7)(3x2 + 2x – 4) =
(6x3 + 5x2 – 3x + 7)*3x2
+ (6x3 + 5x2 – 3x + 7)*2x
+ (6x3 + 5x2 – 3x + 7)*(-4)
The result is 5th order, so we need a 1-by-6 array for the result
C = [
0
0
0
0
0
0 ]
Polynomial Multiplication
Multiplying
a(x) = 6x3 + 5x2 – 3x + 7
b(x) = 3x2 + 2x – 4
A = [6 5 -3 7]
B = [3 2 -4]
Express the product as
(6x3 + 5x2 – 3x + 7)(3x2 + 2x – 4) =
(6x3 + 5x2 – 3x + 7)*3x2 add A*B(1) to C(1:4)
+ (6x3 + 5x2 – 3x + 7)*2x
+ (6x3 + 5x2 – 3x + 7)*(-4)
The result is 5th order, so we need a 1-by-6 array for the result
C = [
0
0
0
0
0
0 ]
Polynomial Multiplication
Multiplying
a(x) = 6x3 + 5x2 – 3x + 7
b(x) = 3x2 + 2x – 4
A = [6 5 -3 7]
B = [3 2 -4]
Express the product as
(6x3 + 5x2 – 3x + 7)(3x2 + 2x – 4) =
(6x3 + 5x2 – 3x + 7)*3x2 add A*B(1) to C(1:4)
+ (6x3 + 5x2 – 3x + 7)*2x
+ (6x3 + 5x2 – 3x + 7)*(-4)
The result is 5th order, so we need a 1-by-6 array for the result
C = [ 18
15
-9
21
0
0 ]
Polynomial Multiplication
Multiplying
a(x) = 6x3 + 5x2 – 3x + 7
b(x) = 3x2 + 2x – 4
A = [6 5 -3 7]
B = [3 2 -4]
Express the product as
(6x3 + 5x2 – 3x + 7)(3x2 + 2x – 4) =
(6x3 + 5x2 – 3x + 7)*3x2 add A*B(1) to C(1:4)
+ (6x3 + 5x2 – 3x + 7)*2x
add A*B(2) to C(2:5)
+ (6x3 + 5x2 – 3x + 7)*(-4)
The result is 5th order, so we need a 1-by-6 array for the result
C = [ 18
15
-9
21
0
0 ]
Polynomial Multiplication
Multiplying
a(x) = 6x3 + 5x2 – 3x + 7
b(x) = 3x2 + 2x – 4
A = [6 5 -3 7]
B = [3 2 -4]
Express the product as
(6x3 + 5x2 – 3x + 7)(3x2 + 2x – 4) =
(6x3 + 5x2 – 3x + 7)*3x2 add A*B(1) to C(1:4)
+ (6x3 + 5x2 – 3x + 7)*2x
add A*B(2) to C(2:5)
+ (6x3 + 5x2 – 3x + 7)*(-4)
The result is 5th order, so we need a 1-by-6 array for the result
C = [ 18
27
1
15
14
0 ]
Polynomial Multiplication
Multiplying
a(x) = 6x3 + 5x2 – 3x + 7
b(x) = 3x2 + 2x – 4
A = [6 5 -3 7]
B = [3 2 -4]
Express the product as
(6x3 + 5x2 – 3x + 7)(3x2 + 2x – 4) =
(6x3 + 5x2 – 3x + 7)*3x2 add A*B(1) to C(1:4)
+ (6x3 + 5x2 – 3x + 7)*2x
add A*B(2) to C(2:5)
+ (6x3 + 5x2 – 3x + 7)*(-4) add A*B(3) to C(3:6)
The result is 5th order, so we need a 1-by-6 array for the result
C = [ 18
27
1
15
14
0 ]
Polynomial Multiplication
Multiplying
a(x) = 6x3 + 5x2 – 3x + 7
b(x) = 3x2 + 2x – 4
A = [6 5 -3 7]
B = [3 2 -4]
Express the product as
(6x3 + 5x2 – 3x + 7)(3x2 + 2x – 4) =
(6x3 + 5x2 – 3x + 7)*3x2 add A*B(1) to C(1:4)
+ (6x3 + 5x2 – 3x + 7)*2x
add A*B(2) to C(2:5)
+ (6x3 + 5x2 – 3x + 7)*(-4) add A*B(3) to C(3:6)
The result is 5th order, so we need a 1-by-6 array for the result
C = [ 18
27
-23 -5 26 28 ]
Do this for every element of B (for loop)
A*B(2)
C(2:2+length(A)-1)
A*B(3) + C(1:1+length(A)-1)
C(3:3+length(A)-1)
A*B(1)
A*B(i)
C(i:i+length(A)-1)
multpoly.m
function C = multpoly(A,B)
% This computes the product of the inputs,
% interpreting them as polynomials.
lenA = length(A);
lenB = length(B);
lenC = lenA + lenB - 1;
C = zeros(1,lenC);
for i=1:lenB
idx = i:i+lenA-1;
C(idx) = A*B(i) + C(idx);
end
Polynomial Evaluation
Use the Matlab function polyval
>> A = [ 1
1 -2 ];
>> x = 2.6;
>> y = polyval(A,x)
polyval works for vectors too
>> x = linspace(-3,3,200);
>> y = polyval(A,x);
>> plot(x,y)
Roots of Polynomials
An nth order polynomial (with nonzero leading coefficient)
p( x)  a1 x  a2 x
n
n 1
   an x  an1
It is a fundamental theorem of algebra that the equation
p( x)  0
has n solutions, called the roots of p. Label these roots r1,
r2,…, rn. Another way to say this is that p can be factored
into the for
p( x)  a1 ( x  r1 )( x  r2 )( x  rn )
Even if the coefficients of p are real numbers, the roots may
be complex.
The roots command
The command roots computes the roots of a polynomial,
and returns them as a column vector.
Compute the roots of
p ( x)  x  x  2
2
q ( x)  x  3 x  5
2
v( x)  2 x  x  4 x  x  3
4
3
2
>> roots([1 1 -2])
>> roots([1 3 5])
>> roots([2 -1 4 1 -3])