Wikinotes

Maintainer: admin

Exercises (and solutions) available on Docuum.

FPT

State the fixed-point theorem.

Show fixed point of iteration

Show that it satisfies conditions

Order of convergence?

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

Compute $x_3$ given some $x_0$

Relative error?

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

See solutions

Construct the table of divided diffs, etc

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

fwd diff

Use Taylor series to show some formula holds

Write out the expansion, rearrange terms

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.

Use the above to find some approximations

Define deg of acc

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

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

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.

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$).

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.

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$.

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.

Write it as a fixed-point iteration

so easy

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

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

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)

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.

Runge-Kutta

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$$

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.

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$.

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$.

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

Final exam review exercises

1Question 1¶

1.1Solution¶

1.1.1Part (a)¶

1.1.2Part (b) (i)¶

1.1.3Part (b) (ii)¶

1.1.4Part (b) (iii)¶

1.1.5Part (b) (iv)¶

1.1.6Part (b) (v)¶

1.2Accuracy and discussion¶

2Question 2¶

2.1Solution¶

2.2Accuracy and discussion¶

3Question 3¶

3.1Solution¶

3.1.1Part (a)¶

3.1.2Part (b)¶

3.1.3Part (c)¶

3.2Accuracy and discussion¶

4Question 4¶

4.1Solution¶

4.1.1Part (a)¶

4.1.2Part (b)¶

4.1.3Part (c)¶

4.2Accuracy and discussion¶

5Question 5¶

5.1Solution¶

5.1.1Part (a)¶

5.1.2Part (b)¶

5.2Accuracy and discussion¶

6Question 6¶

6.1Solution¶

6.1.1Part (a)¶

6.1.2Part (b)¶

6.1.3Part (c)¶

6.1.4Part (d)¶

6.1.5Part (e)¶

6.2Accuracy and discussion¶

7Question 7¶

7.1Solution¶

7.1.1Part (a)¶

7.1.2Part (b)¶

7.1.3Part (c)¶

7.1.4Part (d)¶

7.2Accuracy¶