..Bisection
method.
..Newton's
method.
..Iteration
method
Bisection method.
When f(x) is continuous in the environment of a single root r, then f(x) changes sign through r. There is a small interval [a,b] including r such that f(a).f(b) < 0. Taking the midpoint m of [a,b], there are three possibilities.- f(m) = 0 ; then m is the root r.
- f(m).f(a) < 0 ; then the root r is in [a,m]
- f(m).f(b) < 0 ; then the root r is in [m,b]
Example:
The equation
t3 + 4 t2 - 1 = 0
has a positive root r in [0,1]. f(0)<0 and f(1)>0.Since f(0.5) = 0.125 the root is in [0, 0.5].
Since f(0.25) = -0.73 the root is in [0.25, 0.5].
Since f(0.375) = -0.38 the root is in [0.375, 0.5].
Since f(0.4375) = -0.15 the root is in [0.4375, 0.5].
Since f(0.46875) = -0.018 the root is in [0.46875, 0.5].
Since f(0.484375) = 0.05 the root is in [0.46875, 0.484375].
... and so we approach the root 0.472834 It is superfluous to say that it is easy to computerize this method. Then we have the root in less than a second.
Newton's method.
Say f(x) is differentiable in the environment of a root r and ro is a first approximation of the root r. Now point P(ro,f(ro)) is on the curve of the function. The slope of the tangent line in P is f'(ro). This tangent line intersects the x-axis in a point with a x-value r1. The value r1 is a better approximation of the root than ro. From r1 you can find a better approximation r2. ...Formula
The equation of the tangent line in point P is
y - f(ro) = f'(ro) (x - ro)
for y = 0 we have
f(ro)
r1 = ro - --------
f'(ro)
Example
Take again the equation
t3 + 4 t2 - 1 = 0
Take to = 0.5 as a first approximation. Then
to3 + 4 to2 - 1
t1 = to - ------------------ = 0.4736842
3 to2 + 8 to
Taking t1 as a new approximation we find t2=
0.472834787153Taking t2 as a new approximation we find t3= 0.472833908996
Taking t3 as a new approximation we find t4= 0.472833908996
You see that this method is a very powerful method to approximate the root.
Again it is superfluous to say that it is easy to computerize this method. Then we have the root in less than a second.
This method requires that the first approximation is sufficiently close to the root r.
Iteration method
Suppose that you can bring an equation g(x)=0 in the form x = f(x). We'll show that you can solve this equation , on certain conditions, using iteration.Start with an approximation x0 of the root.
Calculate
x0,x1,...,xn,... such that
x1=f(x0);x2=f(x1);x3=f(x2);
...
Theorem:
If the sequence x0,x1,...,xn,
... belongs to an interval I, where |f'(x)| < k < 1 , then the sequence
has a limit L and L is the only root of x=f(x) in the interval I.
Proof:
Appealing on Lagrange's theorem
we can write:
x2 - x1 = f(x1) - f(x0) = (x1 - x0).f'(c1) with c1 between x0 and x1
x3 - x2 = f(x2) - f(x1) = (x2 - x1).f'(c2) with c1 between x1 and x2
...
xn+1-xn = f(xn) - f(xn-1)=(xn - xn-1).f'(cn) with cn between xn and xn-1
Since |f'(x)| < k < 1
|x2 - x1 | < k.|x1 - x0|
|x3 - x2 | < k.|x2 - x1|
...
|xn+1-xn| < k.|xn - xn-1|
Multiplying each side
|xn+1-xn| < kn . |x1 - x0| (1)
Now
|xn+p-xn| = |xn+p - xn+p-1 + xn+p-1 - xn+p-2 + ...
+ xn+1-xn |
=> |xn+p-xn| =< |xn+p - xn+p-1| + |xn+p-1 - xn+p-2| + ...
+ |xn+1-xn |
and using (1)
=> |xn+p-xn| < |x1 - x0|.(kn+p-1 + kn+p-2+...+kn)
=> |xn+p-xn| < |x1 - x0|. (kn - kn+p)/(1-k)
=> |xn+p-xn| < |x1 - x0|. kn/(1-k)
Since k<1 is kn/(1-k) smaller than each strictly positive
number e if n is sufficiently large and p = 1,2,3, ...
Therefore we conclude with the Criterion of
Cauchy that the sequence {xn} converges. Say the limit is L.
xn = f(xn-1)
=> lim xn = lim f(xn-1)
=> L = f(L)
Thus, L is a root of the equation x =
f(x).
If M is a second root of x = f(x) in interval I, then
M - L = f(M) - f(L) = (M - L).f'(c) with c in I
Then
f'(c) = 1 and this gives a contradiction.
Example of the iteration method
We'll solve x = 2 + sin(x)/2.Here f(x) =2 + sin(x)/2 and f'(x) = cos(x)/2 and the condition |f'(x)| < k < 1 is satisfied for all x.
Starting with x0 = 2 we calculate x1,x2,...
2.45464871341284 2.31708861973148 2.36710557531865 2.34967477062353 2.35585092904743 2.35367483693284 2.35444309931047 2.35417205822186 2.35426770472895 2.35423395542163 2.35424586438903 2.35424166217094 2.35424314497835 2.35424262175115 2.35424280637852 2.35424274123042 2.35424276421875 2.35424275610703 2.35424275896935 2.35424275795934The root is 2.35424275822278
Another example of the iteration method
We'll solve x.tanh(x)=1.x = coth(x) f(x) = coth(x) |f'(x)| = | -1/sinh2(x)| < 1/x2 |f'(x)| < 1 for x > 1 Starting with x0 = 1 we calculate x1,x2,... 1.31303528549933 1.15601401811395 1.21990402611162 1.19100666638769 1.20352756742564 1.19799585895445 1.20041926080065 1.19935362719156 1.19982145104824 1.19961592438525 1.19970618895035 1.19966654047733 1.19968395490739 1.19967630592522 1.19967966556677The root is 1.1996786402
Tranformation of an equation
If we try to solve the equation t3 + 4 t2 - 1 = 0 with the iteration method, we can write t = t + t3 + 4 t2 - 1 .to = 0.5 is a first approximation of the root. But the condition |f'(x)| < k < 1 is not satisfied in the environment of the root.
Therefore, we transform the equation in
t = t + r.(t3 + 4 t2 - 1)
We can choose the value of r without changing the root. From the theorem
above, we know that the convergence is very fast if k has a value near 0.
Here f'(t) = 1 + r.(3t2 + 8t) Since the root is near 0.5, we choose r = -0.21. Now f'(t) is near 0 in the environment of the root. We solve t = t - 0.21(t3 + 4 t2 - 1) starting with t = 0.5 0.47375 0.472892306269531 0.472837688600127 0.472834153854809 0.472833924859327 0.472833910023068 0.472833909061846 0.47283390899957 0.472833908995535 0.472833908995274 0.472833908995257 0.472833908995256
Program for iteration method
You don't need a big program to find the roots of an equation.Here is the extremely simple Perl program used to calculate the root of x.tanh(x) = 1.
#!/usr/bin/perl
$x = 1;
for $i (1..40) {
$x = (exp($x)+exp(-$x))/(exp($x)-exp(-$x)) ;
print $x,"\n";
}
Of course, you can do the same thing in Basic or Pascal or C.
Information Provided by Johan.Claeys@ping.be