Description

Question1 (8 points)
A function f : R → R is differentiable in some open interval I ∈ R if it is differentiable at every point of I, and it is Lipschitz continuous if there is a constant c ≥ 0 such that
|f(x1) − f(x2)| ≤ c|x1 − x2| for all x1,x2 ∈ I
(a) (2 points) Give a function, with proof, that is differentiable but its derivative is not bounded in some open interval.
(b) (2 points) Suppose f is differentiable and f0 is bounded in some open interval. Prove that f is Lipschitz continuous in that interval.
(c) (2 points) Give a function, with proof, that is differentiable but not Lipschitz continuous in some open interval.
(d) (2 points) Give a function, with proof, that is Lipschitz continuous but not differentiable in some open interval.
Question2 (4 points)
A fixed point of a function g(x) is a real number x∗ such that
g(x∗) = x∗
Assume the followings:
1. The function g and its derivative g0 are continuous on [a,b], that is,
g,g0 ∈ C[a,b]
2. The function g is bounded below by a and above by b, that is,
g(x) ∈ [a,b] for all x ∈ [a,b]
3. The initial point x0 is an interior point of [a,b], that is,
x0 ∈ (a,b)
Show the followings are true.
(a) (2 points) If 0 ≤ |g0(x)| < 1 for all x ∈ [a,b], the fixed-point iteration will converge to the unique fixed point x∗ ∈ [a,b].
(b) (2 points) If |g0(x)| > 1 for all x ∈ [a,b], then the fixed-point iteration will never converge to x∗.
Question3 (4 points)
Choose a suitable numerical method to find the smallest positive root and the second smallest positive root of the equation
tanx = 4x,
correct to 3 decimal places. Explain your choice.
Question4 (10 points)
Suppose that the sequence {an} converges to the number L, and there is a constant
0 < λ < ∞
such that

then the sequence is said to converge linearly to L. If

then the sequence is said to converge quadratically to L. If

then the sequence is said to converge to L with order of convergence α. The constant λ is called the asymptotic error. A positive sequence {En} is said to has an order of at least α and a rate of at most λ if there is a sequence {an} that has an order α and a rate of λ such that
En ≤ an for all n.
(a) (2 points) Find the order of convergence and the rate of convergence of the sequence
for n ≥ 1
(b) (2 points) Examine the order of convergence and the rate of convergence of {bn} where
and for k ≥ 1
(c) (2 points) Use the precise definition above to show the method of fixed-point iteration leads an error sequence that has at least linear convergence.
(d) (2 points) Find the asymptotic error constant for the method of fixed-point iteration when it has at least quadratic convergence.
(e) (2 points) Show the order of convergence of the secant method is

Question5 (10 points)
Suppose that f(x) and its derivatives f0(x),…,f(m)(x) are defined and continuous on an interval containing x∗, we say that f(x) = 0 has a root of order m at x = x∗ if and only if f(x∗) = 0, f0(x∗) = 0, f00(x∗) = 0, ··· f(m−1)(x∗) = 0, and f(m)(x∗) 6= 0
The positive integer m is known as the multiplicity of the root. A root of order m = 1 is often called a simple root, and if m > 1, it is called a multiple root.
Page 2
(a) (2 points) Prove by induction that there exists a continuous function h(x) so that f(x) can be expressed as the product
f(x) = (x − x∗)mh(x), where h(x∗) 6= 0
if the equation f(x) has a root of order m at x = x∗.
(b) (2 points) Show the following modified Newton’s iteration will produce a sequence that converges quadratically to x∗

if the original Newton’s method produces a sequence converges linearly to the root x = x∗ of order m > 1.
(c) (2 points) In practice, it is unlikely that m is known, in those cases the following version of modified Newton’s method can be applied to accelerate convergence
where
Explain how this helps to speed up convergence.
(d) (2 points) Zero is a root of multiplicity of 3 for the function
f(x) = sin(x3).
Start with x0 = 1 and compute x1, x2, …, x6 first by using the iteration formula in part (b) and then by using the iteration formula in part (c). What can you conclude based on the values that you have computed.
(e) (2 points) Compare Newton’s method and the modified version of it in part (c) by finding all the roots of the following polynomial correct to 6 decimal places.
f(x) = x5 − 11×4 + 46×3 − 90×2 + 81x − 27
Question6 (4 points)
Provide an example, if exists, of root-finding problems that satisfy the following criteria:
(a) (2 points) It can be solved by Bisection but not by using fixed-point iteration.
(b) (2 points) It can be solved by using fixed-point iteration but not by Newton’s method.
Question7 (0 points)
Let f : C → C be analytic. The following iteration formula can be used to solve f(z) = 0.

where f0(z) and f00(z) are the usual complex derivatives of f(z). (a) (1 point (bonus)) For the following function
f(z) = z7 − 1
depict the relationship between the initial point z0 = x0 + iy0 and the number of iteration required for the sequence to be considered to have converged, that is,
where
(b) (1 point (bonus)) What happens to the relationship in part (a) if we use the criterion
where
Page 3