Review for Exam 2 Ben Wang and Mark Styczynski This is a rough approximation of what we went over in the review session This is actually more detailed in portions than what we went over Also please note that this has not been proofread fully so it may have typos or other things slightly wrong with it but it s a good guide towards what you should know about Finally be familiar with what is in your book so that if there s something on the exam that you don t know well e g LU decomposition from the last exam you at least know where to look for it Chapter 4 IVPs Objective develop iterative rules for updating trajectory with the objective of getting numerical solution to equal to the integration of the exact solution Converting higher order differential equations into systems of coupled first order differential equations What is quadrature Numerical integration will involve integrating a polynomial that is why polynomial interpolation is important Polynomial interpolation Polynomial interpolation is accomplished by definining N support point which the polynomial will equal the function at We define the polynomial p x ao a1 x a2 x 2 a N x N such that p x j ao a1 x j a2 x j a N x j f x j 2 N for j 0 1 2 N You can solve this like way back in the day with a linear system But let s find a better way of doing this Lagrange interpolation For N support points Lagrange interpolation is the sum of N lagrange polynomials each of which are of order x N 1 designed to fit closely exactly at a specified support point Now that we have a sum of polynomials or a single polynomial we can integrate this numerically using trapezoidal rule Simpson s rule etc Integration Newton Cotes uniformly spaced points Different methods trapezoid rule simpson s rule b b a f f 3 f x dx 0 1 a O b a 2 with errors b 4 b a O b a 4 f x dx f f f 0 1 2 a 6 How to get more accurate Break into smaller segments before making too many more points How to integrate in two dimensions Make a rectangle containing all points and multiply the function you are integrating by an indicator function that says whether you are in the area to be integrated indicator 1 or not indicator 0 This all relates to time integrals Linear ODE systems and dynamic stability Linear system begin with a known ode problem x dot Ax You can expand the exponential solution to analyze the results Looking at a linear system which gives rise to a discussion on stability and behavior of solution Nonlinear ODE systems Same type of anlaysis now we use a Taylor expansion invoking the Jacobian Time marching ODE IVP solvers Explicit methods generates a new state by taking a time step based on the function value at the old time step Explicit Euler method Uses Taylor approximation gives first order error globally second order local but O delta t time steps so O delta t error x k 1 x k t f x k Runge Kutta methods Still explicit but uses midpoints Second order RK k t f x 1 k k 1 1 2 k t f x k 2 x k x k k O t 1 2 where the global error is delta t 2 3 Can get higher order ones RK 4th order is basis of ode45 th 4 order RK you just have to know the value of the function at the current state and a time step and you can generate the new state How does ode45 get estimate of error Use 5 function evaluations to get 5th order accurate also gets 4th order accurate compare two to see how accurate you are then know if need to make delta t smaller or bigger Global vs Local error Implicit methods update rule depends on previous values of x at time in the immediate past Use of interpolation to approximate an update Why is it difficult to use x k 1 to get your derivative Because that is nonlinear requires a difficult solution Is this more accurate than explicit in all cases No same order accuracy for explicit Euler vs implicit Euler Are these methods used Yes quite frequently Why or why not Because they are more stable to larger time steps for stiff equations they won t blow up Basic implicit Euler x k 1 x k t f x k 1 Others like Crank Nicholson x k 1 1 k k 1 k x t f x f x 2 Predictor corrector method Use explicit method to generate an initial guess Then use Newton to iteratively find real solution to implicit equation Predictor corrector method ought to converge well for Newton Yes because guess should be relatively near correct value DAE systems What are they y F y z where y are variables in ODEs z are other variables 0 G y z Mass matrix indicates where the differential parts are Is mass matrix singular If it s a DAE yes Otherwise it s just an ODE system What conditions do we need to solve this using an ODE solver DAE system to be of index one the determinant of the Jacobian of the nonlinear equalities must be nonzero So that leaves us with G G y T z 0 T y z Stability of systems steady states Take Jacobian Evaluate at steady state Find eigenvalues If real part of all is 0 stable If 0 quasi stable indifferent to perturbations in some direction If any 0 unstable Don t be confused by stability of integrators and stability of a system s steady state The integrator creates a system based on its solution method and we evaluate that system s stability Which ODE integration routines are more stable Explicit RK vs Implicit Euler Which will have less error in a non stiff system Explicit RK vs Implicit Euler Stiff not stiff systems Eigenvalues of Jacobian Definition Conceptual different time scales Condition number indication of number of steps needed to integrate properly When to use ode15s vs ode45 Condition number 1 or not When will you know things will be stiff not stiff Single ODE equation not stiff Discretized PDEs stiff What to do if not sure Try ode45 if fails use 15s Ways to speed things up in Matlab Return Jacobian of system of ODEs at the supplied point Chapter 5 Optimization Use the gradient of the cost function to find the downhill direction you may want to look in Use the Hessian of the gradient to figure out how close to that gradient direction you want to look and exactly how far you d want to go if local conditions stayed constant globally This is using essentially a Newton method in multiple dimensions to find the optimum Analogy to solving nonlinear algebraic systems Adding to the Hessian matrix H B Add to the main diagonal to make sure matrix is positive definite an application of …