AMATH 242/CS 371 Midterm Solutions
Let a be a real number. Define two functions
f(x) = a2 − x2
a − x
;
g(x) = a3 − x3
a − x
on the domain fx 2 R n fagg, that is, the set of all real numbers except a.
(a) Using f
...
AMATH 242/CS 371 Midterm Solutions
Let a be a real number. Define two functions
f(x) = a2 − x2
a − x
;
g(x) = a3 − x3
a − x
on the domain fx 2 R n fagg, that is, the set of all real numbers except a.
(a) Using floating point arithmetic, why is it difficult to calculate the functions f and g
accurately for values of x that are close to the constant a? Be precise.
Solution: (6 marks) Because when a and x are close, the numerator and the denominator
in both functions will contain sums of terms that are (i) close in magnitude and (ii) of
opposite signs. This implies that the condition number for floating point addition
jaj + jxj
ja + xj
becomes large. This is called catastrophic cancellation.
(b) Find a way to express the functions f and g such that an ordinary computer is more
likely to compute them accurately when a and x are close. (Hint: Both functions are
polynomials and you can find their coefficients.)
Solution: (4 marks)
f(x) =(a − x)(a + x)
a − x
= a + x
g(x) =(a − x)(a2 + ax + x2)
a − x
= a2 + ax + x2
since x 6= 0. This solves the problem mentioned in part (a).
1
This study source was downloaded by 100000904123021 from CourseHero.com on 02-27-2026 19:43:18 GMT -06:00
https://www.coursehero.com/file/32404333/midterm-solutionspdf/2. (10 marks) (Root Finding Algorithms)
Recall the definition of a contraction:
Definition: A real-valued function g that is continuous on a closed interval [a; b]
is said to be a contraction on [a; b] if there exists a constant L 2 (0; 1) such that
jg(x) − g(y)j ≤ Ljx − yj for all x; y 2 [a; b].
Use the definition above to prove the following theorem:
Theorem: Suppose that the real-valued function g is a contraction on the closed interval [a; b] and that 8x 2 [a; b] : g(x) 2 [a; b]. Then (i) there exists a unique number
x∗ 2 [a; b] such that g(x∗) = x∗ and (ii) the sequence fxkg defined by xk+1 = g(xk)
converges to x∗ as k ! 1 for any initial value x0 2 [a; b].
Hints for getting started:
1. For part (i), you can use the facts that a ≤ g(a) and b ≥ g(b) together with Mean Value
Theorem to prove that the fixed point x∗ exists. Then you can prove that the point is
unique by using the definition of a contraction.
2. For part (ii), you can show that the following inequality is true:
jxi − x∗j ≤ Ljxi−1 − x∗j
for adjacent elements xi; xi−1 2 [a; b] in the sequence fxkg. Then you can use this inequality to complete the proof.
Solution: This is the Contraction Mapping Theorem, also called the Banach Fixed-Point
Theorem, which is an important theorem for computational mathematics. See a proof on p.
40{42 in the course notes. Remark: If you need any help understanding the proof, please feel
free to come and see me during my office hours.
[Show More]
