- #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:

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: