Math 104A Computation Homework # 1
1 Main problem
Obtain a fifigure following the instructions. I recommend setting n = 3 to begin with. After you fifinish
programming, you may change it and enjoy other fifigures. The equation x
n
= 1 has n solutions in the
complex plane zk = e
2kπ
n i
= cos(
2kπ
n ) + isin(
2kπ
n ), (k = 0, 1, · · · , n n 1). Newton’s method can be used fifind
roots of complex functions and this homework does so. But you don’t need to do anything new. Just plug
complex numbers into the method when you evaluate f(xn) and f
0
(xn), where xn is a complex number.
That will fifind you a root of f(x) as a complex function. Newton’s method can spot a solution, but we don’t
know which one. That depends on the initial guess. You are going to color the complex plane according
to which solution an initial value leads to using Newton’s method.
Choose a square domain around the origin, and determine a grid resolution so that a matrix stores the
grid points of your domain for initial guesses.
Run Newton’s method to approximate a solution to the equation above with the initial guess x0 being
each of the grid point of your domain. If it turns out to converge to z1, color a small area near the grid
point of the initial guess, say, red. If the initial guess leads to z2, color a small area near the point with a
difffferent color, say, green. If the initial guess leads to z3, color a small area near the point with another
color, say, blue. You may end up getting something weird, say NaN. To treat such abnormalities all at
once, color a small area near your initial guess, say black, for all other cases.
You will have to make various decisions along the way. I have deliberately minimized the instructions
so you can enjoy the process of creating your own program. So, give it shot right away if you believe
you have enough programming experience. But if you are not very confifident with programming, feel
free to consult the tips below to avoid headache.
(Summary)
data
– n ≥ 3 (power of the equation; 3 is recommended to begin with)
output
– img.pdf: a color plot of a domain around the origin. Each difffferent color indicate that if Newton’s
method starts nearby, the method converges to the same zero, or something weird has occurred.
recommended intermediate data (You don’t have to follow these, but they can make things easier. In
particular, the plotting tips assume that you have generated the matrix CC below.)
– ZZ (a complex matrix/array of a grid domain around 0. Each entry serves as an initial guess for the
Newton’s method)
1– CC: a matrix for color plot. If (i, j)–entry of ZZ leads to a convergence to zk , (i, j)–entry of CC is k
(k = 0, 1, · · · , n n 1). If (i, j)–entry of ZZ leads to any other result, (i, j)–entry of CC is n).
– The names of variables ZZ and CC can be arbitrary. But it will enhance the readability of the code.
? Submission: submit the following on GauchoSpace (click on ‘Computation HW1’).
– Your source code (.m, .py, or .ipynb)
– A fractal image fifile (.pdf)
– (optional) A text fifile describing reflflection (.txt). For example, you can share what you struggled
with, how you overcame it, what you newly learned, etc. This may bump up the grade if the result
is not ideal.
2 Tips for plotting
Below, the variable names are assumed to be as follows:
- CC: the matrix as explained above (see the “recommended intermediate data”)
- xmin, xmax: the minimum and maximum of real part of your domain respectively
- ymin, ymax: the minimum and maximum of imaginary part of your domain respectively
(Matlab) Add the following block of code at the end of your main body of code.
figure;
map = [1 0 0; 0 1 0; 0 0 1; 0 0 0]; % [red; green; blue; black]
colormap(map);
image([xmin,xmax], [ymin,ymax], CC);
axis equal; axis tight;
saveas(gcf,‘img.pdf’);
(Python) Add the following block of code at the top of your code:
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
And add the following block of code at the end of your main body of code:
map = [’r’, ’g’, ’b’, ’k’]
cmap = ListedColormap(map)
plt.imshow(CC, cmap=cmap, extent=(xmin, xmax, ymin, ymax))
plt.savefig("img.pdf", format="pdf", bbox inches="tight")
plt.show()
(Python in colab) You can google ’colab’ and use the Jupyter lab environment offffered. However,
to download the fractal image fifile, you will need to add the following block of code at the end in
addition to the above.
2from google.colab import files
files.download(’img.pdf’)
3 Tips for programming
If you haven’t developed your own programming practice, you may want to consider the following.
Do ‘unit test,’ meaning, test each independent functionality separately so that you better know
where bugs are. For example, to make sure your plotting block has no issue, create a small matrix
CC manually and run the plot part before you really compute and plot the fractal. Another example
is to test whether your function of interest f(x) and f
0
(x) (you must determine these) give the
correct values for some known inputs.
(Anonymous function) To construct Newton’s method for a zero of f(x), you will need to specify
f(x) and f
0
(x). For example, if you want to evaluate the function f(x) = 2x
5
+ 3x many times, you
may want one of the the following lines:
– (Matlab) f = @(x) 2*x?5 + 3*x;
– (Matlab vectorized version) f = @(x) 2*x.?5 + 3*x;
– (Python - vectorized by default) f = lambda x: 2*x**5 - 3*x
Vectorize your code. For example, for Matlab, use pointwise operation .*, ./, .? etc whenever
possible to conduct computation in a parallel way rather than use for loop. (The parallelization is
done internally in Matlab.) For Python, I believe the pointwise operation is usually done by default,
say for numpy objects. If this does not make much sense, you may skip this part for the moment.
But your computation can be slow.
If you use Python, you will need to import numpy package to deal with matrices.
Google it if you don’t know something. It is also my teacher. You may feel like you can do
whatever you want.