本次Java代写是解决牛顿分形等问题

MA117 Project 2: Root Finding

Administrative Details

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 f(x) = x − cos x 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.

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 Newton-Raphson algorithm. Let f : C → C be continuously differentiable, and pick a

point z0 ∈ C. Consider the sequence of complex numbers {zn}∞

n=0 generated by the difference relation

zn+1 = zn −

f(zn)

f

0(zn)

.

Typically, if zn converges and limn→∞ zn =: z∗, then f(z∗) = 0.

1

MA117 Programming for Scientists: Project 2 Deadline: Noon, Monday 16th March 2020

−1 1

Re (z)

−1

1

Im (z)

−1 1

Re (z)

Figure 1: An example of Newton fractals for the function f(z) = z

3 − 1 in the square with bottom

left-corner −1 − i and width 2.

In general then, to apply Newton-Raphson, one must know the derivative of f. Whilst there are

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

then, you will consider a polynomial P ∈ C[z]; i.e.

P(z) = a0 + a1z + a2z

2 + · · · + anz

n

where ak ∈ C. P has a (hopefully obvious!) exact derivative.

1.1 Newton Fractals

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

position z0 ∈ C, which root does the sequence produced by Newton-Raphson converge towards? It

turns out that the answer to this question is very hard!

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

3 − 1. Recall

that the roots of this polynomial are αk = e

2πik/3

for k = 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 Newton-Raphson 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 C[z];

• implement the Newton-Raphson method to find the roots of the polynomial;

• investigate some interesting fractals and draw some pictures!

2

MA117 Programming for Scientists: Project 2 Deadline: Noon, Monday 16th March 2020

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 defines three basic classes for

your project:

• Complex.java: represents points z ∈ C;

• Polynomial.java: represents polynomials in C[z];

• Newton.java: given an initial Complex point z0 calculates the corresponding root of Polynomial

by Newton-Raphson, if possible;

• NewtonFractal.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 resemblence 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.

2.2 Polynomial

The Polynomial class is designed to represent a polynomial P(z) = PN

n=0 anz

n

. As such, it contains

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

a0, coeff[1] to a1 and soforth. 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. a0 = 0), and a more general constructor

which is passed an array of Complex numbers {a0, a1, . . . , aN } 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 {a0, a1, 0, 0} then

it should copy {a0, a1} to coeff. (When testing for equality to zero, do not use any tolerances.)

2. Return the degree of the polynomial. Recall that deg f = N.

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

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

P(z) = a0 + a1z + a2z

2 + a3z

3 = a0 + z(a1 + z(a2 + za3)).

2.3 Newton

This class will perform the Newton-Raphson algorithm. There are two constants defined in this class:

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

zn for 0 ≤ n ≤ MAXITER and no more.

• TOL: At each stage of the Newton-Raphson algorithm, we must test whether a sequence converges

to a limit. In this project, we will say that zM approximates this limit if, at any stage of the

3

MA117 Programming for Scientists: Project 2 Deadline: Noon, Monday 16th March 2020

∆z

Figure 2: A 5×5 pixel image representing the square with top left corner −1 + i and bottom right

corner 1 − i. The center of each pixel represents a complex number on the plane.

algorithm, |zM − zM−1| < TOL. We then say that the starting point z0 required M iterations to

converge to the root.

Additionally, you will need to define the iterate function. This accepts a single parameter, z0, which

defines the initial condition of the Newton-Raphson 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 derivative f

0

(zk) 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 Newton 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 );

Newton n = new Newton (p);

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

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

This will print out the root of f(z) = z

3 − 1 obtained with the starting point z0 = 1 + i.

2.4 NewtonFractal

NewtonFractal 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 + i and bottom-right corner 1 − i. In NewtonFractal you will generalise

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

variables inside NewtonFractal. The image will be of size NUMPIXELS by NUMPIXELS. Each pixel can be

accessed by using an ordered pair (j, k) where j is the row number, k the column number and (0, 0) is

the top left pixel, with 0 ≤ j, k < NUMPIXELS. The image itself will be generated using createFractal,

which accepts a single argument colorIterations. When true, the function generates a figure like

the right hand side of figure 1.

4

MA117 Programming for Scientists: Project 2 Deadline: Noon, Monday 16th March 2020

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 ≤ deg p ≤ 5. You will not need to consider any other polynomials in this

class. Then inside createFractal, use the following logic:

1. Copy colorIterations to the instance variable.

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

pixelToComplex, which uses the simple mapping (j, k) 7→ origin + ∆z(j − ik).

3. Run this complex number through the Newton-Raphson algorithm.

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 z1 and z2 are equal if |z1 − z2|< Newton.TOL.

5. Finally, colour the pixel using the colorPixel 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:

NewtonFractal f = new NewtonFractal (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

P(z), 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.

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** [email protected] **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。