Iteration: Newton-Raphson Method

[aznkid310]

Homework Statement

For the exercise to work correctly you’ll need to carry 16 decimal places – double
precision.

Q1) Find the value of x that satisfies
x = ln(2 + x)
Begin with x(0) = 2, and try the iteration scheme
x(k+1) = ln(2 + x(k)):
If this method converges (lets say lim x(k) as =>inf = e), determine it’s order. Repeat the
calculation, and plot log (x(k) -e) on the y-axis against log (x(k-1) -e) on the x axis.

Q2) Solve (1) using the Newton-Raphson method, again beginning with x(0) = 2.
Graph log (x(k) -e) on the y-axis against log (x(k-1) -e) to determine the order of convergence.

Q3) Repeat Q3 with x(0) = -1.999

Point: for a problem with multiple roots, the solution will depend on the starting
point.

Q4) What happens with Newton-Raphson for -1:62 < x(0) < -1:01?

Point: Newton-Raphson converges rapidly when it converges, but convergence is
not guaranteed.

Q5) Use the naive method of Q1 to solve (1) beginning with x(0) = -1:5.

Point: Regions of convergence depend on the function and the method.

Homework Equations

For#1, am I suppose to just use brute force and iterate?

Also, can someone walk me through a few steps of this method? I am not really understanding how to do this?

The Attempt at a Solution

#1) Using MATLAB, i get x= 1.14619321999999 with a difference of about

4.233406958320529e-010. Is this close enough?

 

[D H]

You are supposed to calculate each of the iterates for two different estimation techniques, one being the approach in question 1, $x_{k+1} = \ln(2+x_k)$, and other being Newton-Raphson. The end result is only a small part of the problem. 4.233406958320529e-010 is not "close enough". You were explicitly asked to carry 16 decimal places.

 

[mathmate]

Q3) Repeat Q3 with x(0) = -1.999

This sounds like a recursive question. ;)
Would you please clarify if the repeat is on Q1 or Q2?

 

[mathmate]

For Q1, you will use the brute force iterative method. If you are using MATLAB, you have the option of using a loop and get out when the error is small enough. So it is not as brute force as it may seem.
Also, don't forget to either print or plot the residue (error) at every iteration as requested at the end of Q1.

 

[aznkid310]

This sounds like a recursive question. ;)
Would you please clarify if the repeat is on Q1 or Q2?

Sorry, Q3 should read: Repeat Q2 with x(0) = -1.999

 

[aznkid310]

Here is my code for part 1. Can someone help me check this? I am not sure if it's correct

clc, clear;
format compact;
format long
x = 2;
for count = 1:100 %Number of Iterations
a = log(2+x); %left hand side of equation
b = x; %right hand side of equation
if (a==b)
disp(x)
disp(count) %Number of iterations needed to get to answer
answer = x;
break;
end
x = a; %Answer
end

f = 2; %x(k=0) = 2
for k = 1:count
d = log(2+f);
e = f;
c = d-answer; %x(k)-a, where a is my answer (for convergence)
axisy(k) = c; %put answers in an array
f = d;
end

g = log(-answer);
for k = 1:count
h = log(2+g);
i = g;
j = h-answer; x(k-1)-a, where a is the convergent answer
axisx(k) = j;
g = h;
end

loglog(axisx,axisy)

2)For Newton-Raphson, is my f(x) = ln(2+x)-x?

then i use g(x)=x(k) - f(x)/f('x)

=x(k)-[ ln(2+x)-x] / (1/(2+x)+1) ?

Im not sure how to write a code for this. I've searched online and have found a few codes, but nothing that I need
Should I do this by hand instead?

 

[mathmate]

If MATLAB is part of your coursework, you would probably be obliged to use it. If not, it would be an option, but probably a costly one in time.
If you post your results from MATLAB or hand calculations, I would be pleased to check the answer for you.

 

[mathmate]

Hint: to get an accuracy of 15 decimal places, you would need about 31 iterations for Q1, and the first few digits are: 1.1461932206...
Therefore I think hand calculations are too prohibitive, as I have not yet found calculators of 15+ digits of accuracy.
Edit:
For your information, the primitive iteration method requires 202 iterations to get 100 decimal digits of accuracy, while Newton's method in Q2 requires only 8!

 

[mathmate]

In floating point calculations, a==b will almost never be true because of rounding inaccuracies. You will need to compare the absolute value of the difference with the accuracy (eps) required. In your case,
eps=1.0E-15
So the comparison should read something like:

if abs(a-b)<eps

2)For Newton-Raphson, is my f(x) = ln(2+x)-x?

This is correct.

then i use g(x)=x(k) - f(x)/f('x)
9(x)=x(k)-[ ln(2+x)-x] / (1/(2+x)+1)

You have made a mistake in the sign of the derivative of -x.
g(x) should be equal to x(k)-[ ln(2+x)-x] / (1/(2+x)-1)

For the Newton's method, you proceed as in Q1, except that the values of a and b would be:

a=2.0
for count...
b=g(a)
if abs(a-b)<eps
...
a=b

 

[aznkid310]

for the code I wrote, i got x = 1.14619322062058 and it took 34 iterations

I tried following what you said, but I was unable to get the correct answer. Could you guide me along a bit more? Sorry for being a little slow; it has been a while since I had to do programming of any sort. Here was my attempt

for count = 1:50
a = 2;
g(a)=a-[log(2+a)/((1/2+a)-1)]
b = g(a);
if (a-b)<eps
disp(a)
disp(count)
end
a=b;
end

 

[D H]

You have an error in your update function g(a).

The function at hand is

$$f(x)=\ln(2+x)-x$$

Differentiating,

$$f'(x)=\frac{1}{2+x}-1$$

The k+1^th Newton-Raphson iterate is

$$\aligned x_{k+1} &= x_k - \frac{f(x_k)}{f'(x_k)} \\ &= x_k - \frac{\ln(2+x_k)-x_k}{1/(2+x_k)-1} \aligned$$

Compare this to your code, where you have

g(a)=a-[log(2+a)/((1/2+a)-1)]

 

[aznkid310]

sorry it should have been g(a)=a-([log(2+a)-a)/((1/2+a)-1)]

But even using this, i get:

g =
0 2.40913709258674
2
1

 

[D H]

Look at the denominator.

 

[mathmate]

 for the code I wrote, i got x = 1.14619322062058 and it took 34 iterations

The value of x is correct. Excellent work!
There could be a minor variation of the number of iterations depending on whether the termination condition is based on the latest value or not.

Some minor corections to the Q2 code are required, including the starting value of a & b should be initialized outside of the loop, and the exit condition tested with a while statement.
Note that the line that defines the value of b inside the while-loop has to be edited as per DH's post.
Check the code and the results, as I do not have Matlab.

a=0
b=2
% initialize count here
eps=1E-15  % accuracy required
while abs(a-b)<eps  % test exit condition
a=b
b=a-[log(2+a)/((1/2+a)-1)]   % this line to be corrected as per DH's post
% increment count here
disp(b)
disp(count)
end

 

[aznkid310]

clc, clear;
format compact;
format long
a=0;
b=2;
for count = 1:50 % initialize count here
if abs(a-b)<eps % test exit condition
a=b;
b=a-[log(2+a)/((1/(2+a)-1))];
% increment count here
disp(b)
disp(count)
end
end

I have corrected the denominator (thx DH), am when I enter that code in, i get no output

 

[D H]

That you get no output is a *huge* hint that you have done something wrong. That means that that section of the code is never reached.

You don't need Matlab to run your code. You can run it yourself, on paper. Walk through your code and see what it does.

 

[mathmate]

Walk through your code and see what it does.

Good idea! Do not forget to study the difference between a for-loop and a while-loop!

 

[aznkid310]

clc, clear;
format compact;
format long
a=0;
b=2;
for count = 1:50 % initialize count here % test exit condition
a=b;
b=a-[(log(2+a)-a)/((1/(2+a)-1))];
if abs(a-b)<eps % increment count here
disp(b)
disp(count)
end
end

I basically switched the order, and it gives me the correct answer. Thanks for the help!

 

[mathmate]

How many iterations did it take?

 

[aznkid310]

it took 5 iterations, which should be correct since it is less than the 'power' method

 

[mathmate]

Good work. So now you only have to print the errors at each iteration to plot the graph indicating the order of convergence to log-log scale.

Also now you should have the tools required to do the rest of the questions.

I don't know how many decimal digits Matlab can handle, but if you are interested to experiment further, the result to 38 decimal digits is:
1.14619322062058258523706102852136825279

Have a good week!