Polynomials and Equations

CHAPTER TEN: APPROXIMATION TO REAL ROOTS

CHAPTER TEN APPROXIMATION TO REAL ROOTS We recall that given an equation of degree less than five, the exact values of its roots can be written as expressions that involve only rational operations and root extractions on the coefficients. It is also known that such expressions of roots are not generally available for an equation of higher degree. Therefore, for such equations, we shall have to use numerical methods that would only give approximate decimal values to the real roots. An approximate value is always inferior to the exact value, but for many practical purposes, we only need good approximations. In this chapter we shall learn two iterative processes that can furnish approximations to roots to any desired degree of accuracy. 10.1 Newton-Raphson method In 1669 Newton published a treatise entitled De Analysi per Aequationes Numero Terminorum Infinitas in which he explained a method of approximating roots of numerical equations by working out one example, namely the cubic equation x3 - 2x - 5 = O. 10.1.1 NEWTON'S EXAMPLE. The cubic equation x3 - 2x - 5 = 0 has a root between 2 and 3. Find approximate values to this root. SOLUTION: The discriminant of the equation x3 - 2x - 5 = 0 is negative; hence by 4.3.8 it has only one real root r. With /(2) = -1 and /(3) = 16, we locate r between 2 and 3. Newton's method consists of a series of successive approximations. To begin we take al = 2 as the first rough approximation 187 Polynomials and Equations to r, and proceed to find the next approximation a2 =al + hI with a small correcting term hI. Thus a decimal value of hI is to be found so that l(a2) = 1(2 + hI) = -5 - 2(2 + hI) + (2 + hl)S = (-1 + 10hl) + (6hl 2 + h1 3 ) would be close to o. Obviously it would simplify the matter if we take hI = -1/10 = 0.1. Then the value in the first bracket would be zero and the value in the second bracket which then equals l(a2) = 1(2.1) would be small because it only contains the quadratic and the cubic terms of the decimal 0.1. Indeed with 1(2.1) = 0.061 we could accept a2 = al +hI = 2.1 as a better approximation to r than al = 2 with 1(2) = -1. Should a closer approximation than 2.1 be needed, we proceed to find as = al + hI + h2 with a still smaller correcting term h2. To find h2, we try to make I(as) = 1(2 + (0.1 + h2 )) = -1 + 10(0.1 + h2) + 6(0.1 + h2)2 + (0.1 + h2 )S = (0.061 + 11.23h2) + (6.3h22 + h2s) still closer to 0 than 0.061. Similarly we choose h2 = -0.061/11.23 ~ -0.0054 to make the first bracket vanish and consequently diminish 1(2.1) to 1(2.0946) = 1(2.1 - 0.0054) ~ 0.0005415 . With this improvement, we could accept as = 2.0946 as the third approximation to r. Thus we have obtained three approximate values to the real root r of xS - 2x - 5 = 0 in al = 2, a2 = 2.10, as = 2.0946 with I(ad = -1, l(a2) = 0.061, I(as) ~ 0.0005415 . Further approximations a4, a&, ••• may be found similarly. 188 Approximation to Real Roots We may describe Newton's method in general terms as follows. Given is an equation f(x) = 0 (e.g., f(x) = x3 - 2x2 - 5 = 0) together with an approximation a (e.g., a = 2) to one of its root r. Then we consider a new equation go(h) = f(a + h) = 0 in the unknown h which has a root at r - a. Neglecting all terms in h2 , h3 , etc., we find an approximation hI (e.g., hI = 0.1) to the root r - a. Then a + hI (e.g., 2.1) will be a new approximation to the root r of f(x) = o. If a better one is desired, the next step takes us to yet another new equation gdh') = gO(hl + h') = 0 in the unknown h'. This equation has a root in r - a - hI. Again an approximation h2 (e.g., h2 = -0.0054) to this root is found after neglecting the higher terms. Thus an improved approximation a + hI + h2 (e.g., 2.0946) is obtained. To find the next approximation we consider the equation in...