MACM 316 - Assignment 7 Please read the Guidelines for Assignments first. Submit a one-page PDF report to Canvas and upload you Matlab scripts (as m-files). Do not use any other file formats. Keep in mind that Canvas discussions are open forums. Acknowledge any collaborations and assistance from colleagues, TAs, instructors etc. Monte Carlo Integration As we have seen in class, integrating a function of one variable numerically is relatively straightforward. On the other hand, integrating multivariate functions can be substantially harder, especially when the dimension is high or the domain is complicated. Monte Carlo integration is an extremely powerful technique for integrating multivariate functions. In two dimensions, let f (x, y) be a function defined on a square [x1 , x2 ] [y1 , y2 ]. In Monte Carlo integration, one draws N pairs (x(1) , y (1) ), (x(2) , y (2) ), . . . , (x(N ) , y (N ) ), at random, where the x(i) 's are uniformly distributed in [x1 , x2 ] and the y (i) 's are uniformly distributed in [y1 , y2 ], and computes the approximation Z y2 Z N x2 f (x, y) dx dy y1 x1 (x2 x1 )(y2 y1 ) X f (x(i) , y (i) ). N i=1 As N increases, one expects the approximation error to decrease. One interesting application of Monte Carlo integration is in computing the areas of shapes. Let be a subset of a square [x1 , x2 ] [y1 , y2 ]. Then the area of can be expressed as the integral Z y2 Z x2 Area() = f (x, y) dx dy, y1 x1 where f (x, y) is the function that takes value +1 when (x, y) and 0 otherwise. Hence we can approximate the area using Monte Carlo integration as Area() where M = PM i=1 f (x (i) , y (i) ) (x2 x1 )(y2 y1 ) M, N counts the number of pairs (x(i) , y (i) ) which lie within . Your goal in this assignment is to investigate Monte Carlo integration for computing areas. The two areas which you will be computing are the following: (i) The Lemniscate region. This is defined by the condition (x, y) if 12 (x2 y 2 ) < (x2 +y 2 )2 < 2(x2 y 2 ). (ii) The Mandebrot set. Unlike the previous region, this has no simple definition. To compute it, you should download the Matlab function InMSet.m. This function takes a pair (x, y) as input, and outputs the value +1 when (x, y) and 0 otherwise. 1 0.6 1 0.4 0.5 0.2 0 0 -0.2 -0.5 -0.4 -0.6 -1.5 -1 -1 -0.5 0 0.5 1 1.5 -1.5 Lemniscate -1 -0.5 0 0.5 Mandelbrot In both cases, choose a range of values of N , compute the corresponding approximations and errors, and plot the errors versus N using suitable axes. Remember: use as big values of N as you reasonably can in order to get good plots, and pick your axes appropriately. Comment on the apparent accuracy of Monte Carlo integration and its efficiency. Note: in order to compute the error, you need to know the exact areas. The Lemniscate has area 1.5. Unfortunately the exact area of the Mandelbrot set is unknown, but you may use the approximate value 1.506591884. 2