闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

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

MATH0033

Answer all questions .

1. (a) Consider the function f : [0, 1) ! R deﬁned by f(x) = sinx − x cos x.

We are interested in ﬁnding positive roots of f. Consider the following two ﬁxed point iterations

xk+1 = φ 1 (xk ), φ 1 (x) = tan x

k+1 = φ2 (k ), φ2 (x) = x − +

where x0 and 0 are initial guesses. For each of the two ﬁxed point iterations above, determine

(i) if the method is consistent for any positive root ↵ > 0 of f; (ii) if the method is locally convergent near a positive root ↵ > 0 of f.

If either of these methods is locally convergent, determine also the corre- sponding order of convergence of that method.

(b) Provide an original example of a real-valued function f of a single real vari- able and a corresponding real root ↵ of f such that Newton’s method has local convergence of order equal to three, and no higher than three. Justify your answer by proving that your example fulﬁlls the required condition. Your answer should consist of an original example of your own creation that is not found already in the course materials or other references . (25 marks)

2. Let A 2 Rn ⇥n be the symmetric tridiagonal matrix given by 1C B C

A = B . . . . . . . . . C

B C

B( A(C)

where a and b are both positive real numbers, and where all other entries of A not shown above are zero.

(a) Show that the eigenvalues λk of A are given by

λk = a +2bcos ✓ ◆ ,

for k = 1, . . . ,n. What is the maximum and minimum eigenvalue of A? Hint: check that the vectors vk given by

vj(k) = sin ✓ ◆ j = 1, . . . ,n

are eigenvectors for k = 1, . . . ,n.

(b) Considering still the matrix A given above, show that the Jacobi method for the system Ax = b is convergent if and only if A is positive deﬁnite.

(c) For a given initial guess x0 , let xk , k ≥ 1, denote the k-th iterate of Jacobi’s method for the linear system Ax = b. Let ✏ > 0 be a given tolerance. Find

kxk − xk2 < ✏ .

Use this to describe the behaviour of the convergence of Jacobi’s method as n becomes large.

Hint: your answer should distinguish the cases where a > 2b, a = 2b and a < 2b. (25 marks)

3. Let A 2 Rn ⇥n be a symmetric positive deﬁnite matrix, let b 2 Rn . For a given 北0 2 Rn , consider the Conjugate Gradient method given by the sequence of

iterations

北k+1 = 北k + ↵kpk , ↵k =

(rk , rj ) = 0 Aj = 0, . . . ,k − 1.

Recall any results from the lectures that you use as part of your answer. (b) Show that the coeﬃcients ↵k can be equivalently written as

krk k2(2)

What can be said about the error 北 − 北k if ↵k = 0 for some value of k?

(c) Construct an original example of a matrix A and vector b to show why the Conjugate Gradient method cannot generally be applied in the case where A is not symmetric positive deﬁnite. Your answer should show clearly the reason why the Conjugate Gradient method is not applicable to your example.

Your answer should consist an original example of your own creation that is not found already in the course materials or other references . (25 marks)

4. Consider the initial value problem

y\ (t) = y2 (t) t > 0,

y(0) = 1

and consider it’s approximation by the Backward Euler method with step length h given by

(1) un+1 = un + hun(2)+1 , u0 = 1.

(a) Show that the equation (1) admits two real solutions for un+1 in terms of un , provided that un satisﬁes a condition that you should specify as part of your answer. Explain why one of these solutions is not appropriate for approximating the solution y(t) and can thus be discarded.

rence relation for the quantity zn = 1 − 4hun of the form zn+1 = φ(zn ) for

some function φ that you should determine.

(c) Using your answers in part (a) and (b), prove that for any h > 0, there exists an n 2 N such that no real solution un+1 exists. What feature of the solution y(t) of the original problem does this numerical scheme reproduce?

initial value problem is y(t) = (1 − t)− 1 . (25 marks)

MATH0033 Numerical Methods

Solutions Exam 2021-2022

1. (a) (i) Suppose ↵ > 0 is such that sin ↵ − ↵ cos ↵ = 0. Then it follows from 1 = sin2 ↵ + cos2 ↵ = (↵2 + 1)cos2 ↵ that cos ↵ 0. This further also implies that sin ↵ 0. Hence we can divide by cos ↵ and ﬁnd that ↵ = tan ↵ = φ 1 (↵). So the ﬁrst ﬁxed point iteration is consistent. Since ↵ > 0 is nonzero we also clearly get = and thus ↵ = φ2 (↵), so the second method is also consistent.

(ii) We compute φ(↵) to ﬁnd

φ(↵) = 1 + tan2 ↵

From above we have sin ↵ 0 and cos ↵ 0 for a root, and thus φ(↵) > 1 for any positive root ↵ . Therefore the ﬁrst method is not locally conver-

gent (in any neighbourhood) of any positive root ↵ .

We next compute φ(↵)

1 1 + tan2 ↵ 1 1

↵2 tan2 ↵ ↵2 tan2 ↵

Since |φ(↵)| < 1 the second method is locally convergent, and moreover since φ is smooth in a neighbourhood of any positive root ↵, the conver- gence is at least quadratic. We check that it is not higher than quadratic since

klim!1 = = ✓ − + ◆ = 0

owing to sin ↵ 0 and cos ↵ 0 from above.

(b) This question requires an original example for an unseen situation, for which

there is no unique correct solution. Marking will take into account the origi- nality and interest of the example, and also the justiﬁcations provided with the example . In particular, the answer must pay particular attention to justifying why the order of convergence is exactly equal to but no higher than three . A model solution is given below.

Consider f(x) = x− x3 /3, which has a root ↵ = 0. Newton’s method for this problem is then

x − x3 /3 2x3

Then, since f is a smooth function and f\ (0) = 1 − 0 0 we know from the lectures that Newton’s method has local convergence of order at least 2.

However, in fact the order of convergence is exactly three since, supposing that x0 0 is suﬃciently close to zero (e.g |x0 | < 1/^3 but x0 0, we get xk 0 for all k by induction, and

= = ! as k ! 1,

since xk ! 0 as k ! 1 by local convergence. Therefore the order of conver- gence is at least three. To see if it is at most three, note that any order of convergence q > 3 would require necessarily that

klim!1 = klim!1 (xk− ↵)q−3 = 0.

However in this example, limk!1 0, so the order of convergence

cannot be higher than three.

2. (a) We can extend the formula of vj(k) for j = 0 and j = n + 1 to obtain v0(k) = vn(k)+1 = 0 for all k = 1, . . . ,n. If we set !k = , we can write

(Avk)j = avj(k) + b(vj(k)− 1 + vj(k)+1 )

= asin(!kj)+ b(sin(!k(j − 1)) + sin(!k(j + 1)) = asin(!kj)+2bcos(!k)sin(!kj) = (a +2bcos(!k))vj(k) = λkvj(k)

for all j = 1, . . . ,n, where we note that the special cases j = 1 and j = n use the fact v0(k) = vn(k)+1 = 0 as shown above. Therefore we ﬁnd that A has n distinct eigenvalues {λk}k(n)=1 .

If a and b are both positive, then it is easy to see that the maximum eigenvalue

of A is

λmax = a +2bcos ✓ ◆

whereas the minimum eigenvalue is

λmin = a +2bcos ✓ ◆ = a − 2bcos ✓ ◆ .

(b) The iteration matrix of the Jacobi method is B = I − A, and thus the

eigenvalues of B are

µk = 1 − = − cos ✓ ◆

The Jacobi method is convergent if and only if p(B) < 1, i.e. |µk| < 1 for all k, or equivalently

−1 < − cos ✓ ◆ < 1 () 0 < a ± 2bcos ✓ ◆ .

Since

λn+1−k = a − 2bcos ✓ ◆ , λk = a +2bcos ✓ ◆

we see that |µk| < 1 for all k i↵ all eigenvalues of A are positive, i.e. that A is s.p.d. Therefore the Jacobi method is convergent with p(B) < 1 if and only if A is s.p.d.

kxk − xk2 < p(B) kxk0 − xk2 ,

according to Corollary 4.6.3 in the lectures. Provided that p(B) 2 (0, 1), a suﬃcient condition to obtain kxk − x k02 < ✏ is then

p(B)k < () k ≥

We compute

p(B) = mk(a)x|µk| = k a,x.,n 'cos ✓ ◆ ' = cos ✓ ◆

Therefore, the suﬃcient condition above is equivalent to

log ✏ − logkx − x0 k2

|log ⇣ cos( n 1 )⌘ |

Note that

n!1 a .

If a > 2b then the spectral radius remains uniformly bounded away from 1 for all n and log(p(B)) ! log() which remains bounded away from 0 for all n. Hence the suﬃcient condition to ensure that the error reaches a desired tolerance can be taken to be independent of n. However if a = 2b then the spectral radius p(B) < 1 for all n, but tends to 1 as n becomes large, and the right-hand side in the condition above tends to +1 as n ! 1. This shows that we can expect the convergence to become very slow for large n. If a < 2b then there would then exist n suﬃciently large such that A is not s.p.d. — in this case the condition above is no longer applicable as the Jacobi method is no longer convergent.

3. (a) From the lectures, it is shown that rk is orthogonal in the Euclidean inner- product to the k-th Krylov subspace Vk . It is also shown that rk 2 Vk+1 and that the spaces are nested i.e. V1 ⇢ V2 ⇢ ··· ⇢ Vk . Therefore, if j < k − 1, then rj 2 Vj+1 ⇢ Vk and thus (rk , rj ) = 0.

(b) From the lectures, we have rk ? Vk in the Euclidean inner-product, and pk 2 Vk+1 for all k ≥ 0. We have also seen in the lectures that since A is SPD, that kpk kA(2) = (Apk ,pk). Next, writing

pk = rk − βk−1pk−1

we use the linearity of the inner-product

(rk ,p ) = (rkk , r ) − βk−k1 (rk ,pk−1 ) = (rk , r )k

where the term (rk ,pk−1 ) = 0 since rk ? pk−1 2 Vk . Then, we use the fact that (rk , rk) = krk k2(2) to ﬁnd that

krk k2(2)

↵k =

We have ↵k = 0 for some k if and only if rk = 0 and thus the residual is exactly zero, which is equivalent to xk being equal to the exact solution x.

(c) The answer should include an original example not seen elsewhere . The grade should reﬂect the originality and interest of the example, i. e . an overly trivial example (e .g. A being the zero matrix) does not get full marks . The grade should also reﬂect the quality of the justiﬁcation as to why the Conjugate Gradient method is not applicable: for full marks the answer should detail where and how the algorithm fails . A reasonable example for instance would be as follows: Consider

A = ✓0(1) 1(2)◆ , b = ✓ 1◆ , x0 = 0

The matrix A is nonsingular, but it is not symmetric positive deﬁnite. In this case, we get p0 = r0 = b. But then ↵0 is not well-deﬁned since in the denominator we have

(Ap0 ,p0 ) = b = (1 −1) ✓0(1) 1(2)◆✓ 1◆ = (1 −1) ✓ 1(1)◆ = 0.

This means that the ﬁrst iterate x1 of the Conjugate Gradient method is not well-deﬁned.

Other suitable examples could include symmetric but indeﬁnite matrices, etc .

4. (a) The BE method gives

un+1 = un + hun(2)+1 () (un+1 − )2 =

which has real solutions

un+1 = ⇣1 ±^1 − 4hun⌘

if and only if 4hun < 1 or equivalently un < .

To ﬁnd which of the roots of the quadratic above is the physically relevant one, notice that if we choose the positive root at the ﬁrst timestep, i.e. u1 = (1+^1 − 4h), then we would have u1 ! 1 as h ! 0, whereas the continuous solution y(t1 ) = y(h) ! 1 as h ! 0 since the exact solution is y(t) = (1 − t)−1 for t 2 (0, 1). Therefore the solution using the positive root is not appropriate for approximating y(t) and can be discarded (the same argument applies to any later timestep as well). On the other hand, for the second root we get by Taylor expansion

un+1 = ⇣1 −^1 − 4hun⌘ ⇡ (2hun+2h2un(2)) = un + hun(2)

as h ! 0, so this approaches the Forward Euler solution. We conclude that the physically relevant solution at each timestep is then

un+1 = ⇣1 −^1 − 4hun⌘

(b) Let Xn = 1 − 4hun, therefore

Xn+1 = 1 − 4hun+1 = 1 − 2(1 −^Xn) = 2^Xn − 1,

so we have the recurrence relation Xn+1 = φ(Xn) with the function Xn deﬁned by φ(X) = 2^X − 1.

(c) Recall from (a) that a real solution un+1 exists if and only if Xn ≥ 0. We now show by contradiction that there is an n 2 N such that Xn < 0. Suppose to the contrary that Xn ≥ 0 for all n 2 N. Next, note that X0 = 1 − 4h < 1. Note that for any X ≥ 0, we have 2^X < X +1 and thus φ(X) < X for all X ≥ 0. This implies that the sequence Xn+1 = φ(Xn) < Xn for all n 2 N, so the sequence is decreasing.

Then the sequence Xn is decreasing and bounded from below, so it must have a limit ` ≥ 0. Moreover since X0 = 1 − 4h < 1, we must have ` < 1 − 4h < 1. But then, since φ is continuous on [0, 1), we can pass to the limit and obtain ` = φ(`) for some ` 2 [0, 1). However the function φ : [0, 1) ! R has only one ﬁxed point at X = 1, since φ(X) = X if and only if (X + 1)2 = 4X, which is equivalent to (X − 1)2 = 0. This is contradicted by the existence of a ﬁxed point ` < 1. Therefore, we conclude that there must exist an n 2 N such that Xn < 0 which is equivalent to un > thus the numerical solutions blow up. This is similar to the behaviour of the continuous solution since y(t) = (1 − t)−1 blows up as t ! 1.