University of Toronto at Scarborough .

University of Toronto at Scarborough CSCC37—Numerical Algorithms for Computational Mathematics, Fall 2016 Assignment #1: Computer Arithmetic / Norms Due: October 7, 2016 at 11:45 p.m. This assignment is worth 10% of your final grade. Warning: Your electronic submission on MarkUs affirms that this assignment is your own work and no one else’s, and is in accordance with the University of Toronto Code of Behaviour on Academic Matters, the Code of Student Conduct, and the guidelines for avoiding plagiarism in CSCC37. This assignment is due by 11:45 p.m. October 7. If you haven’t finished by then, you may hand in your assignment late with a penalty as specified in the course information sheet. 1.[10] Consider a fictitious floating-point number system composed of the following numbers: S = f±b1:b2b3 × 2±y : b2; b3; y = 0 or 1; and b1 = 1 unless b1 = b2 = b3 = y = 0g: (a) Draw a portion of the real axis and plot the elements of S. (b) Show that S contains twenty-five elements. What are the largest and smallest (in absolute value, nonzero) floating-point numbers? What is machine epsilon? 2.[10] Prove that machine precision , as defined in lecture, can be used as a bound for relative round-off. In other words, prove that  =  b 1 21b − 1t −t chopping rounding where b is the base of the computer’s floating point number system and t is the mantissa length. 3.[10] Let x; y 2 Rn. Recall that fl(x); fl(y) 2 Rb(t; s) denote the floating-point representations of x and y, respectively, where fl(x) = x(1 − δx), fl(y) = y(1 − δy), and δx; δy quantify the relative roundoff errors in the respective representations. In lecture we showed that a typical computer estimates the product of x and y as fl(fl(x) · fl(y)) = (x · y)(1 − δ:) where jδ:j ≤ 3 eps. Derive a similar error bound for computer division. 4.[10] Prove or disprove the following. (a) Machine multiplication of two n × n matrices is commutative. (b) Machine multiplication of three n × n matrices is associative. Page 1 of 2 pages.5.[10] For x 2 Rn, prove that kxk1 = lim p!1 kxkp where kxkp = (jx1jp + · · · + jxnjp) 1p p 2 N ; p ≥ 1 6.[15] When both A and B are n × n upper-triangular matrices, the entries of C = AB are defined as follows: cij =  P 0 1 j k=i aikbkj 1 ≤ ≤ i j < i ≤ j ≤ ≤ n n : For n = 2 show that fl(AB) = A ^B ^ where A ^ = A + EA and B ^ = B + EB. Derive bounds for kEAk and kEBk showing that they are small relative to kAk and kBk, respectively. In other words, show that the computed product is the exact product of slightly perturbed A and B. [total: 65 marks] Page 2 of 2 pages.

Leave a Reply

Your email address will not be published.