Part II: Roots and Optimization

Instructor
Walid Morsi Ibrahim

1 ENGR 1400 Information Technology for Engineers Fall 2010

 Roots
 Quadratic formula

Solution:

 These values of x are called the roots or zeros of the equation.

 Many functions are not solved so easily, thus we will look at the numerical
methods, for example: Bungee Jumper

 If you want to solve for m, you cant bring m to the left hand side.
 Subtract v(t) from both sides

And then find the roots, i.e. the value of m that makes f(m) = 0

2 ENGR 1400 Information Technology for Engineers Fall 2010

 Optimization
 Is the determination of optimal values.
 For the figure shown, values of x that maximizes or
minimizes f(x)

3 ENGR 1400 Information Technology for Engineers Fall 2010

 Finding the Roots
 Graphical methods: plot the function and see where the zero
crossings are.
 We can zoom in on the plot for increased precision but there
is a great deal of human intervention.
 Therefore it is very slow. More automated methods are
needed.

4 ENGR 1400 Information Technology for Engineers Fall 2010

 General Rules for Finding the Roots
Graphically
 Consider xl and xu are the lower and upper limit points.
 If both are positive or negative no root
Even number of roots
 If they have different sign odd number of roots

5 ENGR 1400 Information Technology for Engineers Fall 2010

 Exceptions

6 ENGR 1400 Information Technology for Engineers Fall 2010

 Bracketing Methods and Initial Guess
 Bracketing methods are based on two initial guesses, one on
either side of the root.
 Advantage: always works
 Disadvantage: converges slowly
 Open methods have an initial guess but do not need to
bracket the root.
 Advantage: more quicker
 Disadvantage: may not work if the solution diverges

7 ENGR 1400 Information Technology for Engineers Fall 2010

 Increment Search
 This method searches for an interval with a sign change.
 It sates that: if f(x) is real and continuous in the interval from
xl to xu and f(xl) and f(xu) have opposite sign that is:
f(xl) f(xu) < 0
Then there is at least one real root between xl and xu

8 ENGR 1400 Information Technology for Engineers Fall 2010

 Limitations
 If the increment length is too small then the search becomes
time consuming.
 If the increment length is too large then some roots may be
missed.

9 ENGR 1400 Information Technology for Engineers Fall 2010

 Bisection Method
 Start with initial bounds and cut the problem in half again
and again.
 Ex: use bisection method to determine the drag coefficient
needed so that an 65 kg bungee jumper has a velocity of 35
m/s after 4.5 s of free fall. g = 9.81 m/s2. start with xl =
0.2, xu = 0.3 and iterate until < 2%.

10 ENGR 1400 Information Technology for Engineers Fall 2010

 Solution

11 ENGR 1400 Information Technology for Engineers Fall 2010

 Solution Cont.

12 ENGR 1400 Information Technology for Engineers Fall 2010

 Example on Bisection Method

Looking at the graph the root

Can be estimated to be at 145

13 ENGR 1400 Information Technology for Engineers Fall 2010

 Now try the same problem
f(50) = -ve and f(200) = +ve

Bracketing [50,200]

xl has to be updated. New interval

xu has to be updated. New interval

Run M-file bisection to get final value of the

root at the 8th iteration 142.7376
14 ENGR 1400 Information Technology for Engineers Fall 2010
 Graphical representation of Bisection
Method

See M-file bisectnew: Given xl = 40 and xu = 200, Sol mass = 142.7376

15 ENGR 1400 Information Technology for Engineers Fall 2010
 False Position Method
 Rather than bisecting the interval, it locates the root by
joining f(xl) and f(xu) with a straight line. The intersection of
this line with the x axis represents an improved estimate of
the root.

16 ENGR 1400 Information Technology for Engineers Fall 2010

 Derivation of the FP Method
 Referring to the figure:
[f(xu) - f(xl)]/[xu - xl ]= m [f(xu) - f(xl)]/[xu - xl ] = f(xu) /[xu - xr ]
And [f(xu) - 0]/[xu - xr ]= m

[xu - xr ] = [f(xu) [xu - xl ]]/ [f(xu) - f(xl)]

- xr = - xu + [f(xu) [xu - xl ]]/ [f(xu) - f(xl)]

xr = xu - [f(xu) [xu - xl ]]/ [f(xu) - f(xl)]

xr = xu - [f(xu) [xl - xu]]/ [f(xl) - f(xu)]

17 ENGR 1400 Information Technology for Engineers Fall 2010

 Disadvantages
 The shape of the function influences the new root estimate
 The figure shows slow convergence of the FP method

f(x)

root

18 ENGR 1400 Information Technology for Engineers Fall 2010

 Open Methods

19 ENGR 1400 Information Technology for Engineers Fall 2010

 Open Methods
 In bracketing methods the root has to be located between an
upper and lower bound: xl and xu
 In open methods the starting value (initial estimate) does not
need to bracket the root.
 Although the solution converges more quickly , sometimes it
may diverge.

20 ENGR 1400 Information Technology for Engineers Fall 2010

 Comparison

21 ENGR 1400 Information Technology for Engineers Fall 2010

 Simple Fixed-point Iteration
 Rearranging the function f(x) = 0 so that x is in the left hand
side of the equation: x = g(x)
 Then given an initial estimate xi the new value of x can be
calculated: xi+1 = g(xi)
 The process continue until the error criteria is met:
= abs([xi+1 – xi]/[xi+1]) x 100%

22 ENGR 1400 Information Technology for Engineers Fall 2010

 Example

23 ENGR 1400 Information Technology for Engineers Fall 2010

 Pros and Cons
 Simple and easy formula
 Slow convergence
 Convergence depends mainly on the location of the initial
guess.
 Divergence may occur

24 ENGR 1400 Information Technology for Engineers Fall 2010

 Newton-Raphson
 The most widely used.
 Considering the figure:

25 ENGR 1400 Information Technology for Engineers Fall 2010

 Example

26 ENGR 1400 Information Technology for Engineers Fall 2010

 Example

27 ENGR 1400 Information Technology for Engineers Fall 2010

 Four Cases of Poor Convergence

28 ENGR 1400 Information Technology for Engineers Fall 2010

 Function file Newton Raphson

29 ENGR 1400 Information Technology for Engineers Fall 2010

 Secant Method
 If the derivative used in NR is not available then a finite
difference derivative can be used

 Secant method requires two initial values xi and xi-1 to yield a

new value xi+1
 An alternative approach uses one initial value and a small
perturbation fraction (modified secant method)

30 ENGR 1400 Information Technology for Engineers Fall 2010

 Convergence and Divergence

31 ENGR 1400 Information Technology for Engineers Fall 2010

 Example

32 ENGR 1400 Information Technology for Engineers Fall 2010

 Example Cont.

33 ENGR 1400 Information Technology for Engineers Fall 2010

 Trade-off in choosing the perturbation
value
 If the perturbation value is chosen too small, round off error
could be increased especially in the denominator.
 If the perturbation value is chosen too large, then the
solution may diverges and the algorithm becomes inefficient

34 ENGR 1400 Information Technology for Engineers Fall 2010

 MATLAB Function: fzero
 Methods that we have seen so far are
either:
1. Slow but reliable (bracketing methods)
2. Fast but possibly unreliable (open
methods)
 As a trade off, better results could be
obtained using the fzero function.
 Fzero is a combination of the bisection Secant method
(reliable), secant (fast) and inverse
quadratic interpolation (very fast).
 Note the inverse quadratic interpolation
uses parabola instead of straight line.

Inverse quadratic
interpolation

35 ENGR 1400 Information Technology for Engineers Fall 2010

 MATLAB Function: fzero
 Syntax:

Initial guess

Guesses that bracket a sign change

 Disadvantages: root has to cross the x axis. If it touches the x

axis then it is not valid.
 Ex: y = x.^2

36 ENGR 1400 Information Technology for Engineers Fall 2010

 Polynomials
 Are nonlinear algebraic equations of the general form:

 MATLAB function: roots

Syntax:
Is a column vector Is a row vector containing
Containing the roots The polynomial coefficients

37 ENGR 1400 Information Technology for Engineers Fall 2010

 Example
 Use MATLAB to find the roots of the following polynomial:

 Sol:

 Evaluate the polynomial at x = 1as substitute by x =1 in f5(x)

38 ENGR 1400 Information Technology for Engineers Fall 2010

 Polynomials
 To get the polynomial from its roots:

39 ENGR 1400 Information Technology for Engineers Fall 2010

 Optimization

40 ENGR 1400 Information Technology for Engineers Fall 2010

 What is optimization?
 It is the process of creating
something that is as effective as
possible.
 Some examples of optimization:
1. Finding the minimum or
maximum
2. Minimizing the fuel consumption
3. Maximizing the data rate
 One popular method for
optimization is to solve for the
root of the problem:
Since at minimum or maximum the
slope should be zero

41 ENGR 1400 Information Technology for Engineers Fall 2010

 Is it maximum or minimum?
 We need to check the sign of that root:
1. If the sign is negative, then it is maximum
2. If the sign is positive then it is minimum.

42 ENGR 1400 Information Technology for Engineers Fall 2010

 Optimization types
 One dimensional: One dependent variable f(x) based on one
independent variable x and we are searching for x*
 Two dimensional: one dependent variable f(x,y) based on two
independent variables x and y and we are searching for x* and
y*

43 ENGR 1400 Information Technology for Engineers Fall 2010

 One Dimensional Optimization
 Global optimum represents the very best solution
 Local optimum is not the very best
 Since optimization is based on finding roots then the
optimization methods are similar to the idea of bracketing
used in bisection method

44 ENGR 1400 Information Technology for Engineers Fall 2010

 Golden Section Search
 Euclid’s definition of the golden ratio:
 Select l1 and l2 such that:
l l2
[l1 + l2]/ l1 = l1 / l2 1

Multiplying by
l1 / l2 = Ф gives: l1 + l2
Ф2 - Ф – 1 = 0
Solving for Ф
Ф = [1 + ]/2 = 1.618033 golden ratio

 Like bisection method we need a lower and an upper bound of an

interval containing a single minimum (unimodal)

45 ENGR 1400 Information Technology for Engineers Fall 2010

 How to proceed with the Golden
Search?
 We need to identify two points
between xl and xu say x1 and x2
 if f(x2) < f(x1) therefore the
minimum lies between x1 and xu

46 ENGR 1400 Information Technology for Engineers Fall 2010

 Example:

47 ENGR 1400 Information Technology for Engineers Fall 2010

 Example Cont.
Since
For next iteration: new values (or updated values)

The process is repeated until the 8th iteration, optimum value

is:

48 ENGR 1400 Information Technology for Engineers Fall 2010

 MATLAB Function fminbnd
 Similar algorithm to fzero
 Find the minimum of a function of one variable within fixed
interval.
 fminbnd for optimization (one dimensional) combines slow
dependable (golden section) and faster possible unreliable
(parabolic interpolation).
Syntax:

Location value of the min of f(x) Bounds of the interval being searched

 Limitations: limited to one dimensional-only handles real

variables-slow convergence

49 ENGR 1400 Information Technology for Engineers Fall 2010

 Multi-dimensional Optimization
 MATLAB function fminsearch
Syntax:
 Unconstrained optimization
 Start with an initial estimates
 Only handles real values
 If complex then it has to be split into two parts.

50 ENGR 1400 Information Technology for Engineers Fall 2010