Numerical Quadrature

(20 pts) Consider the ODE, \[ u'(t) = Au + N(t,u), \]

where \(A\) is a fixed matrix and \(N\) is an arbitrary, e.g., nonlinear, function.

1. (6 pts) With initial data \(u(0) = u_0\), show that the solution to this IVP at time \(t > 0\) is given by, \[ u(t) = e^{tA}u_0 + \int _0^t e^{(t-s)A}N(s,u(s))\,ds, \] where \(e^{tA}\) is the matrix exponential of \(tA\).
2. (14 pts) Exponential integrators form a scheme to compute \(u_{n+1}\) in terms of \(u_n\) by integrating the above expression over the interval \([t_n,t_{n+1}]\) (instead of \([0,t]\)), by approximating \(N(u(s))\) with a quadrature rule/polynomial approximation, and by exactly integrating the matrix exponential term. A Forward Euler exponential integrator makes the approximation \(N(u(s)) \approx N(u_n)\). Write out the Forward Euler exponential integrator scheme explicitly (i.e., by eliminating integrals).

(20 pts)

1. (10 pts) Compute coefficients \(A\), \(B\), \(C\) in the 3-point one-sided approximation \[ u''(x) \approx Au(x) + Bu(x+h) + Cu(x+2h) \]

   that has optimal \(h\)-order of accuracy. What is this order of accuracy?

2. (10 pts) Compute weights for the following quadrature rule that makes it exact for all polynomials of degree 2. \[ \int _{-1}^1 f(x)\,dx = w_0 f(0) + w_1 f'(0) + w_2 f''(0), \]

(20 pts)

1. (10 pts) Compute the stability/amplification factor for forward Euler to solve \(u' = f(t,u)\), and plot the region of the stability.
2. (10 pts) Compute the stability/amplification factor for the trapezoidal rule/Crank- Nicolson scheme and use this to show that the scheme is A-stable.

(Numerical Integration). Determine the coefficients \(A_0\), \(A_1\), and \(A_2\) that make the formula \[ \int _0^2 f(x)\,dx \approx A_0 f(0) + A_1 f(1) + A_2 f(2) \] exact for all polynomials of degree 3.

(Unstable Multistep Method). Consider the numerical method \[ y_{k+1} = 3y_k - 2y_{k-1} + \frac {h}{2}\left (f(x_k,y_k)-3f(x_{k-1},y_{k-1})\right ), \qquad k \ge 1. \] Illustrate with an example of a simple initial value problem that the above scheme is unstable.

(Linear Multistep Methods).

1. Define linear multistep method (give formula). Give definition of the region of absolute stability.
2. Show that the region of absolute stability for the trapezoidal method is the set of all complex \(h\lambda \) with \(\operatorname {Real}(\lambda ) < 0\).

Numerical Integration

Determine a formula \[ \int _{-\pi }^{\pi } f(x)\cos (x)\,dx \approx A_0 f\left (-\frac {3}{4}\pi \right ) +A_1 f\left (-\frac {1}{4}\pi \right ) +A_2 f\left (\frac {1}{4}\pi \right ) +A_3 f\left (\frac {3}{4}\pi \right ) \] that is exact when \(f\) is a polynomial of degree 3.

Unstable Multistep Method

Consider the numerical method \[ y_{k+1}=3y_k-2y_{k-1} +\frac {h}{2}\left (f(x_k,y_k)-3f(x_{k-1},y_{k-1})\right ), \qquad k\ge 1 \] Illustrate with an example of a simple initial value problem that the above scheme is unstable.

Quadrature

Consider the quadrature rule \[ \int _{-1}^{1} f(x)\,dx \approx w_{-1}f(-1)+w_0f(0)+w_1f(1)+w_0'f'(0). \] Compute weights \(w_{-1}\), \(w_0\), \(w_1\), and \(w_0'\) such that this quadrature rule is exact for polynomials up to degree 3.

Unstable Multistep Method

Consider the numerical method \[ y_{p+1}=3y_p-2y_{p-1} +\frac {h}{2}\left (f(x_p,y_p)-3f(x_{p-1},y_{p-1})\right ), \qquad p\ge 1, \]

for the solution of the initial value problem \[ y'=f(x,y),\qquad y(x_0)=y_0. \] Illustrate with an example of a simple initial value problem that the above numerical scheme is unstable.

Numerical Integration

Find a formula of the form \[ \int _0^{2\pi } f(x)\,dx = A_1 f(0)+A_2 f(\pi ) \] that is exact for any function having the form \[ f(x)=c+d\cos (x). \]

Consider the quadrature rule \[ \int _a^b w(x)f(x)dx = \sum _{j=1}^n w_jf(x_j)+E_n. \] Assume that \(w\) is a positive weight function. Discuss how to pick the knots \(x_1,\ldots ,x_n\) and weights \(w_1,\ldots ,w_n\) to make the error \(E_n\) zero for all polynomials \(f\) up to a degree as high as possible.

Midpoint Rule

Derive error estimate for the midpoint rule in the form: \[ |E_n^M|\leq \frac {h^2(b-a)}{24} \max _{a\leq x\leq b}|f''(x)| \] Midpoint rule: \[ M_n(f)=h(f(x_1)+f(x_2)+\cdots +f(x_n)) \] where \(h=(b-a)/n\) and \[ x_j=a+\left (j-\frac {1}{2}\right )h,\qquad j=1,\ldots ,n \]

Numerical Quadrature

Show that there is no set of nodes \(x_1,x_2,\ldots ,x_n\) and coefficients \(\alpha _1,\alpha _2,\ldots ,\alpha _n\) such that the quadrature rule \[ \sum _{j=1}^n \alpha _j f(x_j) \] exactly equals to the integral \(\int _a^b f(x)w(x)dx\) for all polynomials \(f(x)\) of degree less than or equal to \(2n\). \(w(x)\) is the weight function.

Local Truncation Error What is the local truncation error of a numerical scheme? What does consistency mean? Give a specific and precise example.

Adaptive Quadrature Describe the basic idea of adaptive quadrature, and give a simple example, including formulas.

Numerical PDEs Consider the one-dimensional heat equation: Find \(u(x,t)\) such that \[ u_t=u_{xx},\qquad t\geq 0,\qquad x\in [0,1],\qquad u(x,0)=f(x),\qquad u(0,t)=u(1,t)=0. \] Describe how this problem might be solved by applying the Method of Lines and Euler’s Method. Give formulas that could be used to write a suitable computer code.

Gaussian Quadrature Let \(w\) be a positive weight function. Explain how to pick the knots \(x_i\) and the weights \(w_i\), \(i=1,\ldots ,n\) such that the integration formula \[ \int _a^b w(x)f(x)\,dx=\sum _{i=1}^n w_i f(x_i) \tag {2} \] is exact for polynomials \(f\) of degree as high as possible, and show why this works. How high a polynomial degree is possible?

Numerical Quadrature Consider the quadrature formula \[ \int _a^b w(x)f(x)\,dx=\sum _{i=1}^n \alpha _i f(\xi _i)+E, \] for the integral of \(f\) with a given positive weight function \(w(x)>0\). We would like to use \(n\) knot values \((f(\xi _i), i=1,\ldots ,n)\) to achieve the exact integral if \(f\) is a polynomial of degree up to \(2n-1\).

(a) Start from the special case \(a=-1\), \(b=1\) and \(w(x)=1\), define the orthogonal polynomials over \([-1,1]\).

(b) Use those orthogonal polynomials and polynomial division to simplify the integral. How would you pick the knots \(\xi _i\) and the weights \(\alpha _i\) such that the formula is exact (i.e., \(E=0\)) for all polynomials of degree up to \(2n-1\)? Verify that your choice works.

(c) Show that you can extend the approach to more general integrals, with arbitrary \(a<b\) and positive weight function \(w\).

Interpolation and Integration

a) Consider equally spaced points \(x_j=a+jh\), \(j=0,\ldots ,J+1\) on the interval \([a,b]\), where \((J+1)h=b-a\). Let \(f(x)\) be a function defined on \([a,b]\). Consider the problem of finding a cubic spline approximation \(s(x)\) to \(f(x)\) that interpolates \(f\) at the points \(x_j\), is twice continuously differentiable, and satisfies \(s''(a)=s''(b)=0\). Does this problem always have a solution? If your answer is yes, derive formulas by which to determine the spline. If your answer is no, explain your reasoning.

b) Let \(I_n(f)\) denote the result of using the composite Trapezoidal rule to approximate \[ I(f)=\int _a^b f(x)\,dx \] using \(n\) equally sized subintervals of length \(h=(b-a)/n\). It can be shown that the integration error \(E_n(f)=I(f)-I_n(f)\) satisfies \[ E_n(f)=d_2h^2+d_4h^4+d_6h^6+\cdots \] where \(d_2,d_4,d_6,\ldots \) are numbers that depend only on the values of \(f\) and its derivatives at \(a\) and \(b\). Suppose you have a black-box program that, given \(f\), \(a\), \(b\), and \(n\) calculates \(I_n(f)\). Show how to use this program to obtain an \(O(h^4)\) approximation and an \(O(h^6)\) approximation to \(I(f)\).

Gaussian Quadrature Consider the quadrature formula \[ \int _a^b w(x)f(x)\,dx=\sum _{i=1}^n \alpha _i f(\xi _i)+E. \tag {5} \] \(w\) is a given positive weight function. How do you pick the knots \(\xi _i\) and the weights \(\alpha _i\) such that the formula is exact (i.e., \(E=0\)) for all polynomials of degree up to \(2n-1\)? Show that your choice works and that you can find suitable weights and knots for all intervals \([a,b]\) and positive weight functions \(w\).

Quadrature Consider the quadrature formula \[ \int _a^b w(x)f(x)\,dx=\sum _{i=0}^n \alpha _i f(\xi _i)+E. \tag {1} \] \(w\) is a given positive weight function. The knots \(\xi _i\) and the weights \(\alpha _i\) are at your disposal. How do you choose them so that the error \(E\) is 0 for all polynomials \(f\) of degree as high as possible? How high is possible? Give reasons for your answers.

Gaussian Quadrature. What is Gaussian quadrature? How do you pick the weights and knots? Why?

a) What set of four nonlinear equations are satisfied by the nodes and weights for Gaussian quadrature with degree of precision 3, on the interval \([0,1]\).

b) Describe Newton’s method as applied to solving this system of equations.

c) Show how and why the weights and nodes for Gaussian quadrature may be modified from the standard interval to an arbitrary interval.

Find the Green’s function for the Poisson equation \(\Delta u=f\) in the infinite strip \(0\le y\le 1\), \(-\infty <x<\infty \) with boundary data \(u(x,0)=0\) and \(u(x,1)=1\). Then solve the problem (in quadrature) if \(f(x,y)=y(1-y)e^{-x^2}\).