Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Finding Roots of FunctionsAndrew TomkoCOT 481026 February 2008Functions“relation between two sets in which one element of the second set is assigned to each element of the first set”Example: y = x^2Bad example: y^2 = x^2/rootThe value for 'x' for which 'y' will equal zeroIf there is no 'y', can rearrange function so that it equals zeroFunctions can have none, one, or many rootsWho cares?MathematiciansPhysiciansLots of peopleComputer ScientistsMethods for finding a rootBisectionNewton-RaphsonSecantFalse Position (regula falsi)MüllerInverse Quadratic InterpolationBrentIntermediate Value TheoremIf y=f(x) is continuous on [a,b], and N is a number between f(a) and f(b), then there is at least one c [a,b] ∈such that f(c) = N.Bisection MethodEasiestPositive/Negative values chosen, then bisectionRepeats until root is foundAbsolute error is halved each stepRuns in linear timeHas problems with multiple rootsBisection Method cont'dSecant MethodSimilar to bisectionTakes secant of two points on the function and then moves points closer until root is foundDoes not always converge, runs in superlinear time, faster than Newton's method in practiceBased on recurrence relation:Secant Method cont'dFalse Position (regula falsi) MethodCombination of bisection and secantTakes to points: one above/below rootRuns in superlinear timeFirst recorded use in 3rd century BCBased on:Müller's MethodBased on secant method, but takes 3 pointsFaster than the secant method, slower than Newton's methodQuadratic formula can yield complex valuesPolynomial InterpolationGiven a series of points, find a polynomial function that satisfies these points.Useful for transforming more difficult functions (logarithmic, trigonometric, etc)Inverse Quadratic InterpolationRarely used on its own, because it can fail easily if points not chosen close to root.Tries to create a quadratic interpolation for the function's inverse.Using linear interpolation: secant methodInterpolating f instead of the inverse: Müller's methodBrent's MethodCombination of bisection, secant, and inverse quadratic interpolationReliability of bisection, speed of secant/interpolationWill take at most N^2 iterations, where N is the number of iterations when using bisectionHouseholder's MethodsMethods for finding a root in a function with one real variable and has a continuous derivative.Derives from geometric series.The iterations will converge to a zero if the first “guess” is close enough.Newton-Raphson HistoryFirst described by Issac Newton in 1669First published in 1685 in A Treatise of Algebra both Historical and PracticalJoseph Raphson published a simplified version in 1690.Newton most likely got the formula from French mathematician François Viète seigneur de la Bigotière.Newton-Raphson MethodVery efficient method for real functionsQuadratic convergence: the number of correct digits doubles every iterationPossibility to not convergeRequires the calculation of the function's derivative:Newton-Raphson Method cont'dNewton-Raphson exampleNewton-Raphson fail to convergef(x) = x^3 – x – 3f'(x) = 3x^2 – 1Using x0 = 0, will start to cycle between xm=-3 and xn=0Newton-Raphson etc.Can be used to find multi-dimensional roots.Can be used to find roots in systems of non-linear, multivariable functions.Can be used to find the local minimums / maximums in a given function.Can be used to find complex roots, creates “Newton Fractals”x^8 + 15x^4 − 16p(z) = z^3 − 2z + 2x^5 − 1 = 0Roots of PolynomialsFor degrees less than five, the quadratic formula is generally the best. Can sometimes rewrite higher degree functions (x^6 – 4x^3 + 8 » u^2 – 4u + 8)Sturm's Theorem for finding number of real roots.Laguerre's method has cubic convergence.Problems with polynomials: WilkinsonSturm's TheoremUsed to determine the number of unique roots of a polynomial.Applies Euclid's algorithm to X and X'The final polynomial, Xr, is the GCD of X and X'Number of unique roots found by counting the number of sign changes.Fundamental Theorem of Algebra“Every non-constant single-variable polynomial with complex coefficients has at least one complex root”This can be reworked to show that every nth degree polynomial can be written in the form: f(x) = C(x-x1)(x-x2)...(x-xn)Laguerre's MethodPretty much guaranteed a convergence on root, regardless of initial value.Cubic convergence (!)Takes the natural log of both sides of formula on last slide, then takes two derivatives. (First derivative = G, Second derivative = H)Where a = the distance from your guess to the next root, and n = which root you're looking for:Wilkinson polynomialSourcesBurden, Richard L. & Faires, J. Douglas (2000), Numerical Analysis (7th ed.), Brooks/ColeDewdney, A. K. The New Turing Omnibus. New York: Henry Holt and Company, LLC, 1993.http://www.wikipedia.org/Questions1) Do the next iteration of the first Newton-Raphson example.2) What theorem do many of these methods depend
View Full Document
Unlocking...