# Final exam review exercises

Exercises (and solutions) available on Docuum.

## 1Question 1¶

FPT

### 1.1Solution¶

#### 1.1.1Part (a)¶

State the fixed-point theorem.

ez

#### 1.1.2Part (b) (i)¶

Show fixed point of iteration

ez

#### 1.1.3Part (b) (ii)¶

Show that it satisfies conditions

ez

#### 1.1.4Part (b) (iii)¶

Order of convergence?

Find $g'$, evaluate at $x=x^*$. If $g'(x^*) = 0$, it's quadratic.

#### 1.1.5Part (b) (iv)¶

Compute $x_3$ given some $x_0$

ez

#### 1.1.6Part (b) (v)¶

Relative error?

$$\frac{|x_3-x^*|}{|x^*}$$

See solutions

## 2Question 2¶

### 2.1Solution¶

Construct the table of divided diffs, etc

Same as 2004 q3 (d) and 2008 q2 (d)

## 3Question 3¶

fwd diff

### 3.1Solution¶

#### 3.1.1Part (a)¶

Use Taylor series to show some formula holds

Write out the expansion, rearrange terms

#### 3.1.2Part (b)¶

Use Richardson extrap to show some formula holds

Replace $h$ by $h/2$ in the expression for $f'(x_0)$, and eliminate the terms aren't present in the formula we want to prove. Add/subtract expressions until you get the desired one.

#### 3.1.3Part (c)¶

Use the above to find some approximations

ez

## 4Question 4¶

### 4.1Solution¶

#### 4.1.1Part (a)¶

Define deg of acc

largest positive $n$ such that for any poly $p$ of degree $n$ or less, $I(p) = I_h(p)$

#### 4.1.2Part (b)¶

Find deg of acc

Substitute the values given into the formula. Don't even need to choose an interval, just keep $a$ and $b$ there (though we could if we wanted). Then try $x^n$ for all $n$ starting from $n=0$ and see which value of $n$ breaks it

#### 4.1.3Part (c)¶

Find constants to max the deg of acc

There are 3 constants. Try polynomials of up to degree 2 (since then we'd get a system of 3 linear equations, which is the perfect number to fully constrain the constants), so $f(x) = 1$, $f(x) = x$, and $f(x) = x^2$. Evaluate $I(f)$ and $I_h(f)$ for each $f$, and equate them to get an equation with the possible variables $a, b, \alpha, \beta, \gamma, h$. (Leave $h$ as-is as much as you can, and try to cancel it if possible.) This gives us a nonlinear system of 3 equations. Solve it, algebraically (can't use a matrix cus not linear). It's kind of a bitch but it works out in the end.

## 5Question 5¶

### 5.1Solution¶

#### 5.1.1Part (a)¶

Diff between Lagrange/Hermite interp? Diff between clamped/natural cubic splines?

Hermite interpolation: match the derivative of the function at the nodes, whereas with Lagrange it's just the value of the nodes.

Clamped cubic spline: we impose the extra conditions and $S'(x_0) = f'(x_0)$ and $S'(x_n) = f'(x_n)$ (so the first deriv is the same at the endpoints). Natural cubic spline: No such condition for the first deriv, but we set the second deriv to 0 at the endpoints (so $S''(x_0) = S''(x_n) = 0$).

#### 5.1.2Part (b)¶

Find constants in formula for natural cubic spline

Given the equation(s) for the cubic spline, take the first and second derivs, and evaluate it at the midpoints (the $x$-values where the equations change). We know that $S_0$ and $S_1$ have to agree at the first midpoint (and the first and second derivs too), and since it's a natural cubic spline, just set the second deriv to 0 at the endpoints (use the endpoint that gives you info ... one doesn't tell you anything). That is enough to uniquely determine the constants.

pretty easy.

### 5.2Accuracy and discussion¶

There's a typo in the solutions for (a) ... the two extra conditions for clamped cubic splines are actually the same condition >_>

Also pretty sure there's a typo in the solutions for (b) as well. $a$ should be 2, not 1, since $S_0(1) = 1 + 2(1) -1^3 = 2$ and $S_1(1) = a$ ... $b$ is still $-1$ and $c$ is still $-3$, and $d$ is still $-1$.

## 6Question 6¶

### 6.1Solution¶

#### 6.1.1Part (a)¶

Derive Newton's method using Taylor expansions.

The Taylor expansion should be given. Drop the error term and rearrange to get $x^*$ on the LHS:

$$x^* = \frac{f(x^*)-f(x)}{f'(x)} + x$$

Since $x^*$ is a root, we should have $f(x^*) \approx 0$, so drop that term and rearrange again:

$$x^* = x - \frac{f(x)}{f'(x)}$$

Then just replace $x^*$ by $x_{n+1}$ and $x$ by $x_n$ (which makes sense if you think about it ... $x^*$ is the true root) to get

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

which is Newton's method.

#### 6.1.2Part (b)¶

Write it as a fixed-point iteration

so easy

#### 6.1.3Part (c)¶

If $f'(x^*) \neq 0$, show that $g'(x^*) = 0$.

Take the first deriv of $g$ (use the quotient rule, or, if you're like me and can never remember the quotient rule, derive it using the multiplication rule). You should get

$$\frac{f(x)f''(x)}{[f'(x)]^2}$$

Then, if the first deriv is non-zero, the denom is non-zero so we get a valid expression, and since $f(x) = 0$ at $x=x^*$ (cus root etc) then the numerator is 0 so yeah 0 all the way down

#### 6.1.4Part (d)¶

If $f'(x^*) = 0$ but $f''(x^*) \neq 0$, find the limit of $g'(x)$ as $x \to x^*$.

The method presented in the solutions seems a bit arbitrary but let's run with it. Write $f(x) = (x-x^*)^2r(x)$ where $r(x^*) \neq 0$. Take the first and second derivatives, then substitute that into the formula for $g'$ and find the limit, etc. Not really sure where the $1/2$ pops out from, though. If I had to actually do this question on the exam I probably wouldn't do very well. I think I'll just forego trying to understand this fully. Gotta cut your losses at some point amirite

#### 6.1.5Part (e)¶

Order of convergence?

First, make sure that it converges. Then, look at the limit from the previous part. Since it's between 0 and 1 we can safely say that the order of convergence is 1 (linear)

### 6.2Accuracy and discussion¶

There's a typo in the question for (c) - it omits the $=0$ from the $g'(x^*) = 0$. Not a big deal though. In the solution for (c), the expression for $g'(x)$ could be more simplified, but whatever.

## 7Question 7¶

Runge-Kutta

### 7.1Solution¶

#### 7.1.1Part (a)¶

Show that $y(t_{i+1}) = e^{h\lambda}y(t_i)$.

We're given that $y(t) = \lambda y(t)$. Hopefully you know how to solve this ODE - it's just $y(t) = \alpha e^{\lambda t}$. Recall that $t_{i+1} = t_i + h$. Then, substituting that into the expression for $y(t_{i+1})$:

$$y(t_{i+1}) = \alpha e^{\lambda t_{i+1}} = \alpha e^{\lambda(t_i + h)} = \alpha e^{\lambda t_i}e^{\lambda h} = y(t_i)e^{\lambda h} = e^{h\lambda}y(t_i) \;\checkmark$$

#### 7.1.2Part (b)¶

Show that $y_{i+1}$ is equal to some expression.

I don't know if there's a typo in the solution or what, but it doesn't seem to work ... there's an extra $3/4h$ that is unaccounted for. On the other hand, if I completely ignore the provided solutions and treat the first argument to the last $f$ as $t_i$ instead of $t_i + 2/3h$ then everything seems to work okay. Not sure why? Why can I just ignore that argument? Whatever.

#### 7.1.3Part (c)¶

Under what conditions on $h$ does the limit of $y_{i} = 0$ as $i \to \infty$

Well, $y_{i+1} = \beta y_i$ which will converge to 0 if $|\beta| <1$. $\beta$ in this case is $1 + h\lambda + (h\lambda)^2/2$. Replace $h\lambda$ by $x$ and write it as a function $g$:

$$g(x) = 1 + x + \frac{x^2}{2}$$

Take the first deriv, find the zeroes of that. $g$ has a min at $x=-1$, at which point it's $1/2$. $g(x) < 1$ when $g(x) - 1< 0$, i.e., $x(1+x/2)$. This happens when $x > 0$ and $1+x/2 < 0$ (obviously not possible) and when $x <0$ and $1 + x/2 > 0$, i.e., $0 > x > -2$. Thus $0 > h\lambda > -2$. We're given that $\lambda < 0$, and $h > 0$ by definition, so all we need to specify is that $h < -2/\lambda$.

#### 7.1.4Part (d)¶

Define local truncation error, prove that the given expression for it holds

Local truncation error is given by

$$\tau_{i+1}(h) = y(t_{i+1}) - y_{i+1} = y(t_{i+1}) - \left (1+h\lambda + \frac{(h\lambda)^2}{2} \right )y(t_i)$$

Now use Taylor expansions to rewrite $y(t_{i+1})$, using the fact that $y(t_{i+1}) = y(t_i + h)$:

$$y(t_{i+1}) = y(t_i + h) = y(t_i) + hy'(t_i) + \frac{h^2}{2}y''(t_i) + \frac{h^3}{6} y'''(\xi)$$

Recall that $y'(t) = \lambda y(t)$ (given as a premise). Then $y''(t) = \lambda^2 y(t)$, $y'''(t) = \lambda^3 y(t)$. Substitute those into the formula above to get

$$y(t_{i+1}) = y(t_i) + h\lambda y(t_i) + \frac{(h\lambda)^2}{2}y(t_i) + \frac{(h\lambda)^3}{6}y(\xi) = y(t_i)\left (1 + h\lambda + \frac{(h\lambda)^2}{2} \right ) + \frac{(h\lambda)^3}{6}y(\xi)$$

for some $\xi \in (t_i, t_{i+1})$. Then, for some reason, you divide the expression for $\tau$ I had above by $h$ to get the true local truncation error. Why is that? Not sure. Every resource I can find tells me that my formula for LTE above is correct, and yet, it looks like dividing by $h$ is needed for some reason. In the end, you're supposed to end up with

$$\frac{h^2\lambda^3}{6}y(\xi)$$

which makes sense if you somehow require dividing by $h$.

### 7.2Accuracy¶

I like my solution for (a) better than the provided solution but I guess they're equivalent.

Also, there's a typo in the question for (a). I think it's supposed to say $y'(t) = f(t, y(t)) = \lambda y(t)$. I actually found 3 different possible spots for the missing parenthesis that I thought were right before I realised what the correct one was. Which just goes to show how important properly closed parentheses are. Also how bad I am at math because there is only one possibility that makes sense. It's ok, I just need to pass.

Probable typo for solution in (b) (there's a $3/4hy_i$ that is completely unaccounted for in the last line).

Typo for the question in (c) (missing the limit function). Also, I feel like it has to be $< 1$ not $\leq 1$ because otherwise how does that make sense? If it were $\leq 1$, wouldn't it just converge to $\alpha$? A definite typo in the definition of $g$ - should be $x^2/$ not $x/2$.

Part (d): no idea where that $h$ came from