Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Math 128B: Final Exam

Winter 2023

Due June 15

1    Instructions

• The final consists of 4 problems (25 pts each) and 1 optional bonus question which requires some additional coding.

• You do not need to write any report for this final, only produce the requested plots/tables and attach the code at the end of the project.

• Be sure to indicate which plots relate to which questions and label all figures properly (i.e. titles, axis labels, and legends for plots with multiple functions)

• You may use any codes which you wrote in this class or write new code.

• You may not use any symbolic logic or built-in solvers which weren’t previously allowed.

• If you used a built-in solver in a previous project, like lu as a sub-module of your power method code, this is okay to use for a question about the power method, but you need to use your lu solver with your forward and backward solvers for the

question about the lu method.

• Collaboration with other students is forbidden.

• No extensions will be given for this project.  All work must be turned in on Canvas by Thursday 6/15 at midnight.

2    Problems

1. Consider the Equation f(x) =  . Compute the solution to the problem f(x∗ ) = 3 by analytically (i.e. sovle it by hand). Then, algebraically manipulate the equation into a root-finding problem.  With [0, 30] as the initial window, use the bisection method to approximate the solution’s location to within a window of length 1e−8 . Report a graph with the error |x(n) − x∗ | on the y-axis and the iteration count n on the x-axis. Then repeat this using a log-log plot.

2. Consider a single matrix from the family:

A = 7I +  1  (P + R)

where I is a 100 × 100 identity matrix, P is a random permutation of the identity matrix and R is a matrix with entries drawn from the normal distribution, centered at zero.

Compute the LU factorization of the matrix. Then for 25 different random vectors sampled from the unit normal distribution, b, compute the solution to the equa- tion Ax = b using Gaussian elimination, LU factorization (using the precomputed factorization), and the Jacobi Method, and Gauss-Siedel method with update tol- erance 1e−8 .  Report the average time it took to compute the solution, along with the average residual error (||Ax − b||2 ) for each method in a table. (Do not include the time to compute the LU factorization in the LU time)

Hint: To perform a random permutation in matlab use the command: P =  I ( randperm ( n ) , : )

and in python use:

P =  I [ np . random . permutation ( n ) , : ]

3. Consider a 100 × 100 matrix with −4 on the diagonal.  Add a symmetric matrix of the form B  = R + RT  with R =  randn(100, 100) to the matrix above.  (So A = −4I + R + RT ) Then, use some form of the power method to compute the eigenvalue of the matrix which is closest to 1 and the associated eigenvector. Iterate until |λn − λn+1| < 1e−8 .

Report two graphs. First: A graph showing the eigenvector error ||Ax(n) −λ(n)x(n)|| on the y-axis and n on the x-axis. Second: A graph showing |λ(n) − 1| versus n.

4. Consider the nonlinear equations x1 − x1(2) +4x2  = 12 and (x1 −2)2 +(2x2 −3)2  = 25. Plot these equations.  Then use Newton’s method to compute a solution until ∥x(n)  − x(n+1)∥2   < 1e−6  by initializing at x(0)   = 0.  Report a graph showing the residual error (y-axis) vs iteration count (x-axis). Then use a log-log plot to report the same errors.

5. Bonus (up to 15 points): Use the steepest descent to solve problem 4 to an accuracy of 1e−6 .  Start with a manually selected step-size α  (5 pts) and then implement the quadratic-based step-size selection (10 pts) and compare their performances by adding them to the error plots in question 4.

Attach all code you wrote to the end of the report after your results.

3    Academic Integrity

Please copy and sign the following statement of academic integrity:

On my personal integrity as a student and member of the UCD community, I have not given, nor received and unauthorized assistance on this assignment.