r2h = 1000.
UCES
Course:Methods and Analysis in UCES
Assessment: completeness property, intermediate values
Prerequisites:
Objectives:
General Information: This section gives an algorithmic proof of the intermediate theorem. This is intimately related to the completeness axiom of the real line. In the next section the mean value theorem will be proved using the assumption of a continuous derivative and the intermediate value theorem. This sets the foundations for establishing various orders of convergence for solving nonlinear problems, numerical integration and numerical solution of differential equations.
Contact Person: R. E. White, NCSU, white@math.ncsu.edu
Revision Date: 7-29-94
Copyright ©1994, R. E. White. All rights reserved.
A linear problem has the form Ax = d where A and d do not depend on the
unknown x. In this lecture we will study nonlinear
problems of the form f(x) = 0 where x is a single unknown real number, and
f is a real valued function. Later we will look at more complicated nonlinear
problems where there are more than one unknown and more than one nonlinear
equation. A simple example is
2.1.2. Applied Area.
A one liter can is to be made from the same material on the sides, bottom and
top. The top material must have a slightly larger radius than the bottom so
that a seam can be formed. The problem is to find the height, h, and radius,
r, so that the total surface area will be a minimum, or a
minimum cost.
The one liter constraint can be written as
r2h = 1000.
The total surface area is from the bottom, sides and top with extra radius, d,
r2 + 2rh + (r + d)2.
From the constraint let h = 1000/(r2) so that the area is a
function of only r
r2 + 2000/r + (r + d)2.
Then compute the derivative and set it equal to zero
(r + (r + d)).
Thus we must solve the cubic equation
(2r3 + r2d).
If there was no seam, d would be zero and the root is easy to find
)1/3 .)1/3 ) > 0 and
f(0) < 0, we should have a solution between
)1/3
The model is very simple: find x such that
f(x) is zero. In linear problems we can find a solution in a finite number
of steps provided a solution exists. Nonlinear problems generally require
some sort of approximation process which we only stop when convinced that
there will be no further significant improvement in the approximation.
Nonlinear problems also may have no real solution such as
Suppose the graph is unbroken, that is, f is continuous. From the graph we
observe there is a root between x1 and x2 ,
Bisection Algorithm for the Root.
f(x1 ) > 0 , f(x2 ) < 0 and x1 < x2 for l = 1,maxit n = 2l - 1 xp = (xn + xn+1 )/2 if f(xp) = 0 then c = xp go to end endif if f(xp) > 0 then xn+2 = xp xn+3 = xn+1 endif if f(xp) < 0 then xn+2 = xn xn+3 = xp endif if | f(xp) | < eps1 go to end if | xn+2 - xn+3 | < eps2 go to end endloop end.
Example. Find the square root of 2. Let
Often it is easy to graph the function so that we know roughly where the root
is Certainly, we had the graph of
The following is an Maple code for the bisection algorithm. This is not the most efficient implementation because we want to organize the output data so that the monotone even and odd approximating sequences will become clear.
Input Data for f(x) = 2 - x2:
> x1:=1;
> x2:=2;
> f:=x->2-x*x;
> with(linalg):
Procedure for Algorithm is Defined:
> BISEC:=proc(f,x1,x2)
> eps := .001;
> xx:=vector(40,0);
> xx[1] := x1:
> xx[2] := x2:
> for l from 1 to 20 do
> n:=2*l-1;
> xp:=evalf((xx[n] + xx[n+1])/2);
> if abs(f(xp)) < eps then break fi;
> if f(xp) < 0
then
xx[n+2] := xx[n]:
xx[n+3] := xp:
fi;
> if f(xp) > 0
then
xx[n+2] := xp:
xx[n+3] := xx[n+1]:
fi;
> od;
> end;
Procedure is Called:
> BISEC(f,x1,x2);
Output is Given in Odd-Even Intervals:
> approx_sol:=seq([xx[2*l-1],xx[2*l]],l=1..10);
The following is a shorter version of the bisection algorithm which is coded in Matlab.
% choose xl and xr so that xl < xl and f(xl)*f(xr) < 0 % define the function f(x) = 2 -x*x in the f.m m-file eps = .001; xl = 1; xr = 2; for i=1:20 xm = (xl + xr)*.5; fxm = f(xm); if abs(fxm)<eps sol = xm; break; end if fxm*f(xr)<0 xl = xm; end if fxm*f(xl)<0 xr = xm; end end fxm sol Output: fxm = 4.272460937500000e-04 sol = 1.41406250000000
In the section on floating point numbers we noted that the square root of 2 or any prime number could not be a rational number. The real numbers have an additional property that the rational numbers do not have. This is called the completeness axiom, and an immediate consequence of the this is the following property.
Completeness Property of the Real Numbers.
xn+1
M < 
, then
there is a real number, x, such that xn converges to x.
Example. The square root of 2 has decimal expansion 1.41421356237...
x1 = 1. x4 = 1.414 .
x2 = 1.4 x5 = 1.4142 .
x3 = 1.41 x6 = 1.41421 M = 1.5
Since the square root of 2 is not rational, the rational numbers do not have the completeness property.
We want to present two very important consequences of the completeness property. The first will be the intermediate value theorem which will helps us establish the convergence of the bisection algorithm. In the next section we will establish the mean value theorem and some of its generalizations. The mean value theorem is a fundamental tool for the analysis of the rates of convergence of algorithms.
 |
| Figure: Intermediate Value Theorem |
Intermediate Value Theorem. If
R
Proof. This proof is constructive and will result in the bisection
algorithm for finding roots of functions. Let
x3 <
x4 x2 and
| x3 - x4 | | b-a |/2.
xn <
xn+1 xn-1 and
| xn - xn+1 |
| b-a |/2l .
By the completeness property both the even and odd sequences must converge to
xodd and xeven , respectively. Since
| b-a |/2l