程序代写代做 html CSC338. Homework 7

CSC338. Homework 7
Due Date: Wednesday March 11, 9pm
Please see the guidelines at https://www.cs.toronto.edu/~lczhang/338/homework.html
What to Hand In
Please hand in 2 files:
• Python File containing all your code, named hw7.py.
• PDF file named hw7_written.pdf containing your solutions to the written parts of the assignment. Your
solution can be hand-written, but must be legible. Graders may deduct marks for illegible or poorly presented solutions.
If you are using Jupyter Notebook to complete the work, your notebook can be exported as a .py file (File -> Download As -> Python). Your code will be auto-graded using Python 3.6, so please make sure that your code runs. There will be a 20% penalty if you need a remark due to small issues that renders your code untestable.
Make sure to remove or comment out all matplotlib or other expensive code before submitting your homework!
Submit the assignment on MarkUs by 9pm on the due date. See the syllabus for the course policy regarding late assignments. All assignments must be done individually.
import math
import numpy as np
Question 1.
Part (a) – 4 pt
Consider the problem of finding the roots of the functions f1, f2, f3 and f4. What is the (absolute) condition number of each problem?
1. f1(x)=sin( x ),atx=0 100
2. f2(x)=x3−5×2+8x−4,atx=2 3. f3(x)=xcos(20x)−x,atx=0
4. f4(x)=x3,atx=0
Include your solution in your PDF writeup. Show your work.
Part (b) – 6 pt
What is the convergence rate of each of the following sequences? Your answer should be either “linear”, “superlinear but not quadratic”, “quadratic”, “cubic”, or “something else”. Include your solution in your PDF writeup. Show your work.
1. xn = 10−2n 2. xn = 2−n2
3. xn = 2−nlogn
Question 2. Interval Bisection
Part (a) – 4 pt
Write a function bisect that returns a list of intervals where the root of the function f(x) lies. Each interval should be half the size of the previous, and should be obtained using the interval bisection method.
1

def bisect(f, a, b, n):
“””Returns a list of length n+1 of intervals where f(x) = 0 lies, where each interval is half the size of the previous, and is obtained using the interval bisection method.
Precondition: f continuous, a>> bisect(lambda x: x – 1, -0.5, 2, n=5)
[(-0.5, 2),
(0.75, 2),
(0.75, 1.375),
(0.75, 1.0625),
(0.90625, 1.0625),
(0.984375, 1.0625)]
“””
Part (b) – 4 pt
During lecture, we compared the following two computations of the midpoint between floating-point numbers a and b:
a=5
b = 5.1
mid1 = a + (b – a) / 2
mid2 = (a + b) / 2
Using a toy floating-point system, we saw in class that mid2 can be outside of the range of [a, b].
Use the same idea to construct two floating-point values float_a and float_b where (float_a + float_b) / 2 is not bewteen float_a and float_b. Recall that Python uses IEEE Double Precision for floating-point arithmetic
(i.e., round to even in base 2 with a mantissa of 53 bits).
Discuss how you arrived at the answer in your PDF writeup.
float_a = 0
float_b = 0
Part (c) – 2pt
Suppose you would like to use the interval bisection method to find the root of a function f(x), starting with an interval (a, b).
What is the minimum number of interval bisection iterations necessary to guarantee that your estimate of a root is accurate to 10 decimal places?
Include your solution in your PDF writeup.
Question 4. Fixed-Point Iteration
Part (a) – 4 pt
Write a function fixed_point to find the fixed-point of a function f by repeated application of f. The function should return a list of values [x, f(x), f(f(x)), …].
2

def fixed_point(f, x, n=20):
“”” Return a list lst = [x, f(x), f(f(x)), …] with `lst[i+1] = f(lst[i])` and `len(lst) == n + 1`
>>> fixed_point(lambda x: math.sqrt(x + 1), 3, n=5)
[3,
2.0,
1.7320508075688772,
1.6528916502810695,
1.6287699807772333,
1.621348198499395]
“””
Part (b) – 6 pt
To find a root of the equation
f(x)=x2 −3x+2=0
we can consider fixed-point problems involving the following different functions:
1. g1(x) = x2+2 √3
2. g2(x)= 3x−2 3. g3(x) = 3 − 2
x
Use the fixed_point function to generate the fixed-point iterations for each of these functions. Choose the starting valueofxtobex0 =3.
Does fixed-point iteration converge for each of the functions? Include the output of your call to fixed_point in your PDF writeup. If the iteration converges, what is the approximate the convergence rate of convergence? (linear, superliner, quadratic, etc).
Include your solution in your PDF writeup.
3