Taylor-series Method

Consider the ``Taylor Series'' interpretation of problem (see 0.1.3). In this method, we assume (or determine, which is the right thing to do) that all the necessary partial derivatives exist.

Forward Euler was a first order method and in this light, results from keeping the first term of Taylor series. Why not keep the $p^{th}$ order term in Taylor series? Is this ``better'' than Forward Euler? In what ways? Clearly, it is more expensive computationally, so if we are going to develop a technique that is computationally more expensive we'd better make sure we find out in what circumstances it works, if at all.

First, look at how this works by example:

Example: Solve $\left\{\begin{array}{ll} x'= \cos t-\sin x+t^2\\ x(-1)=3 \end{array}\right.$

recall $x(t+h)=x(t)+h x'(t)+\displaystyle \frac12 h^2 x''(t)+\frac16 h^3 x'''(t) +\frac{1}{24} h^{4} x'''' (t)+\cdots$

$$x''&= -\sin t-x' \cos x +2t$$

$$x''' = -\cos t -x'' \cos x + (x')^2\sin x+2$$

$$x^{''''} = \sin t +(x')^3 \cos x +3x'x'' \sin x- x''' \cos x$$

let's stop there. So we say that we're constructing ``an approximation of order $4,$'' which means that THE LOCAL TRUNCATION ERROR is ${\cal O}(h^5)$: as $h\rightarrow 0$ the local error is proportional to $Ch^5$ (we don't know what is $C$ and how big it is).

Algorithm

input $M$ (steps), $t_0$ and $t_f$
output $(x_n, t_n);$ compute $\left\{\begin{array}{ll} h= (t_f -t_0)/M,\\ t_k=t_0+kh & k=0\cdots M+1 \end{array}\right.$

for $k=1: M$

$$x'=\cdots$$

$$x''=\cdots$$

$$x'''=\cdots$$

$$x''''=\cdots$$

$$x_{k+1}=x_k+h\Big(x'+\frac h2\Big(x''+\frac h3\Big(x'''+\frac{h}{4}x^{''''}\Big)\Big)\Big)$$

$\Box$

In above example we can calculate local truncation error:

$$E_n\approx\frac{1}{(n+1)!}h^{n+1}x^{(n+1)}(t+\theta h)\quad 0<\theta <1$$

in above example $n=4$. Could use simple finite differences:

$$E_4\approx\frac{1}{5!}h^5\Bigg[\frac{x^{('''')}(t+h)-x^{('''')}(t)}{h}\Bigg]= \frac{h^4}{120}\Big[x^{('''')}(t+h)-x^{('''')}(t)\Big]$$

Pros and Cons

1)

Number of operations can be large. This is not always a problem these days considering how cheap and fast computers are at present. In general the step size can be made larger the higher the order of the Taylor scheme. But a computational count will tell you whether it is more effective to compute a lot at each step, and take larger steps, or compute little at each step and make due with smaller step sizes. Usually it is more advantageous to go with good lower order method and small steps, but this depends on the problem..

2)

Need to know about smoothness of solution. This is neither a pro or a con since you should always know this, but it is senseless to use a high order method when the solution has unbounded high order derivatives.

3)

Can use symbolic program to compute all the series expansion stuff reducing programming errors, so in principle, it is not too hard to compute high order derivatives required.

4)

For oscillatory functions, a high order Taylor seems a good choice, but can lead to problems of loss of significance in the computation if not programmed carefully.

In general the high order Taylor Method is used ``in special situations'' such as when we want the quantity at a point with low truncation error. $\Box$

QUESTION: Do we always seek to use a high-order method? What does the ORDER of a method have to do with accuracy?

First off, the ``order'' is a property of a particular scheme. The ``accuracy'' merely refers to how ``close'' a particular approximation is to the exact answer. It is actually up to you to define precisely to your audience what you mean by ``accurate'': it may simply mean how far the approximation is to an exact answer, in some appropriate norm. But it can be more complicated: as we will later see in the context of solving wave equations, accuracy may be favoring the overall shape of the wave, rather than its magnitude, or its overall phase, etc).

Suppose we define by accuracy merely the Euclidean distance between the approximate and exact solution at a single point. Then, provided that a scheme converges, the order of a method will tell you the rate at which, in the limit as the step-size goes to zero, the approximation approaches the exact answer at any or all points in the domain of the problem. A high order method will approach the exact answer at a faster rate, if you make your step-size smaller. Now, suppose you have two different convergent schemes with different rates of convergence. Is the one with higher order of convergence more ``accurate''?? The answer is ``it depends''.

YES, if the step size is the same in both methods, the higher-order method will be more accurate (assuming there are no round-off errors).

NO, not necessarily. If you compute with the low order method using a small $h$ and compute with the high order method with a large $h$ it is possible to get higher accuracy with the low order method.

Usually, high order methods are more involved computationally and low order methods less so. Ultimately, you desire high accuracy and you're willing to pay for it in terms of time in computing. If a low order method takes little computer time per time step, compared to a higher order method, the amount of computer time required to get an answer depends on the per-step size time, times the number of steps required. Hence, for a given accuracy you can (and should) always estimate which method is best to use. Now, in these days of fast computers, sometimes a low order method is preferred. But back in the old days, when computers were really room-fulls of people operating adding machines and/or slide rulers in a systematic way (cf. Virtual Museum of Computing), high order methods were often sought. As you might imagine, the ``step-size'' in problems solved in this fashion was required to be quite large.

Another reason for which a low order method and/or an explicit method is preferred to an implicit method has to do with the other issue in computational implementation: storage use. A high order method and/or some implicit methods will require vast amounts of memory usage...in some cases, more than you have. Often times the trade off amounts to giving up speed in the computation in the interest of memory, which might force you to use a lower order method and/or an explicit method.

The storage vs. speed on machines has become a more important issue these days, of parallel computing. A scheme that requires a great deal of communication between processors will tax most significantly the gains in speed-up possible in parallel processing. A low order method usually will be more local, leading then to less communication between processors.

In summary, ``Order'' is not the End of All Things. Decide on what accuracy you're willing to live with and what your criteria is going to be. Then, compare schemes for the approximation and include in your decision of which one to pick the one that will deliver the most robust results with a level of computational efficiency that you are willing to live with: this estimate should be done WAY AT THE BEGINNING. There is no need to gamble gobbs of time on an effort that you could have otherwise determined (with little effort) is less than satisfactory.