Content deleted Content added
Clarify that the coefficients are known |
Add citation for intuition |
||
Line 39:
where <math>x^2 - \alpha</math> is the divisor. Picking a value for <math>\alpha</math> fixes both the quotient <math>q</math> and the coefficients in the remainder <math>\beta</math> and <math>\gamma</math>. The key idea is to cleverly choose <math>\alpha</math> such that <math>\beta = 0</math>, so that
<math display="block"> p(x) = q(x) \cdot (x^2 - \alpha) + \gamma. </math
<ref name="knuth1962"/><ref name="overill1997"/> This way, no operations are needed to compute the remainder polynomial, since it's just a constant. We apply this procedure [[Recursion (computer science)|recursively]] to <math>q</math>, expressing
<math display="block"> p(x) = \left( \left( q(x) \cdot (x^2 - \alpha_m) + \gamma_m \right) \cdots \right) \cdot (x^2 - \alpha_1) + \gamma_1. </math>
After <math>m</math> recursive calls, the quotient <math>q</math> is either a [[Linear function (calculus)|linear]] or a [[Quadratic function|quadratic]] polynomial. In this base case, the polynomial can be evaluated with (say) [[Horner's method]].<ref name="knuth1962"/><ref name="overill1997"/><ref name="muller2016"/>
==== "Preconditioning" ====
| |||