Minimization Using Derivatives

Assume we want to minimize f(x) and it has a unique minimum at p. a<=p<=b we start our search at p.
If f'(p0) > 0, then p is left of p0
If f'(p0) < 0, then p is right of p0
Use bisection for f ‘(x) = 0

Finding the Minimum for Multiple Variables:

Steepest Descent or Gradient Method

Assume we want to minimize f(x) of n vars where x=(x1,x2, thru xn) The gradient =(df(x)/dx1,df(x)/dx2,thru df(x)/dxn)

from the concept of the gradient, we know that the gradient vector points in the direction of the greatest change of f(x). Since we are looking for the minimum, we will use - grad(f(X))

Basic gradient method:

- Start at point P0 and move along the line in the direction -"f(x) on small increment.

- That is going to take you closer to the minimum

Example

f(x) = x2 + 1

f ‘(x) = 2x

"f(x) = 2xi xk = xk-1 – 2xk-2 h

Let h = 0.1 "f(x) = 2(-1)i

x­0 = -1
x1 = -1 - 2(-1)0.1 = -1 + .2 = -0.8
x2 = -.8 – 2(-.8)(.1) = -.8 + .16 = -.64
x3 = -.64 – 2(-.64)(.1) = -.64 + .128 = -.512

…

0

Only good for local searching. Global is called simulated anealing.

Numerical Solution of Differential Equations:

introduction:

example:

y'=k*y

dy/dt=k*y

Euler's Method

Let [a,b] be the interval which we want to find the solution of y' = f(y,t) with y(a) = y0. We will find a set of points: (t0,y0), ..., (tn,yn) that are used to approximate y(t) = y(tk).
Also, tk= a +k*h (where h is the step size) for k = {0,1,2,...,m} over [t0, t1, ..., tm] with y(t0) = 0.

Using Taylor's Expansion to approximate y(t) around t0, we have:
y(t) = y(t0) + y'(t0)*(t-t0) + y''(c)*(t-t0)2/2
We use this equation to obtain y(t1):
y(t1) = y(t0) + y'(t0)*(t-t0) + E(t)
If the step size is small enough, we can neglect the second order error.
y1 = y0 + h*y'(t0)
y1 = y0 + h*f(t0,y0)
In general, tk+1 = tk +h
yk+1 = yk + h*f(tk,yk) for k = 0, 1, 2, ..., m-1

Taylor Series Method:

Using the Taylor Series expansion to approximate the solution
y(t0+h)=y(t0)+hy'(t0)+(h^2/2!)(y''(t0)).......+h^n*(y^n(t0))/n!
we want to solve
y'=f(t,y) at y(t0)=a
from the Taylor expansion we can find the successive points yk+1=yk+hy'k + h^2*y^nk/n!
but we still need to compute yk'' and yk''' using y'=f(t,y)

Runge-Kutta Method of Order 4:

the Taylor method gives a good approximation but it requries the derivatives of the function. The Runge-Kutta method of order 4 simulates the accuracy of the Taylor series method using an order of N=4 but it does not require the computation of derivatives

yk+1=yk+(h/6)(f1+2f2+2f3+f4)
f1=f(tk,yk)
f2=f(tk+h/2,yk+(h/2)f1)
f3=f(tk+h/2,yk+h/2f2)
f4=(tk+h,yk+hf3)

Example:

y'=t^2-y y(0)=1 h=0.2
k=0 t0=0
f1=-1
f2=f(0.1,0.9)=-.89
f3=f(0.1,0.911)=-.901
f4=f(0.2,0.8198=-0.7798

k=1 t0=0.2
f1=-.781273
f2=-0.653416
f3=-0.665958
f4=-0.528081

Heun's Method

Solve y'(t) = f(t,y(t)) over [a,b] with y(t0) = y0
Integrate y'(t) over [t0,t1]
t1 y'(t) dt = t1 f(t,y(t)) dt = y(t1) - y(t0) t0 t0

Using Numerical Integration
y(t1) - y(t0) = h/2 * (f(t0,y(t0)) + f(t1,y(t1)))
y(t1) = y(t0) + h/2 * (f(t0,y(t0)) + f(t1,y(t1)))

In general...

Pk+1 = yk + h*f(tk,yk)
yk+1 = yk + h/2 * (f(tk,yk) + f(tk+1,Pk+1))

Systems of Differential Equations:
Assume we have dx/dt = ¦(t, x, y) and dy/dt = g (t, x, y) with x (t0) = x0 and y (t0) = y0. The solution to this system are functions x (t) and y (t) that when derivated and substituted in the system of equations give equality.

An example of a system of Differential Equations:

x' = x + 2y x (0) = 6
y' = 3x + 2y y (0) = 4

Analytical solution:
x (t) = 4e4t + 2e-t
y (t) = 6e4t - 2e-t

Euler's Method for Systems of Differential Equations
We can extend Euler's method of a single differential equation to a system of equations.

dx/dt = ¦(t, x, y) dx = ¦(t, x, y)dt
dy/dt = g (t, x, y) dy = g (t, x, y)dt

dxk = xk+1 - xk
dyk = yk+1 - yk
dtk = tk+1 - tk

xk+1 - xk = ¦(tk, xk, yk)(tk+1 - tk)
yk+1 - yk = g (tk, xk, yk)(tk+1 - tk)

With h = tk+1 - tk we have that:
xk+1 = xk + ¦(tk, xk, yk)h x (t0) = x0
yk+1 = yk + g (tk, xk, yk)h y (t0) = y0

The Euler method does not give good accuracy because it approximates the Taylor expansion only to the first derivative.

Higher Order Differential Equations

Higher order differential equations involve higher derivates like x ''(t) and y ''(t). For example: mx ''(t) + cx '(t) + kx (t) = g (t). These higher order differential equations can be transformed to a system of differential equations of first order.

Use the substitution: y (t) = x '(t)
For the above system we obtain x ''(t):

x ''(t) = (g (t) - cx '(t) - kx (t))/m
Substituting y (t) = x '(t) we get the first differentional equation of first order in the system:

y '(t) = (g (t) - cy (t) - kx (t))/m
The second equation is simply the substitution y (t) = x '(t).

EXAMPLE

4x'' + 3x' + 5x = 2 x (0) = 1 x '(0) = 3

x'' = (2 - 3x' - 5x)/4 Let y = x'
y' = (2 - 3y - 5x)/4 x' = y

The system of differential equations uses the last two equations from above y' = (2 - 3y - 5x)/4 and x' = y with x (0) = 1 and y (0) = 3.

Final Exam Material:

-least squares line

-least squares for non-linear equations

-transformation for data linearization

-polynomial fitting

-splines
*5 properties of splines
*proofs
*how to use for the spline formulas
*end point constraints

-numerical differentiation
*limit of difference quotient
*central difference formulas

-numerical integration
*Trapezoidal rule
*Simpson rule

-numerical optimization
*local and global minima and maxima
*golden ratio
*gradient method

-Solution of different equations
*Euler's Method
*Heun's Method
*Taylor Series
*Runge-kutta
*systems of differential equations (Euler's method, Runge-kutta)

Final Exam Time and locations

Friday Aug 8th , 10:20-12:20 in WTHR 104.