User:GoodCrossing/LOSalgorithm

A better algorithm

A careful floating-point computer implementation combines several strategies to produce a robust result. Assuming that the discriminant b2 − 4ac is positive, and b is nonzero, the computation would be as follows:[1]

Here sgn denotes the sign function, where is 1 if is positive, and −1 if is negative. This avoids cancellation problems between and the square root of the discriminant by ensuring that only numbers of the same sign are added.

To illustrate the instability of the standard quadratic formula compared to this formula, consider a quadratic equation with roots and . To 16 significant digits, roughly corresponding to double-precision accuracy on a computer, the monic quadratic equation with these roots may be written as

Using the standard quadratic formula and maintaining 16 significant digits at each step, the standard quadratic formula yields

Note how cancellation has resulted in being computed to only 8 significant digits of accuracy.

The variant formula presented here, however, yields the following:

Note the retention of all significant digits for .

Note that while the above formulation avoids catastrophic cancellation between and , there remains a form of cancellation between the terms and of the discriminant, which can still lead to loss of up to half of correct significant digits.[2][3] The discriminant needs to be computed in arithmetic of twice the precision of the result to avoid this (e.g. quad precision if the final result is to be accurate to full double precision).[4] This can be in the form of a fused multiply-add operation.[2]

To illustrate this, consider the following quadratic equation, adapted from Kahan (2004):[2]

This equation has and roots

However, when computed using IEEE 754 double-precision arithmetic corresponding to 15 to 17 significant digits of accuracy, is rounded to 0.0, and the computed roots are

which are both false after the 8th significant digit. This is despite the fact that superficially, the problem seems to require only 11 significant digits of accuracy for its solution.

Other examples

  1. ^ Cite error: The named reference Press_1992 was invoked but never defined (see the help page).
  2. ^ a b c Cite error: The named reference Kahan_2004 was invoked but never defined (see the help page).
  3. ^ Cite error: The named reference Higham_2002 was invoked but never defined (see the help page).
  4. ^ Cite error: The named reference Hough_1981 was invoked but never defined (see the help page).

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.