Spline interpolace - Spline interpolation

V matematický pole numerická analýza, spline interpolace je forma interpolace kde interpolant je speciální typ po částech polynomiální volal a spline. Interpolace spline je často upřednostňována polynomiální interpolace protože chyba interpolace lze zmenšit i při použití polynomů nízkého stupně pro spline.^[1] Spline interpolace se vyhne problému Rungeův fenomén, ve kterém může dojít k oscilaci mezi body při interpolaci pomocí polynomů vysokého stupně.

Úvod

Původně, spline byl termín pro elastický vládci které byly ohnuty, aby prošly několika předdefinovanými body („uzly“). Ty byly použity k výrobě technické výkresy pro stavba lodí a konstrukce ručně, jak je znázorněno na obrázku 1.

Obrázek 1: Interpolace s kubickými spline mezi osmi body. Ručně vyráběné technické výkresy pro stavbu lodí byly vytvořeny pomocí flexibilních pravítek, které byly ohnuty tak, aby sledovaly předem definované body

Přístup k matematickému modelování tvaru takových elastických pravítek fixovaný pomocí $n + 1$ uzly ${ displaystyle left {(x_ {i}, y_ {i}): i = 0,1, cdots, n right }}$ je interpolovat mezi všemi páry uzlů ${ displaystyle (x_ {i-1}, y_ {i-1})}$ a ${ displaystyle (x_ {i}, y_ {i})}$ s polynomy ${ displaystyle y = q_ {i} (x), i = 1,2, cdots, n}$ .

The zakřivení křivky ${ displaystyle y = f (x)}$ darováno:

{ displaystyle kappa = { frac {y ''} {(1 + y '^ {2}) ^ {3/2}}}}

Protože spline získá tvar, který minimalizuje ohyb (pod omezením průchodu všemi uzly), oba ${ displaystyle '$ a ${ displaystyle y ''}$ bude spojitá všude a na uzlech. K dosažení tohoto cíle je třeba mít toto

{ displaystyle { begin {cases} q '_ {i} (x_ {i}) = q' _ {i + 1} (x_ {i}) q '' _ {i} (x_ {i} ) = q '' _ {i + 1} (x_ {i}) end {cases}} qquad 1 leq i leq n-1}

Toho lze dosáhnout pouze při použití polynomů stupně 3 nebo vyšších. Klasickým přístupem je použití polynomů stupně 3 - případ kubické splajny.

Algoritmus pro nalezení interpolační kubické spline

Polynom třetího řádu ${ displaystyle q (x)}$ pro který

{ displaystyle q (x_ {1}) = y_ {1}}

{ displaystyle q (x_ {2}) = y_ {2}}

{ displaystyle q '(x_ {1}) = k_ {1}}

{ displaystyle q '(x_ {2}) = k_ {2}}

lze psát symetricky

{ displaystyle q (x) = { velký (} 1-t (x) { velký)} , y_ {1} + t (x) , y_ {2} + t (x) { velký ( } 1-t (x) { big)} { Big (} { big (} 1-t (x) { big)} , a + t (x) , b { Big)}}

(1)

kde

{ displaystyle t (x) = { frac {x-x_ {1}} {x_ {2} -x_ {1}}},}

(2)

{ displaystyle a = k_ {1} (x_ {2} -x_ {1}) - (y_ {2} -y_ {1}),}

(3)

{ displaystyle b = -k_ {2} (x_ {2} -x_ {1}) + (y_ {2} -y_ {1}).}

(4)

Tak jako

{ displaystyle q '= { frac {dq} {dx}} = { frac {dq} {dt}} { frac {dt} {dx}} = { frac {dq} {dt}} { frac {1} {x_ {2} -x_ {1}}}}

jeden dostane, že:

{ displaystyle q '= { frac {y_ {2} -y_ {1}} {x_ {2} -x_ {1}}} + (1-2t) { frac {a (1-t) + bt } {x_ {2} -x_ {1}}} + t (1-t) { frac {ba} {x_ {2} -x_ {1}}},}

(5)

{ displaystyle q '' = 2 { frac {b-2a + (a-b) 3t} {{(x_ {2} -x_ {1})} ^ {2}}}.}

(6)

Nastavení $t = 0$ a $t = 1$ respektive v rovnicích (5) a (6) jeden dostane z (2), že skutečně první deriváty $q ' (X 1) = k 1$ a $q ' (X 2) = k 2$ a také druhé deriváty

{ displaystyle q '' (x_ {1}) = 2 { frac {b-2a} {{(x_ {2} -x_ {1})} ^ {2}}}}

(7)

{ displaystyle q '' (x_ {2}) = 2 { frac {a-2b} {{(x_ {2} -x_ {1})} ^ {2}}}}

(8)

Pokud teď $(X i, y i), i = 0, 1, ..., n$ jsou $n + 1$ body a

{ displaystyle q_ {i} = (1-t) , y_ {i-1} + t , y_ {i} + t (1-t) { big (} (1-t) , a_ { i} + t , b_ {i} { velký)}}

(9)

kde i = 1, 2, ..., n a ${ displaystyle t = { tfrac {x-x_ {i-1}} {x_ {i} -x_ {i-1}}}}$ jsou n interpolace polynomů třetího stupně $y$ v intervalu $X i -1 \leq X \leq X i$ pro i = 1, ..., n takhle $q ' i (X i) = q ' i +1 (X i)$ pro i = 1, ..., n-1 pak n polynomy společně definují diferencovatelnou funkci v intervalu $X 0 \leq X \leq X n$ a

{ displaystyle a_ {i} = k_ {i-1} (x_ {i} -x_ {i-1}) - (y_ {i} -y_ {i-1})}

(10)

{ displaystyle b_ {i} = - k_ {i} (x_ {i} -x_ {i-1}) + (y_ {i} -y_ {i-1})}

(11)

pro i = 1, ..., n kde

{ displaystyle k_ {0} = q_ {1} '(x_ {0})}

(12)

{ displaystyle k_ {i} = q_ {i} '(x_ {i}) = q_ {i + 1}' (x_ {i}) qquad i = 1, dotsc, n-1}

(13)

{ displaystyle k_ {n} = q_ {n} '(x_ {n})}

(14)

Pokud sekvence $k 0, k 1, ..., k n$ je takový, že navíc $q ' ' i (X i) = q ' ' i +1 (X i)$ platí pro i = 1, ..., n-1, pak bude mít výsledná funkce dokonce spojitou druhou derivaci.

Z (7), (8), (10) a (11) vyplývá, že tomu tak je tehdy a jen tehdy

{ displaystyle { frac {k_ {i-1}} {x_ {i} -x_ {i-1}}} + left ({ frac {1} {x_ {i} -x_ {i-1} }} + { frac {1} {x_ {i + 1} -x_ {i}}} vpravo) 2k_ {i} + { frac {k_ {i + 1}} {x_ {i + 1} - x_ {i}}} = 3 left ({ frac {y_ {i} -y_ {i-1}} {{(x_ {i} -x_ {i-1})} ^ {2}}} + { frac {y_ {i + 1} -y_ {i}} {{(x_ {i + 1} -x_ {i})} ^ {2}}} vpravo)}

(15)

pro i = 1, ..., n-1. Vztahy (15) jsou $n - 1$ lineární rovnice pro $n + 1$ hodnoty $k 0, k 1, ..., k n$ .

Protože jsou pružná pravítka modelem interpolace splajnu, máme tu, že nalevo od „uzlu“ nejvíce vlevo a napravo od „uzlu“ nejvíce vpravo se může pravítko volně pohybovat, a proto bude mít podobu přímka s $q ' ' = 0$ . Tak jako $q ' '$ by měla být spojitou funkcí $X$ jeden dostane to za "Natural Splines" jeden navíc k $n - 1$ lineární rovnice (15) by to mělo mít

{ displaystyle q '' _ {1} (x_ {0}) = 2 { frac {3 (y_ {1} -y_ {0}) - (k_ {1} + 2k_ {0}) (x_ {1 } -x_ {0})} {{(x_ {1} -x_ {0})} ^ {2}}} = 0,}

{ displaystyle q '' _ {n} (x_ {n}) = - 2 { frac {3 (y_ {n} -y_ {n-1}) - (2k_ {n} + k_ {n-1} ) (x_ {n} -x_ {n-1})} {{(x_ {n} -x_ {n-1})} ^ {2}}} = 0,}

tj. to

{ displaystyle { frac {2} {x_ {1} -x_ {0}}} k_ {0} + { frac {1} {x_ {1} -x_ {0}}} k_ {1} = 3 { frac {y_ {1} -y_ {0}} {(x_ {1} -x_ {0}) ^ {2}}},}

(16)

{ displaystyle { frac {1} {x_ {n} -x_ {n-1}}} k_ {n-1} + { frac {2} {x_ {n} -x_ {n-1}}} k_ {n} = 3 { frac {y_ {n} -y_ {n-1}} {(x_ {n} -x_ {n-1}) ^ {2}}}.}

(17)

Nakonec, (15) dohromady s (16) a (17) představovat $n + 1$ lineární rovnice, které jednoznačně definují $n + 1$ parametry $k 0, k 1, ..., k n$ .

Existují další koncové podmínky: „Upnutý spline“, který určuje sklon na koncích spline, a populární „spline bez uzlu“, která vyžaduje, aby třetí derivace byla také spojitá na $X 1$ a $X N -1$ points.For the "not-a-knot" spline, the additional equations will read:

{ displaystyle q '' '_ {1} (x_ {1}) = q' '' _ {2} (x_ {1}) Rightarrow { frac {1} { Delta x_ {1} ^ {2 }}} k_ {0} + left ({ frac {1} { Delta x_ {1} ^ {2}}} - { frac {1} { Delta x_ {2} ^ {2}}} right) k_ {1} - { frac {1} { Delta x_ {2} ^ {2}}} k_ {2} = 2 left ({ frac { Delta y_ {1}} { Delta x_ {1} ^ {3}}} - { frac { Delta y_ {2}} { Delta x_ {2} ^ {3}}} vpravo)}

{ displaystyle q '' '_ {n-1} (x_ {n-1}) = q' '_ {n} (x_ {n-1}) Rightarrow { frac {1} { Delta x_ {n-1} ^ {2}}} k_ {n-2} + left ({ frac {1} { Delta x_ {n-1} ^ {2}}} - { frac {1} { Delta x_ {n} ^ {2}}} vpravo) k_ {n-1} - { frac {1} { Delta x_ {n} ^ {2}}} k_ {n} = 2 vlevo ( { frac { Delta y_ {n-1}} { Delta x_ {n-1} ^ {3}}} - { frac { Delta y_ {n}} { Delta x_ {n} ^ {3 }}}že jo)}

kde ${ displaystyle Delta x_ {i} = x_ {i} -x_ {i-1}, Delta y_ {i} = y_ {i} -y_ {i-1}}$ .

Příklad

Obrázek 2: Interpolace s kubickými „přirozenými“ spline mezi třemi body.

V případě tří bodů hodnoty pro ${ displaystyle k_ {0}, k_ {1}, k_ {2}}$ jsou nalezeny řešením tridiagonální lineární rovnice

{ displaystyle { begin {bmatrix} a_ {11} & a_ {12} & 0 a_ {21} & a_ {22} & a_ {23} 0 & a_ {32} & a_ {33} end {bmatrix}} { begin {bmatrix} k_ {0} k_ {1} k_ {2} end {bmatrix}} = { begin {bmatrix} b_ {1} b_ {2} b_ {3} end {bmatrix}}}

s

{ displaystyle a_ {11} = { frac {2} {x_ {1} -x_ {0}}}}

{ displaystyle a_ {12} = { frac {1} {x_ {1} -x_ {0}}}}

{ displaystyle a_ {21} = { frac {1} {x_ {1} -x_ {0}}}}

{ displaystyle a_ {22} = 2 vlevo ({ frac {1} {x_ {1} -x_ {0}}} + { frac {1} {x_ {2} -x_ {1}}} že jo)}

{ displaystyle a_ {23} = { frac {1} {x_ {2} -x_ {1}}}}

{ displaystyle a_ {32} = { frac {1} {x_ {2} -x_ {1}}}}

{ displaystyle a_ {33} = { frac {2} {x_ {2} -x_ {1}}}}

{ displaystyle b_ {1} = 3 { frac {y_ {1} -y_ {0}} {(x_ {1} -x_ {0}) ^ {2}}}}

{ displaystyle b_ {2} = 3 vlevo ({ frac {y_ {1} -y_ {0}} {{(x_ {1} -x_ {0})} ^ {2}}} + { frac {y_ {2} -y_ {1}} {{(x_ {2} -x_ {1})} ^ {2}}} vpravo)}

{ displaystyle b_ {3} = 3 { frac {y_ {2} -y_ {1}} {(x_ {2} -x_ {1}) ^ {2}}}}

Za tři body

{ displaystyle (-1,0,5) , (0,0) , (3,3)}

,

jeden to dostane

{ displaystyle k_ {0} = - 0,6875 , k_ {1} = - 0,1250 , k_ {2} = 1,5625}

a od (10) a (11) že

{ displaystyle a_ {1} = k_ {0} (x_ {1} -x_ {0}) - (y_ {1} -y_ {0}) = - 0,1875}

{ displaystyle b_ {1} = - k_ {1} (x_ {1} -x_ {0}) + (y_ {1} -y_ {0}) = - 0,3750}

{ displaystyle a_ {2} = k_ {1} (x_ {2} -x_ {1}) - (y_ {2} -y_ {1}) = - 3,3750}

{ displaystyle b_ {2} = - k_ {2} (x_ {2} -x_ {1}) + (y_ {2} -y_ {1}) = - 1,6875}

Na obrázku 2 je funkce splajnu skládající se ze dvou kubických polynomů ${ displaystyle q_ {1} (x)}$ a ${ displaystyle q_ {2} (x)}$ dána (9) je zobrazen.

Viz také

Počítačový kód

TinySpline: Open source C-knihovna pro splajny, která implementuje kubickou spline interpolaci

SciPy Spline Interpolation: balíček Pythonu, který implementuje interpolaci

Kubická interpolace: Open source C # -knihovna pro kubickou spline interpolaci

Reference

^ Hall, Charles A .; Meyer, Weston W. (1976). Msgstr "Optimální hranice chyb pro kubickou spline interpolaci". Žurnál teorie přiblížení. 16 (2): 105–122. doi:10.1016 / 0021-9045 (76) 90040-X.

Schoenberg, Isaac J. (1946). „Příspěvky k problému aproximace ekvidistantních dat analytickými funkcemi: Část A. - K problému vyhlazení nebo promoce. První třída vzorců analytické aproximace“. Quarterly of Applied Mathematics. 4 (2): 45–99. doi:10.1090 / qam / 15914.CS1 maint: ref = harv (odkaz)
Schoenberg, Isaac J. (1946). „Příspěvky k problému aproximace ekvidistantních dat analytickými funkcemi: Část B. - K problému oscilační interpolace. Druhá třída vzorců analytické aproximace“. Quarterly of Applied Mathematics. 4 (2): 112–141. doi:10.1090 / qam / 16705.CS1 maint: ref = harv (odkaz)

externí odkazy

[1] Hall, Charles A .; Meyer, Weston W. (1976). Msgstr "Optimální hranice chyb pro kubickou spline interpolaci". Žurnál teorie přiblížení. 16 (2): 105–122. doi:10.1016 / 0021-9045 (76) 90040-X.

[1]