0
$\begingroup$

Assume that a sequence $\{x_i\}_{i=0}^\infty$ of Newton's method $x_{i+1}=x_i-\frac{f(x_i)}{f'(x_i)}$ is convergent and set $x_\infty = \lim_{i\to\infty} x_i$. Furthermore assume that $f'(x_\infty) \neq 0$. How is it possible to show that $x_\infty$ is an solution to $f(x)=0$?

My solution for this were assuming that $x_{\infty+1}$=$x_\infty$ so $$x_{\infty+1}=x_\infty-\frac{f(x_\infty)}{f'(x_\infty)}$$ $$0=-\frac{f(x_\infty)}{f'(x_\infty)}$$ $$0=-f(x_\infty)$$ $$f(x_\infty)=0$$

$\endgroup$
  • $\begingroup$ Newton's method only works for certain differentiable functions $f$ and when $x_0$ is a close enough "guess" of what $x_\infty$ might be. See: en.wikipedia.org/wiki/Newton%27s_method $\endgroup$ – B. Núñez Nov 13 '19 at 1:10
  • $\begingroup$ I'm taking Calculus Beta right now and this is an assignment problem. In the problem description it is derived from the tangent line equation that $x_i+1=x_i-\frac{f(x_i)}{f'(x_i)}$. Furthermore the question is that we assume a sequence is convergent and $f'(x_\infty) \neq 0$ and for $x_\infty$ it is defined as $\lim_{i\to\infty} x_i $, how do we show that $x_\infty$ is an solution (the root) to $f(x)=0$. There aren't any other details about this sub-problem in the assignment. $\endgroup$ – Rakozay Nov 13 '19 at 1:53
  • 1
    $\begingroup$ One might be able to guess from your use of the term "Newton method" in your question that you mean $x_{i+1}=x_i-\frac{f(x_i}{f'(x_i)}$. Yet, I would think you should put this info in your question, to make it clear. You dont need any $x_{\infty+1}$. If $x_i\to x_\infty$ then also $x_{i+1}\to x_\infty$, so $x_\infty=x_\infty-\frac{f(x_\infty)}{f'(x_\infty)}$. Welcome to MSE ! $\endgroup$ – Mirko Nov 13 '19 at 1:55
  • $\begingroup$ Incredible! Makes much more sense and thanks @Mirko! $\endgroup$ – Rakozay Nov 13 '19 at 2:05
  • $\begingroup$ You are welcome ! $\endgroup$ – Mirko Nov 13 '19 at 2:06
2
$\begingroup$

The following proof works if we assume that $\{x_i\}_{i\geq 0}$ is a convergent sequence such that $x_{i+1}=x_i-\frac{f(x_i)}{f'(x_i)}$ for all $i\geq 0$ (this assumption wasn't on your initial post, hence my comment) and $f$ and $f'$ are both continuous in some interval containing $x_\infty$ (i.e. $f$ is continuously differentiable in $x_\infty$).

Your intuition that "$x_{\infty}=x_{\infty+1}$" is good, but doesn't yet constitute a proof. We can use the fact that $\displaystyle \lim_{i\to\infty} x_i=\lim_{i\to\infty} x_{i+1}$ (see here; this stems from the fact that $\{x_{i+1}\}_{i\geq 0}$ is a subsequence of $\{x_i\}_{i\geq 0}$) to deduce the following: $$\lim_{i\to \infty} x_{i+1}=\lim_{i\to \infty}\left(x_i-\frac{f(x_{i})}{f'(x_i)}\right) ~~\implies~~x_{\infty}=x_{\infty}-\frac{f(x_{\infty})}{f'(x_{\infty})},$$ by sum and fraction of limits and the convergence of $\{f(x_i)\}_{i\geq 0}$ and $\{f'(x_i)\}_{i\geq 0}$ if $f,f'$ are continuous and $f'(x_{\infty})\neq 0$. Substracting $x_{\infty}$ on both sides and multiplying by $-f'(x_{\infty})$, we obtain: $$-\frac{f(x_{\infty})}{f'(x_{\infty})}=0 ~~~~\text{and thus}~~~~ f(x_{\infty})=0.$$ That is, $x_{\infty}$ is a solution for $x$ in $f(x)=0$.


I'd like to remark (as in my comment) that the Newton-Rhapson method does not always converge to a root; this proof required fairly strong assumptions. Here's an interesting discussion about this.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.