File: Divided-Difference-Representation-of-Polynomials.html

package info (click to toggle)
gsl-ref-html 2.3-1
  • links: PTS
  • area: non-free
  • in suites: bullseye, buster, sid
  • size: 6,876 kB
  • ctags: 4,574
  • sloc: makefile: 35
file content (157 lines) | stat: -rw-r--r-- 9,119 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 The GSL Team.

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "GNU General Public License" and "Free Software
Needs Free Documentation", the Front-Cover text being "A GNU Manual",
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled "GNU Free Documentation
License".

(a) The Back-Cover Text is: "You have the freedom to copy and modify this
GNU Manual." -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library &ndash; Reference Manual: Divided Difference Representation of Polynomials</title>

<meta name="description" content="GNU Scientific Library &ndash; Reference Manual: Divided Difference Representation of Polynomials">
<meta name="keywords" content="GNU Scientific Library &ndash; Reference Manual: Divided Difference Representation of Polynomials">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Function-Index.html#Function-Index" rel="index" title="Function Index">
<link href="Polynomials.html#Polynomials" rel="up" title="Polynomials">
<link href="Quadratic-Equations.html#Quadratic-Equations" rel="next" title="Quadratic Equations">
<link href="Polynomial-Evaluation.html#Polynomial-Evaluation" rel="previous" title="Polynomial Evaluation">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>


</head>

<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Divided-Difference-Representation-of-Polynomials"></a>
<div class="header">
<p>
Next: <a href="Quadratic-Equations.html#Quadratic-Equations" accesskey="n" rel="next">Quadratic Equations</a>, Previous: <a href="Polynomial-Evaluation.html#Polynomial-Evaluation" accesskey="p" rel="previous">Polynomial Evaluation</a>, Up: <a href="Polynomials.html#Polynomials" accesskey="u" rel="up">Polynomials</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Divided-Difference-Representation-of-Polynomials-1"></a>
<h3 class="section">6.2 Divided Difference Representation of Polynomials</h3>
<a name="index-divided-differences_002c-polynomials"></a>
<a name="index-evaluation-of-polynomials_002c-in-divided-difference-form"></a>

<p>The functions described here manipulate polynomials stored in Newton&rsquo;s
divided-difference representation.  The use of divided-differences is
described in Abramowitz &amp; Stegun sections 25.1.4 and 25.2.26, and
Burden and Faires, chapter 3, and discussed briefly below.
</p>
<p>Given a function <em>f(x)</em>, an <em>n</em>th degree interpolating polynomial <em>P_{n}(x)</em>
can be constructed which agrees with <em>f</em> at <em>n+1</em> distinct points
<em>x_0,x_1,...,x_{n}</em>. This polynomial can be written in a
form known as Newton&rsquo;s divided-difference representation:
</p>
<div class="example">
<pre class="example">P_n(x) = f(x_0) + \sum_(k=1)^n [x_0,x_1,...,x_k] (x-x_0)(x-x_1)...(x-x_(k-1))
</pre></div>

<p>where the divided differences <em>[x_0,x_1,...,x_k]</em> are defined in section 25.1.4 of
Abramowitz and Stegun. Additionally, it is possible to construct an interpolating
polynomial of degree <em>2n+1</em> which also matches the first derivatives of <em>f</em>
at the points <em>x_0,x_1,...,x_n</em>. This is called the Hermite interpolating
polynomial and is defined as
</p>
<div class="example">
<pre class="example">H_(2n+1)(x) = f(z_0) + \sum_(k=1)^(2n+1) [z_0,z_1,...,z_k] (x-z_0)(x-z_1)...(x-z_(k-1))
</pre></div>

<p>where the elements of <em>z = \{x_0,x_0,x_1,x_1,...,x_n,x_n\}</em> are defined by
<em>z_{2k} = z_{2k+1} = x_k</em>. The divided-differences <em>[z_0,z_1,...,z_k]</em>
are discussed in Burden and Faires, section 3.4.
</p>
<dl>
<dt><a name="index-gsl_005fpoly_005fdd_005finit"></a>Function: <em>int</em> <strong>gsl_poly_dd_init</strong> <em>(double <var>dd</var>[], const double <var>xa</var>[], const double <var>ya</var>[], size_t <var>size</var>)</em></dt>
<dd><p>This function computes a divided-difference representation of the
interpolating polynomial for the points (<var>x</var>, <var>y</var>) stored in
the arrays <var>xa</var> and <var>ya</var> of length <var>size</var>.  On output the
divided-differences of (<var>xa</var>,<var>ya</var>) are stored in the array
<var>dd</var>, also of length <var>size</var>. Using the notation above,
<em>dd[k] = [x_0,x_1,...,x_k]</em>.
</p></dd></dl>

<dl>
<dt><a name="index-gsl_005fpoly_005fdd_005feval"></a>Function: <em>double</em> <strong>gsl_poly_dd_eval</strong> <em>(const double <var>dd</var>[], const double <var>xa</var>[], const size_t <var>size</var>, const double <var>x</var>)</em></dt>
<dd><p>This function evaluates the polynomial stored in divided-difference form
in the arrays <var>dd</var> and <var>xa</var> of length <var>size</var> at the point
<var>x</var>.  An inline version of this function is used when <code>HAVE_INLINE</code> is defined.
</p></dd></dl>

<dl>
<dt><a name="index-gsl_005fpoly_005fdd_005ftaylor"></a>Function: <em>int</em> <strong>gsl_poly_dd_taylor</strong> <em>(double <var>c</var>[], double <var>xp</var>, const double <var>dd</var>[], const double <var>xa</var>[], size_t <var>size</var>, double <var>w</var>[])</em></dt>
<dd><p>This function converts the divided-difference representation of a
polynomial to a Taylor expansion.  The divided-difference representation
is supplied in the arrays <var>dd</var> and <var>xa</var> of length <var>size</var>.
On output the Taylor coefficients of the polynomial expanded about the
point <var>xp</var> are stored in the array <var>c</var> also of length
<var>size</var>.  A workspace of length <var>size</var> must be provided in the
array <var>w</var>.
</p></dd></dl>

<dl>
<dt><a name="index-gsl_005fpoly_005fdd_005fhermite_005finit"></a>Function: <em>int</em> <strong>gsl_poly_dd_hermite_init</strong> <em>(double <var>dd</var>[], double <var>za</var>[], const double <var>xa</var>[], const double <var>ya</var>[], const double <var>dya</var>[], const size_t <var>size</var>)</em></dt>
<dd><p>This function computes a divided-difference representation of the
interpolating Hermite polynomial for the points (<var>x</var>, <var>y</var>) stored in
the arrays <var>xa</var> and <var>ya</var> of length <var>size</var>. Hermite interpolation
constructs polynomials which also match first derivatives <em>dy/dx</em> which are
provided in the array <var>dya</var> also of length <var>size</var>. The first derivatives can be
incorported into the usual divided-difference algorithm by forming a new
dataset <em>z = \{x_0,x_0,x_1,x_1,...\}</em>, which is stored in the array
<var>za</var> of length 2*<var>size</var> on output. On output the
divided-differences of the Hermite representation are stored in the array
<var>dd</var>, also of length 2*<var>size</var>. Using the notation above,
<em>dd[k] = [z_0,z_1,...,z_k]</em>. The resulting Hermite polynomial
can be evaluated by calling <code>gsl_poly_dd_eval</code> and using
<var>za</var> for the input argument <var>xa</var>.
</p></dd></dl>

<hr>
<div class="header">
<p>
Next: <a href="Quadratic-Equations.html#Quadratic-Equations" accesskey="n" rel="next">Quadratic Equations</a>, Previous: <a href="Polynomial-Evaluation.html#Polynomial-Evaluation" accesskey="p" rel="previous">Polynomial Evaluation</a>, Up: <a href="Polynomials.html#Polynomials" accesskey="u" rel="up">Polynomials</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>



</body>
</html>