Lori Pearman
EMT 669
Root - Finding
The zeros of a polynomial f(x) are the solutions of the equation f(x)
= 0. Calculators and computers can be used to find or approximate zeros.
However, before using a computer, it is worth knowing what type of zeros
to expect.
The Fundamental Theorem of Algebra states that if f(x) has positive degree
and complex coefficients, then f(x) has at least one complex zero.
Another important theorem from pre-calculus states that if f(x) is a polynomial
of degree n >0, then there exist n complex numbers C1, C2, . . . ,Cn
such that
f(x) = a(x - C1)(x - C2) . . . (x - Cn)
where 'a' is the leading coefficient of f(x). Each number Ck is a zero
of f(x).
Note that the numbers C1, C2, . . . ,Cn are not necessarily all different.
If a factor x - c occurs m times in the factorization, then c is a zero
of multiplicity m of f(x).
For example, the polynomial f(x) = (x - 2)(x -4)3(x + 3)2 has three distinct
zeros, 2, 4, and -3. The zero 2 has multiplicity 1, the zero 4 has multiplicity
3, and the zero -3 has multiplicity 2. Note that f(x) has degree 6. The
following is a graph of f(x).
Each zero is an x- intercept of the graph of f.
Now let's look at ways in which we can numerically estimate a root of an
equation. Let f(x) = x3-2x-5. Let's graph this function in Algebra Xpresser.
This graph crosses the x- axis between 0 and 5. Let's zoom in on the graph
from x=0 to x=5 to see more accurately where the root is.
From this graph, we can see that there is a root somewhere between 2 and
2.3. Let's now try to approximate this root using a spread sheet.
x f(x)
2.00 -1.000
2.01 -0.899
2.02 -0.798
2.03 -0.695
2.04 -0.590
2.05 -0.485
2.06 -0.378
2.07 -0.270
2.08 -0.161
2.09 -0.051
2.10 0.061
2.11 0.174
2.12 0.288
2.13 0.404
2.14 0.520
2.15 0.638
2.16 0.758
2.17 0.878
2.18 1.000
2.19 1.123
2.20 1.248
2.21 1.374
2.22 1.501
2.23 1.630
2.24 1.759
2.25 1.891
2.26 2.023
2.27 2.157
2.28 2.292
2.29 2.429
2.30 2.567
From the above chart, we can see that the root is between x=2.09 and x=2.10.
F(x) is close to zero at these values. Also, the sign of f(2.09) is negative
while the sign of f(2.10) is positive. Let's take a look at the graph of
the chart values.
We can now get a more accurate approximation of the root by using a spread
sheet once again with smaller increments for x=2.09 to x=2.10.
x f(x)
2.090 -0.051
2.091 -0.040
2.092 -0.028
2.093 -0.017
2.094 -0.006
2.095 0.005
2.096 0.016
2.097 0.027
2.098 0.039
2.099 0.050
2.100 0.061
From the above chart, we can see that the root is between x=2.094 and x=2.095.
We could continue getting better and better approximations of the root by
continuing to look at increments of smaller intervals.
Another way of numerically estimating a root of an equation is by using
the Bisection Method (explained below).
A root occurs when f(x) = 0. If x lies in an interval [a,b] where f(a) is
negative and f(b) is positive, then we can use this information to find
the root.
Take the midpoint of segment ab, and call it `c'. If f(c) is negative, we
know the root lies in the interval [c,b], and if f(c) is positive, we know
the root lies in the interval [a,c].
When we evaluate f(c), we can determine a smaller interval (either [c,b]
or [a,c]) containing the root. Suppose f(c) is negative, and we get the
new interval [c,b]. We can then take the midpoint of this interval and repeat
the same process. The function evaluated at the endpoints of each new interval
should always have opposite signs.
By continuing the process, we are finding smaller and smaller intervals
containing the root. In a sense, we are "closing in" on the root.
Let's look again at the above example. Solve x3 -2x-5 = 0 for a root in
the interval [2,3]. Start with the interval [a,b], where a = 2 and b = 3.
Note that f(a) is negative and f(b) is positive. The midpoint of this interval
is 2.5.
f(2.5) = 5.625, which is positive. Thus, our next interval is [a,c]. Now
take the midpoint of this interval, and call it C2. C2 = 2.25, and f(2.25)
= 1.8906250 which is positive. Our next interval will be [a,C2].
Repeating this process will get you closer and closer to the root since
the interval containing the root is becoming smaller and smaller. The following
chart demonstrates this. (K is the number of iterations.) Each time, f(a)
is negative and f(b) is positive. C is the midpoint of the interval [a,b],
and C will become our new `a' or `b' in the next iteration depending on
the sign of f(c).
K a b c f(c)
1 2.0000000 3.0000000 2.5000000 5.6250000
2 2.0000000 2.5000000 2.2500000 1.8906250
3 2.0000000 2.2500000 2.1250000 0.3457031
4 2.0000000 2.1250000 2.0625000 -0.351318
5 2.0625000 2.1250000 2.0937500 -0.008942
6 2.0937500 2.1250000 2.1093750 0.1668358
7 2.0937500 2.1093750 2.1015625 0.0785623
8 2.0937500 2.1015625 2.0976563 0.0347143
9 2.0937500 2.0976563 2.0957032 0.0128626
10 2.0937500 2.0957032 2.0947266 0.0019548
11 2.0937500 2.0947266 2.0942383 -0.003495
12 2.0942383 2.0947266 2.0944825 -0.000770
13 2.0944682 2.0947266 2.0945974 0.0005125
14 2.0944682 2.0946045 2.0945364 -0.000169
15 2.0945435 2.0946045 2.0945740 0.0002513
16 2.0945435 2.0945740 2.0945588 0.0000811
17 2.0945435 2.0945587 2.0945511 -0.000004
18 2.0945511 2.0945587 2.0945549 0.0000382
19 2.0945511 2.0945549 2.0945530 0.0000169
20 2.0945511 2.0945530 2.0945521 0.0000063
The interval length decreases from one iteration to the next, "closing
in" on the root which is, correct to 9 decimal places, 2.094551481.
From the computations summarized in the above table, we know that after
20 iterations, the maximum absolute error approximately equals 2.0945530-2.0945521
= 0.0000009.
The bisection method makes no use of the value of f(x) at a particular point
other than to use the sign of f(x) in the selection of an appropriate interval
containing the root. However, it may be helpful to see what the actual value
of f(x) is at particular points. In the above (bisection method) example,
f(2) = -1 and f(3) = 16. From this, we could expect the root to be closer
to x = 2 than to x = 3 (since -1 is closer to 0 than 16 is). So instead
of finding the midpoint of [2,3], let's instead consider a "weighted
average" of 2 and 3. We'll use the regula-falsi method to do
this.
Let [Ak,Bk] be the interval enclosing the root after k-1 iterations. The
regula-falsi method obtains the next approximation x(k) = Ak - (Bk-Ak)f(Ak)/[f(Bk)-f(Ak)].
Call this equation *.
The sign of f(x(k)) may be used to determine whether the root lies in the
interval [Ak,x(k)] or in [x(k),Bk], after which the above equation * may
be applied once again and x(k+1) determined. This may be repeated until
we are satisfied with the approximate root obtained.
x(k) as given by equation * is the point of intersection of the line joining
Ak, f(Ak)) and (Bk, f(Bk)). During each iteration, the regula-falsi method
approximates the root of f(x) = 0 by replacing f(x) with the secant line
joining the points (a, f(a)) and (b,f(b)), where [a,b] is an interval enclosing
the root. See the below picture. (* is the root we're approximating.)
Unlike the bisection method, the regula-falsi method does not produce an
interval of "small" width enclosing the root. Thus, we need "stopping
criteria" ( to tell us when to stop). In the following example, the
termination criteria is x(n)-x(n-1) < x(n), where > 0 is a prescribed
tolerance.
Let's look again at the problem of solving x3-2x-5 = 0 for a root in the
interval [2,3]. Solve for a root using the regula-falsi method. The below
chart shows the result with = 10-6.
k a b c f(c)
1 2.0000000 3.0000000 2.0588235 -0.390800
2 2.0588235 3.0000000 2.0812636 -0.147204
3 2.0812637 3.0000000 2.0896392 -0.054676
4 2.0896392 3.0000000 2.0927396 -0.020203
5 2.0927396 3.0000000 2.0938837 -0.007450
6 2.0938837 3.0000000 2.0943054 -0.002746
7 2.0943055 3.0000000 2.0944609 -0.001011
8 2.0944608 3.0000000 2.0945181 -0.000373
9 2.0945181 3.0000000 2.0945392 -0.000137
10 2.0945392 3.0000000 2.0945470 -0.000050
11 2.0945470 3.0000000 2.0945498 -0.000018
12 2.0945498 3.0000000 2.0945509 -0.000007
The above picture demonstrates what is happening. Note that this method
may be slow if the graph of f(x) has significant curvature between A1 and
B1.
If the root of an equation is not obvious, it can be estimated in several
different ways. Graphing utilities (such as Algebra Xpresser), spread
sheets (such as in Micosoft Excel), and the methods discussed above
are helpful tools for estimating roots.
References
Asaithambi, N.S. (1995). Numerical Analysis: Theory and Practice.
New York: Saunders College Publishing.
Swokowski, Earl W. (1990) Precalculus:Functions and Graphs. Massachusetts:
pws- Kent Publishing Co.
Return to Lori's EMT 669 Page