John Trangenstein: Math 563 Scientific Computing II

John Trangenstein : Math 563 Scientific Computing II

Class hours: TTh 8:30-9:45 Physics 119
Scientific Computing (Local users only)

Course grade depends on weekly homework assignments
All homework must contain

a written description of the problem and numerical approach
a copy of the code
pictures or numbers for numerical results, and
a discussion of the results (e.g., describe the accuracy, convergence rate, ...)

To get online help with commands and utilities, there are 2 useful sources:

yelp. Type "yelp &". When the window comes up, click on "Manual pages" to see a list of commands ; "Applications" will contain most of the commands you need. To find a particular command, pull down on the scroll bar.
kdbg. Type "kdbg &". When the window comes up, click on "Help".

To develop a webpage, see OIT web info Syllabus:

Interpolation and Approximation
- Polynomial Interpolation
  - well-posedness 1/10
  - error estimation 1/10
  - Newton interpolation 1/15
  - Lagrange interpolation 1/15
  - Hermite interpolation 1/15
  - Runge phenomenon 1/17
  - Chebyshev interpolation 1/17
  - Bernstein polynomials 1/17
- Multidimensional Polynomial Interpolation
  - multidimensional polynomials
  - simplices
  - quadrilaterals and octahedra
  - error estimate
- Rational Polynomials
  - Pade approximation
  - continued fractions
  - interpolation and approximation
- Quadric Surfaces
- Splines
  - continuous
  - continuously differentiable
    - piecewise quadratics
    - piecewise cubics or higher
  - twice continuously differentiable
    - piecewise cubics
    - piecewise quartics
    - piecewise quintics or higher
  - error estimate
  - tension splines
  - Parametric curves
    - Hermite curves
    - Bezier curves
    - rational splines
- Least Squares Approximation
  - Norms and inner products
  - normal equations
  - orthogonal polynomials
  - trigonometric polynomials
    - orthogonality
    - theory
    - fast Fourier transform
    - real FFT
    - fast evaluation
- Wavelets
  - discrete time signals
    - example
    - signals
    - filters
    - discrete Fourier transform
    - continuous Fourier transform
    - adjoints
    - filter banks
    - orthogonal filter banks
    - maxflat orthogonal filters
    - spline filters
  - functions on a continuum
    - scaling functions
    - wavelets
    - Riesz sequences
    - orthonormal sequences
    - multiresolution analysis
    - orthogonal complements
    - wavelet construction
    - function decomposition
    - error estimates
  - multi-wavelets
Differentiation and Integration
- Numerical differentiation
  - polynomials
    - synthetic division
    - trigonometric polynomials
    - orthogonal polynomials
  - one-sided differencing
  - centered differencing
  - Richardson extrpolation
- Numerical integration
  - Monte Carlo
  - Riemann sums
  - midpoint rule
  - trapezoidal rule
  - Euler-MacLaurin formula
  - Romberg integration
  - Gaussian quadrature
  - Lobatto quadrature
  - Newton-Cotes quadrature
  - difficult integrals
  - adaptive quadrature
  - multiple dimensions
Initial value problems
- theory
- linear equations with constant coefficients
  - matrix exponentials
  - appoximate matrix exponentials
- linear multistep methods
  - consistency
  - characteristic polynomials
  - zero stability
  - absolute stability
  - Adams-Bashforth methods
  - Adams-Moulton methods
  - Nystrom methods
  - backward differentiation formulae
  - predictor-corrector methods
  - choosing step sizes
- deferred correction
  - classical deferred correction
  - spectral deferred correction
- Runge-Kutta methods
  - methods with error-estimation
  - stiffly stable methods
- extrapolation methods
- stiffness
- nonlinear stability
Boundary value problems
- existence and uniqueness
- shooting methods
- finite difference methods
- finite element methods
  - weak form
  - Galerkin methods
  - finite element method
  - essential and natural boundary conditions
  - higher-order elements
  - Sobolev spaces
  - regularity
  - error estimates
  - non self-adjoint problems
  - approximation theory

Homework:

due January 19
Problem 3, section 9.2 Kai Zhang solution Jiaqi Yan solution Luis Tobon solution Alex Pruss solution Harrison Potter solution Lin Wang solution
due January 26
Problem 1, section 9.3.5 Jiaqi Yan solution Luis Tobon solution Kai Zhang solution Zhiru Yu solution Lin Wang solution Alex Pruss solution Harrison Potter solution
due February 7
Write a program to compute the Legendre polynomials of order at most n at a given point x. Then write a program to find all of the zeros of these Legendre polynomials. Make a table of the zeros for all orders between 1 and 10. HINT: the zeros of p_k are real, between -1 and 1, and interlace the zeros of p_{k-1}: the first is between -1 and the first zero of p_{k-1}, the next is between the first 2 zeros of p_{k-1},... ane the last is between the last zero of p_{k-1} and 1. Kai Zhang solution Jiaqi Yan solution Lin Wang solution Zhiru Yu solution Luis Tobon solution Alex Pruss solution Harrison Potter solution
due February 21
Determine the scaling functions and wavelet functions for the multi-wavelet basis in the Beylkin, Coifman and Rokhlin paper; consider multi-wavelets of order less than or equal to 2. Find the coefficients in the dilation and wavelet equations for these multi-wavelets. Program the cascade and pyramid algorithms for these multi-wavelets. Given f(x) = exp(x), determine the coefficients in the expansion of f on dyadic intervals of width 2^{-7} in terms of the multi-wavelet scaling functions. Then use the pyramid and cascade algorithms to determine the expansion of f in on coarser scales. Plot the multi-wavelet approximations on all scales. Kai Zhang solution Alex Pruss solution
due March 14
Problem 3, section 10.6 Kai Zhang solution Zhiru Yu solution Lin Wang solution Alex Pruss solution Jiaqi Yan solution Luis Tobon solution
due March 28
Solve y'(t)=z(t), z'(t)=1000(1-y(t)^2)z(t)-y(t) with y(0)=2, z(0)=0 for t between 0 and 3000. This problem has internal boundary layers, and the initial condition is nearly on the limit cycle, which has a perior of about 1615.5. Use EPSODE to solve this problem, and examine how the numerical solution depends on the choice of error tolerance. You can find some discussion of this problem in Shampine, "Evaluation of a Test Set for Stiff ODE Solvers", ACM Transactions on Mathematica Software v. 7 #4 (1981) pp 409-420. Kai Zhang solution Zhiru Yu solution Alex Pruss solution Lin Wang solution Jiaqi Yan solution
due April 18
Consider the two-point boundary value problem -u'' = pi^2 cos(pi x) for x in (0,1), with u(0) = 1 and u(1)=-1.
- Find the analytical solution of this problem.
- Program the finite element method for this problem, using continuous piecewise linear elements.
- Plot the log of the error in the solution at the mesh points versus the log of the number of basis functions, for 2^n elements with n between 1 and 10. What is the slope of this curve (ie, the order of convergence)?
- Plot the log of the error in the derivative of the solution at the midpoints of the mesh intervals versus the log of the number of basis functions, for 2^n elements with n between 1 and 10. What is the slope of this curve?
- Suppose that we change the right-hand boundary condition to u'(1) = 0. Modify the finite element method to handle this boundary condition. What is the order of convergence of u(1) and u'(1) for this finite element approximation? Kai Zhang solution Luis Tobon solution

Return to: John A. Trangenstein *