AGH University of Mining and Metallurgy
Faculty of Mechanical Engineering and Robotics
Department of Robotics and Mechatronics
Numerical Methods and Programming
Laboratory 4
Methods of solving nonlinear equations
- initial approximation   starting methods,
- bisection method,
- Newton s method.
Joanna Iwaniec, Krakow 2007
1 Methods of solving nonlinear equations
Roots of nonlinear equations usually can t be described by closed-form formulas or these
formulas are too complicated to be used in practical applications. Therefore methods of
solving nonlinear equation are based on the idea of consecutive approximations or
linearization. These methods require one (or more) root initial values and return the sequence
x0, x1, x2, & that is likely to converge to the real value. In some cases, in order to obtain
convergence, it is sufficient to know band containing a root. Other methods require
initial approximation that is close enough to the considered root (these methods usually
converge more quickly than remaining methods). Therefore the nonlinear equations are
usually solved in two steps: first the root (or a band containing the root) is roughly evaluated,
next more accurate solution is estimated.
2 Initial approximation   starting methods
Initial approximation of roots of equation f(x) = 0 can be obtained by plotting function
f(x). On the basis of Fig. 1 we know that the root of the considered equation
2
(0,5x) - sin x = 0 belongs to the band (0,5Ä„ , 2).
2
Fig. 1. Function y = (0,5x) - sin x and its roots.
For the purposes of initial assessment of equation roots, we can prepare table of values of
function f(x).
x (0,5)x2 sinx f(x)
1,6 0,64 -0,9996 < 0
1,8 0,81 -0,974 < 0
2,0 1,00 0,909 > 0
In general, if f(x) is continuous in the band (a, b) and f(a)f(b) < 0 then equation f(x) = 0 has
at least one real root in the band (a, b).
3 Bisection method
Bisection method is one of the simplest and most reliable methods of finding solution of
nonlinear equations. It belongs to the class of iterative methods, which means that
computations are repeated as long as the accuracy criterion is not met.
The method requires estimation of band containing the function root. If the function is
continues and has a single root in a given band, this condition is satisfied if function values at
the edges of a considered band have different signs (Fig. 2). Slow convergence is the main
method disadvantage.
y
Single root in (a,b)
f(b) > 0
a
x
x1
b
f(a) < 0
Fig. 2. Idea of the bisection method
3.1 Algorithm of bisection method.
1. Having band edges: ai < bi check the condition of sign change: f (ai )f (bi ) < 0 .
ai + bi
2. If the signs are different, determine point ci = and value of the considered
2
function f(ci) at this point.
3. Decide which of the edge points should be replaced by the point ci. Use the following
criterion: if f (ai )f (ci ) < 0 then ai+1 = ai , bi+1 = ci , otherwise ai+1 = ci , bi+1 = bi .
4. Repeat the above steps as long as the band being narrowed is smaller than the assumed
tolerance µ, which means that bi - ai d" µ .
4 Newton s method
Newton s method or the method of tangents (dedicated to estimation of roots of nonlinear
equations) is one of most popular and efficient numerical methods. As the main method
disadvantages the requirement of function derivative knowledge and method sensitivity to
accuracy of root initial values are treated. In order to start a procedure realizing the Newton s
method it is necessary to specify one starting point.
3
4.1 Algorithm of Newton s method
1. Compute value of function f(xi) and its derivative f (xi) in the current point xi.
2. Plot tangent to a considered function in point (x0, f(x0)) and determine the point in which
f (xi )
this tangent crosses Ox axis. Use equation: xi+1 = xi - .
f '(xi )
3. Assume point xi+1 as a consecutive root approximation.
4. As a  stop criterion assume obtaining consecutive approximations differing from each
other less than assumed accuracy xi+1 - xi d" µ together with a small value of function:
f (xn ) d" µ .
y
root
y = f(x)
x2 x1 x0 x
¾
Fig. 3. Idea of the Newton s method.
5 Useful MATLAB functions
5.1 FZERO: scalar nonlinear zero finding.
X = FZERO(FUN,X0) tries to find a zero of the function FUN near X0.
FUN accepts real scalar input X and returns a real scalar function value F evaluated at X. The
value X returned by FZERO is near a point where FUN changes sign (if FUN is continuous),
or NaN if the search fails.
X = FZERO(FUN,X0), where X is a vector of length 2, assumes X0 is an interval where the
sign of FUN(X0(1)) differs from the sign of FUN(X0(2)). An error occurs if this is not true.
Calling FZERO with an interval guarantees FZERO will return a value near a point where
FUN changes sign.
X = FZERO(FUN,X0), where X0 is a scalar value, uses X0 as a starting guess. FZERO looks
for an interval containing a sign change for FUN and containing X0. If no such interval is
found, NaN is returned. In this case, the search terminates when the search interval is
expanded until an Inf, NaN, or complex value is found.
4
X = FZERO(FUN,X0,OPTIONS) minimizes with the default optimization parameters
replaced by values in the structure OPTIONS, an argument created with the OPTIMSET
function. See OPTIMSET for details. Used options are Display and TolX. Use OPTIONS = []
as a place holder if no options are set.
EXAMPLES
FUN can be specified using @:
X = fzero(@sin,3)
returns pi.
X = fzero(@sin, 3, optimset('disp','iter'))
returns pi, uses the default tolerance and displays iteration information.
FUN can also be an inline object:
X = fzero(inline('sin(3*x)'),2);
LIMITATIONS
X = fzero(inline('abs(x)+1'), 1)
returns NaN since this function does not change sign anywhere on the real axis (and does not
have a zero as well).
X = fzero(@tan,2)
returns X near 1.5708 because the discontinuity of this function near the point X gives the
appearance (numerically) that the function changes sign at X.
5.2 ROOTS: finds polynomial roots.
ROOTS(C) computes the roots of the polynomial whose coefficients are the elements of the
vector C. If C has N+1 components, the polynomial is C(1)*X^N + ... + C(N)*X + C(N+1).
5.3 INLINE: constructs INLINE object.
INLINE(EXPR) constructs an inline function object from the MATLAB expression contained
in the string EXPR. The input arguments are automatically determined by searching EXPR
for variable names (see SYMVAR). If no variable exists, 'x' is used.
INLINE(EXPR, ARG1, ARG2, ...) constructs an inline function whose input arguments are
specified by the strings ARG1, ARG2, ... Multicharacter symbol names may be used.
INLINE(EXPR, N), where N is a scalar, constructs an inline function whose input arguments
are 'x', 'P1', 'P2', ..., 'PN'.
EXAMPLES:
g = inline('t^2')
g = inline('sin(2*pi*f + theta)')
g = inline('sin(2*pi*f + theta)', 'f', 'theta')
g = inline('x^P1', 1)
5
6 EXERCISES
1. By means of  starting methods assess initial values of roots of the following equations:
a) 3x3  x - 2 = 0
b) 1 - x  e-2x = 0
2. Implement algorithm of the bisection method in MATLAB. Verify correctness of the
created function performance for estimation of roots of the following equations:
a) 3x3  x - 2 = 0, x0 = 0,8
2
b) (0,5x) - sin x = 0 , x0 = 1,8.
and compare obtained results with results returned by the MATLAB function
fzero(inline &  , x0).
3. In MATLAB write a function realizing Newton s method of solving nonlinear equations.
Assume that required accuracy µ = 1e-6.
Consider two cases:
a) exact value of considered function derivative is known,
b) exact value of considered function derivative is unknown, approximate value of derivative
is used:
f (xi-1)- f (xi+1)
f '(xi ) =
2"x
6