One equation, two numerical tasks
The familiar quadratic formula is exact algebra, but an implementation must evaluate it with finite precision. For , suppose throughout that the stored real coefficients are the exact data, , and the discriminant is positive. There are two distinct real roots. We first also assume ; the zero-constant case is handled separately below. Computing both roots accurately requires attention to two different issues: cancellation in a root formula, and sensitivity of the roots to perturbations in the coefficients. A change of formula can address the first but cannot remove the second.
Definition 8.2.1
(Cancellation-avoiding root formulas)
Set and define when and otherwise. Form
The subscript indicates a root of at least as large an absolute value as the other, not the numerically larger signed root. Since and , . The two terms inside the parentheses have the same sign or one is zero, so this addition does not subtract nearly equal positive magnitudes.
Theorem 8.2.2
(A cancellation-avoiding identity)
Under these assumptions, and are exactly the two roots, with .
Proof
(Use the product of the roots)
The first formula is one choice of the quadratic formula and therefore gives a root. The product of the two roots is , so the other root equals . This also proves the identity without evaluating the difference of nearly equal numbers. The magnitude of is ; the other root has magnitude . As , the stated ordering follows. When , the convention chooses one of two opposite roots of equal magnitude.
Worked example 8.2.3
(Cancellation in binary64 arithmetic)
Take , , in IEEE binary64 arithmetic with round to nearest. The exact roots are , so the small root is . The stored discriminant is exact, and its computed square root is . Near , consecutive binary64 numbers are apart, so the naive numerator can only be a small multiple of ; here it is . Dividing by gives , a relative error of about . The stable formula forms and returns , correct to about sixteen digits; the large root is correct to the same precision.
Worked example 8.2.4
(Equal-magnitude roots when )
For we have , and . The convention gives , so , and . Both roots are recovered, and : the label only promises an absolute value at least as large, so in this edge case it merely records which root the sign convention produced.
Common mistake
(Choosing the sign of the square root by habit)
Writing , or always taking , reintroduces exactly the subtraction the identity was designed to avoid whenever is close to , that is, whenever is small compared with . The sign of must match the sign of .
What a rounding bound actually assumes
Suppose a real floating-point calculation uses round-to-nearest with unit roundoff , each of the relevant operations satisfies with , and no overflow or problematic underflow occurs. Suppose the computed nonnegative square-root value also obeys the independently established relative bound
This last hypothesis includes error in forming the discriminant as well as in the square root. It is not guaranteed merely by using a correctly rounded square-root instruction. Compute by a rounded addition and a rounded multiplication by , then compute and . Define
Theorem 8.2.5
(Conditional relative root bounds)
If , both computed roots are nonzero and
Proof
(Track the noncancelling sum)
Because and have the same sign or , replacing by changes their sum by a relative amount at most : its absolute change is at most , while the original sum has magnitude . Thus the unrounded sum is the exact sum times with . The two subsequent rounding factors yield with . Indeed their product is bounded above by , and its distance below one is no greater than this upper excess. In particular .
For the first division, , giving the first bound by the same product estimate. For the second, , and hence
The argument treats division as a separately rounded operation. It does not apply unchanged if the prescribed operations overflow, underflow outside the model, or are reassociated by a compiler.
Proof X-ray
Where the sign convention pays off
The whole proof rests on one structural fact: the only addition, , combines two numbers of the same sign. That is what converts an absolute perturbation of the square root into a relative perturbation of at most of the sum, because the sum is at least in magnitude. With the opposite sign, the same absolute perturbation would be divided by , which can be arbitrarily small, and no relative bound would follow. After that step everything is multiplicative: three factors , , give , and one more factor gives each root. The small root is computed by dividing by , so its error factor appears inverted, which is why appears in the denominator and why is needed. The hypothesis on is used once and is not proved here; the theorem is only as good as that external bound.
A worked decimal experiment
Worked example 8.2.6
(Three significant decimal digits)
Use a hypothetical decimal machine with three significant digits, rounding each operation to nearest, and ample exponent range. For , , , the exact roots are . In this arithmetic, rounds to , and its square root rounds to . The naive small-root numerator is therefore zero. The alternative gives , and the computed small root is . The actual small root is approximately , so this retains three significant digits even though the naive calculation returns zero. The large root is approximately , which rounds to in the same format. This is a worked arithmetic example, not a universal exactness guarantee.
The stable formula repairs a loss of accuracy that the naive formula itself introduced. Sensitivity of the roots to the coefficients is a property of the problem, and no rearrangement of the arithmetic removes it.
Counterexample mode
A stable formula cannot create missing discriminant information
Let and ; this has a repeated root . Changing only to gives positive discriminant and roots . A coefficient change of order therefore separates the roots by order . Changing instead to , with , gives negative discriminant. Near a double root even the number of real roots is sensitive to the data. The preceding relative theorem expressly requires and a valid bound on ; it cannot be invoked when rounding changes the discriminant's sign or makes it zero.
The explorer below rounds every operation to significant digits and runs the textbook formula and the product-of-roots formula side by side, so that lowering shows the cancellation in and the lost sign of near a double root.
Computing naively can itself subtract close terms. Scaling the coefficients by a common nonzero factor leaves the roots unchanged and may reduce overflow or underflow, but scaling does not by itself certify the discriminant's sign or cure ill-conditioning. A validated sign or error bound needs appropriate exact, higher-precision, or interval arithmetic. If , return the roots and directly; if also , zero is a repeated root. When , is the repeated root, but establishing that is exactly zero requires evidence about the data. Negative requires a complex-arithmetic treatment outside this section.
Concept lensAnalytic
The discriminant controls the root condition number
For a simple root , perturbing the coefficients by moves it, to first order, by
If every relative coefficient change is at most , the relative root change is at most to first order. The factor belongs to the problem, not to any formula, and as the linear estimate fails altogether, giving the square-root behavior of the counterexample.
Common mistake
(Trusting the sign of a computed discriminant)
Near a repeated root, and are nearly equal, so the computed may be rounded to zero or acquire the wrong sign. Deciding between two real roots, a double root and complex roots from a floating-point alone is unreliable; the decision needs a bound on the error in .
Practice with solutions
Quick check
(For , which direct numerator is cancellation-prone? Give a cancellation-avoiding expression for the small root.)
Compare the signs of and of in each numerator.
Solution · Answer
The numerator subtracts nearly equal positive numbers. Here and the small root is .
Quick check
(Assume and . Bound above by and give a bound for the relative error of the small root.)
Expand and then use the second bound of the theorem.
Solution · Answer
Direct expansion gives . The theorem gives . This conclusion is conditional on the independent square-root input bound and the rounding model.
Quick check
(For , find both exact roots. Explain why a small relative error in the coefficients does not imply equally small relative error in each root.)
Compute the discriminant first.
Solution · Answer
The discriminant is and the roots are . Replacing the constant by changes it by about relative but merges the two roots at , moving either root by . This illustrates the sensitivity near a repeated root.
Quick check
(For , why should one not evaluate blindly in every implementation?)
Consider what happens to if were also zero.
Solution · Answer
The direct special case returns and . Although in this example, when it is zero, and is undefined. Handling explicitly covers both cases without an unnecessary exceptional division.