辅导cS 335程序、辅导R编程语言
cS 335 Assignment 3
(6 marks) Floating Point Basics
(a) (2 marks) Suppose that on a given base-10 flfloating point system of the form considered in class, the number 23 and the next representable flfloating point number larger than 23 are separated by 10?3 . What is the number of digits, t, in this system?
(b) (2 marks) Using what you found above, what is the spacing between 5 and the next larger representable number in the same flfloating point system?
(c) (2 marks) Suppose you are now given the fact that the range for the exponent is given by L = ?4 and U = 6 in the system above. What is the largest magnitude negative number that can be represented in this system? Express your answer in terms of the form
±0.d1d2 · · · dt × 10p . (1)
(8 marks) Effffects of Cancellation
We saw in class that adding two numbers of similar magnitude and opposing sign has the potential to cause large relative errors under flfloating point – this effffect is known as catastrophic cancellation, since cancellation of the leading digits causes a disastrous loss of precision. In some cases, however, this effffect can be avoided by rearranging the arithmetic expression to be computed.
The roots of a quadratic equation,
(a) (3 marks) Consider performing arithmetic in a flfloating point number system with β = 10,t = 5, L = ?10, U = 10 with truncation. Using the above formulas, you are to simulate by hand (with the aid of a calculator) the computation of the roots of the following quadratic equation, (2)
under this flfloating point system. (Obey the usual order of operations.) The true roots of the given quadratic, correct to fifive signifificant digits, are 0.11780 and 70.882. What is the relative error of each of your computed roots, x1 and x2?
(b) (2 marks) A cancellation problem arises when applying the above formulae for any quadratic equation having the property that
|b| ≈ p b 2 ? 4ac.
When this property holds, if b > 0 then the quadratic formula for x1 will exhibit cancellation, while if b < 0 then x2 will exhibit cancellation. We will try to circumvent this problem by reformulating our expression. Show that the following formula for x1,
is mathematically equivalent to the usual one given at the start of the question (i.e., assuming you are working with real numbers rather than flfloating point numbers.) Hint:
Rationalize the denominator of this expression.
(c) (1 mark) The formula for x2 can be manipulated similarly. Deduce a better algorithm for calculating the roots of a quadratic equation (which avoids cancellation errors), and present it in the form below (i.e., fifilling in the blanks for the x1 and x2 expressions).
Algorithm R.
if b > 0 then
x2 = ?b? √ b 2?4ac /2a
x1 =c/ax2
else
x1 =___
x2 =___
end
(d) (2 marks) Redo the calculation of the roots of equation (2) by applying Algorithm R using the same flfloating point number system. Compute the relative error of the computed roots and compare against your results from part (a). What do you observe?
(8 marks) Floating Point Error Analysis
Show that if x, y, z are already flfloating point numbers in some flfloating point system F, the relative error of the flfloating point calculation (x y)
z with respect to the true value of (x ? y)/z is less than or equal to 2E + E2 (where E is machine epsilon for the FP system F) assuming no overflflow/underflflow errors occurs.
The symbols and
here represent flfloating point subtraction and division, respectively. Just like we saw for addition in class, they satisfy a b = fl(a ? b) and a
b = fl(a/b), for flfloating point inputs a and b.
(6 marks) Convergence of Fixed Point Iteration
Consider a fifixed point iteration:
xk+1 = g(xk) (3)
g(x) =sin(x + π/2)/2 (4)
Will this iteration converge for any x ∈ [0, π/2]? Justify your answer by considering all the conditions of a convergence theorem.
(16 marks) Root fifinding methods
In this question you will implement each of the four root fifinding algorithms discussed in class in a Jupyter/Python notebook. The function prototypes are as follows:
Bisection method.
def bisection(f, a, b, tol, maxiter):
% This function computes a root of f in the interval [a, b]
% using the bisection method.
Secant method.
def secant(f, a, b, tol, maxiter):
% This function computes a root of f using the secant method
% with initial guesses x_{-1} = a, x0 = b.
Newton’s method.
def newton(f, fprime, x0, tol, maxiter):
% This function computes a root of f using the Newton’s method
% with initial guess x0. fprime should be the derivative of f.
Fixed point iteration.
def fixedpoint(g, x0, tol, maxiter):
% This function computes a fixed point of g using fixed point
% iteration with initial guess x0.
For each of these functions, the output should be a vector:
x = [x1, x2, . . . , xn],
where xk is the approximate solution found after k iterations. The stopping criterion is when either |xn ? xn?1| < tol or the number of iteration exceeds the maximum, maxiter. You will also need to defifine the functions f, fprime, g according to the problem to be solved, below.
(Note that Python allows you to pass functions as inputs to other functions, as implied by the function defifinitions above.)
Find the root (x ? = √ 3) of the following equation:
x 2 ? 3 = 0, x ∈ [0.5, 3.5]
using your four root fifinding functions with tol=1e-10 and maxiter=100. For the bisection and secant methods, use [a,b]=[0.5,3.5]. For Newton and fifixed point iteration, use x0=0.5. You will need to determine a g(x) function such that the fifixed point iteration converges. There are multiple valid choices here. (Do not use the g(x) that corresponds to Newton’s method.)
Next, using the root-fifinding methods above, write code that, for each of the methods, computes the errors of approximations, ek = |xk ? x ? |, and generates a simple text-format table like the following:
Print the x, e, and various ratio values in scientifific notation. A straightforward way to perform this type of formatting is using the print command, such as in the following (generic) example: print(“Row %d First Number: %0.7f Second Number: %0.7e” % (3, 1.73648392e-8,1.73648392e-8))
which prints
Row 3 First Number: 0.0000000 Second Number: 1.7364839e-08
The %d is used to indicate an integer. %0.7f and %0.7e are used to display flfloating point numbers in standard and scientifific notation, respectively, with the integer 7 here indicating the number of digits desired after the decimal. You can also use ’\t’ to insert tabs rather than spaces, such as print(“Word1\tWord2″), which may help in aligning text columns. For the last 3 column headers, you can use the simpler titles ’ratio1’, ’ratio2’, and ’ratio3’ in your code,rather than the mathematical expressions shown in the table above.
Using these tables, determine and state the order of convergence for each of the methods. Provide a brief text explanation of how you arrived at your answers.