Home Work TWO

  1. 2.4


    $\displaystyle x^2-1=E^x,  x\simeq -1.14776,$

    $\displaystyle \sin(x)=1-x^2,  x\simeq 0.636733,$

    $\displaystyle x^2+2x =\frac{1}{1+x^2}, x\simeq 0.37081,$

    $\displaystyle E^{-x}=x^3, x\simeq 0.772883,$

    $\displaystyle \ln(x)=2-x^2, \simeq 1.3141,$

    $\displaystyle \sin(x)=2\sin(x+\frac{\pi}{4}), x\simeq 1.85572.$


    Start bisection from

    1. $ x^2-1=E^x,  -3<x<3,$ one root
    2. $ \sin(x)=1-x^2, 0<x<1,$ there are two roots with $ \lim\limits_{x\to\pm\infty} f(x)=\infty,$, and 0 is between these two roots
    3. $ x^2+2x =\frac{1}{1+x^2},  0<x<1$, as in the previous example
    4. $ E^{-x}=x^3, -1<x<1$, as there is one root only
    5. $ \ln(x)=2-x^2,  0<x<2,$ one root
    6. $ \sin(x)=2\sin(x+\frac{\pi}{4}), 0<x<3$, two roots with $ \lim\limits_{x\to\pm\infty} f(x)=\infty,$


    For the example $ A$ the Newton formula is

    $\displaystyle x_{k+1} = x_k - \frac{x_k^2 - 1 -E^{x_k}}{2 x_k - E^{x_k}},$

    with the good starting point $ x=-0.5$. This starting point will quickly leed to the solution


    For the example $ A$ the Secant formula is

    $\displaystyle x_{k+1} = x_k - \frac{(x_k^2 - 1 -E^{x_k})(x_k-x_{k-1})}
{x_k - E^{x_k} - x_{k-1} + E^{x_{k-1}}},$

    with the good starting points $ 0, -\frac{1}{2}.$

    e Solutions are stated above, the example of bisection and Newton codes were provided during lectures. Good stopping criteria would be, for example,

    $\displaystyle \vert f(x)\vert\le 10^{-16}.$

  2. 2.9 a-c


    Suppose $ y$ is given, and we now how to calculate $ g(x)$, we want to sove for $ x$ the equation $ y=g(x)$. In other words, we want to find 0 of $ f(x)=y-g(x)$. Then the Newtow formula is indeed

    $\displaystyle x_{k+1} = x_k - \frac{y-g(x)}{-g'(x)},$

    which leads to the formula in the text book.


    We now need to evaluate $ E^2$, using only $ \ln(x)$ function. This gives

    $\displaystyle x_{k+1} = x_k + x_k (2-\ln(x_k)).$

    Similarly, to evaluate $ E^{-3}$ we use

    $\displaystyle x_{k+1} = x_k +x_k (-3 -\ln(x)).$


    Similarly, to calculate $ \arccos({\frac{1}{2}})$, we use

    $\displaystyle x_{k+1} = x_k - \frac{\frac{1}{2}-\cos(x_k)}{\sin(x_k)}.$

    Also, to calculate $ \arccos({\frac{1}{3}})$, we use

    $\displaystyle x_{k+1} = x_k - \frac{\frac{1}{3}-\cos(x_k)}{\sin(x_k)}.$

  3. 2.10

    a To answer this question, please think about convergence rates. If convergence rate is quadratic, as it is for the Newtwon method, then the error is squared at each iteration. Since the $ f(x)=1$ in the end of iterations, then in Method one the error is $ .1$ at first iteration, $ 0.01$ at second and $ 0.0001$ at the third iteration. Since the error is squared, than with out shadow of a doubt the first method is Newton iterations

    b I would say that the Bisection is the Method 3, since the error is halved at each iteration. Indeed, the error is $ 0.05$ initially, then $ 0.025$, and then $ 0.0125$ which is exactly a half at each iteration

    c Method 3 can not be Secant, since the error is only halved at each iteration. Secant should converge faster, so I would guess that Secant is Method 2.

  4. 2.22


    Approximating the function $ f(x)$ by a second degree polynomial, we obtain

    $\displaystyle f(x)\simeq f(x_k) + f'(x_k)(x-x_k)+f''(x_k)(x-x_k)^2/2.$

    We now solve where this crosses the $ x$ axis to obtain

    $\displaystyle x_{k+1} = x_k + \frac{-f'(x_k)\pm\sqrt{(f'(x_k))^2 - 2 f''(x_k) f(x_k)}}

    There is a $ \pm $, since one needs to solve quadratic equation to obtain $ x_{k+1}$.

    b The biggest disadvantage of this formula is that it has two roots. This is natural, since the parabola may cross the $ x$ axis in two places. The second big disadvantage of this formula is that it may not cross $ x$ at all, i.e. the quadratic equation may have no real roots. Finally, the third big disadvantage is that the formula contains $ f''(x)$, i.e. one need to know analytically the second derivative of $ f(x)$.


    We need to chose a solution that is closest to the solution one would obtain if $ f''(x)$ were to be equal to zero. In other words, one should choose a solution that is closest to the solution obtained by the Newton method. By using the Taylor expansion, we see that the correct choice is
    “+” if $ f'(x_k)>0,$
    “-” if $ f'(x_k)<0.$
    In other words, the sign in front of the radical should be the sign of $ f'(x_k)$. Then this formula will reduce to Newton formula (PLEASE MAKE SURE YOU CAN ACTUALLY SEE THIS!).

    d The fastest way to derive the Halley method is to apply the Newton formula to the function

    $\displaystyle g(x) = \frac{f(x)}{\sqrt{\vert f'(x)}},$

    since any root of $ g(x)$ that is not a root of $ g'(x)$ is also a root of $ f(x)$.

    e Since the Newton formula is

    $\displaystyle x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)},$

    we can equivalently rewrite it as

    $\displaystyle (x_{k+1} - x_{k})=- \frac{f(x_k)}{f'(x_k)}.$

    The resulting formula for Halley method is therefore $ x_{k+1}$

    $\displaystyle x_{k+1} = x_k - \frac{2 f(x_k) f'(x_k)}{2(f'(x_k))^2 -f(x_k)f''(x_k)}.

  5. (2.27)


    Since $ \epsilon_i = x_i - {\bar{x}}, $ we get

    $\displaystyle f(x_i) = f({\bar x}+\epsilon_i)
\simeq f({\bar x})+\epsilon_i f'({\bar x}) +\epsilon^2/2 f''({\bar x}) +
\epsilon^3/6 f'''({\bar x}) +\dots,$


    $\displaystyle f'(x_i) = f'({\bar x}+\epsilon_i) \simeq f'({\bar x})+\epsilon_i
...({\bar x}) +\epsilon^2/2 f'''({\bar x}) + \epsilon^3/6
f''''({\bar x}) +\dots.$

    Now assuming $ f({\bar x})=f''({\bar x})=0$ with $ f'''({\bar x})\ne 0$, and keeping terms only up to $ f'''({\bar x})$ inclusively, we divide these two expressions to obtain, in leading order,

    $\displaystyle \frac{f(x_i)}{f'(x_i)} = \epsilon \frac{1+\epsilon^2 \frac{f'''}{...
...''}{2f'}}\simeq \epsilon( 1-\epsilon^2 \frac{f'''({\bar x})}{3f'({\bar{x}})}



    $\displaystyle f({\bar x})=f'({\bar x})=0$

    then the above expressions are replaced by

    $\displaystyle f(x_i) =
\simeq \epsilon^2/2 f''({\bar x}) +
\epsilon^3/6 f'''({\bar x}) +\dots,$


    $\displaystyle f'(x_i) =\simeq \epsilon_i f''({\bar x}),$

    so that

    $\displaystyle \frac{f(x_i)}{f'(x_i)}\simeq\frac{\epsilon}{2}.$

    Consequently, the formula for Newton method

    $\displaystyle x_{i+1}=x_i - \frac{f(x_i)}{f'(x_i)},$


    $\displaystyle e_i = e_i - \frac{e_i}{2}=\frac{e_i}{2}$

    , which implies linear convergence.

  6. (2.28)

    (a) The Newton method

    $\displaystyle x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)},$


    $\displaystyle f(x) = x^2 -a$

    is given by

    $\displaystyle x_{k+1}= x_k - \frac{x_k^2 -a }{2 x_k},$

    simplifies to

    $\displaystyle x_{k+1}= x_k/2 + \frac{ a }{2 x_k},$


    Using $ a_f = m\times 2^E$ with

    $\displaystyle m = 1+\frac{b_1}{2}+\frac{b_2}{4}\dots,$


    $\displaystyle \sqrt{1+y} = 1 +\frac{y}{2}-\frac{y^2}{8},$

    we change variables as $ m = 1+(1-m)$ we get

    $\displaystyle \sqrt{a_f} = \sqrt{m}\times 2^{\frac{E}{2}}\simeq
+\dots)*2 ^{\frac{E}{2}}.$

    Here the $ \frac{y^2}{8}$ term is not taken into account.



    $\displaystyle 28=(1+\frac{1}{2}+\frac{1}{2^2})\times 2^4,$

    we obtain

    $\displaystyle \sqrt{28}\simeq (1+\frac{1}{4}+\frac{1}{8})*2^2
= \frac{11}{2}.$

    This compares well with $ \sqrt{28}\simeq 5.2915$.

    d For the case of $ 50=(1+1/2+1/2^4)\times 2^5$, we write it as $ 50\simeq (1+1/2)\times 2^4 \times 2$, to obtain

    $\displaystyle \sqrt{50}\simeq \sqrt{1+1/2}\times 2^2\times\sqrt{5} \simeq
(1+1/4)\times 2^2 \times \sqrt{2}.$

    This evaluates to $ 7.07107$ which is remarkably close to $ \sqrt{50}\simeq 7.0710678118654752440$.