Home Work TWO

1. 2.4

   a

   $$x^2-1=E^x, x\simeq -1.14776,$$
   $$\sin(x)=1-x^2, x\simeq 0.636733,$$
   $$x^2+2x =\frac{1}{1+x^2}, x\simeq 0.37081,$$
   $$E^{-x}=x^3, x\simeq 0.772883,$$
   $$\ln(x)=2-x^2, \simeq 1.3141,$$
   $$\sin(x)=2\sin(x+\frac{\pi}{4}), x\simeq 1.85572.$$

   b

   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,$

   c

   For the example $A$ the Newton formula is

   $$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

   d

   For the example $A$ the Secant formula is

   $$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,

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

2. 2.9 a-c

   a

   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

   $$x_{k+1} = x_k - \frac{y-g(x)}{-g'(x)},$$
   which leads to the formula in the text book.

   b

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

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

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

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

   c

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

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

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

   $$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

   a

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

   $$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
   $$x_{k+1} = x_k + \frac{-f'(x_k)\pm\sqrt{(f'(x_k))^2 - 2 f''(x_k) 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)$.

   c

   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

   $$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

   $$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)},$$
   we can equivalently rewrite it as
   $$(x_{k+1} - x_{k})=- \frac{f(x_k)}{f'(x_k)}.$$
   The resulting formula for Halley method is therefore $x_{k+1}$
   $$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)

   (a)

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

   $$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,$$
   and
   $$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,
   $$\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}})} .$$

   b

   If

   $$f({\bar x})=f'({\bar x})=0$$
   then the above expressions are replaced by
   $$f(x_i) = \simeq \epsilon^2/2 f''({\bar x}) + \epsilon^3/6 f'''({\bar x}) +\dots,$$
   and
   $$f'(x_i) =\simeq \epsilon_i f''({\bar x}),$$
   so that
   $$\frac{f(x_i)}{f'(x_i)}\simeq\frac{\epsilon}{2}.$$
   Consequently, the formula for Newton method
   $$x_{i+1}=x_i - \frac{f(x_i)}{f'(x_i)},$$
   gives
   $$e_i = e_i - \frac{e_i}{2}=\frac{e_i}{2}$$
   , which implies linear convergence.

6. (2.28)

   (a) The Newton method

   $$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)},$$
   for
   $$f(x) = x^2 -a$$
   is given by
   $$x_{k+1}= x_k - \frac{x_k^2 -a }{2 x_k},$$
   simplifies to
   $$x_{k+1}= x_k/2 + \frac{ a }{2 x_k},$$

   (b)

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

   $$m = 1+\frac{b_1}{2}+\frac{b_2}{4}\dots,$$
   and
   $$\sqrt{1+y} = 1 +\frac{y}{2}-\frac{y^2}{8},$$
   we change variables as $m = 1+(1-m)$ we get
   $$\sqrt{a_f} = \sqrt{m}\times 2^{\frac{E}{2}}\simeq (1+\frac{b_1}{4}+\frac{b_2}{8} +\dots)*2 ^{\frac{E}{2}}.$$
   Here the $\frac{y^2}{8}$ term is not taken into account.

   c

   Since

   $$28=(1+\frac{1}{2}+\frac{1}{2^2})\times 2^4,$$
   we obtain
   $$\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

   $$\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$.