Iterative methods







Numerical Methods

Iterative methods

The equation $F(x)=0$ can be transformed into the form,

\[ \begin{equation}\label{gl2} x=f(x). \end{equation} \]

This can be used to seek the zeros of $F(x)$ by iteration.

\[ \begin{eqnarray}\label{gladd} x_{0} & & \mbox{ Starting value} \nonumber\\ x_{1} & = & f(x_{0}) \nonumber\\ x_{2} & = & f(x_{1}) \nonumber\\ & . & \nonumber\\ & . & \nonumber\\ x_{t+1} & = & f(x_{t}) \qquad (t=0,1,2,\ldots) \end{eqnarray} \]

If the method converges, this iteration can lead arbitrarily close to the exact solution of the problem (within roundoff error),

\[ \lim_{t \to \infty} x_{t} \to x_{exact} \]

There is no guarantee that this method will converge. The convergence depends strongly from the way in which $F(x)=0$ is reformulated into $x=f(x)$. One formulation is $f(x)=F(x)+x$ however other formulations can sometimes be found that converge better.

Consider the function $F(x)=x^{3}-x-5$ in the vicinity of $x=2$. Three reformulations of this equation into a form $x=f(x)$ are,

\[ a)\quad x=x^{3}-5 \qquad b) \quad x=\frac{5}{x^{2}-1} \qquad c) \quad x=\sqrt[3]{x+5} \]

Iterating the first two forms results in a diverging series while $c)$ converges quickly to a root of $x^{3}-x-5=0$. A condition for convergence is $\left|\frac{df}{dx}\right| < 1$ at the root.

Code that iterates these equations is given below.

<script language="javascript" type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.2.6/jquery.js"></script> <script language="javascript" type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/flot/0.8.3/jquery.flot.min.js"></script> <script> var dx = []; //array used for plotting x var df = []; //array used for plotting f(x) var xn = []; //array used for plotting iterations function f(x) { return xxx - 5; } $(document).ready(function(){ x0 = 2; txt = ""; //text output n = 0; for (i=0; i<10; i++) { txt += "x<sub>"+i+"<\/sub> = "+x0+"<br \/>" xn[n] = [x0,x0]; n++; x1 = f(x0); xn[n] = [x0,x1]; n++; x0 = x1; } //generate data for the plot of f(x) for (i=0; i<400; i++) { x = i/100; df[i] = [x,f(x)]; } dx[0] = [0,0]; dx[1] = [4,4]; document.getElementById('iterations').innerHTML=txt; var data1 = [{ data: dx, color: "rgb(0,0, 0)", shadowSize:0, lines: {show:true} }, { data: df, color: "rgb(200,0, 0)", shadowSize:0, lines: {show:true}, label: "f(x)" }, { data: xn, color: "rgb(200,200, 200)", shadowSize:0, lines: {show:true}, points: {show:true} }]; $.plot($("#placeholder"), data1,{xaxis:{ min: 0, max: 4}, yaxis:{ min: 0, max: 4}}); }); </script> <table><tr><td valign="middle"><i>f</i>(<i>x</i>)</td><td> <div id="placeholder" style="width:400px;height:300px;"></div> </td></tr><tr><td></td><td><p style="text-align:center"><i>x</i></p></td></tr></table> <p style="margin-left:3cm" id="iterations"></p>

var dx = []; //array used for plotting x
  var df = []; //array used for plotting f(x)
  var xn = []; //array used for plotting iterations

function f(x) {
    return x*x*x - 5;
  }

$(document).ready(function(){
  x0 = 2;
  txt = ""; //text output
  n = 0;
  for (i=0; i<10; i++) {
    txt += "x<sub>"+i+"<\/sub> = "+x0+"<br \/>"
    xn[n] = [x0,x0]; n++;
    x1 = f(x0);
    xn[n] = [x0,x1]; n++;
    x0 = x1;
  }

//generate data for the plot of  f(x) 
  for (i=0; i<400; i++) {
    x = i/100;
    df[i] = [x,f(x)]; 
  }

dx[0] = [0,0];
  dx[1] = [4,4];

document.getElementById('iterations').innerHTML=txt;

var data1 = [{ data: dx, color: "rgb(0,0, 0)", shadowSize:0, lines: {show:true} }, { data: df, color: "rgb(200,0, 0)", shadowSize:0, lines: {show:true}, label: "f(x)" }, { data: xn, color: "rgb(200,200, 200)", shadowSize:0, lines: {show:true}, points: {show:true} }];
  $.plot($("#placeholder"), data1,{xaxis:{ min: 0, max: 4}, yaxis:{ min: 0, max: 4}});

});

</script>
<table><tr><td valign="middle"><i>f</i>(<i>x</i>)</td><td>
<div id="placeholder" style="width:400px;height:300px;"></div>
</td></tr><tr><td></td><td><p style="text-align:center"><i>x</i></p></td></tr></table>

var dx = []; //array used for plotting x
  var df = []; //array used for plotting f(x)
  var xn = []; //array used for plotting iterations

function f(x) {
    return 5/(x*x-1);
  }

//generate data for the plot of  f(x) 
  for (i=0; i<400; i++) {
    x = i/100;
    df[i] = [x,f(x)]; 
  }

dx[0] = [0,0];
  dx[1] = [4,4];

document.getElementById('iterations').innerHTML=txt;

});

var dx = []; //array used for plotting x
  var df = []; //array used for plotting f(x)
  var xn = []; //array used for plotting iterations

function f(x) {
    return Math.pow(x+5,1/3);
  }

//generate data for the plot of  f(x) 
  for (i=0; i<400; i++) {
    x = i/100;
    df[i] = [x,f(x)]; 
  }

dx[0] = [0,0];
  dx[1] = [4,4];

document.getElementById('iterations').innerHTML=txt;

});