Discuss the following basic idea of the chapter
- Write the algorithms of all methods
- List the similarity and difference between all methods
Chapter two Forum:-Ans.......
my name is Ahmedin Jemal ,
ID-099-10,
G2-civil-C,
Thank you!!
(a)algorithm of bisection method
Start
- Decide initial values for x1 and x2 and stopping criterion, E.
- Compute f1 = f(x1) and f2 = f(x2).
- If f1 * f2>0, x1 and x2 do not bracket any root and go to step 7;
Otherwise continue. - Compute x0 = (x1+x2)/2 and compute f0 = f(x0)
- If f1*f0 < 0 then
set x2 = x0
else
set x1 = x0
set f1 = f0 - If absolute value of (x2 – x1)/x2 is less than error E, then
root = (x1 + x2)/2
write the value of root
go to step 7
else
go to step 4 - Stop
- Start
- Read values of x0, x1 and e
*Here x0 and x1 are the two initial guesses
e is the degree of accuracy or the absolute error i.e. the stopping criteria* - Computer function values f(x0) and f(x1)
- Check whether the product of f(x0) and f(x1) is negative or not.
If it is positive take another initial guesses.
If it is negative then goto step 5. - Determine:
x = [x0*f(x1) – x1*f(x0)] / (f(x1) – f(x0)) - Check whether the product of f(x1) and f(x) is negative or not.
If it is negative, then assign x0 = x;
If it is positive, assign x1 = x; - Check whether the value of f(x) is greater than 0.00001 or not.
If yes, goto step 5.
If no, goto step 8.
*Here the value 0.00001 is the desired degree of accuracy, and hence the stopping criteria.* - Display the root as x.
- Stop
Obtain a function f in the appropriate form (f(x)=0⇔x=g(x)) and assume that a root α exists. Obtain an initial approximation x0, a maximum number of iterations, and an error tolerance ϵ.
For i=1,2,... up to the maximum number of iterations prescribed:
Step 1: Obtain the successive approximations by the fixed point method with the following formula:
(1)xn+1=g(xn)
Step 2: Check the error tolerance:
(2)∣xn−xn−1∣<ϵ
If the above inequality is true, then stop. xn is a good approximation of the root α. If the inequality above is false, then continue to compute successive approximations until the maximum number of iterations is reached. If the maximum number of iterations is reached and the error tolerance ϵ is not obtained, then print out a failure message.
Obtain a function f and assume that a root α exists. Obtain an initial approximation x0 to this root. Also obtain a maximum number of iterations allowed and an error tolerance ϵ.
For i=1,2,... up to the maximum number of iterations prescribed:
Step 1: Obtain the successive approximations of the root α with the following formula:
(1)xi=xi−1−f(xi−1)f′(xi−1)
Step 2: Check the error tolerance:
(2)∣xn−xn−1∣<ϵ
If the above inequality does not hold, then continue to obtain successive approximations for α. If the above inequality is true, then further verify the accuracy of xn. Check that to see whether or not:
(3)f(xn+ϵ)⋅f(xn−ϵ)<0
If the signs of f(xn+ϵ) and f(xn−ϵ) are opposites of each other, then the accuracy of xn is verified and stop the algorithm. xn is a good approximation to α. If the signs of f(xn+ϵ) and f(xn−ϵ) are the same, then α is not contained in the small interval [xn−ϵ,xn+ϵ]. Print out an error message.
If the maximum number of iterations is reached, then print our a failure message.
(e)secant method algorithm
- Start
- Get values of x0, x1 and e
*Here x0 and x1 are the two initial guesses
e is the stopping criteria, absolute error or the desired degree of accuracy* - Compute f(x0) and f(x1)
- Compute x2 = [x0*f(x1) – x1*f(x0)] / [f(x1) – f(x0)]
- Test for accuracy of x2
If [ (x2 – x1)/x2 ] > e, *Here [ ] is used as modulus sign*
then assign x0 = x1 and x1 = x2
goto step 4
Else,
goto step 6 - Display the required root as x2.
- Stop
How to compare between two different numerical methods which these methods have same Big O, i.e local truncation error to show that the one numerical method producing better results in comparison to another method by theories tools
(1),
(a)algorithm of bisection method
Start
- Decide initial values for x1 and x2 and stopping criterion, E.
- Compute f1 = f(x1) and f2 = f(x2).
- If f1 * f2>0, x1 and x2 do not bracket any root and go to step 7;
Otherwise continue. - Compute x0 = (x1+x2)/2 and compute f0 = f(x0)
- If f1*f0 < 0 then
set x2 = x0
else
set x1 = x0
set f1 = f0 - If absolute value of (x2 – x1)/x2 is less than error E, then
root = (x1 + x2)/2
write the value of root
go to step 7
else
go to step 4 - Stop
- Start
- Read values of x0, x1 and e
*Here x0 and x1 are the two initial guesses
e is the degree of accuracy or the absolute error i.e. the stopping criteria* - Computer function values f(x0) and f(x1)
- Check whether the product of f(x0) and f(x1) is negative or not.
If it is positive take another initial guesses.
If it is negative then goto step 5. - Determine:
x = [x0*f(x1) – x1*f(x0)] / (f(x1) – f(x0)) - Check whether the product of f(x1) and f(x) is negative or not.
If it is negative, then assign x0 = x;
If it is positive, assign x1 = x; - Check whether the value of f(x) is greater than 0.00001 or not.
If yes, goto step 5.
If no, goto step 8.
*Here the value 0.00001 is the desired degree of accuracy, and hence the stopping criteria.* - Display the root as x.
- Stop
Obtain a function f in the appropriate form (f(x)=0⇔x=g(x)) and assume that a root α exists. Obtain an initial approximation x0, a maximum number of iterations, and an error tolerance ϵ.
For i=1,2,... up to the maximum number of iterations prescribed:
Step 1: Obtain the successive approximations by the fixed point method with the following formula:
(1)xn+1=g(xn)
Step 2: Check the error tolerance:
(2)∣xn−xn−1∣<ϵ
If the above inequality is true, then stop. xn is a good approximation of the root α. If the inequality above is false, then continue to compute successive approximations until the maximum number of iterations is reached. If the maximum number of iterations is reached and the error tolerance ϵ is not obtained, then print out a failure message.
Obtain a function f and assume that a root α exists. Obtain an initial approximation x0 to this root. Also obtain a maximum number of iterations allowed and an error tolerance ϵ.
For i=1,2,... up to the maximum number of iterations prescribed:
Step 1: Obtain the successive approximations of the root α with the following formula:
(1)xi=xi−1−f(xi−1)f′(xi−1)
Step 2: Check the error tolerance:
(2)∣xn−xn−1∣<ϵ
If the above inequality does not hold, then continue to obtain successive approximations for α. If the above inequality is true, then further verify the accuracy of xn. Check that to see whether or not:
(3)f(xn+ϵ)⋅f(xn−ϵ)<0
If the signs of f(xn+ϵ) and f(xn−ϵ) are opposites of each other, then the accuracy of xn is verified and stop the algorithm. xn is a good approximation to α. If the signs of f(xn+ϵ) and f(xn−ϵ) are the same, then α is not contained in the small interval [xn−ϵ,xn+ϵ]. Print out an error message.
If the maximum number of iterations is reached, then print our a failure message.
(e)secant method algorithm
- Start
- Get values of x0, x1 and e
*Here x0 and x1 are the two initial guesses
e is the stopping criteria, absolute error or the desired degree of accuracy* - Compute f(x0) and f(x1)
- Compute x2 = [x0*f(x1) – x1*f(x0)] / [f(x1) – f(x0)]
- Test for accuracy of x2
If [ (x2 – x1)/x2 ] > e, *Here [ ] is used as modulus sign*
then assign x0 = x1 and x1 = x2
goto step 4
Else,
goto step 6 - Display the required root as x2.
- Stop
How to compare between two different numerical methods which these methods have same Big O, i.e local truncation error to show that the one numerical method producing better results in comparison to another method by theories tools
,#Bisection method
#False position(Regular false)method
#Fixed point iteration method
#Newton method
#Secant method
- 2 List the similarity and difference between all methods
~1.1. Bisection Method
It is one of the most basic problems of numerical approximation. It is also known as the root-finding problem or Binary-search method. It is a process of dividing a set continually in half to search for the solution to a certain problem [2]. It states that if f(x) is a continuous function defined on the interval a0, then there is a root between p1 and b1. And so on.
1.2. Newton Raphson Method
It is one of the well-known numerical approaches for solving a root-finding problem [2]. This technique supposes that po be an approximation to the root (i.e. iteration guess) and belongs to the interval [a,b] in such that f '(po)0 and |p-po| is so small and hence [7, 9] 40 Ali Jassim Mohamed Ali: The Application of Numerical Approximation Methods upon Digital Images 1 1 1 ( ) , 1 ( ) n n n n f p p p for n f p (2)
~ newton method is the shortest of all
1.3. Secant Method
This method uses a secant line joining two points that cut curve's function and can be presented in the following expression [2, 8]: 1 1 2 1 1 2 ( )( ) , 2 ( ) ( ) n n n n n n n f p p p p p for n f p f p (3)
1.4. False Position Method
In this technique, one uses results that are known to be false to converge to the true root. This method chooses an initial approximations po and p1 such that f(po).f(p1)<0. The new approximation value will be then obtained in the way as described in the secant method mentioned above. After that and in order to decide which secant line to be used, the product of f(p2) and f(p1) should be taken and one of the following considerations shall be verified [7]: Choose p3 as a line joining (p1,f(p1)) and (p2,f(p2)) if f(p1).f(p2)<0. Choose p3 as a line joining (po,f(po)) and (p2,f(p2)) if f(p1).f(p2)>0. In order to estimate the approximation errors, two methods had been used here; these are the absolute and relative errors as shown in the following expressions [2]:
Fixed point : A point, say, s is called a fixed point if it satisfies the equation x = g(x).
Fixed point Iteration : The transcendental equation f(x) = 0 can be converted algebraically into the form x = g(x) and then using the iterative scheme with the recursive relationxi+1= g(xi), i = 0, 1, 2, . . .,
with some initial guess x0 is called the fixed point iterative scheme.
Given an equation f(x) = 0
Convert f(x) = 0 into the form x = g(x)
Let the initial guess be x0
Do
xi+1= g(xi)
while (none of the convergence criterion C1 or C2 is met)
C1. Fixing apriori the total number of iterations N . C2. By testing the condition | xi+1 - g(xi) | (where i is the iteration number) less than some tolerance limit, say epsilon, fixed apriori.
Numerical Example :
Find a root of x4-x-10 = 0 [ Graph]
Consider g1(x) = 10 / (x3-1) and the fixed point iterative scheme xi+1=10 / (xi3 -1), i = 0, 1, 2, . . .let the initial guess x0 be 2.0
So the iterative process with g1 gone into an infinite loop without converging.Consider another function g2(x) = (x + 10)1/4 and the fixed point iterative scheme
xi+1= (xi + 10)1/4, i = 0, 1, 2, . . .let the initial guess x0 be 1.0, 2.0 and 4.0
That is for g2 the iterative process is converging to 1.85558 with any initial guess.Consider g3(x) =(x+10)1/2/x and the fixed point iterative scheme
xi+1=( xi+10)1/2 /xi, i = 0, 1, 2, . . .
let the initial guess x0 be 1.8,
That is for g3 with any initial guess the iterative process is converging but very slowly toGeometric interpretation of convergence with g1, g2 and g3
The graphs Figures Fig g1, Fig g2 and Fig g3 demonstrates the Fixed point Iterative Scheme with g1, g2 and g3 respectively for some initial approximations. It's clear from the
Fig g1, the iterative process does not converge for any initial approximation.Fig g2, the iterative process converges very quickly to the root which is the intersection point of y = x and y = g2(x) as shown in the figure.Fig g3, the iterative process converges but very slowly.
1#Bisection method
#False position(Regular false)method
#Fixed point iteration method
#Newton method
#Secant method
2,
v The Bisection method
v The bisection method does not (in general) produce an exact solution of an equation f (x) = 0. However, we can give an estimate of the absolute error in the approxiation.
v Very stable Algorithm - Good technique to find starting point for Newton’s method
v Costs only one function evaluation, so rapid iterations
v Linear convergences, so slow (3.3 iterations/digit)
v The Secant method
· The secant method is a variant of Newton’s method, where f0(xn) is replaced by its finite difference approximation based on the evaluated function values at xn and at the previous iterate xn−1.
· Assuming convergence, observe that near the root
f0 (xn) ≈ f (xn) −f (xn−1)/ xn −xn−1
· Substitution of this approximation into the formula for Newton’s method yields the Secant method,
Xn+1 =
F (xn)(xn −xn−1) f (xn)−f (xn−1)
, n = 0,1,2,3, ···
· Hard to find starting points (Unknown basin of attraction)
· Costs only two function evaluations, so rapid iterations
· Superlinear convergences, α ≈ 1.62, which is pretty fast
v The Newton’s method
ü Newton’s method is an extremely powerful technique, but it has a major weakness; the need to know the value of the derivative of f at each approximation.
ü Frequently, f0(x) is far more difficult and needs more arithmetic operations to calculate than f (x).
ü Hard to find starting points (Unknown basin of attraction)
ü Finding and evaluating derivative requires more machine work at each iteration
ü Quadratic convergences is very fast- doubling the digits at each iteration
Ans: - The basic similarity of all methods?
Ø All of the methods to determine of Root
Ø The error decreases slowly at first but then rapidly after a few iterations
Ø The method is guaranteed to converge
1.List all the Algorithm Method
a.Bisection method
b.False position(Regular false) method
c.Fixed point iteration method
d.Newton method
e.Secant method
2.Similariy and Difference between the all
Algorithm
1.Bisection method
.It is one of the most basic problem of numerical approximation
.It is aprocess of dividing aset continually in half to search for the solution to acertain problem
.It states if f(x) is acontious function defined on the interval (ao.bo) then there is aroot b/n p1 and p2
2.Newton Raphson method
.It is one of the well knowm numerical approches for solving aroot-finding problem
.It is the shortest of all methods
3.Secant method
.This method uses asecant line joining two points that cut curves function
.The secant method is avariant of Newton's method where f(xn) is replaced by its finite difference approximation based on the evaluated function value at xn and athe previous iteration xn-1
4.False poision method
.In this techinique one uses result that are known to be false to converge to the true root
.This method chooses an initial approximations p0 and p1 such that f(p0).f(p1)<0
5.Fixed point iteration method
.Fixed point: apoint say S is called afixed point if it sasifies the equation x=g(x)
.Fixed point iteration: the transcendental equation f(x)=0 can be converted algorically into the form x=g(x)
1.List all the Algorithm Method
a)bisection method
b)False position(Regular false) method
c)Fixed point iteration method
d)Newton method
e)scant method
2.similarity and Difference between the all Algorithm
1.Bisection method
@It is one of the most basic problem of numerical approximation
@its process of dividing aset continually in half to search for the solution to acertain problem
@It states if f(x) is acontious function defined on the interval (ao.bo) then there is aroot b/n p1 and p2
2.Newton Raphson method
@It is one of the well known numerical approaches for solving aroot-finding problem
@It is the shortest of all methods
3.Secant method
.This method uses asecant line joining two points that cut curves function
.The secant method is avariant of Newton's method where f(xn) is replaced by its finite difference approximation based on the evaluated function value at xn and athe previous iteration xn-1
4.False poison method
.In this technique one uses result that are known to be false to converge to the true root
.This method chooses an initial approximations p0 and p1 such that f(p0).f(p1)<0
5.Fixed point iteration method
.Fixed point: apoint say S is called affixed point if it sasifies the equation x=g(x)
.Fixed point iteration: the transcendental equation f(x)=0 can be converted algorically into the form x=g(x)
Answer for question 2
2.Similariy and Difference between the all
Algorithm
1.Bisection method
.It is one of the most basic problem of numerical approximation
.It is aprocess of dividing aset continually in half to search for the solution to acertain problem
.It states if f(x) is acontious function defined on the interval (ao.bo) then there is aroot b/n p1 and p2
2.Newton Raphson method
.It is one of the well knowm numerical approches for solving aroot-finding problem
.It is the shortest of all methods
3.Secant method
.This method uses asecant line joining two points that cut curves function
.The secant method is avariant of Newton's method where f(xn) is replaced by its finite difference approximation based on the evaluated function value at xn and athe previous iteration xn-1
4.False poision method
.In this techinique one uses result that are known to be false to converge to the true root
.This method chooses an initial approximations p0 and p1 such that f(p0).f(p1)<0
5.Fixed point iteration method
.Fixed point: apoint say S is called afixed point if it sasifies the equation x=g(x)
.Fixed point iteration: the transcendental equation f(x)=0 can be converted algorically into the form x=g(x)
answer for Q
2.Similariy and Difference between the all
Algorithm
1.Bisection method
.It is one of the most basic problem of numerical approximation
.It is aprocess of dividing aset continually in half to search for the solution to acertain problem
.It states if f(x) is acontious function defined on the interval (ao.bo) then there is aroot b/n p1 and p2
2.Newton Raphson method
.It is one of the well knowm numerical approches for solving aroot-finding problem
.It is the shortest of all methods
3.Secant method
.This method uses asecant line joining two points that cut curves function
.The secant method is avariant of Newton's method where f(xn) is replaced by its finite difference approximation based on the evaluated function value at xn and athe previous iteration xn-1
4.False poision method
.In this techinique one uses result that are known to be false to converge to the true root
.This method chooses an initial approximations p0 and p1 such that f(p0).f(p1)<0
5.Fixed point iteration method
.Fixed point: apoint say S is called afixed point if it sasifies the equation x=g(x)
.Fixed point iteration: the transcendental equation f(x)=0 can be converted algorically into the form x=g(x)
1.List all the Algorithm Method
a.Bisection method
b.False position(Regular false) method
c.Fixed point iteration method
d.Newton method
e.Secant method
2.Similariy and Difference between the all
Algorithm
1.Bisection method
.It is one of the most basic problem of numerical approximation
.It is aprocess of dividing aset continually in half to search for the solution to acertain problem
.It states if f(x) is acontious function defined on the interval (ao.bo) then there is aroot b/n p1 and p2
2.Newton Raphson method
.It is one of the well knowm numerical approches for solving aroot-finding problem
.It is the shortest of all methods
3.Secant method
.This method uses asecant line joining two points that cut curves function
.The secant method is avariant of Newton's method where f(xn) is replaced by its finite difference approximation based on the evaluated function value at xn and athe previous iteration xn-1
4.False poision method
.In this techinique one uses result that are known to be false to converge to the true root
.This method chooses an initial approximations p0 and p1 such that f(p0).f(p1)<0
5.Fixed point iteration method
.Fixed point: apoint say S is called afixed point if it sasifies the equation x=g(x)
.Fixed point iteration: the transcendental equation f(x)=0 can be converted algorically into the form x=g(x)
1.List all the Algorithm Method
a)bisection method
b)False position(Regular false) method
c)Fixed point iteration method
d)Newton method
e)scant method
2.similarity and Difference between the all Algorithm
1.Bisection method
@It is one of the most basic problem of numerical approximation
@its process of dividing aset continually in half to search for the solution to acertain problem
@It states if f(x) is acontious function defined on the interval (ao.bo) then there is aroot b/n p1 and p2
2.Newton Raphson method
@It is one of the well known numerical approaches for solving aroot-finding problem
@It is the shortest of all methods
3.Secant method
.This method uses asecant line joining two points that cut curves function
.The secant method is avariant of Newton's method where f(xn) is replaced by its finite difference approximation based on the evaluated function value at xn and athe previous iteration xn-1
4.False poison method
.In this technique one uses result that are known to be false to converge to the true root
.This method chooses an initial approximations p0 and p1 such that f(p0).f(p1)<0
5.Fixed point iteration method
.Fixed point: apoint say S is called affixed point if it sasifies the equation x=g(x)
.Fixed point iteration: the transcendental equation f(x)=0 can be converted algorically into the form x=g(x)
Algorithm Method
a)bisection method
b)False position(Regular false) method
c)Fixed point iteration method
d)Newton method
e)scant method
2.similarity and Difference between the all Algorithm
1.Bisection method
It is one of the most basic problem of numerical approximation
its process of dividing aset continually in half to search for the solution to acertain problem
It states if f(x) is acontious function defined on the interval (ao.bo) then there is aroot b/n p1 and p2
2.Newton Raphson method
It is one of the well known numerical approaches for solving aroot-finding problem
It is the shortest of all methods
3.Secant method
.This method uses asecant line joining two points that cut curves function
.The secant method is avariant of Newton's method where f(xn) is replaced by its finite difference approximation based on the evaluated function value at xn and athe previous iteration xn-1
4.False poison method
.In this technique one uses result that are known to be false to converge to the true root
.This method chooses an initial approximations p0 and p1 such that f(p0).f(p1)<0
5.Fixed point iteration method
.Fixed point: apoint say S is called affixed point if it sasifies the equation x=g(x)
.Fixed point iteration: the transcendental equation f(x)=0 can be converted algorically into the form x=g(x
1. a) Bisection method
b) False position method
c) Fixed iteration method
d) Secant method
e) Newton Raphon method
2. Secant method
* Hard to find starting point
* Costs only two function evaluation and rapit iteration
*Superlinear convergence which is pretty fast
Bisection method
* Very stable algorithm
* Costs only one function evaluation so it is rapid iteration
* Linear convergence
Newton Raphon method
* It's also hard to find the starting point
* Quadratic convergence , is very fast
* Finding & evaluating derivatives required more machine works at each iteration.