Interpolació cúbica monòtona

Archiu:MonotCubInt es.png

Eixemple que mostra l'interpolació cúbica no monòtona (en roig) i l'interpolació cúbica monòtona (en blava) d'un conjunt de senyes monòtones

En el camp matemàtic del anàlisis numèric, la interpolació cúbica monòtona és una variant del interpolador cúbic de Hermite que preserva la monotonicidad del conjunt de senyes que s'està interpolando.^[1]

l'interpolació llineal preserva la monotonicidad (és dir, que l'altura de la série de punts i de la curva siga sempre ascendent o descendent, sense canvis en el signe de la pendent), pero l'interpolació cúbica no la garantisa.

Interpolació cúbica monòtona de Hermite

L'interpolació monòtona es pot conseguir usant l'interpolador cúbic de Hermite en les tangentes $m_{i}$ modificades per a garantisar la monotonicidad del spline de Hermite resultant.

També està disponible un algoritme per a l'interpolació monòtona quíntica de Hermite.

Selecció del polinomi interpolante

Hi ha vàries formes de seleccionar tangentes d'interpolació per a cada punt del conjunt de senyes. Esta secció descriurà l'us del método de Fritsch-Carlson.^[2] Tinga's en conte que solament es requerix una passada de l'algoritme.

Considere's que els punts del conjunt de senyes $(x_{k}, y_{k})$ s'indexen en orde per a $k = 1, \dots n$ .

Calcular les pendents de les rectes secantes entre punts successius:
$δ_{k} = \frac{y_{k + 1} - y_{k}}{x_{k + 1} - x_{k}}$
per a $k = 1, \dots n - 1$ .
Estes assignació són provisionals, i poden ser reemplaçades en els passos restants. Inicialícense les tangentes en cada punt de senyes interior com el promig de les secantes,
$m_{k} = \frac{δ_{k - 1} + δ_{k}}{2}$
per a $k = 2, \dots n - 1$ .

Per als punts finals, utilisar les diferències d'un sol costat:
$m_{1} = δ_{1} y m_{n} = δ_{n - 1}$
.
Si $δ_{k - 1}$ i $δ_{k}$ tenen signes oposts, configurar $m_{k} = 0$ .
Per a $k = 1, \dots n - 1$ , sempre que $δ_{k} = 0$ (a on dos $y_{k} = y_{k + 1}$ successius siguen iguals),
establir $m_{k} = m_{k + 1} = 0,$ ya que el spline que conecta estos punts sempre deu decréixer (o créixer) a mida que s'alvança segons l'eix x per a preservar la monotonicidad.
Ignorar els passos 4 i 5 per a aquells $k$ .
Deixar
$α_{k} = m_{k} / δ_{k} y β_{k} = m_{k + 1} / δ_{k}$
.
Si $α_{k}$ o $β_{k}$ és negatiu, llavors els punts de senyes d'entrada no són estrictament monòtons i $(x_{k}, y_{k})$ és un extrem local. En tals casos, encara es poden generar curves monòtones "per parts" elegint $m_{k} = 0$ si $α_{k} < 0$ o $m_{k + 1} = 0$ si $β_{k} < 0$ , encara que la monotonicidad estricta no és possible globalment.
Per a evitar sobrepasse i garantisar la monotonicidad, es deu complir a lo manco una de les tres condicions següents:

(a) La funció

$ϕ_{k} = α_{k} - \frac{(2 α_{k} + β_{k} - 3)^{2}}{3 (α_{k} + β_{k} - 2)} > 0$
, 'o

(b)

α_{k} + 2 β_{k} - 3 \leq 0

, 'o

(c)

2 α_{k} + β_{k} - 3 \leq 0

.

Solament la condició (a) és suficient per a garantisar una monotonicidad estricta:

ϕ_{k}

deu ser positiu.

Una forma senzilla de satisfer esta restricció és restringir el vector

(α_{k}, β_{k})

a un círcul de radi 3. És dir, si és

α_{k}^{2} + β_{k}^{2} > 9

, establir

$τ_{k} = \frac{3}{\sqrt{α_{k}^{2} + β_{k}^{2}}}$
,

i canviar l'escala de les tangentes per mig de

$m_{k} = τ_{k} α_{k} δ_{k} y m_{k + 1} = τ_{k} β_{k} δ_{k}$
.

Com a alternativa, és suficient restringir

α_{k} \leq 3

i

β_{k} \leq 3

. Per a conseguir açò, si és

α_{k} > 3 o β_{k} > 3

, configurar

m_{k} = 3 δ_{k}

.

Interpolació cúbica

Despuix del preprocesamiento anterior, l'evaluació del spline interpolado és equivalent a la del interpolador cúbic de Hermite, utilisant les senyes $x_{k}$ , $y_{k}$ i $m_{k}$ per a $k = 1, \dots n$ .

Per a evaluar en $x$ , buscar l'índex $k$ en la seqüència a on $x$ es troba entre $x_{k}$ i $x_{k + 1}$ , és dir: $x_{k} \leq x \leq x_{k + 1}$ . Calcular

Δ = x_{k + 1} - x_{k} y t = \frac{x - x_{k}}{Δ}

llavors, el valor interpolado és

f_{interpolada} (x) = y_{k} \cdot h_{00} (t) + Δ \cdot m_{k} \cdot h_{10} (t) + y_{k + 1} \cdot h_{01} (t) + Δ \cdot m_{k + 1} \cdot h_{11} (t)

a on $h_{i i}$ són les funcions bàsiques per al interpolador cúbic de Hermite.

Còdic d'eixemple

El següent còdic en JavaScript pren un conjunt de senyes i produïx una funció d'interpolació monòtona per mig d'un spline cúbic:

/*
 * Monotone cubic spline interpolation
 * Usage example listed at bottom; this is a fully-functional package. For
 * example, this ca be executed either at sites like
 * https://www.programiz.com/javascript/online-compiler/
 * or using nodeJS.
 */
function DEBUG(s) {
    /* Uncomment the following to enable verbose output of the solver: */
    //console.log(s);
}
var outputCounter= 0;
var createInterpolant= function(xs, ys) {
    var i, length= xs.length;
    
    // Deal with length issues
    if (length != ys.length) {throw 'Need an equal count of xs and ys.'; }
    if (length=== 0) {return function(x) {return 0; }; }
    if (length=== 1) {
        // Impl: Precomputing the result prevents problems if ys is mutated later and allows garbage collection of ys
        // Impl: Unary plus properly converts values to numbers
        var result= +ys[0];
        return function(x) {return result; };
    }
    
    // Rearrange xs and ys baix that xs is sorted
    var indexes= [];
    for (i= 0; i < length; i++) {indexes.push(i); }
    indexes.sort(function(a, b) {return xs[a] < xs[b] ? -1 : 1; });
    var oldXs= xs, oldYs= ys;
    // Impl: Creating new arrays also prevents problems if the input arrays llaure mutated later
    xs= []; ys= [];
    // Impl: Unary plus properly converts values to numbers
    for (i= 0; i < length; i++) {
        xs[i]= +oldXs[indexes[i]];
        ys[i]= +oldYs[indexes[i]];
    }

    DEBUG("debug: xs= [ " + xs + " ]")
    DEBUG("debug: ys= [ " + ys + " ]")
    
    // Get consecutive differences and slopes
    var dys= [], dxs= [], ms= [];
    for (i= 0; i < length - 1; i++) {
        var dx= xs[i + 1] - xs[i], dy= ys[i + 1] - ys[i];
        dxs[i]= dx;
        dys[i]= dy;
        ms[i]= dy/dx;
    }
    // Get degree-1 coefficients
    var c1s= [ms[0]];
    for (i= 0; i < dxs.length - 1; i++) {
        var m= ms[i], mNext= ms[i + 1];
        if (m*mNext <= 0) {
            c1s[i]= 0;
        } else {
            var dx_= dxs[i], dxNext= dxs[i + 1], common= dx_ + dxNext;
            c1s[i]= 3*common/((common + dxNext)/m + (common + dx_)/mNext);
        }
    }
    c1s.push(ms[ms.length - 1]);

    DEBUG("debug: dxs= [ " + dxs + " ]")
    DEBUG("debug: ms= [ " + ms + " ]")
    DEBUG("debug: c1s.length= " + c1s.length)
    DEBUG("debug: c1s= [ " + c1s + " ]")
    
    // Get degree-2 and degree-3 coefficients
    var c2s= [], c3s= [];
    for (i= 0; i < c1s.length - 1; i++) {
        var c1= c1s[i];
        var m_= ms[i];
        var invDx= 1/dxs[i];
        var common_= c1 + c1s[i + 1] - m_ - m_;
        DEBUG("debug: " + i + ". c1= " + c1);
        DEBUG("debug: " + i + ". m_= " + m_);
        DEBUG("debug: " + i + ". invDx= " + invDx);
        DEBUG("debug: " + i + ". common_= " + common_);
        c2s[i]= (m_ - c1 - common_)*invDx;
        c3s[i]= common_*invDx*invDx;
    }
    DEBUG("debug: c2s= [ " + c2s + " ]")
    DEBUG("debug: c3s= [ " + c3s + " ]")

    // Return interpolant function
    return function(x) {
        // The rightmost point in the dataset should give an exact result
        var i= xs.length - 1;
        // Uncomment the following to return only the interpolated value.
        //if (x== xs[i]) {return ys[i]; }
        

// Search for the interval x is in, returning the corresponding i if x is one of the original xs
        var low= 0, mid, high= c3s.length - 1;
        while (low <= high) {
            mid= Math.floor(0.5*(low + high));
            var xHere= xs[mid];
            if (xHere < x) {low= mid + 1; }
            else if (xHere > x) {high= mid - 1; }
            else {
                // Uncomment the following to return only the interpolated value.
                //return ys[mid];
                low= c3s.length - 1;
                high= mid;
                break;
            }
        }
        i= Math.max(0, high);

        // Interpolate
        var diff= x - xs[i];
        outputCounter++;
        var interpolatedValue= ys[i] + diff * (c1s[i] + diff *  (c2s[i] + diff * c3s[i]));
        // The value of the interpolator's derivative at this point.
        var derivativeValue= c1s[i] + diff * (2c2s[i] + diff * 3c3s[i]);
        DEBUG("debug: #" + outputCounter + ". x= " + x + ". i= " + i + ", diff= " + diff + ", interpolatedValue= " + interpolatedValue + ", derivativeValue= " + derivativeValue);
        // Uncomment the following to return only the interpolated value.
        // return interpolatedValue;
        return [ interpolatedValue, derivativeValue ];
    };
};

/*
   Usage example below will approximate x^2 for 0 <= x <= 4.

   Command line usage example (requires installation of nodejs):
   node monotone-cubic-spline.js
*/

var X= [0, 1, 2, 3, 4];
var F= [0, 1, 4, 9, 16];
var f= createInterpolant(X,F);
var N= X.length;
console.log("# BLOCK 0 :: Data for monotone-cubic-spline.js");
console.log("X" + "	" + "F");
for (var i= 0; i < N; i += 1) {
    console.log(X[i] + '	' + F[i]);
}
console.log(" ");
console.log(" ");
console.log("# BLOCK 1 :: Interpolated data for monotone-cubic-spline.js");
console.log("      x       " + "		" + "     P(x)      " + "		" + "    dP(x)/dx     ");
var message= '';
var M= 25;
for (var i= 0; i <= M; i += 1) {
    var x= X[0] + (X[N-1]-X[0])*i/M;
    var rvals= f(x);
    var P= rvals[0];
    var D= rvals[1];
    message += x.toPrecision(15) + '	' + P.toPrecision(15) + '	' + D.toPrecision(15) + '
';
}
console.log(message);

Referències

↑ Gary D. Knott (2012). Interpolating Cubic Splines, Springer Science & Business Media, pp. 69 de 244. ISBN 9781461213208.
↑ Boris I Kvasov (2000). Methods Of Shape-preserving Spline Approximation, World Scientific, pp. 146 de 356. ISBN 9789814494472.

Bibliografia

Referències

Este artícul conté una traducció derivada de «Interpolación cúbica monótona» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[GDK-1] Gary D. Knott (2012). Interpolating Cubic Splines, Springer Science & Business Media, pp. 69 de 244. ISBN 9781461213208.

[BIK-2] Boris I Kvasov (2000). Methods Of Shape-preserving Spline Approximation, World Scientific, pp. 146 de 356. ISBN 9789814494472.

[1]

[2]