Loss of Significance - A Better Algorithm

A Better Algorithm

A better algorithm for solving quadratic equations is based on two observations: that one solution is always accurate when the other is not, and that given one solution of the quadratic, the other is easy to find.

If

and

then we have the identity (one of Viète's formulas for a second degree polynomial)

.

The above formulas (1) and (2) work perfectly for a quadratic equation whose coefficient 'b' is negative (b < 0). If 'b' is negative then '-b' in the formulas get converted to a positive value as -(-b) is equal to 'b'. Hence, we can avoid subtraction and loss of significant digits caused by it. But if the coefficient 'b' is positive then we need to use a different set of formulas. The second set of formulas that are valid for finding roots when coefficient 'b' is positive are mentioned below.

and

In the above formulas (3) and (4) when 'b' is positive the formula converts it to negative value as -(+b) is equal to -b. Now, as per the formulas '-b' is subtracted by square root of (b*b - 4ac) so basically it's an addition operation. In our example, coefficient 'b' of quadratic equation is positive . Hence, we need to use the second set of formulas i.e. formula (3) and (4).

The algorithm is as follows. Use the quadratic formula to find the solution of greater magnitude, which does not suffer from loss of precision. Then use this identity to calculate the other root. Since no subtraction is involved, no loss of precision occurs.

Applying this algorithm to our problem, and using 10-digit floating-point arithmetic, the solution of greater magnitude, as before, is The other solution is then

which is accurate. However, there remains a further possible source of cancellation when computing and indeed this can lead to up to half of significant figures being lost: to correct for this requires to be computed in extended precision, of twice the precision of the final result (see quadratic equation for details).