讲解Math 170A、MATLAB程序语言调试、MATLAB辅导 辅导Database|讲解Python程序
- 首页 >> Algorithm 算法 Math 170A, Winter 2020 Sample Questions for Final
The following are a set of questions that are similar to questions that will be on the Final.
Q1. a) Let p be a permutation of 1, 2, . . . , n, and P be the permutation matrix defined
by p. That means that each entry of P is either 0 or 1, with the property that
for every row i, 1 ≤ i ≤ n, P(i, p(i)) = 1 and P(i, j) = 0 for all j 6= p(i).
Show that P
TP = I.
b) Let A be an n × n, symmetric matrix and let B be the result of A after just one
step of Gaussian elimination (so B satisfies bi1 = 0 for all i = 2, 3, . . . , n). Prove
that bij = bji, for all 2 ≤ i, j ≤ n. Be sure to label exactly where you use the
symmetry of A.
Q2. Consider an iterative method for solving Ax = b defined by a “splitting” A = M − N,
and the iterating equation
Mx(k+1) = Nx(k) + b ,Use the
iterating equation Mx(k+1) = Nx(k) + b to obtain a simpler iterating equation for e
(k)
(you will need the facts that Ax∗ = b and A = M − N).
Given M, N above, will this iterative method converge for any initial condition x. Will the Gauss Seidel iteration converge regardless of the
initial guess x
(0)? Explain your answer.
Q4. Write a MATLAB function that takes as input a matrix A, a vector b, an initial guess
x
(0), and a maximal number of iterations k, and then uses the Gauss Seidel method
to solve Ax = b with initial guess x
(0). Your function should stop when the maximal
number k of iterations is reached.
with partial pivoting. Make sure you write out the matrices P, L, U. Remember
that you can always check your answer by computing A = P
TLU.
Q6. To answer the questions below, you may assume that the following holds (you don’t
need to prove this):
kxk∞ ≤ kxk2 ≤ kxk1 ≤√nkxk2 ≤ nkxk∞.
Questions:
1
a) Show that kAk1 ≤ nkAk∞.
b) Find an example of a matrix for n = 2 such that kAk1 = 2kAk∞. You must
compute both norms to show that your example works.
Hint: It may help to first find an example of a length 2 vector x for which
kxk1 = 2kxk∞ first.
c) Let Q be an orthogonal matrix. Show that kQxk2 = kxk2 for every vector x.
Q7. Let u be a unit-norm vector (||u||2 = 1) and let Qu be the Householder reflector
Qu = I − 2uuT
. What are the eigenvalues and determinant of Qu? (Hint: recall that
P = uuT
is a rank-one matrix for which P u = u.)
Q8. Consider the positive definite matrix A ∈ R
n×n
, and let A = RTR be its Cholesky
decomposition.
a) Show that κ2(A) = (κ2(R))2
, where κ2 stands for “condition number in norm 2”.
b) Show that the right singular vectors of A are also right singular vectors for R.
Q9. Suppose that the matrix A ∈ C
4×4 has eigenvalues {2, −2, 1.5, 0.5}, with eigenvectors
v1, v2, v3, respectively, v4. Let q = v3 + 2v4. Will the power method started with q0 = q
converge, and if so, to what? (Hint: without normalizing the vectors, try writing out
q1, q2, q3, q4, . . .)
a) Perform the Gram-Schmidt process on {v1, v2, v3} to obtain three orthonormal
vectors q1, q2, q3.
b) Let A = [v1, v2, v3]; use a) to find the minimizer x for the least squares problem
involving A and b = [1, 1, 1, 1]T
.
Q11. The following is an excerpt from a MATLAB code:
[U, S, V] = svd(A);
S = diag(S);
r = rank(A);
S1 = S(1:r,1:r);
S2 = diag(ones(r,1)./S(1:r));
X = V(:,1:r)*S2*U(:,1:r)’;
Y = U(:,1:r)*S1*V(:,1:r)’;
Read and understand the code, then answer the following questions:
2
a) What is X?
b) In exact arithmetic, what is norm(A-Y)?
Q12. Let A ∈ C
2×2 be a defective matrix. Show that A is similar to a matrix,
for some particular choices of λ and α 6= 0 in C
2
.
3
The following are a set of questions that are similar to questions that will be on the Final.
Q1. a) Let p be a permutation of 1, 2, . . . , n, and P be the permutation matrix defined
by p. That means that each entry of P is either 0 or 1, with the property that
for every row i, 1 ≤ i ≤ n, P(i, p(i)) = 1 and P(i, j) = 0 for all j 6= p(i).
Show that P
TP = I.
b) Let A be an n × n, symmetric matrix and let B be the result of A after just one
step of Gaussian elimination (so B satisfies bi1 = 0 for all i = 2, 3, . . . , n). Prove
that bij = bji, for all 2 ≤ i, j ≤ n. Be sure to label exactly where you use the
symmetry of A.
Q2. Consider an iterative method for solving Ax = b defined by a “splitting” A = M − N,
and the iterating equation
Mx(k+1) = Nx(k) + b ,Use the
iterating equation Mx(k+1) = Nx(k) + b to obtain a simpler iterating equation for e
(k)
(you will need the facts that Ax∗ = b and A = M − N).
Given M, N above, will this iterative method converge for any initial condition x. Will the Gauss Seidel iteration converge regardless of the
initial guess x
(0)? Explain your answer.
Q4. Write a MATLAB function that takes as input a matrix A, a vector b, an initial guess
x
(0), and a maximal number of iterations k, and then uses the Gauss Seidel method
to solve Ax = b with initial guess x
(0). Your function should stop when the maximal
number k of iterations is reached.
with partial pivoting. Make sure you write out the matrices P, L, U. Remember
that you can always check your answer by computing A = P
TLU.
Q6. To answer the questions below, you may assume that the following holds (you don’t
need to prove this):
kxk∞ ≤ kxk2 ≤ kxk1 ≤√nkxk2 ≤ nkxk∞.
Questions:
1
a) Show that kAk1 ≤ nkAk∞.
b) Find an example of a matrix for n = 2 such that kAk1 = 2kAk∞. You must
compute both norms to show that your example works.
Hint: It may help to first find an example of a length 2 vector x for which
kxk1 = 2kxk∞ first.
c) Let Q be an orthogonal matrix. Show that kQxk2 = kxk2 for every vector x.
Q7. Let u be a unit-norm vector (||u||2 = 1) and let Qu be the Householder reflector
Qu = I − 2uuT
. What are the eigenvalues and determinant of Qu? (Hint: recall that
P = uuT
is a rank-one matrix for which P u = u.)
Q8. Consider the positive definite matrix A ∈ R
n×n
, and let A = RTR be its Cholesky
decomposition.
a) Show that κ2(A) = (κ2(R))2
, where κ2 stands for “condition number in norm 2”.
b) Show that the right singular vectors of A are also right singular vectors for R.
Q9. Suppose that the matrix A ∈ C
4×4 has eigenvalues {2, −2, 1.5, 0.5}, with eigenvectors
v1, v2, v3, respectively, v4. Let q = v3 + 2v4. Will the power method started with q0 = q
converge, and if so, to what? (Hint: without normalizing the vectors, try writing out
q1, q2, q3, q4, . . .)
a) Perform the Gram-Schmidt process on {v1, v2, v3} to obtain three orthonormal
vectors q1, q2, q3.
b) Let A = [v1, v2, v3]; use a) to find the minimizer x for the least squares problem
involving A and b = [1, 1, 1, 1]T
.
Q11. The following is an excerpt from a MATLAB code:
[U, S, V] = svd(A);
S = diag(S);
r = rank(A);
S1 = S(1:r,1:r);
S2 = diag(ones(r,1)./S(1:r));
X = V(:,1:r)*S2*U(:,1:r)’;
Y = U(:,1:r)*S1*V(:,1:r)’;
Read and understand the code, then answer the following questions:
2
a) What is X?
b) In exact arithmetic, what is norm(A-Y)?
Q12. Let A ∈ C
2×2 be a defective matrix. Show that A is similar to a matrix,
for some particular choices of λ and α 6= 0 in C
2
.
3