MHB Monotonically convergence to the root

[mathmari]

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:

 

[I like Serena]

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]

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]

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:

 

[I like Serena]

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]

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:

 

[I like Serena]

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]

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:

 

[I like Serena]

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]

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:

 

[I like Serena]

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]

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!

 

[mathmari]

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:

 

[I like Serena]

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]

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:

 

[I like Serena]

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]

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]

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:

 

[I like Serena]

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) \]

 

[HOI]

"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.

 

[I like Serena]

"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.

 

[HOI]

I'm so ashamed!