1

the equation $x^3-5x+1=0$ has a root in $(0,1)$. Using a proper sequence for which $$|a(n+1)-a(n)|\le c|(a(n)-a(n-1)|$$ with $0<c<1$ , find the root with an approximation of $10^{-4}$.

angryavian
  • 89,882
Plom
  • 661
  • 1
    Source of the problem? Reason for interest in it? Indication of any effort of your own, beyond that required to copy-paste? – Gerry Myerson Jul 23 '13 at 09:20
  • its from a real analysis book of mine, i read it for fun :D – Plom Jul 23 '13 at 09:27
  • 1
    And what techniques does the book give you for tackling this kind of problem? – Mark Bennet Jul 23 '13 at 09:27
  • It doesnt really have any similar solved problems. In the respective chapter, it only gives the definition and proves how sequences like the above, are cauchy and converge. It also gives an irrelevant to the problem, example and thats all :( – Plom Jul 23 '13 at 09:30
  • Notice that $f:x\mapsto x^3-5x+1$ is convex on $[0,1]$. You can construct a suitable sequence $(a_n)$ converging towards the root with the Newton-Raphson method. Some analysis should yield a constant $c$. – zuggg Jul 23 '13 at 09:34
  • The sequence $a_0=0$ and $a_{n+1}=\frac {a_n^3+1}5$ converges very quickly, but you have to prove the condition applies. – Mark Bennet Jul 23 '13 at 09:42
  • and how do i actually compute the root from that? i dont get it :( – Plom Jul 23 '13 at 09:51
  • The sequence converges rapidly to a root. But you have to prove there is a $c$ which works to satisfy the terms of the question. – Mark Bennet Jul 23 '13 at 10:03

2 Answers2

2

You can attempt this: define a sequence $x_n$ by $$ x_{n+1} = \frac 15\left(1 + x_n^3\right). $$ We know that if $x_1 \in (0, 1)$, then $x_n \in (0, 1)$ for all $n$. Next, we show that it satisfies the said condition: \begin{align*} x_{n+1} - x_n & = \frac 15(1 + x_n^3 - 5x_n)\\ & = \frac 15\left(1 + x_n^3 - (1 + x_{n-1}^3)\right)\\ & = \frac 15\left(x_n^3 - x_{n-1}^3\right) \\ & = \frac 15\left(x_n - x_{n-1}\right)\left(x_n^2 + x_nx_{n-1} + x_{n-1}^2\right) \\ \therefore \left|x_{n+1} - x_n\right| & = \frac 15\left|\left(x_n - x_{n-1}\right)\left(x_n^2 + x_nx_{n-1} + x_{n-1}^2\right)\right| \\ & \le \frac 15\left|x_n - x_{n-1}\right| \cdot 3 \\ & \le \frac 35\left|x_n - x_{n-1}\right|. \end{align*} From this, we see that the sequence is Cauchy, hence convergent. Let $x$ be the limit of the sequence. Take the limit $n \to \infty$ in the first equation (which defines $x_{n+1}$ from $x_n$) to get $$ x = \frac 15(1 + x^3). $$ This means $x$ is a root of $f(x) = x^3 - 5x + 1$.

To compute $x$ numerically within a given error tolerance $\epsilon$, we need to find $x_N$ such that $|x_N - x| \le \epsilon$. However, we do not know $x$, so instead, we can use the following criterion to find $N$: for all $n > N$, $|x_{n} - x_N| < \epsilon$. This criterion is sufficient because if the inequality holds for all $n > N$, it will follow that $\lim_{n \to \infty} |x_n - x_N| = |x - x_N| \le \epsilon$.

One convenient way to guarantee $|x_n - x_N| < \epsilon$ for all $n > N$ is via the triangle inequality: $$ |x_n - x_N| \le \sum_{k=N}^{n-1} \left|x_{k+1} - x_k\right| \le \sum_{k=N}^\infty \left|x_{k+1} - x_k\right| \le \frac{\left(\frac 35\right)^N}{1 - \frac 35} = \frac 52\left(\frac 35\right)^N. $$ So, if we can find $N$ such that $\frac 52\left(\frac 35\right)^N < \epsilon$, we will get $|x_N - x| \le \epsilon$.

Tunococ
  • 10,303
1

Wouldn't a bisect algorithm do something like this:

Let $f(x)=x^3-5x+1$. Then we find the root by:

f(0)>0, f(1)<0

f(0.5)<0 (hence, there is a root between 0 and 0.5)

f(0.25)<0

f(0.125)>0

f(0.1875)

and so on... The sequence would be (0.5, 0.25,0.125, 0.1875...) and c=1/2

Edit: and the algorithm works as f is continuous :)

chris
  • 135