APMA 4300: Introduction to Numerical Methods
Introduction to Numerical Methods
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
APMA 4300: Introduction to Numerical Methods
Midterm (Thursday, March 23, 2023)
Name and UNI:
Problem 1. Given n ≥ 1 and m ≥ 1, let A1 ∈ Rn×n, A2 ∈ Rm×m, and
B ∈ Rn×m be given matrices. We are interested in solving the following
block linear system [
A1 B
BT A2
] [
x
y
]
=
[
z1
z2
]
.
Consider the following two methods
(i) A1x
(k+1) +By(k) = z1, B
Tx(k) +A2y
(k+1) = z2 ;
(ii) A1x
(k+1) +By(k) = z1, B
Tx(k+1) +A2y
(k+1) = z2 .
(a) Write a function to solve the system using method (i). Your function has
to take the matrices A1, A2, and B, the right hand side
[
z1
z2
]
, and an initial
guess
[
x(0)
y(0)
]
as input and output the solution
[
x
y
]
. Your algorithm should
stop if
∥∥∥ [x(k+1)
y(k+1)
]
−
[
x(k)
y(k)
] ∥∥∥
ℓ2
≤ ε with ε = 10−8.
(b) Write a function to solve the system using method (ii). The input and
output of the function should be the same as those of the function in part
(a).
(c) Take the system where
A1 =
62 24 123 50 7
4 6 58
, A2 = [66 32 54
]
, B =
8 1514 16
20 22
,
z1 =
11
1
, z2 = [11
]
.
Run the algorithms in (a) and (b) on this system starting from initial guess[
x(0)
y(0)
]
= 0. Stop the algorithm at 100 iterations if they don’t stop earlier.
Output the final results.
(d) Can you find sufficient conditions in order for the two schemes to be
convergent for any choice of the initial data
[
x(0)
y(0)
]
? Provide some justification
for your answer.
Problem 2. Consider the function f : R→ R defined as
f(x) = −e−x
2
2 +
1
4
cos(2x) .
We are interested in finding the minimum of f(x).
(a) Design a fixed point iteration for this problem. Your fixed point iteration
should converge if the initial guess is sufficiently close to the true solution
x = 0.
(b) Write a function that solves the problem using the following fixed-point
iteration:
x(k+1) = g(x(k)), g(x) = sin(2x)
[ex22 (x sin(2x) + 2 cos(2x))− 2
2
(
x sin(2x) + 2 cos(2x)
) ]
Does this iteration converge if the initial guess is sufficiently close to the true
solution?
(c) Try to reproduce the convergent analysis we had in class to find the speed
of convergence for the fixed-point iteration you designed. Your calculations
should be done assuming you are close to the true solution x = 0. If the g
function you designed has non-zero derivative around the true solution, you
should have exactly what we had in class.
(d) Can you do the analysis in part (c) for the fixed-point algorithm in (b)?
Problem 3. In a chemical experiment, we are able to measure a quantity y
that depends on two other quantities x1 and x2. For simplicity, we use the
notation x = (x1, x2). We are interested in learning the relation between x
and y, that is, y = f(x). Our knowledge in chemistry says that y should
depend on x in the following way:
y = a0 + a1 cos(πI · x) + a2 cos(2πI · x) + · · ·+ a10 cos(10πI · x) ,
with I =
[
1
1
]
. However, we do not know the coefficients a0, a1, · · · , a10.
Suppose that in an experiment, we collect the following data:
{xj, yj}500j=1.
Propose a method that we can use to learn the unknown coefficients {a0, a1, · · · , a10}
of the model. You don’t need to implement your method. You need to out-
line your method, to a point that if we have the data, we can implement
your method. The more details you are willing to provide, the better.