Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/Aug05 667

Problem 4a Given a smooth function , state the secant method for the approximate solution of nonlinear equation in Solution 4a Problem 4b State the order of convergence for this method, and explain how to derive it. Solution 4b If is bounded and is close to , then the secant method has convergence order (the Golden ratio). A partial proof of this can be found here Problem 4c Are there situations in which the order of convergence is higher? Explain your answers. Solution 4c Problem 5 Consider the initial value problem Problem 5a Write the ODE in integral form and explain how to use the trapezoidal quadrature rule to derive the trapezoidal method with uniform time step : Solution 5a Problem 5b Define the concept of absolute stability. That is, consider applying the method to the case with real . Show that the region of absolute stability contains the entire negative real axis of the complex plane. Solution 5b Letting , we have If we let , and rearrange the equation we have We require . This is true if is a negative real number. Problem 5c Suppose that where is a symmetric matrix and . Examine the properties of which guarantee that the method is absolutely stable (Hint: study the eigenvalues of ). Solution 5 We now want instead i.e. or (since is symmetric) or (since multiplying by orthogonal matrices does not affect the norm) or (by definition) If is negative definite (all its eigenvalues are negative), the above inequality holds. Problem 6 Consider the following two-point boundary value problem in Problem 6a Give a variation formulation of (1), i.e, express it it as Define the function space , the bilinear form , and the linear functional and state the relation between and . Show that the solution is unique. Solution 6a Variational Form Derive the variational form by multiplying by test function and integrating from 0 to 1. Use integration by parts and substitute initial conditions to then have: Find such that for all Relationship between (1) and (2) (2) is an equivalent formulation of (1) but it does not involve second derivatives. Existence of Unique Solution By the Lax-Milgram theorem, we have the existence of a unique solution. bilinear form continuous/bounded: bilinear form coercive: functional bounded: Problem 6b Write the finite element method with piecewise linear elements over a uniform partition with meshsize . If is the vector of nodal values of the finite element solution, find the stiffness matrix and right hand side such that . Show that is symmetric and positive definite. Show that solution is unique Solution 6b Define hat functions as basis of the discrete space. Note that and have only half the support as the other basis functions. Using this basis we have Observe that is symmetric. It is positive definite by Gergoshin's theorem. The solution is unique since is diagonally dominant. Problem 6c Consider two partitions and of , with a refinement of . Let and be the corresponding piecewise linear finite element spaces. Show that is a subspace of Solution 6c If then it is also in since is a refinement of . In other words, since is piecewise linear over each intervals, it is also piecewise linear over a refinement of its interval. Problem 6d Let and be the finite element solutions. Show the orthogonality equality. Solution 6 From orthogonality of error, we have for all Specifically, Then