Advanced Numerical methods lecture notes

advanced numerical methods for complex environmental models needs and availability. and advanced numerical methods for hyperbolic equations and applications pdf free download
NancyWest Profile Pic
NancyWest,Germany,Professional
Published Date:12-07-2017
Your Website URL(Optional)
Comment
MA50174 ADVANCED NUMERICAL METHODS – Part 1 I.G. Graham (heavily based on original notes by C.J.Budd)Aims 1. To be an advanced level course in numerical methods and their applications; 2. To (introduce and) develop confidence in MATLAB (and UNIX); 3. To teach mathematical methods through computation; 4. To develop numerical methods in the context of case studies. Objectives 1. To learn numerical methods for data analysis, optimisation,linear algebra and ODEs; 2. To learn MATLAB skills in numerical methods, programming and graphics; 3. To apply 1,2 to Mathematical problems and obtain solutions; 4. To present these solutions in a coherent manner for assessment. Schedule 11 weeks of: 1 workshop in Lab; 1 lecture/problems class; 1 general lecture. Books • N and D Higham “Matlab Guide” SIAM • Vettering et al “Numerical Recipes” CUP • A Iserles “A First Course in the Numerical Solution of DEs”, CUP • C.R.MacCluer “Industrial Maths, Modelling in Industry, Science and Government” Prentice Hall. • L.L.Ascher and L.Petzold “Computer methods for ordinary differential equations and differential algebraic equations”, SIAM. • C.B. Moler, Numerical Computing with MATLAB, SIAM. Other Resources • I.Graham, N.F. Britton and A. Robinson “MATLAB manual and Introductory tutorials.” • M.Willis, notes on UNIX • Unix tutorial: http://www.isu.edu/departments/comcom/unix/workshop/unixindex.html • Additional Unix tutorial: http://people.bath.ac.uk/mbr20/unix/ 1The website for the first part of the course is http://www.maths.bath.ac.uk/igg/ma50174 The website for the second part of the course is http://www.maths.bath.ac.uk/cjb/MA50174/MA50174.html Email addresses of the lecturers: I.G.Grahambath.ac.uk cjbmaths.bath.ac.uk 2General Outline Thecoursewillbebasedaroundfourassignments,eachofwhichisintendedtotaketwoweeksandwhich contribute 20% each to the final total. The assignments can be completed in your own time, although assistance will be given during the lab workshops and you can ask questions during the problem classes. Therewillalsobeabenchmarktestduring whichyouwillberequiredtoperformcertaincomputational tasks in UNIX and MATLAB in a fixed time period. This will be given as a supervised lab session and will count for 20% of the course. The assessed assignments are: 1. Data handling and function approximation; 2. Numerical Linear Algebra and applications; 3. Initial value ordinary differential equations, with applications to chemical engineering; 4. Boundary value problems. 3Contents 1 Introduction 6 1.1 Modern numerical methods for problems in industry . . . . . . . . . . . . . . . . . . . . 6 1.2 An example of this approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 A brief introduction to MATLAB 11 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 General Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Manipulating Matrices and Vectors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 Programming in MATLAB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4.1 Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4.2 Making Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4.3 Script and function files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4.4 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4.5 Structured Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4.6 Help . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4.7 Recording a MATLAB session . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 Operations on, and the analysis of, data. 17 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Curve fitting using regression and splines . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.1 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2.2 Regression. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2.3 Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3 The Discrete Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3.3 An Interpretation of the DFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3.4 An example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3.5 Denoising a signal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4 Finding the roots of a nonlinear function and optimisation. 26 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2 Finding the zero of a single function of one variable . . . . . . . . . . . . . . . . . . . . . 26 4.2.1 Secant as an Approximate Newton Method . . . . . . . . . . . . . . . . . . . . . 29 4.3 Higher dimensional nonlinear systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.4 Unconstrained Minimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.4.1 The Method of Steepest Descent . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.4.2 Variants of Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.4.3 Applications of minimisation methods . . . . . . . . . . . . . . . . . . . . . . . . 33 4.5 Global Minimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 45 Linear Algebra. 38 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.2 Vectors and Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3 Solving Linear Systems when A is a square matrix . . . . . . . . . . . . . . . . . . . . . 40 5.3.1 Direct Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.3.2 Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.4 The QR decomposition of the matrix A . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.5 Eigenvalue calculations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.6 Functions of a matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5Chapter 1 Introduction 1.1 Modern numerical methods for problems in industry Most industrial problems require the computational solution of a variety of problems. The solution process generally involves three stages. 1. Front end: Problem description in easy manner. GUI - Java - Internet 2. Main computational effort. Various tasks including: Data input Data manipulation . Image and signal processing Linear Algebra Optimisation Solution of ordinary/partial DEs Approximation 3. Output: Typical 3D graphics. Often now animated. Most “traditional” numerical courses concentrate on item 2 and teach this in isolation. They also don’t look at software packages. This course will aim to teach computational mathematics and numerical methods in the overall context of 1,2,and 3 through: • The use of the high level mathematical package MATLAB. • Understanding of the mathematical principles behind how the various algorithms in MATLAB work and their limitations. • Learning some ideas of structured programming through using the MATLAB language. • Looking at all theory and methods in the context of case studies found from real applications. This course is meant to give you some of the tools that you will need for further Msc courses and also for your project.In particular it links to: The Modelling Course (MA50176)...how do you recognise and formulate a problem? The Scientific Computing Course ...how do you apply computational (MA50177 which uses methods to the large scale FORTRAN 95) problems that you encounter in real applications when you must use a different programming language to get a solution quickly. 6Further theory underlying the numerical methods used in this course can be found in the optional courses in this MSc. In summary, the approach behind the implementation of a numerical method to an industrial problem can be summarised as follows: • Solve the right problem ...make sure your model is right; • Solve the problem right ...use the best methods; • Don’t reinvent the wheel ...Be aware of the existence of good software and be prepared to use it. • Keep a healthy scepticism about your answers. 1.2 An example of this approach Wesummarisewithashortstudyofafamoussystem: thependulum,whichisdescribedbythefollowing second order ordinary differential equation 2 d θ +sin(θ) =0 (1.1) 2 dt dθ subject to initial conditions (for example θ = θ and = 0 at t = 0). It is known that this problem 0 dt has periodic solutions. 1. The Traditional Mathematical Approach: Change/simplify problem to 2 d θ +θ =0 . (1.2) 2 dt Now solve this analytically to give θ(t) =Asin(t)+Bcos(t) (1.3) Thisapproachisfineforsmallswings,butisbadforlargeswings,wherethesolutionisqualitatively wrong. 2. The Traditional Numerical Method: Now rewrite (1.1) as the system: dθ/dt =v (1.4) dv/dt =−sin(θ) (1.5) Divide time into equal steps t =n△t and approximate θ(t),v(t) by n θ ≈θ(t ), V ≈v(t ) (1.6) n n n n Now discretise the system (1.4), (1.5). For example by using the Euler method: θ −θ n+1 n =V n △t V −V n+1 n =−sin(θ ) n △t Finallywriteaprogram(typicallyasaloop)thatgeneratesasequenceofvalues(θ ,V )plotthese n n andcomparewithreality. Theproblemwiththisapproachisthatweneedtowriteanewprogram everytime we want to solve an ODE. Furthermore, any program that we will write will probably not be as accurate as one which has been written (hopefully) and will be tested by “experts”. Intheaboveexamplethevaluesofθ andV quicklyspiralouttoinfinityandallaccuracyislost. n n 73. Software Approach: Instead of doing the discretisation “by hand” we can use a software package. We will now see how we use MATLAB to solve this.The approach considered is one that we will use a lot for the remainder of this course. (a) Firstly we create a function file func.m with the ODE coded into it This is the file %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % MATH0174 : function file func.m % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % This file sets up the equations for % theta’’ + sin(theta) = 0 % % To do this it takes thet(1) = theta and thet(2) = theta’ % It then sets up the vector thetprime so that % % thetprime(1) = theta’ % thetprime(2) = theta’’ % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % function func.m % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function thetprime=func(t,thet) thetprime=thet(2);-sin(thet(1)); It is a sequence of commands to describe the system: ′ ′ θ =θ , θ =−sin(θ ) 2 1 1 2 In this file anything preceded by a % is a comment for the reader (it is ignored by the computer). Only the last two lines do anything. (b) Now set the initial conditions, and the time span t∈ 0,10 through the commands start= 0;1; tspan = 0,10 (c) Next use the MATLAB command ode45 to solve the ODE over the time span; This imple- ments a Runge-Kutta routine to solve (1.1) with a Dormand-Price error estimator. You can specify the error tolerance in advance (d) Finally plot the result. This will look like plot(t,thet) or plot(thet(:,1), thet(:,2)) The code to implement this takes the following form: 8%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % MATH0174: Code to solve the pendulum equation given % % the function file func.m % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % We specify an interval of t in 0,10 % tspan = 0 10; % % We specify the initial conditions thet,v = 0 1 % start = 0;1; % % Options sets the tolerance to 1d-6 % options = odeset(’AbsTol’,1d-6); % % Now solve the ODE using the Dormand-Price explicit Runge-Kutta % method t,thet = ode45(’func’,tspan,start,options); % % Now plot the solution % plot(t,thet) pause % % Now plot the phase plane % theta = thet(:,1); v = thet(:,2); plot(theta,v) axis(’equal’) The output of from this code is the following plots. These plots are fairly crude and by using the plotting commands in MATLAB you can make them look a lot better. Over the short 91.5 1 0.5 0 −0.5 −1 −1.5 0 1 2 3 4 5 6 7 8 9 10 1 0.8 0.6 0.4 0.2 0 −0.2 −0.4 −0.6 −0.8 −1 −0.5 0 0.5 1 time span we have considered the MATLAB code has given an accurate answer. 4. The best Approach of all - use Geometry: It is worth saying that even MATLAB is not perfect. Over a long period of time the MATLAB solution and the true solution of the pendulum will drift apart (see Assignment 3). In this case it is possible to prevent this drift by using a different method based upon the underlying geometry of the solution. An example of this is the Sto¨rmer - Verlet method which is given by △t θ 1 =θ + V n n n+ 2 2 V =V −△tsin(θ 1) n+1 n n+ 2 △t θ =θ 1 + V n+1 n+1 n+ 2 2 In Assignment 3 you will investigate the advantages of using such a method, over the use of ode 45. 10Chapter 2 A brief introduction to MATLAB 2.1 Introduction The majority of this course will use MATLAB. This will be familiar to some and not others. MATLAB iswritteninCandfitsonmostPCsrunningundereitherWindowsorLinux.Westartbydiscussingsome of its features. Then the course will teach various numerical analysis concepts through MATLAB.These notes are only meant to be a brief overview. For more detail you should read the MATLAB manual (by Graham, Britton and Robinson) and also the MATLAB guide by Higham & Higham MATLAB has the following features 1. Ithasahighlevelcodewithmanycomplexmathematicalinstructionscodedassingleinstructions. e.g.to invert a matrix A you type inv(A), to find its eigenvalues you type eig(A). 2. Matrices and vectors are the basic data type. 3. Magnificent and easy to use graphics, including animation. In fact you often use MATLAB as a very high level plotting engine to produce jpeg, pdf,and postscript files from data sets that may be created from a calculation in another high-level language. 4. There are many specialist toolboxes→ PDE → control → signal and image processing → SIMULINK 5. It is a flexible programming language. 6. Very good documentation is available. 7. An increasing amount of code is written in MATLAB both in universities and in industry. 8. Itisaninterpretedlanguagewhichmakesitflexiblebutitmaybeslowerthanacompiledlanguage. ++ It is also rapidly getting faster. However it can’t yet compete with FORTRAN for sheer speed, C for total flexibility or JAVA or Visual Basic for internet applications. We will have the opportunity to compare MATLAB with FORTRAN later on in this course. 2.2 General Points MATLABhasessentially one datatype. Thisisthe complex matrix. Itperformsoperationsonmatrices usingstateoftheartnumericalalgorithms(writteninC).Forthiscoursewewillneedtoknowsomething about the speed and reliability of these algorithms and their suitability for certain operations, but we 11don’t need to know the precise details of their implementation to use MATLAB. Later on you will write some of your own algorithms which you can compare with MATLAB ones.See other MSc courses for more detailed descriptions of the algorithms themselves.. • To give an example. Suppose A is a matrix eg.   10 9 8 7   6 5 3 4   A =   1 2 7 8 0 3 0 5 We set this up in MATLAB via the command: Second row z A =10 9 87 ; 6 53 4 ;1 2 78 ;03 0 5 ; z First row Here the semicolons between the groups of numbers are row separators. The last semi-colon sup- presses the output. • We can invert A to give the matrix B by B = inv (A). Usually MATLAB uses a direct method based on Gaussian elimination to do this inversion. This is good, but may not be optimal for certain problems. For these MATLAB has a suite of different other methods, mostly based on iterative techniques such as “gmres”. You can also write your own routines and we will do this in assignment 4. IMPORTANT POINT MATLAB inverts a matrix numerically to within a certain precision. It can work with large matrices. Other packages such as MAPLE invert a matrix exactly using symbolic operations. This process takes a lot longer and can only be used for small matrices. 2.3 Manipulating Matrices and Vectors. Most MATLAB commands are pretty obvious; but setting up and manipulating matrices and vectors needs a little care. To set up a matrix such as:   1 2 A = 3 4 we type: A =1 2 ;34 . To set up a new vector such as x =(1 2 3) we type: x= 12 3 and to set up a column vector such as   3   x = 4 5 12we either type: x=3; 4; 5 or we type: ′ x=3 4 5 տtranspose operator All matrices have a size. So if A is an n×m matrix (n rows, m columns), then the command size(A) returns the vector n m. Thus size(48) = 12 ′ size(48) =2 1 If size(A) = n m and size(B) = m k then you can multiply A by B and get a n×k matrix, to give C via C =A∗B. If x and y are vectors then MATLAB has various facilities for setting them up and manipulating them. 1. We often want to set up a vector of the form x= a,a+d,a+2d,...,b This is useful for plotting points on a graph. MATLAB sets up x through the command: x= a : d : b; 2. We might want to plot a function of x eg. sinx. To do this we firstly create a new vector y through the command y = sin(x); now we plot the output through the command plot(x,y) The plot command gives you a basic graph. However, MATLAB plotting is very flexible ...you can change axes, label things, change the colour and the line type. For a detailed description of the use of these commands see Higham & Higham, Chapter 8. If you have 3 vectors x,y,z ; you can plot all three via the command plot3 (x,y,z). Later on we will look at animating these plots. 3. Given row vectors y = (y ,...y ) 1 n x = (x ,...x ) 1 n ′ Wecanformulatetheirscalarordotproducty.xviathecommandx∗y . (Thisisamatrix-vector ′ multiplication of the row vector x with the column vector y .) Alternativelywemaybeinterestedinthevectorz =(x y ...,x y )Thisisgivenbythecommand 1 1 n n z =x.∗y Note the dot . makes this an operation on the components of the vectors. Similarly the vector   2 2 2 1 1 (x ,...,x ) is obtained by typing x. and the vector ,..., is obtained by typing 1./x. 1 n x x 1 n 4. You can access individual elements of the vector y = (y ,...,y ,...,y ) 1 k n For example if you want to find y you type y(k). Similarly, if you type y(1 : 4) then you get k y ,y ,y ,y . 1 2 3 4 132.4 Programming in MATLAB MATLAB has a powerful programming language which allows you to combine instructions in a flexible way. We will be expecting you to use this language when using MATLAB to solve the various case studies in the assignments. Full details of the language are given in the MATLAB manual and in Higham and Higham, and you should read these. 2.4.1 Loops These allow you to repeat the use of commands. A simple loop takes the form : for i =j :m :k statements end which increases i from j to k in steps of m. You can also nest loops. An important Matrix in numerical analysis is the Hilbert matrix A = 1/(i+j). In MATLAB you could set this up by using a double ij loop in the manner: for i =1 :n for j = 1 :n A(i,j) = 1/(i+j); end end IMPORTANT NOTE. The vector and Matrix operations in MATLAB mean that many operations that would use loops in languages such as FORTRAN can be achieved by single instructions in MATLAB. This is both quicker and clearer than using a loop. 2.4.2 Making Decisions Usually in any code we have to make decisions and then act on these decisions. This is generally achieved in one of two ways. The while statement takes the form while (condition) statements end This tests the condition and if it is true it repeats the statements until it is false. The if-then-else statement takes the form if (condition) statements1 else statements2 end In this case it executes statements1 if the condition is true and statements2 if it is false. AWFUL WARNING TO LONG ESTABLISHED FORTRAN USERS: MATLAB has NO goto statement ( You never really had to use it) 142.4.3 Script and function files We will be making extensive use of script and function files, which are both lists of instructions stored as name.m. A script file is just a list of instructions, run by typing name. Generally you would use a script file to do a complete task. In contrast a function file accomplishes a sub-task in the code which you may want to use repeatedly. Typically a function file has a set of inputs and a set of outputs. For example we used a function file to set up the derivatives of the differential equation describing the pendulum. The variables in a function file are local i.e. they do not change what is going on in the program which calls the function file. Very often we also want to specify variables as being global so that they take the same value in both the main code and the function file. 2.4.4 Input and output You can input a variable directly. x = input (‘‘Type in the variable x’’) or (generally better) from a file. For example the file data may include a series of measurements x of i a process at times t stored as a series of lines of the form t x (so that t and x are two columns of data i i i in this file). To access this information type load data t = data (:,1); x= data (:,2); The vectors x and t are now in your MATLAB workspace, and you can work directly with them. You can save variables x,t created in a MATLAB session by typing: save filenamext This stores x and t in the file filename.mat. To use these variables in future calculations type load filename MATLAB has a wide variety of formats for outputting data, from simple lists of numbers, through to plots or even movies stored as postscript, pdf, jpeg etc files. Full details are given in Higham and Higham 2.4.5 Structured Programming You will be writing some programs in this course and more in the course on Scientific Computing. Programsaremucheasiertofollow,andaremuchmorelikelytowork,iftheyarewritteninastructured way. Some useful hints for doing this are as follows. 1. Break up the program into well defined tasks (which may be coded in function files) and test the code for each task separately. For example, it is useful to have a file which just handles input and another which just handles output. 2. Makeextensive(butcareful)useofcomments.%Inparticularatthestartofeachscriptorfunction file you should state clearly what the file does and what variables it uses. 3. Give your variables names which clearly indicate what they represent. 4. Make use of blank lines and indenting to break up your code. 5. Don’t use a loop if there is a MATLAB command which will do the job for you. In the Scientific Computing course you will learn a lot more about structured programming in the context of large scale code development. 152.4.6 Help The most useful command in MATLAB is help. This gives extensive help on all MATLAB commands. You will use this command regularly 2.4.7 Recording a MATLAB session I will ask you to make records of what you have done for the purposes of assessment. The best way to do this in a MATLAB session is to type: diary filename work session diary off This will record what you have done in the file given by filename. To print this in a MATLAB session type: lpr -P7 filename This will print the file into printer 7 in the MSc room. The command tells MATLAB that you are using a UNIX command. Similarly, if you have created a figure and you want to save it type: print -dps filename.ps This will save the figure to a file called filename as a postscript file. To print this then type: lpr -P7 filename.ps 16Chapter 3 Operations on, and the analysis of, data. 3.1 Introduction Numerical methods are concerned with the manipulation of both functions and of data stored within a computer. Usually the functions are complicated and the data set is large. We need to be able to handle both efficiently. Two closely related tasks are as follows: 1. How can we approximate a function ? For example should we take point values or should we represent the function in terms of simpler functions ? 2. The extraction of information from data. To give three examples of this we might: (a) Have a series of experimental data points and we want to fit a curve through them. (b) Want to synthesise the sound of an oboe. How do you determine what notes make up this sound? (c) Have an experiment which depends on parameters a and b. Can you work out a and b from the experimental data? A closely related problem is that of data compression namely you have a complicated function or a long set of data. How can you convey the same (or at most slightly reduced set) of information using many fewer data points? This is important in computer graphics and in transmitting images over the Internet (jpeg files, for example, use data compression to transmit images). Also closely related is the question of reducing the noise level of a signal and/or removing the effects of distortion (such as blurring). MATLAB allows us to perform these operations relatively easily. Most data derived in applications has errors associated with it, and this should be considered when performing operations on it. 3.2 Curve fitting using regression and splines Suppose that we have a data set and we wish to find a curve which models this set. How can we do this? The following criteria are appropriate in finding such a curve. 1. The curve should be as “simple” as possible. Later on we may wish to perform calculations on it such as integration and differentiation 2. The curve should be simple to compute 3. It should be robust to errors in the data 4. It should “look good to the eye” 17Two methods can be used to find such a curve: (A) Interpolation. This is a good method for clean data and is used in computer graphics. (B) Regression. ...This is better for noisy data and is used to interpret experiments. 3.2.1 Interpolation Suppose that we have a underlying function u(t), the values u ,...,u of which are given exactly at 1 N the data points t ,...,t . Now suppose that we have a larger set of sample points s ,...,s with 1 N 1 M M ≫ N. The question is, knowing u at points t , how can we approximate it at the points s ? Here i i we see the effects of data compression in that we need only transmit the N values u(t ) to recover the i many more values of u(s ). i The simplest method is to approximateu(t) by a piecewise linear function, where we draw straight lines between the data points. For example if t =1,2,3,4,5,6 and u = 1,2,−1,0,−2,4 then the resulting interpolant has the following form: 4 3 2 1 0 −1 −2 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 Figure 3.1: Linear interpolant The resulting curve p(t) is called the linear interpolant. It has the following properties: 1. p(t) is continuous 2. p(t ) =u(t ), so the curve exactly fits the given data i i 3. p(t) is linear on each interval t ,t i i+1 A nice way to implement piecewise linear interpolation in MATLAB is with the command interp1, selecting the option ‘linear’. If u(t) is not very smooth then the linear interpolant may be as good a representation of the data as you could reasonably expect. However, if u(t) is a smooth function (i.e. many of its derivatives are continuous) then a better approximation of u(t) might be possible with higher order polynomial interpolants. An example is the “cubic spline”. A cubic spline p(t) interpolant to the data (t ,u(t )),(t ,u(t )),...,(t ,u(t )) is defined by the 1 1 2 2 N N following criteria: 181. p is a cubic function on each interval t ,t , i= 1,...,N−1. i i+1 ′ ′′ 2. p,p and p are continuous on t ,t . 1 N 3. p(t ) =u(t ) i.e. p interpolates u at the points t , i=1,...,N. i i i Let us see whether this prescription can define p uniquely. Sincep is cubic in each t ,t ,i=1,...,N−1, that means that altogetherp has 4(N−1) degrees i i+1 of freedom which have to be determined. ′ ′′ The condition 2 imply that the values of p,p and p have to agree from each side at the “break points” t ,i = 2,...,N−1, so this is 3(N−2) conditions. Condition 3 specifies the values of p at N i points, so this is N conditions, so altogether we have 4N−6 conditions, which is not enough. The two final conditions are what is called the “Natural” conditions at the end points: ′′ ′′ 4. p (t ) =p (t ) =0. 1 N For the above data set this looks like: 4 3 2 1 0 −1 −2 −3 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 Figure 3.2: Cubic spline Simple Example, N = 3: Then we have points t ,t ,t and on (t ,t ) 1 2 3 1 2 2 3 p(t) =a +b t+c t +d t , 1 1 1 1 with a similar representation on the interval t ,t with coefficients a ,b ,c ,d . Then a ,b ,c ,d must 2 3 2 2 2 2 i i i i satisfy the following conditions. (a) They must interpolate the data so that: 2 3 a +b t +c t +d t = u(t ) 1 1 1 1 1 1 1 1 2 3 a +b t +c t +d t = u(t ) 1 1 2 1 1 2 2 2 2 3 a +b t +c t +d t = u(t ) 2 2 2 2 2 2 2 2 2 3 a +b t +c ,t +d t = u(t ) 2 2 3 2 2 3 3 3 ′ ′′ (b) The continuity of p(t) and p requires that, 2 2 b +2c t +3d t = b +2c t +3d t 1 1 2 1 2 2 2 2 2 2 2c +6d t = 2c +6d t 1 1 2 2 2 2 This gives six equations for the eight unknowns a ,...d ,a ...d and the two further conditions are 1 1 2 2 given by the ‘natural” condition 4. 19

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.