math

MTH 2001: Project 2

Instructions

• Each group must choose one problem to do, using material from chapter 14 in the textbook.

• Write up a solution including explanations in complete sentences of each step and drawings or computer graphics if helpful. Cite any sources you use and mention how you made any diagrams.

• Write at a level that will be comprehensible to someone who is mathematically competent, but may not have taken Calculus 3. Use calculus, but explain your method in simple terms. Your report should consist of 80−90% explanation and 10−20% equations. If you find yourself with more equations than words, then you do not have nearly enough explanation. See the checklist at the end of this document.

• One person from each group must present the work orally to Naveed or Ali. Presenters must make an appointment. Visit the Calc 3 tab: http://www.fit.edu/mac/group_projects_presentations.php

• Submit written work to the Canvas dropbox for Project 2 by October 7 at 9:55PM. The deadline for the oral presentation is October 7 at 2PM.

Problems

1. You probably studied Newton’s method for approximating the roots of a function (i.e. approximating values of x such that f(x) = 0) in Calculus 1:

(1) Guess the solution, xj

(2) Find the tangent line of f at xj,

y = f′(xj)(x−xj) + f(xj) (1)

(3) Find the tangent line’s x-intercept, call it xj+1,

0 = f′(xj)(xj+1 −xj) + f(xj) xj+1f

′(xj) = xjf ′(xj) −f(xj)

xj+1 = xj − f(xj)

f′(xj) (2)

(4) If f(xj+1) is sufficiently close to 0, stop, xj+1 is an approximate solution. Otherwise, return to step (2) with xj+1 as the guess.

See this animation for a geometric view of the process. It simply follows the tangent line to the curve at a starting point to its x-intercept, and repeats with this new x value until we (hopefully) find a good approximation of the solution.

Newton’s method can be generalized to two dimensions to approximate the points (x,y) where the surfaces z = f(x,y) and z = g(x,y) simultaneously touch the xy-plane. (In other words, it can approximate solutions to the system of equations f(x,y) = 0 and g(x,y) = 0.) Here, the method is

(1) Guess the solution (xj,yj)

(2) Find the tangent planes to each f and g at this point.

z = f(x,y) =

z = g(x,y) =

(3) Find the line of intersection of the planes.

(4) Find the line’s xy-intercept, call this point (xj+1,yj+1),

xj+1 =

yj+1 =

(5) If f(xj+1,yj+1) < ε and g(xj+1,yj+1) < ε for some small number ε (error tolerance), stop, (xj+1,yj+1) is an approximate solution. Otherwise, return to step (2) with (xj+1,yj+1) as the guess.

(a) Find equations of the tangent planes for step (2), an equation for their line of intersection for step (3), and find formulas for xj+1 and yj+1 for step (4).

(b) What assumptions must we make about f and g in order for the method to work? How might the method fail? Explain in words how the method works.

For the following parts of the problem, it is recommended to use a spreadsheet or write some code.

(c) Use the method to approximate the solutions to the system of equations

(x− 1) cos(x− 1) + (y − 1) cos(y − 1) = 3

4

(x−π)2 + (y −π)2 = 8

In other words, find the intersections of the blue and orange curves.

(d) Use the method to approximate the location of the critical points of f(x,y) = 10x2y−5x2−4y2− x4 − 2y4 given its contour map,

For each of the critical points, use enough steps in Newton’s method to approximate the their locations such that the partial derivatives at the approximation have absolute values below 10−4.

2. One method for finding extreme values of a function f of two (or more) variables is gradient descent (or ascent). The idea is to guess a point in the domain that could be a minimum, and follow a certain

path in the domain to reach a much more precise approximation of the location of a minimum. In order to do this, we find the direction of steepest decline, take a small step in that direction, and repeat over and over until we reach what seems to be a minimum.

The method would look like the following on a contour map (i.e. taking the most direct path between level curves).

Gradient ascent uses the same idea to find maxima, but follows the steepest incline rather than decline.

(a) Assuming we are able to find partial derivatives of f, use ideas from §14.6 to write down the steps for carrying out a gradient descent strategy. How can we know when to stop (i.e. how do we know if we have reached a minimum)? What is different for the method of gradient ascent?

[Hint. The inputs to our method will be f, its partial derivatives, and a point in the domain we guess is a minimum.]

(b) Suppose we have function f with continuous partial derivatives, but we are not able to calculate them. How can we modify the process in part (a) so that it can still work? (How could we determine in which direction f has a steepest decline without the partial derivatives?)

(c) Suppose our method converges to a relative minimum that is not an absolute minimum. How can we check to see if there are other minima?

(d) Use a gradient ascent method to find the 3 maxima for part (d) of problem 2 above.

(e) Use a gradient descent and ascent method to approximate the absolute minimum and maximum of f(x,y) = sin x sin y

(xy)2+1 where −2π ≤ x ≤ 2π, −2π ≤ y ≤ 2π. Below is f on the domain, with red

colors corresponding to high points and blue colors low points.

3. You are the Duke of Wellington and are charged, by his high and most exalted holiness the emperor of Egghead, to help settle an age old border dispute with the neighboring state, Bufoonia. Between your two states is a no mans land that you need to determine how to most equitably share between Egghead and Bufoonia. Representing Bufoonia is your arch rival and nemesis the Arch Duke of Strong Island. The existing borders of Egghead are determined by the following set of inequalities:

x + 2y + z ≥ 3 0 ≤ x ≤ 2, 0 ≤ y ≤ 2, 0 ≤ z ≤ 2

The Arch Duke of Strong Island has furnished you with his own border specifications:

4x + 3y + 6z ≥−12 −3 ≤ x ≤ 0,−4 ≤ y ≤ 0,−2 ≤ z ≤ 0

Note: I suggest reading sections 5.1.1, 5.1.2, 5.2.1 (about 3 pages with pretty large font) of Convex Optimization by Boyd and Vandenberghe (available for free download from authors here: https: //web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf) before you start to get a different perspective on the problem.

(a) Plot, in 3D, these borders and give at least 2 views showing the separation of the states. Re- member, the states are formed by the regions enclosed by the given planes. You may use the MATLAB code provided to do this.

(b) Find a plane, passing through (0, 1 2 , 2) that separates Egghead and Bufoonia. Is there more than

one such plane? Why? This is the border that the Arch Duke of Strong Island (your nemesis) wants.

(c) Find a plane, passing through (0, 0, 0) that separates Egghead and Bufoonia. Is there more than one such plane? Why? This is the border that your rival and foe, the Arch Duke of Strong Island, thinks you want (he is, after all, a Bufoon).

(d) Find a plane that strictly separates the two states. That is, find a vector a =< a1,a2,a3 > and a scalar γ such that a1x + a2y + a3z > γ for all (x,y,z) ∈ Egghead and a1x + a2y + a3z < γ for all (x,y,z) ∈ Bufoonia. Make a valid mathematical argument for why the plane you find is the best such separating plane. Hint: the vector a and scalar γ must satisfy

max (x,y,z)∈Bufoonia

a1x + a2y + a3z < γ < min (x,y,z)∈Egghead

a1x + a2y + a3z

(e) Offer an interesting back story that outlines how you, the Duke of Wellington, and your nemesis, the Arch Duke of Strong Island, came to be rivals.

(f) Note: There are two additional MATLAB files provided with the project document to serve as a guide to plotting the required regions. Feel free to port these to other languages / tools if you wish. If you do, please submit the code in your written project document.

References

[1] Wolfram Alpha http://www.wolframalpha.com

[2] Plotting 3D in MATLAB http://www.mathworks.com/help/matlab/2-and-3d-plots.html [3] Google http://www.google.com

Project Document Checklist Checklist for writing projects. Based on checklists by Annalisa Crannell and Franklin & Marshall and Tommy Ratliff at Wheaton College, Does this paper:

1. clearly (re)state the problem to be solved?

2. provide an explanation as to how the problem will be approached?

3. state the answer in a few complete sentences which stand on their own?

4. Give a precise and well-organized explanation of how the answer was found?

5. clearly label diagrams, tables, graphs, or any other visual representations of the math?

6. define all variables, terminology, and notation used?

7. clearly state the assumptions which underlie the formulas and theorems, and explain how each formula or theorem is derived or where it can be found?

8. give acknowledgement where it is due?

9. use correct spelling, grammar, and punctuation?

10. contain correct mathematics?

11. solve the questions that were originally asked?