Welcome to our community

Be a part of something great, join today!

Monotonically convergence to the root

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,713
Hey!! 😊

We have the following iteration from Newton's method \begin{align*}x_{k+1}&=x_k-\frac{f(x_k)}{f'(x_k)}=x_k-\frac{x_k^n-a}{nx_k^{n-1}}=\frac{x_k\cdot nx_k^{n-1}-\left (x_k^n-a\right )}{nx_k^{n-1}}=\frac{ nx_k^{n}-x_k^n+a}{nx_k^{n-1}}\\ & =\frac{ (n-1)x_k^{n}+a}{nx_k^{n-1}}\end{align*}

I want to show that for $x_0\geq a^{1/n}$ the method converges monotonically to the root.


So first we have to show that the sequence $(x_k)$ is monotone decreasing, right?


I have done the following:

\begin{align*}&x_{k+1}=\frac{ (n-1)x_k^{n}+a}{nx_k^{n-1}}=\frac{n-1}{n}x_k+\frac{a}{nx_k^{n-1}}=\left (1-\frac{1}{n}\right )x_k+\frac{a}{nx_k^{n-1}} \\ & \Rightarrow \frac{x_{k+1}}{x_k}=\frac{\left (1-\frac{1}{n}\right )x_k+\frac{a}{nx_k^{n-1}}}{x_k}=\left (1-\frac{1}{n}\right )+\frac{a}{nx_k^{n}}=1+\frac{a-x_k^{n}}{nx_k^{n}}\end{align*}

Since $x_0\geq a^{1/n}$ we have that all approximations are greater than $a^{1/n}$. Is this correct? :unsure:

So we get $x_k\geq a^{1/n} \Rightarrow x_k^n\geq a \Rightarrow a-x_k^{n}\leq 0$.

Therefore we get that $\frac{x_{k+1}}{x_k}\leq 1 \Rightarrow x_{k+1}\leq x_k$ and so the sequence is decreasing.


Then I want to show also that $$x_{k+1}-a\leq \frac{n-1}{n}(x_k-a)$$

I have done the following:
$$x_{k+1}-a=\frac{n-1}{n}x_k+\frac{a}{nx_k^{n-1}}-a=\frac{n-1}{n}x_k+\frac{a}{nx_k^{n-1}}-\frac{nx_k^{n-1}a}{ nx_k^{n-1}}=\frac{n-1}{n}x_k-a\cdot \frac{nx_k^{n-1}-1}{ nx_k^{n-1}}$$

To get the desired result we need:
$$\frac{nx_k^{n-1}-1}{ nx_k^{n-1}}\geq \frac{n-1}{n} \Rightarrow \frac{nx_k^{n-1}-1}{ x_k^{n-1}}\geq n-1
\Rightarrow nx_k^{n-1}-1\geq nx_k^{n-1}-x_k^{n-1} \Rightarrow x_k^{n-1}\geq 1 $$ but does this hold? :unsure:



Then last question....
I want to calculate $2010^{(1/17)}$ with starting point $x_0=2010$, with $4$ decimal digits.
For that we use the above formula with $a=2010$, $n=17$ and $x_0=2010$.

Some approximations that we get:
\begin{align*}&x_1=\left (1-\frac{1}{17}\right )\cdot 2010+\frac{2010}{17\cdot 2010^{17-1}}=\frac{16}{17}\cdot 2010+\frac{2010}{17\cdot 2010^{16}}=\frac{16}{17}\cdot 2010+\frac{1}{17\cdot 2010^{15}}=\frac{16\cdot 2010^16+1}{17\cdot 2010^{15}}\approx 1891.7647 \\ &x_2=\left (1-\frac{1}{17}\right )\cdot 1891.7647+\frac{2010}{17\cdot 1891.7647^{17-1}}=\frac{16}{17}\cdot 1891.7647+\frac{2010}{17\cdot 1891.7647^{16}}\approx 1780.4844 \\ &x_3=\left (1-\frac{1}{17}\right )\cdot 1780.4844+\frac{2010}{17\cdot 1780.4844^{17-1}}=\frac{16}{17}\cdot 1780.4844+\frac{2010}{17\cdot 1780.4844^{16}}\approx 1675.7500\end{align*}
In Wolfram I checked that the result is about $1.5642$. So to get the correct result we have to apply the method many items or have I done something wrong? :unsure:
 
Last edited:

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,593
Hi mathmari !!

It looks correct to me.
Btw, you might formulate it more properly as a proof by induction. (Nerd)

Still, it is not enough is it? We still need to prove that the sequence converges to $a$.
And if we have that, then perhaps we can also deduce that the sequence is decreasing. (Sweating)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,713
It looks correct to me.
Btw, you might formulate it more properly as a proof by induction. (Nerd)

Still, it is not enough is it? We still need to prove that the sequence converges to $a$.
And if we have that, then perhaps we can also deduce that the sequence is decreasing. (Sweating)
We show by induction that $x_k\geq a^{1/n}$ for all $k\geq 0$.

Base Case: For $k=0$ it is true, as thisis given.

Inductive Hypothesis: We suppose that this is true for $k=i$, i.e. $x_i\geq a^{1/n}$.
We want to show that this is also true for $k=i+1$, i.e. that $x_{i+1}\geq a^{1/n}$.
We have that $$x_{i+1}=\frac{ (n-1)x_i^{n}+a}{nx_i^{n-1}}\geq \frac{ (n-1)\left(a^{1/n}\right )^{n}+a}{nx_i^{n-1}}=\frac{ (n-1)a+a}{nx_i^{n-1}}=\frac{ na}{nx_i^{n-1}}=\frac{ a}{x_i^{n-1}}$$ How do we continue? :unsure:
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,713
For the second part, to show the inequality $x_{n+1}-a\leq \frac{n-1}{n}(x_k-a)$, do we maybe do the following?
\begin{align*}x_{k+1}-a-\frac{n-1}{n}(x_k-a)&=x_{k+1}-a-\left (1-\frac{1}{n}\right )(x_k-a) \\ & =x_{k+1}-a-\left (1-\frac{1}{n}\right )x_k+\left (1-\frac{1}{n}\right )a \\ & =x_{k+1}-a-x_k+\frac{1}{n}x_k+a-\frac{1}{n}a \\ & =x_{k+1}-x_k+\frac{1}{n}x_k-\frac{1}{n}a \\ & =x_{k+1}-x_k+\frac{x_k-a}{n} \\ & \leq x_{k}-x_k+\frac{x_k-a}{n} \\ & = \frac{x_k-a}{n}\end{align*} So we have to show that the last term is negative. How can we see that? :unsure:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,593
Then last question....
I want to calculate $2010^{(1/17)}$ with starting point $x_0=2010$, with $4$ decimal digits.
For that we use the above formula with $a=2010$, $n=17$ and $x_0=2010$.

Some approximations that we get:
\begin{align*}&x_1=\left (1-\frac{1}{17}\right )\cdot 2010+\frac{2010}{17\cdot 2010^{17-1}}=\frac{16}{17}\cdot 2010+\frac{2010}{17\cdot 2010^{16}}=\frac{16}{17}\cdot 2010+\frac{1}{17\cdot 2010^{15}}=\frac{16\cdot 2010^16+1}{17\cdot 2010^{15}}\approx 1891.7647 \\ &x_2=\left (1-\frac{1}{17}\right )\cdot 1891.7647+\frac{2010}{17\cdot 1891.7647^{17-1}}=\frac{16}{17}\cdot 1891.7647+\frac{2010}{17\cdot 1891.7647^{16}}\approx 1780.4844 \\ &x_3=\left (1-\frac{1}{17}\right )\cdot 1780.4844+\frac{2010}{17\cdot 1780.4844^{17-1}}=\frac{16}{17}\cdot 1780.4844+\frac{2010}{17\cdot 1780.4844^{16}}\approx 1675.7500\end{align*}
In Wolfram I checked that the result is about $1.5642$. So to get the correct result we have to apply the method many items or have I done something wrong?
This iteration process looks correct to me.
Note that in each iteration we have $x_{k+1}=\frac{n-1}n x_k + \text{ something positive}$.
So for a large starting value, we go down by less than a factor $\frac{n-1}n=\frac{16}{17}$ per iteration. 🤔
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,713
This iteration process looks correct to me.
Note that in each iteration we have $x_{k+1}=\frac{n-1}n x_k + \text{ something positive}$.
So for a large starting value, we go down by less than a factor $\frac{n-1}n=\frac{16}{17}$ per iteration. 🤔
I applied the method online for the given function and I saw that to get a result close to the true value we have to do about 115 iterations. (Lipssealed)

So taking this starting point is a bad idea....


Do you have also an idea about the question with the inequality? :unsure:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,593
Do you have also an idea about the question with the inequality?
Have you considered looking at the error as is given by a formula with the second derivative of $f$?
If we can prove that this error is always positive and that it converges to 0, then we have what we need. 🤔
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,713
Have you considered looking at the error as is given by a formula with the second derivative of $f$?
If we can prove that this error is always positive and that it converges to 0, then we have what we need. 🤔
What do you mean? I haven't really understood that. :unsure:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,593
What do you mean? I haven't really understood that.
Wiki lists the error in each iteration to a root $\alpha$ as
$$\varepsilon_{n+1} = \frac {- f'' (\xi_n)}{2 f'(x_n)} \cdot {\varepsilon_n}^2$$
where $\varepsilon_n = \alpha - x_n$ and $\xi_n$ is between $\alpha$ and $x_n$.

If we can prove that $\varepsilon_n$ is a negative and increasing sequence that converges to 0, we have proven everything, haven't we? 🤔
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,713
Wiki lists the error in each iteration to a root $\alpha$ as
$$\varepsilon_{n+1} = \frac {- f'' (\xi_n)}{2 f'(x_n)} \cdot {\varepsilon_n}^2$$
where $\varepsilon_n = \alpha - x_n$ and $\xi_n$ is between $\alpha$ and $x_n$.

If we can prove that $\varepsilon_n$ is a negative and increasing sequence that converges to 0, we have proven everything, haven't we? 🤔
So in this case we have that $\epsilon_k=a^{1/n}-x_k$, right?

So we get
$$\epsilon_{k+1}=-\frac{n(n-1)\xi_k^{n-2}}{2nx_k^{n-1}}\cdot \epsilon_n^2=-\frac{(n-1)\xi_k^{n-2}}{2x_k^{n-1}}\cdot \epsilon_n^2\leq -\frac{(n-1)(a^{1/n})^{n-2}}{2(a^{1/n})^{n-1}}\cdot \epsilon_n^2=-\frac{n-1}{2a^{1/n}}\cdot \epsilon_k^2$$ with $\epsilon_k=a^{1/n}-x_k$.

Is that correct so far? :unsure:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,593
The inequality is not correct since the expression is negative.
Instead the inequality would apply if we take the magnitudes of both sides. 🤔

Either way, we can already see that each error after the first is negative, so we can conclude that $x_n \ge a^{1/n}$. 🤔
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,713
The inequality is not correct since the expression is negative.
Instead the inequality would apply if we take the magnitudes of both sides. 🤔

Either way, we can already see that each error after the first is negative, so we can conclude that $x_n \ge a^{1/n}$. 🤔

Ahh ok!
 
Last edited:

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,713
I tried again to show the ineuqlaity $x_{k+1}-a\leq \frac{n-1}{n}(x_k-a)$ and I have the following:

\begin{align*}x_{k+1}&=\left (1-\frac{1}{n}\right )x_k+\frac{a}{nx_k^{n-1}} \\ & \leq \left (1-\frac{1}{n}\right )x_k+\frac{a}{n\left (a^{1/n}\right )^{n-1}} \\ & = \left (1-\frac{1}{n}\right )x_k+\frac{a}{na^{1-\frac{1}{n}}} \\ & = \left (1-\frac{1}{n}\right )x_k+\frac{a^{\frac{1}{n}}}{n} \\ & \leq \left (1-\frac{1}{n}\right )x_k+\frac{a}{n}\end{align*}
At the second line I used the fact that $x_k\geq a^{1/n}$ and so $\frac{1}{x_k}\leq \frac{1}{a^{1/n}}$ and at the last line I used the fact that $a^{1/n}\leq a$.

Are these inequalities correct? :unsure:

Then subtracting at both sides "$a$" we get \begin{equation*}x_{k+1}-a\leq \left (1-\frac{1}{n}\right )x_k+\frac{a}{n}-a=\left (1-\frac{1}{n}\right )x_k-\left (1-\frac{1}{n}\right )a=\left (1-\frac{1}{n}\right )(x_k-a)\end{equation*}

Is everything correct? :unsure:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,593
I tried again to show the ineuqlaity $x_{k+1}-a\leq \frac{n-1}{n}(x_k-a)$ and I have the following:

At the second line I used the fact that $x_k\geq a^{1/n}$ and so $\frac{1}{x_k}\leq \frac{1}{a^{1/n}}$ and at the last line I used the fact that $a^{1/n}\leq a$.

Are these inequalities correct?
We need $a\ge 1$ for the inequality $a^{1/n}\leq a$ to be true.
So you're proving a weaker version of the statement. 🤔

Then subtracting at both sides "$a$" we get \begin{equation*}x_{k+1}-a\leq \left (1-\frac{1}{n}\right )x_k+\frac{a}{n}-a=\left (1-\frac{1}{n}\right )x_k-\left (1-\frac{1}{n}\right )a=\left (1-\frac{1}{n}\right )(x_k-a)\end{equation*}

Is everything correct?
Yep.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,713
We need $a\ge 1$ for the inequality $a^{1/n}\leq a$ to be true.
So you're proving a weaker version of the statement. 🤔
So do we have to prove that $a\geq 1$ ? Or do we have to take cases, if $a\geq 1$ and if $a<1$ ? :unsure:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,593
So do we have to prove that $a\geq 1$ ? Or do we have to take cases, if $a\geq 1$ and if $a<1$ ?
We cannot prove that $a\ge 1$, since $a$ is part of the input statement without any constraints.
We can only assume that $a \ge 0$ because otherwise $a^{1/n}$ is not well defined. 🧐

What you have now only works for $a\ge 1$, although the statement is also true for $a<1$. We can tell if we consider the graph.
So either we have to be satisfied with the proof of a weaker statement, or we have to indeed take the case $a<1$ separately, or we need to find a different way. 🤔
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,713
Do you have an idea for the case $a<1$ ?

I have done the following:

If $a< 1$ then $a^{1/n}\leq a$ and so $$x_{k+1}\leq \left (1-\frac{1}{n}\right )x_k+\frac{a^{\frac{1}{n}}}{n} \Rightarrow x_{k+1}-a\leq \left (1-\frac{1}{n}\right )x_k+\frac{a^{\frac{1}{n}}}{n}-a=\left (1-\frac{1}{n}\right )x_k-\frac{na-a^{\frac{1}{n}}}{n}=\left (1-\frac{1}{n}\right )x_k-\frac{n\left (a^n\right )^{\frac{1}{n}}-a^{\frac{1}{n}}}{n}$$ But I don't have an idea how to continue.... :unsure:
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,713
One other idea:

If $a< 1$ then \begin{align*}x_{k+1}&=\left (1-\frac{1}{n}\right )x_k+\frac{a}{nx_k^{n-1}}\\ & \leq \left (1-\frac{1}{n}\right )x_k+\frac{1}{nx_k^{n-1}} \\ & \leq \left (1-\frac{1}{n}\right )x_k+\frac{1}{n\left (a^{1/n}\right )^{n-1}} \\ & = \left (1-\frac{1}{n}\right )x_k+\frac{1}{na^{1-\frac{1}{n}}} \\ & = \left (1-\frac{1}{n}\right )x_k+\frac{a^{\frac{1}{n}-1}}{n} \\ & = \left (1-\frac{1}{n}\right )x_k+\frac{a^{\frac{1-n}{n}}}{n} \end{align*}
But how could we get the power of $a$ below? :unsure:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,593
Then I want to show also that $$x_{k+1}-a\leq \frac{n-1}{n}(x_k-a)$$
Just realized, shouldn't we try to show that $x_{k+1}-a^{1/n}\leq \frac{n-1}{n}(x_k-a^{1/n})$ instead? (Wondering)
The root of $y=x^n-a$ is $a^{1/n}$ after all, while $-a$ is the $y$-intersection.

Let $\alpha=a^{1/n}$.
Then we have:
\[ x_{k+1}-\alpha = x_k - \frac{x_k^n-a}{nx_k^{n-1}}-\alpha =x_k-\alpha - \frac{x_k^n-\alpha^n}{nx_k^{n-1}} =\left(1 - \frac{x_k^{n-1}+\ldots+\alpha^{n-1}}{nx_k^{n-1}}\right)(x_k-\alpha) \le \left(1 - \frac{1}{n}\right)(x_k-\alpha) \]
🤔
 
Last edited:

Country Boy

Well-known member
MHB Math Helper
Jan 30, 2018
854
"Convergence" is a noun, not a verb, adjective, or adverb. You need an adjective to modify it, not an adverb- "Monotone Covergence" NOT "Monotonically Convergence"!

("Coverge" is a verb so "Monotonically Converge" is correct.)

Okay, that's my rant for today.
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,593
"Convergence" is a noun, not a verb, adjective, or adverb. You need an adjective to modify it, not an adverb- "Monotone Covergence" NOT "Monotonically Convergence"!

("Coverge" is a verb so "Monotonically Converge" is correct.)

Okay, that's my rant for today.
Indeed... but... erm... "coverge" is not a verb. It is "converge".

Okay, that's my nitpicking for today.
 

Country Boy

Well-known member
MHB Math Helper
Jan 30, 2018
854
I'm so ashamed!