Euler method

The same idea used for slope fields--the graphical approach to finding solutions to first order differential equations--can also be used to obtain numerical approximations to a solution. The basic idea of differential calculus is that, close to a point, a function and its tangent line do not differ very much. Consider, for example, the function , and its tangent line at .

Now consider the differential equation

If we want to compute the solution passing through the point (-1,4), then we can compute the tangent line at this point. Its slope at x=-1 is given by the differential equation

thus, the equation for the tangent line is given by

Since we expect the solution to the differential equation and its tangent line to be close when x is close to -1, we should also expect that the solution to the differential equation at, let's say, x=-0.75 will be close to the tangent line at x=-0.75.

We compute the y-value of the tangent line to be y(-0.75)=2.75. This method can now be iterated; the tangent line equation for x=-.075 and y=2.75 is given by

using the tangent line equation for x=-0.5, we obtain as an approximation to our solution

You can use a programmable calculator or a symbolic math program like Mathematica to do the calculations a little faster.

What is the formula we use to find our approximations?

We start at the point . Let h denote the x-increment. Then . is the the y-coordinate of the point on the line passing through the point with slope thus

The next approximation is found by replacing and by and ; so and . In general, we obtain the following formula for ,

We obtain better approximations if we reduce the step size h. The following graphs give approximations for step sizes h=0.25 in blue, h=0.1 in purple and h=0.01 in red:

For this example it is not hard to compute the exact solution

The next graph shows the exact solution in black. We see that a step size of h=0.01, leading to 500 steps of computation, does a satisfactory job in approximating the exact solution.

The rest of this page is devoted to some of the pitfalls of numerical computations. Here is another example of a "harmless" differential equation:

First, we try Euler's method with a step size of h=0.1. Recall that this step size gave a satisfactory approximation in the previous example.

Not much is happening. Note, however, that the scale on the y-axis is of the magnitude .

Let's try again with a step size of h=0.0025, leading to 6,000 computing steps.

It is easy to solve the differential equation analytically (do it!). The next picture compares the previous approximation (in red) to the graph of the exact solution (in black). The approximation is off by about 50%!

It is of interest to use numerical methods only when one is unable to compute solutions with pencil and paper. But, in such a situation you cannot compare the approximation to the exact solution so you have no control over how good your approximation is! If you take a course in Numerical Mathematics you will learn that there are ways to predict the error in Euler's method even if you cannot compute the exact solution. The class is also the place to learn more sophisticated numerical methods to solve differential equations. For the differential equation we considered, one should use a method which automatically reduces the step size where the slope of the solution changes rapidly!

The last example addresses another pitfall. Let's consider the differential equation

We want to find the solution satisfying the initial condition y(0)=1.1, using Euler's method with step size h=.1.

The following is a table with the first four values; the function is decreasing rapidly:

Let's look at the graph of the approximation.

The next picture compares the approximation (in blue) to the graph of the exact solution (in red).

Notice that there is no hint of a resemblance between the two. What has happened? An explanation requires the knowledge of the concept of a node. The differential equation has an equilibrium solution y=1. The equilibrium is a down node; thus the exact solution with initial condition y(0)=1.1 is decreasing and approaches 1 as t approaches infinity. The Euler approximation "jumps" below the equilibrium solution in the first computational step (look again at the table above). Once it is below the equilibrium solution it moves away from the position of the node rather rapidly! In our case, a smaller step size would prevent the Euler approximation from ever jumping below the equilibrium solution. 

 reference: www.sosmath.com

» ادامه مطلب

The Perceptron

A Learning Program

For decades there have been attempts to create computer programs that can learn like people - Artificial Intelligence. For example, how do you teach a child to recognize what a chair is? You show him examples telling him "This is a chair ; That one is not a chair" until the child learns the concept of what a chair is. In this stage, the child can look at the examples we have shown him and answer correctly to the question "Is this object a chair?". Furthermore, if we show to the child new objects, that he didn't see before, we could expect him to recognize correctly whether the new object is a chair or not, providing that we've given him enough positive and negative examples. This is exactly the idea behind the perceptron.

The Perceptron

The perceptron is a program that learn concepts, i.e. it can learn to respond with True (1) or False (0) for inputs we present to it, by repeatedly "studying" examples presented to it. The Perceptron is a single layer neural network whose weights and biases could be trained to produce a correct target vector when presented with the corresponding input vector. The training technique used is called the perceptron learning rule. The perceptron generated great interest due to its ability to generalize from its training vectors and work with randomly distributed connections. Perceptrons are especially suited for simple problems in pattern classification. Our perceptron network consists of a single neuron connected to two inputs through a set of 2 weights, with an additional bias input. The perceptron calculates its output using the following equation:

P * W + b > 0
        

where P is the input vector presented to the network, W is the vector of weights and b is the bias.

The Learning Rule

The perceptron is trained to respond to each input vector with a corresponding target output of either 0 or 1. The learning rule has been proven to converge on a solution in finite time if a solution exists. The learning rule can be summarized in the following two equations:

For all i:

                W(i) = W(i) + [ T - A ] * P(i)

                b    = b + [ T - A ]
        

where W is the vector of weights, P is the input vector presented to the network, T is the correct result that the neuron should have shown, A is the actual output of the neuron, and b is the bias.

Training

Vectors from a training set are presented to the network one after another. If the network's output is correct, no change is made. Otherwise, the weights and biases are updated using the perceptron learning rule. An entire pass through all of the input training vectors is called an epoch. When such an entire pass of the training set has occured without error, training is complete. At this time any input training vector may be presented to the network and it will respond with the correct output vector. If a vector P not in the training set is presented to the network, the network will tend to exhibit generalization by responding with an output similar to target vectors for input vectors close to the previously unseen input vector P.

Limitations

Perceptron networks have several limitations. First, the output values of a perceptron can take on only one of two values (True or False). Second, perceptrons can only classify linearly separable sets of vectors. If a straight line or plane can be drawn to seperate the input vectors into their correct categories, the input vectors are linearly separable and the perceptron will find the solution. If the vectors are not linearly separable learning will never reach a point where all vectors are classified properly. The most famous example of the perceptron's inability to solve problems with linearly nonseparable vectors is the boolean exclusive-or problem.

Our Implementation

We implemented a single neuron perceptron with 2 inputs. The input for the neuron can be taken from a graphic user interface, by clicking on points in a board. A click with the left mouse button generates a '+' sign on the board, marking that it's a point where the perceptron should respond with 'True'. A click with the right mouse button generates a '-' sign on the board, marking that it's a point where the perceptron should respond with 'False'. When enough points have been entered, the user can click on 'Start', which will introduce these points as inputs to the perceptron, have it learn these input vectors and show a line which corresponds to the linear division of the plane into regions of opposite neuron response. Here's an example of a screen shot:

» ادامه مطلب