Looks like no one added any tags here yet for you.
true
(T/F) open methods require only a single starting value or two starting values that do not necessarily bracket the root
true
(T/F) open methods sometimes diverge or move away from the true root
- fixed point iteration
- Newton- Raphson
- Secant
- Modified Secant
open methods include
utilizing fixed point iteration(one point / successive substitution) to get x on the left hand side.
for more on fixed point refer to lecture powerpoint
how do open methods predict a root?
bisection and secant method. It's good because it combines them
Fzero uses
- allows one to predict a new value of x as a function of an old value of x
Thus, given an initial guess at the root xi , Eq. (6.1) can be used to compute a new estimate xi+1 as expressed by the iterative formula
& so on
x(i+2) = g(x(i + 1))
what is the advantage of fixed point iteration?
approximate relative error is given by this formula
the approximate percent relative error is halved after each iteration
fixed point iteration has linear convergence and can be proved by
- separating the equation into two components and then graphing the components separately and seeing where they intersect.
- just graph the original function and see where it intersects the x axis
two alternative graphical methods for determining the root of an equation are
the intersection of the two components of the equation (it's the same thing as the root of the function) (denoted by red circle)
-- idk if abscissa will always be the root!
what is an abscissa
For the first case (Fig. 6.3a), the initial guess of x0 is used to determine the corresponding point on the y2 curve [x0, g(x0)]. The point [x1, x1] is located by moving left horizontally to the y1 curve. These movements are equivalent to the first iteration of the fixed-point method:
x1 = g(x0)
Thus, in both the equation and in the plot, a starting value of x0 is used to obtain an esti- mate of x1. The next iteration consists of moving to [x1, g(x1)] and then to [x2, x2].
fixed point iteration graphically
|g′(x)| < 1.
Convergence for fixed point iteration occurs when
fixed point iteration convergence
fixed point iteration divergence
decrease with each iteration
for fixed point iteration, if |g′| < 1 , the errors
grow
for fixed point iteration, if |g′| > 1, the error
positive, and hence the errors will have the same sign (a and c)
If for fixed point iteration, the derivative is positive, the errors will be
change sign on each iteration (b and d)
If for fixed point iteration, the derivative is negative, the errors will
if the initial guess of the root is xi , a tangent can be extended from the point [xi , f (xi )]. The point where this tangent crosses the x axis usually represents an improved estimate of the root.
Newton Raphson method
for the newton raphson method, The first derivative at x is equivalent to the slope ... which can be rearranged to ..
no. Well, the percent relative error at each iteration decreases much faster for newton than fixed
usually is the fixed point iterative method faster than the newton raphson method?
proportional to the square
for newton raphson method, the error should be roughly ..... of the previous error
NOTE: the number of significant figures of accuracy approximately doubles with each iteration
is exhibited by newton raphson method because the error is roughly proportional to the square of the previous error... this means the number of significant figures of accuracy approximately doubles with each iteration
quadratic convergence
example of slow convergence using newton raphson method
* multiple roots
when the first guess is in a region where the slope is near zero (so first iteration flings solution far away!! so it takes time to converge back in on it (nature of the function basically*) -- figure on left
* (figure a) inflection point (f'(x) = 0) occurs in the vicinity of a root, causing the iterations to diverge from the root. So slow when root is at an inflection point
* (figure b) illustrates the tendency of the Newton-Raphson technique to oscillate around a local maximum or minimum. Such oscillations may persist, or, as in Fig. 6.6b, a near-zero slope is reached whereupon the solution is sent far from the area of interest.
* (fig C) encountering near zero slopes (disaster cause a derivative of 0 causes division by 0)
* (fig d) tangent line shoots off horizontally. never hitting the x axis
when is there slow convergence for newton raphson method? (4)
true. its convergence depends on the nature of the function and on the accuracy of the initial guess.
(T/F) There is no general convergence criterion for Newton-Raphson
when derivatives are hard to evaluate, so use the backward finitde divided difference
when can the secant method be used?
uses the finite divided difference and two arbitrary initial guesses
used when derivatives are hard to evaluate
secant method
because f(x) is not required to change signs between the estimates
why is the secant method not considered a bracketing method?
a fractional perturbation of the independent variable to estimate f'(x)
where sigma is a small perturbation fraction.
instead of using arbitrary initial guesses for the secant method, what can you do
a small perturbation fraction is used instead of two arbitrary initial guesses
modified secant method
modified secant method example
the perturbation might not be a proper value. It sigma is too small, the method can be swamped by round-off error caused by subtractive cancellation in the denominator of Eq. (6.9). If it is too big, the technique can become inefficient and even divergent. How- ever, if chosen correctly, it provides a nice alternative for cases where evaluating the derivative is difficult and developing two initial guesses is inconvenient.
what are possible errors that come with the modified secant method
hybrid approach that combined the reliability of bracketing with the speed of the open methods
chooses when to use which
didn't read this section (6.4) page 163
brent's mehod
used to find the real root of a single equation.
takes in the function and an initial guess (open method)
or two guesses in a vector can also be passed.
(another card tells you more specifics)
fzero()
the guess that you need to pass needs to be a guess near the root. for example x^2 - 9 has two roots, so if you pass 0 it'll give you -3, if you pass 4, 3.
for fzero function, wat is a disadvantage,
it first performs a search to identify a sign change. This search differs from the incremental search described in Section 5.3.1, in that the search starts at the single initial guess and then takes increasingly bigger steps in both the positive and negative directions until a sign change is detected.
Then it does the fast methods (secant and inverse quadratic interpolation) unless an unacceptable result occurs (root estimate falls outside bracket), then bracketing method occurs.
once it finds an acceptable root (or gets closer to the root) it switches to the faster methods. Bisection typically dominates at first, but then switches to the other
how does the fzero function work if a single initial guess is passed,
secant and inverse quadratic interpolation
fast root finding methods
[x,fx] = a vector containing the root x and the function evaluated at the root fx, options is a data structure created by the optimset function, and p1, p2... are any parameters that the function requires. Note that if you desire to pass in parameters but not use the options, pass an empty vector [] in its place.
fzero syntax
optimest function spills out all the data that occurred during the fzero function
bisection method and newton raphson method
for polynomials, which root finding method is utile for finding a single root
roots function
if we want to find all the roots of a polynomial, what do we use
x is a column vector containing the roots and c is a row vector containing the polynomial coefficients
roots function syntax
treats it as an eigenvalue problem
creates a companion matrix by dividing the all the coefficients by the first coefficient then placing them in a matrix with 1s and 0s. The companion matrix has a useful property that its eigenvalues are the roots of the polynomial.
after it makes the matrix, it uses matlab's eigenvalue evaluation function to determine the roots of the polynomial.
how does the roots function work
poly() function
inverse function of roots function is
when passed the values of the roots, it returns the polynomial's coefficients.
where r is a column vector containing the roots and c is a row vector containing the polynomial's coefficients.
poly() function
example, finding roots of polynomial. using polyval(), poly(), roots(), and deconv()
(1/3)
(2/3)
(3/3)
- combines reliability of bracketing with speed of open methods.
- chooses when to do which.
for bracketing method uses bisection and for open methods uses secant method or inverse quadratic interpolation
Brent's method
secant method is sometimes referred to as such because the lines that connects the two guesses is used to estimate the new root estimate by observing where it crosses the x axis
linear interpolation method
determining a sideways quadratic function that goes through 3 points and observing where it intersects the x axis
the point where it intersects the x axis will be used as the new root estimate
y = 0 corresponds to the root x(i+1)
this equation finds the root
inverse quadratic interpolation
the parabola might not intersect the x axis (when the parabola has complex roots)
so inverse quadratic interpolation was created to switch the axis and make a sideways graph
what is the flaw with quadratic interpolation not inverse
inverse quadratic interpolation is better as seen in the picture
comparing inverse quadratic interpolation vs secant
inverse quadratic interpolation example
reversing x and y in this equation will yield a quadratic in x
quadratic in y is made using this equation
If the three y values are not distinct (i.e., yi-2 = yi-1 or yi-1 = yi), an inverse quadratic function does not exist.
If we arrive at a situation where the y values are not distinct, we can always revert to the less efficient secant method to generate a root using two of the points. If yi 2 yi 1, we use the secant method with xi-1 and xi. If yi-1 yi, we use xi-2 and xi-1.
when does inverse quadratic interpolation not work