Is the iterative method suitable??

Question

We have the equation $g(x)=x^{2}-3x-4=0$ that has the roots $-1$ and $4$ and 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] $.Is this one: $\varphi(x)=\frac{x^{3}-3x^{2}}{4}$ suitable?How can I check this??

score 3 · Answer 1 · answered May 13 '14 at 21:30

@evinda;

One obvious way to get the idea that you form will not work is to try it. Using initial conditions of 4.1, 3.9, -1.1 and -.9 the iteration either blows up or heads to a false root.

A more analytical idea is to use the rule that for

$x = g(x)$

convergence will occur if

$\left | g'(x) \right |<1$

so

$g'(x)=\frac{1}{4} \left(3 x^2-6 x\right)$

plugging in x = 4 and taking the absolute value yields 6 which is greater than 1 and therefore convergence will not occur. Plugging in -1 yields 9 / 4 so again no convergence.

Amzoti · Accepted Answer · 2014-01-14T22:41:51.663

2

Recall, you need $x = g(x)$.

The function you are trying does not meet the criteria $x = g(x)$, so is not a candidate.

Possible choices are:

$x = \dfrac{x^2-4}{3}$, (fails to converge for any $x_0$),
$x = (3x + 4)^{1/2}$, (converges to $4$ for $x_0 \in [3,~5]$)
Other choices are possible, try some to see if you can find another example that does and does not work.

You can test iterates to see if they pass the criteria for this method and can even write the general error term.

edited Jan 14 '14 at 22:41

answered Jan 14 '14 at 22:36

Amzoti

56,093

@Amzoti So,in order to find a suitable iterative method,I have to solve for x?And then how can I know if a method I found is suitable or not?Why does,for example,the first one you found fail to converge? – evinda Jan 15 '14 at 18:59
@evinda: You could try actually iterating and see if convergence happens (these are pretty easy examples and algorithm). However, from a theory point of view. search for "So, when does fixed point iteration work and when does it fail?" on http://wwwf.imperial.ac.uk/metric/metric_public/numerical_methods/iteration/fixed_point_iteration.html. You can actually figure this out and should do so for the two examples I provided using this theorem! Regards – Amzoti Jan 15 '14 at 21:17

score 1 · Answer 3 · answered Jan 14 '14 at 22:42

To check that an iterative method is stable, you need to relate the error of $x_n$ to the error of $x_{n+1}$. In particular, you need to show that the errors do not grow.

As an example, let $x_n = 4 + e_n$; here $e_n$ is the error. Then $x_{n+1} = \varphi(x_n) = \varphi(4 + e_n) = 4 + 6 e_n + (9/4) e_n^2 -(3/4)e_n^3$, so then the new error is

$$ e_{n+1} = 6 e_n + (9/4) e_n^2 -(3/4)e_n^3$$

It is clear that for $e_n$ very small, $e_{n+1}$ is in fact larger than $e_n$, so the method is not stable.

Is the iterative method suitable??

3 Answers3