Edit or run this notebook

Final exam for CS 4220 / Math 4260 / CS 5223

Due date: 2022-05-18

This is meant to be straightforward based on the course notes and previous assignments, but you can (and should) consult any resources you wish except for people outside the course staff. Provide attribution (e.g. a citation or link) for any ideas you get. Your final write-up should be your own.

You should do problem 1, and any four out of the remaining five problems. Please indicate which four of the remaining five problems you want graded.

279 μs
243 μs
2.9 s

1. Snacks (5 points)

  1. (1 pt) Give an example of a 1D polynomial root-finding problem p(x)=0 where Newton converges, but not quadratically.

  2. (1 pt) Given a square nonsingular A with A=QR, how would you solve Ax=b in O(n2)?

  3. (1 pt) Given data x1,,xnR, write a simple formula for the minimizer y of ϕ(y)=12j=1n(yxi)2.

  4. (2 pt) Let ϕ(x)=cTB(x)1b where B(x)=A+diag(x). Starting with F = lu(A+diagm(x)), write code to compute ϕ(x) and ϕ(x) in O(n2) additional cost.

1.4 ms

2. Hanging cables (10 points)

Consider cable of length 2L strung between poles at positions x=±t and y=0 where t=Ld. The hanging cable takes the shape of a catanery:

y(x)=β1(cosh(βx)1)h.

Here β is an (unknown) shape parameter and h is how far down the catanery hangs at the midpoint x=0. The constraint that the length remains 2L gives us

Lβ=sinh(tβ)

where t=Ld. It will be convenient to rewrite this in terms of v=tβ; a couple options are

Lv=tsinh(v)L(sinh(v)v)=dsinh(v)

Hyperbolic trig identities let us rewrite the end constraint y(t)=0 to obtain a relatively simple formula for the mid-point hang h:

h=β1(cosh(v)1)=Lsinh(v)cosh(v)+1.

  1. (2 pts) When dL, we find that tβ1. Use the given equations and the Taylor expansion for sinh(x)=x+x3/6+O(x5) to find that v6d/t.

  2. (4 pts) Complete the Newton iteration to v (and from there h) in terms of L and d. Give the result and a semilog convergence plot (for an appropriate residual measure) for the case of L=100 and d=1 and d=10. Your convergence criterion should target a relative error of 108 or smaller in the computed v.

  3. (4 pts) Write a Newton solver to compute d from L and h. You will want a good initial guess (e.g. from Taylor expansions around v=0). Give the computed d and a convergence plot for L=100 and h=10.

You may also want to sanity check your code by ensuring consistency with the numbers from problem 2 (no points for this, just a hint).

1.3 ms

Partial codes

Feel free to modify these implementations as you see fit.

155 μs
compute_hang (generic function with 1 method)
1.3 ms
compute_d (generic function with 1 method)
1.5 ms

3. Close calls

For this problem, we define two cubic Bézier curves, the images of f:[0,1]R2 and g:[0,1]R2. Along with implementing f and g, we also provide f, g, f, and g.

201 μs
#11 (generic function with 1 method)
14.4 ms

Below, we show the curve for f in blue and the curve for g in red.

112 μs
plot_curves (generic function with 2 methods)
2.7 ms
1.5 s

Finding the point on f([0,1]) that is closest to a target q can be rewritten as a polynomial root-finding problem. We implement a function nearest_cubic_b(pf, q) that takes the control points for a Bézier curve and a target point q and returns t[0,1] such that f(t)q is minimal (along with the distance).

137 μs
nearest_cubic_b (generic function with 1 method)
2.3 ms
18.2 ms

Our goal is to find the closest points on these two curves, i.e. (s,t) such that

ϕ(s,t)=12f(t)g(s)2

is minimal. As a starting point, we provide coe to get an initial guess based mesh of 10 points each in t and s.

  1. (5 points) Starting from the guess from the first part, implement a nonlinear Gauss-Seidel method (aka coordinate descent), where in each sweep you first update t (assuming s correct) then update s (assuming t correct). Use the provided nearest_cubic_b routine as a building block. Give a semi-log convergence plot of ϕ vs k. Give an estimate for the constant in the (linear) convergence rate.

  2. (5 points) Write a Newton iteration to refine s and t. Do not worry about the end cases (closest points are at the ends), nor about having an inadequate initial guess. Give a convergence plot to illustrate quadratic convergence of the method.

315 μs

Partial codes

We give you the closest_on_mesh code. I wrote closest_gs and closest_newton routines for questions 1-2.

139 μs
closest_on_mesh (generic function with 1 method)
1.8 ms
ts_mesh
167 μs
16.1 ms

4. Largely linear (10 points)

Consider the general class of equations AxBg(cTx)=0, where ARn×n is nonsingular, BRn×k, and g:RRk. As a specific example, we will consider

G(x)=[523256369][x1x2x3][cos(x3)sin(x3)0]=0.

  1. (2 pts) Define y=cTx and show x can be eliminated to obtain an equation y=h(y).

  2. (2 pts) If g is Lipschitz with constant M, show that h is Lipschitz with constant cTA1BM.

  3. (2 pts) Argue that the equation G(x)=0 has a unique solution.

  4. (2 pts) Use fixed point iteration on the 1D reduced equation to solve G(x)=0.

  5. (2 pts) Use Newton on the 1D reduced equation to solve G(x)=0.

421 μs

5. Rational approximation

We consider the problem of approximating log(x) on [0.1,2] by a rational function r(x)=p(x)/q(x) where p(x)=a0+a1x+a2x2+a3x3 and q(x)=1+b1x+b2x2+b3x3. We use fitting based on samples of log(x) at points x1,x2,,xn evenly spaced on the interval.

  1. (2 pts) Why is the constant coefficient of q chosen to be 1 rather than a free parameter b0?

  2. (4 pts) Find an initial guess at the vectors a and b by minimizing j=1n(p(xj)log(xj)q(xj))2 with a mesh of size n=100. This is a linear least squares problem. What is the root mean square error?

  3. (4 pts) Use Gauss-Newton to refine the coefficient vector, starting from the linearized initial guess. Give a convergence plot. What is the root mean square error?

341 μs

6. Funny fixed point

Consider the problem

minimize xTAx s.t. jxj4=1

  1. (4 pts) Use the method of Lagrange multipliers to derive stationarity conditions of the form Ax=λD(x)x where D(x) is a diagonal matrix whose entries depend on x.

  2. (2 pts) Dot the stationarity conditions with x to show that if x is a constrained stationary point, then the multiplier λ is given by λ=xTAx.

  3. (4 pts) Implement the fixed point iteration Axk+1=λkD(xk)xk+1, where λk is the smallest eigenvalue for the pencil (A,D(xk)), and each iterate is normalized according to the constraint. Use Julia's eigen to solve the generalized eigenvalue problem at each step. Run starting from the proportional-to-all-ones guess. Monitor the residual AxxTAxD(x)x. What is the minimum value found?

368 μs

For the third part, use the matrix

109 μs
A
3×3 Matrix{Float64}:
 3.0  1.0  1.0
 1.0  4.0  1.0
 1.0  1.0  5.0
13.5 ms

Note: We say λ,v are an eigenvalue and eigenvector of a pencil (A,B) if Av=λBv. When B is invertible, this is the same as saying λ and v are an eigenvalue and eigenvector of B1A.

12.7 ms
Loading...
ii