Please enable JavaScript.
Coggle requires JavaScript to display documents.
Fixed-point Method, Secant Method, Bisection Method, Newton's Method,…
Fixed-point Method
It is the number at which the
value of function does not change
any further when the function is applied.
p is the number g is the function p is fixed point if g(p)=p
Definition:
if gE[a,b] & g(x)E[a,b]:
a) for all xE[a,b] then g has
atleast one Fixed point in [a,b]
b) if in addition g'(x) exists on [a,b] & a is positive then constant k<1 exists with
|g'(x)| <= k for all xE[a,b]
then their is exactly one fixed-point in [a,b]
if the interval is not given
then put x=0,x=1,...x=n in the function f(x). when the two consective values of f(x) give opposite signs then the interval lies in that range
Example:
if in function f(0)=-1 & f(1)=1 then the interval lies in [0,1]
Choose fixed approximation Xo
which lies in the range [a,b]
it is mostly taken as the midpoint of the interval.
In interval [0,1] min point is 0.5 so Xo=0.5
Stopping Criteria:
If after the decimal the four digit are same in consecetive two numbers then we stop the iteration.
Advantages
numbers are represented exactly
high precision
A good example of a fixed-point use case is anything relating with currency: Essentially, you can fix your unit to be cents, or one hundredth of a cent, and make all your monetary values be integers in that unit
Disadvantages
provides a very limited range
expensive in terms of area and power
dynamic range and accuracy
Fixed-point iteration should never be used outside of a theoretical situation. There not many advantages here aside from being marginally simpler to use for really simple or specific situations.
Secant Method
Steps to Find Solution
To find a solution to f (x) = 0 given initial approximations p0 and p1:
INPUT initial approximations p0, p1; tolerance TOL; maximum number of iterations N0.
OUTPUT approximate solution p or message of failure.
Step 1
set i=0;
q0 = f ( p0);
q1 = f ( p1).
Step 2
While i ≤ N0 do Steps 3–6.
Step 3
Set p = p1 − q1( p1 − p0)/(q1 − q0). (Compute pi.)
Step 4
If | p − p1| < TOL then
OUTPUT (p); (The procedure was successful.)
STOP.
Step 5
Set i = i + 1.
Step 6
Set p0 = p1; (Update p0, q0, p1, q1.)
q0 = q1;
p1 = p;
q1 = f ( p).
Step 7
OUTPUT (‘The method failed after N0 iterations, N0 =’, N0);
(The procedure was unsuccessful.)
STOP.
DEFINATION
In numerical analysis, the secant method is a root-finding algorithm that uses a succession of roots of secant lines to better approximate a root of a function f. The secant method can be thought of as a finite-difference approximation of Newton's method. However, the secant method predates Newton's method by over 3000 years.
FORMULA
f(Pn)= Pn-1 -[ f(Pn-1)(Pn-2 - Pn-1)] / f(Pn-2)-f(Pn-1)
Advantages
It converges at a faster than a linear rate so that it is more rapid. Convergent than the bisection method.
It does not require the use of the derivative of the function, something that is not available in a number
of applications.
It requires only one function evaluation per iteration, as compared with Newton’s method which requires
two.
Disadvantages
It may not converge.
There is no guaranteed error bound for the computed
iterates.
It is likely to have difficulty if f 0(α) = 0. This means the x-axis is tangent to the graph of y = f (x)
at x = α.
Newton’s method generalizes more easily to new methods for solving simultaneous systems of nonlinear
equations.
Bisection Method
Introduction:
Based on Intermediate Value Theorem.
Intermediate Value Theorem:
Let f be an continuous function on an interval of 'a' and 'b'. and let x be any number such that f(a) < s < f(b) then there exist a point x such that f(s)=x.
Defination:
For example, we are given with a function that is continuous on any given interval i.e. f(x). this method helps us solve the roots of that function f(x)=0. Root by this method is also called
Zero Root
.
There is possibility of more than one root in the given interval. (Interval Must be Continuous). This method will still be valid
Bisection method is used to solve algebraic and transcendental equation.
Overview:
Steps To Find Roots
.
Step 3
•
We find midpoint, let p=a1+b1/2.
Solution
If f(p1)=0 then it is the root of the equation.
If f(p1) != 0 then f(p1) has same sign as f(a1).
Bracket the interval at
[p1 , b]
Repeat From Step 1 until Tolerance
if f(p1) !=0 and f(p1) has same sign as f(b1).
Bracket the interval at [a1,p1]
Repeat From Step 1 until Tolerance
Step 1
Suppose we are given with a function f(x) on interval [a,b], such that f(a) and f(b) have opposite signs
Step 2
• Let a=a1 and b=b1.
Bracketing and overview
• If it
doesn’t yield zero
then we
bracket out
interval and iterate it until it give 0.
• That
midpoint
is then put in function and iff function yields 0. It is root.
•
Bracketing,
is a technique that we use here. We find the midpoint by putting two extremes of interval.
• We are given with a
continuous function
on given interval.
Applications In Real Life
1
short detection in video content for digital video library.
2
bisection method for determining the adequate population size.
3
locating and computing periodic orbits in molecular system.
Draw Backs
It takes more than normal number of iterations so it is time consuming.
Due to More iterations, Error in the solution increases
Newton's Method
Features:
It is non-bracketing method. Also known as open bracket method
Convergence is Not Guaranteed
Quadratic rate of convergence so faster
Approach: Taylor's series. Concept of tangent line
Observations:
Demerits
whenever when f′(xn)=0. If xn is a stationary point of f, then Newton's method attempts to divide by zero — and fails.
Inflection point issue might occur
In case of multiple roots, this method converges slowly
Near local maxima and local minima, due to oscillation, its convergence is slow
Merits
While the bisection method only requires f to be continuous, Newton's method requires the function f to be differentiable. This is necessary for f to have a tangent line
f(Xn)=0, so that Xn is an exact solution of f(x)=0, then the algorithm gives Xn+1=Xn, and in fact all of Xn, Xn+1, Xn+2, Xn+3,… will be equal. If you have an exact solution, Newton's method will stay on that solution
It requires only one guess
Derivation is more intuitive, which means it is easier to understand its behaviour, when it is likely to converge and when it is likely to diverge
Definition:
The Newton-Raphson method (also known as Newton's method) is a way to quickly find a good approximation for the root of a real-valued function f(x)=0f(x) = 0f(x)=0. It uses the idea that a continuous and differentiable function can be approximated by a straight line tangent to it
Formula:
Let f:R→R be a differentiable function. We seek a solution of f(x)=0, starting from an initial estimate x=x1
At the n'th step, given Xn, compute the next approximation Xn+1 by:
Xn+1=Xn − [ f(Xn) / f ′(Xn) ]
and repeat.
Steps to find solution
:
Find interval [a,b] such that a<b and f(a)⋅f(b)<0
find X0 = (a+b)\2
Find f(x0) and f
'
(x0)
x1=x0 - [ f(x0) / f
′
(x0) ]
If f(x1)=0 then x1 is an exact root,
else put x0=x1 and repeat step 2 and 4 until f(Xn)=0
Iterate this process until it matches stopping criteria
Tolerance:
(
T)
Maximum Number of iteration required to reach root of function
T=( Pn - Pn-1 ) / (Pn) < ε
