Why do you sometimes get more and more outrageous after repeatedly "improving your answers"?
Not all repeated calculations will come close to the answer; for the same question, the rewriting method and starting point will all affect the result.
General Algorithms and Numerical Computing
You revise a guess over and over again, hoping that the error will get smaller and smaller. But the same fifth-order equation in the book may change from stable convergence to constant beating just by changing the writing method. Put them in the same picture and see when the "iteration" requires changing tools.
Guess first
If the same equation is rewritten in an equivalent way, will iterations yield exactly the same convergence performance?
Show answer and explanation
uncertain — Equivalent equations have the same roots, but the stability of the update rules can be completely different.
Then connect experience and science
Let’s first look at “How to change each time”
The same equation can be rewritten into different update rules. Check each rule instead of trusting it to converge when you see it being repeated.
xnew = g(xold)
Look at the residuals, not just look at whether the numbers look like
The residual f(x) shows how far the candidate answer is. Convergence, running out of steps, and numerical runaway must be noted separately.
Residual |f(x)| and step tolerance
Newton uses tangents to predict the next step
The intersection of the tangent line and the horizontal axis gives a new guess. This prediction may also fail when the tangent line is too flat or the starting point is not good.
xnew = xold − f(xold)/f′(xold)
Two points guard an interval with roots
It is known that the two ends of the continuous function have different signs, and the interval is halved each time. It may be slower, but the error bound is clear at each step.
nth step interval width = original width / 2ⁿ
Expand the calculation
xₙ₊₁ = g(xₙ) xₙ₊₁ = xₙ − f(xₙ)/f′(xₙ) m = (a+b)/2 二分nwheel后的宽Spend = (b₀−a₀)/2ⁿ
Corresponding to fixed point, Newton and bisection respectively. Newton's method requires that the derivative is available and non-zero; bisection requires anisotropic brackets for continuous functions. If the step size is small, the residuals should also be checked.
give it a try
Let’s look at the convergence example first, and then choose the divergence and jump-back rewrites. Newton will also fail when encountering a bad starting point; bisection relies on continuous and different-signed bounding intervals.
No need to memorize symbols
- f(x)
- function that wants to become zero
- f′(x)
- Tangent slope, denominator of Newton's method
- [a,b]
- An interval surrounded by endpoints of a continuous function with different signs
- Tolerance
- Allowable residual or interval width, without exact floating-point equality as the only stopping condition
Algorithm, accuracy and scope of application
Supplement Chapter 5 Examples 5.b–5.d with Newton, bisection and floating point stopping conditions. Comparable to x⁵+17x−8, x⁵+3x−8, x⁵−3x−8, s³+3s−0.9. The fixed point forms are (b−xᵖ)/a, real odd roots (b−ax)^(1/p), b/(x^(p−1)+a), and different rewritings of the same equation may converge, diverge, or form two periods. Newton uses the derivative p x^(p−1)+a, and the derivative stops near zero; bisection works in the interval of continuous polynomials with proven different signs. The demonstration can take up to 40 steps. If the absolute candidate value exceeds 1e8, it will stop and prompt. No truncation is called convergence; the tolerance is 1e−10. The floating-point mantissa oscillation of old hardware only explains its reasons. The same sequence will inevitably occur in the current JavaScript engine without forging it. The curve window is fixed to x∈[−3,3], y∈[−40,40], and the values outside the window are indicated by numbers.
my understanding check
If the decimal displayed twice looks the same, should we stop?
Also check tolerances and residuals — Explicit rounding may mask changes; the algorithm must have clear stopping conditions and iteration bounds.
Can the dichotomy method ensure that there is a zero point in the middle as long as the two ends have different signs?
The function is also required to be continuous within the interval — The vertical asymptote across tan will also have a different sign, but there will be no zero point.
When Newton's derivative approaches zero, should it?
Stop or change starting point/method — A denominator that is too small can result in large, unreliable corrections.
Iteration is not "just count a few more times". Choose the right rules, check the residuals, and explicitly stop when it fails.
Jean Meeus · Astronomical Algorithms, 2nd ed. · No. 5 chapter
General Algorithms and Numerical Computing · All interactive courses