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

Problem 4 Consider the system . Problem 4a Show that if the parameter is chosen sufficiently small, then this system has a unique solution within some rectangular region. Solution 4a The system of equations may be expressed in matrix notation. The Jacobian of , , is computed using partial derivatives If is sufficiently small and are restricted to a bounded region , From the mean value theorem, for , there exists such that Since is bounded in the region give sufficiently small Therefore, is a contraction and from the contraction mapping theorem there exists a unique fixed point (solution) in a rectangular region. Problem 4b Derive a fixed point iteration scheme for solving the system and show that it converges. Solution 4b Use Newton Method To solve this problem, we can use the Newton Method. In fact, we want to find the zeros of The Jacobian of , , is computed using partial derivatives Then, the Newton method for solving this linear system of equations is given by Show convergence by showing Newton hypothesis hold Jacobian of g is Lipschitz We want to show that is a Lipschitz function. In fact, and now, using that is Lipschitz, we have Jacobian of g is invertible Since is a contraction, the spectral radius of the Jacobian of is less than 1 i.e. . On the other hand, we know that the eigenvalues of are . Then, it follows that or equivalently is invertible. inverse of Jacobian of g is bounded Since exists, . Given a bounded region (bounded ), each entry of the above matrix is bounded. Therefore the norm is bounded. norm of (Jacobian of g)^-1 (x_0) * g(x_0) bounded since and is bounded. Then, using a good enough approximation , we have that the Newton's method is at least quadratically convergent, i.e, Problem 5a Outline the derivation of the Adams-Bashforth methods for the numerical solution of the initial value problem . Solution 5a We want to solve the following initial value problem: . First, we integrate this expression over , to obtain , To approximate the integral on the right hand side, we approximate its integrand using an appropriate interpolation polynomial of degree at . This idea generates the Adams-Bashforth methods. , where, denotes the approximated solution, and denotes the associated Lagrange polynomial. Problem 5b Derive the Adams-Bashforth formula Solution 5b From (a) we have where Then if we let , where h is the fixed step size we get So we have the Adams-Bashforth method as desired Problem 5c Analyze the method (1). To be specific, find the local truncation error, prove convergence and find the order of convergence. Solution 5c Find Local Truncation Error Using Taylor Expansion Note that . Also, denote the uniform step size as h. Hence, Therefore, the given equation may be written as Expand Left Hand Side Expanding about , we get Expand Right Hand side Also expanding about gives Show Convergence by Showing Stability and Consistency A method is convergent if and only if it is both stable and consistent. Stability It is easy to show that the method is zero stable as it satisfies the root condition. So stable. Consistency Truncation error is of order 2. Truncation error tends to zero as h tends to zeros. So the method is consistent. Order of Convergence Dahlquist principle: consistency + stability = convergent. Order of convergence will be 2. Problem 6 Consider the problem Problem 6a Give a variational formulation of (2), i.e. express (2) as Define the Space H, the bilinear form B and the linear functional F, and state the relation between (2) and (3). Solution 6a Multiplying (2) by a test function and using integration by parts we obtain: Thus, the weak form or variational form associated with the problem (2) reads as follows: Find such that for all where . Problem 6b Let be a mesh on with , and let . Define the finite element approximation, based on the approximation space . What can be said about the error on the Sobolev norm on ? Solution 6b Define piecewise linear basis For our basis of , we use the set of hat functions , i.e., for Define u_h Since is a basis for , and we have . Discrete Problem Now, we can write the discrete problem: Find such that for all If we consider that is a basis of and the linearity of the bilinear form and the functional , we obtain the equivalent problem: Find such that This last problem can be formulated as a matrix problem as follows: Find such that where and . Bound error In general terms, we can use Cea's Lemma to obtain In particular, we can consider as the Lagrange interpolant, which we denote by . Then, . It's easy to prove that the finite element solution is nodally exact. Then it coincides with the Lagrange interpolant, and we have the following punctual estimation: Problem 6c Derive the estimate for , the error in . Hint: Let w solve (#) : We characterize variationally as . Let to get Use formula (4) to estimate . Solution 6c Continuity of Bilinear Form Orthogonality of the Error . Bound for L2 norm of w Hence, Bound for L2 norm of w From , we have Then, Bound L2 Error Finally, from (#), we have that . Then, , or equivalently, . Problem 6d Suppose is a basis for . Show that where is the stiffness matrix. Solution 6d We know that where the substitution in the last lines come from the orthogonality of error. Now, Then, we have obtained