Monotonically convergence to the root

In summary, we have a conversation about applying Newton's method to find the root of a function and proving its convergence. The method is shown to be monotonically decreasing when the starting point is greater than or equal to the root. The conversation then moves on to proving that the sequence converges to the root and discussing the number of iterations needed to get a close approximation. Finally, there is a question about an inequality, but it is left unresolved.
  • #1
mathmari
Gold Member
MHB
5,049
7
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 by a moderator:
Mathematics news on Phys.org
  • #2
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)
 
  • #3
Klaas van Aarsen said:
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:
 
  • #4
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:
 
  • #5
mathmari said:
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. 🤔
 
  • #6
Klaas van Aarsen said:
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:
 
  • #7
mathmari said:
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. 🤔
 
  • #8
Klaas van Aarsen said:
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:
 
  • #9
mathmari said:
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? 🤔
 
  • #10
Klaas van Aarsen said:
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:
 
  • #11
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}$. 🤔
 
  • #12
Klaas van Aarsen said:
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 by a moderator:
  • #13
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:
 
  • #14
mathmari said:
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.
 
  • #15
Klaas van Aarsen said:
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:
 
  • #16
mathmari said:
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. 🤔
 
  • #17
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:
 
  • #18
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:
 
  • #19
mathmari said:
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:
  • #20
"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.
 
  • #21
Country Boy said:
"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.
 
  • #22
I'm so ashamed!
 

FAQ: Monotonically convergence to the root

1. What is monotonically convergence to the root?

Monotonically convergence to the root refers to the behavior of a sequence of values that approach a specific value, known as the root, in a consistent and monotonic manner. This means that the values either consistently increase or decrease as the sequence progresses, ultimately reaching the root.

2. How is monotonically convergence to the root different from other types of convergence?

Monotonically convergence to the root is a specific type of convergence that is characterized by the monotonic behavior of the sequence. Other types of convergence may have different patterns of behavior, such as oscillating or diverging, and may not necessarily approach a single root value.

3. What is the significance of monotonically convergence to the root in scientific research?

Monotonically convergence to the root is important in scientific research because it allows for the precise determination of a specific value or parameter. This can be useful in fields such as mathematics, physics, and engineering, where accurate measurements and calculations are crucial.

4. How is monotonically convergence to the root used in numerical methods?

In numerical methods, monotonically convergence to the root is often used to solve equations or find the roots of functions. This is done by iteratively calculating values that approach the root in a monotonic manner, until the desired level of precision is achieved.

5. Are there any limitations to monotonically convergence to the root?

Yes, there are some limitations to monotonically convergence to the root. In some cases, a sequence may not monotonically converge to the root due to the complexity of the function or equation being solved. Additionally, the speed of convergence may vary depending on the initial values chosen and the specific method used.

Similar threads

Back
Top