首页 >
> 详细

MA117 Programming for Scientists: Project 2 Deadline: 12pm, Friday 19th March 2021

1

MA117 Project 2: Root Finding

Administrative Details

• This project is the second of the three assignments required for the assessment in this course. It is to

be submitted by 12pm, Friday 19th March 2021. Details of the method of the submission via the Tabula

system have been described in the lecture notes and are also available on the course web page.

• This assignment will count for 35% of your total grade in the course.

• The automated submission system requires that you closely follow instructions about the format of

certain files; failure to do so will result in the severe loss of points in this assessment.

• You may work on the assignment during the lab session, provided you have completed the other tasks

that have been set. You can use the work areas at all times when they are not booked for teaching, 7

days per week. If you are working on the assignment on your home system you are advised to make

regular back-up copies (for example by transferring the files to the University systems). You should

note that no allowance will be made for domestic disasters involving your own computer system. You

should make sure well ahead of the deadline that you are able to transfer all necessary files to the

University system and that it works there as well.

• The Tabula system will be open for the submission of this assignment starting from 1st March 2021.

You will not be able to test your code for correctness using Tabula but you can resubmit your work

several times, until the deadline, if you find a mistake after your submission. A later submission always

replaces the older one, but you have to re-submit all files.

• Remember that all work you submit should be your own work. Do not be tempted to copy work; this

assignment is not meant to be a team exercise. There are both human and automated techniques to

detect pieces of the code which have been copied from others. If you are stuck, then ask for assistance

in the lab sessions. TAs will not complete the exercise for you, but they will help if you do not

understand the problem, are confused by an error message, need advice on how to debug the code,

require further explanation of a feature of Java or similar matters.

• If you have more general or administrative problems e-mail me immediately. Always include the course

number (MA117) in the subject of your e-mail.

1 Formulation of the Problem

Finding the roots of a function is a classical and extremely well-known problem which is important in many

branches of mathematics. In Analysis II, you have probably seen that it is often easy to prove results about

the existence of roots. For example, using the Intermediate Value Theorem, you should easily be able to

prove that the function 𝑓(𝑥) = 𝑥 − cos 𝑥 has a root in the interval [0,1]. On the other hand, calculating an

exact value for this root is impossible, since the equation is transcendental.

MA117 Programming for Scientists: Project 2 Deadline: 12pm, Friday 19th March 2021

2

Root finding is a classic computational mathematical problem, and as such there are many algorithms which

one may use to approximate the roots of a function. In this project, you will write a program which uses the

Secant algorithm. Let 𝑓 ∶ ℂ → ℂ be continuously differentiable and pick two points 𝑧0, 𝑧1 ∈ ℂ. Consider the

sequence of complex numbers {𝑧𝑛

}𝑛=1

∞ generated by the difference relation

𝑧𝑛+1 = 𝑧𝑛 − 𝑓(𝑧𝑛

)

𝑧𝑛 − 𝑧𝑛−1

𝑓(𝑧𝑛

) − 𝑓(𝑧𝑛−1)

.

Figure 1: An example of fractals for the function

𝑓(𝑧) = 𝑧

3 − 1 in the square with bottom left-corner −1 − 𝑖 and width 2.

Typically, if 𝑧𝑛 converges and lim𝑛→∞

𝑧𝑛 =: 𝑧∗

, then 𝑓(𝑧∗) = 0.

Some methods of finding the roots (Newton-Raphson) require knowing the derivative of 𝑓. Whilst there are

numerical tricks to accomplish this, this problem is somewhat beyond the scope of this course. Instead, you

will use the Secant method which does not require the derivative, however it does require two initial values.

We will consider a polynomial 𝑃 ∈ ℂ[𝑧]; i.e.

𝑃(𝑧) = 𝑎0 + 𝑎1𝑧 + 𝑎2𝑧

2 + ··· + 𝑎𝑛𝑧

𝑛

Where 𝑎𝑘 ∈ ℂ.

1.1 Secant Fractals

One of the most fascinating aspects of this problem arises from a very simple question: given two starting

positions 𝑧0, 𝑧1 ∈ ℂ, which root does the sequence produced by Secant converge towards? It turns out that

the answer to this question is very hard!

− 1 1

Re( z)

− 1

1

− 1 1

Re( z)

MA117 Programming for Scientists: Project 2 Deadline: 12pm, Friday 19th March 2021

3

Figure 1 shows two examples of how we might visualise this for the polynomial 𝑓(𝑧) = 𝑧

3 − 1. Recall that

the roots of this polynomial are 𝑎𝑘 = 𝑒

2𝜋𝑖𝑘

3 for 𝑘 = 1,2,3 (i.e. the third roots of unity). Each of the three

colours represents one of these roots. In the left-hand figure, we colour each point depending on which root

the method converges to. The right-hand figure is the same, asides from the fact that we make the colour

darker as the number of iterations it takes to get to the root within a tolerance 𝜀 increases. The resulting

images are examples of fractals, which you have undoubtedly seen before.

Don’t worry if all of this seems quite difficult – the main aim of the assignment is for you to successfully

implement the Secant scheme. Most of the code to deal with drawing and writing the images will be given

to you.

1.2 Summary

Your task then involves several distinct elements. You will:

• write a class to represent complex numbers;

• write a class to represent a polynomial in ℂ[𝑧];

• implement the Secant method to find the roots of the polynomial;

• investigate some interesting fractals and draw some pictures!

2 Programming instructions, classes in your code and hints

On the course web page for the project, you will find the following files, which should serve as templates and

should help you to start with the project. As with the previous projects, the files have some predefined

methods that are either complete or come with predefined names and parameters. You must keep all names

of public objects and methods as they are in the templates. Other methods have to be filled in and it is up

to you to design them properly. The files define three basic classes for your project:

• Complex.java: represents points 𝑧 ∈ ℂ;

• Polynomial.java: represents polynomials in ℂ[𝑧];

• Secant.java: given two initial Complex points 𝑧0, 𝑧1 close to the root calculate the corresponding

root of Polynomial by Secant, if possible;

• SecantFractal.java: will generate a fractal similar to the one pictured above in a square.

These classes are documented in more detail in the following sections. You should complete them in the

order of the following sections, making sure to carefully test each one with a main function.

2.1 Complex

Complex is the simplest of the classes you will need to implement and will represent complex numbers. In

fact, it bears a striking resemblance to the CmplxNum class you (hopefully) implemented in week 14.

They are not identical however, so you should carefully copy and paste your code into this new class.

MA117 Programming for Scientists: Project 2 Deadline: 12pm, Friday 19th March 2021

4

2.2 Polynomial

The Polynomial class is designed to represent a polynomial 𝑃(𝑧) = ∑ 𝑎𝑛𝑧

𝑁 𝑛

𝑛=0

. As such, it contains

coeff, an array of Complex coefficients which define it. It is assumed that coeff[0] corresponds to 𝑎0,

coeff[1] to 𝑎1 and so forth. To complete this class, you will have to:

1. Define appropriate constructors. There are two that need implementation; a default constructor

which initialises the polynomial to the zero polynomial (i.e. 𝑎0 = 0), and a more general constructor

which is passed an array of Complex numbers {𝑎0,𝑎1,… , 𝑎𝑁} which should be copied into coeff.

In addition, you should ensure that if any of the leading co-efficients are zero then they are not copied.

For example, if the constructor is passed the complex numbers {𝑎0, 𝑎1,0, 0} then it should

copy{𝑎0,𝑎1

} to coeff. (When testing for equality to zero, do not use any tolerances.)

2. Return the degree of the polynomial. Recall that 𝑑𝑒𝑔 𝑓 = 𝑁.

3. Evaluate the polynomial at any given point 𝑧 ∈ ℂ. Note that you should not implement a pow

function inside Complex as it is unnecessary and inefficient. Instead, notice that (for example)

𝑃(𝑧) = 𝑎0 + 𝑎1𝑧 + 𝑎2𝑧

2 + 𝑎3𝑧

3 = 𝑎0 + 𝑧[𝑎1 + 𝑧(𝑎2 + 𝑧𝑎3)].

∆z

Figure 2: A 5x5 pixel image representing the square with top left corner

−1 + 𝑖 and bottom right corner 1 − 𝑖. The centre of each pixel represents a

complex number on the plane.

2.3 Secant

This class will perform the Secant algorithm. There are two constants defined in this class:

• MAXITER: the maximum number of iterations to make; that is, you should generate the sequence 𝑧𝑛

for 0 ≤ 𝑛 ≤ MAXITER and no more.

• TOL: At each stage of the Secant algorithm, we must test whether a sequence converges to a limit. In

this project, we will say that 𝑧𝑀 approximates this limit if, at any stage of the algorithm, |𝑧𝑀 − 𝑧𝑀−1

| <

TOL . We then say that the starting points 𝑧0, 𝑧1 required 𝑀 iterations to converge to the root.

MA117 Programming for Scientists: Project 2 Deadline: 12pm, Friday 19th March 2021

5

Additionally, you will need to define the iterate function. This accepts two parameters, 𝑧0, 𝑧1, which defines

the initial condition of the Secant difference relation, and performs the root finding algorithm. There are

three things that can occur during this process:

• everything is fine and we converge to a root;

• the difference |𝑓(𝑧𝑛

) − 𝑓(𝑧𝑛−1

)| goes to zero during the algorithm;

• we reach MAXITER iterations.

If any of the last two cases occur, then you set the error flag err to be −1 and −2 respectively; otherwise, err

is set to zero. Here is a quick example of how Secant should be used:

Complex[] coeff = new Complex[] { new Complex(-1.0,0.0), new Complex(),

new Complex(), new Complex(1.0,0.0) };

Polynomial p = new Polynomial(coeff);

Secant n = new Secant(p);

n.iterate(new Complex(), new Complex(1.0, 1.0));

System.out.println(n.getRoot());

This will print out the root of 𝑓(𝑧) = 𝑧

3 − 1 obtained with the starting point 𝑧0 = 0, 𝑧1 = 1 + 𝑖.

2.4 SecantFractal

SecantFractal will be responsible for drawing images of the fractals we saw in figure 1. However, let us

briefly consider how images are represented on computer first. A two-dimensional image is, in general,

broken down into small squares called pixels. Each of these is given a colour, and there are generally many

hundreds of pixels comprising the width and height of the image.

An example of this can be seen in figure 2. This image (badly) represents a square in the complex plane with

top-left corner −1 + 𝑖 and bottom-right corner 1 − 𝑖. In SecantFractal you will generalise this concept

to visualise squares with a top-left corner origin and width width, stored as instance variables inside

SecantFractal. The image will be of size NUMPIXELS by NUMPIXELS. Each pixel can be accessed by using

an ordered pair (𝑗, 𝑘) where 𝑗 is the row number, 𝑘 the column number and (0,0) is the top left pixel, with

0 ≤ 𝑗, 𝑘 < 𝑁𝑈𝑀𝑃𝐼𝑋𝐸𝐿𝑆. The image itself will be generated using createFractal, which accepts a

single argument colourIterations. When true, the function generates a figure like the right-hand

side of figure 1.

To complete the class, first ensure that you call the setupFractal function at the end of your constructor.

This will initialise the more complex drawing objects. It also checks that the polynomial you have given it has

3 ≤ 𝑑𝑒𝑔 𝑝 ≤ 5 . You will not need to consider any other polynomials in this class. Then inside

createFractal, use the following logic:

1. Copy colourIterations to the instance variable.

2. Iterate over each pixel at position (𝑗, 𝑘). Then translate this position to a complex number using

pixelToComplex, which uses the simple mapping (𝑗, 𝑘) ↦ 𝑜𝑟𝑖𝑔𝑖𝑛 + Δ𝑧(𝑗 − 𝑖𝑘).

3. Use 0 and this complex number as the starting points to run through the Secant algorithm.

MA117 Programming for Scientists: Project 2 Deadline: 12pm, Friday 19th March 2021

6

4. Check to see whether you’ve found this root already. You will store the list of already found roots inside

the ArrayList roots. This is the purpose of the findRoot function. In this formulation, two

complex numbers 𝑧1 and 𝑧2 are equal if |𝑧1 − 𝑧2

| < Secant. TOL.

5. Finally, colour the pixel using the colourPixel function.

After you are done, you can save the image using saveFractal. Here is an example from start to finish,

which creates the two images of figure 1. Note that your filename should end with .png:

SecantFractal f = new SecantFractal(p, new Complex(-1.0,1.0), 2.0);

f.createFractal(false);

f.saveFractal("fractal-light.png");

f.createFractal(true);

f.saveFractal("fractal-dark.png");

You should then create a document which is precisely one page long. In this document, pick a polynomial

𝑃(𝑧), a square in the complex plane and use your program to generate the two plots. You should call this file

Fractal.pdf and ensure it is saved as a PDF file.

3 Submission

You should submit, using the Tabula system, the following four files: Complex.java,

Polynomial.java, Secant.java, SecantFractal.java and Fractal.pdf which contains

your plots.

There will be a large number of tests performed on your classes. This should allow for some partial credit

even if you don’t manage to finish all tasks by the deadline. Each class will be tested individually so you may

want to submit even a partially finished project. In each case, however, be certain that you submit Java files

that compile without syntax error. Submissions that do not compile will be marked down.

If you submit a code and later (before the deadline) you realise that something is wrong and you want to

correct it, you may do so. You can submit as many versions as you wish until the deadline. However, only the

last submission will be tested. Each new submission replaces the previous one, so in particular, you MUST

submit all files required for the project even if you corrected only a single file.

Keep back-up copies of your work. Lost data are not a valid excuse for missing the deadline.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Cs2461-10实验程序代做、代写java，C/C++，Python编程设 2021-03-02
- 代写program程序语言、代做python，C++课程程序、代写java编 2021-03-02
- Programming课程代做、代写c++程序语言、Algorithms编程 2021-03-02
- 代写csc1-Ua程序、代做java编程设计、Java实验编程代做 代做留学 2021-03-02
- 代做program编程语言、代写python程序、代做python设计编程 2021-03-02
- 代写data编程设计、代做python语言程序、Python课程编程代写 代 2021-03-02
- Cse 13S程序实验代做、代写c++编程、C/C++程序语言调试 代写留学 2021-03-02
- Mat136h5编程代做、C/C++程序调试、Python，Java编程设计 2021-03-01
- 代写ee425x实验编程、代做python，C++，Java程序设计 帮做c 2021-03-01
- Cscc11程序课程代做、代写python程序设计、Python编程调试 代 2021-03-01
- 代写program编程、Python语言程序调试、Python编程设计代写 2021-03-01
- 代做r语言编程|代做database|代做留学生p... 2021-03-01
- Data Structures代写、代做r编程课程、代做r程序实验 帮做ha 2021-03-01
- 代做data留学生编程、C++，Python语言代写、Java程序代做 代写 2021-03-01
- 代写aps 105编程实验、C/C++程序语言代做 代写r语言程序|代写py 2021-03-01
- Fre6831 Computational Finance 2021-02-28
- Sta141b Assignment 5 Interactive Visu... 2021-02-28
- Eecs2011a-F20 2021-02-28
- Comp-251 Final Asssessment 2021-02-28
- 代写cs1027课程程序、代做java编程语言、代写java留学生编程帮做h 2021-02-28