# [SOLVED]Neighbourhood of Convergence of Sequence

#### Sudharaka

##### Well-known member
MHB Math Helper
Hi everyone, Can somebody give me a hint to solve this problem. Problem:

Let $$f$$ be a function defined on $$[a,\,b]$$ with continuous second order derivative. Let $$x_0\in (a,\,b)$$ satisfy $$f(x_0)=0$$ but $$f'(x_0)\neq 0$$. Prove that, there is a neighbourhood of $$x_0$$, say $$U(x_0)$$, such that, for all $$x_1\in U(x_0)$$, the following sequence,

$x_{n+1}=x_{n}-\frac{f(x_n)}{f'(x_n)}$

where $$n=1,\,2,\,\cdots$$ is convergent.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Hi everyone, Can somebody give me a hint to solve this problem. Problem:

Let $$f$$ be a function defined on $$[a,\,b]$$ with continuous second order derivative. Let $$x_0\in (a,\,b)$$ satisfy $$f(x_0)=0$$ but $$f'(x_0)\neq 0$$. Prove that, there is a neighbourhood of $$x_0$$, say $$U(x_0)$$, such that, for all $$x_1\in U(x_0)$$, the following sequence,

$x_{n+1}=x_{n}-\frac{f(x_n)}{f'(x_n)}$

where $$n=1,\,2,\,\cdots$$ is convergent.
Use Taylor's theorem:
$$f(x_n) = f(x_0) + f'(x_0)(x_n - x_0) + \frac 1 {2!} f''(\xi_n)(x_n - x_0)^2$$
where $\xi_n$ is between $x_0$ and $x_n$.

Let $\varepsilon_n = x_0 - x_n$.
This is the error with respect to the root of f in iteration n.
Consider the error $\varepsilon_{n+1}$ in terms of $\varepsilon_n$.
If it approaches zero, you're done.

#### Sudharaka

##### Well-known member
MHB Math Helper
Use Taylor's theorem:
$$f(x_n) = f(x_0) + f'(x_0)(x_n - x_0) + \frac 1 {2!} f''(\xi_n)(x_n - x_0)^2$$
where $\xi_n$ is between $x_0$ and $x_n$.

Let $\varepsilon_n = x_0 - x_n$.
This is the error with respect to the root of f in iteration n.
Consider the error $\varepsilon_{n+1}$ in terms of $\varepsilon_n$.
If it approaches zero, you're done.
Thanks very much for the reply but I am not sure whether I get you. If the error approaches zero then the sequence converges. But how does that guarantee the existence of a neighbourhood $$U(x_0)$$ where each element $$x_1$$ makes the sequence convergent?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Thanks very much for the reply but I am not sure whether I get you. If the error approaches zero then the sequence converges. But how does that guarantee the existence of a neighbourhood $$U(x_0)$$ where each element $$x_1$$ makes the sequence convergent?
If you work it out, you'll find there are some boundary conditions.
To satisfy those boundary conditions you need to take $x_1$ "close enough" to $x_0$, or equivalently $\varepsilon_1$ "close enough" to 0.
This is represented by a neighbourhood $U(x_0)$ that is "small enough".

#### chisigma

##### Well-known member
Hi everyone, Can somebody give me a hint to solve this problem. Problem:

Let $$f$$ be a function defined on $$[a,\,b]$$ with continuous second order derivative. Let $$x_0\in (a,\,b)$$ satisfy $$f(x_0)=0$$ but $$f'(x_0)\neq 0$$. Prove that, there is a neighbourhood of $$x_0$$, say $$U(x_0)$$, such that, for all $$x_1\in U(x_0)$$, the following sequence,

$x_{n+1}=x_{n}-\frac{f(x_n)}{f'(x_n)}$

where $$n=1,\,2,\,\cdots$$ is convergent.
A counterexample shoul be $\displaystyle f(x)= x^{\frac{1}{3}}$ because the difference equation becomes...

$\displaystyle \Delta_{n} = x_{n+1} - x_{n} = - 3\ x_{n}\ (1)$

... that diverges for any $x_{1} \ne 0$...

Kind regards

$\chi$ $\sigma$

#### Klaas van Aarsen

##### MHB Seeker
Staff member
A counterexample shoul be $\displaystyle f(x)= x^{\frac{1}{3}}$ because the difference equation becomes...
It doesn't satisfy the criteria.
f'(0) is not defined, so it does not have a continuous second order derivative around x=0.

#### Sudharaka

##### Well-known member
MHB Math Helper
If you work it out, you'll find there are some boundary conditions.
To satisfy those boundary conditions you need to take $x_1$ "close enough" to $x_0$, or equivalently $\varepsilon_1$ "close enough" to 0.
This is represented by a neighbourhood $U(x_0)$ that is "small enough".
Thanks, now I am understanding it more clearly. So we can get the $$\epsilon_{n+1}$$ in terms of $$\epsilon_n$$ as mentioned >>here<<.

$\epsilon_{n+1}=-\frac{f''(\gamma_n)}{2f'(x_n)}\epsilon_{n}$

I hope I am correct up to this point. Am I?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Thanks, now I am understanding it more clearly. So we can get the $$\epsilon_{n+1}$$ in terms of $$\epsilon_n$$ as mentioned >>here<<.

$\epsilon_{n+1}=-\frac{f''(\gamma_n)}{2f'(x_n)}\epsilon_{n}$

I hope I am correct up to this point. Am I?
Almost.
You dropped a square.

Note that you've already used that both f' and f'' exist, and that $f'(x_n)\ne 0$.
Are you aware of the conditions involved?

And I see you picked $\gamma_n$. Didn't you like $\xi_n$? #### Sudharaka

##### Well-known member
MHB Math Helper
Almost.
You dropped a square.

Note that you've already used that both f' and f'' exist, and that $f'(x_n)\ne 0$.
Are you aware of the conditions involved?
Sorry, that's a typo. It should be,

$\epsilon_{n+1}=-\frac{f''(\gamma_n)}{2f'(x_n)}\epsilon_{n}^2$

It's given that $$f$$ is twice differentiable. Hence $$f'$$ and $$f''$$ exists. But I thought that $$f'(x_n)\neq 0$$ is implied through the equation generating the terms of the sequence. What I felt from the beginning when solving this problem is how to incoperate the fact that $$f'(x_0)\neq 0$$.

And I see you picked $\gamma_n$. Didn't you like $\xi_n$? No I hate that symbol. First I never can write it properly and in this context I don't like to use it because it looks like $$\epsilon$$ and there's a chance I will confuse the two.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Sorry, that's a typo. It should be,

$\epsilon_{n+1}=-\frac{f''(\gamma_n)}{2f'(x_n)}\epsilon_{n}^2$

It's given that $$f$$ is twice differentiable. Hence $$f'$$ and $$f''$$ exists. But I thought that $$f'(x_n)\neq 0$$ is implied through the equation generating the terms of the sequence. What I felt from the beginning when solving this problem is how to incoperate the fact that $$f'(x_0)\neq 0$$.
It's the other way around.
You can only use $f'(x_n)\neq 0$ because you have $f'(x_0)\neq 0$.

Due to the fact that f' is continuous and that $f'(x_0)\neq 0$, you can infer that there will be some open interval around $x_0$ that will have $f'(x) \ne 0$ for x in that interval.

Only within that interval can you use the Taylor expansion as given.

#### Sudharaka

##### Well-known member
MHB Math Helper
It's the other way around.
You can only use $f'(x_n)\neq 0$ because you have $f'(x_0)\neq 0$.

Due to the fact that f' is continuous and that $f'(x_0)\neq 0$, you can infer that there will be some open interval around $x_0$ that will have $f'(x) \ne 0$ for x in that interval.

Only within that interval can you use the Taylor expansion as given.
This occurred me previously but I was confused by the fact that if we take that interval how do we know for sure that all the values $$x_n$$ lie in that interval? That is we choose $$x_1$$ from that interval, then calculate the value $$x_2$$. Now how can we guarantee that $$x_2$$ also lie in that same interval?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
This occurred me previously but I was confused by the fact that if we take that interval how do we know for sure that all the values $$x_n$$ lie in that interval? That is we choose $$x_1$$ from that interval, then calculate the value $$x_2$$. Now how can we guarantee that $$x_2$$ also lie in that same interval?
That happens if we can make sure that $|\varepsilon_{n+1}| < |\varepsilon_n|$.

#### Sudharaka

##### Well-known member
MHB Math Helper
That happens if we can make sure that $|\varepsilon_{n+1}| < |\varepsilon_n|$.
Yes, I think I am getting a hold of this. So we have the inequality,

$|\epsilon_{n+1}|=\left|\frac{f''(\gamma_n)}{2f'(x_n)}\right||\epsilon_{n}|^2$

To get $|\varepsilon_{n+1}| < |\varepsilon_n|$, we should have,

$|\epsilon_{n}|<\left|\frac{2f'(x_n)}{f''(\gamma_n)}\right|$

And this is the interval that we are looking for. Am I correct? #### Klaas van Aarsen

##### MHB Seeker
Staff member
Yes, I think I am getting a hold of this. So we have the inequality,

$|\epsilon_{n+1}|=\left|\frac{f''(\gamma_n)}{2f'(x_n)}\right||\epsilon_{n}|^2$

To get $|\varepsilon_{n+1}| < |\varepsilon_n|$, we should have,

$|\epsilon_{n}|<\left|\frac{2f'(x_n)}{f''(\gamma_n)}\right|$

And this is the interval that we are looking for. Am I correct? Yes.
With the additional constraints that we're inside the interval $(a,b)$ and that $f'(x) \ne 0$.
Also note that $f''(\gamma_n)$ could be zero, so we have to allow for that.

#### Sudharaka

##### Well-known member
MHB Math Helper
Yes.
With the additional constraints that we're inside the interval $(a,b)$ and that $f'(x) \ne 0$.
Also note that $f''(\gamma_n)$ could be zero, so we have to allow for that.
Well, so one last question. We have to assume that $$f''(\gamma_n)\neq 0$$. This is just something we have to assume and cannot be deducted from the given details. Am I correct? #### Klaas van Aarsen

##### MHB Seeker
Staff member
Well, so one last question. We have to assume that $$f''(\gamma_n)\neq 0$$. This is just something we have to assume and cannot be deducted from the given details. Am I correct? Not really.
If f''(x) = 0, we have instantaneous convergence to the root.

#### Sudharaka

##### Well-known member
MHB Math Helper
Not really.
If f''(x) = 0, we have instantaneous convergence to the root.
And that I believe tells us $$f$$ is a straight line. Isn't? But what's wrong with that?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
And that I believe tells us $$f$$ is a straight line. Isn't? But what's wrong with that?
Yep and nothing's wrong with that.
And btw, it is not given that f''(x) = 0 everywhere.
What it does mean, is that $|\varepsilon_{n+1}| < |\varepsilon_{n}|$ if $\varepsilon_{n} \ne 0$, which is what we wanted.

#### Sudharaka

##### Well-known member
MHB Math Helper
Yep and nothing's wrong with that.
And btw, it is not given that f''(x) = 0 everywhere.
What it does mean, is that $|\varepsilon_{n+1}| < |\varepsilon_{n}|$ if $\varepsilon_{n} \ne 0$, which is what we wanted.
Yes, I am sorry, too tired to understand that $$f''(\gamma)=0$$ does not mean that $$f$$ is a straight line. However if $$f''(\gamma)=0$$ then $$x_{n+1}=x_0$$ so obviously,

$0=|\varepsilon_{n+1}| < |\varepsilon_{n}|$

I guess this is what you meant. Am I correct? #### Klaas van Aarsen

##### MHB Seeker
Staff member
Yes, I am sorry, too tired to understand that $$f''(\gamma)=0$$ does not mean that $$f$$ is a straight line. However if $$f''(\gamma)=0$$ then $$x_{n+1}=x_0$$ so obviously,

$0=|\varepsilon_{n+1}| < |\varepsilon_{n}|$

I guess this is what you meant. Am I correct?
Yes.

#### Sudharaka

##### Well-known member
MHB Math Helper
Thank you sooooooooooooooooooo much for all your help. I think I understood every bit and piece of the problem, though it took a considerable amount of time. 