Instructions:   Compress  all your  codes  and  the project  report  (in  PDF format)  into  a single zip  or tarball,  and submit it to  Canvas .   The report must be typeset using LaTeX or WORD, with answers to all questions .  Include sufficient comments in your codes .  Feel free to include  any additional discussions that you want to make .  Note that this is not a group project and an honor code pledge must be included in the submitted report.

1. Linear least squares. Suppose we need to fit an ellipse to a set of points {(xi, yi)} . This can be achieved by fitting the quadratic curve

x2 + Ay2 + Bx + Cy + D = 0

to these data points, where A, B, C, D are fitting parameters to be found.  For sim- plicity, we do not consider tilted ellipses.

(a) Formulate a linear least squares problem to determine A, B, C, D .  The ellipse equation can also be written as

(x − x0 )2         (y − y0 )2

a2                       b2                  ,

where (x0 , y0 ) is the center and a and b are the semi axes of this ellipse. Derive formulas to compute x0 , y0 , a, b from A, B, C, D .  You will need these formulas for your code in (b).

(b)  Develop a function ellipse .m to compute the ellipse fit. The linear least squares problem should be solved by normal equations or QR factorization.  If you use the normal equations, you may use the code that you have developed in project 1 to solve the SPD system. If you use QR factorization, you will need to develop a code to compute the QR factorization using a method that you learn in this course. You are not allowed to use left divide or other advanced matlab functions to solve the least squares problem or the linear system.Your function should have the following format. Attach the code to your report.

function  [a,b,x0,y0]=ellipse(xi,yi)

%  Ellipse  fit  by  linear  least  squares .

%  input

%     xi,yi      -     vectors  for  x  and  y  coordinates  of  the  data  points

%  output

%      a,b .        -  semi  axes  of  the  ellipse

%     x0,y0      -  center  of  the  ellipse

xi=xi(:);

yi=yi(:);  %  transform  the  input  vectors  into  column  vectors . . .  the  rest  of  your  code  starts  here

(c)  Test the function with some points from an ellipse of your own choice.  Include the results in the report.

(d)  The data file points .dat contains two columns for the x and y coordinates of 20 points. Write a script file to compute the ellipse fit using your function ellipse and plot the ellipse fit (as a solid curve) together with the given data points (as symbols). Attach the plot to your report.

2. Nonlinear least squares. The ellipse fitting can also be obtained by directly fitting

(x − x0 )2         (y − y0 )2

a2                       b2

to the data points, where a, b, x0 , and y0  are now the fitting parameters.  This will result in a nonlinear least squares problem.

(a)  Theoretical preparation.   Find the vector-valued function F and its Jacobian matrix J for this nonlinear least squares problem.  Describe how to solve this problem using the Gauss-Newton method.  You will need these to develop the code in (b).

(b)  Develop a function ellipse nonlin .m to compute the ellipse fit using the Gauss- Newton method. You may stop the iteration when ek  = |c(k − c(k − 1)|2  < 10 − 10 , where c = [a, b, x0 , y0]T  is the vector of fitting parameters. Your function should have the following format. Attach the code to your report.

function  [a,b,x0,y0]=ellipse_nonlin(xi,yi)

%  Ellipse  fit  by  nonlinear  least  squares .

%  input

%     xi,yi      -     vectors  for  x  and  y  coordinates  of  the  data  points

%  output

%      a,b .        -  semi  axes  of  the  ellipse

%     x0,y0      -  center  of  the  ellipse

xi=xi(:);

yi=yi(:);  %  transform  the  input  vectors  into  column  vectors

. . .  the  rest  of  your  code  starts  here

(c) Use your code to compute the ellipse fit for the data points in points .dat. Keep track of convergence history and complete the following table until convergence. You may add more columns if you feel appropriate.