CSC336-Assignment 1 Solved

CSC336S                                                                                  Assignment 1                      

(a)Find the condition number of f (x) = (a + x)1/4 − a1/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)Consider the (numerical) stability of the computation of the expression (a + x)1/4 − a1/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) 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,...,1019,1020}, 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  ne−tdt,      n = 0, 1, 2,...

(a) 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) 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)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)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.

CSC336  Assignment 1       C. Christara - 2 -

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