HIST 251 Final, Fall 2007
American University of Beirut · History of North Africa and Spain in the Middle Ages · 10 pages
More HIST 251 files
Show the text of this final exam
AMERICAN UNIVERSITY OF BEIRUT
Faculty of Arts and Sciences
Mathematics Department
MATH 251
FINAL EXAM
FALL 2007-2008
Closed Book, 2 HOURS
WRITE YOUR ANSWERS ON THE QUESTION SHEET
STUDENT NAME
ID NUMBER
Problem
Out of
Grade
1
30
2
15
3
15
4
40
TOTAL
100
1
1. (30 points) Consider the following 5 points:
x
1
2
3
4
5
f(x)
1
4
11
17
23
Find the cubic spline of each subinterval in the following way:
(a) Find the values of the moments (wi) by solving the system Aw = r
• Specify the elements of matrix A and vector r:
• Apply Naive Gauss Elimination to get an upper triangular
system.
2
(Continued...)
• Perform backward substitution to get the solution of the sys-
tem Aw = r.
3
(b) Find the derivatives (zi)
• Find the value of z0.
• Using z0 compute the remaining values of z.
4
2. (15 points) Let
a = (1, aq−1, aq−2, · · · · · · , a1, a0), ai ∈ {0, 1}
b = (1, br−1, br−2, · · · · · · , b1, b0) , bi ∈ {0, 1}
be the binary representations of 2 base 10 numbers M and N respec-
tively. The base 10 numbers M and N corresponding to the bits given
by a and b are:
M = 2q + aq−12q−1 + · · · · · · + a12 + a0
N = 2r + br−12r−1 + · · · · · · + b12 + b0
such that N ≤ M ⇔ r ≤ q.
M ∗ N =
(2r + br−12r−1 + · · · · · · + b12 + b0) ∗ N
=
b0N
+
=
b12N
+
...
=
br−12r−1N+
=
2rN
(a) Complete the following MATLAB program which evalutes M ∗ N
using nested multiplication:
function [P]= MbyN(r,b,N)
T = N;
P = 1;
%%% Using the nonzero elements of vector b compute M*N
for i=
end
5
(b) Prove that r ≈ log2 N
6
3. (15 points) Consider the problem of finding r =
1
√
R.
(a) Give the function f(x) for which r is the unique positive solution,
such that the computation of f(x) does not require any division.
(b) Write Newton’s iteration formula that gives the sequence {xn}
that would converge to r. Give a graphic justification into why
the the sequence {xn} converges for every x0 > 0.
(c) Prove that:
xn+1 − r = (xn − r)2
2xn
7
4. The function values of f(x) are arranged in a table as follows:
i
xi
f(xi)
0
0.000
1.0000000
1
0.125
1.1108220
2
0.250
1.1979232
3
0.375
1.2663800
4
0.500
1.3196170
5
0.625
1.3600599
6
0.750
1.3895079
7
0.875
1.4093565
8
1.000
1.4207355
(a) Give the formula for the composite trapezoid rule, T(h) to ap-
proximate the integral I =
� 1
0 f(x)dx and write the expression of
I − T(h) in terms of powers of h.
8
(b) Derive subsequent, Romberg integration formulae, R1(h), R2(h), R3(h).
(c) Based on the above f(xi) data, approximate the integral I =
� 1
0 f(x)dx, by filling the following table:
h
T(h)
R(1)(h)
R(2)(h)
R(3)(h)
h0 = 1
h0/2 = 0.5
h0
4 = 0.25
h0
8 = 0.125
9
(d) Using the forward Difference formula to approximate f
′(0), fol-
lowed by Richardson extrapolation, find the best approximation
to f
′(0) starting with h0 = 0.5.
For that purpose, derive the
formulae of the following table and fill its entries:
h
φ(h)
φ(1)(h)
φ(2)(h)
h0 = 0.5
10