Lagrange Interpolating Polynomial: Basic Example

The Lagrange polynomial of degree m is defined as:

$\ell_j(x) := \prod\limits_{i=0,\, i\neq j}^{m} \frac{x-x_i}{x_j-x_i}$

The interpolation happens like

$\sum\limits_{j = 1}^{N} y_j*\ell_j(x_k) = y_k$

At the sampled points, $x_j$ the accuracy will be perfect. But at points inbetween, the accuracy of the constructed polynomial may suffer, especially for higher degree interpolations.

The runge phenomena is a manifesation of this innaccuracy, when we interpolate functions that grow with sucessive differentiation, we open ourselves up to this error, because the high order terms get large. This error appears at the boundrys, and it has been shown that using nodes with an asymptotic density to the boundrys, such as chebyshev nodes, will effectively solve this problem.

Chebyshev nodes $x_k$ can be constructed like:

$x_k = cos(\pi*\frac{k}{N})$

for $k = 0,1,2....N$ , the result is on an interval of $\left[-1,1\right]$

Here is a simple matlab function doing a lagrange interpolation for $y$ on $x$ to $x2$

function y2 = lagrange(x,y,x2)
for m=1:numel(x2)
	y2(m) = 0;
	for j=1:numel(x)
		l = 1;
		for k=1:numel(x)
			if k ~= j
				l = l*(x2(m)-x(k))/(x(j)-x(k));
			end

		end

	y2(m) = y2(m) + l*y(j);
	end
end

Like this:

Be the first to like this post.

This entry was posted on April 19, 2009 at 8:41 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.