Graphics Programs Reference
In-Depth Information
The realzeroes of polynomials with real coefficients can always becomputedby
one of the methods already described. But ifcomplexroots aretobecomputed, it is
best to use amethod thatspecializes inpolynomials. Here we present amethoddueto
Laguerre, which is reliable and simple to implement.Before proceeding to Laguerre's
method, we must first develop two numerical tools that are needed in any method
capable of determining the zeroes of apolynomial. The first of these is an efficient
algorithm for evaluating a polynomial and its derivatives. The second algorithmwe
needisfor the deflation of apolynomial, i.e.,for dividing the P n ( x ) by x
r , where r is
aroot of P n ( x )
=
0
.
Evaluation of Polynomials
It istempting to evaluate the polynomial in Eq. (4.9)from left to right by the following
algorithm (we assumethat the coefficients are storedinthe array a ):
p=0.0
fori=1:n+1
p=p+a(i)*xˆ(n-i+1)
end
Since x k isevaluatedas x
×
x
×···×
x ( k
1multiplications), we deduce that the
number of multiplications in this algorithmis
1
2 n ( n
1
+
2
+
3
+···+
n
1
=
1)
If n islarge, the number of multiplicationscan be reduced considerablyif weevaluate
the polynomialfromright to left.Foranexample, take
a 1 x 4
a 2 x 3
a 3 x 2
P 4 ( x )
=
+
+
+
a 4 x
+
a 5
which can be rewrittenas
P 4 ( x )
=
a 5 +
x
{
a 4 +
x [ a 3 +
x ( a 2 +
xa 1 )]
}
We now see that an efficientcomputational sequence for evaluating the poly-
nomial is
P 0 ( x )
=
a 1
P 1 ( x )
=
a 2 +
xP 0 ( x )
P 2 ( x )
=
a 3 +
xP 1 ( x )
=
a 4 +
P 3 ( x )
xP 2 ( x )
P 4 ( x )
=
a 5
+
xP 3 ( x )
Search WWH ::




Custom Search