Re: HSC 2016 4U Marathon - Advanced Level
It was a calculus book. Some guy proved that it converges to a number only if the graph's concavity is towards the x axis.
Which book/guy? And what exactly do you mean by saying that the concavity is towards the x-axis? That in a small neigbourhood of the root the second derivative is non-positive? That the second derivative is non-positive on the whole real line? (Note also by symmetry that if functions with a certain concavity have convergent Newton iterates, then so will functions of the opposite concavity.)
Well I will post what is clear to me:
1. For Newton's method to be well defined, we must have f' nonzero. (Apart from the possibility of higher order zeros of f, which we will ignore for now).
This means that f' is always positive or always negative, that is, f is monotonic. Consequently f can have at most one zero, which we may assume is at x=0, by a change of variables. We also assume wlog that f is increasing.
2. Let g(x)=f(x)/f'(x), the correction term in Newton's method.
We have g'(x)=1-f(x)f''(x)/f''(x)^2, so 0 < g'(x) < 2 by the assumption.
3. The above implies 0 < g(x) < 2x for x > 0, and 2x < g(x) < 0 for negative x. Which implies that the (n+1)-th approximation from Newtons method is closer to the exact root than the n-th approximation.
4. If we have a concavity condition, like: f''(x) > 0 for x > 0 or f''(x)<0 for x < 0, then we can show that the Newton iterates eventually stay on the same side of the root, which implies they converge. (Monotone bounded sequences converge, a convergent sequence of Newton iterates must converge to a fixed point, i.e. a root.) This fact is completely independent of the bound 3. though and only used concavity and monotonicity. Furthermore, this concavity condition is not necessary for convergence, we can also have "bad concavity" near the root that leads the iterates to cross the root at each step...this process can still zigzag towards the root though.
Basically, I think you should be more precise in your question statement for something like this. There are lots of ways of guaranteeing convergence of Newton's method, but being able to say that Newton's ONLY works at a certain set of numbers is a much harder task, and I suspect your source question is not actually asking for this given the provided conditions.
