3 Consider the trisection method which is analogous to bisec

3) Consider the trisection method, which is analogous to bisection except that at each iteration, it creates 3 intervals instead of 2, ahd keeps one interval where there is a sign change.

a) Is the trisection method guaranteed to converge if the inital interval has a sign change? Why or why not?

b) Adapt the bisection code to create a code that performs tbe trisection method. Compare the results of bisection to trisection for \"myfun1.m\" for the same stopping tolerance, but several different starting intervals. How do the methods compare?

c) The main computational cost of bisection and trisection is function evaluations. The other operations it does is a few additions and divisions, but the evaluations of most functions, including sin, cos, exp, etc., are much more costly. Based on this information, explain why you would never want to use trisection over bisection.

Solution

Trisection method guaranteed to converge if the inital interval has a positive sign.

because If (b-a) > (if root is not found and level of desired accuracy is not reached.)

b) solution :- Following is the bisection code to create a code that performs tbe trisection method.

%To find the root of f(x)=0 in the interval of (a,b) using n partition
clear all, close all, clc
f = @(x) x.^3; %given function
a=10; %left endpoint of the interval
b=-10; %right endpoint of the interval
n= 4; % number of partitions (2 for bisection, 3 for trisection, etc…)
ep=10e-15; %tolerance lebvel
nmax=abs(log(ep/(b-a))/log(2)); %calculates the number of iteration needed
Nmax=ceil(nmax); %number of iteration
ya=f(a); yb=f(b); %computes the function value at the endpoint of the given interval
if ya*yb > 0,display ‘no root in this interval’,break,end %if no sign change
%while abs(b-a)>ep %iterate the program until the level of desired accuracy is achieved
for j=1:Nmax
x= linspace(a,b,n+1);% divide the interval into equal section with respect to n
for i=1:(n);
if (f(x(i))*f(x(i+1)))<=0; %when a sign change occur
tempa=x(i); %lower endpoint of the interval assignment
tempb=x(i+1); % upper endpoint of the interval assignment
end
end
a=tempa; b=tempb;
end
root=a

c)

The bisection method will converge on a root,
one may naturally ask if sectioning an interval in smaller sections could result in a faster convergence
and increase in efficiency.
If one partitions the interval in smaller sections the result would be a smaller error.
The bisection will reduce the error by a factor of 1/2 , trisection would reduce by 1/3 , and so on.
In the bisection method one only has to evaluate the point in the center.
For the trisection method it depends upon where the root is located.
If the root is located in the first third of the interval this will result in only one evaluation per iteration.
However, if the root is not in the first third then the result is two evaluations per iteration.
If considering the worst case scenario then the bisection has a distinct advantage over trisection.
Also, on average the trisection will result in more evaluations per iteration compared to the bisection
rendering the bisection as the more efficient method.
Of course one could make the argument that the trisection is more efficient
if the root is always with the first third of the interval
but the probability of this happening for several iterations is very unlikely.
Also, the smaller the partitions are results in the more evaluations per iteration and a decrease in efficiency.