0

Disclaimer: I'm aware that this topic is very well documented, and I've done considerable research before asking the MST community, but most of the documentation on this topic is highly formal, and I do not have a very good grasp of formal mathematics

1.) Use three iterations of Newton's Method to approximate a zero of f(x) = x$^2$-2. Use x = 1 as the initial guess.

Here are my answer:

    x1 = 1.5

    x2 = 1.416666667

    x3 =  1.414215686

What I don't understand is how to find the multiplicity and rate of convergence.

I'm aware that formula for multiplicity is $m = (m-1)/m$.

And the formula for rates of convergence is ($x_n-x_{n-1})/(x_{n-1}-x_{n-2})$.

But I don't know how to apply either of these formulas. Thank you for any assistance.

Julián Aguirre
  • 76,354
user132761
  • 1

1 Answers1

0

Obviously, your example is not well suited for the study of multiplicities since all roots $\pm\sqrt2$ are simple.

To study the convergence behavior, extend your output to a table that includes

$x_k$, $f(x_k)$, $Δx_k$, $\ln|Δx_k|$, $\frac{|Δx_k|}{|Δx_{k-1}|}$, $\frac{\ln|Δx_k|}{\ln|Δx_{k-1}|}$

and possibly also the same fractions with $|f(x_k)|$ instead of $|Δx_k|$.

For the example case $f(x)=x^m$ one gets $$ Δx_k=-\frac{x_k}m, \quad \frac{|Δx_{k+1}|}{|Δx_{k}|}=\frac{x_k+Δx_k}{x_k}=\frac{m-1}{m}\xrightarrow[m\to\infty]{}1 $$ and $$ f(x_{k+1})=(x_k+Δx_k)^m=\left(1-\tfrac1m\right)^m (x_k)^m, \quad \frac{|f(x_{k+1})|}{|f(x_{k})|}=\left(1-\tfrac1m\right)^m\xrightarrow[m\to\infty]{}e^{-1} $$ so that, taking into account approximation and numerical errors in the general case, these measurements can not really distinguish large multiplicities.

Lutz Lehmann
  • 126,666
  • I appreciate the long and well thought out answer, but i'll be blunt: it went over my head. I'm looking for something less theoretical and more applied. Or at least a less formal explanation as to why i'm doing something dumb – user132761 Mar 03 '14 at 17:39
  • The values $x_k$ are correct, but you are not displaying enough information about the Newton iteration. You need at least also the progression of the function values and update steps. So run the computation again with extended output. And then do the same for $f(x)=x^2$ and compare the reductions in step length and function value for both cases. – Lutz Lehmann Mar 03 '14 at 18:04