[go: up one dir, main page]
Scribd
Upload
58 views4 pages

Homework II Solution: August 25, 2017

This document contains solutions to homework problems involving numerical analysis techniques. Several problems involve using the bisection method or fixed-point iteration to find roots of equations or approximations. The problems are ranked in order of the apparent speed of convergence of different fixed-point iteration methods. Additionally, conditions for convergence of fixed-point iteration are derived when finding reciprocals or solving specific equations.

Uploaded by

Nilson Aguirre Velasquez
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
58 views4 pages

Homework II Solution: August 25, 2017

This document contains solutions to homework problems involving numerical analysis techniques. Several problems involve using the bisection method or fixed-point iteration to find roots of equations or approximations. The problems are ranked in order of the apparent speed of convergence of different fixed-point iteration methods. Additionally, conditions for convergence of fixed-point iteration are derived when finding reciprocals or solving specific equations.

Uploaded by

Nilson Aguirre Velasquez
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Homework II Solution

August 25, 2017

Section 1.3 6: Find the rates of convergence of the following sequences as n → ∞.


1 1
a. lim sin = 0 b. lim sin =0
n→∞ n n→∞ n2
2
1

c. lim sin = 0 d. lim [ln(n + 1) − ln(n)] = 0
n→∞ n n→∞

Solution:
1
sin −0
a. limn→∞ 1/nn
= 1, then we say sin n1 converges to 0 with rate of
convergence O( n1 ).
sin 12 −0
b. limn→∞ n
1/n2
= 1, then we say sin n12 converges to 0 with rate of
1
convergence O( n2 ).
1 2
(sin n ) −0
 2
c. limn→∞ 1/n2
= 1, then we say sin n1 converges to 0 with
rate of convergence O( n12 ).
d. Using Taylor expansion:
1 1 1 1 1
ln(n + 1) − ln(n) = ln(1 + )= − 2
+ O( 3 ).
n n 2n n
Then we have
1 1 1
ln(n + 1) − ln(n) n − 2 n2 + O( n13 )
lim 1 = lim 1 = 1.
n→∞ n→∞
n n

Therefore we say ln(n + 1) − ln(n) converges to 0 with rate of conver-


gence O( n1 ).

1
Section 2.1 2(a): Let f (x) = 3(x + 1)(x − 1/2)(x − 1). Use the Bisection method
on the following intervals to find p3 .
a. [−2, 1.5].
Solution:
a+b
a = −2, b = 1.5, p1 = 2 = −0.25
f (a) = −22.5, f (b) = 3.75, f (p1 ) = 2.1094, take a = −2, b = p1 =
−0.25, p2 = a+b
2 = −1.125
f (a) = −22.5, f (b) = 2.1094, f (p2 ) = −1.2949, take a = p2 = −1.125, b =
−0.25, p3 = a+b
2 = −0.6875

√
14 (12): Find an approximation to 3 correct to within 10−4 using
the Bisection Algorithm. [Hint: Consider f (x) = x2 − 3.]
Solution:
Take a = 1, b = 2, we have
b−a 1
|pn − p| ≤ n
= n < 10−4 .
2 2
We solve this inequality and obtain n > 13.2877. So we take n = 14
and compute p14 = 1.73205566406250.

20 (16): Let f (x) = (x − 1)10 , p = 1, and pn = 1 + 1/n. Show that


|f (pn )| < 10−3 whenever n > 1 but that |p − pn | < 10−3 requires that
n > 1000.
Proof:
1
|f (pn )| = |(pn − 1)10 | = | | < 10−3 .
n10
Since 2110 = 9.765625000000000 · 10−4 < 10−3 and |f (pn )| is a decreas-
ing function with n, we have |f (pn )| < 10−3 whenever n > 1.
On the other hand,
1
|p − pn | = | | < 10−3 .
n
Solving this inequality, we obtain n > 1000.

2
Section 2.2 6 (4): The following four methods are proposed to compute 71/5 .
Rank them in order, based on their apparent speed of convergence,
assuming p0 = 1.
 3
7−p5n−1
a.pn = pn−1 1 + p2n−1

p5n−1 −7
b.pn = pn−1 − p2n−1
p5n−1 −7
c.pn = pn−1 − 5p4n−1
p5n−1 −7
d.pn = pn−1 − 12
Solution:

n=1, pa=343 ,pb=7 ,pc=2.2 ,pd=1.5


n=2, pa=-2.25393e+25 ,pb=-335.857 ,pc=1.81976,pd=1.45052
n=3, pa=-3.38385e+253,pb=3.78844e+07 ,pc=1.58347,pd=1.49875
n=4, pa=-Inf ,pb=-5.43726e+22,pc=1.48946,pd=1.4519
n=5, pa=NaN ,pb=1.60746e+68 ,pc=1.47602,pd=1.49758
n=6, pa=NaN ,pb=-Inf ,pc=1.47577,pd=1.45319
n=7, pa=NaN ,pb=NaN ,pc=1.47577,pd=1.49648
n=8, pa=NaN ,pb=NaN ,pc=1.47577,pd=1.4544
n=9, pa=NaN ,pb=NaN ,pc=1.47577,pd=1.49544
n=10, pa=NaN ,pb=NaN ,pc=1.47577,pd=1.45552

We have 71/5 = 1.47577316159455. So the order should be (c), (d),


(b), (a).

8 (6). Use a fixed-point iteration method to determine a solution


accurate to within 10−2 for x3 − x − 1 = 0 on [1, 2]. Use p0 = 1.
Solution: we can set r
1
g(x) = 1+ ,
x
√
which is a decreasing function in [1, 2] with g(1) = 2 and g(2) =
1.2247. We have g(x) ∈ [1, 2].

3
Then g 0 (x) = − 2√x13 +x4 , which is a increasing function in [1, 2] with
g 0 (1) = −0.3536 and g 0 (2) = −0.1021. We have

|g 0 (x)| < 0.4 = k.

We have

|pn − p| ≤ k n max(p0 − 1, 2 − p0 ) = k n < 10−2 .

Solving this inequality, we have n > 5.0259. So we take n = 6.

n=1,p_n=1.41421
n=2,p_n=1.30656
n=3,p_n=1.32867
n=4,p_n=1.32387
n=5,p_n=1.3249
n=6,p_n=1.32468

20 (16): Let A be a given positive constant and g(x) = 2x − Ax2 .


a. Show that if fixed-point iteration converges to a nonzero limit, then
the limit is p = 1/A, so the reciprocal of a number can be found using
only multiplications and subtraction.
b. Find an interval about 1/A for which fixed-point iteration con-
verges, provided p0 is in that interval.
Solution:
(a) The limit p should satisfy:

p = 2p − Ap2 .
1
We solve this equation and obtain p = A.
(b) We want:
|g 0 (x)| = |2 − 2Ax| < 1.
1 3
Therefore x ∈ ( 2A , 2A )

You might also like