Description
0.1 Ch. 1 Exercises
1. The Fibonacci numbers and nature. The Fibonacci numbers are defined by F1 = 1,
F2 = 1, F3 = F2 + F1 = 2, F4 = F3 + F2 = 3, etc. In general, Fj+1 = Fj + Fj1, j = 2, 3,….
Write down F5, F6, and F7.
F5 = F4 + F3 = 5, F6 = F5 + F4 = 8, F7 = F6 + F5 = 13.
It is often observed that the number of petals on a flower or the number of branches on a
tree is a Fibonacci number. For example, most daisies have either 34, 55, or 89 petals, and
these are the 9th, 10th, and 11th Fibonacci numbers. The reason four-leaf clovers are so rare
is that 4 is not a Fibonacci number.
To see the reason for this, consider the following model of branch growth in trees. We start
with the main trunk (F1 = 1), which spends one season growing (F2 = 1), and then after
another season, develops two branches (F3 = 2) – a major one and a minor one. After the
next season, the major branch develops two branches – a major one and a minor one – while
the minor branch grows into a major one, ready to divide in the following season. At this
point there are F4 = 3 branches – two major ones and one minor one. At the end of the next
season, the two major branches divide, producing two major branches and two minor ones,
while the minor one from the previous season grows into a major one. Thus at this point
there are F5 = 5 branches, with F4 = 3 of these being major branches ready to divide during
the next season. Explain why the Fibonacci numbers arise from this model of branch growth.
11 2 3 5
Let Mj be the number of major branches after season j and let mj be the number
of minor branches, so that the total number of branches is Fj = Mj +mj . The total
number of branches Fj+1 after j + 1 seasons is 2Mj + mj since each major branch
divides in two and each minor branch grows into a major one. This is equal to
Mj + Fj . The number of major branches Mj after j seasons is the total number of
branches Fj1 after j 1 seasons because each of these branches produces exactly
one major branch, either by dividing or by growing. Hence Fj+1 = Mj + Fj =
Fj1 + Fj , which is the defining recurrence for the Fibonacci numbers.
2
Homework 1
Friday, September 14, 12
2. Drunkard’s walk. A drunkard starts at position x in the diagram below and with each step
moves right one space with probability .5 and left one space with probability .5. If he reaches
the bar, he stays there, drinking himself into oblivion. If he reaches home, he goes to bed and
stays there. You wish to know the probability p(x) that he reaches home before reaching the
bar.
01 5
bar home
2 4 3
x
This is a typical Markov chain problem that will be discussed later in the text. Note that
p(0) = 0 and p(5) = 1, since the drunk does not leave either the bar or his home. For
x = 1, 2, 3, 4, p(x) = .5p(x 1) + .5p(x + 1), since he moves left with probability .5 and right
with probability .5.
(a) Let the drunk’s starting position be x = 3. What are the possible positions that he
could be in after one step, and what are the probabilities of each? How about after two
steps?
After one step, he is in position 2 with probability .5 and in position 4 with
probability .5. After 2 steps, he is in position 1 with probability .25, position 3
with probability .5, and position 5 with probability .25.
(b) For which initial positions x would you expect him to reach the bar first and for which
would you expect him to reach home first, and why?
From position 0, 1, or 2 he is likely to reach the bar first, and from positions 3,
4, or 5 he is likely to reach home first. Since there is no preferred direction in
his movement, he will probably reach first whichever destination he is closer to.
This is a typical random walk problem, and while it is posed as a silly story, it has real physical
applications.
Consider an electrical network with equal resistors in series and a unit voltage across the
ends.
1 23 4
0
5
v(0)=0
v(5)=1
Voltages v(x) will be established at points x = 0, 1, 2, 3, 4, 5. We have grounded the point
x = 0 so that v(0) = 0, and there is no resistor between the source and point x = 5, so that
v(5) = 1. By Kircho↵’s laws, the current flowing into x must be equal to the current flowing
out. By Ohm’s Law, if points x and y are separated by a resistor of strength R, then the
current ixy that flows from x to y is
ixy = v(x) v(y)
R .
Thus for x = 1, 2, 3, 4, we have
3
2. Drunkard’s walk. A drunkard starts at position x in the diagram below and with each step
moves right one space with probability .5 and left one space with probability .5. If he reaches
the bar, he stays there, drinking himself into oblivion. If he reaches home, he goes to bed and
stays there. You wish to know the probability p(x) that he reaches home before reaching the
bar.
01 5
bar home
2 4 3
x
This is a typical Markov chain problem that will be discussed later in the text. Note that
p(0) = 0 and p(5) = 1, since the drunk does not leave either the bar or his home. For
x = 1, 2, 3, 4, p(x) = .5p(x 1) + .5p(x + 1), since he moves left with probability .5 and right
with probability .5.
(a) Let the drunk’s starting position be x = 3. What are the possible positions that he
could be in after one step, and what are the probabilities of each? How about after two
steps?
After one step, he is in position 2 with probability .5 and in position 4 with
probability .5. After 2 steps, he is in position 1 with probability .25, position 3
with probability .5, and position 5 with probability .25.
(b) For which initial positions x would you expect him to reach the bar first and for which
would you expect him to reach home first, and why?
From position 0, 1, or 2 he is likely to reach the bar first, and from positions 3,
4, or 5 he is likely to reach home first. Since there is no preferred direction in
his movement, he will probably reach first whichever destination he is closer to.
This is a typical random walk problem, and while it is posed as a silly story, it has real physical
applications.
Consider an electrical network with equal resistors in series and a unit voltage across the
ends.
1 23 4
0
5
v(0)=0
v(5)=1
Voltages v(x) will be established at points x = 0, 1, 2, 3, 4, 5. We have grounded the point
x = 0 so that v(0) = 0, and there is no resistor between the source and point x = 5, so that
v(5) = 1. By Kircho↵’s laws, the current flowing into x must be equal to the current flowing
out. By Ohm’s Law, if points x and y are separated by a resistor of strength R, then the
current ixy that flows from x to y is
ixy = v(x) v(y)
R .
Thus for x = 1, 2, 3, 4, we have
3
Friday, September 14, 12
2. Drunkard’s walk. A drunkard starts at position x in the diagram below and with each step
moves right one space with probability .5 and left one space with probability .5. If he reaches
the bar, he stays there, drinking himself into oblivion. If he reaches home, he goes to bed and
stays there. You wish to know the probability p(x) that he reaches home before reaching the
bar.
01 5
bar home
2 4 3
x
This is a typical Markov chain problem that will be discussed later in the text. Note that
p(0) = 0 and p(5) = 1, since the drunk does not leave either the bar or his home. For
x = 1, 2, 3, 4, p(x) = .5p(x 1) + .5p(x + 1), since he moves left with probability .5 and right
with probability .5.
(a) Let the drunk’s starting position be x = 3. What are the possible positions that he
could be in after one step, and what are the probabilities of each? How about after two
steps?
After one step, he is in position 2 with probability .5 and in position 4 with
probability .5. After 2 steps, he is in position 1 with probability .25, position 3
with probability .5, and position 5 with probability .25.
(b) For which initial positions x would you expect him to reach the bar first and for which
would you expect him to reach home first, and why?
From position 0, 1, or 2 he is likely to reach the bar first, and from positions 3,
4, or 5 he is likely to reach home first. Since there is no preferred direction in
his movement, he will probably reach first whichever destination he is closer to.
This is a typical random walk problem, and while it is posed as a silly story, it has real physical
applications.
Consider an electrical network with equal resistors in series and a unit voltage across the
ends.
1 23 4
0
5
v(0)=0
v(5)=1
Voltages v(x) will be established at points x = 0, 1, 2, 3, 4, 5. We have grounded the point
x = 0 so that v(0) = 0, and there is no resistor between the source and point x = 5, so that
v(5) = 1. By Kircho↵’s laws, the current flowing into x must be equal to the current flowing
out. By Ohm’s Law, if points x and y are separated by a resistor of strength R, then the
current ixy that flows from x to y is
ixy = v(x) v(y)
R .
Thus for x = 1, 2, 3, 4, we have
3
v(x 1) v(x)
R = v(x) v(x + 1)
R .
Multiplying by R and combining like terms we see that v(x) = .5v(x 1) + .5v(x + 1). This
is exactly the same formula (with the same boundary conditions) that we found for p(x) in
the drunkard’s walk problem.
Can you think of other situations that might be modeled in this same way? The behavior
of a stock price perhaps? Suppose you generalize by allowing di↵erent probabilities of the
drunkard moving right or left, say, the probability of moving right is .6 while that of moving
left is .4. What generalization of the resistor problem would this correspond to? [Hint:
Consider resistors of di↵erent strengths.]
Daily changes in stock prices are sometimes modeled in this way, usually with
di↵erent probabilities of going up or down. In the drunkard’s walk, if he moves
right with probability .6 and left with probability .4, then the equations for p(x),
x = 1, 2, 3, 4, become p(x) = .4p(x 1) + .6p(x + 1). In the resistor problem, if the
strength of the resistor between points x and y is denoted Rxy, then the equations
for v(x), x = 1, 2, 3, 4, become
v(x 1) v(x)
Rx1,x
= v(x) v(x + 1)
Rx,x+1
.
Expressing v(x) in terms of v(x 1) and v(x + 1), we have
v(x) = Rx,x+1
Rx,x+1 + Rx1,x
v(x 1) + Rx1,x
Rx,x+1 + Rx1,x
v(x + 1),
so the given parameters would correspond to resistors of alternating strengths .6
and .4; that is, R01 = R23 = R45 = .6 and R12 = R34 = .4.
3. Ehrenfests’ urn. Consider two urns, with N balls distributed between them. At each
unit of time, you take a ball from one urn and move it to the other, with the probability of
choosing each ball being equal, 1/N. Thus, the probability of choosing a ball from a given
urn is proportional to the number of balls in that urn. Let X(t) denote the number of balls
in the left urn at time t, and suppose that X(0) = 0. Then X(1) = 1, since a ball must be
drawn from the right urn and moved to the left one.
(a) Let N = 100. What are the possible values for X(2), X(3), and X(4), and what is the
probability of each?
At step 2, with probability 1/100, the ball in the left urn is moved to the right
urn, making X(2) = 0; with probability 99/100, a ball from the right urn is
moved to the left urn, making X(2) = 2.
At step 3: If X(2) = 0, then with probability 1, X(3) = 1. If X(2) = 2, then
with probability 2/100, X(3) = 1, while with probability 98/100, X(3) = 3.
4
Friday, September 14, 12
0 0.5 1 1.5 2 2.5 3 3.5 4 −1.5
−1
−0.5
0
0.5
1
plot of (4x sin(x) − 3)/(2 + x2
)
0.933 0.9332 0.9334 0.9336 0.9338 0.934 0.9342 −1
−0.5
0
0.5
1
1.5
x 10−3 zoomed view
6. Plot each of the functions below over the range specified. Produce 4 plots on the same page
using the subplot command.
(a) f(x) = |x 1| for 3 x 3. (Use abs in MATLAB)
(b) f(x) = p|x| for 4 x 4. (Use sqrt in MATLAB)
(c) f(x) = ex2
= exp(x2) for 4 x 4. (Use exp in MATLAB)
(d) f(x) = 1
10×2 + 1
for 2 x 2
The following code produces the plots below:
% (a)
x = [-3:.01:3]; fx = abs(x-1);
subplot(2,2,1)
plot(x,fx)
title(’abs(x-1)’)
% (b)
x = [-4:.01:4]; fx = sqrt(abs(x));
subplot(2,2,2)
plot(x,fx)
title(’sqrt(abs(x))’)
% (c)
x = [-4:.01:4]; fx = exp(-x.^2);
subplot(2,2,3)
plot(x,fx)
title(’exp(-x^2)’)
12
Problem 3
Chapt 2
Friday, September 14, 12
This exercise uses the MATLAB M-file koch.m, which you will find on the web page. The
M-file contains all the necessary commands to create the fractal, except for the necessary
plotting commands. Edit this M-file so that each stage of the fractal is plotted. (Hint: This
can be accomplished by adding a plot command just before the completion of the outer for
loop.) Add the following commands to keep consistency between plots in the animation:
axis([-0.75 0.75 -sqrt(3)/6 1]);
axis equal
Note that the cla command clears the axes. Finally, add the command pause(0.5) in
appropriate places to slow the animation. (The fill command, as opposed to plot, produced
the filled fractals depicted above.) We will create fractals using Newton’s Method in Chapter
??.
The following modified code plots the stages of Koch’s snowflake, pausing briefly
after each stage:
%
% Plot stages 0 through n of Koch’s Snowflake
%
% For more information on Koch’s Snowflake, see:
% http://mathworld.wolfram.com/KochSnowflake.html
%
x = [-1/2 0 1/2 -1/2]; y = [0 1 0 0];
n = 4;
for i = 1:n,
k = length(x);
v = zeros(4*k-3);
w = zeros(4*k-3);
for j = 1:k-1,
v(4*j – 3) = x(j);
w(4*j – 3) = y(j);
dirx = x(j+1) – x(j);
diry = y(j+1) – y(j);
v(4*j – 2) = x(j) + 1/3*dirx;
w(4*j – 2) = y(j) + 1/3*diry;
orthox = -diry;
orthoy = dirx;
v(4*j – 1) = x(j) + 1/2*dirx + 1/3*1/2*sqrt(3)*orthox;
w(4*j – 1) = y(j) + 1/2*diry + 1/3*1/2*sqrt(3)*orthoy;
15
theta = linspace(0, 2*pi, 1000);
% First circle
r = sqrt(2);
x = 2 + r*cos(theta);
y = 1 + r*sin(theta);
plot(x,y)
axis equal
hold on
% Second circle
r = sqrt(3.5);
x = 2.5 + r*cos(theta);
y = r*sin(theta);
plot(x,y)
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
−1.5
−1
−0.5
0
0.5
1
1.5
2
8. In this exercise, you will plot initial stages of a process that creates a fractal known as Koch’s
Snowflake, which is depicted below.
Koch’s Snowflake
Stage 0 Stage 1 Stage 2
14
Chapt 2
Problem 4
4.
Friday, September 14, 12
reaches 1 and a renormalization is performed, there are fewer nonzero bits in the
significand. Eventually, the significand must contain all 0’s and then when the
exponent reaches 0, the number stays there at 1.
Note that the only rounding error made in the example at the beginning of this
chapter was in rounding the input 1/10. The observed behavior matches that of
the exact algorithm when applied not to 1/10 but to round(1/10).
12. The total resistance of an electrical circuit with two resistors connected in parallel, with
resistances R1 and R2 respectively, is given by the formula
T = 1
1
R1 + 1
R2
.
R
1 R2
If R1 = R2 = R, then the total resistance is R/2 since half of the current flows through
each resistor. On the other hand, if R2 is much less than R1, then most of the current will
flow through R2 but a small amount will still flow through R1 so the total resistance will
be slightly less than R2. What if R2 = 0? Then T should be 0 since if R1 6= 0, then all of
the current will flow through R2, and if R1 = 0 then there is no resistance anywhere in the
circuit. If the above formula is implemented using IEEE arithmetic, will the correct answer
be obtained when R2 = 0? Explain your answer.
YES. 1/R2 will be set to +1. If R1 6= 0, then 1/R1 will be a number while if
R1 = 0 then 1/R1 will also be set to +1. In either case, 1/R1 + 1/R2 will be +1,
and then 1/(1/R1 + 1/R2) will be 0.
13. In the 7th season episode Treehouse of Horror VI of The Simpsons, Homer has a nightmare
in which the following equation flies past him
178212 + 184112 = 192212. (6)
Note that this equation, if true, would contradict Fermat’s Last Theorem, which states: For
n 3, there do not exist any natural numbers x, y and z that satisfy the equation xn+yn = zn.
Did Homer dream up a counterexample to Fermat’s Last Theorem?
(a) Compute 12p
178212 + 184112 by typing the following into MATLAB:
format short
(1782^12 + 1841^12)^(1/12)
What result does Matlab report? Now look at the answer using format long.
66
Problem 5
Chapt 5
MATLAB returns the answer 1.9220e + 03 (i.e., 1922), or, with format long
1.921999999955867e + 03 (which is very close to 1922).
(b) Determine the absolute and relative error in the approximation 178212+184112 ⇡ 192212.
[Such an example is called a Fermat near-miss because of the small relative error. This
example was created by The Simpsons writer David S. Cohen with the intent of catching
the eye of audience members with a mathematical interest.]
The absolute error is |178212 + 184112 192212| ⇡ 7 ⇥ 1029, while the relative
error is this number divided by 192212, or, about 3 ⇥ 1010.
(c) Note that the right-hand side of equation (6) is even. Use this to prove that the equation
cannot be true.
Since the right-hand side is even and the left-hand side – being the sum of an
even number and an odd number – is odd, the two cannot be equal.
(d) In a later episode entitled The Wizard of Evergreen Terrace, Homer writes the equation
398712 + 436512 = 447212. Can you debunk this equation?
Each of the numbers 3987 and 4365 is divisible by 3, but 4472 is not divisible
by 3. Thus the left-hand side is divisible by 312 but the right-hand side is not,
so the two cannot be equal.
14. In the 1999 movie Oce Space, a character creates a program that takes fractions of cents
that are truncated in a bank’s transactions and deposits them to his own account. This is not
a new idea, and hackers who have actually attempted it have been arrested. In this exercise
we will simulate the program to determine how long it would take to become a millionaire
this way.
Assume that we have access to 50,000 bank accounts. Initially we can take the account
balances to be uniformly distributed between, say, $100 and $100,000. The annual interest
rate on the accounts is 5%, and interest is compounded daily and added to the accounts,
except that fractions of a cent are truncated. These will be deposited to an illegal account
that initially has balance $0.
Write a MATLAB program that simulates the Oce Space scenario. You can set up the
initial accounts with the commands:
accounts = 100 + (100000-100)*rand(50000,1); % Sets up 50,000 accounts with balances
% between $100 and $100000.
accounts = floor(100*accounts)/100; % Deletes fractions of a cent from
% initial balances.
(a) Write a MATLAB program that increases the accounts by (5/365)% interest each day,
truncating each account to the nearest penny and placing the truncated amount into an
account, which we will call the illegal account. Assume that the illegal account can hold
fractional amounts (that is, do not truncate this account’s values) and let the illegal
account also accrue daily interest. Run your code to determine how many days it would
take to become a millionaire assuming the illegal account begins with a balance of zero.
67
MATLAB returns the answer 1.9220e + 03 (i.e., 1922), or, with format long
1.921999999955867e + 03 (which is very close to 1922).
(b) Determine the absolute and relative error in the approximation 178212+184112 ⇡ 192212.
[Such an example is called a Fermat near-miss because of the small relative error. This
example was created by The Simpsons writer David S. Cohen with the intent of catching
the eye of audience members with a mathematical interest.]
The absolute error is |178212 + 184112 192212| ⇡ 7 ⇥ 1029, while the relative
error is this number divided by 192212, or, about 3 ⇥ 1010.
(c) Note that the right-hand side of equation (6) is even. Use this to prove that the equation
cannot be true.
Since the right-hand side is even and the left-hand side – being the sum of an
even number and an odd number – is odd, the two cannot be equal.
(d) In a later episode entitled The Wizard of Evergreen Terrace, Homer writes the equation
398712 + 436512 = 447212. Can you debunk this equation?
Each of the numbers 3987 and 4365 is divisible by 3, but 4472 is not divisible
by 3. Thus the left-hand side is divisible by 312 but the right-hand side is not,
so the two cannot be equal.
14. In the 1999 movie Oce Space, a character creates a program that takes fractions of cents
that are truncated in a bank’s transactions and deposits them to his own account. This is not
a new idea, and hackers who have actually attempted it have been arrested. In this exercise
we will simulate the program to determine how long it would take to become a millionaire
this way.
Assume that we have access to 50,000 bank accounts. Initially we can take the account
balances to be uniformly distributed between, say, $100 and $100,000. The annual interest
rate on the accounts is 5%, and interest is compounded daily and added to the accounts,
except that fractions of a cent are truncated. These will be deposited to an illegal account
that initially has balance $0.
Write a MATLAB program that simulates the Oce Space scenario. You can set up the
initial accounts with the commands:
accounts = 100 + (100000-100)*rand(50000,1); % Sets up 50,000 accounts with balances
% between $100 and $100000.
accounts = floor(100*accounts)/100; % Deletes fractions of a cent from
% initial balances.
(a) Write a MATLAB program that increases the accounts by (5/365)% interest each day,
truncating each account to the nearest penny and placing the truncated amount into an
account, which we will call the illegal account. Assume that the illegal account can hold
fractional amounts (that is, do not truncate this account’s values) and let the illegal
account also accrue daily interest. Run your code to determine how many days it would
take to become a millionaire assuming the illegal account begins with a balance of zero.
67
MATLAB returns the answer 1.9220e + 03 (i.e., 1922), or, with format long
1.921999999955867e + 03 (which is very close to 1922).
(b) Determine the absolute and relative error in the approximation 178212+184112 ⇡ 192212.
[Such an example is called a Fermat near-miss because of the small relative error. This
example was created by The Simpsons writer David S. Cohen with the intent of catching
the eye of audience members with a mathematical interest.]
The absolute error is |178212 + 184112 192212| ⇡ 7 ⇥ 1029, while the relative
error is this number divided by 192212, or, about 3 ⇥ 1010.
(c) Note that the right-hand side of equation (6) is even. Use this to prove that the equation
cannot be true.
Since the right-hand side is even and the left-hand side – being the sum of an
even number and an odd number – is odd, the two cannot be equal.
(d) In a later episode entitled The Wizard of Evergreen Terrace, Homer writes the equation
398712 + 436512 = 447212. Can you debunk this equation?
Each of the numbers 3987 and 4365 is divisible by 3, but 4472 is not divisible
by 3. Thus the left-hand side is divisible by 312 but the right-hand side is not,
so the two cannot be equal.
14. In the 1999 movie Oce Space, a character creates a program that takes fractions of cents
that are truncated in a bank’s transactions and deposits them to his own account. This is not
a new idea, and hackers who have actually attempted it have been arrested. In this exercise
we will simulate the program to determine how long it would take to become a millionaire
this way.
Assume that we have access to 50,000 bank accounts. Initially we can take the account
balances to be uniformly distributed between, say, $100 and $100,000. The annual interest
rate on the accounts is 5%, and interest is compounded daily and added to the accounts,
except that fractions of a cent are truncated. These will be deposited to an illegal account
that initially has balance $0.
Write a MATLAB program that simulates the Oce Space scenario. You can set up the
initial accounts with the commands:
accounts = 100 + (100000-100)*rand(50000,1); % Sets up 50,000 accounts with balances
% between $100 and $100000.
accounts = floor(100*accounts)/100; % Deletes fractions of a cent from
% initial balances.
(a) Write a MATLAB program that increases the accounts by (5/365)% interest each day,
truncating each account to the nearest penny and placing the truncated amount into an
account, which we will call the illegal account. Assume that the illegal account can hold
fractional amounts (that is, do not truncate this account’s values) and let the illegal
account also accrue daily interest. Run your code to determine how many days it would
take to become a millionaire assuming the illegal account begins with a balance of zero.
67
Friday, September 14, 12
x0=5, x1=4.908422e+00, fx0=-5, fx1=7.402024e+00
x0=4.908422e+00, x1=4.963079e+00, fx0=7.402024e+00, fx1=2.808942e-01
x0=4.963079e+00, x1=4.965235e+00, fx0=2.808942e-01, fx1=-1.675050e-02
x0=4.965235e+00, x1=4.965114e+00, fx0=-1.675050e-02, fx1=3.473149e-05
x0=4.965114e+00, x1=4.965114e+00, fx0=3.473149e-05, fx1=4.280999e-09
c =
4.965114231713327e+00
The error at step k+1 of the secant method is approximately equal to a constant
times the product of the errors at steps k and k 1, and if we assume that the
absolute value of fx1 printed above is something like the error, we can estimate
from the computed values that the constant is about 0.007. Thus the error at the
next step would be approximately 0.007 ⇥ 4.281 ⇥ 109 ⇥ 3.473 ⇥ 105 ⇡ 1015.
The error at the step after that would well below 1016. Thus, it would probably
take 2 more steps of the secant method to achieve the tolerance of 1016.
3. Newton’s method can be used to compute reciprocals, without division. To compute 1/R,
let f(x) = x1 R so that f(x) = 0 when x = 1/R. Write down the Newton iteration for
this problem and compute (by hand or with a calculator) the first few Newton iterates for
approximating 1/3, starting with x0 = 0.5, and not using any division. What happens if you
start with x0 = 1? For positive R, use the theory of fixed point iteration to determine an
interval about 1/R from which Newton’s method will converge to 1/R.
Newton’s method is
xk+1 = xk f(xk)
f0
(xk) = xk x1
k R
x2
k
= 2xk Rx2
k.
Thus, one can implement the recurrence without doing any division. Taking R = 3
and x0 = 0.5, one finds: x1 = 0.25, x2 = 0.3125, x3 = 0.3320, x4 = 0.3333. If you
start with x0 = 1, then you find x1 = 1, x2 = 5, x3 = 85, etc., and the method
diverges.
Newton’s method is fixed point iteration for the problem ‘(x) ⌘ 2x Rx2 = x.
Since ‘0
(x)=2 2Rx, we will have |’0
(x)| < 1 if 3 2R >x> 1
2R . Since this interval
is centered about the fixed point 1
R , it follows that if x0 2 ⇥ 1
2R + ,
3
2R
⇤
for any
> 0, then Newton’s method will converge to 1
R .
4. Use Newton’s method to approximate p2 to 6 decimal places.
Letting f(x) = x2 2 and using Newton’s method to solve f(x) = 0, with initial
guess x0 = 1, we find: x1 = 1.5, x2 = 1.416667, x3 = 1.414216, x4 = 1.414214, and
x4 is accurate to 6 decimal places (in fact the error in x4 is about 1012).
51
Problem 6
Chapt 4
x0=5, x1=4.908422e+00, fx0=-5, fx1=7.402024e+00
x0=4.908422e+00, x1=4.963079e+00, fx0=7.402024e+00, fx1=2.808942e-01
x0=4.963079e+00, x1=4.965235e+00, fx0=2.808942e-01, fx1=-1.675050e-02
x0=4.965235e+00, x1=4.965114e+00, fx0=-1.675050e-02, fx1=3.473149e-05
x0=4.965114e+00, x1=4.965114e+00, fx0=3.473149e-05, fx1=4.280999e-09
c =
4.965114231713327e+00
The error at step k+1 of the secant method is approximately equal to a constant
times the product of the errors at steps k and k 1, and if we assume that the
absolute value of fx1 printed above is something like the error, we can estimate
from the computed values that the constant is about 0.007. Thus the error at the
next step would be approximately 0.007 ⇥ 4.281 ⇥ 109 ⇥ 3.473 ⇥ 105 ⇡ 1015.
The error at the step after that would well below 1016. Thus, it would probably
take 2 more steps of the secant method to achieve the tolerance of 1016.
3. Newton’s method can be used to compute reciprocals, without division. To compute 1/R,
let f(x) = x1 R so that f(x) = 0 when x = 1/R. Write down the Newton iteration for
this problem and compute (by hand or with a calculator) the first few Newton iterates for
approximating 1/3, starting with x0 = 0.5, and not using any division. What happens if you
start with x0 = 1? For positive R, use the theory of fixed point iteration to determine an
interval about 1/R from which Newton’s method will converge to 1/R.
Newton’s method is
xk+1 = xk f(xk)
f0
(xk) = xk x1
k R
x2
k
= 2xk Rx2
k.
Thus, one can implement the recurrence without doing any division. Taking R = 3
and x0 = 0.5, one finds: x1 = 0.25, x2 = 0.3125, x3 = 0.3320, x4 = 0.3333. If you
start with x0 = 1, then you find x1 = 1, x2 = 5, x3 = 85, etc., and the method
diverges.
Newton’s method is fixed point iteration for the problem ‘(x) ⌘ 2x Rx2 = x.
Since ‘0
(x)=2 2Rx, we will have |’0
(x)| < 1 if 3 2R >x> 1
2R . Since this interval
is centered about the fixed point 1
R , it follows that if x0 2 ⇥ 1
2R + ,
3
2R
⇤
for any
> 0, then Newton’s method will converge to 1
R .
4. Use Newton’s method to approximate p2 to 6 decimal places.
Letting f(x) = x2 2 and using Newton’s method to solve f(x) = 0, with initial
guess x0 = 1, we find: x1 = 1.5, x2 = 1.416667, x3 = 1.414216, x4 = 1.414214, and
x4 is accurate to 6 decimal places (in fact the error in x4 is about 1012).
51
Chapt 4
Problem 7
Friday, September 14, 12
