12,072,536 members (60,504 online)
alternative version

82.1K views
79 bookmarked
Posted

# Curve Fitting using Lagrange Interpolation

, 12 Sep 2008 CPOL
 Rate this:
Fitting a set of points P to a curve using Lagrange Interpolation Polynomial.

## Introduction

In this article, I will explain curve fitting using the Lagrange interpolation polynomial. Curve fitting is used in a wide spectrum in engineering applications such as cars and air crafts surface design. The main problem is, given a set of points in the plan, we want to fit them in a smooth curve that passes through these points. The order of the curve f(x) depends on the number of points given. For example, if we have two points, the function will be of the first order, and the curve will be the line that passes through these two points, while if you have three points, the function will be of the second order f(x) = x2 . Let's first explain the Lagrange polynomial, then we will proceed to the algorithm and the implementation. In this article, I am using C# for coding.

## Background

### Lagrange Polynomial

An interpolation on two points, (x0, y0) and (x1, y1), results in a linear equation or a straight line. The standard form of a linear equation is given by y = mx + c, where m is the gradient of the line and c is the y-intercept.

```m = y1 − y0 / x1 − x0
c = y0 − mx0```

which results in:

`y = (y1 − y0 / x1 − x0) * x + (x1 y0 − x0 y1 )/ (x1 − x0)`

The linear equation is rewritten so that the two interpolated points, (x0, y0) and (x1, y1), are directly represented.

With this in mind, the linear equation is rewritten as:

`P1(x) = a0(x − x1) + a1(x − x0)`

where a0 and a1 are constants . The points x0 and x1 in the factors of the above equation are called the centers. Applying the equation at (x0, y0), we obtain:

```y0 = a0(x0 − x1) + a1(x0 − x0)

or

a0 = y0/ x0−x1 ```

At (x1, y1), we get:

`y1 = a0(x1 − x1) + a1(x1 − x0), or a1 = y1/ x1−x0`

Therefore, the linear equation becomes:

`P1(x) = y0 (x− x1) /(x0 − x1) + y1 (x− x0) / (x1 − x0)`

The quadratic form of the Lagrange polynomial interpolates three points, (x0, y0), (x1, y1), and (x2, y2). The polynomial has the form:

`P2(x) = a0(x− x1)(x− x2) + a1(x− x0) (x− x2) + a2(x− x0)(x− x1)`

with centers at x0, x1, and x2. At (x0, y0):

```y0 = a0(x0 − x1)(x0 − x2) + a1(x0 − x0)(x0 − x2) + a2(x0 − x0)(x0 − x1),

or

a0 = y0/ (x0 − x1)(x0 − x2)
a1 = y1 / (x1 − x0)(x1 − x2)
a2 = y2/ (x2 − x0)(x2 − x1)
P2(x) = y0 (x− x1)(x− x2) / (x0 − x1)(x0 − x2) + y1 (x − x0)(x − x2)/
(x1 − x0)(x1 − x2) + y2 (x− x0)(x− x1)/ (x2 − x0)(x2 − x1)```

In general, a Lagrange polynomial of degree n is a polynomial that is produced from an interpolation over a set of points, (xi , yi ) for i = 0, 1, . . ., n, as follows:

`Pn(x) = y0L0(x) + y1L1(x) + ··· + ynLn(x)`

## Using the Code

### The Algorithm

```Given the interpolating points (xi , yi ) for i =0, 1, . . . ,n;

for i = 0 to n
//the cumulative multiplication from k = 1 (and k not equal i) to n
Evaluate Li (x) = ∏nk=1,k != i (x−xk ) / (xi−xk ) ;
endfor

Evaluate Pn(x) = y0L0(x) + y1L1(x) + ··· + ynLn(x);
```

Download the source code from the top of this page to view the code.

## Points of Interest

Numerical computing is a very interesting field in software development. This article is related to that field ... And, I will post more articles soon about Computational Geometry ...such as Convex Hull algorithm and Triangulation.

## About the Author

 Software Developer Egypt
No Biography provided

## Comments and Discussions

 First Prev Next
 A compact version gustavtr20-Feb-12 12:24 gustavtr 20-Feb-12 12:24
 Re: A compact version Member 1194359329-Aug-15 10:18 Member 11943593 29-Aug-15 10:18
 My vote of 5 MarkDaniel5-Jan-12 13:21 MarkDaniel 5-Jan-12 13:21
 how to get all pixels coordinate from curve fitting using Lagrange interpolationan on an image MrKyaw24-Oct-11 17:18 MrKyaw 24-Oct-11 17:18
 Radius of curve M i s t e r L i s t e r25-Aug-10 10:48 M i s t e r L i s t e r 25-Aug-10 10:48
 need help plz d_e_e_o6-Aug-10 5:33 d_e_e_o 6-Aug-10 5:33
 Corrected an Overflow error SBGTrading22-Jul-10 6:05 SBGTrading 22-Jul-10 6:05
 Contact icae27-Apr-09 6:42 icae 27-Apr-09 6:42
 Area under the curve Dorisvaldo16-Sep-08 16:06 Dorisvaldo 16-Sep-08 16:06
 piecewise bezier Sarath.14-Sep-08 22:54 Sarath. 14-Sep-08 22:54
 Re: piecewise bezier catbertfromgilead15-Sep-08 10:31 catbertfromgilead 15-Sep-08 10:31
 I don't mean to quibble but this looks like interpolation MicroImaging11-Sep-08 12:15 MicroImaging 11-Sep-08 12:15
 Re: I don't mean to quibble but this looks like interpolation axelriet12-Sep-08 6:30 axelriet 12-Sep-08 6:30
 Re: I don't mean to quibble but this looks like interpolation MicroImaging12-Sep-08 10:20 MicroImaging 12-Sep-08 10:20
 Awesome! Just what I've been looking for! dybs6-Sep-08 8:42 dybs 6-Sep-08 8:42
 Re: Awesome! Just what I've been looking for! Fady Aladdin11-Sep-08 3:36 Fady Aladdin 11-Sep-08 3:36
 Re: Awesome! Just what I've been looking for! dybs11-Sep-08 7:32 dybs 11-Sep-08 7:32
 I can't give out too much information since it's a work-related project, but we have a graph with 2 fixed points at the end, and we fit a curve to a point the user clicks on somewhere on the graph. Right now we only use a single click point, but we may extend it to work with a series of user-defined points. Sorry, I can't really say much more than that. Thanks again for the article! Dybs
 Re: Awesome! Just what I've been looking for! axelriet12-Sep-08 6:26 axelriet 12-Sep-08 6:26
 Computational Geometry abombardier2-Sep-08 15:37 abombardier 2-Sep-08 15:37
 Re: Computational Geometry axelriet12-Sep-08 6:10 axelriet 12-Sep-08 6:10
 Re: Computational Geometry abombardier12-Sep-08 10:26 abombardier 12-Sep-08 10:26
 getting back values KJJ22-Sep-08 11:21 KJJ2 2-Sep-08 11:21
 Last Visit: 31-Dec-99 19:00     Last Update: 10-Feb-16 10:30 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.