So we have our fixed point problem, we have the iterative process, and we have examples of situations where it converges and where it doesn't. So we clearly need to prove something to make some statement of the convergence criteria. Here they are. Suppose there is a root. Suppose that in some neighborhood of this root and some range around it, the iterated function, our fixed point function Phi is differentiable, and the absolute value of its derivative is bounded with the bound, that's the most important part, that the bound is smaller than one if this works, if this holds, then we can start from some point in this neighborhood. My iterations will stay in that neighborhood U. The convergence will be converged with the rate of a geometric series. The common ratio in this series will be precisely this upper bound for the derivative. So in simple words, for the convergence of the fixed point iteration, we need to have our derivative of the fixed point function to be bounded by something which is less than one. Okay. So let's prove this theorem. This is fairly simple. We did all the hard work already. Let's see. So let's look at the iterate number n plus one, and distance to the root. It equals the distance of the fixed point function because of the way we organize our iterations. The fixed point function we assume that it's continuous and differentiable. Therefore, we can use the mean value theorem and say that this distance of the valence of Phi to points is the derivative at some point between them times the difference. So here Psi is some point. The mean value theorem actually asserts that this point Phi exists in this range from either iterate and the root such that this condition holds. By assumption, this derivative is bounded by q. So we take the absolute value of the right-hand side and left-hand side, and we have this condition which relates the deviations from the root at two successive steps. The rest is done by Lemma A. So like I said, we did all the hard work already. Okay. Then we've discussed how to perform this fixed point iterations. We've defined the conditions for the convergence. We have some idea about the convergence rate. Then we will talk about convergence rate quite a bit more. But first let's discuss this. We have our iterative process. When do we stop? Let's see. What we want, we want to find the fixed point with a predefined tolerance. We have a sequence of iterates. Then the question is, how do we know that we have achieved the target tolerance? We have a theorem which gives an error bound. But then the theorem, let's look at this. It tells you that the distance of the nth iterate from the true root is bounded by the distance from the initial point to the true root again and this upper limit for the derivative. But the main trouble is, we don't know x star. So we cannot readily use these error bound. This is formally called apriori error bound. We don't need to do any calculations to prove it in [inaudible] calculations, we've just proven it. So this works before we do any calculations. But what we actually need, we need an a posteriori bound. Meaning we need to be able to operate with the iterates with elements of our sequence and look at them, and at some points say, "Okay, enough, we're done, we've achieved. We have our acquired tolerance." So this is again the main difference between something which is apriori before the calculation, and a posteriori. Which in this context, it means during the calculation. In this case, we have this theorem two, which gives us this a posterior error bond. This will sound like this, it will connect what we want to achieve which is the distance to the true root, with what we can compute during the iterations. Literally, this theorem says that if the convergence theorem holds, then our target tolerance is bounded by the distance between consecutive iterates times some factor which depends on this queue, the upper bound of the derivative. So again that's a fairly typical setup, we first prove a theorem which gives us apriori bound. It's nice but not very useful. Then we need to prove something which relates this theoretical apriori bound with something which we can compute, with a posterior error bond. Then we use that in the calculations. So it's not hard to prove this. Again, we will use the mean value theorem. We take the distance from the nth iterate to the root, we use the fact that we're doing fixed-point iterations, then we use the mean value theorem, and then we play the trick which probably one of the most useful tricks ever mathematics, or in many parts of mathematics. We add and subtract something. Here we add and subtract x n. So then n one set of brackets, we have the distance between iterates, and in other brackets, we have the distance from the nth iterate to the route. So we have the distance to the root in the left-hand side, and in the right-hand side. This is precisely why I added x n. I wanted to get something in the left-hand side and right-hand side together. So we can combine these two bits together. Once, we've done this, we have the distance to the root, something which enters our apriori bound, and the distance between our estimates. They are related by the derivatives for our iterator function at some point. But we know that these derivatives are unbounded. So we take the absolute value, and we take the upper bound. We have the relation which was stated in the theorem. We have that the distance to the root is bounded by the distance between consecutive iterates times these combination of the skew, the upper bound for the derivative. Remember, q is smaller than one. So this combination is certainly known divergent. However, it can get large if q is close to one. So if we want to achieve a target tolerance of Epsilon, we carry on our iterations until the distance in consecutive iterates is larger than this Epsilon times this one minus q divided by q. That's what the theorem tells us. Well, it's not very convenient still, because it's not always easy to find the skew. Even if you know the q, it's just extra factor. So in practice, we often just drop it. We expect that if q is smaller than a half, then this factor is larger than one. Then we just say, "Okay, well, I'm going to iterate until the distance in iterates is, until the distance gets smaller than this predefined accuracy." This is not exactly the condition we wanted, but this is convenient enough. If q is small enough, is smaller than half, or if the convergence is fast enough, then it's justified.