## 这是一篇来自加拿大的CS代写，具体作业要求是提交解决方案的所有组件（书面/分析工作、代码/脚本/笔记本、图形、绘图等）。在每个问题的部分中以PDF形式进行众包标记。您还必须单独提交一个单独的zip文件，其中包含任何和所有的DropBox文件（也就是说，zip中的文件应该是.ipynb类型）

- (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*.d*1*d*2 *· · · **d**t **× *10*p **. *(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, *ax*2 + *bx *+ *c *= 0, are given by

*x*1 = *−**b *+ p *b *2 *− *4*ac* */*(2*a*)*, x*2 = *−**b **− *p *b *2 *− *4*ac* */*(2*a*)

when *a **6 *= 0.

(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

0*.*2*x *2 + 14*.*2*x *+ 1*.*67 = 0*, *(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, *x*1 and *x*2?

(b) (2 marks) A *cancellation problem *arises when applying the above formulae for any quadratic equation having the property that

*|**b**| ≈ *p *b *2 *− *4*ac. *

When this property holds, if *b > *0 then the quadratic formula for *x*1 will exhibit cancellation, while if *b < *0 then *x*2 will exhibit cancellation. We will try to circumvent this problem by reformulating our expression. Show that the following formula for *x*1,

*x*1 = (2*c*)*/ * *−**b **− *p *b *2 *− *4*ac* *, *

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 *x*2 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 *x*1 and *x*2 expressions).

**Algorithm R.**

if *b > *0 then

*x*2 = *−**b**− **√ **b *2*−*4*ac /*2*a *

*x*1 =*c/**ax*2

else

*x*1 =___

*x*2 =___

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 2*E *+ *E*2 (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:

*x**k*+1 = *g*(*x**k*) (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:

def bisection(f, a, b, tol, maxiter):

% This function computes a root of f in the interval [a, b]

% using the bisection 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.

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.

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 *= [*x*1*, x*2*, . . . , x**n*]*, *

where *x**k *is the approximate solution found after *k *iterations. The stopping criterion is when either *|**x**n **− **x**n**−*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, *e**k *= *|**x**k **− **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.