INF5620: Numeriske metoder for partielle differensiallikninger, V06

Forelesere: Hans Petter Langtangen (hpl@ifi.uio.no) og Xing Cai (xingca@ifi.uio.no)

Messages

Undervisning

Annen info

Talks for the INF5620 exam on June 8, 2006:

Note that talk no. 3 has been simplified (but there is no disadvantage in presenting a Taylor-Galerkin approach).

  1. Instability of spatial discretizations.
    Our model problem reads -v*p'(x)=k*p''(x) with and p(0)=A, p(1)=B, where v and k are positive constants and A and B are given numbers. First show how this problem can be scaled. Set up a "standard" finite difference and finite element method for this problem and sketch how the solution typically looks like. Find an exact solution of the discrete equations and use this solution to explain the numerical difficulties. Then present some stabilizing techniques (motivate each technique). Analyze also the stabilized methods. Set up a 3D extension of the model problem and explain briefly how the stabilizing techniques generalize to 3D.

  2. Classical iterations and multigrid.
    Now we look at the frequently arising Poisson equation on a rectangular 2D domain, discretized by finite differences over a uniform grid. Set up Jacobi's method for solving the linear systems in this problem (choose a notation for this algorithm that suits the problem). Explain extensions to the Gauss-Seidel, SOR, and SSOR methods. How can we analyze how fast these methods converge? Demonstrate the analysis for a 1D version of our model problem. Use the analysis to motivate for the multigrid method and explain the basic steps in the multigrid algorithm.
    Suppose there is a contest with two disciplines: one where the aim is to make the computationally fastest method for solving the linear system ("highest computational efficiency"), and one where the aim is to program a working solution method as fast as possible ("highest human efficiency"). What type of numerical algorithms would you choose to have the best starting point for winning both disciplines?

  3. The preconditioned Conjugate Gradient family of methods.
    We address the 2D nonlinear convection-diffusion equation du/dt + v*du/dy = div(k(u)*grad(u)) + f(x,y,t) solved by a finite element method in space, a Crank-Nicolson method in time, and successive substitution approach where u from the previous time level is used in the k(u) term.
    Explain why we need to solve a single linear system at each time level. Sketch the sparsity structure of this linear system in two cases: (i) a rectangular domain with a structured mesh where the nodes are numbered row by row in the mesh, and (ii) a geometrically complicated domain divided into triangles by some preprocessor software. How does the type of finite elements used in the mesh influence the sparsity structure (you may limit the discussion to case (i))?
    Derive the algorithms based on Galerkin and Least-Squares solution of the linear system arising from the discretization. How do these algorithms simplify if v=0?
    Explain what preconditioning is and give an overview of the preconditioning methods you are aware of. Show how one of the derived algorithms is modified by preconditioning.

  4. A nonlinear heat equation in 1D.
    We consider the equation q(u)*du/dt = div(k(u)*grad(u)) + f(u) in the domain (0,a) in 1D with the boundary conditions u(0)=A and -k(u(a))*u'(a)=B and initial condition u(x,0)=0. Show in detail how we can apply the finite element method to solve the problem. Use a Backward Euler difference in time and the Newton-Raphson method to solve the nonlinear algebraic equations. Show in detail how you calculate the Jacobian on the element level and how this matrix is assembled in the global system. Exemplify calculation of all integrals by using the group finite element method and nodal-point integration. Comment on how this discretization relates to a standard finite difference discretization in space.
    Suppose your implementation of the methods does not work properly so you decide to simplify the problem for debugging. Let q, k, and f be constants, work with three grid points in total, and set up the global linear system in the Newton-Raphson method for the first time step in this particular case. Explain why the Newton-Raphson iteration now should converge in just one iteration.

  5. A wave equation in 1D.
    A 1D wave equation is given as u_tt = u_xx on (0,1) with boundary conditions u(a,t)=u(b,t)=0 and initial conditions u_t(x,0)=f(x), u(x,0)=0. Mention some physical applications that lead to this type of wave equation (possibly with other initial and boundary conditions). Set up a complete algorithm for a finite difference solution of this problem. Explain briefly how the discretization changes if we use linear finite elements in space instead of standard finite differences. Find exact solutions of the finite difference scheme, and use these solutions to analyze accuracy and stability. Quote the similar results for a finite element-based spatial discretization and explain how the inferior finite element approach can be improved. Set up a test case that produces significant non-physical noise in the solution and explain (from the previous analysis) why this noise arises.

  6. Shallow water equations in 2D/1D.
    Set up the system of three partial differential equations for shallow water waves in 2D. Introduce a grid staggered in space and time, and show how the equations can be discretized. Set up the total algorithm for solving a problem in a rectangular "ocean area". Take zero normal velocity as boundary condition. Reduce the equations to 1D. Show that the scheme in 1D is equivalent to solving a standard second-order linear wave equation by a standard finite difference method. Use this result to analyze the staggered scheme with respect to accuracy and stability (in the 1D case).