MATH50003 Numerical Analysis: Problem Sheet 2¶
This week we look at other variants of finite-differences, including central differences and second-order
finite-differences. We also investigate mathematical properties of dual numbers, extend their implementation to
Copyright By PowCoder代写 加微信 powcoder
other functions. Finally, we see how dual numbers can be combined with Newton iteration for root finding.
Questions marked with a ⋆ are meant to be completed without using a computer.
1. Finite-differences¶
Problem 1.1⋆ Use Taylor’s theorem to derive an error bound for central differences
f'(x) ≈ {f(x + h) – f(x – h) \over 2h}.
Find an error bound when implemented in floating point arithmetic, assuming that
f^{\rm FP}(x) = f(x) + δ_x
where $|δ_x| \leq c ϵ_{\rm m}$.
Problem 1.2 Implement central differences for $f(x) = 1 + x + x^2$ and $g(x) = 1 + x/3 + x^2$.
Plot the errors for h = 2.0 .^ (0:-1:-60) and h = 10.0 .^ (0:-1:-16).
Derive the error exactly for the different cases to explain the observed behaviour.
Problem 1.3⋆ Use Taylor’s theorem to derive an error bound on the second-order derivative approximation
f”(x) ≈ {f(x+h) – 2f(x) + f(x-h) \over h^2}
Find an error bound when implemented in floating point arithmetic, assuming that
f^{\rm FP}(x) = f(x) + δ_x
where $|δ_x| \leq c ϵ_{\rm m}$.
Problem 1.4 Use finite-differences, central differences, and second-order finite-differences to approximate to 5-digits the first and second
derivatives to the following functions
at the point $x = 0.1$:
\exp(\exp x \cos x + \sin x), \prod_{k=1}^{1000} \left({x \over k}-1\right), \hbox{ and } f^{\rm s}_{1000}(x)
where $f^{\rm s}_n(x)$ corresponds to $n$-terms of the following continued fraction:
1 + {x-1 \over 2 + {x-1 \over 2 + {x-1 \over 2 + \ddots}}},
\begin{align*}
f^{\rm s}_1(x) &= 1 + {x-1 \over 2} \\
f^{\rm s}_2(x) &= 1 + {x-1 \over 2 + {x -1 \over 2}} \\
f^{\rm s}_3(x) &= 1 + {x-1 \over 2 + {x -1 \over 2 + {x-1 \over 2}}}
\end{align*}
2. Dual numbers¶
Problem 2.1⋆
Show that dual numbers $𝔻$ are a commutative ring, that is, for all $a,b,c ∈ 𝔻$ the following are satisfied:
additive associativity: $(a + b) + c = a + (b + c)$
additive commutativity: $a + b = b + a$
additive identity: There exists $0 ∈ 𝔻$ such that $a + 0 = a$.
additive inverse: There exists $-a$ such that $(-a) + a = 0$.
multiplicative associativity: $(ab)c = a(bc)$
multiplictive commutativity: $ab = ba$
multiplictive identity: There exists $1 ∈ 𝔻$ such that $1a= a$.
distributive: $a(b+c) = ab + ac$
Problem 2.2⋆ A field is a commutative ring such that $0 ≠ 1$ and all nonzero elements have a multiplicative inverse, i.e.,
there exists $a^{-1}$ such that $a a^{-1} = 1$. Why isn’t $𝔻$ a field?
Problem 2.3⋆ A matrix representation of a ring are maps from a group/ring to matrices such that matrix addition and multiplication
behave exactly like addition and multiplication that of the ring.
That is, if $A$ and $B$ are elements of the ring and $ρ$ is a representation, then
ρ(A + B) = ρ(A) + ρ(B) \hbox{ and } ρ(AB) = ρ(A)ρ(B).
Show that the following are matrix representations of complex numbers and
dual numbers (respectively):
\begin{align*}
a + b {\rm i} &\mapsto \begin{pmatrix} a & b \\ -b & a \end{pmatrix} \\
a + b {\rm i} &\mapsto \begin{pmatrix} a & b \\ 0 & a \end{pmatrix}
\end{align*}
Problem 2.4⋆ What is the correct definition of division on dual numbers, i.e.,
(a + b \epsilon )/(c + d \epsilon ) = s + t \epsilon
for what choice of $s$ and $t$? Use dual numbers to compute the derivative of the following functions at $x = 0.1$:
\exp(\exp x \cos x + \sin x), \prod_{k=1}^3 \left({x \over k}-1\right),\hbox{ and } f^{\rm s}_2(x) = {1 + {x – 1 \over 2 + {x-1 \over 2}}}
Problem 2.5 Add support for cos, sin, and / to the type Dual:
# Dual(a,b) represents a + b*ϵ
struct Dual{T}
# Dual(a) represents a + 0*ϵ
Dual(a::Real) = Dual(a, zero(a)) # for real numbers we use a + 0ϵ
# Allow for a + b*ϵ syntax
const ϵ = Dual(0, 1)
import Base: +, *, -, /, ^, zero, exp, cos, sin
# support polynomials like 1 + x, x – 1, 2x or x*2 by reducing to Dual
+(x::Real, y::Dual) = Dual(x) + y
+(x::Dual, y::Real) = x + Dual(y)
-(x::Real, y::Dual) = Dual(x) – y
-(x::Dual, y::Real) = x – Dual(y)
*(x::Real, y::Dual) = Dual(x) * y
*(x::Dual, y::Real) = x * Dual(y)
# support x/2 (but not yet division of duals)
/(x::Dual, k::Real) = Dual(x.a/k, x.b/k)
# a simple recursive function to support x^2, x^3, etc.
function ^(x::Dual, k::Integer)
error(“Not implemented”)
elseif k == 1
x^(k-1) * x
# Algebraic operationds for duals
-(x::Dual) = Dual(-x.a, -x.b)
+(x::Dual, y::Dual) = Dual(x.a + y.a, x.b + y.b)
-(x::Dual, y::Dual) = Dual(x.a – y.a, x.b – y.b)
*(x::Dual, y::Dual) = Dual(x.a*y.a, x.a*y.b + x.b*y.a)
exp(x::Dual) = Dual(exp(x.a), exp(x.a) * x.b)
function cos(x::Dual)
# TODO: implement cos for Duals
function sin(x::Dual)
# TODO: implement sin for Duals
function /(x::Dual, y::Dual)
# TODO: implement division for Duals
/ (generic function with 119 methods)
Problem 2.6 Use dual numbers to compute the derivatives to
\exp(\exp x \cos x + \sin x), \prod_{k=1}^{1000} \left({x \over k}-1\right), \hbox{ and } f^{\rm s}_{1000}(x).
Does your answer match (to 5 digits) Problem 1.4?
3. Newton iteration¶
Newton iteration is an algorithm for computed roots of a function $f$ using its derivative: given an initial guess $x_0$, one
obtains a sequence of guesses via
x_{k+1} = x_k – {f(x_k) \over f'(x_k)}
Problem 3.1 Use Dual to implement the following function which returns $x_n$:
function newton(f, x0, n)
## TODO: compute x_n
newton (generic function with 1 method)
Problem 3.2 Compute points $y$ such that $|f(y)| \leq 10^{-13}$ (i.e., approximate roots):
\exp(\exp x \cos x + \sin x)-6\hbox{ and } \prod_{k=1}^{1000} \left({x \over k}-1\right) – {1 \over 2}
(Hint: you may need to try different x0 and n to get convergence. Plotting the function should give an
indication of a good initial guess.)
Problem 3.3 Compute points $y$ such that $|f^{\rm s}_{1000}(y) – j| \leq 10^{-13}$ for $j = 1,2,3$.
Make a conjecture of what $f^{\rm s}_n(x)$ converges to as $n → ∞$. (Bonus problem: Prove your conjecture.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com