Welcome to our community

Be a part of something great, join today!

How can I choose which is the most suitable method?

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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

"Read Euler, read Euler." - Laplace
MHB Math Helper
Feb 29, 2012
342
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

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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:
 

Fantini

"Read Euler, read Euler." - Laplace
MHB Math Helper
Feb 29, 2012
342
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
See if $x_n$ converges for $x_0=5$.
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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

Indicium Physicus
Staff member
Jan 26, 2012
4,192
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.
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
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 \(\displaystyle \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

Well-known member
Feb 13, 2012
1,704
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-...ation-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

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
Could you explain me how you got to this equation? :eek:

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?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
Could you explain me how you got to this equation? :eek:
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

Indicium Physicus
Staff member
Jan 26, 2012
4,192
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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