0

I have to write a program that implements the bisection method.The program should end if the number of iterations surpass the maximum number of iterations,or if one or both of these conditions : $\left | x_{k}-x_{k-1} \right | $ < ε and $ \left | f(x_{k}) \right | $< ε
are valid?? Which should be my termination criteria when the first interval is [a,b]...Could it be |b-a|<ε?? If yes,why???

evinda
  • 7,823

1 Answers1

0

Remember that $x_k$ stand for your iterates. If you were to check the conditions $\big|x_k-x_{k-1}\big|$ when you start your program, you will need to know what $x_0$ and $x_1$ are. Usually, $x_0= \frac{b+a}{2}$ if $f(a)\times f(b) < 0$. To compute $x_1$, you will need to apply the bisection method to the new interval $[a, \frac{b+a}{2}]$ or $[\frac{b+a}{2}, b]$ (depending on what $f(b)$ and $f(a)$).

So to answer your question, the first stopping criteria would not be $|b-a|< \epsilon$ because $x_0\neq a$ and $x_1\neq b$ (not necessarily).

ZanCoul
  • 455
  • 2
  • 11
  • Could you give me an example?If for example the maximum number of iterations is 100,ε is 0.001 and the initial interval is [a,b] =[0,2]

    what is equal to first

    $\big|x_k-x_{k-1}\big|$ that we use????

     – evinda Nov 19 '13 at 08:29
  • You will need to know what your function $f(x)$ is. The iterates $x_0,x_1, \dots$ are determined by your function. So say for example your function is $f(x)=x-2/3$ (clearly, we know that the solution is $2/3$). – ZanCoul Nov 19 '13 at 16:03
  • You will need to know what your function $f(x)$ is. The iterates $x_0,x_1, \dots$ are determined by your function. So say for example your function is $f(x)=x-2/3$ (clearly, we know that the solution is $2/3$).

    You check that $f(0) <0$ and $f(2)>0$, and so $x_0=(2+0)/2=1$. Since $f(1)<0$, your new interval becomes $[1, 2]$.

    You will again that $f(1)<0$ and $f(2)>0$ and so your $x_1=(1+2)/2=3/2$. Since $f(3/2)>0$, your new interval will be $[1, 3/2]$.

    Notice that after the first two iterations, you have $x_0$ and $x_1$, you can use that to start checking for your stopping criteria.

     – ZanCoul Nov 19 '13 at 16:11