How can I choose which is the most suitable method?

[evinda]

Hello! (Wave)
I have a question.
Given the equation $t(x)=x^{2}-3x-4=0$ which roots are $-1$ and $4$ , we are looking for a suitable iterative method $x_{n+1}=\varphi(x_{n}),n=0,1,2$ so that the sequence $(x_{n})$ converges to the root $4 \forall x_{0} \in [3,5] $.Which of the following would you choose?
1) $\varphi(x)=3+\frac{4}{x}$
2) $\varphi(x)=\frac{(x^2-4)}{3}$
3) $\varphi(x)=x^2-2x-4$
4) $\varphi(x)=\frac{(x^3-3x^2)}{4}$

How can I check which of the above is a suitable iterative method? (Thinking)

 

[Fantini]

I'll assume $\varphi$ is continuous, which I don't think it's a hindrance. You have a sequence $(x_n)$ which converges to the root 4, that means $\lim_{n \to \infty} x_n = 4$. Since you want an iterative method, you will define it as $x_{n+1} = \varphi(x_n)$. Since $\varphi$ is continuous as I've said, this means that

$$\lim_{n \to \infty} x_{n+1} = \lim_{n \to \infty} \varphi(x_n) = \varphi \left( \lim_{n \to \infty} x_n \right),$$

or in other words

$$\lim_{n \to \infty} x_{n+1} = 4 = \lim_{n \to \infty} \varphi(x_n) = \varphi \left( \lim_{n \to \infty} x_n \right) = \varphi(4).$$

Do you think you can take over from here? :)

 

[evinda]

I'll assume $\varphi$ is continuous, which I don't think it's a hindrance. You have a sequence $(x_n)$ which converges to the root 4, that means $\lim_{n \to \infty} x_n = 4$. Since you want an iterative method, you will define it as $x_{n+1} = \varphi(x_n)$. Since $\varphi$ is continuous as I've said, this means that

$$\lim_{n \to \infty} x_{n+1} = \lim_{n \to \infty} \varphi(x_n) = \varphi \left( \lim_{n \to \infty} x_n \right),$$

or in other words

$$\lim_{n \to \infty} x_{n+1} = 4 = \lim_{n \to \infty} \varphi(x_n) = \varphi \left( \lim_{n \to \infty} x_n \right) = \varphi(4).$$

Do you think you can take over from here? :)

In each case,I found $\varphi(4)=4$ How can I find then which is the suitable method??

 

[Fantini]

My math was wrong. I did calculations in my head and ended up mistaken. I thought that noting that $\varphi(4) =4$ would exclude a couple of possibilities. :p Let's hope someone else chimes in, as I'm not knowledgeable in iterative methods. Meanwhile, I'll try to search the answer.

Sorry. :(

 

[Evgeny.Makarov]

See if $x_n$ converges for $x_0=5$.

 

[evinda]

See if $x_n$ converges for $x_0=5$.

Why do I have to check the convergence for $x_0=5$ ?

 

[Evgeny.Makarov]

Why do I have to check the convergence for $x_0=5$ ?

we are looking for a suitable iterative method $x_{n+1}=\varphi(x_{n}),n=0,1,2$ so that the sequence $(x_{n})$ converges to the root $4 \forall x_{0} \in [3,5] $.

Because according to the problem statement the sequence must converge for every initial value $x_0\in[3,5]$, including $x_0=5$.

 

[Ackbach]

Hello! (Wave)
I have a question.
Given the equation $t(x)=x^{2}-3x-4=0$ which roots are $-1$ and $4$ , we are looking for a suitable iterative method $x_{n+1}=\varphi(x_{n}),n=0,1,2$ so that the sequence $(x_{n})$ converges to the root $4 \forall x_{0} \in [3,5] $.Which of the following would you choose?
1) $\varphi(x)=3+\frac{4}{x}$
2) $\varphi(x)=\frac{(x^2-4)}{3}$
3) $\varphi(x)=x^2-2x-4$
4) $\varphi(x)=\frac{(x^3-3x^2)}{4}$

How can I check which of the above is a suitable iterative method? (Thinking)

I would pick the one with the smallest maximum absolute value of its derivative on the interval $[3,5]$. Then the Fixed Point Theorems can help you out. If my calculations are correct, 1) yields the smallest maximum absolute value of the derivative. It is my guess, then, that 1) will converge the quickest. Indeed, I am not at all sure that the other functions are guaranteed convergence.

 

[I like Serena]

Hello! (Wave)
I have a question.
Given the equation $t(x)=x^{2}-3x-4=0$ which roots are $-1$ and $4$ , we are looking for a suitable iterative method $x_{n+1}=\varphi(x_{n}),n=0,1,2$ so that the sequence $(x_{n})$ converges to the root $4 \forall x_{0} \in [3,5] $.Which of the following would you choose?
1) $\varphi(x)=3+\frac{4}{x}$
2) $\varphi(x)=\frac{(x^2-4)}{3}$
3) $\varphi(x)=x^2-2x-4$
4) $\varphi(x)=\frac{(x^3-3x^2)}{4}$

How can I check which of the above is a suitable iterative method? (Thinking)

Hey evinda! (Smile)

Can I assume that this question is intended to practice the concept of numerical stability?

If so, then you should take a look at what happens to an error in the neighborhood of x=4.
Suppose we have an error $\varepsilon$ in $x$ and we calculate the next iteration.
Will the error get bigger (numerically unstable) or smaller (numerically stable)?

Let me give an example.
If we pick $$\varphi(x) = \frac{(x^2-4)}{3}$$ and introduce an error $\varepsilon$ we get:
$$\varphi(x+\varepsilon) = \frac{((x+\varepsilon)^2-4)}{3} = \frac{(x^2-4)}{3} + \frac 2 3 x \varepsilon + \mathcal O(\varepsilon^2)$$
Therefore the error in the next iteration is:
$$\varepsilon_{i+1} = \frac 2 3 x \varepsilon_i + \mathcal O(\varepsilon_i^2)$$
Since we're interested in the root $x=4$ (with values of $|\varepsilon| \le 1$), we can substitute $x=4$:
$$\varepsilon_{i+1} = \frac 2 3 \cdot 4 \cdot \varepsilon_i + \mathcal O(\varepsilon_i^2)$$
Since $|\frac 2 3 \cdot 4| > 1$, we can tell that the process is numerically unstable around $x=4$.
That is, an error in the input will grow iteration by iteration, meaning it diverges from the root.

More generally, we're looking at:
$$\varepsilon_{i+1} = \varphi(x+\varepsilon_i) - \varphi(x) = \varphi'(x) \varepsilon_i + \mathcal O(\varepsilon_i^2)$$

Do you see what you should do?

 

[chisigma]

The precise criteria to prove convergence of a sequence $x_{n}$ obeying the difference equation $\displaystyle x_{n+1} = \varphi (x_{n}),\ x_{0}= a$ is described in...

http://mathhelpboards.com/discrete-mathematics-set-theory-logic-15/difference-equation-tutorial-draft-part-i-426.html#post2492

The most obvious way to find one of the roots of the equation $\displaystyle f(x)= x^{2} - 3\ x - 4 =0$ is to write the difference equation...

$\displaystyle \Delta_{n} = x_{n+1} - x_{n} = f(x_{n}) = x^{2}_{n} - 3\ x_{n} - 4\ (1)$ ... which corresponds to the option 3). This approach however fails because, as explained in the tutorial, x=4 is a repulsive fixed point, so that the sequence converges to 4 only for $\displaystyle x_{0}= 4$... Kind regards $\chi$ $\sigma$

 

[evinda]

Because according to the problem statement the sequence must converge for every initial value $x_0\in[3,5]$, including $x_0=5$.

So do I have to find for each method $x_{1},x_{2},x_{3},x_{4},...$ to check if $4$ appears?

- - - Updated - - -

I would pick the one with the smallest maximum absolute value of its derivative on the interval $[3,5]$. Then the Fixed Point Theorems can help you out. If my calculations are correct, 1) yields the smallest maximum absolute value of the derivative. It is my guess, then, that 1) will converge the quickest. Indeed, I am not at all sure that the other functions are guaranteed convergence.

I found that the function $\varphi=3+\frac{4}{x}$ has the smallest maximum absolute value..Do you think that this is the suitable method?

 

[evinda]

Could you explain me how you got to this equation?

Therefore the error in the next iteration is:
$$\varepsilon_{i+1} = \frac 2 3 x \varepsilon_i + \mathcal O(\varepsilon_i^2)$$
Since we're interested in the root $x=4$ (with values of $|\varepsilon| \le 1$), we can substitute $x=4$:
$$\varepsilon_{i+1} = \frac 2 3 \cdot 4 \cdot \varepsilon_i + \mathcal O(\varepsilon_i^2)$$
Since $|\frac 2 3 \cdot 4| > 1$, we can tell that the process is numerically unstable around $x=4$.
That is, an error in the input will grow iteration by iteration, meaning it diverges from the root.

More generally, we're looking at:
$$\varepsilon_{i+1} = \varphi(x+\varepsilon_i) - \varphi(x) = \varphi'(x) \varepsilon_i + \mathcal O(\varepsilon_i^2)$$

Do you see what you should do?

 

[I like Serena]

Could you explain me how you got to this equation?

We have the algorithm:
$$x_{i+1} = \varphi(x_i)$$

Now suppose that $\varepsilon_i$ is the error in $x_i$ with respect to the actual root $x$.
That means that $x_i = x + \varepsilon_i$ and $x_{i+1} = x + \varepsilon_{i+1}$.

Then substituting gives us:
$$x + \varepsilon_{i+1} = \varphi(x + \varepsilon_i)$$
From Taylor's theorem we know that:
$$\varphi(x + \varepsilon_i) = \varphi(x) + \varphi'(x) \varepsilon_i + \mathcal O(\varepsilon_i^2)$$
And since $x$ is the root, we also know that:
$$\varphi(x) = x$$

In other words:
$$\varepsilon_{i+1} = \varphi'(x) \varepsilon_i + \mathcal O(\varepsilon_i^2)$$

This is guaranteed to diverge if $|\varphi'(x)| > 1$ where $x$ is the actual root.
So if $|\varphi'(4)| > 1$, you have a diverging algorithm.

 

[Ackbach]

I found that the function $\varphi=3+\frac{4}{x}$ has the smallest maximum absolute value..Do you think that this is the suitable method?

Assuming you meant that $3+4/x$ has the smallest possible maximum absolute value of its derivative, then yep!

 

[Evgeny.Makarov]

So do I have to find for each method $x_{1},x_{2},x_{3},x_{4},...$ to check if $4$ appears?

4 may never appear; that's why it's called a limit. But if you calculate several initial values, you can see that the sequence rapidly grows except in the case of $\varphi$ from 1). The same is seen from the graphs (the picture is clickable):

[GRAPH]ig9m08odka[/GRAPH]

It should not be hard to prove algebraically that every $\varphi$ except the first one increases unboundedly after $x=4$, and so the sequence that starts with $x_0=5$ tends to infinity.

 

[evinda]

We have the algorithm:
$$x_{i+1} = \varphi(x_i)$$

Now suppose that $\varepsilon_i$ is the error in $x_i$ with respect to the actual root $x$.
That means that $x_i = x + \varepsilon_i$ and $x_{i+1} = x + \varepsilon_{i+1}$.

Then substituting gives us:
$$x + \varepsilon_{i+1} = \varphi(x + \varepsilon_i)$$
From Taylor's theorem we know that:
$$\varphi(x + \varepsilon_i) = \varphi(x) + \varphi'(x) \varepsilon_i + \mathcal O(\varepsilon_i^2)$$
And since $x$ is the root, we also know that:
$$\varphi(x) = x$$

In other words:
$$\varepsilon_{i+1} = \varphi'(x) \varepsilon_i + \mathcal O(\varepsilon_i^2)$$

This is guaranteed to diverge if $|\varphi'(x)| > 1$ where $x$ is the actual root.
So if $|\varphi'(4)| > 1$, you have a diverging algorithm.

I understand...Thanks a lot! :)

- - - Updated - - -

Assuming you meant that $3+4/x$ has the smallest possible maximum absolute value of its derivative, then yep!

Great!Thank you very much! :)

- - - Updated - - -

4 may never appear; that's why it's called a limit. But if you calculate several initial values, you can see that the sequence rapidly grows except in the case of $\varphi$ from 1). The same is seen from the graphs (the picture is clickable):

[GRAPH]ig9m08odka[/GRAPH]

It should not be hard to prove algebraically that every $\varphi$ except the first one increases unboundedly after $x=4$, and so the sequence that starts with $x_0=5$ tends to infinity.

I see..Thanks a lot! :p