Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 7
Текст из файла (страница 7)
. , an. This polynomial has (exact) degreen in case its leading coefficient a, is nonzero.The power form (2.1) is the standard way to specify a polynomial inmathematical discussions. It is a very convenient form for differentiatingor integrating a polynomial. But, in various specific contexts, other formsare more convenient.Example 2.1: The power form may lead to loss of significance If we construct the powerform of the straight line p(x) which takes on the values p(6000) = 1/3, p(6001) =- 2/3, then, in five-decimal-digit floating-point arithmetic, we will obtain p(x) =600.3 - x. Evaluating this straight line, in the same arithmetic, we find p(6000) = 0.3and p(6001) = - 0.7, which recovers only the first digit of the given function values, aloss of four decimal digits.A remedy of sorts for such loss of significance is the use of the shiftedpower form(2.2)If we choose the center c to be 6000, then, in the example, we wouldget p(x) = 0.33333 - (x - 6000.0), and evaluation in five-decimal-digitfloating-point arithmetic now provides p(6000) = 0.33333, p(6001) =- 0.66667; i.e., the values are as correct as five digits can make them.It is good practice to employ the shifted power form with the center cchosen somewhere in the interval [a,b] when interested in a polynomial onthat interval.
A more sophisticated remedy against loss of significance (orillconditioning) is offered by an expansion in Chebyshev polynomials orother orthogonal polynomials; see Sec. 6.3.The coefficients in the shifted power form (2.2) provide derivativevalues, i.e.,.if p(x) is given by (2.2). In effect, the shifted power form provides theTaylor expansion for p(x) around the center c.A further generalization of the shifted power form is the Newton form(2.3)2.1POLYNOMIAL.
FORMS 33This form plays a major role in the construction of an interpolatingpolynomial. It reduces to the shifted power form if the centers c1, . . . , cn,all equal c, and to the power form if the centers c1, . . . , cn, all equal zero.The following discussion on the evaluation of the Newton form thereforeapplies directly to these simpler forms as well.It is inefficient to evaluate each of the n + 1 terms in (2.3) separatelyand then sum. This would take n + n(n + 1)/2 additions and n(n + 1)/2multiplications.
Instead, one notices that the factor (x - c1 ) occurs in allterms but the first; that is,Again, each term between the braces but the first contains the factor(x - c2); that is,Continuing in this manner, we obtain p(x) in nested form:whose evaluation for any particular value of x takes 2n additions and nmultiplications. If, for example, p(x) = 1 + 2(x - 1) + 3(x - 1)(x - 2)+ 4(x - 1)(x - 2)(x - 3), and we wish to compute p(4), then we calculateas follows:This procedure is formalized in the following algorithm.Algorithm 2.1: Nested multiplication for the Newton form Given then + 1 coefficients a0, .
. . , an, for the Newton form (2.3) of the polynomial p(x), together with the centers c1 , . . . , cn . Given also thenumber z.Then,Moreover, the auxilliary quantitiesare of34INTERPOLATION BY POLYNOMIALSindependent interest. For, we have(2.4)i.e.,are also coefficients in the Newton form for p(x), butwith centers z, c1, c2, . . . , cn-1.We prove the assertion (2.4). From the algorithm,Substituting these expressions into (2.3), we getwhich proves (2.4).Aside from producing the value of the polynomial (2.3) at any particular point z economically, the nested multiplication algorithm is useful inchanging from one Newton form to another.
Suppose, for example, that wewish to express the polynomialin terms of powers of x, that is, in the Newton form with all centers equalto zero. Then, applying Algorithm 2.1 with z = 0 (and n = 2), we getHence2.1POLYNOMIAL FORMS35Applying Algorithm 2.1 to this polynomial, again with z = 0, givesThereforeIn this simple example, we can verify this result quickly by multiplying outthe terms in the original expression.Repeated applications of the Nested Multiplication algorithm areuseful in the evaluation of derivatives of a polynomial given in Newtonform (see Exercises 2.1-2 through 2.1-5). The algorithm is also helpful inestablishing the following basic fact.Lemma 2.1 If z1, .
. . , zk are distinct zeros of the polynomial p(x),thenfor some polynomial r(x).To prove this lemma, we write p(x) in power form (2.1), i.e., in Newtonform with all centers equal to zero, and then apply Algorithm 2.1 once, togeta polynomial of[sincedegree < n.
In effect, we have divided p(x) by the linear polynomial(x - z); q(x) is the quotient polynomial and the number p(z) is theremainder. Now pick specifically z = z1. Then, by assumption, p(z1) = 0,i.e.,This finishes the proof in case k = 1. Further, for k > 1, it follows thatz2, . .
. , zk are necessarily zeros of q(x), since p(x) vanishes at these pointswhile the linear polynomial x - z 1 does not, by assumption. Hence,induction on the number k of zeros may now be used to complete theproof.36INTERPOLATION BY POLYNOMIALSCorollary If p(x) and q(x) are two polynomials of degree < k whichagree at the k + 1 distinct points z0, .
. . , zk, then p(x) = q(x) identically.Indeed, their difference d(x) = p(x) - q(x) is then a polynomial ofdegree < k, and can, by Lemma 2.1, be written in the formwith r(x) some polynomial. Suppose thatThensome coefficients c0, . . . , cm withforwhich is nonsense. Hence, r(x) = 0 identically, and so p(x) = q(x).This corollary gives the answer, “At most one,” to the question “Howmany polynomials of degree < k are there which take on specified valuesat k + 1 specified points?”These considerations concerning zeros of polynomials can be refinedthrough the notion of multiplicity of a zero.
This will be of importance tous later on, in the discussion of osculatory interpolation. We say that thepoint z is a zero of (exact) multiplicity j, or of order j, of the function f(x)providedExampleFor instance, the polynomialhas a zero of multiplicity j at z. It is reasonable to count such a zero j times since it canbe thought of as the limiting case of the polynomialwith j distinct, or simple, zeros as all these zeros come together, or coalesce, at z.As another example, forthe functionhas three (simple)zeros in the intervalwhich converge to the number 0 asCorrespondingly, the (limiting) function sin x - x has a triple zero at 0.With this notion of multiplicity of a zero, Lemma 2.1 can bestrengthened as follows.Lemma 2.2 If z1, .
. . zk is a sequence of zeros of the polynomial p(x)counting multiplicity, thenfor some polynomial r(x).See Exercise 2.1-6 for a proof of this lemma. Note that the number zcould occur in the sequence z1, . . . , zk as many as j times in case z is azero of p(x) of order j.2.1POLYNOMIAL FORMS37From the lemma 2.2, we get by the earlier argument theCorollary If p(x) and q(x) are two polynomials of degree < k whichagree at k + 1 points z0, . .
. , z k in the sense that their differencer(x) = p(x) - q(x) has the k + 1 zeros z0, . . . , zk (counting multiplicity), then p(x) = q(x) identically.EXERCISES2.1-1 Evaluate the cubic polynomialThen use nested multiplication to obtain p(x) in power form, and evaluate that power form atx - 314.15.
Compare!2.1-2 Letbe a polynomial in Newtonform. Prove: If c1 = c2 = · · · = cr+1, then p(j)(c1) = j!aj,j = 0, . . . ,r. [Hint: Under theseconditions, p(x) can be writtenwith q(x) some polynomial. Now differentiate.]2.1-3 Find the first derivative ofat x = 2. [Hint: Apply Algorithm 2.1 twice to obtain the Newton form for p(x) with centers 2,2, 1, - 1; then use Exercise 2.1-2.]2.1-4 Find also the second derivative of the polynomial p(x) of Exercise 2.1-3 at x = 2.2.1-5 Find the Taylor expansion around c = 3 for the polynomial of Exercise 2.1-3.
[Hint:The Taylor expansion for a polynomial around a point c is just the Newton form for thispolynomial with centers c, c, c, c, . . . .]2.1-6 Prove Lemma 2.2. [Hint: By Algorithm 2.1, p(x) = (x - z1)q(x), Now, to finish theproof by induction on the number k of zeros in the given sequence, prove that z2, . . . , zk isnecessarily a sequence of zeros (counting multiplicity) of q(x). For this, assume that thenumber z occurs exactly j times in the sequence z2, . .
. , zk and distinguish the cases z = z1andAlso, use the fact that p (j)(x) = (x - z 1 )q (j)(x) + jq(j-1)(x). ]2.1-7 Prove that, in the language of the corollary to Lemma 2.2, the Taylor polynomiali! agrees with the function f(x) j-fold at the point x = a (i.e., a is aj-fold zero of their difference).2.1-8 Suppose someone gives you a FUNCTION F(X) which supposedly returns the value atX of a specific polynomial of degree < r.
Suppose further that, on inspection, you find thatthe routine does indeed return the value of some polynomial of degree < r (e.g., you find onlyadditions/subtractions and multiplications involving X and numerical constants in thatsubprogram, with X appearing as a factor less than r times). How many function valueswould you have to check before you could be sure that the routine does indeed do what it issupposed to do (assuming no rounding errors in the calculation)?2.1-9 For each of the following power series, exploit the idea of nested multiplication to findan efficient way for their evaluation. (You will have to assume, of course, that they are to besummed only over n < N, for some a priori given N.).38INTERPOLATION BY POLYNOMIALS2.2 EXISTENCE AND UNIQUENESS OF THEINTERPOLATING POLYNOMIALLet x0, x1, . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
