**Unformatted text preview: **MATH 472 Midterm Exam Please ll in: 28 February 2019 Leave blank:
Problem
Points
Out of
1
10
2
10
3
10
4
10
5
10
Total
50 First name
Last name
uniqname Read the following instructions carefully:
• Do not turn this sheet over before the instructor tells you to do so. • Write your name at the top right of each page.
• Use a pen (or pencil) with blue or black ink. Do not use red pens. • There are ve problems and you have 80 minutes. one double-sided sheet (8.5 by 11 inches) of notes/formulas in your own
handwriting. No other notes or books are allowed. • You may use • You may use a calculator, but all intermediate steps in your calculations must be compre- hensible from your notes. • All results have to be justied by appropriate intermediate steps and/or arguments. You can, however, use standard formulas and results known from the lecture without derivation (unless explicitly stated otherwise). • Scrap papers will be provided. FFF Good luck! FFF Page 1 of 6 Problem 1 (10 Points) Name: (a) (4 Points) Convert the binary number (1001.10)2 to base 10.
(b) (6 Points) Find the binary representation of the decimal number 157 .
Solution:
(a) The integer part is (1001)2 = 23 + 20 = 9.
The fractional part is x = (0.10)2 . Using the shift property, we have (22 − 1)x = (10.)2 = 2.
Hence, x = 23 .
Therefore (1001.10)2 = 9 + 32 = 293 .
(b) Note that 157 = 2 + 17 . The integer part 2 = (10)2 .
As for the fractional part 17 , the algorithm discussed in class yields:
1
7
2
2·
7
4
2·
7
1
2·
7
2· ..
. 2
7
4
=0+
7
1
=1+
7
2
=0+
7
=0+ Hence, 17 = (0.001)2 .
Therefore 157 = (10.001)2 . Page 2 of 6 Problem 2 (10 Points) Name: 1
(a) (4 Points) Show that f (x) = x − 1+x
has a root in the interval [0, 1] and apply two steps of the Bisection Method (with initial interval [0, 1]) to nd an approximate root within 1/8
of a true root.
(b) (2 Points) How many steps of the Bisection Method would you need to perform to ensure
that the approximate root is correct within 9 decimal places?
(c) (4 Points) Find all xed points of g(x) = x2 − 14 x + 38 and for each xed point, decide whether
Fixed-Point Iteration is locally convergent to it. Solution:
(a) As f is continuous on [0, 1], f (0) = −1 is negative, and f (1) = 12 is positive, f has a root in
the interval [0, 1] by the intermediate value theorem.
We apply two steps of the Bisection Method with a0 = 0 and b0 = 1:
0
= 21 and f (c1 ) = 12 − 23 = − 16 < 0. Hence, f has a root in [ 12 , 1] and we set
Step 1: c1 = a0 +b
2
1
a1 = c1 = 2 and b1 = b0 = 1.
5
1
Step 2: c2 = a1 +b
= 43 and f (c2 ) = 34 − 47 = 28
> 0. Hence, f has a root in [ 21 , 34 ].
2
The midpoint c3 = 21 ( 12 + 34 ) = 58 of the interval [ 21 , 34 ] therefore lies within 1/8 of a true root
of f .
1
< 0.5 × 10−9 . So n > log9 2 ≈
(b) From the denition of 9 decimal places, we require that 2n+1
10
29.897. So we need at least 30 steps.
(c) x is a xed point of g(x) if g(x) = x, i.e., x2 − 14 x + 38 = x. Equivalently, 0 = x2 − 54 x + 83 =
(x − 12 )(x − 34 ). Thus, x1 = 12 and x2 = 34 are the only xed points of g .
We have g 0 (x) = 2x − 14 and thus |g 0 (1/2)| = 3/4 < 1 and |g 0 (3/4)| = 5/4 > 1. Therefore,
FPI converges locally to 1/2 by Theorem 1.6, but does not converge locally to 3/4. Page 3 of 6 Problem 3 (10 Points) Name: Let f (x) = x4 + 2x3 − 2x − 1.
(a) (4 Points) Apply two steps of Newton's Method to f with initial guess x0 = 0.
(b) (5 Points) Determine for each of the two roots r1 = −1 and r2 = 1 of f whether Newton's
method converges locally linearly or quadratically, and determine the rate of convergence.
(c) (1 Point) For the roots of f where the convergence is not quadratic, suggest a modication
of the algorithm so that the convergence becomes quadratic. Solution:
(a) We have f 0 (x) = 4x3 + 6x2 − 2. We apply two steps of Newton's Method with initial guess
x0 = 0: = − 12 .
Step 1: x1 = x0 − ff0(x(x00)) = 0 − −1
−2 Step 2: x2 = x1 − ff0(x(x11)) = − 12 − 1
− 82 +1−1
16
− 48 + 64 −2 = − 12 − −3/16
1 = − 11
.
16 (b) We need to determine the multiplicity of both roots.
For r1 = −1, we have f 0 (r1 ) = 0, f 00 (r1 ) = 12r12 +12r1 = 0, and f 000 (r1 ) = 24r1 +12 = −12 6= 0.
Hence, the multiplicity of the root r1 is m = 3. By Theorem 1.12, we conclude that Newton's
= 23 .
method converges locally linearly to r1 = −1 with rate S = m−1
m
For r2 = 1, we have f 0 (r2 ) = 8 6= 0. Hence, r2 is a simple root.
1.11, Newton's 00By Theorem f (r2 ) 24
method converges locally quadratically to r2 with rate M = 2f 0 (r2 ) = 2·8
= 32 . (c) For approximating the point r1 we suggest the following modication of Newton's method
xk+1 := xk − 3f (xk )
f 0 (xk ) Page 4 of 6 Problem 4 (10 Points)
Let A = Name:
1
1
.
1+δ 1 (a) (5 Points) Find the condition number cond(A) as a function of δ > 0.
Remark:
a b
The inverse of a matrix B =
is B −1 =
c d 1
ad−bc
d −b
.
−c a (b) (5 Points) Find
magnication factor (as a function
of
the error
δ > 0) for the approximate
solution xa = −1
2
to the system Ax = b, where b =
.
3+δ
2+δ Solution:
(a) By Theorem 2.6, cond(A) = kAk∞ kA−1 k∞ . The inverse of A is given by
−1 A 1
=
1 − (1 + δ) 1
1
1
−1
−δ
δ
= 1
.
−(1 + δ) 1
+ 1 − 1δ
δ As kAk∞ = max(1 + 1, 1 + δ + 1) = 2 + δ and kA−1 k∞ = max( 1δ + 1δ , 1δ + 1 + 1δ ) = 2δ + 1, we
obtain cond(A) = (2 + δ)( 2δ + 1) = δ + 4 + 4δ .
(b) The exact solution of Ax = b is x = A−1 b = (1, 1)> . The relative forward and backward
errors are
kx − xa k∞
k(0, −2 − δ)> k∞
=
= 2 + δ,
kxk∞
k(1, 1)> k∞
k(2, 2 + δ)> − (2 + δ, 2)> k∞
δ
kb − Axa k∞
=
=
.
Relative Backward Error =
kbk∞
k(2, 2 + δ)> k∞
2+δ Relative Forward Error = Hence, the error magnication factor for xa is
Error Magnication Factor = RelativeForwardError
2+δ
4
=
=δ+4+ .
RelativeBackwardError
δ/(2 + δ)
δ Page 5 of 6 Problem 5 (10 Points) Name: (a) (7 Points) Find the matrices L, U , and P in the P A = LU factorization (using partial
pivoting) of the matrix 6 −6 −2
8 .
A=0 1
12 −4 −4 (b) (3 Points) Let A be a non-singular 1000 × 1000 matrix. Suppose that your computer needs
exactly 1 minute to solve 500 linear systems with the same matrix A (but dierent righthand side vectors, namely Ax = b(i) , i = 1, . . . , 500) using the LU factorization method.
Estimate how many seconds the computer was working on the LU factorization alone
(without the back substitution part). Solution:
(a) We swap the rst and third rows (so that the largest element is on the diagonal), and then
1 ):
2 − 0 1 and 3 − 12 eliminate the rst column ( 12
12 −4 −4 0
0 1
8 −→ 1
6 −6 −2 2 −4 −4 1
8 , −4 0 0 0 1
P = 0 1 0 .
1 0 0 3 − (− 14 ) 2 ):
We swap the second and third rows and then eliminate the second column ( 12 1
2 0 12
−4 −4 1 −4 0 −→ 2 1
8
0 −4 0
, 8 −4
−4
− 41 0 0 1
P = 1 0 0 .
0 1 0 Now we can read o the matrices P , L and U : 0 0 1
P = 1 0 0 ,
0 1 0 1 ,
L = 21 1
1
0 −4 1 12 −4 −4
−4 0 .
U =
8 (b) For a system of dimension n = 1000, solving k = 500 systems using the LU factorization
method needs approximately 32 n3 + 2kn2 operations. The LU factorization alone needs
approximately 23 n3 operations. Thus, the fraction of time spent on the LU factorization is
approximately
2 3
n
3
2 3
n
3 + 2kn2 = 2
10003
3
2
10003
3 + 2 · 500 · 10002 = 0.4. Thus, the computer was working approximately 0.4·60 = 24 seconds on the LU factorization. Page 6 of 6 ...

View
Full Document