## Taylor method with automatic differentiation – 2

In the previous post, we have talked about Taylor method to solve ordinary differential equation (ODE) numerically. All the derivatives in the Taylor method are computed using automatic differentiation. However, the drawback of this method is when we change our ODE, we have to write another code. In this post, we are going to present a way such that when we want to compute another ODE, we don’t need to change the majority of our code.

Continuing our analysis in the last post, we are going to need operations on polynomials. We are going to define operations such as:

- Addition between a constant and a polynomial
- Multiplication between a constant and a polynomial
- Addition between polynomials
- Multiplication between polynomials
- Dividing a constant by a polynomial
- Dividing a polynomial by a polynomial
- Logarithm of a polynomial
- Exponentiation of a polynomial
- Power of a polynomial

Operation 1 and 2 are trivial. Suppose is a polynomial, then for some real constant . Suppose is a real constant, then the addition between and is a polynomial where and for all . The multiplication between and is a polynomial where for all .

Operation 3 and 4 are not difficult. Suppose are polynomials. Then the addition between and is a polynomial where for all . The multiplication between and is a polynomial where .

Operation 5 and 6 are a little bit tricky. Suppose is a polynomial and is a constant. We want to compute where . Notice that . Therefore, we are going to take advantage of this equality to find the coefficient of . Thus we shall have , and . For operation 6, let’s suppose . As before, notice that , thus we can compute the coefficient of using this equality. Thus, and .

Now, let’s consider the next operation, which is a logarithm of a polynomial. Suppose is a polynomial and we are going to find . Let’s differentiate both side with respect to , then we have . Thus by exploiting a division operation above, we have and .

Now, let’s consider the exponential operator, which is an exponentiation of a polynomial. Suppose is a polynomial and we are going to find . Let’s take logarithm on both side and then differentiate it, we then have , or . Therefore, by exploiting a multiplication operation, we shall have and .

For the last operation of this post, we shall consider the power of a polynomial. Suppose is a polynomial, we are going to find for any real number . First, we need to take logarithm on both sides and then differentiate the result with respect to , or . By exploiting multiplication and division, we will get the coefficient of .

To facilitate these operation, we build a Python module that will handle these operations. We will also write another code to integrate an ODE. This integration code will work in general without any dependencies on the system or on the order of the system.

def integrate(F,y_init,t_init = 0.0 ,tStop = 1.0 ,h = 0.05 ): dim = len(y_init) y_sol = [] for i in range(0,dim): y_sol.append([]) y_sol[i].append(y_init[i]) t_sol = [] t_sol.append(t_init) t = t_init while t < tStop: y = [] for i in range(0,dim): y.append([]) y[i].append(y_sol[i][-1]) for k in range(0,20): dy = F(y) for i in range(0,dim): y[i].append(dy[i][k]/float(k+1)) n = len(y[0]) for i in range(0,dim): temp = 0.0 for j in range(0,n): temp = temp + y[i][j]*h**j y_sol[i].append(temp) t_sol.append(t+h) t = t + h return np.array(t_sol) ,np.transpose(np.array(y_sol))

All the operations above and the last code will be written in a python file so that if we need to use this Taylor method, we can just import it. Let’s take an example to integrate one ODE. We will create another code that specifies the ODE and also imports all the operations above and then numerically integrate it.

from mytaylor import * import matplotlib.pyplot as plt import numpy as np import math as m #define your ODE here def fun(y): z = subtractpoli(y[0],multiplypoli(y[0],y[0])) return [z] #define your computation parameter here y_init = [0.5] t_init = 0 h = 0.1 tStop = 5.0 #integrating ODE T, Y = integrate(fun,y_init,t_init,tStop,h) #real solution computation real_sol = [] for t in T: temp = m.exp(t)/(m.exp(t)+1.0) real_sol.append(temp) #plotting the error versus time real_sol = np.array(real_sol) error = Y[:,0]-real_sol plt.plot(T[:],error[:]) plt.show()

In the above code, we try to numerically integrate with initial condition . This is the same system we try to integrate in the previous post. I hope you can see the difference between the last code and the code we have shown in the previous post. We really don’t need to consider about Taylor method at all, we just need to write our system in the above code if we want to compute the numerical solution of our code. Notice that we have written all the operations and the integrating code in a file named mytaylor.py which is imported in the first line of the above code. In the fifth line, we can write any ODE we want to integrate, however, the way we write our ODE will be slightly different. Due to polynomial operations that we have defined in this post, cannot be written as just but addpoly(). Once we define our ODE, we can just integrate it like in line 15.

Another thing we would like to do is to extend the operation of polynomial. We have not included trigonometry operations on polynomials and et cetera. We would like also to test this Taylor method to a stiff system. Please find the following two files (mytaylor.py and test_case.py) for interested readers if you would like to test yourselves.

## Taylor method with automatic differentiation

I teach numerical analysis course and in the one of the chapters, I teach my students about the numerical solution of ordinary differential equations (ODEs). One of numerical solution methods I teach is the so-called Taylor method. This method works by applying the Taylor series to the solution of the differential equation. Suppose we have one-dimensional differential equation as follow:

and .

Let’s assume that we only consider an autonomous ODE first. To find a solution at the next step, , we need to apply Taylor expansion, as follow:

.

Therefore, depending on how accurate we want our solution is, all we need is to compute the derivatives of . Unfortunately, computing all the derivatives is not an easy task for a computer. We have to derive all the derivatives by ourselves and then input them to the computer.

In this note, I will introduce an automatic differentiation as a tool to compute the derivatives of so that we can compute as accurately as possible. Let us consider the series expansion of as above, but I will use constant to replace the th derivative of ,

.

Let us derive the above series with respect to .

.

Notice that the derivative at the left hand side of the above equation is actually equal to since we know that satisfies the ordinary differential equation. Then we have,

.

Since is a series of then is also a series of . Then both sides of the above equation are series of , thus we can equate each of the coefficient of to get , and so on. The most difficult task in this problem is to find the series of since the function can be anything.

Let’s take an example. Suppose we want to integrate the following differential equation,

and .

Let us choose and compute . As before, we assume that is a series of as follows,

.

Differentiating both sides of the above equation, we get

.

The right hand side of the above is equal to

.

Therefore, we get,

, ,, and so on.

The real question is how to find , and so on. If the function only involves operations such as addition, subtraction and multiplication, it would be easy to find the ‘s. But if the function has operations such as division, exponential, logarithm and trigonometric functions then we have to think a bit harder on how to find ‘s. We go back to the previous example. Since the operations in this example are only multiplication and subtraction, we can easily compute , and so on. Using algebraic modification, we get the following,

, thus

, thus

, thus

and so on.

The more ‘s we compute, the more accurate our solution is. Using Taylor method this way, we can easily apply this method in a program. It should be clear why this method is called automatic differentiation because we don’t need to manually derive all the derivatives.

Next, I tried to numerically integrate the previous example. Below is the graphic of the error of Taylor method with automatic differentiation versus time. As we can see from the figure, that the error of our numerical integrator is so small and it is almost exact. The number of I used in this graph is 10.

I use python to numerically integrate this example. You can find the code to produce the above figure in the end of this note. One of the drawbacks of this method is when you change your ODE, you have to change your code as well. In other numerical integrators such as Runge Kutta, we don’t need to change the whole code, we just need to change the ODE and we should get the solution. Together with my student, I am trying to tackle this problem and I hope it will be posted in here.

import math as m import numpy as np import pylab as plt #preliminary constants order = 10 h = 0.1 t = 0.0 t_end = 5 y0 = 0.5 #defining solution sol = [] sol.append(y0) time = [] time.append(t) #start of the program while t<t_end: a = [] a.append(sol[-1]) for k in range(1,order): if k == 1: a.append(a[k-1]*(1-a[k-1])) else: sum = 0.0 for j in range(0,k-1): sum = sum + a[j]*(-a[k-1-j]) a.append((sum+a[k-1]*(1.0-a[0]))/k) sum = 0.0 for i in range(0,order): sum = sum + a[i]*h**i sol.append(sum) t = t + h time.append(t) #end of the program #real solution computation real_sol = [] for t in time: temp = m.exp(t)/(m.exp(t)+1.0) real_sol.append(temp) #plotting the error versus time sol = np.array(sol) real_sol = np.array(real_sol) time = np.array(time) error = sol-real_sol plt.plot(time[:],error[:]) plt.show()

## How to fold a paper into thirds, a real analysis perspective

Folding a paper into third is useful when you want to mail someone using an envelope. I search around the internet and there are so many ways to do this. So far, I didn’t see the method I am about to explain. I found this method by accident while I am teaching Real Analysis this semester. I am going to prove that this method actually works. Other methods that I found always use Geometry in the proof but I am going to use Real Analysis instead.

The procedure

Please have a look at the following figure.

The above figure is the first step of our method. Take a sheet of paper and let’s call the left side, side A and the right side, side B. First, you need to fold the paper side A as in the second image of the figure above. It doesn’t have to divide the paper equally, you can just fold it anywhere. Once you do that, you undo the fold and you will have a fold mark, which we call it . Next, you need to fold again, but now you need to fold the right side (side B) along the fold mark as in the second row of the above figure. Now you will have two fold marks, the latter is called . Now take a look at the following figure.

Now that we have two fold marks ( and ), we need to fold side A along the fold mark , as in the first row of the above figure. Undo the fold, you will have the third fold mark (we call it ). Next, we fold the side B until it touch the fold mark and we will have four fold marks, and . Continue the step over and over again and at one stage, at the n-step, will be close to one third of the paper and will be very close to two third of the paper.

Simulation

Let’s take an example. Suppose in the beginning, let’s fold side A such that we divide the paper equally. Assume the length of a paper is 1. This means . If we simulate this case, we will get the following table.

n | 1 | 2 | 3 | 4 | 5 |

0.5 | 0.375 | 0.3475 | 0.3359375 | 0.333984375 | |

0.75 | 0.6875 | 0.671875 | 0.66796875 | 0.666992188 | |

6 | 7 | 8 | |||

0.333496094 | 0.333374023 | 0.333343506 | |||

0.666748047 | 0.666687012 | 0.666671753 |

As we see, that it took approximately 4-8 steps until is closed to one third of a paper or is closed enough to two third of the paper. However, what happens if we choose different initial condition. We simulate this using a number of initial condition. Suppose we use an A4 paper which has length of 29.7 cm. We choose a number of different initial conditions. We can see the results in the following figures. The x-axis from the above figure is the initial condition and the y-axis is the number of iteration needed until it is closed enough to one third of paper. Since we use an A4 paper, the x-axis ranges from 0 to 29.7 cm. The tolerance we use in the above figure is 1 mm. In conclusion, we only need to do only maximum four steps until the last fold mark is only 0.1 cm away from one third of the A4 paper.

We relax the tolerance in the above figure. We use 0.5 cm as the tolerance and the number of iterations is slightly improved. It can be seen that if our first trial is close enough to one third of A4 paper, we only need to do one step.

Mathematical proof

Finally, it comes to prove that this methods should work. mathematically not numerically. First of all, we need to mathematically model the above procedures. Let’s assume that the length of the paper we use is 1. Let’s use the same notation as used in the above procedures. Given we will get . Recursively, we could compute and as follow:

and , as n=1,2, … .

Even though there are two sequences and , we only need to consider . We could simplify the sequence as follow.

is given and for .

*Lemma 1
*

*When (as ), the sequence is bounded above (bounded below).*

*Lemma 2
*

*When (as ), the sequence is monotonically increasing (decreasing).*

*Theorem 3
*

*Given , the sequence converges to 1/3.*

**Corollary**** 4**

*Given , the sequence converges to 2/3.*

The proofs of the above results are given to my students as exercises.

This is the end of this note and the following is the code to produce the above figures.

import math import numpy as np import pylab as plt def f(x): return (29.7+x)/2.0 def g(y): return y/2.0 def number_of_iter(x,tol,max_iter): iter = 0 er = abs(x-29.7/3) if er <= tol: return 1 while er > tol and iter < max_iter: iter = iter + 1 y = f(x) x = g(y) er = min(abs(29.7/3-x),abs(2*29.7/3-y)) return iter #main code x = np.arange(0,29.7,0.1) y = [] tol = 0.5 max_iter = 100 for t in x: result = number_of_iter(t,tol,max_iter) y.append(result) y = np.array(y) ax = plt.gca() ax.set_ylim([0,5]) plt.plot(x,y) plt.show()

## How to compute distance between a point and a line

This semester (Even Semester, 2015-2016) I am teaching a new course, that is called Analytic Geometry or Geometry Analytic, both are the same, I think. Don’t get me wrong, the course is not new, it is just I would be teaching this course the first time. When they told me that I was going to be the lecturer of this course, they did not give me a standard, they did not give me a textbook they normally use, or a list of topics that I must cover, perhaps because this course is not a compulsory course. So, I have a freedom, I can choose topics that I want to teach in Analytic Geometry. The first thing I did, was to browse the internet any textbook about Analytic Geometry or any lecture note. In the end, I pick a textbook (Indonesian book) and I choose some topics of my interest to be the material of this course.

Okay, enough for the background, I am sure you don’t want to hear anymore on that. Let’s get back to main point of this note. Long story short, a straight line became one of the topics in my course, and I was interested on how the formula to compute distance between a point and a line is derived.In this case, I only consider two dimensional case and by distance, I mean the shortest distance between such a point and a certain line, which also means the perpendicular distance. If you don’t remember what is the formula, let me recall you.

Consider a straight line , given by the following equation:

.

Suppose we have a point , then the distance between the point and the straight line is

There are other proofs on how to derive the above formula, but I really really like the proof I am going to show you below. I will divide this note into two section. The first section will talk about a straight line and how to get an equation of a straight line. The latter section will derive the formula.

1. A straight line equation

In high school, I think you must know what conditions we need to have in order to obtain a straight line equation. If we have two points in coordinate we can compute the line equation using the following:

.

If we have a gradient and a point, we can also compute the line equation using the following:

.

Of course, in a problem, we won’t get this information so easily. We have work a bit more to get either two points or one point and a gradient and then we are able to obtain the equation of the straight line.

Before I teach this course, I can only conclude that if you want to know the equation of a straight line you need to know either:

(i) two points, or

(ii) a point and gradient of the line.

But, actually there is a third condition, and if we know this condition, we can also compute the equation of a straight line. In the third condition, a line is assumed to be the tangent line of a certain circle. Thus, the characteristics we need to know to form a line are the radius of the circle and the angle between the radius and the positif axis. See the figure below.

In the figure, we can see that a line can be determined uniquely if the radius of the circle and the angle are known. In the first section of this note, we shall derive how to define a line equation given these two conditions.

Suppose we have a straight line, are are given. See the figure below. Consider the point . We are going to find the relationship of and .

The radius , which is , can be computed by adding and . We shall consider first. Consider triangle which is a right triangle at . We have the relationship:

.

Consider another triangle, , which is also a right triangle at . We have the following relationship

as it can be computed that the angle is also .

Therefore, we have , which is the equation of straight line given that and is known.

Before we discuss how to derive the formula to compute the distance between a point and a line, I would like to discuss how to find and if we know the general equation of a straight line . Consider a line equation, then we move $c$ to the right hand side and multiple both sides with a non zero constant , . We shall choose such that and . Therefore, we have

and

our equation of line becomes:

.

Here, we have that the right hand side of the above equation is , and we choose the positive value to get . The angle can also be computed once we determine .

2. Distance between a point and a line

To compute a perpendicular distance between a point and a line, we shall use the above result. Consider a straight line and a point in the following figure.

We want to compute . In order to do that, we need to make another line that is parallel to the line and passing through point . This line, because it is parallel to and, has the following equation:

Thus the distance between the point and the line can be easily computed by considering the absolute difference between and as follow:

As we know from the first section that we can substitute the latter expression into:

or

which is the same as the formula we mentioned in the beginning of our note.

## Notes on diagonalizable linear operators

Okay, I have a few things in my mind about this topic and I don’t want to lose them tomorrow or the day after. Therefore, I created this note. Hope it is useful to other people as well. Background of this note are as follows:

- Suppose is an matrix and it is diagonalizable. Therefore, by definition, there is an invertible matrix and a diagonal matrix . However, I always forget the relationship between and , whether it is or . Generally, those two are no different, but we can choose such that the column vectors of matrix are the eigenvectors of matrix , hence we have to know precisely which one it is, otherwise it gets wrong. Until now, when I forget about this, I always derive it and it takes some of my precious time (haha) but now after I have this, I can just open the Internet and look for this note.
- Point 1 above talks about diagonalizability of a matrix. But generally, we have a linear operator acting on a general vector field instead. A linear operator is called diagonalizable if there is a basis B such that the matrix representation of this linear operator is a diagonal matrix. It seems for me, diagonalizability of a linear operator and that of a matrix are talking about two different things. One is talking about how to find a basis, while the other is talking about how to find an invertible matrix. However, these two concepts turn out to be the same.

We begin with the following theorem.

*Theorem 1 (Coordinate-change matrix)*

*Let be a standard basis and be another basis for an -dimensional linear space . Then there is an invertible matrix such that for every *

*. (1)*

*Matrix is called the transition or coordinate-change matrix from the basis to the basis . Note that and are the coordinates of vector with respect to basis and respectively. In fact, the column vectors of matrix are the coordinates of the basis vectors of with respect to the standard bases (i.e. if then ). *

We won’t prove the theorem as it can be found in any linear algebra textbook. However, using this theorem we can relate the diagonalizability of a linear operator and that of a matrix.Suppose is a diagonalizable linear operator on an -dimensional linear space . Take then let be . Suppose is a standard basis in and is a basis in that consists of independent eigenvectors of .

Then we have the following.

(i) , where is a representation matrix of with respect to standard basis .

(ii) , where is a representation matrix of with respect to basis . We also know that is a diagonal matrix.

We want to show that using the theorem 1, or . From equation (1) we get:

.

Hence, we have . While from point (ii) we have . As a conclusion, we have,

.

We have derived that in fact, is the right one. We also derived that the invertible matrix has such a close relationship with the basis as the column vectors of are the basis vectors of , which are the eigenvectors of the linear operator . This conclude my note.

## Academic Recharging

I first hear about this phrase in the Indonesian government of education website. Academic recharging is one of fund application schemes provided to academician who feels bored and sometimes tired doing teaching in their respective university. This scheme is provided to ‘recharge’ them in some way such that they are able to go abroad conducting research with their colleagues overseas. Indonesian government hopes by doing this scheme, lecturer and academician could update their knowledge to the current topics so that Indonesian academic society would not be left behind.

But I have found my way of academic recharging. And I give many thanks to ICTP and MIT. Courses that are provided by ICTP and MIT have been recorded and have been available online. I don’t know since when this happens but for me it is great. I can update my knowledge with some new information that I have never learned before.

After downloaded a video, I can watch the course that I am interested. When I don’t understand a thing, I can just pause and google them. I can pause anytime I want when some students knocking my door. I strongly recommended this way of learning to my colleagues and my students as this is much as fun as watching movie.

Here are some references that you might like.

## Mixture problem in Calculus

I keep forgetting the way to solve this problem. So, when I in future have no clue I know where to look.

**The problem**

A 200-galon tank is half full of distilled water. At time , a solution containing 0.5 pound/galon of salt enters the tank at the rate of 5 gal/minutes, and the well-stirred mixture is withdrawn at the rate of 3 gal/minutes.

a. Give a mathematical model representation of the above problem.

b. At what time, will the tank be full?

c. At the time the tank is full, how many pounds of salt will it contain?

**The mathematical model**

The model describing the above process is based on the following formula:

rate of change of the amount of salt = (rate of salt arrived) – (rate of salt departed)

Suppose is the volume of the liquid in the tank at time . The volume of liquid inside the tank will increase as the inflow (5 gal/minutes) is bigger than the outflow (3 galon/minutes). Thus, we have

100 galon + (5 gal/min – 3 gal/min) min,

gal,

as we know that initially the tank is half full (100 gal).

Suppose is the amount of salt inside the tank at time . The rate in of salt is as follows,

rate in (pound/min) (0.5 pound/gal) (5 gal/min) 2.5 pound/min,

while the rate out is

rate out (pound/min) outflow (gal/min)

(pound/min)

(pound/min).

Therefore, the mathematica model is given by,

. (1)

**The solution**

First we determine time at which the tank will be full. We use the following equation,

,

We solve for when the volume is 200 galon, then we obtain .

To solve the differential equation (1) we need the initial condition

as follow,

.

We are going to use Maple to solve the problem

` > model := diff(y(t),t) = 2.5 - (3*y(t))/(100+2*t); `

` > init := y(0)=0; `

` > dsolve({model,init}); `

We obtain the solution that is given by

When , the amount of salt inside the tank will be

.

## Your says