EMT 669

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

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.567From 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.061From 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

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.0000063The 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

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

Asaithambi, N.S. (1995).

Swokowski, Earl W. (1990)