MHB How can I choose which is the most suitable method?

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Method
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Mathematics news on Phys.org
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? :)
 
Fantini said:
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?? :confused:
 
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. :(
 
See if $x_n$ converges for $x_0=5$.
 
Evgeny.Makarov said:
See if $x_n$ converges for $x_0=5$.

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

evinda said:
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$.
 
evinda said:
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.
 
evinda said:
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?
 
  • #10
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$
 
  • #11
Evgeny.Makarov said:
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 - - -

Ackbach said:
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?
 
  • #12
Could you explain me how you got to this equation? :o

I like Serena said:
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?
 
  • #13
evinda said:
Could you explain me how you got to this equation? :o

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.
 
  • #14
evinda said:
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!
 
  • #15
evinda said:
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.
 
  • #16
I like Serena said:
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 - - -

Ackbach said:
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 - - -

Evgeny.Makarov said:
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
 
Back
Top