AS/3408/WKC/1

THE UNIVERSITY OF HONG KONG

DEPARTMENT OF MATHEMATICS
MATH 3408 Computational Methods and Differential Equations with Applications
Assignment 1
Due Date: 16 Sept. 2025 (12:00pm)

1. Let Z π
I(a) = log(1 + 2a cos x + a2 )dx.
0

(a) Show that I(a) = I(−a) and I( a1 ) = I(a) − 2π log |a| for a ̸= 0.
(b) Hence find I(a).

2. (a) Show that

n−1
 π n−1
Y  rπ 
sin n θ + =2 cos θ + .
2 r=0
n
ix −ix ) √
Hint: sin(x) = (e −e2i
where i = −1.
n−1
X  rπ 
(b) Hence, find tan2 θ + .
r=0
n

3. Apply the ϵ-n approach to prove that for 0 < |α| < 1, the sequence defined by

xn+1 = αxn + b, n = 0, 1, 2, . . . .

converges to b(1 − α)−1 for b ∈ R.

4. Consider the sequence in Question 1 by adding an independent random error en+1 .

Let 0 < |α| < 1, and define

xn+1 = αxn + b + en+1 , n = 0, 1, 2, . . . ,

where en+1 ∼ N (0, σ 2 ) and x0 = 1. Find the probability distribution of xn .

√
1+ 2
5. Construct (with a proof) a rational sequence xn which converges to 2
. You may
try
5
x0 = and xn = f (xn−1 ) for n = 1, 2, . . . ,
4
1
with f (x) = 1 + 4x .

6. It is known that the equation 0.5x = sin(x) has a root x ∈ [1.5, 2]. Apply the
bisection method to obtain an approximation xn for the solution x such that
|xn − x| < 0.01. You may first find the minimum number of iterations.

7. Discuss the advantage and weakness of the bisection method.

1
 8. Find an approximation (up to 2 decimal places) of the definite integral
Z 1
√ −x
xe dx.
0
(a) By using the Taylor’s series of e−x .
(b) By considering Z 1
I(n) = xn e−x dx
0
show that
1 1
I(n) = + I(n + 1) and lim I(n) = 0.
(n + 1)e n + 1 n→∞

Then get an approximation of I( 12 ).

9. Let g(x) = 2 sin(x). Apply the fixed point theorem to show that there exists at
least one fixed point x ∈ [−2, 2] such that x = g(x). Consider the iterative scheme
xn+1 = g(xn ) with different choices of x0 = −1, 0, 1, to obtain approximations (xn
with n = 30 iterations) of three different fixed points x.
10. Let B and C be two n × n matrices such that (B − In ) is invertible where In is the
n × n identity matrix. By using Mathematical Induction on k prove that
k  k
B (B k − In )(B − In )−1 C
 
B C
= .
0 In 0 In
Here 0 is the n × n zero matrix.
11. Let |λ| < 1 and
 
λ 1 0
..
 0 λ
 . 
J =

... ... 
 1 
0 0 λ
be an n × n Jordan matrix where n ≥ 2. Show that
lim J k = 0
k→∞

where 0 is the n × n zero matrix.

12. Consider the Strassen’s Algorithm. Let
     
A11 A12 B11 B12 C11 C12
A= B= and C =
A21 A22 B21 B22 C21 C22
be three 2 × 2 matrices such that C = A · B. We define
M1 = (A11 + A22 )(B11 + B22 )
M2 = (A21 + A22 )B11
M3 = A11 (B12 − B22 )
M4 = A22 (B21 − B11 )
M5 = (A11 + A12 )B22
M6 = (A21 − A11 )(B11 + B12 )
M7 = (A12 − A22 )(B21 + B22 ).

2
 Show that
   
C11 C12 M1 + M4 − M5 + M7 M3 + M5
C= =
C21 C22 M2 + M4 M1 − M2 + M3 + M6 .

which needs only seven multiplications.

13. Provide the MATLAB codes to calculate the value of s:

1 1 1 1
s=1− + − ··· − .
2 3 4 100
14. (a) Provide the MATLAB codes to construct the following matrix M by applying
for-loop where  
1 1/2 1/3 1/4
 1/2 1/3 1/4 1/5 
M =  1/3 1/4 1/5 1/6  .


1/4 1/5 1/6 1/7

(b) Provide the MATLAB codes for solving the following system of linear equations.
Express the solution in the form of a vector.


 x1 + 21 x2 + 31 x3 + 14 x4 = 1
 1
x + 13 x2 + 41 x3 + 15 x4 = 2
2 1
1
x1 + 14 x2 + 51 x3 + 16 x4 = 3
 31


x + 15 x2 + 61 x3 + 17 x4 = 4
4 1

15. The value of ex can be approximated by the function

n
X xk
Sn (x) = , x ∈ R,
k=0
k!

when n is a large positive integer. Use for-loop to write a function with calling
syntax
s = exp(x, n)
so that the function gives an approximation when the user specifies the values of x
and n, it also outputs 0 if n is not a positive integer.
Hint: you may need the MATLAB built-in functions fix and factorial.

3
1. (a) Let y = π − x, then we have
Z π Z 0
2
I(a) = log(1 + 2a cos x + a )dx = − log(1 − 2a cos y + a2 )dy = I(−a).
0 π

and for a ̸= 0,
Z π Z π
1 2 cos x 1 1 2
I( ) = log(1 + + 2 )dx = log (a + 2a cos x + 1)dx.
a 0 a a 0 a2
Therefore, I( a1 ) = I(a) − 2π log |a|.
(b) Now
Z π Z π
2 2 4
2I(a) = I(a)+I(−a) = log(1 − 2a (1 − 2 cos x) + a )dx = log(1+2a2 cos 2x+a4 )dx
0 0

Let y = 2x, we have

Z 2π
1
2I(a) = log(1 − 2a2 cos y + a4 )dy
0 2
and
Z π Z 2π
2 4
4I(a) = log(1 − 2a cos y + a )dy + log(1 − 2a2 cos y + a4 )dy.
0 π

Let z = 2π − y, we have
Z 2π Z 0
2 4
log(1 − 2a cos y + a )dy = − log(1 − 2a2 cos z + a4 )dz.
π π

Therefore, we have
Z π
4I(a) = 2 log(1 − 2a2 cos y + a4 )dy = 2I(−a2 ) = 2I(a2 ).
0
n
Hence, we have I(a) = 21n I(a2 ). Now, I(0) = 0.
(i) For |a| ≤ 1, as n → ∞, we have I(a) → 0. Therefore I(a) = 0 for |a| ≤ 1.
(ii) For |a| > 1, I(a) = I( a1 ) + 2π log |a| = 0 + 2π log |a|.
2. (a) Let x := θ + π2 .
einx −e−inx
sin(nx) = 2i
e−inx
= 2i Q
(ei2nx − 1)
−inx n−1 i2x i2rπ
= e
2i r=0 (e − e− n )
e−inx
Qn−1 ix− irπ eix+ irπ irπ 
n −e−ix− n
= 2ie n
 2i−inx r=0 2i
in(n−1)π Qn−1
e n inx − rπ
= 2i
(2i) e e 2n
r=0 sin(x + n )
i(n−1)π Qn−1
= (2i)n−1 e− 2 rπ
r=0 sin(x + n )
iπ
(2i)n−1 (e− 2 )n−1 n−1 rπ
Q
= r=0 sin(x + n )
n−1
(2i)n−1 (−i)n−1 r=0 sin(x + rπ
Q
= n
)
n−1
Qn−1 rπ
= 2 sin(x + n )
Qr=0
= 2n−1 n−1 rπ
r=0 cos(θ + n ).

4
 (b) Using the result in (a)
n−1
 π  X  rπ 
log sin n(θ + ) = (n − 1) log(2) + log cos(θ + ) .
2 r=0
n

Differentiate both side with respect to θ,

n−1
n cos n(θ + π2 ) X − sin(θ + rπ n
)
π = rπ .
sin n(θ + 2 ) r=0
cos(θ + n
)

n−1 n−1
 π  X  rπ  X
n cot n(θ + ) + nθ = − tan θ + + θ.
2 r=0
n r=0

Then differentiate both sides with respect to θ,

n−1 
−n2

X 1

+n= 1− rπ
sin2 π
n(θ + 2 ) r=0
2
cos (θ + n
)

Hence,
n−1
2 2
 π  X  rπ 
n csc n(θ + ) − n = tan2 θ + .
2 r=0
n

3. From the lecture notes, we have

∞  
−1 n
X
i n b
|xn − b(1 − α) | = α x0 − b α ≤ |α| |x0 | + +1 .
i=n
1−α

We have  
n b
|α| |x0 | + +1 <ϵ
1−α
if and only if
ϵ
log |x
| |+1
b
0 |+ 1−α
n> .
log |α|
Thus, for any given positive ϵ, we may take
log |x |+ ϵ b +1
( )
0 | 1−α |
N = max 1,
log |α|

then we have |xn − b(1 − α)−1 | < ϵ for n > N .

4. We have

xn+1 = αxn + b + en+1 = α2 xn−1 + b(1 + α) + αen + en+1

n n n
n+1
X
i
X
i n+1 b(1 − αn+1 ) X i
xn+1 = α x0 + b α + α en+1−i = α x0 + + α en+1−i .
i=0 i=0
1−α i=0

5
 Sum of independent normal random variables is still a normal random variable.
Furthermore,
V ar(X + Y ) = V ar(X) + V ar(Y )
for two independent random variables X and Y and V ar(aX) = a2 V ar(X). Now,
we obtain !
Xn Xn
i
E α en+1−i = αi E(en+1−i ) = 0
i=0 i=0

and
n
! n n
X X X (1 − α2(n+1) )σ 2
V ar αi en+1−i = α2i V ar(en+1−i ) = α2i σ 2 = .
i=0 i=0 i=0
1 − α2

Therefore, we have

b(1 − αn+1 ) (1 − α2(n+1) )σ 2

 
n+1
xn+1 ∼N α + , .
1−α 1 − α2

5. We apply Mathematical Induction (M.I.) to the problem. We note that x1 = 54 ∈

[1, 1.5] and is rational, so the statement is true for n = 1. Assume that xn ∈ [1, 1.5]
and is also rational for some n ∈ N. Then we have
1 1 1
1+ ≤ xn+1 = 1 + ≤1+
6 4xn 4
and xn+1 ∈ [7/6, 5/4] ⊂ [1, 1.5]. Clearly if xn = p/q for some integers p and q, we
have
4p + q
xn+1 =
4p
is also rational. Hence by the principle of M.I., the statement is true for all n ∈ N.
We first solve the equation
1
x = f (x) = 1 +
4x
2
i.e., x − x − 1/4 = 0 so we have the positive root
√
1+ 2
x= ∈ [1, 1.5].
2
We note that
1 1 |xn−1 − x| |xn−1 − x| 1
|xn − x| = |1 + −1− |= ≤ = |xn−1 − x|
4xn−1 4x 4|xn−1 x| 4×1×1 4

as |x| ≥ 1 and |xn−1 | ≥ 1. We observe that

 2  n  n    n
1 1 1 1 1 1
|xn −x| ≤ |xn−1 −x| ≤ |xn−2 −x| ≤ · · · ≤ |x0 −x| ≤ ≤ .
4 4 4 4 2 4

6
 Since limn→∞ |xn − x| = 0, we have
√
1+ 2
lim xn = x = .
n→∞ 2
Because for any given ϵ > 0, one may take
 
log(ϵ)
N = max 1,
log(1/4)

and we have for n > N  n

1
|xn − x| < < ϵ.
4

6. We wish to have 0.5 × ( 21 )k < 0.01 where k is the number of iterations. Therefore
k > 5.64 or the minimum value of k is 6 and we need to compute x7 .

x f (x) = sin(x) − 0.5x

x0 = 1.5 0.247494987
x2 = 1.75 0.108985947
x3 = 1.875 0.016585782
x6 = 1.890625 0.003976798
x7 = 1.8984375 −0.002414677
x5 = 1.90625 −0.008863941
x4 = 1.9375 −0.035235719
x1 = 2 −0.090702573

7. The bisection method for solving roots of the equation f (x) = 0 is simple and easy
to implement. The main computational cost comes from testing the sign of the
function f (x) which is also cheap. One weakness of the method is that it fails in
solving repeated roots like f (x) = x2 = 0.
√ xn+1/2 (−1)n
8. (a) Using the results in the lecture notes xe−x = ∞
P
n=0 n!
. Thus, we have
1 ∞
1X ∞ ∞
√ xn+1/2 (−1)n X (−1)n
Z Z  
−x 2 X
I= xe dx = dx = ≡ an .
0 0 n=0
n! n=0
n! 2n + 3 n=0

We can compute the terms and get I ≈ 0.38.

Pn
n an i=0 ai
0 0.666666667 0.666666667
1 −0.40000000 0.266666667
2 0.142857143 0.40952381
3 −0.037037037 0.372486772
4 0.007575758 0.38006253
5 −0.001282051 0.378780479
6 0.000185185 0.378965664
7 −2.33427E − 05 0.378 942321

7
 (b) We have
Z 1 1 Z 1 n+1 −x
e−x xn+1 e−x 1
Z
n −x n+1 x e 1 1
I(n) = x e dx = dx = |0 + dx = + I(n+1)
0 0 n+1 n+1 0 n+1 (n + 1)e n + 1
and Z 1
1
|I(n)| ≤ xn dx =
→ 0 as n → ∞.
0 n+1
Then by using the above recursion formula, we have
1
I( 12 ) = (1/2+1)e 1
+ e(1+1/2)(2+1/2) + ··· + .
= 0.245252961 + 0.098101184 + 0.02802891 + 0.006228647 + 0.001132481 + · · · +
≈ 0.378 9.

9. Since g([−2, 2]) ⊂ [−2, 2] and g(x) is continuous, by the fixed point theorem, there
exists at least one fixed point x such that x = f (x). In 30 iterations, three fixed
points obtained are −1.89549,0 and 1.89549.
10. Clearly when k = 1 the equality holds. We assume that
k  k
B (B k − In )(B − In )−1 C
 
B C
= .
0 In 0 In
Then
k+1  k 
B (B k − In )(B − In )−1 C
   k  
B C B C B C B C
= = .
0 In 0 In 0 In 0 In 0 In
Since
B k C+(B k −In )(B−In )−1 C = (B k (B−In )+B k −In )(B−In )−1 C = (B k+1 −In )(B−In )−1 C,
we have
k+1
B k+1 (B k+1 − In )(B − In )−1 C
  
B C
= .
0 In 0 In
Therefore by the principle of M.I., we proved the result.
11. We note that
   
λ 1 0 0 1 0
.. ..
 0 λ
 . 
 0 0
 . 
J =  = λI + N where N =  .
 
 . .
.. .. 1   . .
.. .. 1 
0 0 λ 0 0 0

The matrix N has the property that N k = 0 for k ≥ n. Now for k ≥ n

n   n  
k
X k! k−i i
X k(k − 1) · · · (k − i + 1)
J = λ N = i i!
λk N i .
i=0
i!(k − i)! i=0
λ

We see that n is fixed and as k → ∞, k i λk → 0. Therefore the result follows.

8
12. It is straight-forward to verify

C11 = A11 B11 + A12 B21 = M1 + M4 − M5 + M7

C12 = A11 B12 + A12 B22 = M3 + M5
C21 = A21 B11 + A22 B21 = M2 + M4
C22 = A21 B12 + A22 B22 = M1 − M2 + M3 + M6 .

The computations of all Mi require only 7 multiplications.

13. s=sum(1./(1:2:100))-sum(1./(2:2:100)).

14. (a)

n=4;
M=zeros(n,n);
for i=1:n
for j=1:n
M(i,j)=1/(i+j-1);
end
end
disp(M)

(b)

x=inv(M)*a

with M being the matrix in Part (b) and

a=[1 2 3 4]’

15. function s=expp(x,n)

if n <= 0 | n~=fix(n)
s=0
else
s=0
for k=0:n
s=s+x^k/ factorial(k)
end
end
end