Prelim 2 Review Questions
Nonlinear Keywords: Newton, Finite-different Newton, secant method, bisection, golden section search, line search, steepest descent, rate of convergence, fzero, fminbnd.
1. How would you use fminbnd to find the area of the largest triangle that can fit inside the ellipse (x/a)^2 + (y/b)^2 = 1.? (By largest we mean in terms of perimeter.)
2. Assume that A(lambda) is an n-by-n matrix whose entries are differentiable functions of the scalar lambda. Define the function F from R^{n+1} to R^{n+1} by F([lambda;x]) = [A(lambda)x ; x'x-1. What is the Jacobian of the function F?
3. The nonlinear function F = [F1(x) ; ...; Fn(x)] has the property that
the kth component function Fk(x) depend only x(k) and x(n) EXCEPT Fn, which
depends on x(1),...,x(n). Describe a Newton method step.
4. Suppose F(x) is a function from Rn to Rn with the property that its Jacobian J(x) is pentadiagonal for all x. Explain how one can generate a divided difference approximation of J with just five F-evaluations. Hint: for a cleverly chosen vector v, (F(x+hv)-F(x))/h will provide an approximation to J(:,1), J(:,5), J(:,9), etc.
5. F:Rn-->Rn has the property that F(x) is linear in x(1:m) where 1<=m<n. How could this structure be exploited in an implementation of the finite difference Newton method?
6. Consider applying the secant method to the function f(x) = (x^2 - A) where A>0. Show that
e(k+1) = e(k) * e(k -1) / (x(k) + x(k-1) ) where e(j) = x(j) - sqrt(A)
7. Write a function r = cRoots(a,b,c,d) that returns in the column 3-vector r all the roots of the cubic equation ax^3 + bx^2 + cx + d = 0. Make effective use of fzero and assume that the cubic has three real distinct roots.
Linear Keywords: QR, QR-with column pivoting, SVD, least squares, symmetrix Schur decomposition, power method, Jacobi's algorithm for the symmetric eigenvalue problem.
8. Complete:
function X = TwoSidedLS(A,C,B)
% A is m-by-n with rank n
% C is p-by-q with rank q
% B is m-by-q
% X is n-by-p and minimizes norm(A*X*C - B,'fro')
[UA,SA,VA] = svd(A);
[UC,SC,VC] = svd(C);
9. p(x) = det(T - xI) where T is symmetric and tridiagonal. Show how to compute the newton step
xNew = xc - p(xc) / p'(xc).
10. F and G are n-by-r matrices with full column rank and b is n-by-1. Show how to compute an n-vector x so that norm(F*G'x - b,2) is minimized and x has at most r nonzeros. Use the Matlab QR function.
11.