Worksheet15: Dickson 076
Current Work (editable)
Example. f(x) = x^{3} + 4x^{2} - 7. Then f' = 3x^{2} + 8x, f = (1/3 x + 4/9)f' - f_{2}, f_{2} $$ 32/9 x + 7, f' = (27/32 x + 603/1024) f_{2} - f_{3}, f_{3} = 4221/1024. For[1] x = 1, the signs of f, f', f_{2}, f_{3}, are - + + +, showing a single variation of consecutive signs. For x = 2, the signs are + + + +, showing no variation of sign. Sturm's theorem states that there is a single real root between 1 and 2. For x = -$$, the signs are - + - +, showing 3 variations of sign. The theorem states that there are 3 - 1 = 2 real roots between -$$ and 1. Similarly, x Signs Variations -1 - - + + 1 -2 + - - + 2 -3 + + - + 2 -4 - + - + 3 Hence there is a single real root between -2 and -1, and a single one between -4 and -3. Each real root has now been isolated since we have found two numbers such that a single real root lies between these two numbers or is equal to one of them. Some of the preceding computation was unnecessary. After isolating a root between -2 and -1, we know that the remaining root is isolated between -$$ and -2. But before we can compute it by Horner's method, we need closer limits for it. For that purpose it is unnecessary to find the signs of all four functions, but merely the sign of f (§63). 69. Sturm's Theorem. Let f(x) = 0 be an equation with real coefficients and without multiple roots. Modify the usual process of seeking the greatest common divisor of f(x) and its first derivative[2] f_{1}(x) by exhibiting each remainder as the negative of a polynomial f_{i}: (1) f = q_{1} f_{1} - f_{2}, f_{1} = q_{2} f_{2} - f_{3}, f_{2} = q_{3} f_{3} - f_{4}, ..., f_{n-2} = q_{n-1} f_{n-1} - f_{n}, where[3] f_{n} is a constant $$ 0. If a and b are real numbers, a < b, neither 1 Before going further, check that the preceding relations hold when x = 1 by inserting the computed values of f, f', f_{2} for x = 1. Experience shows that most students make some error in finding f_{2}, f_{3}, ..., so that checking is essential. 2 The notation f_{1} instead of the usual f', and similarly f_{0} instead of f, is used to regularize the notation of all the f's, and enables us to write any one of the equations (1) in the single notation (3). 3 If the division process did not yield ultimately a constant remainder $$ 0, f and f_{1} would have a common factor involving x, and hence f(x) = 0 a multiple root.
Answer Key (non-editable)
%[** Attn spacing of signs] \begin{Example} $f(x) = x^{3} + 4x^{2} - 7$. Then $f' = 3x^{2} +8x$, \begin{align*} f &= (\tfrac{1}{3}x + \tfrac{4}{9})f'- f_{2}, & f_{2} &\equiv \tfrac{32}{9} x + 7, \\ f' &= (\tfrac{27}{32} x + \tfrac{603}{1024}) f_{2} - f_{3}, & f_{3} & = \tfrac{4221}{1024}. \end{align*} For\footnote {Before going further, check that the preceding relations hold when $x = 1$ by inserting the computed values of $f$, $f'$, $f_{2}$ for $x = 1$. Experience shows that most students make some error in finding $f_{2}$, $f_{3}$, \dots, so that checking is essential.} $x = 1$, the signs of $f$, $f'$, $f_{2}$, $f_{3}$, are $- + + +$, showing a single variation of consecutive signs. For $x = 2$, the signs are $+ + + +$, showing no variation of sign. Sturm's theorem states that there is a \emph{single} real root between $1$ and $2$. For $x = -\infty$, the signs are $- + - +$, showing 3 variations of sign. The theorem states that there are $3 - 1 = 2$ real roots between $-\infty$ and $1$. Similarly, \[ \begin{array}{c|c|c} x & \text{Signs} & \text{Variations} \\ \hline -1 & - - + + & 1 \\ -2 & + - - + & 2 \\ -3 & + + - + & 2 \\ -4 & - + - + & 3 \end{array} \] Hence there is a single real root between $-2$ and $-1$, and a single one between $-4$ and $-3$. Each real root has now been \emph{isolated} since we have found two numbers such that a single real root lies between these two numbers or is equal to one of them. Some of the preceding computation was unnecessary. After isolating a root between $-2$ and $-1$, we know that the remaining root is isolated between $-\infty$ and $-2$. But before we can compute it by Horner's method, we need closer limits for it. For that purpose it is unnecessary to find the signs of all four functions, but merely the sign of $f$ (§63). \end{Example} \Par{69. Sturm's Theorem.} \begin{Thm} Let $f(x) = 0$ be an equation with real coefficients and without multiple roots. Modify the usual process of seeking the greatest common divisor of $f(x)$ and its first derivative\footnote {The notation $f_{1}$ instead of the usual $f'$, and similarly $f_{0}$ instead of $f$, is used to regularize the notation of all the $f$'s, and enables us to write any one of the equations \Eq{(1)} in the single notation \Eq{(3)}.} $f_{1}(x)$ by exhibiting each remainder as the negative of a polynomial $f_{i}$: \[ \Tag{(1)} f = q_{1} f_{1} - f_{2},\quad f_{1} = q_{2} f_{2} - f_{3},\quad f_{2} = q_{3} f_{3} - f_{4},\ \dots,\quad f_{n-2} = q_{n-1} f_{n-1} - f_{n}, \] where\footnote {If the division process did not yield ultimately a constant remainder $\neq 0$, $f$ and $f_{1}$ would have a common factor involving $x$, and hence $f(x) = 0$ a multiple root.} $f_{n}$ is a constant $\neq 0$. If $a$ and $b$ are real numbers, $a < b$, neither \end{Thm}%[** Continues]
Comparison of Current Work and Answer Key
Text to be deleted.
Text to be inserted.
¶
symbols signify newlines.