Starting from:
$29
Homework 1-The Fibonacci numbers
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.
1 1 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 j1 seasons because each of these branches produces exactlyone 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.
0 1 5
bar home
24 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(x1)+.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 2 3 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.
0 1 5
bar home
24 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(x1)+.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 2 3 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.
0 1 5
bar home
24 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(x1)+.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 2 3 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(x1)v(x) R
=
v(x)v(x + 1) R
. Multiplying by R and combining like terms we see that v(x)=.5v(x1) + .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(x1)+.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(x1)v(x) Rx1,x = v(x)v(x + 1) Rx,x+1 . Expressing v(x) in terms of v(x1) and v(x + 1), we have
v(x)=
Rx,x+1 Rx,x+1 + Rx1,x
v(x1) +
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)=|x1| for 3x3. (Use abs in MATLAB) (b) f(x)=p|x| for 4x4. (Use sqrt in MATLAB) (c) f(x)=ex2 = exp(x2) for 4x4. (Use exp in MATLAB) (d) f(x)= 1 10x2 +1 for 2x2
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
R 2
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. IfR1 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 n3, 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 12 p178212 + 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 k1, 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 whenx =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) ⌘ 2xRx2 = x. Since '0(x)=22Rx, 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 k1, 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 whenx =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) ⌘ 2xRx2 = x. Since '0(x)=22Rx, 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
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.
1 1 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 j1 seasons because each of these branches produces exactlyone 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.
0 1 5
bar home
24 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(x1)+.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 2 3 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.
0 1 5
bar home
24 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(x1)+.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 2 3 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.
0 1 5
bar home
24 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(x1)+.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 2 3 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(x1)v(x) R
=
v(x)v(x + 1) R
. Multiplying by R and combining like terms we see that v(x)=.5v(x1) + .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(x1)+.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(x1)v(x) Rx1,x = v(x)v(x + 1) Rx,x+1 . Expressing v(x) in terms of v(x1) and v(x + 1), we have
v(x)=
Rx,x+1 Rx,x+1 + Rx1,x
v(x1) +
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)=|x1| for 3x3. (Use abs in MATLAB) (b) f(x)=p|x| for 4x4. (Use sqrt in MATLAB) (c) f(x)=ex2 = exp(x2) for 4x4. (Use exp in MATLAB) (d) f(x)= 1 10x2 +1 for 2x2
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
R 2
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. IfR1 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 n3, 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 12 p178212 + 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 k1, 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 whenx =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) ⌘ 2xRx2 = x. Since '0(x)=22Rx, 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 k1, 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 whenx =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) ⌘ 2xRx2 = x. Since '0(x)=22Rx, 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
1 file (2.0MB)
