of 7

Introduction to Scientific Computing Lecture 5

Introduction to Scientific Computing Lecture Professor Hanno Rein Last updated: October 3, 16.7 Newton s method in 3D See Computational physics book..8 Multiple roots In many cases, functions have multiple
0 views7 pages
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Documenttranscript
Introduction to Scientific Computing Lecture Professor Hanno Rein Last updated: October 3, 16.7 Newton s method in 3D See Computational physics book..8 Multiple roots In many cases, functions have multiple roots. For example f(x) = x 2 1 has roots at x = 1 and x 1 = 1. How can we find multiple roots? All the above methods give us only one root. Well, the short answer is that in general we might not be able to find all the root of a function. Especially if you think of a function like sin(x) which has an infinite number of roots. However, there is a trick that allows us to find at least multiple roots in simple functions. Suppose the function you are trying to find the root is f(x) and you have already found a root x. Then, look at the function h(x) = f(x) x x and find its roots. The figure below shows the function f(x) = x 2 1 in red. Suppose our first attempt at root finding resulted in the value x = 1. Then, the function h is h(x) = f(x)/(x 1), which is plotted in blue. You can see that the function h has now only one root, namely the one we missed before at x 1 = 1. 1 Figure 1: Finding multiple roots. 6 Interpolation Let s start with the definition. Interpolation is the method of constructing new data points within the range of a known data points. Suppose we are given a dataset with the average temperature for each of the year. The dataset for Toronto is printed in Table 1 and plotted in Figure 2. Each data point represents the average temperature during one. Note that the s are enumerated with integers starting at (January). There is no information given about the temperature on a particular day Figure 2: Average ly temperature in Toronto ( = January). Source: Environment Canada. 2 Month Average temperature [C] Table 1: Temperatures in Toronto ( = January). If someone asks, What is the temperature at the end of January, the honest answer would be I don t know. The dataset that was given to us only knows about the temperature averaged over the entire of January. However, one can see by eye, that there is a clear trend: it is coldest in January and warmest in July. If you want to be able to give an answer but don t have any additional data available, we use a method called interpolation. In general, you will be given a set of N function values of an unknown function f in the form (x, f(x )), (x 1, f(x 1 )),..., (x N 1, f(x N 1 )) and your task is to estimate f(x) for an arbitrary x in x x x N Interpolation with a piece-wise constant function Figure 3: Temperature in Toronto ( = January). Piece-wise constant interpolation. 3 To come back to the question from above, a reasonable answer would be, Well, I don t know what the typical temperature at the end of January is, but it is probably not drastically different from the average temperature in January.. This idea corresponds to the simplest interpolation one can do: using piece-wise constant functions. It is sometimes also referred to as nearest-neighbour interpolation. We simply choose the x i and the corresponding f(x i ) which is closes to the x that we are interested in. The result is a discontinuous series of constant functions. If you know nothing about the data points that are given to you, to get a value of the interpolated function f(x), you need to go through the entire list of known data points to find the one that is closest. For the temperature data from above, we can simply things quite a bit. First, we have the data already sorted. Second, the known data points have integers (the s) as their x value. So we only need to find the closes integer to the x that we are interested in and then look up the known data point. Figure 3 shows a piece-wise constant function interpolation to the Toronto weather data. The following function shows a possible implementation in python, assuming the known data points are given in the array temperature[]. def temperature constant interpolation(x): x = int( round(x)) return temperature[x] Code 1: Python listing implementing piece-wise constant interpolation of the temperature data. We can also apply this method to a function that depends on two variables x and y. In this two dimensional case, we ll end up with a Voronoi diagram as shown in Figure 4 Figure 4: Example of a piece-wise constant interpolation in two dimensions. (CCSA). Source: Wikimedia 4 6.2 Interpolation with a piece-wise linear function Figure : Temperature in Toronto ( = January). Piece-wise linear interpolation. There are several disadvantages with a pice-wise constant interpolation. First of all, it s not a very good approximation. Most likely, it is warmer at the end of April than at the beginning of April. However, we have assumed a constant temperature across the entire. Furthermore, at the transition from end of April to beginning of May the temperature suddenly jumps by degrees. This seems unrealistic. Mathematicians call the piece-wise constant interpolation discontinuous. We can indeed do better. What if we just draw a straight line from one data point to the next? This is called piece-wise linear interpolation, sometimes just referred to as linear interpolation or lerp. The result looks much smoother, as shown in Figure. Now the function is continuous. However, some people will still not be happy with this. If you look closely, you ll see that the function has a sharp kink at every data point. That means we can t calculate the derivative of the interpolating function at those points. Hence the piece-wise linear interpolation is non-differentiable. We ll later discuss another interpolation scheme which is both continuous and differentiable. But before we do that, let s look at how we calculate the piece-wise linear function. First, we need to find the given data point to the left and right of the value x that we are interested in. Let s call them x l and x r. Then, the interpolation function f(x) is f(x) = f(x l ) + ( f(x r ) f(x l ) ) x x l x r x l Remember that the values f(x l ) and f(x r ) are given to us. What we don t know is how the function f looks like, which is why we are constructing an approximation (an interpolation), which we call f. The python source code to create the piece-wise linear interpolation of the temperature data is shown in Code 2. Note that the code snippet is specific for the periodic temperature example from. It assumes the temperatures are stored in the one dimensional array temperature with indices ranging from to 11. Note that the code does not check if x l or x r are exceeding the array bounds. def temperature linear interpolation(x): xl = int(math.floor(x)) xr = int(math.ceil(x)) f xl = temperature[xl] f xr = temperature[xr] return f xl + ( f xr f xl ) ( x xl)/(xr xl) Code 2: Python listing implementing piece-wise linear interpolation of the temperature data. 6.3 High order polynomial interpolation So far, we have only considered the point directly to the left and right of the value x that we want to interpolate to. What if we take into account all the data points that we are given. If we have N data points, then we can find a polynomial of degree N 1 that goes through all the points and which we can evaluate at any point x to find the interpolated value we want to know. This is exactly what the Lagrange interpolation polynomial does. Given a set of N data points of the form (x, y ),..., (x N 1, y N 1 ) the interpolation polynomial in Lagrange form is a linear combination where the Lagrange basis polynomials are l j (x) = m N 1 m j L(x) = N 1 j= y j l j (x) x x m = (x x ) x j x m (x j x ) (x x j 1) (x j x j 1 ) (x x j+1 ) (x j x j+1 ) (x x N 1) (x j x N 1 ) Have a look at the basis polynomials. They are constructed such that they are exactly zero at all data points points except the j-th one, where the basis polynomial is 1. This guarantees that all data points lie on the curve. An example of a Lagrange polynomial, fitted to our temperature dataset is shown below. 6 Figure 6: Lagrange interpolating polynomial to the temperature dataset. This figure also illustrates a few of the problems associated with high order polynomial interpolation. First, you can see that outside of the interval where we have data points, the curve goes of very quickly. This makes sense, since it is a high order polynomial after all! Second, you can see a hint of ringing. Just between the data points at x = and x = 1 you can see a local maximum. This is clearly not shown in our original data and purely an artifact of our interpolation routine. Ringing can be much worse than in the example shown above. Especially if the data points are spaced equidistantly or if there is some noise in the data (which will be for all measurements taken in a real world scenario). One way to avoid ringing is to choose the x points according to Chebyshev nodes. We will not cover this in the lectures, but you might want to keep the name in mind. Nevertheless, you can see that the Lagrange polynomial is an excellent choice to get a good estimate of interpolated values in-between data points. The curve is very smooth, in fact, it is infinitely differentiable. 7
Advertisement
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x