Roots of Polynomials

Roots of Polynomials

Antony Jameson

Department of Aeronautics and Astronautics, Stanford University, Stanford, California, 94305

Roots of Polynomials

1. Evaluation of polynomials and derivatives by nested multiplication 2. Approximate location of roots 3. Bernoulli's method 4. Newton's method 5. Bairstow's method

1

1 Evaluation of polynomials

Let Pn(x) = a0xn + a1xn-1 . . . + an. To calculate Pn() use nesting. b0 = a0

b1 = b0 + a1 = a0 + a1 b2 = b1 + a2 = a02 + a1 + a2

??? bn = Pn() If we set Pn(x) = (x - )Qn-1(x) + R0 where R0 = Pn(), then on multiplying out and equating coefficients we find Qn-1(x) = b0xn-1 + b1xn-2 . . . + bn-1, P0 = bn Repeating the division we have Qn-1(x) = (x - )Qn-2(x) + R1 where R1 = Qn-1(), and thus Pn(x) = (x - )2Qn-2(x) + (x - )R1 + R0.

2

Differentiating with respect to x and setting x =

Pn() = R1.

The procedure can be continued to yield

Pn(x) = Rn(x - )n . . . + R1(x - ) + R0

where

1d Rk = k! dxk Pn(x) x=

The evaluation of the coefficients is indicated by the array

a0 b0 c0 ? ? ? a1 b1 c1 ? ? ? ... an-2 bn-2 cn-2 an-1 bn-1 R1 an R0

Rn Rn-1

where any entry outside the 1st row and column is found by multiplying the entry above by and adding the entry to the left

ck = ck-1 + k etc.

3

Nested multiplication (Horner's rule) for polynomial Let

P3(z) = a0z3 + a1z2 + a2z + a3 = ((a0z + a1)z + a2) z + a3

To sum pn(z) let

Then Also we have Division theorem

b0 = a0 b1 = a1 + b0z bi = ai + bi-1z

...

pn(z) = bn

p(x) x

- -

p(z) z

=

n-1

bixn-1-i

i=0

4

Denote right side by qn-1(x)

n-1

n-1

(x - z)qn-1(x) =

bixn-i - bizxn-i-1

i=0

i=0

n

=

(bi - bi-1z)xn-i + b0xn - bn

i=1 n

=

aixn-i + a0xn - p(z)

i=1

= p(x) - p(z)

Note also that where the bi are evaluated for pn(z)

qn-1(z) = pn(z)

since differentiating

(x - z)qn-1(x) = pn(x) - pn(z)

gives

qn-1(x) + (x - z)qn-1(x) = pn(x)

We can sum qn-1(z) by the same rule

c0 = b0

ci = bi + zci-1 ???

qn-1(z) = cn-1 5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download