1

Numerical Solutions to CE Problems

ROOTS OF NON-LINEAR EQUATIONS

OVERVIEW

In this chapter we extend from linear algebra to deal with nonlinear algebraic
problems. This kind of problem arises when there is a parameter or variable that can
be changed in order to satisfy a constraint or achieve some goal. We start with
scalar functions of a single variable, then generalize to variables and nonlinear
equations. Finally, we generalize the problem of linear least squares to situations
with more nonlinear constraints to satisfy than there are variables. In every case the
strategy used is one of the cornerstones of numerical computing: replace a problem
you can’t solve with an approximate one that you can. In the context of nonlinear
algebraic problems, the particular tactic is to set up and solve a sequence of linear
problems of the types covered in the two previous chapters.

Learning Objective

At the end of this module the student shall be able to:

1) Solve problem on Bisection method
2) Solve problems on False Position method
3) Solve problems on Newton Raphson Method
5) Solve problems on Secant Method

INTRODUCTION

1 INTRODUCTION
2 BISECTION METHOD
3 FALSE POSITION METHOD
4 NEWTON RAPHSON METHOD
5 SECANT METHOD

NUMERICAL ANALYSIS
What does numerical analysis mean?
Numerical Analysis is the branch of mathematics that provides tools and methods for
solving mathematical problems in numerical form.
In numerical analysis we are mainly interested in implementation and analysis of
numerical algorithms for finding an approximate solution to a mathematical problem.

NUMERICAL ALGORITHM

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus
 2
Numerical Solutions to CE Problems

A complete set of procedures which gives an approximate solution to a mathematical

problem.

NUMERICAL ITERATION METHOD

A specific way of implementation of an iteration method, including to termination
criteria is called algorithm of an iteration method. In the problem of finding the
solution of an equation, an iteration method uses as initial guess to generate
successive approximation to the solution.

Why we use numerical iterative methods for solving equations?

As analytic solutions are often either too tiresome or simply do not exist, we need to
find an approximate method of solution. This is where numerical analysis comes into
picture.

A quadratic equation is an algebraic equation, which is not linear. In other words, a

nonlinear equation is an algebraic equation of degree 2 or higher. X2 + 3x + 2 = 0 is
a single variable nonlinear equation. X2 + y3+ 3xy= 4 and 8yzx2 + y2 + 2z2 + x + y +
z = 4 are examples of nonlinear equations of 3 and 4 variables respectively. A
second degree nonlinear equation is called a quadratic equation. If the degree is 3,
then it is called a cubic equation. A linear equation is an algebraic equation of degree
1, but a nonlinear equation is an algebraic equation of degree 2 or higher. Even
though any linear equation is analytically solvable, it is not the case in nonlinear
equations.

DIRECT METHODS & INDIRECT (ITERATIVE) METHODS

There are two types of methods to find the roots of Algebraic: (i) DIRECT METHODS
(ii) INDIRECT (ITERATIVE) METHODS.

DIRECT METHODS
 Direct methods give the exact value of the roots in a finite number of steps.
 These methods determine all the roots at the same time as suming no round off
errors.
 In the category of direct methods; Elimination Methods are advantageous
because they can be applied when the system is large.
INDIRECT (ITERATIVE) METHODS
 These are based on the concept of successive approximations. The general
procedure is to start with one or more approximation to the root and obtain a
sequence of iterates “x” which in the limit converges to the actual or true solution
to the root.
 Indirect Methods determine one or two roots at a time.

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus
 3
Numerical Solutions to CE Problems

 Rounding error have less effect These are self-correcting methods.

 Easier to program and can be implemented on the computer.

REMEMBER: Indirect Methods are further divided into two

categories:
I. BRACKETING METHODS:
These methods require the limits between which the root lies. e.g. Bisection method,
False position method.
II. OPEN METHODS:
These methods require the initial estimation of the solution. e.g.
Newton Raphson method.

BISECTION METHOD
The bisection method is used to find the roots of a polynomial equation. It separates
the interval and subdivides the interval in which the root of the equation lies. The
principle behind this method is the intermediate theorem for continuous functions. It
works by narrowing the gap between the positive and negative intervals until it
closes in on the correct answer. This method narrows the gap by taking the average
of the positive and negative intervals. It is a simple method, and it is relatively slow.
The bisection method is also known as interval halving method, root finding method,
binary search method. Let, consider a continuous function “f” which is defined on the
closed interval [a, b], is given with f(a) and f(b) of different signs. Then by
intermediate theorem, there exists a point x belong to (a, b) for which f(x) =0.

Definition: (Bisection method) The method is applicable for solving the equation f(x)
= 0 for the real variable x, where f is a continuous function defined on an interval [a,
b] and f(a) and f(b) have opposite signs i.e. f (a)f (b) < 0. In this case a and b are said
to bracket a root since, by the intermediate value theorem, the continuous function (f)
must have at least one root in the interval (a, b).
a+b
c = ---------
2
Then pick that interval [a, c] or [c, b].
If f (c).f (a) < 0, then (c=b [a,c]) else (c=a [c, b])

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus
 4
Numerical Solutions to CE Problems

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus
 5
Numerical Solutions to CE Problems

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus
 6
Numerical Solutions to CE Problems

FALSE POSITION METHOD

False position algorithm is basically a root finding

method. It is quite similar to bisection method and it
has been used to find the real roots of an equation
using bracketing approach.

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus
 7
Numerical Solutions to CE Problems

NEWTON RAPHSON METHOD (Tangent Method)

Definition (Newton’s Method):

The Newton Raphson method is a powerful and well known method for solving
equations numerically. It is based on the idea of linear approximation. Usually
converges much faster than the linearly convergent methods. Newton method is an
iterative method, meaning that it repeatedly attempts to get better approximations to
the desired root. Instead of just computing f(x) the derivative f ′ (x) also
calculated. it is assumed that the next estimate of the root (solution), is where the
tangent crosses the x axis. The values of f(x) and f ′ (x) are calculated and the
process repeated until it converges.

Newton’s method is an Open method, how?

It is an open method because initial guess of the root that is needed to get the
iterative method started is a single point. While other open methods use two initial
guesses of the root but they do not have to bracket the root.

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus
 8
Numerical Solutions to CE Problems

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus
 9
Numerical Solutions to CE Problems

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus
 10
Numerical Solutions to CE Problems

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus
 11
Numerical Solutions to CE Problems

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus
 12
Numerical Solutions to CE Problems

Secant method

A major disadvantage of the Newton-Raphson algorithm requires the evaluation of

two functions (the function and its derivative) per each iteration. The secant method
is a slight modification for the Newton-Raphson method. This method (secant
method) requires the selection of two initial approximations x0 and x1, which may or
may not bracket the desired root, but which are chosen reasonably close to the exact
root. This method also known as QUASI NEWTON’S METHOD.

ADVANTAGES
1. No computations of derivatives.
2. One f(x) computation each step. It requires only one function evaluation per
iteration, as compared with Newton’s method which requires two.

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus
 13
Numerical Solutions to CE Problems

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus
 14
Numerical Solutions to CE Problems

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus
 15
Numerical Solutions to CE Problems

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus
 16
Numerical Solutions to CE Problems

Engr. Edbert Tulipas

University Of Eastern Philippines Laoang Campus