Analytical and Computational Foundations Coursework 1: Iterative methods
CW1-ACF
CW1-ACF November 21, 2022
Coursework 1 - ACF (2022-23)
This question is associated with the core module Analytical and Computational Foundations (ACF). 1.0.1
Marks
• There are 3 subquestions, a) and b) are worth 30 marks and c) is worth 40 marks. • The number of marks asssociated with test-cell is indicated in a comment at the top of that cell. • The number of marks associated to a manually marked taks. (like drawing a graph) is indicated in the text immediately above this cell.
How to Answer Write your code in the “answer” cell where it says “# YOUR CODE HERE” and remove both the line “# YOUR CODE HERE” and the line “raise NotImplementedError()”
Important: Do not change the name or remove the existing function and write all your code “inside” the existing function, i.e. with at least one-tab’s indentation.
When you have written your code you should evaluate the cell and then evaluate the “Test” cells following it. If you don’t see any errors then your code is (hopefully) correct and you can go on to the next question.
If you see some errors then you have to go back and edit your code and try to fix the “bug”.
1.1 Introduction
Iterative methods are sometimes useful for finding solutions to certain equations, for instance square-roots and cube roots etc. One early example of such a method was discovered by the ancient Babylonians, who discovered that for a given positive real number a and some real number x0 the sequence xn defined by will approximate the square-root of a, i.e. |x2n − a| → 0 as n → ∞. In this problem we will implement a version of this which instead computes the cube-root of a positive real number a using the iterative sequence where x0 is an arbitrary positive real number. Successive values are computed for xn until the desired level of accuracy is reached. Hence, if we desire the maximum error to be e, we stop when n = N , where
(Note that this in general larger than the “true” error estimate |xN − 3 a| but is much easier to test for and we leave the details of such error analysis to a later course.) a) [30 marks] Write a Python function called ‘cube_root’ that - Takes as input three numbers a, e and x0 .
- Uses “assert” to assert that a, e and x0 are positive numbers. - Uses the iterative sequence
above to estimate 3 a with maximum error e. - Returns the tuple (xN , N ) where xN is the sought
approximation.
def cube_root(a,e,x0): # YOUR CODE HERE raise NotImplementedError()# [5 marks] from nose.tools import assert_equal # Check that the function returns a tuple assert_equal(type(cube_root(2.0,1e-10,1)),tuple)# [5 marks] from nose.tools import assert_equal # This cell contains hidden tests# [5 marks] from nose.tools import assert_almost_equal # Check that we return sqrt(2) if we start with 1 assert_almost_equal(cube_root(2.0,1e-10,1)[0],1.259921049894873,delta=1e-8)# [5 marks] from nose.tools import assert_almost_equal # check that we return sqrt(2) also for starting with 3 assert_almost_equal(cube_root(2.0,1e-10,3)[0],1.259921049894873,delta=1e-8)# [5 marks] from nose.tools import assert_almost_equal # This cell contains hidden tests# [5 marks] from nose.tools import assert_raises import math assert_raises(AssertionError,cube_root,-2,1e-10,1)
b) [30 marks] Write a modified function that returns the whole list of approximations [x0 , x1 , x2 , . . . , xn ].
def cube_root_list(a,e,x0):
# YOUR CODE HERE
raise NotImplementedError()# [5 marks]
from nose.tools import assert_equal,assert_almost_equal
# Check that the function returns a list
assert_equal(type(cube_root_list(2.0,1e-10,1)),list)# [5 marks]
from nose.tools import assert_equal
## Check that the first element is the initial element
assert_almost_equal(cube_root_list(2.0,1e-10,1)[0],1.0,delta=1e-8)# [5 marks]
from nose.tools import assert_equal,assert_almost_equal
# Check that the last element in the list is a good approximation
assert_almost_equal(cube_root_list(2.0,1e-10,1)[-1],1.
,→259921049894873,delta=1e-8)# [5 marks]
from nose.tools import assert_equal,assert_almost_equal
# This cell contains hidden tests# [5 marks]
from nose.tools import assert_equal,assert_almost_equal
# This cell contains hidden tests# [5 marks]
from nose.tools import assert_equal,assert_almost_equal
# This cell contains hidden testsc)[40 marks] Use the function from part b) to compute a list of approximations (xn ) to 3 20000 and use pylab to plot the points xn against n as a scatterplot and in the same plot also add a horizontal red line corresponding to the value given by math.sqrt(20000) as well as appropriate legends for the plot and labels for the x and y axes. - Insert the code for drawing the plot in the function draw_plot below. - Generate the plot in the cell below by calling the function draw_plot. Note: If you didn’t complete the previous part you can use the following list of values for cube_root_list(20000,1e-10,1):
[1, 6667.333333333333, 4444.889038858893, 2963.259696671749, 1975.5072236707565, 1317.006524030
import pylab
def draw_plot(a):
data = cube_root_list(a,1e-10,1)
# YOUR CODE HERE
raise NotImplementedError()# YOUR CODE HERE
raise NotImplementedError()
