Скачать книгу
href="#fb3_img_img_c3ca72c0-9fa0-5f15-b772-9b5b483e0dfd.png" alt="images"/>, with
. Overall, after
bisections, the tolerance is
, becoming halved in the next iteration.
If we evaluate the radicals that appear in (1.3) with a scientific calculator, we can check that Cardano's analytical solution is approximately . Expression (1.3) is mathematically elegant, but not very practical if one needs an estimation of its numerical value. For we already have that estimation nearly within a or relative error. The reader may keep iterating further to provide better approximations of , overall obtaining the sequence . A natural question is whether this sequence has a limit. This leads to the mathematical concept of convergence of a sequence:
Convergence (Exact): The sequence is said to be convergent to if or, equivalently, if , where .
The difference appearing in the previous definition is called the error associated with . However, since may be positive or negative and we are just interested in the absolute discrepancy between and the root , it is common practice to define the absolute error of the th iterate. Checking convergence numerically using the previous definition has two main drawbacks. The first one is that we do not know the value of , which is precisely the goal of root‐finding. The second is that in practice we cannot perform an infinite number of iterations in order to compute the limit as , and therefore we must substitute the convergence condition by a numerically feasible one. For example, looking at the sequence resulting from the bisection method, it is clear that the absolute difference of two consecutive elements decreases when increasing (for example, and ). Since, by construction, the bisection sequence satisfies , it is common practice to consider a sequence as converged when this difference becomes smaller than a prescribed threshold or tolerance :
Convergence (Practical): A sequence is said to be converged to the desired tolerance after iterations if , .
The criterion above only refers to the convergence of a sequence, and not necessarily to the convergence to a root. After an iterative method has apparently converged to some stagnated value , it is always advisable to check the magnitude of in order to confirm if the method has succeeded. The code below is a simple implementation of the bisection method using the tolerance criterion previously described:
% Code 1: Bisection method for solving f(x) = 0 in [a,b] % Input: 1. [a,b]: interval (it assumes that f(a)f(b) < 0) % 2. tol: tolerance so that abs(x_k+1 - x_k) < tol % 3. itmax: maximum number of iterations allowed % 4. fun: function's name % Output: 1. xk: resulting sequence % 2. res: resulting residuals % 3. it: number of required iterations function [xk,res,it] = bisection(a,b,tol,itmax,fun) ak = a; bk = b; xk = []; res = []; it = 0; tolk = abs(bk-ak)/2 ; while it < itmax & tolk > tol ck = (ak + bk)/2; xk = [xk ck]; if it > 0; tolk = abs(xk(end)-xk(end-1)); end fa = feval(fun,ak); fc = feval(fun,ck); res = [res abs(fc)]; if fc*fa < 0; bk = ck; else ak = ck; end it = it + 1 ; end
In the previous code, the iterations stop either when the number of iterations reaches itmax or when tol, i.e. the condition for practical convergence. This condition therefore provides what is usually known as a stopping criterion for root‐finding methods such as the bisection and other algorithms. However, two words of caution deserve to be mentioned at this point. First, we are implicitly assuming that since seems to be a Cauchy Sequence6 (that is, decreases with increasing ), its convergence is guaranteed. While a convergent sequence must necessarily be of Cauchy type, the reverse statement is, in general, not true (although here it will be assumed to be). Second, the quantity has disappeared from the convergence criteria. In other words, once for some and beyond, we only know that the sequence has converged (in the practical sense) to some value , that henceforth will play the role of the numerical root within the prescribed tolerance.
Finally, the bisection code also provides the vector res containing the sequence of absolute quantities
Скачать книгу
