Mathematics

Summer 2021: Numerical Analysis
Assignment 1 (due July 12, 2021 at 11am ET)
Homework submission. Homework assignments must be submitted through Gradescope. Please
hand in cleanly handwritten or typed (preferably with LATEX—I will provide the source files of these
assignments if you want to use them to learn LATEX) homeworks. If you are required to hand in code
or code listings, this will explicitly be stated on that homework assignment.
Collaboration. NYU’s integrity policies will be enforced. You are encouraged to discuss the
problems with other students on Campuswire. However, you must write (i.e., type) every line of
code yourself and also write up your solutions independently. Copying of any portion of someone
else’s solution/code or allowing others to copy your solution/code is considered cheating.
Plotting and formatting. Plot figures carefully and think about what you want to illustrate with
a plot. Choose proper ranges and scales (semilogx, semilogy, loglog), always label axes, and
give meaningful titles. Sometimes, using a table can be useful, but never submit pages filled with
numbers. Discuss what we can observe in and learn from a plot. Use format compact and other
format commands to control MATLAB’ outputs. When you create figures in MATLAB (or Python),
please export them in a vector graphics format (.eps, .pdf, .dxf) rather than raster graphics or
bitmaps (.jpg, .png, .gif, .tif). Vector graphics-based plots avoid pixelation and thus look much
cleaner.
Programming. This is an essential part of this class. We will use MATLAB for demonstration
purposes in class, but you are free to use other languages (Python, Julia). Basic programming skills
are crucial for many jobs, so this is also a good chance to get more comfortable with it, if you aren’t
already. In your programs, please use meaningful variable names, try to write clean, concise and
easy-to-read code and use comments for explanation.
1. [5pt] We search for solutions in [1, 2] to the equation
x
3 − 3x
2 + 3 = 0.
(a) Compute the first iterates x0, . . . , x5 of the secant method in [1, 2].
(b) Compute the first iterates x0, . . . , x5 using Newton’s method with starting value x0 = 1.5.
(c) Compute the first iterates using Newton’s method with starting value x0 = 2.1. Sketch the
equation graph and try to explain the behavior.
2. [10pts] In this problem, you will prove the rate of convergence for the secant method.
(a) Show that the secant method
xk+1 = xk −
xk − xk−1
f(xk) − f(xk−1)
f(xk)
can be rewritten in the form:
xk+1 =
xkf(xk−1) − xk−1f(xk)
f(xk−1) − f(xk)
. (1)
1(b) Now, denote the root of f to be ξ, so that f(ξ) = 0. Also assume that f is twice continuously
differentiable and that f
0 > 0 and f
00 > 0 in a neighborhood of ξ. Define the quantity ψ to
be:
ψ(xk, xk−1) = xk+1 − ξ
(xk − ξ)(xk−1 − ξ)
,
where xk+1 is as in (1). Compute (for fixed value of xk−1)
ϕ(xk−1) = lim
xk→ξ
ψ(xk, xk−1).
(c) Now compute
lim
xk−1→ξ
ϕ(xk−1),
and therefore show that
lim
xk,xk−1→ξ
ψ(xk, xk−1) = f
00(ξ)
2f
0(ξ)
.
(d) Next, assume that the secant method has convergence order q, that is to say that
lim
k→∞
|xk+1 − ξ|
|xk − ξ|
q
= A < ∞.
Using the above results, show that q − 1 − 1/q = 0, and therefore that q = (1 + √
5)/2.
(e) Finally, show that this implies that
lim
k→∞
|xk+1 − ξ|
|xk − ξ|
q
=

f
00(ξ)
2f
0(ξ)
q/(1+q)
.
3. [5pt] Consider the following ordinary differential equation (ODE):
du
dt = g(u).
To solve this numerically, you can use the backward Euler method, for some time step ∆t > 0
(we will talk about this later in the semester):
u
n+1 − u
n
∆t
= g(u
n+1).
The numerical result from this process is the sequence u
0
, u1
, u2
, . . ., which can be interpreted as
an approximation to the exact solution sampled at times 0, ∆t, 2 ∆t, . . ..
(a) If g(u) = au for some a < 0, derive a formula for u
n+1 as a function of u
n
.
(b) If g(u) is a general nonlinear function and is differentiable, write down an iteration which
determines u
n+1 from Newton’s method.
(c) The convergence of Newton’s method depends on the choice of the initial guess. What
would be a sensible choice for an initial guess?
4. [5pt] Raytracing is an algorithm that involves finding the point at which a ray (a line with a
direction and an origin) intersects a curve or surface. We will consider a ray intersecting with an
ellipse. The general equation for an ellipse is
x
α
2
+

y
β
2
− 1 = 0
2and the equation for a ray starting from the point P0 = [x0, y0] in the direction V0 = [u0, v0], is
R(t) = [x0 + tu0, y0 + tv0]
where t ∈ [0, ∞) parameterizes the ray. In this problem we will take α = 3, β = 2, P0 = [0, b],
V0 = [1, −0.3]. Using your favorite root finding algorithm write a code which computes the
intersection of the given ray and the ellipse and plot your results. .
(a) Plug the equation for the ray, R(t), into the equation for the ellipse and analytically (with
pen and paper) solve for the value of t which gives the point of intersection, call it ti
.
(b) Perform the same calculation numerically using your favorite root finder. Report your answer
to within an error of 10−6
and justify how you found the minimum number of iterations
required to achieve this tolerance. Also report the point of intersection Pi = R(ti)