MATH661 Homework 10 - Multiple operators

MATH661 Homework 10 - Multiple operators

This homework is a reading assignment meant as final examination preparation. The particular topic is numerical solution of ordinary differential equations, but the presentation is also a synthesis of the ideas encountered in the course. The scheduled course grade points are automatically awarded, but several suggestions are given for independent work that can be submitted for extra course credit up to the date prior to the final examination.

1Problem and algorithm statement

The problem considered here is finding approximations of $y \in 𝒴$ , $y : ℝ \to ℝ$ a real-valued function with $p$ continuous derivatives specified by an equality between the action of two operators

ℒ y = ℱ y,

with $ℒ$ linear and $ℱ$ nonlinear. The particular choice of operators $ℒ = d / d t$ and $ℱ = f$ corresponds to the ordinary differential equation

y^{'} = f (t, y),

but the ideas underlying the approach are generic, applicable to other operator choices.

The function $y : ℝ \to ℝ$ is approximated by a sample $𝒟 = {(t_{i}, y_{i}), i = 0, \dots, N}$ , with $y_{i} ≅ y (t_{i})$ , $t_{i} = i h$ . Consider an approximation of $ℒ = d / d t$ by linear combination of the sample values

{(ℒ y)}_{i} ≅ \frac{1}{h} \sum_{k = 0}^{s} a_{k} y_{i + k} .

(1)

Also introduce an approximation of $ℱ y$ by linear combination of $f_{i} = f (t, y_{i}) ≅ f (t, y (t_{i}))$

{(ℱ y)}_{i} ≅ \sum_{k = 0}^{s} b_{k} f_{i + k} .

(2)

Overall, the above approximations lead to the algorithm

\frac{1}{h} \sum_{k = 0}^{s} a_{k} y_{i + k} = \sum_{k = 0}^{s} b_{k} f_{i + k} .

(3)

2Consistency

A first question that arises is whether the operator approximations converge. These are discrete approximations based upon sampling $y (t)$ at $t_{i} = i h$ . The function $y$ would be recovered in the limit $h \to 0$ , leading to the definition of consistency by

{lim}_{h \to 0} {(ℒ y)}_{i} = y^{'} (t_{i}), {lim}_{h \to 0} (ℱ y) = f (t_{i}, y (t_{i})),

stating that the exact operators are obtained.

Exercise 1. Carry out Taylor series expansion of the operator approximation (1) applied to the exact function $y (t)$ to determine consistency conditions for coefficients $a_{k} .$

Solution. Applied to the exact function, the operator approximation gives

y^{'} (t_{i}) ≅ {(ℒ y (t))}_{i} = \frac{1}{h} \sum_{k = 0}^{s} a_{k} y (t_{i + k}) .

Taylor series expansion around $t_{i}$ gives

y (t_{i + k}) = y (t_{i}) + k h y^{'} (t_{i}) + \frac{{(k h)}^{2}}{2!} y^{''} (t_{i}) + \dots .

Gathering terms,

{(ℒ y (t))}_{i} = \frac{1}{h} [(\sum_{k = 0}^{s} a_{k}) y (t_{i}) + h (\sum_{k = 0}^{s} k a_{k}) y^{'} (t_{i}) + h^{2} (\sum_{k = 0}^{s} k^{2} a_{k}) y^{''} (t_{i}) + \dots +] .

In order for ${lim}_{h \to 0} {(ℒ y (t))}_{i} = y^{'} (t_{i})$ the conditions

(\sum_{k = 0}^{s} a_{k}) = 0, (\sum_{k = 0}^{s} k a_{k}) = 1,

must be met.

Exercise 2. Define a polynomial $ρ (r) =$ $(\sum_{k = 0}^{s} a_{k} r^{k})$ . State the consistency conditions for $ℒ$ as imposed values for $ρ, ρ^{'}$ .

Solution. The above consistency conditions correspond to

ρ (1) = 0, ρ^{'} (1) = 1 .

Exercise 3. Verify that the forward Euler, backward Euler, leapfrog schemes are consistent for $f = 0$

Solution. The above schemes use operator series truncations

\frac{d}{d t} ≅ \frac{1}{h} Δ, \frac{d}{d t} ≅ \frac{1}{h} \nabla, \frac{d}{d t} ≅ \frac{1}{h} δ,

respectively. These all correspond to the same polynomial

ρ (r) = r - 1,

after shifting indices. For example, in the leapfrog scheme

\frac{1}{h} (y_{i + 1 / 2} - y_{i - 1 / 2}) = f (t_{i}, y_{i})

shifting by 1.2 gives

\frac{1}{h} (y_{i + 1} - y_{i}) = f (t_{i + 1 / 2}, y_{i + 1 / 2}) .

Since $ρ (1) = 0, ρ^{'} (1) = 1$ , the scheme is consistent.

Exercise 4. (1 Extra Credit point). Verify that the $ℒ$ approximation in the first four Adams-Bashforth schemes are consistent.

Exercise 5. (1 Extra Credit point). Verify that the $ℒ$ approximation in the first four Adams-Moulton schemes are consistent.

Exercise 6. Carry out Taylor series expansion of the operator approximation (2) applied to the exact function $f (t, y (t))$ to determine consistency conditions for coefficients $b_{k} .$

Solution. Applied to the exact function, the operator approximation gives

f (t_{i}, y (t_{i})) ≅ {(ℱ y (t))}_{i} = \sum_{k = 0}^{s} b_{k} f (t_{i + k}, y (t_{i + k})) .

Taylor series expansion around $t_{i}$ gives

f (t_{i + k}, y (t_{i + k})) = f (t_{i}, y (t_{i})) + k h \frac{\partial f}{\partial t} (t_{i}, y (t_{i})) + \frac{\partial f}{\partial y} (t_{i}, y (t_{i})) (y (t_{i + k}) - y (t_{i})) + \dots =

f (t_{i}, y (t_{i})) + k h \frac{\partial f}{\partial t} (t_{i}, y (t_{i})) + \frac{\partial f}{\partial y} (t_{i}, y (t_{i})) (y (t_{i}) + k h y^{'} (t_{i}) + \dots - y (t_{i})) + \dots =

f (t_{i}, y (t_{i})) + k h [\frac{\partial f}{\partial t} (t_{i}, y (t_{i})) + y^{'} (t_{i}) \frac{\partial f}{\partial y} (t_{i}, y (t_{i}))] + 𝒪 (h^{2})

Gathering terms,

{(ℱ y (t))}_{i} = [(\sum_{k = 0}^{s} b_{k}) f (t_{i}, y (t_{i})) + 𝒪 (h)] .

In order for ${lim}_{h \to 0} {(ℱ y (t))}_{i} = f (t_{i}, y (t_{i}))$ the condition

(\sum_{k = 0}^{s} b_{k}) = 1,

must be met.

Exercise 7. Define a polynomial $σ (r) =$ $(\sum_{k = 0}^{s} b_{k} r^{k})$ . State the consistency conditions for $ℱ$ as imposed values for $ρ, ρ^{'}$ .

Solution. The above consistency condition corresponds to

σ (1) = 1 .

Exercise 8. State the consistency condition for (3) in terms of the $ρ, σ$ polynomials

Solution. Gathering the above,

ρ (1) = 0, ρ^{'} (1) = 1, σ (1) = 1 .

This can be slightly generalized to

ρ (1) = 0, ρ^{'} (1) = σ (1),

allowing a multiplicative factor in the evaluation of the derivative $y^{'}$ .

Exercise 9. Determine the consistency of the $ℱ$ approximation for the forward, Euler, backward Euler, and leap frog schemes.

Solution. The $σ$ polynomial for forward Euler is $σ (r) = 1$ , that for backward Euler is $σ (r) = r$ . For leapfrog, rescale $h \to 2 h$ , and obtain again $σ (r) = r$ . All satisfy $σ (1) = 1$ .

Exercise 10. (1 Extra Credit point). Verify that the $ℱ$ approximation in the first four Adams-Bashforth schemes are consistent.

Exercise 11. (1 Extra Credit point). Verify that the the $ℱ$ approximation in the first four Adams-Moulton schemes are consistent.

Exercise 12. Apply the boundary locus method to determine the domain of linear stability for the forward, Euler, backward Euler, and leap frog schemes when $f (t, y) = λ y$

Solution. The characteristic polynomial of the overall scheme is $π (r, z) = ρ (r) - z σ (r)$ , and the boundary locus method seeks roots of unit absolute value, $r = e^{i θ}$ .

Forward Euler

$ρ (r) = r - 1$ , $σ (r) = 1$ , $π (r, z) = r - 1 - z = 0 \Rightarrow$ $z (θ) = e^{i θ} - 1$ , a circle centered at (-1,0)

∴	n=90; h=2π/n; θ=(0:n)h; zFE=exp.(θ*im) .- 1;

∴

Backward Euler

$ρ (r) = r - 1$ , $σ (r) = r$ , $π (r, z) = r - 1 - z r = 0 \Rightarrow$ $z (θ) = 1 - e^{- i θ}$ , a circle centered at (1,0)

∴	n=90; h=2π/n; θ=(0:n)h; zBE=1 .- exp.(θ*im);

∴

Leapfrog

$ρ (r) = r^{2} - 1$ , $σ (r) = 2 r$ , $π (r, z) = r^{2} - 1 - z r = 0 \Rightarrow$ $z (θ) = e^{i θ} - e^{- i θ} = i \sin θ$ , a line segment on the imaginary axis

∴	n=90; h=2π/n; θ=(0:n)h; zLF=im.*sin.(θ);

∴	plot(real(zFE),imag(zFE),real(zBE),imag(zBE),real(zLF),imag(zLF));

∴	axis("equal"); grid("on"); xlabel("Re(z)"); ylabel("Im(z)");

∴	title("Boundary locii for forward Euler, backward Euler, leapfrog");

∴	savefig("/home/student/courses/MATH661/images/H10Fig01.png");

∴

Figure 1. Stability region for forward Euler is inside the circle, for backward Euler outside the circle, and for leapfrog within the slit on the imaginary axis.

Exercise 13. (2 Extra Credit points). Use the boundary locus method to find the linear stability region for the first four Adams-Bashforth schemes.

Exercise 14. (2 Extra Credit points). Use the boundary locus method to find the linear stability region for the first four Adams-Moulton schemes.