---
title: 10-1. Runge phenomenan and condition number
tags: Spectral method
---

**Reading**
1. [wiki: Runge's phenomenon](https://en.wikipedia.org/wiki/Runge%27s_phenomenon)
2. [SIAM Rev.: The Runge Example for Interpolation and Wilkinson's. Examples for Rootfinding](https://epubs.siam.org/doi/pdf/10.1137/18M1181985)

**Textbook**
1. [Spectral method in Matlab](https://people.maths.ox.ac.uk/trefethen/spectral.html) by *Lloyd N. Trefethen*

---

## Myths - Polynomial interpolants diverges as $n\to\infty$

* This is true for equi-spaced points, known as Runge's phenomenan.

* If the orthogonal polynomials are used instead, the polynomial interpolants converge without any problem.

% p9.m - polynomial interpolation in equispaced and Chebyshev pts

N = 16;
xx = -1:.005:1; clf
for i = 1:2
    if i==1, s = 'equispaced points'; x = -1 + 2*(0:N)/N; end
    if i==2, s = 'Chebyshev points';  x = cos(pi*(0:N)/N); end
    subplot(2,1,i)
    u = 1./(1+16*x.^2);
    uu = 1./(1+16*xx.^2);
    p = polyfit(x,u,N);              % interpolation
    pp = polyval(p,xx);              % evaluation of interpolant
    plot(x,u,'.','markersize',13)
    line(xx,pp)
    axis([-1.1 1.1 -1 1.5]), title(s)
    error = norm(uu-pp,inf);
    text(-.5,-.5,['max error = ' num2str(error)])
end

#### Condition number for Runge function at equi-spaced points

N = 16;
x = -1 + 2*(0:N)/N;
u = 1./(1+16*x.^2);

xx = -1:.005:1;
B = zeros(size(xx));
for ii=1:N+1
    u0 = zeros(1,N+1);
    u0(ii)=1;
    p = polyfit(x,u0,N);
    B = B+abs(polyval(p,xx))*u(ii);
end
semilogy(xx, B)

#### Condition number for Runge function at Chebyshev points

N = 16;
x = cos(pi*(0:N)/N);
u = 1./(1+16*x.^2);

xx = -1:.005:1;
B = zeros(size(xx));
for ii=1:N+1
    u0 = zeros(1,N+1);
    u0(ii)=1;
    p = polyfit(x,u0,N);
    B = B+abs(polyval(p,xx))*u(ii);
end
plot(xx, B)