Home MATH 317 HTSEFP

HTSEFP CC-BY-NC

Maintainer: admin

How to solve every problem.

Examples are listed at the end of each section. If one list item has multiple examples, it means the questions are identical.

Under construction

1Newton's method

1.1Using Taylor expansions

Use a Taylor expansion to derive Newton's method.

The Taylor expansion should be given. Let $x = x_n$ and $x^* = x_{n+1}$, substitute those into the Taylor expansion (ignoring the error term) and solve for $x_{n+1}$.

1.2As a fixed-point iteration

Write Newton's method as a fixed point iteration.

Just let $g$ be the expression for $x_{n+1}$

1.3Derivative of the iteration function

Show that $g'(x^*) = 0$ when $f'(x^*) \neq 0$, and find the limit when $f'(x^*) = 0$ but $f''(x^*) \neq 0$.

Take the deriv of $g$, show that the numerator is 0 so it's 0 when the denom is not zero.

Finding the limit is a bit weird. Given the values for the first and second derivs, figure out the general form of $f$ (with some unknown function), and calculate $f'$ and $f''$ based on that. Then take the limit.

1.4Computing $x_n$

Use Newton's method to compute $x_n$ for some $n$.

Just follow the iterations, starting with the given $x_0$. Not hard.

1.5Finding the rate of convergence

What's the apparent rate of convergence?

Order of convergence is quadratic if the root is simple (i.e., multiplicity of 1), linear otherwise (since then the error would be decreased by a constant factor for each step). Take the first and second derivs - if the first deriv is zero and the second deriv exists, then it's linear. If the first deriv is non-zero and the second deriv is non-zero, it's quadratic. If the first deriv is non-zero and the second deriv is zero, it's faster than quadratic (cubic? quartic? depends).

2Fixed-point theorem

2.1Proving a variation of it

Prove a variant of the fixed point theorem, from first principles. Given a continuous function $g(x)$ such that $\forall x \in [a, b]$, $g(x) \in [a, b]$, prove that there exists a $x^* \in [a, b]$ such that $g(x^*) = x^*$.

I thought this was impossible but it actually isn't that hard once you know what tools to use. First, note that if $g(a) = a$ or $g(b) = b$, then we are done - $x^*$ is either $a$ or $b$, respectively. So we assume that $g(a) \neq a$ and $g(b) \neq b$. In fact, it must be that $g(a) > a$ and $g(b) < b$ (due to the $\forall x \in [a, b]$, $g(x) \in [a, b]$ thing).

Now we create a new function $f(x) = g(x) - x$, which is clearly continuous. Consider $f(a)$ and $f(b)$. Well, $f(a) = g(a) - a > 0$ since $g(a) > 0$. Similarly, $f(b) = g(b) - b < 0$ since $g(b) < b$. By the intermediate value theorem, there must be at one point in the interval $[a, b]$, which we'll call $x^*$, such that $f(x^*) = 0$. But if $f(x^*) = 0$, then $f(x^*) = g(x^*) - x^* = 0$ which means that $g(x^*) = x^*$. So this $x^*$ is what we're looking for.

Show that this $x^*$ is unique.

To show that this $x^*$ is unique, we use a proof by contradiction. Suppose that $x_0$ and $x_1$ are both fixed points of $g(x)$ such that $x_0 \neq x_1$. Then $|g(x_0) - g(x_1)| \leq \gamma|x_0 - x_1|$ . But $g(x_0) = x_0$ and $g(x_1) = x_1$. So this statement says that $|x_0 - x_1| \leq \gamma |x_0 - x_1|$, which is not possible if $\gamma < 1$. Contradiction. Thus there is only one fixed point, $x^*$.

Consider the sequence generated iteratively via $x_{n+1} = g(x_n)$. Show that $|x_{j+1} - x^*| \leq \gamma|x_j-x^*|$, and deduce that $\displaystyle x^* = \lim_{n\to \infty}x_n$.

$x_{j+1} = g(x_j)$ by definition. So $|x_{j+1} - x^*| = |g(x_j) - x^*| = |g(x_j) - g(x^*)| \leq \gamma |x_j-x^*|$.

This tells us that the difference between a term in the sequence and the root gets smaller for each subsequent term. I don't know if this is really what we should be doing, since this method is really just analysis 1 stuff, but:

$$|x_{j+1} - x^*| \leq \gamma |x_j-x^*| \leq \gamma^2|x_{j-1} - x^*| \leq \gamma^3|x_{j-2} - x^*| \leq \cdots \gamma^{j+1} |x_0 - x^*|$$

Thus $\displaystyle \lim_{n \to \infty} |x_{n}- x^*| \leq \gamma^{n} |x_0 - x^*|$ and since $0 \leq \gamma < 1$ (it's $\geq 0$ because of the absolute-value-having condition involving it), the RHS goes to 0 and so $\lim_{n \to \infty} |x_n - x^*| = 0$ and thus $\lim_{n\to \infty} x_n = x^*$.

What additional assumption does the usual fixed-point theorem make that this does not? Given an example of a function that we can't use the standard FPT for but that we can use this for.

The standard FPT assumes differentiability of $g$. Example: $f(x) = |x/2|$. This is not differentiable at $x = 0$ but it satisfies all the other conditions of the theorem.

2.2Stating it

State it

Let $g$ be a continuous, differentiable function over the interval $[a, b]$ such that $g(x) \in [a, b]$ for all $x \in [a, b]$. Also suppose that there is a constant $k$, $0 < k < 1$, such that $|g'(x)| \leq k < 1$ for all $x \in (a, b)$. Then, for any $x_0 \in [a, b]$, the sequence defined by $x_{n+1} = g(x_n)$ converges to a unique fixed point in $[a, b]$.

2.3Proving a specific fixed point

Show that there is a specific fixed point at $x = \alpha$.

Plug in $\alpha$ for $x$ in $g$. Not hard.

2.4Satisfying conditions

Show that $g(x) \in [a, b]$ $\forall x \in [a, b]$ and that there is a constant $k$ between 0 and 1 that is the upper bound for the magnitude of the derivative. Pretty straightforward.

2.5Order of convergence

Look at the first and second derivs. If the first is 0, it's linear. If the first isn't 0 and the second isn't either, it's quadratic. If the second is 0, it's faster than quadratic.

2.6Computing $x_n$

Compute $x_n$

Do the iterations, etc

2.7Relative error

Find the relative error

Find the absolute error, divide by the true value.

2.8Finding an interval and starting point

Find an interval and starting point on which some iterative scheme for finding something satisfies the conditions of the theorem, and find the rate of convergence.

To find the interval: guess and check? Remember the conditions of the theorem. If it's an appropriate interval, any starting point in the interval should work.

For the rate of convergence, see the order of convergence section above.

3Divided differences

3.1Zeroth divided differences

Define $f[x_j]$.

$f[x_j] = f(x_j)$ lol

3.2Interpolating polynomial (Newton form)

Define $w_j$ and $c_j$ in the interpolating polynomial (in Newton form).

$w_0 = 1$; $\displaystyle w_j = \prod_{i=0}^{j-1} (x-x_i)$ for $j = 1, \ldots, n$; $c_j = f[x_0, \ldots, x_j]$ for $j=0, \ldots, n$

3.3Existence of $\xi$

Prove that there is some $\xi$ such that $f[x_0, \ldots, x_n]$ satisfies some formula involving $\xi$.

Define a new function $g(x) = f(x) - p_n(x)$. Since $f(x) = p_n(x)$ for $x= x_0, \ldots, x_n$, we know that $g$ has $n+1$ zeroes (at least). By the generalised version of Rolle's theorem, then, $g^{(n)}$ has at least one zero, which we'll call $\xi$. So there is a $\xi \in [x_0, x_n]$ such that $g^{(n)} = f^{(n)}(\xi) - p^{(n)}(\xi) = 0$.

Now, $p^{(n)}(x)$ looks like $n!f[x_0, \ldots, x_n]$ since the highest-order term has a coeff of $f[x_0, \ldots, x_n]$ and all the lower-order terms vanish once we take the $n$th deriv. Substitute this into the formula and we get

$$g^{(n)} = f^{(n)}(\xi) - n!f[x_0, \ldots, x_n] = 0$$

And if you rearrange this, the formula we want pops right out.

3.4Table of divided differences

Given some values, construct the table of divided diffs and state some polynomials of some degree which interpolate at some points.

The rows are $x_i$'s, starting from $x_0$. The columns are $f[x_i]$, $f[x_{i-1}, x_i]$, etc (so the first entry goes down). Filling in the table is pretty straightforward - you only need to fill in everything on and under the diagonal.

To find the polynomial of degree $k$ which interpolates at $x_i, x_{i+1}, \ldots, x_{i+j}$, take the coefficients from the diagonal (if $k = n$ where $x_n$ is the last point) or $n-k$ levels below the diagonal. Each coefficient gets a term $(x-x_i)(x-x_{i-1})\cdots$ where $i$ depends on the row the coefficient is in. To confirm that your answer is right, evaluate the polynomial at the interpolating points and make sure it matches the $f$-values given.

4Forward differences

4.1Approximating the derivative

Use the forward difference formula with given values of $h$ to obtain approximations for $f'(x_0)$ at some point $x_0$.

free points

4.2Finding the error term

Use Taylor series to find the error term.

Write out Taylor expansion, rearrange to solve for $f'(x_0)$

4.3Richardson extrapolation

Use Richardson extrapolation to get a better approximation.

Given some formula for $f'(x_0)$ that uses $h$, replace all the $h$'s by $h/2$, and do some algebra with the two equations for $f'(x_0)$ (one with $h$, one with $h/2$) to get another formula for $f'(x_0)$. Then apply this new formula to obtain a better approximation.

4.4Approximating the second derivative

State a formula for approximating the second derivative and use it.

Here's the centered diff formula

$$f''(x) \approx \frac{f(x+h) -2f(x)+f(x-h)}{h^2}$$

To derive this, find the Taylor expansions for $f(x + h)$ and $f(x-h)$, add them together, and rearrange to solve for $f''(x)$.

Not sure how to derive the forward and backward diff formulas for the second derivative but I'm sure it's possible.

5Quadrature

5.1Defining the degree of accuracy

Define the degree of accuracy for a quadrature

The degree of accuracy is the largest positive integer $n$ such that $I(p) = I_h(p)$ for all polynomials $p$ of degree $\leq n$.

5.2Finding the degree of accuracy

Given some $I_h$, find the degree of accuracy.

Consider $x^n$, and see what $I_h$ and $I$ do to it. (Could use $[0, 1]$ as the interval for the definite integral, or just keep $b$ and $a$ the way they are.) The largest $n$ for which $I_h$ and $I$ give the same result is the degree.

5.3Maximising the degree of accuracy

Find constants $\alpha$, $\beta$, and $\gamma$ to maximise the degree of accuracy of some quadrature formula.

There are 3 constants, so try $1, x, x^2$ and evaluate $I$ and $I_h$ for each of those. Equate to get a system of 3 equations and solve it for the constants.

5.4Finding some error constant

Find some constant $k$ in some error term etc.

Just simple algebraic manipulations. Use $f(x) = x^n$ where $n$ is the degree of accuracy.

5.5Approximating something

Approximate something (using an integral), and find an upper bound for the error

Approximating is easy; just plug in values, and use the given $f$. To find the error bound, plug in values for the error formula given previously.

6Simpson's rule

6.1The composite rule

Derive the composite rule.

Just apply it to every pair of subintervals: $x_0, x_1, x_2$, then $x_2, x_3, x_4$, then $x_4, x_5, x_6$, etc. Pretty easy to derive from the regular rule (which should be given, though it's also easy to remember):

$$I_h(f) = \frac{h}{3} \sum_{j=0}^{n/2-1} [f_{2j} + 4f_{2j+1} + f_{2j+2}] = \frac{h}{3} \left ([f_0 + f_n] + 2\sum_{j=1}^{n/2-1} f_{2j} + 4\sum_{j=0}^{n/2-1} f_{2j+1} \right )$$

6.2Proving a property of the composite rule

Show that the composite rule satisfies some error formula.

We're given the error bound for Simpson's rule. Sum that over the subintervals to get the error bound for the composite rule:

$$\sum_{j=0}^{n/2-1} \left [ \frac{-h^5}{90} f^{(4)} (\zeta_j) \right ] = -\frac{h^5}{90} \sum_{j=0}^{n/2-1} f^{(4)}(\zeta_j) \tag{where $\zeta_j \in [x_{2j}, x_{2j+2}]$}$$

Assume that $f^{(4)}$ is continuous on the interval $[a, b]$. Then there is a max and min value that $f^{(4)}$ attains over the interval, and by the intermediate value theorem, $f$ also attains every intermediate value. Most notably, it must evaluate to the following value at some point:

$$\frac{2}{n} \sum_{j=0}^{n/2-1} f^{(4)}(\zeta_j)$$

(Basically we just evaluate $f$ at a few points, take the sum, divide it accordingly; this value can't be greater than the max or less than the min of $f$ along the interval.)

Let's call this point $\xi \in [a, b]$. So then we have

$$f^{(4)}(\xi) = \frac{2}{n} \sum_{j=0}^{n/2-1} f^{(4)}(\zeta_j)$$

We can rearrange this to solve for $\displaystyle \sum_{j=0}^{n/2-1} f^{(4)}(\zeta_j)$:

$$\sum_{j=0}^{n/2-1} f^{(4)}(\zeta_j) = \frac{n}{2}f^{(4)}(\xi)$$

Then, substituting this into the error bound equation, and using the fact that $nh = b-a$, we get:

$$I(f) - I_h(f) = -\frac{h^5}{90} \cdot \frac{n}{2} f^{(4)}(\xi) = -\frac{h^4(hn)}{180} f^{(4)}(\zeta) = \frac{-(b-a)h^4}{90}f{(4)}(\xi) \; \blacksquare$$

6.3Finding an upper bound for the error

Find an upper bound for the error.

sooo easy. Plug and chug. See example.

6.4Using the rule

Evaluate it somewhere, and find the value of $h$ required to ensure some degree of precision.

even easier. see example.

7Runge-Kutta

7.1Proving an identity for $y(t_{i+1})$

Show that $y(t_{i+1}) = $ something.

use common sense

7.2Proving an identity for $w_{i+1}$

Some identity.

see above

7.3Conditions for the limit to approach 0

Under what conditions on $h$ does $\displaystyle \lim_{i \to \infty} w_i = 0$?

$y_{i+1}$ is probably defined as $y_i$ multiplied by something. If that something $<1$ (absolute-value-wise), it will converge to 0. So solve that inequality.

7.4Defining local truncation error

Define it

$\tau_{i+1}(h) = y(t_{i+1}) - w_{i+1}$ where $y(t)$ solves $y' = f(y)$ and $y(t_i) = w_i$.

7.5A formula for local truncation error

Prove that a given formula for the location truncation error holds.

Remember the definition for LTE. Recall that $t_{i+1} = t_i+h$, so you can do a Taylor expansion of $y(t_{i+1})$ which might help with simplifying the expression for LTE.

7.6Determining the order

Determine the order of the method.

If the error is $O(h^n)$ then the method is of order $n-1$

8Lagrange interpolation

8.1Defining Lagrange polynomials

Define the fundamental Lagrange polys for the interpolation points and show that $p_n(x)$ interpolates $f$ at each of the points.

$$l_j = \frac{x-x_0}{x_j-x_0} \cdots \frac{x-x_{j-1}}{x_j-x_{j-1}} \cdot \frac{x-x_{j+1}}{x_j-x_{j+1}} \cdots \frac{x-x_n}{x_j-x_n}$$

To show that it interpolates $f$ at all of the points, we just need to show that $p_n(x_j) = f(x_j)$ for $j=0, \ldots, n$. Well, in the expression for $p_n(x_j)$, all of the terms $l_k$ where $j \neq k$ vanish, because we have $x_j - x_j$ in the numerator of one of the terms in the product. So only $l_j$ remains, and $l_j$ looks like

$$l_j(x_j) = \frac{x_j-x_0}{x_j-x_10} \cdots \frac{x_j-x_{j-1}}{x_j - x_{j-1}} \cdot \frac{x_j - x_{j+1}}{x_j-x_{j+1}} \cdots \frac{x_j-x_n}{x_j-x_n} = 1$$

and so $p_n(x_j) = f(x_j)$ QED.

8.2Uniqueness

Show that $p_n(x)$ is the unique interpolating polynomial of degree $n$.

Suppose there's another poly, $q(x)$. Define $r(x) = p_n(x) - q(x)$. This is a poly of deg $\leq n$. At each of the data points, $x_i$, $r(x_i) = p_n(x_i) - q(x_i) = 0$ because both interpolate. Thus $r(x)$ has $n+1$ roots. But $r$ can't have $n+1$ roots if its degree is bounded above by $n$ ... unless $r(x) = 0$. So it must be that $r(x) = 0$ $\forall x$ which means that $p_n(x) = q(x)$ and so $p_n(x)$ is the unique interpolating polynomial.

8.3Finding the polynomial

Given some values, find $p_n$ for some $n$.

Construct the table of divided differences (REMEMBER TO DIVIDE, AND DIVIDE BY THE RIGHT THING) and build the Lagrange poly from there.

8.4Error bounds

Find a bound for the error in this approximation, using some given error formula.

Use the formula. Remember that $x$ is the point we're evaluating at.

9Splines, etc

9.1Differences between methods

Difference between Lagrange and Hermite? Clamped and natural cubic splines?

Hermite tries to match the first deriv at the nodes as well, Lagrange doesn't care about that shit

Clamped: matching the first derivs at the endpoints. Natural: the second derivs at the endpoints are 0.

9.2Finding constants for a cubic spline

Given the formula for a natural cubic spline, find some constants in it.

Find the first and second derivs, match the piecewise functions at the midpoints, etc

9.3Bezier curve stuff

Some q about Bezier curves

not gonna

10Trapezoidal rule

10.1Applying the composite rule

Apply the composite rule

Literally trapezoids. Not hard.

10.2Deriving an error bound

Derive some error bound

The error bound for the trapezoidal rule is

$$\frac{(b-a)^3}{12}f''(\xi)$$

To apply it to the composite rule, replace $b$ by $a+h$ for each segment (where $a$ is the first endpoint) and take the sum.

10.3Applying the error bound

Use the error bound you found to obtain upper bounds on the error for a specific approximation.

Use the formula.

10.4Using Richardson extrapolation

Use it to improve the approximation

think about it

10.5Computing relative error

Compute it

easy

11Linear shooting method

Not covered this semester.

12Root approximation and stuff

12.1Exactly one zero

Show that some function has exactly one zero in an interval.

could look at the derivative, find the stationary points, and look at values at the endpoints

or, if it's like $f(x) = x^3-3$, use the fact that there's only a zero when $x^3 = 3$ and $\sqrt{3}[3]$ lies between 1 and 2?

Whatever, don't really care if I get this wrong

12.2The bisection method

Use it to obtain an approximation. How many steps are required to ensure a certain degree of precision?

Actually pretty easy to compute ... Just keep bisecting the interval and figure out which section the root must be in. Convergence is governed by $2^n$, so to figure out the number of steps needed to ensure a certain degree of precision just do

$$\text{number of steps} = \log_2\left ( \frac{b-a}{\text{error}} \right )$$

12.3Comparing iterative methods

Rank given iterative methods based on order of convergence in a neighbourhood of the positive root

Look at the derivs I guess

12.4Using the quadratic formula

Using the quadratic formula, compute approximations to the roots of some formula

exactly what it says on the tin I would assume

13Finite difference

13.1The second derivative

Show that some formula holds for the second deriv and use this formula to approximate it at some point.

Use Taylor, apply the formula

13.2Minimising a bound

Some really long question asking you to find the value of $h$ to minimise some bound

the usual

14Aitken's method

Hopefully not covered but I'm not sure

15Matrix stuff

15.1Computing decompositions

$LDL^T$ and Cholesky decomps. Is this even possible without a computer?

TODO

  • Assignment 4 question 1 (a), (b)

15.2Solving systems

Jacobi and Gauss-Seidel. Which is faster?

TODO

  • Assignment 4 question 2

16Computing and precision

16.1Computing something to a certain precision

How accurately do we need to know something to compute it with a certain precision

Use Taylor series.

  • Midterm exercises question 2