2. Apply the bisection routine bisect(?) to find the root of the function f(x) =
ID: 638470 • Letter: 2
Question
2. Apply the bisection routine bisect(?) to find the root of the function f(x) = root x - 1.1 starting from the interval [0, 2] (that is a = 0 and b = 2), with tot = 1.e - 8. (a) How many iterations are required? Does the iteration count match the expectations, based on our convergence analysis? (b) What is the resulting absolute error? Could this absolute error be predicted by our convergence analysis?Explanation / Answer
function iterate (f$:call, x:numerical, n:natural=0, till=none, eps=none, best=false) Iterates f starting from x to convergence. This function iterates xnew=f(x), until xnew~=x (using the internal epsilon or the optional eps), or the maximal number of iterations n is exceeded. If >best is set the iteration will continue until abs(x-f(x)) does no longer get smaller. It returns the limit for n=0 (the default), or n iterated values. There is a "till" expression, which can also stop the iteration. f is either a function of a scalar returning a scalar, or a function of a vector returning a vector. The function will work with column or row vectors, and even for matrices, if n==0. f can also be an expression of a variable x. The iteration can also be used for intervals or interval vectors. In this case, The iteration will stop until the left and right interval bounds are closer than epsilon. If >best is set the iteration continues until the interval length does not get any smaller. f : function or expression x : start point for the algorithm n : optional number of steps (0 = till convergence) till : optional end condition best : Iterate until best result is achieved (takes long if the limit is 0). >iterate("cos",1) // solves cos(x)=x, iterating from 1 0.739085133216 >longest iterate("(x+2/x)/2",1,n=7)' 1 1.5 1.416666666666667 1.41421568627451 1.41421356237469 1.414213562373095 1.414213562373095 1.414213562373095 >iterate("x+1",1000,till="isprime(x)") 1009 >function f(x,A,b) := A.x-b >A=random(3,3)/2; b=sum(A); >iterate("f",zeros(3,1);A,b) -11.7766 -12.4523 -14.938 >iterate("(middle(x)+2/x)/2",~1,2~) // interval iteration ~1.414213562372,1.414213562374~ >iterate("(x+I/x)/2",1) // complex iteration 0.707107+0.707107i Returns {x,n}, where n is the number of iterations needed function niterate (f$:call, x:numerical, n:natural, till=none) Iterates f n times starting from x. Works like iterate with n>0. f : function or expression x : start point for the algorithm n : number of iterations till : optional end condition Returns v, where v is the vector of iterations and n the number of iterations. function sequence (f$:call, x:numerical, n:natural) Computes sequences recursively. This function can be used to compute x[n]=f(x[1],...,x[n-1]) recursively. It will work for scalar x[i], or for column vectors x[i]. Depending on the iteration function, more than one start value x[1] to x[k] is needed. These start values are stored in a row vector x0 (or in a matrix for vector iteration). The iteration counter n can be used in the expression. f$ must be a function f$(x,n), or an expression in x an n. The parameter x contains the values x[1],...,x[n-1] computed so far as elements of a row vector, or as columns in a matrix x. In case of a vector sequence, the function can also work with row vectors, depending on the result of the function f$. Note, that the start value must fit to the result of the function. f$ : function f$(x,n) where x is m x (n-1) or (n-1) x m, and the result m x 1 or 1 x m x : start values (m x k or k x m) n : desired number of values >sequence("x[n-1]+x[n-2]",[1,1],10) [1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >sequence("n*x[n-1]",1,9) [1, 2, 6, 24, 120, 720, 5040, 40320, 362880] >A=[1,2;3,4]; sequence("A.x[,n-1]",[1;1],5) 1 3 17 91 489 1 7 37 199 1069 >matrixpower(A,4).[1;1] // more efficiently 489 1069 >function f(x,n) := mean(x[n-4:n-1]) >plot2d(sequence("f",1:4,20)): See: iterate (Numerical Algorithms) function steffenson (f$:call, x:scalar, n:natural=0, eps=none) Does n steps of the Steffenson operator, starting from x. This is a similar function as iterate. However, the function assumes an asymptotic expansion of the error of the convergence, and uses the Steffenson operator to speed up the convergence. f$ is either a function of a scalar returning a scalar, or a function of a column vector returning a column vector. f can also be an expression of a variable x. f$ : function or expression of a scalar x x : start point n : optional number of iterations See: iterate (Numerical Algorithms) function nsteffenson (f$:call, x0:scalar, n:natural, eps=none) Does n steps of the Steffenson operator, starting from x0. Works like "steffenson", but returns the history of the iteration. See: niterate (Numerical Algorithms) function aitkens (x: vector) Improves the convergence of the sequence x. The Aitkens operator assumes that a-x[n] has a geometric convergence 1/c^n to 0. With this information, it is easy to compute the limit a. x : row vector (1xn, n>2) Return a row vector (1x(n-2)) with faster convergence. >v=iterate("cos",1,40); longest v[-1] 0.7390851699445544 >longest aitkens(v)[-1] 0.7390851332151597 >longest iterate("cos",1) 0.7390851332157367 See: steffenson (Numerical Algorithms)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.