Chapter 2.1 5A.
## we first define the R function based on the given equation
fn = function(x){
f.val = x-2**(-x)
f.val
}
## INPUT INFO
a = 0
b = 1
TOL = 10**(-5) # tolerance limit
N = 200 # max iterations
## Initialization
n = 0
ERR = abs(b - a)
## Loop begins
while(ERR > TOL){
5
n = n + 1
m = a + (b - a) / 2 # midpoint of interval [a, b]
if (fn(m)*fn(b) < 0){ # new interval should be [m, b]
a = m # m will be the new a
b = b
} else { # new interval should be [a,m]
a = a
b = m # m will be the new 'b'
}
ERR = abs(b - a) # updated absolute error
## Output information
if(ERR < TOL){ # if the absolute error is less than TOL, print out results
cat("\nThe algorithm converges!")
cat("\nThe number of iteration n =", n, ".")
cat("\nThe approximate root r =", (a + b)/2,".")
cat("\nThe absolute error ERR =", ERR,".")
break
} else { ## output of intermediate iteration
cat("\nIteration:",n,". The absolute error ERR =", ERR, ".")
}
### Test attainment to the max iteration
if(n == N){
cat("\n\n Iteration limit reached. The algorithm diverges!")
break
}
}##
## Iteration: 1 . The absolute error ERR = 0.5 .
## Iteration: 2 . The absolute error ERR = 0.25 .
## Iteration: 3 . The absolute error ERR = 0.125 .
## Iteration: 4 . The absolute error ERR = 0.0625 .
## Iteration: 5 . The absolute error ERR = 0.03125 .
## Iteration: 6 . The absolute error ERR = 0.015625 .
## Iteration: 7 . The absolute error ERR = 0.0078125 .
## Iteration: 8 . The absolute error ERR = 0.00390625 .
## Iteration: 9 . The absolute error ERR = 0.001953125 .
## Iteration: 10 . The absolute error ERR = 0.0009765625 .
## Iteration: 11 . The absolute error ERR = 0.0004882812 .
## Iteration: 12 . The absolute error ERR = 0.0002441406 .
## Iteration: 13 . The absolute error ERR = 0.0001220703 .
## Iteration: 14 . The absolute error ERR = 6.103516e-05 .
## Iteration: 15 . The absolute error ERR = 3.051758e-05 .
## Iteration: 16 . The absolute error ERR = 1.525879e-05 .
## The algorithm converges!
## The number of iteration n = 17 .
## The approximate root r = 0.6411858 .
## The absolute error ERR = 7.629395e-06 .my_fun1 <- function(x) {x} # Create own functions
my_fun2 <- function(x) {2*sin(x)}
curve(my_fun1, from = - 2, to = 2, col = 2) # Draw Base R plot
curve(my_fun2, from = - 2, to = 2, col = 3, add = TRUE)
## we first define the R function based on the given equation
fn = function(x){
f.val = x-2*sin(x)
f.val
}
## INPUT INFO
a = 1.8
b = 2.0
TOL = 10**(-5) # tolerance limit
N = 200 # max iterations
## Initialization
n = 0
ERR = abs(b - a)
## Loop begins
while(ERR > TOL){
5
n = n + 1
m = a + (b - a) / 2 # midpoint of interval [a, b]
if (fn(m)*fn(b) < 0){ # new interval should be [m, b]
a = m # m will be the new a
b = b
} else { # new interval should be [a,m]
a = a
b = m # m will be the new 'b'
}
ERR = abs(b - a) # updated absolute error
## Output information
if(ERR < TOL){ # if the absolute error is less than TOL, print out results
cat("\nThe algorithm converges!")
cat("\nThe number of iteration n =", n, ".")
cat("\nThe approximate root r =", (a + b)/2,".")
cat("\nThe absolute error ERR =", ERR,".")
break
} else { ## output of intermediate iteration
cat("\nIteration:",n,". The absolute error ERR =", ERR, ".")
}
### Test attainment to the max iteration
if(n == N){
cat("\n\n Iteration limit reached. The algorithm diverges!")
break
}
}##
## Iteration: 1 . The absolute error ERR = 0.1 .
## Iteration: 2 . The absolute error ERR = 0.05 .
## Iteration: 3 . The absolute error ERR = 0.025 .
## Iteration: 4 . The absolute error ERR = 0.0125 .
## Iteration: 5 . The absolute error ERR = 0.00625 .
## Iteration: 6 . The absolute error ERR = 0.003125 .
## Iteration: 7 . The absolute error ERR = 0.0015625 .
## Iteration: 8 . The absolute error ERR = 0.00078125 .
## Iteration: 9 . The absolute error ERR = 0.000390625 .
## Iteration: 10 . The absolute error ERR = 0.0001953125 .
## Iteration: 11 . The absolute error ERR = 9.765625e-05 .
## Iteration: 12 . The absolute error ERR = 4.882812e-05 .
## Iteration: 13 . The absolute error ERR = 2.441406e-05 .
## Iteration: 14 . The absolute error ERR = 1.220703e-05 .
## The algorithm converges!
## The number of iteration n = 15 .
## The approximate root r = 1.895493 .
## The absolute error ERR = 6.103516e-06 .x= seq(2, 3, length = 200)
y = x**3-25
#
4## [1] 4plot(x, y,
type = "l",
lty = 1,
lwd = 2,
col = "blue",
xlab = "X",
ylab = "Y",
main = "The curve of y = x^3-25")
abline(h = 0, lty = 2, lwd = 1, col = "darkred")
## we first define the R function based on the given equation
fn = function(x){
f.val = x**3 - 25
f.val
}
## INPUT INFO
a = 2
b = 3
TOL = 10**(-4) # tolerance limit
N = 200 # max iterations
## Initialization
n = 0
ERR = abs(b - a)
## Loop begins
while(ERR > TOL){
5
n = n + 1
m = a + (b - a) / 2 # midpoint of interval [a, b]
if (fn(m)*fn(b) < 0){ # new interval should be [m, b]
a = m # m will be the new a
b = b
} else { # new interval should be [a,m]
a = a
b = m # m will be the new 'b'
}
ERR = abs(b - a) # updated absolute error
## Output information
if(ERR < TOL){ # if the absolute error is less than TOL, print out results
cat("\nThe algorithm converges!")
cat("\nThe number of iteration n =", n, ".")
cat("\nThe approximate root r =", (a + b)/2,".")
cat("\nThe absolute error ERR =", ERR,".")
break
} else { ## output of intermediate iteration
cat("\nIteration:",n,". The absolute error ERR =", ERR, ".")
}
### Test attainment to the max iteration
if(n == N){
cat("\n\n Iteration limit reached. The algorithm diverges!")
break
}
}##
## Iteration: 1 . The absolute error ERR = 0.5 .
## Iteration: 2 . The absolute error ERR = 0.25 .
## Iteration: 3 . The absolute error ERR = 0.125 .
## Iteration: 4 . The absolute error ERR = 0.0625 .
## Iteration: 5 . The absolute error ERR = 0.03125 .
## Iteration: 6 . The absolute error ERR = 0.015625 .
## Iteration: 7 . The absolute error ERR = 0.0078125 .
## Iteration: 8 . The absolute error ERR = 0.00390625 .
## Iteration: 9 . The absolute error ERR = 0.001953125 .
## Iteration: 10 . The absolute error ERR = 0.0009765625 .
## Iteration: 11 . The absolute error ERR = 0.0004882812 .
## Iteration: 12 . The absolute error ERR = 0.0002441406 .
## Iteration: 13 . The absolute error ERR = 0.0001220703 .
## The algorithm converges!
## The number of iteration n = 14 .
## The approximate root r = 2.924042 .
## The absolute error ERR = 6.103516e-05 .Chapter 2.2 1. A. f(x)= x4+2x2-x-3 –> (x+3-2x2)(1/4)=x B. f(x)= x4+2x2-x-3 –> ((3+x-2x2)/2)(1/2)=x C. f(x)= x4+2x2-x-3 –> ((x+3)/(x2+2))(1/2)=x D. f(x)= x4+2x2-x-3 –> ((3x4+2x2+3))/(4x^3+4x-1))=x
g=expression(pi + 0.5*sin(x/2))
D(g,'x')## 0.5 * (cos(x/2) * (1/2))Clearly this function exists on (0, 2pi). g’(x) is 0 when x = pi. Now do g(0)= pi, g(pi)= pi + 0.5, g(2pi)= pi Now take absolute value of g’(x) |.25cos(x/2)| <= .25 which is true for all values [0,2pi] Therefore g(x) has a unique fixed point in [0,2pi]
12A.
## input values
TOL = 10**(-5)
M = 200
####
gfun = function(x) 2+sin(x)
####
a = 2
b = 3
x = 1 # initial value of x
n = 0 # initializing iterator
ERR = Inf # initial error
##
while (ERR > TOL){
n = n + 1
new.x = gfun(x)
ERR = abs(new.x - x)
if(ERR < TOL){
cat("\n\nThe algorithm converges!")
cat("\nThe approximate root is:", new.x,".")
cat("\nThe absolute error is:", ERR, ".")
cat("\nThe number of iterations is:", n, ".")
break
} else{
if(ERR > 10**7){
cat("\n\nThe algorithm diverges!")
break
} else{
4
cat("\nIteration:",n,". Estimated root:", new.x, ". Absolute error:", ERR,".")
x = new.x # update x value!!!
}
}
if(n == M){
cat("\n\nThe maximum number of iterations is achieved!")
break
}
}##
## Iteration: 1 . Estimated root: 2.841471 . Absolute error: 1.841471 .
## Iteration: 2 . Estimated root: 2.295636 . Absolute error: 0.5458345 .
## Iteration: 3 . Estimated root: 2.748605 . Absolute error: 0.452969 .
## Iteration: 4 . Estimated root: 2.38295 . Absolute error: 0.3656558 .
## Iteration: 5 . Estimated root: 2.687937 . Absolute error: 0.3049876 .
## Iteration: 6 . Estimated root: 2.438254 . Absolute error: 0.2496831 .
## Iteration: 7 . Estimated root: 2.646768 . Absolute error: 0.2085134 .
## Iteration: 8 . Estimated root: 2.474878 . Absolute error: 0.1718898 .
## Iteration: 9 . Estimated root: 2.618408 . Absolute error: 0.14353 .
## Iteration: 10 . Estimated root: 2.499642 . Absolute error: 0.1187661 .
## Iteration: 11 . Estimated root: 2.598759 . Absolute error: 0.09911769 .
## Iteration: 12 . Estimated root: 2.516564 . Absolute error: 0.08219511 .
## Iteration: 13 . Estimated root: 2.58512 . Absolute error: 0.06855624 .
## Iteration: 14 . Estimated root: 2.528194 . Absolute error: 0.05692638 .
## Iteration: 15 . Estimated root: 2.57565 . Absolute error: 0.04745583 .
## Iteration: 16 . Estimated root: 2.536212 . Absolute error: 0.03943797 .
## Iteration: 17 . Estimated root: 2.569075 . Absolute error: 0.03286336 .
## Iteration: 18 . Estimated root: 2.54175 . Absolute error: 0.02732548 .
## Iteration: 19 . Estimated root: 2.564513 . Absolute error: 0.02276305 .
## Iteration: 20 . Estimated root: 2.545579 . Absolute error: 0.0189338 .
## Iteration: 21 . Estimated root: 2.561348 . Absolute error: 0.01576891 .
## Iteration: 22 . Estimated root: 2.548229 . Absolute error: 0.01311928 .
## Iteration: 23 . Estimated root: 2.559153 . Absolute error: 0.01092454 .
## Iteration: 24 . Estimated root: 2.550063 . Absolute error: 0.009090329 .
## Iteration: 25 . Estimated root: 2.557632 . Absolute error: 0.007568714 .
## Iteration: 26 . Estimated root: 2.551333 . Absolute error: 0.006298615 .
## Iteration: 27 . Estimated root: 2.556577 . Absolute error: 0.005243871 .
## Iteration: 28 . Estimated root: 2.552213 . Absolute error: 0.00436422 .
## Iteration: 29 . Estimated root: 2.555846 . Absolute error: 0.003633195 .
## Iteration: 30 . Estimated root: 2.552822 . Absolute error: 0.003023884 .
## Iteration: 31 . Estimated root: 2.555339 . Absolute error: 0.002517269 .
## Iteration: 32 . Estimated root: 2.553244 . Absolute error: 0.002095179 .
## Iteration: 33 . Estimated root: 2.554988 . Absolute error: 0.001744109 .
## Iteration: 34 . Estimated root: 2.553536 . Absolute error: 0.001451695 .
## Iteration: 35 . Estimated root: 2.554745 . Absolute error: 0.001208424 .
## Iteration: 36 . Estimated root: 2.553739 . Absolute error: 0.001005838 .
## Iteration: 37 . Estimated root: 2.554576 . Absolute error: 0.0008372715 .
## Iteration: 38 . Estimated root: 2.553879 . Absolute error: 0.0006969155 .
## Iteration: 39 . Estimated root: 2.554459 . Absolute error: 0.0005801151 .
## Iteration: 40 . Estimated root: 2.553977 . Absolute error: 0.0004828713 .
## Iteration: 41 . Estimated root: 2.554379 . Absolute error: 0.0004019413 .
## Iteration: 42 . Estimated root: 2.554044 . Absolute error: 0.0003345663 .
## Iteration: 43 . Estimated root: 2.554322 . Absolute error: 0.0002784913 .
## Iteration: 44 . Estimated root: 2.554091 . Absolute error: 0.0002318103 .
## Iteration: 45 . Estimated root: 2.554284 . Absolute error: 0.0001929571 .
## Iteration: 46 . Estimated root: 2.554123 . Absolute error: 0.0001606139 .
## Iteration: 47 . Estimated root: 2.554257 . Absolute error: 0.0001336934 .
## Iteration: 48 . Estimated root: 2.554145 . Absolute error: 0.0001112841 .
## Iteration: 49 . Estimated root: 2.554238 . Absolute error: 9.263168e-05 .
## Iteration: 50 . Estimated root: 2.554161 . Absolute error: 7.710512e-05 .
## Iteration: 51 . Estimated root: 2.554225 . Absolute error: 6.418139e-05 .
## Iteration: 52 . Estimated root: 2.554172 . Absolute error: 5.34236e-05 .
## Iteration: 53 . Estimated root: 2.554216 . Absolute error: 4.446914e-05 .
## Iteration: 54 . Estimated root: 2.554179 . Absolute error: 3.701545e-05 .
## Iteration: 55 . Estimated root: 2.55421 . Absolute error: 3.081119e-05 .
## Iteration: 56 . Estimated root: 2.554184 . Absolute error: 2.564679e-05 .
## Iteration: 57 . Estimated root: 2.554206 . Absolute error: 2.134805e-05 .
## Iteration: 58 . Estimated root: 2.554188 . Absolute error: 1.776981e-05 .
## Iteration: 59 . Estimated root: 2.554203 . Absolute error: 1.479135e-05 .
## Iteration: 60 . Estimated root: 2.55419 . Absolute error: 1.231211e-05 .
## Iteration: 61 . Estimated root: 2.554201 . Absolute error: 1.024844e-05 .
##
## The algorithm converges!
## The approximate root is: 2.554192 .
## The absolute error is: 8.530655e-06 .
## The number of iterations is: 62 .Chapter 2.3 2. We start off with P_0 = -1 and put that in for x =
# Define f(x) and f'(x)
fn = function(x) -x**3-cos(x)
dfn = function(x) sin(x)-3*x**2
# initial values
n = 0
x = -1
M = 200
TOL = 10^(-6)
ERR = abs(fn(x)/dfn(x))
# loop begins
while(ERR > TOL){
n = n + 1
x = x - fn(x)/dfn(x)
ERR = abs(fn(x)/dfn(x))
if(ERR < TOL){
cat("\n\nAlgorithm converges!")
cat("\nThe approximated root:", x, ".")
cat("\nThe absolute error:", ERR, ".")
cat("\nThe number of iterations n =",n,".")
break
} else{
cat("\nIteration n =",n, ", approximate root:",x,", absolute error:", ERR,".")
}
if (n ==M){
cat("\n\nThe maximum iterations attained!")
cat("\nThe algorithm did not converge!")
break
}
}##
## Iteration n = 1 , approximate root: -0.8803329 , absolute error: 0.01464874 .
## Iteration n = 2 , approximate root: -0.8656842 , absolute error: 0.0002100872 .
##
## Algorithm converges!
## The approximated root: -0.8654741 .
## The absolute error: 4.285136e-08 .
## The number of iterations n = 3 .Here we use P_0=0 and put that in for x =
# Define f(x) and f'(x)
fn = function(x) -x**3-cos(x)
dfn = function(x) sin(x)-3*x**2
# initial values
n = 0
x = -1 # we would put in 0 here for x which results in an error message
M = 200
TOL = 10^(-6)
ERR = abs(fn(x)/dfn(x))
# loop begins
while(ERR > TOL){
n = n + 1
x = x - fn(x)/dfn(x)
ERR = abs(fn(x)/dfn(x))
if(ERR < TOL){
cat("\n\nAlgorithm converges!")
cat("\nThe approximated root:", x, ".")
cat("\nThe absolute error:", ERR, ".")
cat("\nThe number of iterations n =",n,".")
break
} else{
cat("\nIteration n =",n, ", approximate root:",x,", absolute error:", ERR,".")
}
if (n ==M){
cat("\n\nThe maximum iterations attained!")
cat("\nThe algorithm did not converge!")
break
}
}##
## Iteration n = 1 , approximate root: -0.8803329 , absolute error: 0.01464874 .
## Iteration n = 2 , approximate root: -0.8656842 , absolute error: 0.0002100872 .
##
## Algorithm converges!
## The approximated root: -0.8654741 .
## The absolute error: 4.285136e-08 .
## The number of iterations n = 3 .It is not possible since we get an error message. This is because when we plug in x = 0 into the first derivative of f(x) we get f’(0) = 0
3A. Secant
########################################
## Root Finding: Secant Method
#########################################
SecantMethod = function(fn, # input function
TOL, # error tolerance
max.iter = 100, # max allowed iterations
x1, # initial value #1
x2, # initial value #2
detail = TRUE, # output intermediate output
## adding controls for the graphic
graphic = TRUE, # default
xlimit, # x-limits: a vector of lower and upper limits
ylimit, # y-limits: a vector of lower and upper limits
... # other optional arguments if any
){
ctr = 0 # counter of iteration
ERR = abs(x2 - x1)
## base graph
if(graphic ==TRUE){
xx = seq(xlimit[1], xlimit[2], length = 500) # x-coordinates
yy = fn(xx) # y-coordinates
plot(xx, yy, type = "l",
xlab = "x",
ylab = "Y",
xlim = xlimit,
ylim = ylimit,
lwd = 2,
col = "blue",
lty = 1)
}
abline(h = 0, lty = 2, col = "navy")
##
while(ERR > TOL){
ctr = ctr + 1
new.x = x2 - fn(x2) * (x2 - x1) / (fn(x2) - fn(x1))
ERR = abs(new.x - x2)
if(ERR < TOL){
cat("\n\nThe algorithm converges!")
cat("\nThe approximated root is", new.x,".")
cat("\nThe absolute relative error ERR=",ERR,".")
cat("\nThe number of iterations:", ctr, ".")
break
} else{
if(graphic == TRUE){
segments(x2, fn(x2), x1, fn(x1), lty = 1, col = "purple")
segments(new.x, fn(new.x), new.x, 0, col = "red", lty = 2)
}
if(detail == TRUE){
cat("\nIteration:", ctr,", approximated root:", new.x,", absolute relative error:", ERR,".")
}
# updating the two values. CAUTION: order matters
x1 = x2
x2 = new.x
}
if(ctr == max.iter){
cat("\n\nThe maximum number of iterations attained!")
cat("\nThe algorithm did not converge!")
break
}
} # close the while-loop
} # close the function environment# define the function f(x) that satisfies f(x) = 0
test_func = function(x){x**2-6}
###
# call the function
SecantMethod(fn = test_func, # input function
TOL = 10^(-8), # error tolerance
max.iter = 100, # max allowed iterations
x1=3, # initial value #1
x2=2, # initial value #2
detail=TRUE, # output intermediate output
## adding controls for the graphic
graphic = TRUE, # default
xlimit=c(0,3), # x-limits: a vector of lower and upper limits
ylimit = c(-1, 35) # y-limits: a vector of lower and upper limits
)
##
## Iteration: 1 , approximated root: 2.4 , absolute relative error: 0.4 .
## Iteration: 2 , approximated root: 2.454545 , absolute relative error: 0.05454545 .
## Iteration: 3 , approximated root: 2.449438 , absolute relative error: 0.005107252 .
## Iteration: 4 , approximated root: 2.44949 , absolute relative error: 5.14874e-05 .
## Iteration: 5 , approximated root: 2.44949 , absolute relative error: 5.313575e-08 .
##
## The algorithm converges!
## The approximated root is 2.44949 .
## The absolute relative error ERR= 5.591083e-13 .
## The number of iterations: 6 .P_3 is iteration 3 which is 2.449438
11A. False Position
########################################
## Root Finding: False Method
#########################################
FalseMethod = function(fn, # input function
TOL, # error tolerance
max.iter = 100, # max allowed iterations
x1, # initial value #1
x2, # initial value #2
x3,
detail = TRUE, # output intermediate output
## adding controls for the graphic
graphic = TRUE, # default
xlimit, # x-limits: a vector of lower and upper limits
ylimit, # y-limits: a vector of lower and upper limits
... # other optional arguments if any
){
ctr = 0 # counter of iteration
ERR = abs(x2 - x1)
## base graph
if(graphic ==TRUE){
xx = seq(xlimit[1], xlimit[2], length = 500) # x-coordinates
yy = fn(xx) # y-coordinates
plot(xx, yy, type = "l",
xlab = "x",
ylab = "Y",
xlim = xlimit,
ylim = ylimit,
lwd = 2,
col = "blue",
lty = 1)
}
abline(h = 0, lty = 2, col = "navy")
##
while(ERR > TOL){
ctr = ctr + 1
new.x = x1-((x2-x1)*fn(x1))/(fn(x2)-fn(x1))
ERR = abs(new.x - x2)
if(ERR < TOL){
cat("\n\nThe algorithm converges!")
cat("\nThe approximated root is", new.x,".")
cat("\nThe absolute relative error ERR=",ERR,".")
cat("\nThe number of iterations:", ctr, ".")
break
} else{
if(graphic == TRUE){
segments(x2, fn(x2), x1, fn(x1), lty = 1, col = "purple")
segments(new.x, fn(new.x), new.x, 0, col = "red", lty = 2)
}
if(detail == TRUE){
cat("\nIteration:", ctr,", approximated root:", new.x,", absolute relative error:", ERR,".")
}
# updating the two values. CAUTION: order matters
x1 = x2
x2 = new.x
}
if(ctr == max.iter){
cat("\n\nThe maximum number of iterations attained!")
cat("\nThe algorithm did not converge!")
break
}
} # close the while-loop
} # close the function environment# define the function f(x) that satisfies f(x) = 0
test_func = function(x){3*x-exp(x)}
###
# call the function
FalseMethod(fn = test_func, # input function
TOL = 10^(-5), # error tolerance
max.iter = 100, # max allowed iterations
x1=1, # initial value #1
x2=2, # initial value #2
detail=TRUE, # output intermediate output
## adding controls for the graphic
graphic = TRUE, # default
xlimit=c(0,3), # x-limits: a vector of lower and upper limits
ylimit = c(-1, 35) # y-limits: a vector of lower and upper limits
)
##
## Iteration: 1 , approximated root: 1.168615 , absolute relative error: 0.8313847 .
## Iteration: 2 , approximated root: 1.311517 , absolute relative error: 0.1429012 .
## Iteration: 3 , approximated root: 1.797043 , absolute relative error: 0.4855265 .
## Iteration: 4 , approximated root: 1.436778 , absolute relative error: 0.3602651 .
## Iteration: 5 , approximated root: 1.486766 , absolute relative error: 0.04998839 .
## Iteration: 6 , approximated root: 1.515326 , absolute relative error: 0.02855947 .
## Iteration: 7 , approximated root: 1.512012 , absolute relative error: 0.003313826 .
## Iteration: 8 , approximated root: 1.512134 , absolute relative error: 0.0001220417 .
##
## The algorithm converges!
## The approximated root is 1.512135 .
## The absolute relative error ERR= 5.757598e-07 .
## The number of iterations: 9 .Secant Method
########################################
## Root Finding: Secant Method
#########################################
SecantMethod = function(fn, # input function
TOL, # error tolerance
max.iter = 100, # max allowed iterations
x1, # initial value #1
x2, # initial value #2
detail = TRUE, # output intermediate output
## adding controls for the graphic
graphic = TRUE, # default
xlimit, # x-limits: a vector of lower and upper limits
ylimit, # y-limits: a vector of lower and upper limits
... # other optional arguments if any
){
ctr = 0 # counter of iteration
ERR = abs(x2 - x1)
## base graph
if(graphic ==TRUE){
xx = seq(xlimit[1], xlimit[2], length = 500) # x-coordinates
yy = fn(xx) # y-coordinates
plot(xx, yy, type = "l",
xlab = "x",
ylab = "Y",
xlim = xlimit,
ylim = ylimit,
lwd = 2,
col = "blue",
lty = 1)
}
abline(h = 0, lty = 2, col = "navy")
##
while(ERR > TOL){
ctr = ctr + 1
new.x = x2 - fn(x2) * (x2 - x1) / (fn(x2) - fn(x1))
ERR = abs(new.x - x2)
if(ERR < TOL){
cat("\n\nThe algorithm converges!")
cat("\nThe approximated root is", new.x,".")
cat("\nThe absolute relative error ERR=",ERR,".")
cat("\nThe number of iterations:", ctr, ".")
break
} else{
if(graphic == TRUE){
segments(x2, fn(x2), x1, fn(x1), lty = 1, col = "purple")
segments(new.x, fn(new.x), new.x, 0, col = "red", lty = 2)
}
if(detail == TRUE){
cat("\nIteration:", ctr,", approximated root:", new.x,", absolute relative error:", ERR,".")
}
# updating the two values. CAUTION: order matters
x1 = x2
x2 = new.x
}
if(ctr == max.iter){
cat("\n\nThe maximum number of iterations attained!")
cat("\nThe algorithm did not converge!")
break
}
} # close the while-loop
} # close the function environment# define the function f(x) that satisfies f(x) = 0
test_func = function(x){3*x-exp(x)}
###
# call the function
SecantMethod(fn = test_func, # input function
TOL = 10^(-5), # error tolerance
max.iter = 100, # max allowed iterations
x1=1, # initial value #1
x2=2, # initial value #2
detail=TRUE, # output intermediate output
## adding controls for the graphic
graphic = TRUE, # default
xlimit=c(0,3), # x-limits: a vector of lower and upper limits
ylimit = c(-1, 35) # y-limits: a vector of lower and upper limits
)
##
## Iteration: 1 , approximated root: 1.168615 , absolute relative error: 0.8313847 .
## Iteration: 2 , approximated root: 1.311517 , absolute relative error: 0.1429012 .
## Iteration: 3 , approximated root: 1.797043 , absolute relative error: 0.4855265 .
## Iteration: 4 , approximated root: 1.436778 , absolute relative error: 0.3602651 .
## Iteration: 5 , approximated root: 1.486766 , absolute relative error: 0.04998839 .
## Iteration: 6 , approximated root: 1.515326 , absolute relative error: 0.02855947 .
## Iteration: 7 , approximated root: 1.512012 , absolute relative error: 0.003313826 .
## Iteration: 8 , approximated root: 1.512134 , absolute relative error: 0.0001220417 .
##
## The algorithm converges!
## The approximated root is 1.512135 .
## The absolute relative error ERR= 5.757598e-07 .
## The number of iterations: 9 .Newton Method
NewtonVersion01 = function(fn, # function used to define the equation
dfn, # derivative of f(x)
x, # initial value
M, # pre-set maximum iteration
TOL, # error tolerance
...
){
n = 1
ERR = abs(fn(x)/dfn(x))
# loop begins
while(ERR > TOL){
n = n + 1
x = x - fn(x)/dfn(x)
ERR = abs(fn(x)/dfn(x))
if(ERR < TOL){
cat("\n\nAlgorithm converges!")
cat("\nThe approximated root:", x, ".")
cat("\nThe absolute error:", ERR, ".")
cat("\nThe number of iterations n =",n,".")
break
} else{
cat("\nIteration n =",n, ", approximate root:",x,", absolute error:", ERR,".")
}
if (n ==M){
cat("\n\nThe maximum iterations attained!")
cat("\nThe algorithm did not converge!")
break
}
}
}##
fn = function(x) 3*x-exp(x)
dfn = function(x) 3-exp(x)
##
NewtonVersion01(fn = fn, # function used to define the equation
dfn = dfn, # derivative of f(x)
x = 1, # initial value
M = 200, # pre-set maximum iteration
TOL = 10**(-5) # error tolerance
)##
## Iteration n = 2 , approximate root: 0 , absolute error: 0.5 .
## Iteration n = 3 , approximate root: 0.5 , absolute error: 0.1100597 .
## Iteration n = 4 , approximate root: 0.6100597 , absolute error: 0.008937125 .
## Iteration n = 5 , approximate root: 0.6189968 , absolute error: 6.450361e-05 .
##
## Algorithm converges!
## The approximated root: 0.6190613 .
## The absolute error: 3.380632e-09 .
## The number of iterations n = 6 .17A. Newton
NewtonVersion01 = function(fn, # function used to define the equation
dfn, # derivative of f(x)
x, # initial value
M, # pre-set maximum iteration
TOL, # error tolerance
...
){
n = 1
ERR = abs(fn(x)/dfn(x))
# loop begins
while(ERR > TOL){
n = n + 1
x = x - fn(x)/dfn(x)
ERR = abs(fn(x)/dfn(x))
if(ERR < TOL){
cat("\n\nAlgorithm converges!")
cat("\nThe approximated root:", x, ".")
cat("\nThe absolute error:", ERR, ".")
cat("\nThe number of iterations n =",n,".")
break
} else{
cat("\nIteration n =",n, ", approximate root:",x,", absolute error:", ERR,".")
}
if (n ==M){
cat("\n\nThe maximum iterations attained!")
cat("\nThe algorithm did not converge!")
break
}
}
}##
fn = function(x) 230*x**4+18*x**3+9*x**2-221*x-9
dfn = function(x) 920*x**3+54*x**2+18*x-221
##
NewtonVersion01(fn = fn, # function used to define the equation
dfn = dfn, # derivative of f(x)
x = 1, # initial value
M = 200, # pre-set maximum iteration
TOL = 10**(-6) # error tolerance
)##
## Iteration n = 2 , approximate root: 0.9649805 , absolute error: 0.00256882 .
## Iteration n = 3 , approximate root: 0.9624117 , absolute error: 1.330587e-05 .
##
## Algorithm converges!
## The approximated root: 0.9623984 .
## The absolute error: 3.557772e-10 .
## The number of iterations n = 4 .17B. Secant
########################################
## Root Finding: Secant Method
#########################################
SecantMethod = function(fn, # input function
TOL, # error tolerance
max.iter = 100, # max allowed iterations
x1, # initial value #1
x2, # initial value #2
detail = TRUE, # output intermediate output
## adding controls for the graphic
graphic = TRUE, # default
xlimit, # x-limits: a vector of lower and upper limits
ylimit, # y-limits: a vector of lower and upper limits
... # other optional arguments if any
){
ctr = 0 # counter of iteration
ERR = abs(x2 - x1)
## base graph
if(graphic ==TRUE){
xx = seq(xlimit[1], xlimit[2], length = 500) # x-coordinates
yy = fn(xx) # y-coordinates
plot(xx, yy, type = "l",
xlab = "x",
ylab = "Y",
xlim = xlimit,
ylim = ylimit,
lwd = 2,
col = "blue",
lty = 1)
}
abline(h = 0, lty = 2, col = "navy")
##
while(ERR > TOL){
ctr = ctr + 1
new.x = x2 - fn(x2) * (x2 - x1) / (fn(x2) - fn(x1))
ERR = abs(new.x - x2)
if(ERR < TOL){
cat("\n\nThe algorithm converges!")
cat("\nThe approximated root is", new.x,".")
cat("\nThe absolute relative error ERR=",ERR,".")
cat("\nThe number of iterations:", ctr, ".")
break
} else{
if(graphic == TRUE){
segments(x2, fn(x2), x1, fn(x1), lty = 1, col = "purple")
segments(new.x, fn(new.x), new.x, 0, col = "red", lty = 2)
}
if(detail == TRUE){
cat("\nIteration:", ctr,", approximated root:", new.x,", absolute relative error:", ERR,".")
}
# updating the two values. CAUTION: order matters
x1 = x2
x2 = new.x
}
if(ctr == max.iter){
cat("\n\nThe maximum number of iterations attained!")
cat("\nThe algorithm did not converge!")
break
}
} # close the while-loop
} # close the function environment# define the function f(x) that satisfies f(x) = 0
test_func = function(x){230*x**4+18*x**3+9*x**2-221*x-9}
###
# call the function
SecantMethod(fn = test_func, # input function
TOL = 10^(-6), # error tolerance
max.iter = 100, # max allowed iterations
x1=1, # initial value #1
x2=2, # initial value #2
detail=TRUE, # output intermediate output
## adding controls for the graphic
graphic = TRUE, # default
xlimit=c(0,3), # x-limits: a vector of lower and upper limits
ylimit = c(-1, 35) # y-limits: a vector of lower and upper limits
)
##
## Iteration: 1 , approximated root: 0.9920166 , absolute relative error: 1.007983 .
## Iteration: 2 , approximated root: 0.9857878 , absolute relative error: 0.00622875 .
## Iteration: 3 , approximated root: 0.9636985 , absolute relative error: 0.02208928 .
## Iteration: 4 , approximated root: 0.9624576 , absolute relative error: 0.001240956 .
## Iteration: 5 , approximated root: 0.9623986 , absolute relative error: 5.899391e-05 .
##
## The algorithm converges!
## The approximated root is 0.9623984 .
## The absolute relative error ERR= 1.542282e-07 .
## The number of iterations: 6 .- Subtraction of those numbers are nearly equal. This makes the formula less accurate in the long run.