Welcome to our community

Be a part of something great, join today!

[SOLVED] Neighbourhood of Convergence of Sequence

Sudharaka

Well-known member
MHB Math Helper
Feb 5, 2012
1,621
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
Mar 5, 2012
8,868
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
Feb 5, 2012
1,621
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
Mar 5, 2012
8,868
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
Feb 13, 2012
1,704
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
Mar 5, 2012
8,868
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
Feb 5, 2012
1,621
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
Mar 5, 2012
8,868
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
Feb 5, 2012
1,621
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
Mar 5, 2012
8,868
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
Feb 5, 2012
1,621
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
Mar 5, 2012
8,868
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
Feb 5, 2012
1,621
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
Mar 5, 2012
8,868
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
Feb 5, 2012
1,621
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
Mar 5, 2012
8,868
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
Feb 5, 2012
1,621
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
Mar 5, 2012
8,868
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
Feb 5, 2012
1,621
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
Mar 5, 2012
8,868
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
Feb 5, 2012
1,621
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. :)