-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
563 lines (535 loc) · 20.9 KB
/
Copy pathindex.html
File metadata and controls
563 lines (535 loc) · 20.9 KB
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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>Interpolation Methods in Python | Newton, Lagrange, Splines</title>
<meta
name="description"
content="Learn interpolation methods in Python: Newton, Lagrange, barycentric interpolation, cubic splines, divided differences, Chebyshev nodes, plots, and source code."
/>
<meta
name="keywords"
content="Newton interpolation Python, Lagrange interpolation Python, barycentric interpolation Python, cubic splines Python, divided differences Python, polynomial interpolation Python, Chebyshev nodes Python, Runge phenomenon, numerical methods Python, SciPy interpolation"
/>
<meta name="author" content="Jon Ramos" />
<meta name="robots" content="index, follow, max-image-preview:large" />
<link
rel="canonical"
href="https://jonramos.dev/newton-lagrange-interpolation-python/index.html"
/>
<link
rel="alternate"
hreflang="en"
href="https://jonramos.dev/newton-lagrange-interpolation-python/index.html"
/>
<link
rel="alternate"
hreflang="es"
href="https://jonramos.dev/newton-lagrange-interpolation-python/index-es.html"
/>
<link
rel="alternate"
hreflang="eu"
href="https://jonramos.dev/newton-lagrange-interpolation-python/index-eu.html"
/>
<link
rel="alternate"
hreflang="x-default"
href="https://jonramos.dev/newton-lagrange-interpolation-python/index.html"
/>
<meta property="og:type" content="website" />
<meta property="og:title" content="Interpolation Methods in Python" />
<meta
property="og:description"
content="A practical guide to Newton, Lagrange, barycentric interpolation, cubic splines, Chebyshev nodes, and the Runge phenomenon."
/>
<meta name="twitter:card" content="summary_large_image" />
<meta name="twitter:title" content="Interpolation Methods in Python" />
<meta
name="twitter:description"
content="Learn Newton, Lagrange, barycentric interpolation and cubic splines in Python with interactive examples."
/>
<script type="application/ld+json">
{
"@context": "https://schema.org",
"@type": "SoftwareSourceCode",
"name": "Interpolation Methods in Python",
"description": "Practical guide and Python source code for Newton interpolation, Lagrange interpolation, barycentric interpolation, cubic splines, divided differences, Chebyshev nodes and the Runge phenomenon.",
"programmingLanguage": "Python",
"learningResourceType": "Tutorial",
"keywords": [
"Newton interpolation Python",
"Lagrange interpolation Python",
"barycentric interpolation Python",
"cubic splines Python",
"divided differences Python",
"polynomial interpolation",
"Chebyshev nodes",
"Runge phenomenon"
],
"codeRepository": "https://github.com/jramosg/newton-interpolation-method-python"
}
</script>
<link rel="stylesheet" href="styles.css" />
</head>
<body>
<header>
<nav aria-label="Main navigation">
<strong>Python Interpolation Methods</strong>
<div>
<a href="#methods">Methods</a>
<a href="#nodes">Nodes</a>
<a href="#implementation">Code</a>
<a href="#demo">Interactive demo</a>
<a href="#support">Support</a>
<a href="index-es.html" lang="es">Español</a>
<a href="index-eu.html" lang="eu">Euskara</a>
<a href="polynomial_interpolation.py">Source code</a>
</div>
</nav>
</header>
<div class="hero">
<div class="hero-inner">
<div>
<p class="eyebrow">Numerical methods tutorial</p>
<h1>Interpolation methods in Python</h1>
<p class="lead">
A practical guide to Newton interpolation, Lagrange interpolation,
barycentric interpolation, cubic splines, Chebyshev nodes, the Runge
phenomenon, plots, errors, and reusable Python code.
</p>
<div class="hero-actions">
<a class="button primary" href="#demo">Try the demo</a>
<a class="button coffee-link" href="#support">
Support this guide
</a>
<a class="button" href="polynomial_interpolation.py">
Open Python file
</a>
<a
class="button"
href="https://github.com/jramosg/newton-interpolation-method-python"
>
GitHub repository
</a>
</div>
</div>
<figure class="hero-visual" aria-label="Interpolation plot preview">
<div class="visual-toolbar">
<strong>Runge function, 11 nodes</strong>
<div class="legend">
<span><i class="dot" style="background: #17202a"></i>Real</span>
<span><i class="dot" style="background: #1e5eff"></i>Newton</span>
<span><i class="dot" style="background: #c0392b"></i>Nodes</span>
</div>
</div>
<canvas id="heroChart" width="720" height="420"></canvas>
</figure>
</div>
</div>
<main>
<section class="support-strip" aria-label="Support this free guide">
<div>
<strong>Free interpolation guide.</strong>
If this guide saves you time, you can support more tutorials,
examples, and open code.
</div>
<div class="coffee-button">
<a class="coffee-cta" href="https://www.buymeacoffee.com/jramosg">
Buy me a coffee
</a>
</div>
</section>
<section id="methods" aria-labelledby="what">
<h2 id="what">What you will learn</h2>
<p class="section-lead">
This page is written for anyone who wants to understand how to
interpolate data points in Python, not just copy a formula.
</p>
<div class="grid">
<article class="card">
<h3>Newton interpolation</h3>
<p>
Build the divided-difference table and evaluate the Newton
polynomial efficiently with nested multiplication.
</p>
<strong>Core idea: divided differences</strong>
</article>
<article class="card">
<h3>Lagrange interpolation</h3>
<p>
Understand the direct polynomial formula and how SciPy can create
the Lagrange polynomial for small educational examples.
</p>
<strong>Core idea: polynomial basis functions</strong>
</article>
<article class="card">
<h3>Chebyshev nodes</h3>
<p>
Compare equispaced nodes against Chebyshev nodes and see why node
choice matters for the Runge phenomenon.
</p>
<strong>Core idea: better node placement</strong>
</article>
<article class="card">
<h3>Barycentric interpolation</h3>
<p>
Compare a numerically stable polynomial interpolation method used
by SciPy for practical evaluation.
</p>
<strong>Core idea: stable polynomial evaluation</strong>
</article>
<article class="card">
<h3>Cubic splines</h3>
<p>
See why piecewise cubic interpolation can avoid many high-degree
polynomial oscillations.
</p>
<strong>Core idea: smooth piecewise interpolation</strong>
</article>
</div>
</section>
<section id="nodes" aria-labelledby="nodes-title">
<h2 id="nodes-title">Chebyshev nodes vs equispaced nodes</h2>
<p class="section-lead">
Node placement can matter as much as the interpolation formula. With
high-degree polynomial interpolation, equally spaced points may create
large oscillations near the interval edges. Chebyshev nodes cluster
near the endpoints and often reduce that behavior.
</p>
<div class="comparison-grid">
<article class="card">
<h3>Equispaced nodes</h3>
<p>
Easy to understand and common in first examples, but they can
produce large edge oscillations for functions such as Runge's
function when the polynomial degree grows.
</p>
<pre><code>x_nodes = np.linspace(-1, 1, n)</code></pre>
</article>
<article class="card">
<h3>Chebyshev nodes</h3>
<p>
Nodes are denser near the interval endpoints. For global
polynomial interpolation, this usually gives a much better error
profile than equally spaced nodes.
</p>
<pre><code>k = np.arange(1, n + 1)
x_nodes = np.cos((2*k - 1) * np.pi / (2*n))</code></pre>
</article>
</div>
<table>
<thead>
<tr>
<th>Node type</th>
<th>What tends to happen</th>
<th>Try it in the demo</th>
</tr>
</thead>
<tbody>
<tr>
<td>Equispaced</td>
<td>
Simple spacing, but more vulnerable to Runge oscillations.
</td>
<td>Use Runge function with 11 or 21 nodes.</td>
</tr>
<tr>
<td>Chebyshev</td>
<td>
Lower edge oscillation for many global polynomial examples.
</td>
<td>Switch the node type to Chebyshev and compare the curve.</td>
</tr>
</tbody>
</table>
</section>
<section id="newton" aria-labelledby="newton-title">
<h2 id="newton-title">Newton interpolation in Python</h2>
<p class="section-lead">
Newton interpolation writes the polynomial using coefficients from a
divided-difference table. It is useful because adding one new data
point does not require rebuilding the whole polynomial from scratch.
</p>
<div class="steps">
<article class="step">
<h3>Choose the interpolation nodes</h3>
<p>
Start with data points <code>(x0, y0), (x1, y1), ...</code>. The
x-values must be unique.
</p>
</article>
<article class="step">
<h3>Build the divided-difference table</h3>
<p>
The first column is <code>y</code>. Every next column divides the
difference of previous values by the distance between x-nodes.
</p>
</article>
<article class="step">
<h3>Evaluate the Newton polynomial</h3>
<p>
Use nested multiplication for a stable and compact evaluation of
the polynomial.
</p>
</article>
</div>
<pre><code>import numpy as np
from polynomial_interpolation import (
evaluate_newton_polynomial,
newton_coefficients,
)
x_nodes = np.array([-1.0, -0.5, 0.0, 0.5, 1.0])
y_nodes = 1 / (1 + 25 * x_nodes**2)
coefficients = newton_coefficients(x_nodes, y_nodes)
value = evaluate_newton_polynomial(coefficients, x_nodes, 0.25)
print(float(value))</code></pre>
</section>
<section id="lagrange" aria-labelledby="lagrange-title">
<h2 id="lagrange-title">Lagrange interpolation in Python</h2>
<p class="section-lead">
Lagrange interpolation builds the same polynomial as Newton when the
same nodes are used. The formula is direct and easy to read, so it is
common in numerical methods courses.
</p>
<pre><code>import numpy as np
from scipy.interpolate import lagrange
x_nodes = np.array([-1.0, -0.5, 0.0, 0.5, 1.0])
y_nodes = 1 / (1 + 25 * x_nodes**2)
polynomial = lagrange(x_nodes, y_nodes)
print(polynomial(0.25))</code></pre>
<table>
<thead>
<tr>
<th>Method</th>
<th>Best for learning</th>
<th>Práctical note</th>
</tr>
</thead>
<tbody>
<tr>
<td>Newton</td>
<td>Divided differences, incremental interpolation</td>
<td>Good method to implement from scratch.</td>
</tr>
<tr>
<td>Lagrange</td>
<td>Understanding the interpolation polynomial formula</td>
<td>Clear mathematically, but less efficient for updates.</td>
</tr>
<tr>
<td>Barycentric</td>
<td>Stable polynomial interpolation</td>
<td>Usually preferred for numerical polynomial evaluation.</td>
</tr>
<tr>
<td>Cubic spline</td>
<td>Smooth interpolation without high-degree oscillation</td>
<td>Often more robust for real data.</td>
</tr>
</tbody>
</table>
</section>
<section id="implementation" aria-labelledby="implementation-title">
<h2 id="implementation-title">Inside the Python implementation</h2>
<p class="section-lead">
The repository keeps the Newton method as small, readable NumPy
functions. Here are the core pieces, straight from
<a href="polynomial_interpolation.py">polynomial_interpolation.py</a>.
</p>
<h3>Building the divided-difference table</h3>
<p>
The table starts with the <code>y</code> values in the first column.
Each next column divides the difference of the previous column by the
distance between the matching x-nodes. The Newton coefficients are
simply the top row of the finished table.
</p>
<pre><code>def divided_difference_table(x, y):
n = len(x)
table = np.zeros((n, n))
table[:, 0] = y
for order in range(1, n):
for row in range(n - order):
numerator = table[row + 1, order - 1] - table[row, order - 1]
denominator = x[row + order] - x[row]
table[row, order] = numerator / denominator
return table
# Newton coefficients are the top row of the table:
coefficients = divided_difference_table(x, y)[0, :]</code></pre>
<h3>Evaluating with nested multiplication (Horner's scheme)</h3>
<p>
Instead of expanding the polynomial, the evaluator walks the
coefficients backwards and multiplies as it goes. This is numerically
stable, works on a single point or a whole NumPy array, and keeps the
cost linear in the number of nodes.
</p>
<pre><code>def evaluate_newton_polynomial(coefficients, x_nodes, x_eval):
result = np.full_like(x_eval, coefficients[-1], dtype=float)
for i in range(len(coefficients) - 2, -1, -1):
result = result * (x_eval - x_nodes[i]) + coefficients[i]
return result</code></pre>
<h3>Comparing four methods on the same nodes</h3>
<p>
The benchmark builds the Newton polynomial from this repository and
the Lagrange, barycentric and cubic-spline interpolants from SciPy,
then measures the maximum and L2 error against the true function on a
dense grid.
</p>
<pre><code>from scipy.interpolate import (
BarycentricInterpolator,
InterpolatedUnivariateSpline,
lagrange,
)
# Newton (implemented in this repository)
coefficients = newton_coefficients(x_nodes, y_nodes)
y_newton = evaluate_newton_polynomial(coefficients, x_nodes, x_grid)
# Lagrange, barycentric and cubic spline (SciPy)
y_lagrange = lagrange(x_nodes, y_nodes)(x_grid)
y_bary = BarycentricInterpolator(x_nodes, y_nodes)(x_grid)
y_spline = InterpolatedUnivariateSpline(x_nodes, y_nodes, k=3)(x_grid)
# Error against the true function on a dense grid
max_error = np.max(np.abs(y_newton - y_true))
l2_error = np.sqrt(np.trapezoid((y_newton - y_true)**2, x_grid))</code></pre>
</section>
<section id="demo" aria-labelledby="demo-title">
<h2 id="demo-title">Interactive interpolation demo</h2>
<p class="section-lead">
Change the function, nodes, and evaluation point. The plot shows why
Newton and Lagrange give the same polynomial for the same nodes, and
why Chebyshev nodes often reduce oscillation.
</p>
<div class="demo">
<aside class="controls" aria-label="Interpolation controls">
<div class="field">
<label for="functionSelect">Function</label>
<select id="functionSelect">
<option value="runge">Runge: 1 / (1 + 25x²)</option>
<option value="sin">sin(x)</option>
<option value="gaussian">exp(-20x²)</option>
</select>
</div>
<div class="field">
<label for="nodeSelect">Node type</label>
<select id="nodeSelect">
<option value="equispaced">Equispaced nodes</option>
<option value="chebyshev">Chebyshev nodes</option>
</select>
</div>
<div class="field">
<label for="countInput">Number of nodes</label>
<input
id="countInput"
type="number"
min="3"
max="25"
value="11"
/>
</div>
<div class="field">
<label for="pointInput">Evaluate at x</label>
<input
id="pointInput"
type="number"
min="-1"
max="1"
step="0.05"
value="0.25"
/>
</div>
<div class="result" id="demoResult">P(0.25) = ...</div>
</aside>
<figure class="wide-visual">
<div class="visual-toolbar">
<strong>Polynomial interpolation plot</strong>
<div class="legend">
<span><i class="dot" style="background: #17202a"></i>Real</span>
<span
><i class="dot" style="background: #1e5eff"></i>Newton</span
>
<span
><i class="dot" style="background: #c0392b"></i>Nodes</span
>
</div>
</div>
<canvas id="demoChart" width="860" height="430"></canvas>
</figure>
</div>
</section>
<section id="spanish" aria-labelledby="spanish-title">
<h2 id="spanish-title">Newton and Lagrange interpolation in Python</h2>
<div class="split">
<div>
<p>
This page is also useful for readers looking for
<strong>Newton interpolation in Python</strong>,
<strong>Lagrange interpolation in Python</strong>, and
<strong>divided differences in Python</strong>.
</p>
<p>
The main repository script lets you compare equispaced nodes and
Chebyshev nodes, compute maximum error, estimate L2 error, and
save results to CSV.
</p>
</div>
<div>
<pre><code>python -m venv .venv
source .venv/bin/activate
pip install -r requirements.txt
python polynomial_interpolation.py</code></pre>
</div>
</div>
</section>
<section
id="support"
class="support-panel"
aria-labelledby="support-title"
>
<div>
<p class="eyebrow">Support the project</p>
<h2 id="support-title">Help keep this guide free</h2>
<p class="section-lead">
I built this for people looking for a clear interpolation reference
with code, plots, and explanations. If it helped you, a coffee helps
me publish more numerical methods resources.
</p>
</div>
<div class="coffee-button">
<a class="coffee-cta" href="https://www.buymeacoffee.com/jramosg">
Buy me a coffee
</a>
<p>
<a href="https://www.buymeacoffee.com/jramosg">
Open Buy Me a Coffee
</a>
</p>
</div>
</section>
<footer>
<p>
Source code:
<a href="polynomial_interpolation.py">polynomial_interpolation.py</a>.
Repository:
<a
href="https://github.com/jramosg/newton-interpolation-method-python"
>
GitHub </a
>.
</p>
</footer>
</main>
<script src="app.js" defer></script>
<script
data-name="BMC-Widget"
data-cfasync="false"
src="https://cdnjs.buymeacoffee.com/1.0.0/widget.prod.min.js"
data-id="jramosg"
data-description="Support me on Buy Me a Coffee!"
data-message=""
data-color="#FFDD00"
data-position="Right"
data-x_margin="18"
data-y_margin="18"
></script>
</body>
</html>