- Steepest Decent or Gradient Method
Assume we want to minimize f(x) of N variables where x = (x1,x2,x3,...,xN)
The gradient 
f(x)
is a vector function defined as
grad(f(x)) = f(x)
= (δf(x)/δx1,δf(x)/δx2,...,δf(x)/δxN)
From the concept of gradient we knew that the gradient vector points in
the direction of the greatest increase of f(x)
Since we are looking for the minimum we will use -f(x),
that points in the direction of the greatest decrease.
- Basic Gradient Method
Start at p0 move along the line in the direction f(x)
a small increment that is going to take you closer to the minimum
p1 = p0 - f(p0)*h
...
pk = pk-1 - f(pk-1)*h
The gradient method does not guarantee a global minimum. The point
obtained is the closest minimum in the path of the starting point.
The method for finding the global minimum is called "simulated
anealing"
y' = Ky
dy/dt = Ky
dy/dt = Kdt
ln(y) = Kt + K2
y = eKt+K2
y = eK2eKt = K3eKt
Very often differential equations do not have an analytic solution, so they
are approximated with numerical methods
- Euler's Method
Let [a,b] be the interval which we want to find the solution of y' =
f(t,y), with y(a) = y0. We will find a set of points (t0,y0),
(t1,y1),...,(tK,yK) that are
used to approximate y'(t) ~= y'(tK).
h = (b-a)/m step size
Also, tk = a + k*h for k = 0,1,2,...,m
we want to solve y' = f(t,y) over [t0,t1,...,tm]
with y(t0) = 0
Use Taylor Expansion to approximate y(t)
y(t) = y(t0) + y'(t0)(t-t0) + y''(c1)(t-t0)2/2
\___Error___/
Use equation to obtain y(t1)
y(t1) = y(t0) + y'(t0)(t1-t0)
+ y''(c1)(t1-t0)2/2
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,...,m-1
- 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)))
Use Euler to approximate y(t1)
y(t1) = y(t0) + h*f(t0,y(t0))
therefore
y(t1) = y(t0) + h/2 * (f(t0,y(t0))
+ f(t1,y(t0) + h*f(t0,y(t0))))
y1 = y(t0) , y0 = y(t0)
y1 = y0 + h/2 * (f(t0,y0) +
f(t1,y0 + h*f(t0,y0)))
In general...
Pk+1 = yk + h*f(tk,yk)
yk+1 = yk + h/2 * (f(tk,yk) +
f(tk+1,Pk+1))
- Taylor Series Method
y(t0 + h) = y(t0) + h*y'(t0) + h2y''(t0)/2
+ ... + hNy(N)(t0)/N! + O(hN+1)
\_t1_/
We want to solve y' = f(y,t)
From the taylor expansion we can find the successive points
yk+1 = yk + h*yk' + h2yk''/2
+ h3yk'''/3! + ... + hNyk(N)/N!
We still need to compute yk'', yk(3),...
using y'=f(y,t)
Ex: y' = t2 - y; y(0) = 1; h= .2; N = 3
yk+1 = yk + h*yk'+ h2yk''/2
+ h3yk(3)/6
y' = t2 - y
y'' = 2t - y'
y(3) = 2 - y''
k = 0; t = 0; y0 = 1
y0' = 02
- 1 = -1
y0'' = 2(0) - (-1) = 1
y0(3) = 2 - 1 = 1
k = 1; t = .2
y1 = 1 + .2(-1) + (.2)2(1)/2 + (.2)3(1)/6
= .821333
y1' = (.2)2 - .821333 = -.781333
y1'' = ...
...
k=2; t=.4
...
To reduce error, make N larger or h smaller
- Runge-Kutta, Method of Order 4
Taylor gives a good approximation, but requires
derivatives
yk+1 = yk + h * (f1
+2 f2 + 2f3 + f4) / 6
f1 = f( tk, yk )
f2 = f( tk + h/2, yk + h/2*f1 )
f3 = f( tk + h/2, yk + h/2*f2 )
f4 = f( tk + h, yk + h*f3 )
Ex:y' = t2 - y
\_f(t,k)_/
dx/dt = f(t,x,y)
dy/dt = g(t,x,y)
with x(t0) = x0; 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.
Ex of a system of differential equations
x' = x + 2y
x(0) = 6
y' = 3x + 2y y(0) = 4
Solution
x(t) = 4e4t + 2e-t
y(t) = 6e4t - 2e-t
- Euler Method
We can extend Euler's method of a single differential
equation to a system of equations
dx/dt = f(t,x,y)
dx = f(t,x,y)dt
dy/dt = g(t,x,y)
dy = g(t,x,y)dt
Approximate
dxk = xk+1-xk
dyk = yk+1
- yk
dtk = tk+1
- tk
xk+1-xk = f(tk,xk,yk)(tk+1-tk)
yk+1-yk = g(tk,xk,yk)(tk+1-tk)
x(t0) = x0
\__h__/
y(t0) = y0
Therefore
xk+1 = xk + f(tk,xk,yk)*h
yk+1 = yk + g(tk,xk,yk)*h
Bad Accuracy because it approximates Taylor to the 1st
Derivative
- Runge-Kutta (Order 4) for a system of differential
equations
xk+1 = xk + h * (f1 +
2f2 + 2f3 + f4) / 6
yk+1 = yk + h * (g1 + 2g2 + 2g3
+ g4) / 6
f1 = f( tk, xk, yk
)
f2 = f( tk + h/2, xk + h/2*f1, yk
+ h/2*g1 )
f3 = f( tk + h/2, xk + h/2*f2, yk
+ h/2*g2 )
f4 = f( tk + h, xk + h*f3, yk
+ h*g3 )
g1 = g( tk, xk, yk
)
g2 = g( tk + h/2, xk + h/2*f1, yk
+ h/2*g1 )
g3 = g( tk + h/2, xk + h/2*f2, yk
+ h/2*g2 )
g4 = g( tk + h, xk + h*f3, yk
+ h*g3 )
- Higher Order Differential Equations x''(t), y''(t)
Ex. mx''(t) + cx'(t) + Kx(t) = g(t)
Can be transformed to a system of 1st order
differentials
Use substitution y(t) = x'(t)
mx''(t) + cx'(t) + Kx(t) = g(t)
x''(t) = (g(t) - x'(t) - Kx(t)) / m
(1) y'(t) = (g(t) - x'(t) - Kx(t)) / m
(2) x'(t) = y(t)