QuestionQuestion

Transcribed TextTranscribed Text

1. Recall that the condition number in the 2-norm is the ratio of largest to smallest singular value. The singular value decomposition of an n by n matrix takes the form A = UΣV T where U, V are n × n orthonormal matrices and Σ is an n × n diagonal matrix with the singular values σi on its diagonal. a) Write a matlab routine to generate an n×n matrix with an arbitrary (known) condition number. You can proceed as follows. For a given condition number, condno, • start by generating two random matrices U1, V1 (using the matlab function rand: >>U1 = rand(n,n)); • make the two matrices U1, V1 orthogonal by using QR factorization. This is done as follows. Execute [Q,R] = qr(U1) and set U = Q (repeat the same process to construct V ); Say why the constructed matrices U, V are both orthogonal. • generate a diagonal matrix Σ whose diagonal elements are given by σii = condno−(i−1)/(n−1) , 1 ≤ i ≤ n. This can be accomplished in matlab with the command: >>SIGMA = diag(condno^(-(0:1:n-1)/(n-1))) ; • set A = UΣV T . Compute the L2 condition number of the matrix A you generated by executing the command cond(A) to check whether it is equal to the one prescribed at the begining. Your matlab M-file can look like this: function A = matgen(n, condno) %Input size n and condition number condno %output: an nxn random matrix A whose condition number is condno. U = rand(n,n); [Q,R] = qr(U); U = Q; ... (fill in the blanks) 1 b) With n = 16 and for each condno = 1, 104 , 108 , 1012 , 1016, use your matlab routine in (a) to generate an n×n random matrix A with condition number condno. Also generate a random vector X_true of length n, and compute the product >>b= A*X_true. Solve AX = b by Gauss elimination, X=A\b in matlab. Determine the relative error ||X − Xtrue||/||Xtrue||. Explain how this is related to the condition number of A. Compute the residual ||b−Ax||/(||b||). Plot both the relative error and the residual as functions of the condition number, for condno = 1, 104 , 108 , 1012 , 1016. Does the algorithm for solving Ax = b appear to be backward stable, in other words, is the computed solution the exact solution to a nearby problem? Note: Forward stability means that a small error in the solution ||X − Xtrue|| implies the residual ||b − AX|| is small while backward stability means a small residual implies a small error in the solution. c) Now solve Ax = b by inverting A: >>Ainv = inv(A), and then multiply b by A−1 : >>X=Ainv*b. Again compare the relative errors and the residuals. Is the new algorithm backward stable? d) Redo b) and c) with n = 32 and with n = 64. Does the value of n matter at all? Matlab Hint: to compute the p-norm of a vector or matrix X in matlab, for a given p, simply execute the built in matlab function norm: >>norm(X,p) 2. Note: The singular value decomposition generalizes to m by n matrices and takes the form A = UΣV T where U is an m × m orthonormal matrix, Σ is an m × n diagonal matrix with the singular values σi on its main diagonal, and V an n × n orthonormal matrix. As such it permits to define the condition number of a matrix of an arbitrary dimension. Type >>help svd in matlab. Similarly to the SVD decomposition, the QR factorization generalizes to m × n matrices: A = Q  R O  where Q is an m × m orthogonal matrix, R is n × n upper triangular matrix and O is m − n × n matrix with zero entrees (n ≤ m). Let Q = Q1 Q2 where Q1 is m × n and Q2 is m × (m − n); both orthogonal matrices (that is their columns are mutually orthogonal: QT i Qi = I, i = 1, 2). The couple (Q1, R) is often called the economy size QR decomposition. Type >>help qr in matlab. a) Consider the problem of least square approximation Ax ≈ b where A is a m × n matrix and b ∈ R m (n ≤ m). By noting that ||Ax − b||2 2 = ||Rx − QT 1 b||2 2 + ||QT 2 b||2 2 (why?). Show that the problem of least square approximation reduces to the solution of the n × n system Rx = Q T 1 b, 2 which constitutes an attractive procedure for solving the least square problem. Show that R is non singular if A has full rank. Note: The “matrix division” X=A\b of matlab uses the QR decomposition, as outlined above, and returns the least square solution when A is not a square matrix. Moreover, the condition number defined as the ratio between the largest to the smallest singular value, can be extended to non square matrices. b) Show that cond(AT A) = (cond(A))2 and then argue why for cases when cond(A) is large the QR factorization technique is advantageous, for least square problems, then the normal method which solves instead AT AX = AT b, but for moderate cond(A) values the normal method is preferable in general. Hint: the normal method takes advantage of the Cholesky factorization. 3. Execute the following matlab code, then report and comment the results. Also put some comments in the provided blank space (fill in the blanks) to help document the code for users. For example, on the first line (Synopsis) you say what the code precisely does. e.g., What is the input and what is the output? Hint: Use the matlab help command to learn about the commands that are not familiar to you. %Synopsis:_This matlab code___________________________________________________________________ %_____________________________________________________________________________________________________ D=[319.32 320.36 320.82 322.06 322.17 321.95 321.20 318.81 317.82 317.37 318.93 319.09 319.94 320.98 321.81 323.03 323.36 323.11 321.65 319.64 317.86 317.25 319.06 320.26 321.65 321.81 322.36 323.67 324.17 323.39 321.93 320.29 318.58 318.60 319.98 321.25 321.88 322.47 323.17 324.23 324.88 324.75 323.47 321.34 319.56 319.45 320.45 321.92 323.40 324.21 325.33 326.31 327.01 326.24 325.37 323.12 321.85 321.31 322.31 323.72 324.60 325.57 326.55 327.80 327.80 327.54 326.28 324.63 323.12 323.11 323.99 325.09 326.12 326.61 327.16 327.92 329.14 328.80 327.52 325.62 323.61 323.80 325.10 326.25 326.93 327.83 327.95 329.91 330.22 329.25 328.11 326.39 324.97 325.32 326.54 327.71 328.73 329.69 330.47 331.69 332.65 332.24 331.03 329.36 327.60 327.29 328.28 328.79 329.45 330.89 331.63 332.85 333.28 332.47 331.34 329.53 327.57 327.57 328.53 329.69 330.45 330.97 331.64 332.87 333.61 333.55 331.90 330.05 328.58 328.31 329.41 330.63 331.63 332.46 333.36 334.45 334.82 334.32 333.05 330.87 329.24 328.87 330.18 331.50 332.81 333.23 334.55 335.82 336.44 335.99 334.65 332.41 331.32 330.73 332.05 333.53 334.66 335.07 336.33 337.39 337.65 337.57 336.25 334.39 332.44 332.25 333.59 334.76 335.89 336.44 337.63 338.54 339.06 338.95 337.41 335.71 333.68 333.69 335.05 336.53 337.81 338.16 339.88 340.57 341.19 340.87 339.25 337.19 335.49 336.63 337.74 338.36]; 3 %comment:_D is_a_________________________________________________ [M,N]=size(D) %This returns ____________________________________ figure subplot(2,1,1) contour(D) %comment:___________________________________________________ colorbar C = D*D’; %comment:___________________________________________________ [V,L]=eig(C); lambda = diag(L) % This displays_______________________in___________________order A=V’*D; % This computes ________________________________________ Vn = V(:,M); %To select the ________________ associated with the ______________________________________ An = A(M,:); %This is the _______________________ associated with the __________________________________ Df= Vn*An; subplot(2,1,2) contour(Df) %comment:___________________________________________________ 4 4. Here we aim to use the shooting method to solve the boundary value problem v 00 = x 2 + 3v + 10v 3 , 0 ≤ x ≤ 1 v(0) = 0; v(1) = β. (1) Where β ∈ R is fixed. Consider the associated initial value problem with an arbitrary speed s v 00 = x 2 + 3v + 10v 3 , 0 ≤ x ≤ 1 v(0) = 0; v 0 (0) = s. (2) 1. The problem in (2) has a unique solution, v(x; s), 0 ≤ x ≤ 1, for any given real number s and the function s −→ v(x; s) is continuous. Why? 2. We define the function φ(s) = v(1, s) − β. Recall that the shooting method consist in finding the right speed s ∗ so that φ(s ∗ ) = v(1; s ∗ ) − β = 0. Show that Newton’s method applied to the root finding problem φ(s) = 0 is equivalent to si+1 = si − v(1; si) − β vs(1; si) where vs(1; si) = ∂v(1; s) ∂s is the solution for the IVP v 00 s = (3 + 30v(x; s) 2 )vs, 0 ≤ x ≤ 1 vs(0) = 0; v 0 s (0) = 1. (3) Here v(x, s) is the solution for the IVP in (2) and IVP (3) is obtained by differentiating (2) with respect to s. 3. Write a matlab program to solve the BVP in (1) following the steps in (1) and (2). Use matlab ode45 to solve the 4 × 4 IVP obtained by converting the coupled BVPs in (2) and (3) for v(1; si) and vs(1; si), respectively. At each iteration of the Newton’s method, you need to solve this (coupled) IVP and substitute the values of v(1, s) and vs(1, s) in the Newton iterative scheme. 4. Execute your program with β = 0 and plot (in the same graph, i.e, on top of each other) the approximate solution v(x) of the PVB problem corresponding to Niter = 10, 50, and 100 Newton iterations. Observe the convergence to the expected solution. 5. With the most converged solution, Nmax=100, plot the sequence |si+1 − s∞| |si − s∞| 2 , where s∞ ≈ sNmax is the last (converged) iterate, then conclude. Do you observe the “expected” quadratic rate of convergence? Hint: For this question you need to save the consecutive iterates si in a vector S then use the matlab command >>plot(abs(S(2:50) -S(100))./abs(S(1:49) -S(100)).^2). 5. Let A be a square matrix and consider its singular value decomposition A = UΣV where U, V are orthogonal matrices and Σ = a diagonal matrix with diagonal entrees s1, s2, · · · , sn. (a)By noting that AV T = ΣU, show that |si | |Ui |2 ≤ ||A||2|Vi |2, for all i = 1, 2, · · · , n. 5 Where Ui , Vi are the ith columns of the matrices U, V , respectively, |.|2 is the Euclidean vector norm, and ||.||2 is the associated subordinate matrix norm. (b)Deduce that |si | ≤ ||A||2 for all i = 1, 2, · · · , n. (c)Use the definition of the matrix subordinate norm ||A||2 = max |X|2=1 |AX|2 to show that ||Σ||2 = max 1≤i≤n |si | for any given diagonal matrix Σ with diagonal entrees s1, s2, · · · , sn. (d)Show that ||A||2 ≤ ||Σ||2 where ||.||2 is the Euclidean subordinate matrix norm and Σ is the diagonal matrix formed by the singular values of A. (e)Deduce that ||A||2 = max 1≤i≤n |si |. 6

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

    By purchasing this solution you'll be able to access the following files:
    Solution.pdf.

    $50.00
    for this solution

    PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

    Find A Tutor

    View available Numerical Analysis Tutors

    Get College Homework Help.

    Are you sure you don't want to upload any files?

    Fast tutor response requires as much info as possible.

    Decision:
    Upload a file
    Continue without uploading

    SUBMIT YOUR HOMEWORK
    We couldn't find that subject.
    Please select the best match from the list below.

    We'll send you an email right away. If it's not in your inbox, check your spam folder.

    • 1
    • 2
    • 3
    Live Chats