Class 8. Root Finding in 1-DNonlinear Equations• Often (most of the time??) the relevant system of equations is nonlinear in the un-knowns.• Then, cannot decompose as Ax = b. Oh well.• Instead write as:1. f(x) = 0 (for functions of one variable, i.e., 1-D);2. f(x) = 0 (for x = (x1, x2, ..., xn), f = (f1, f2, ..., fn), i.e., n-D).• Not guaranteed to have any real solutions, but generally do for astrophysical problems.Solutions in 1-D• Generally, solving multi-D equations is much harder, so we’ll start with the 1-D casefirst...• By writing f(x) = 0 we have reduced the problem to solving for the roots of f.• In 1 -D it is usually possible to tra p or bracket the desired roots and hunt them down.• Typically all root-finding methods proceed by iteration, improving a trial solution untilsome convergence criterion is satisfied.Function Pathologies• Before blindly applying a root-finding algorithm to a problem, it is essential that theform of the equation in question be understood: graph it!• For smooth functions, good algorithms will always converge, provided the initial guessis good enough.• Pathologies include discontinuities, singularities, multiple or very close roots, or noroots at all!Numerical Root Finding• Suppose f(a) and f(b) have opposite sign.• Then, if f is cont inuous on the interval (a, b), there must be at least one root betweena and b ( t his is the Intermediate Value Theorem).• Such roots ar e said to be bracketed.1Bracketed root Many roots No rootsExample Application• Use root finding to calculate the equilibrium temperature of the ISM.• The ISM is a very diffuse plasma.– Heated by nearby stars and cosmic rays.– Cooled by a variety of processes:∗ Bremsstrahlung: collisions between electrons and ions.∗ Atom-electron collisions followed by radiative decay.∗ Thermal radiation from dust grains.• Equilibrium temperature given when rate of heating H = rate of coo ling C.– Often H is not a function of temperature T.– Usually C is a complex, nonlinear f unction of T .TH or CCHSolution• To solve, find T such that H − C(T ) = 0 .Bracketing and Bisection• NRiC §9.1 lists some simple bracketing routines that search for sign changes of f:– zbrac(): expand search range geometrically;– zbrak(): look for roots in subintervals.• Once bracketed, root is easy t o find by bisection:2– Evaluate f at interval midpoint (a + b)/2.– Root must be bracketed by midpoint and whichever a or b gives f of oppositesign.– Bracketing interval decreases by 2 each iteration:εn+1= εn/2.– Hence to achieve error tolerance of ε starting from interval of size ε0(ε ≤ ε0)requires n = log2(ε0/ε) step(s).Convergence• Bisection converges linearly (first power of ε).• Methods for whichεn+1= constant × (εn)m, m > 1,are said to converge superlinearly.• Note error actually decreases exponentially for bisection. It converges “linearly” be-cause successive significant figures are won linearly with computational effort (i.e.,1 → 0.5 → 0.2 5 → 0.125 → · · ·).Tolerance• What is a practical tolerance ε for convergence?• Best you can do is machine precision (em, about 10−7in single precision); more prac-tically, absolute convergence within em(|a| + |b|)/2 is used.• Sometimes consider fractional accuracy,|xi+1− xi||xi|∼ em,but this can fail for xinear zero.Newton-Raphson Method• Can we do better than linear convergence? Duh!• Expand f(x) in a Taylor series:f(x + δ) = f(x) + f0(x)δ +f00(x)2δ2+ ...• For small |δ|, drop higher-order terms, so:f(x + δ) = 0 implies δ = −f(x)f0(x).3• δ is correction added to current guess of root, i.e.,xi+1= xi+ δ.• Graphically, Newton-Raphson (NR) uses tangent line at xito find zero crossing, thenuses x at zero crossing as next guess:xi+2xi+1xi• Note: only works near root...– When higher order terms important, NR fails spectacularly. Other pathologiesexist too:12321Shoots to infinity Never converges• Why use NR if it fails so badly?• Can show thatεi+1= −ε2if00(x)2f0(x),i.e., quadratic convergence!• Note both f(x) and f0(x) must be evaluated each iteration, plus both must be contin-uous near root.• Popular use of NR is t o “polish up” bisection