Can't make simple iteration work

Hi,

I let $\displaystyle f(x)=e^x-3x-1=0$ for $\displaystyle x\in [1,2]$ and rewrite the equation such that $\displaystyle x=ln(3x+1)$.

I then rewrite $\displaystyle f(x)=0$ to the equivalent form $\displaystyle x-g(x)=0$ where $\displaystyle g(x)=ln(3x+1)$.

Since $\displaystyle g'(x)=\frac{3}{3x+1}$ I have that $\displaystyle g'(1)=\frac{3}{4}$ and $\displaystyle g'(2)=\frac{3}{7}$.

By the mean value theorem I know that there exists a number $\displaystyle \eta\in [1,2]$ such that

$\displaystyle |g(x)-g(y)|=|g'(\eta)||x-y|$.

Since $\displaystyle g''(x)=-\frac{9}{(3x+1)^2}$, $\displaystyle g$ is monotonic decreasing and so

$\displaystyle g'(1)\geq g'(\eta) \geq g'(2)$.

$\displaystyle g$ is then a contraction with $\displaystyle L=g'(1)=\frac{3}{4}$.

I then look at the sequence $\displaystyle x_{k+1}=g(x_k)}$ and write a small piece of code that prints out the first 20 iterations.

(0, 1)

(1, 1.3862943611198906)

(2, 1.6407200993500939)

(3, 1.778701297541748)

(4, 1.846264051572333)

(5, 1.8777524625894917)

(6, 1.8920959939166664)

(7, 1.8985621417401013)

(8, 1.9014635019263759)

(9, 1.9027626111520601)

(10, 1.9033437520231324)

(11, 1.9036036091052895)

(12, 1.9037197823293694)

(13, 1.9037717150438356)

(14, 1.9037949295626633)

(15, 1.9038053065444669)

(16, 1.9038099450615822)

(17, 1.9038120184745679)

(18, 1.9038129452869204)

(19, 1.9038133595703104)

(20, 1.9038135447541562)

The maximum number of iterations I need to get an accuracy of $\displaystyle |x_k-\xi|\leq \epsilon$ where $\displaystyle x_k $is the kth iteration and $\displaystyle \xi$ is the fixed point og $\displaystyle g$ is given by:

$\displaystyle k_0(\epsilon) \leq \right[ \frac{ln|x_1-x_0| - ln(\epsilon(1-L))}{ln(1/L)}\left] +1$

If I calculate this with $\displaystyle x_1 = 1.386294$, $\displaystyle x_0=1$, $\displaystyle L=3/4$ and $\displaystyle \epsilon=0.5*10^{-4}$ (to get an accuracy of 4 decimal digits) I get approx. 41 iterations.

But from my calculation of the sequence it seems as if the number of iterations needed for an accuracy of 4 decimal digits is not more than about 15.

Funny thing is, in the book I am reading they use $\displaystyle g(x)=ln(2x+1) $and that seems to work..

Sorry for the long post, but I hope someone can help me out.