Description
1.
(a) [10 points] Find the condition number of f (x) = (a + x)
1/4
− a
1/4, for x > 0, a >0 and study whether there are ranges
of x∈IR+
for which the computation of f is ill-conditioned. (You may need to use de l’ Hospital’s rule.)
(b) [10 points] Consider the (numerical) stability of the computation of the expression (a + x)
1/4
− a
1/4, for x > 0, a > 0,
when x is close to 0. Explain what problems the computation of the expression may give rise to. Propose a mathematically equivalent expression that is likely to be more stable for x close to 0, and explain.
(c) [10 points] Set a = 1. Write a MATLAB or equivalent script that goes through the values of x in
{10−20, 10
−19,…,10
−1
, 1, 10, … , 10
19, 10
20}, and computes and outputs x, the respective values of f using the original
expression, as well as your proposed (more stable) expression, the respective condition numbers (computed using the
values of f with the original expression and the values of f with the proposed expression), and the relative error
between the f values computed using the original and proposed expressions. Comment on the results. Use an appropriate format for the results, e.g. fprintf(’%9.2e %12.5e %12.5e %12.5e %12.5e %10.2e0, …
2. Consider the integrals
yn =
1
0
∫
t
n
e
−t
dt, n = 0, 1, 2, …
(a) [10 points] Derive a recurrence relation for yn
relating yn
to yn−1
. (You may have to use integration by parts.) Rearrange the formula so that you have a recurrence relation for yn−1
relating yn−1
to yn
. Name the first recurrence formula (A) and the second one (B).
(b) [10 points] With repeated applications of (A), give a formula that gives yn as a function of y0
, i.e. yn = fn
(y0
). With
repeated applications of (B), give a formula that gives yn as a function of ym, for m > n, i.e. yn = gn,m(ym).
(c) [10 points] Find the condition number of the functions
fn
(y0
) and gn,m(ym) for m > n.
(Note: Function fn has y0 as the variable, and function gn,m has ym as the variable.)
Taking into account the condition numbers of the above two functions formulate a stable method for computing
y0
, y1
,
…
, yN , where N ≥ 1 is giv en.
(d) [10 points] Write and run a MATLAB or equivalent program that computes and outputs y0
, y1
,
…
, yN , starting with y0
and using recursion (A). Explain what happens! (A reasonable N to stop is N = 20.)
(e) [15 points] Write a MATLAB or equivalent program that sets yN+K to some appropriate value (which may be approximate), and computes and outputs (N + K − 1, yN+K−1
), (N + K − 3, yN+K−2
), … , (N, yN ), starting with yN+K and using
recursion (B). At the end of the recursion, when the value of yN is output, also output the ‘‘exact’’ value and the (absolute) error in the computed yN . Run the program for K = 3, … ,9 and N = 20 (7 cases). Note that the code should
have a nested loop (one loop for K and one for the recursion). Explain what happens! Assume the ‘‘exact’’ value is q
= 0.018350467697256206326; Comment on how one should compute y20 to machine precision.
Notes: You should not use any symbolic environment. No integral calculations (other than the recurrences given). Use (the
standard) double precision. You should not change the precision. Use an appropriate format, e.g. fprintf(’%3d
%20.16f\n’, i-1, y(i)); and fprintf(’%3d %20.16f %20.16f %10.6e\n’, 20, y(21), q, qy(21));.
CSC336 Assignment 1
-2-
3. [15 points] Assume that A and B are given dense n × n matrices, B is non-singular, II is the identity matrix of order n,
and b a giv en n × 1 vector, for some n large. Explain how you would efficiently compute z = B
−1
(2A + II)(B
−1
+ A)b.
Give, in terms of n, approximate operation counts for all computations you propose.
Note: The computations that you will propose may include LU factorization, back-and-forward substitutions, matrixvector products, matrix-matrix products, matrix inverse calculation, addition of vectors or matrices, and other similar
computations. However, you are not obliged to use all these types of computations. For each computation you propose, you should give operation counts (indicating the highest power of n, including the coefficient), and make sure
that the total number of operation counts is as little as possible. You do not need to describe algorithms for these computations. Also note that, while B is given, B
−1
is not given.
CSC336 Assignment 1
