2

Successive substitution is a technique, we learned, used to find the roots of a polynomial $f(x)=x^2-2$ for example. We must construct some function $g(x)$ so that $g(x)=x$ iff $f(x)=0$, for example $g(x)=f(x)+x$. It is done by taking some start value $u_0$, and creating a row $u_{i+1}=u_{i}+f(u_{i}).$ Basically what we're doing is projecting the function outputs on the $1st$ bissectrice $(?$, the line $y=x$), so normally it would converge to the point where this function $g(x)$ intersects the line $y=x$, and then this would be a solution to $f(x)=0$. However sometimes it is not the case, $u_i$ diverges and that is what my question is about.

It had something to do with the derivative of the function, but I want to know specifically, in what point? It is very hard to find any information about this on the internet, also it wasn't mentioned in my course. I THINK it was that the value of $|f'(a)|$ where $f(a)=0$, had to be $<1$ or $>1$ but I don't know which one! Does anyone have any knowledge on this topic, who could possibly help me. I know my question is very unclear, I am sorry, I hope someone will understand. Many thanks.

It looks like this: (when it converges)

successive substitution

steedsnisps
  • 665
  • http://en.wikipedia.org/wiki/Cobweb_plot – vadim123 Apr 13 '15 at 22:17
  • yes that's ít "in the cobweb plot, a stable fixed point corresponds to an inward spiral, en i an unstable fixed point is an outward one." but when is it stable, and when is it not? – steedsnisps Apr 13 '15 at 22:20

1 Answers1

2

If you want to (numerically) solve the equation $$g(x)=x$$ by choosing some starting point and iterating $g$, then in order for a solution $x_0$ to the above equation to attract nearby points to it, it must satisfy: $$|g'(x_0)|\leq 1$$ (Although, if $g'(x_0)=1$, it still might not attract nearby points). The reason for this is that we require that if we choose some $y$ near $x_0$ that $g(y)$ will be even closer to $x_0$ than $y$ was; so, if we take the linear approximation to $g$ near $x_0$ we have that $g$ is about (noting that $g(x_0)=x_0$): $$x_0+g'(x_0)(y-x_0)$$ and the distance of this term from $x_0$ is: $$|g'(x_0)(y-x_0)|$$ so the factor $g'(x_0)$ acts to scale $y$ towards $x_0$ - and if it's less than one, it's pulling $y$ closer. If it's more than one, it's pushing $y$ further away.

It's worth noting that other behaviors (like cycles) may occur, and that this becomes a deep topic of study quickly.

Milo Brandt
  • 60,888