Let's take a little detour into discussing the rate of convergence. Let's give some useful definitions and prove one useful lemma. Okay. So the formal statement is this, suppose we have a sequence of iterates, which I'll call x0, x1, and so on. For simplicity, I will assume that each step only depends on the previous one. However, it's not very necessary, you can relax that if needs be. We define x star as a limit of the sequence if this limit exists, and we assume it exists. Then definition: this sequence converges with the rate of a geometric series with common ratio q if the following estimate holds: if the distance of the nth estimate from the limit is bounded by the common ratio to power n times, probably some constant, for all n larger than something. In that case, we say that the sequence converges to x star with a rate of a geometric series. Then, different definition is, the linear or non-linear, linear excuse me, or super linear convergence. Let's see. Suppose that our sequence satisfies the following condition: the distance of the n plus first iterate towards the root is bounded by the distance of the nth iterate from the root to some power p, and p is a constant. Then this p is called the rate of convergence. I used that word many times over, now it's time to give a precise definition. So the rate of convergence is this power p in the area bound for the n plus first iterate and nth iterate. Okay. Then if p is one, we say that we have a linear convergence. If p is larger than one, the convergence is superlinear. Okay. So we have two seemingly different sets of definitions, we have the definition of rate of convergence and we have the convergence with the rate of a geometric series. Are they related to each other? The answer is yes, and even we can formulate a lemma. So suppose we have a sequence which is linearly convergent, and then we can, first it's linearly convergent in some region around the root. Then if the start of our iteration is close enough to the root, we can state that first, all iterations stay within this range. Then the sequence converges with the rate of a geometric series with a common ratio of q. Remember q can be traced to the definition of the linear convergence. That's the factor in the relation between the errors or distance to the root at consecutive steps. Then the third and the most important ingredient statement of this lemma is that, we have an error bound for the nth iterate, so that's a distance to the root. For large enough n, this distance to the root is smaller than what we started with, the distance from my initial point to the root multiplied by the common ratio to power n. Clearly, this is the most important bit. So first of all if this 0.3 holds, and this distance is smaller than the size of my range, then all iterates are within the range and we have 0.1 following from three. Also, by just definitions, if three holds, then two holds as well. So in this lemma, actually the 0.3 is the most important one, two first ones are just calories. So let's prove this last bit, prove this lemma. The easiest way of proving it is by mathematical induction. It's often looks like little cheating, but this cheating is actually an axiom of mathematics. So we can use it. Let's see. Let's start with the base of induction, let's take n equals zero. Then, if n equals zero, the error bound obviously holds because here, the sign is less than or equal, so we have an equality sign. So we have a base of induction, then we do the inductive step. We suppose that the error bound holds for n minus one and we try to prove that it will hold for n, and that's reasonably simple. We have from the linear convergence, we have the relation between, from the assumption of linear convergence, we have the relation between these error bounds at steps n and an n minus one. Then by inductive assumption, we can bound further the n minus first difference by this q to power n minus one and then we collect everything, and we have our original statement proven. So just two steps; linear convergence and inductive assumption, and we're done. Okay. This was probably the technical and boring. But like I said, I will try to, in this module, I'm trying to give possible accessive details just to give you a flavor of how the proofs go even more complicated cases.