代写TGauss-Seidel的、代写Python，c/c++，Java编程设计、代做PageRank algorithm

日期：2019-03-15 10:45

Practice Exercise for the Final 1

1. Consider an iterative method of the form:

x(k+1) = Tx(k) + c, k = 0, 1, . . .

with kTk < 1 and x

(0) and c arbitrary. Prove that

kx(k) xk ≤ kTkkkx

(0) xkandkx

(k) xk ≤ kTk

2. Consider the system

2x1 x2 + x3 = 1

2x1 + 2x2 + 2x3 = 4

x1  x2 + 2x3 = 5

By finding the spectral radius of TJacobi and of TGauss-Seidel prove that the Jacobi method

diverges while Gauss-Seidel’s method converges for this system.

3. Consider the matrix

a) Show that T is positive definite.

b) Compute the ρ(T), the spectral radius of T.

c) Suppose you have an iterative method defined by this particular matrix T in the

(k+1) = Tx(k) + c, k = 0, 1, . . .

Will the iterations converge explain.

4. When are iterative methods preferable to direct methods (i.e. Gaussian elimination)?

5. True (T) or False (F). Suppose A is an n × n symmetric, positive definite matrix:

a) ( ) The vector x that minimizes xTAx 2x

Tb is the unique solution to Ax = b

1All course materials (class lectures and discussions, handouts, homework assignments, examinations, web

materials) and the intellectual content of the course itself are protected by United States Federal Copyright

Law, the California Civil Code. The UC Policy 102.23 expressly prohibits students (and all other persons)

from recording lectures or discussions and from distributing or selling lectures notes and all other course

materials without the prior written permission of the instructor.

1

b) ( ) The Conjugate Gradient Method will converge to the solution of Ax = b in at

most n steps.

c) ( ) Gaussian elimination can be performed without row interchange.

d) ( ) kAk2 = det(A).

6. Consider the linear system. (2)

(a) Find the condition number K∞(A) of the matrix of coefficients A in the infinity

norm.

(b) Let x = (0.142, 0.166)T be an approximation to the solution x of the system.

Using K∞(A) find an estimate of the relative error kx xk∞/kxk∞.

7. Let x be an approximation to the solution x of the linear system Ax = b. Prove that

the error e = x x satisfies

(a) Show that A is positive definite and find its condition number in the 2 norm, i.e.,

K2(A).

(b) Consider the linear system Ax = b where b = (0, 1)T

. Taking x

(0) = (0, 0)T as

your initial guess, compute the first three iterations of the steepest descent method.

9. True (T) or False (F). Suppose A is an n × n positive definite matrix:

a) ( ) The search directions for the conjugate gradient (CG) method are always the

residuals.

b) ( ) The CG method will converge to the exact solution of Ax = b in at most n

2

iterations.

c) ( ) Two vectors u and v are said to be conjugate with respect to A if and only if

u

TAv > 0.

d) ( ) The most expensive part in a CG iteration is computing the product of A and

a vector.

e) ( ) For A sparse, the CG method generally beats Jacobi and Gauss-Seidel.

10. Prove that for the Steepest Descent Method consecutive search directions are orthogonal,

i.e. hv

(k+1), v(k)

i = 0.

2

11. Let Φ(x) = 1

2

hx, Axi hb, xi where A is an n × n symmetric, positive definite matrix

and b a column n- vector. Prove that the Hessian of Φ, i.e. the matrix of second

derivatives of Φ is the matrix A.

12. In the Conjugate Gradient Method prove that if v

(k) = 0 for some k then Ax(k) = b.

13. Consider the matrix

(3)

(a) Prove that A is positive definite.

(b) Let b = [1 0 1]T

. Find the exact solution x

of Ax = b using the Conjugate

Gradient Method (by hand) with initial guess x

(0) = [0 0 0]T.

(c) Verify that the residuals are orthogonal and that the search directions are conjugate.

14. a) Prove that the Bisection Method converges to the zero (root) of f(x) = x

2 2 in

the interval [1, 2].

b) Find x3 (and hence an approximation to x.

15. A zero of f(x) = x

2 2 is also a fixed point of g(x) = x

a) Explain why fixed point iteration using g(x) = x

for any x0 in [1, 2].

b) Compute x2 starting with x0 = 1.

16. a) Compute x2 in Newton’s method to find the zero of f(x) = x

2 2 in the interval

[1, 2] beginning with x0 = 1.

b) Which iteration converges the fastest to x

(x2  2) or Newton’s method? Explain.

17. The following two methods are proposed to compute 51/35

. (5)

Explain, based on the theory seen in class, which method is expected to converge the

fastest for a sufficiently good initial guess x0.

b) We would like to design a numerical method to solve equation f(x) = 0. For this,

we consider a fixed point iteration with iterative function

g(x) = x φ(x)f(x)

Determine what the function φ(x) must be to achieve quadratic convergence of the

sequence xk = g(xk1) to the single root x.

3

18. a) Consider the equation x

2+ cos x10x = 0 for x ∈ [0, 1]. Show that a solution (zero)

of this equation is a fixed point of g(x) = (x2 + cos x)/10.b) Prove that there is a unique fixed point x

of g in [0, 1] and hence a unique solution,

also x, to x

2 + cos x 10x = 0 in that interval.

c) Using x0 = 0.15 as initial guess, obtain x4.

d) Show that this fixed point iteration can only converge linearly to .

19. Consider the 3 × 3 nonlinear system:,

in D = [1, 1]×[1, 1]×[1, 1]. (a) Discuss the existence of a solution in D. (b) Write

down fixed point iteration equations for this system (only write the equations, you do

NOT have to perform any iteration).

20. Consider the nonlinear system:

This system has, in addition to (0, 0), a second solution near [3/4, 5/12]. a) Write Newton’s

method componentwise (compute the Jacobian and its inverse, etc). b) Starting

with (0.7, 0.4) perform 2 iterations of Newton’s method to find an approximation for

the second root.

21. Find the first 3 iterations obtained by the Power Method applied to the matrix

(0) = [1 2 1]T.

22. Determine a shift that can be used in the Power Method to compute λ1 when the

eigenvalues of A satisfy: λ1 = ?λ2 > |λ3| ≥ . . . ≥ |λn|.

23. Explain why Google’s PageRank algorithm is a huge eigenvalue problem.