A summer program and resource for middle school students
showing high promise in mathematics

Useful Computational Methods


The Regula Falsi Method for Square-roots

Regula Falsi is a linearly convergent algorithm like the Bisection method but faster. One could ask: between two methods that are each linearly convergent, how can one of them be faster? The answer is clear by noting that given two straight lines with different slopes, precisely one of them has a greater slope than the other.

Regula Falsi works very similar to the bisection method: it starts with a change of sign interval [a,b] containing the root, and each step of the method tries to make this interval smaller. The methods differ only in how the next approximation is generated from the endpoints a and b. Suppose we wish to find the value of √5. Noting that 22 = 4 < 5 < 9 = 32, we let a = 2 and b = 3. √5 is the root of the polynomial x2 - 5. That is, √5 is the value of x that makes x2 - 5 equal zero. In other words, it is the x-value where the graph of x2 - 5 crosses the x-axis. Now, let us see where the crossing occurs relative to x = 2 and x = 3. Since 22 - 5 = 4 - 5 = -1 and 32 - 5 = 9 - 5 = 4, the function-value changes sign from -ve at x = 2 to +ve at x = 3. In other words, [2,3] is a change-of-sign interval. But f(x) = x2-5 is a polynomial and hence a continuous function. It is a property of a continuous function that its graph crosses the x-axis at least once in a change-of-sign interval. So we would expect our graph to cross between x = 2 and x = 3. Moreover, since the function value is only -1 at x = 2 but +4 at x = 3, we would expect the crossing to be nearer x = 2 than to x = 3. This is the information used by the Regula Falsi method.

Regula Falsi means false position. Why false position? Well, if the graph were a straight line between the points (2,-1) and (3, 4), then the line would have crossed at x = (2(3) + 5)/(2+3) (why?). The Regula Falsi method assumes that the graph is a straight line for very small intervals. This is a reasonable assumption since very small segments of the graph look almost straight. As a result, as the change-of-sign interval becomes smaller, the crossing point of the straight line gets closer to the crossing point of the graph. The straight line joining the points corresponding to x = 2 and x = 3 on the graph is a chord of the graph. The position of the crossing of the chord is a false position of the crossing of the graph - hence the name of Regula Falsi. However, the position where the chord crosses is closer to the crossing point of the graph than either of the end-points is to the crossing point of the graph. Hence, using the crossing point of the chord to decide on the next interval makes sense. Let us look at the decision step for choosing the next interval. Let [L,H] be an interval so that L2 < Q while H2 > Q. Then the graph crosses the x-axis between L and H. We will prove later that the position where the chord crosses the x-axis is given by
c = (LH + Q)/(L + H).      ----- Equation (1)
Note that if L and H are very close to √Q, then c @ (√Q √Q + Q)(√Q + √Q) = 2Q/(2√Q) = √Q.
How do we find the next interval?
The decision step:
If c2 < Q, let L = c.
If c2 > Q, let H = c.
We will show later that the sequence of c's thus obtained converges to √Q.

EXAMPLE:
Let us apply the method to find √ 5. We get the following table of values.

L H c c2
2 3 2.2 4.84 < 5
2.2 3 2.32 5.38 > 5
2.2 2.32 2.2354 4.997 < 5
2.2354 2.32 2.23606 4.999945 < 5
2.23606 2.32 --- ---

Notice that after a few iterations, the right end-point of the intervals is fixed at 2.32 and the left end-point is moving closer and closer to √5. If you compare this table with the table for approximations to √5 given in the Bisection Method, for same starting values for L and H, you will find that the Regular Falsi method is faster. How much faster? In other words, what is the speed of convergence?

The speed of of convergence
The speed of of convergence is given by the size of the error at the (n+1)-th step as compared to that at the n-th step, for sufficiently large n. "Sufficiently large n" means that there there exists an integer N such that from N onwards the error behaves as specified. The error at the n-th step, denoted by en, is defined as ï√Q - cnï, where cn is the value of c, the approximation to √Q, at the n-th step. Then the speed of convergence is defined in terms of a positive real number k so that en+1/(en)k = A, where A is a constant. In other words, en+1 is proportional to enk. For the Regula Falsi Method, k = 1 and for finding square-roots, A = 1/(2√Q). Try to work this out from the ratio ï√Q - cn+1ï/ï√Q - cnï by substituting for cn+1 and cn. Thus, for instance, if Q = 25, A = 1/(2√25) = 1/10, so that the error of the approximation becomes roughly a tenth of the error in the preceding step, for sufficiently large n. In other words, the difference between √Q and the approximation to √Q at the (n+1)-th step will have one more zero after the decimal point than at the n-th step, for sufficiently large n. This means that the growth of the zeros after the decimal point in en is slow. But it is still faster than the Bisection Method which also has k =1, but en+1/en = 1/2. That is to say, the number of zeros in the error in the Bisection Method is guaranteed to increase by one after every four steps, for sufficiently large n.

Using the Regula Falsi method to find the zeros of functions
We have described above the use of the Regula Falsi method to find square-roots. However, the method applies to more than finding square-roots. Finding √Q is the same as finding the zero of the function f(x) = x2 - Q. A value of x that makes f(x) equal to zero will be a root of the equation x2 - Q = 0. The graph of f(x) = x2 - Q is a parabola, which is an example of a continuous curve. So f(x) = x2 - Q is a continuous function. A precise definition of a continuous function is encountered in introductory calculus courses. The Regula Falsi method applies to finding the zeros of continuous functions. First we bracket the root. That is, we find two numbers a and b so that [a,b] encloses the root. Then we find the point (c,0) on the x-axis where the straight line L joining the points (a,f(a)) and (b,f(b)) crosses the x-axis. To find the value of c, we evaluate the slope m of the line L in two ways and equate them:
m = (f(b)-f(a))/(b-a) using the points (a,f(a)) and (b,f(b)).
Also, m = (0-f(b))/c-b, using the points (c,0) and (b,f(b)).
Equating the two values of m, we get
c = (af(b)-bf(a))/(f(b)-f(a)).
Let a0 = a, b0 = b, and c0 = c.
There are three possibilities.
If f(c) = 0, c is the root, and we are done.
If f(c).f(a) < 0, the root lies in [a,c]. Let b1 = c
If f(c).f(b) < 0, the root lies in [c,b]. Let a1 = c
Let cn = (anf(bn)-bnf(an))/(f(bn)-f(an)) ---- Equation (2)
By the Nested Intervals Property of Real Numbers, the sequence of nested intervals [an, bn] converges to a unique point. Since each of the intervals [an, bn] contains both cn and the zero of f, this unique point must be the zero of f.
It can be shown that the error at the n+1-st step is related to the error in the n-th step by the expression
en+1/en = A, where A is a constant depending on f. This shows that the sequence {cn} converges linearly to the root. Often, one of the end-points stays fixed and the other marches toward the root as n increases, as in the animation.

For finding the square-root of √5, f(x) = x2-5. Substituting in Equation (2), we get Equation (1). Since cn goes to √Q as n ® ¥, a computer program must use a termination point by stipulating that the program stop once en reaches a desired value.

Ü   BACK

 

MathPath - "BRIGHT AND EARLY"



Send suggestions to webmaster@mathpath.org
Copyright © 2001-   MathPath
Last updated - January 04, 2004