def bisection(f, a, b, tol=1e-10, maxit=200): fa, fb = f(a), f(b) if fa == 0: # Why? endpoint is already an exact root return a if fb == 0: return b if fa * fb > 0: raise ValueError("f(a) and f(b) must have opposite signs") for _ in range(maxit): m = (a + b) / 2 # Why? midpoint splits the bracket evenly fm = f(m) if fm == 0 or (b - a) / 2 < tol: return m # Why? exact root, or width below tol -> good enough if fa * fm < 0: # Why? sign change is on the LEFT half b, fb = m, fm else: # Why? sign change is on the RIGHT half a, fa = m, fm return (a + b) / 2
def newton(f, df, x0, tol=1e-12, maxit=100): x = x0 for _ in range(maxit): fx = f(x) dfx = df(x) if dfx == 0: raise ZeroDivisionError("zero derivative — tangent is flat") step = fx / dfx # Why? -fx/dfx is the move to the tangent's root x = x - step if abs(step) < tol: # Why? step size measures how much we moved return x return x
What condition must a bracket [a,b] satisfy for bisection?
f(a)⋅f(b)<0 (a sign change), by the Intermediate Value Theorem.
Why should bisection check the endpoints before the loop?
If f(a)=0 or f(b)=0 exactly, the strict bracket test f(a)f(b)<0 fails and the loop would discard a real root; return the endpoint immediately.
What is the Newton-Raphson update formula?
xn+1=xn−f′(xn)f(xn).
Where does the Newton formula geometrically come from?
The x-intercept of the tangent line to f at xn.
Convergence order of bisection vs Newton?
Bisection is linear (error halves each step); Newton is quadratic (error ∝en2, digits double).
How many bisection steps to reach tolerance ε on [a,b]?
n≥log2εb−a−1.
Name two ways Newton can fail.
f′(x)≈0 (huge/undefined step) and a starting guess too far away (divergence or cycling).
Why is bisection "guaranteed" but Newton not?
Bisection always keeps a valid bracket so the root stays trapped; Newton blindly follows a tangent that may point away from the root.
What does Newton on x2−2 reduce to?
The Babylonian method xn+1=2xn+xn1 for 2.
What algorithm does scipy.optimize.brentq actually use?
Brent's method = bisection combined with the secant method and inverse-quadratic interpolation (NOT Newton's method — it needs no derivative).
What quantity is a good stopping test for Newton?
The step size ∣xn+1−xn∣ (or ∣f(x)∣) below a tolerance.
Recall Feynman: explain to a 12-year-old
Imagine you lost your toy somewhere on a long hallway and you know it's between rooms 1 and 100. Bisection = you walk to room 50 and ask "is the toy before or after here?" Then you only search that half. Each question cuts the hallway in half — super safe, you'll always find it, just takes a few steps. (And if the toy happens to be sitting exactly at room 1 or 100, just check those doors first!)
Newton = you have a magic arrow that points roughly toward the toy. You sprint where it points, look at the new arrow, sprint again. If the arrow is good you're there in 2 jumps — but if you start in a weird spot the arrow can fling you out the window! So: arrow when you can, halving when you must.
Dekho, root-finding ka matlab hai woh x dhoondhna jahan f(x)=0 ho jaye — jaise x2−2=0 ka root 2 hai. Haath se solve karna mushkil hota hai, isliye hum iterate karte hain: ek guess se start karo, usko behtar banao, repeat karo jab tak kaafi paas na pahunch jao.
Bisection simple aur 100% bharosemand hai. Agar f(a) negative aur f(b) positive hai (sign change), to beech mein root zaroor hoga (Intermediate Value Theorem). Midpoint m nikalo, dekho sign kahan change ho raha hai, aur aadha interval phenk do. Har step interval ko half kar deta hai — slow but guaranteed, bilkul binary search jaisa. Ek chhoti si baat: agar endpoint a ya b exactly root nikla to loop se pehle hi check karke return kar do, warna woh root chhoot jaayega.
Newton-Raphson fast hai. Idea: point xn pe curve ki tangent line kheencho, aur jahan woh line zero ko cut kare wahan jump kar jao. Formula nikalta hai xn+1=xn−f′(xn)f(xn). Iski khaas baat — har step mein sahi digits roughly double ho jaate hain (quadratic convergence). Lekin yeh risky hai: agar f′(x) zero ke paas ho ya guess bahut door ho, to yeh udd ke kahin door chala jaata hai.
Toh practical funda (80/20): jab tumhare paas derivative aur achha guess ho, Newton use karo speed ke liye. Jab function gandagi ho ya sirf bracket pata ho, bisection use karo safety ke liye. Real-world libraries jaise scipy ka brentq Brent's method use karti hai — yeh bisection ko secant aur inverse-quadratic interpolation ke saath milati hai (Newton nahi, isliye derivative ki zaroorat bhi nahi). Yahi engineering ka asli maza hai: robustness aur speed ka balance.
