Interpolação de spline - Spline interpolation

No campo matemático da análise numérica , a interpolação de spline é uma forma de interpolação em que o interpolante é um tipo especial de polinômio por partes chamado spline . Ou seja, em vez de ajustar um único polinômio de alto grau a todos os valores de uma vez, a interpolação de spline ajusta polinômios de baixo grau a pequenos subconjuntos dos valores, por exemplo, ajustando nove polinômios cúbicos entre cada um dos pares de dez pontos , em vez de ajustar um único polinômio de grau dez a todos eles. A interpolação de spline é geralmente preferida em relação à interpolação polinomial porque o erro de interpolação pode ser reduzido mesmo ao usar polinômios de baixo grau para o spline. A interpolação de spline também evita o problema do fenômeno de Runge , no qual a oscilação pode ocorrer entre pontos ao interpolar usando polinômios de alto grau.

Introdução

Interpolação com splines cúbicos entre oito pontos. Desenhos técnicos desenhados à mão para construção naval são um exemplo histórico de interpolação de spline; os desenhos foram construídos com réguas flexíveis que foram dobradas para seguir pontos pré-definidos.

Originalmente, spline era um termo para réguas elásticas que eram dobradas para passar por vários pontos predefinidos, ou nós . Estes foram usados ​​para fazer desenhos técnicos de construção naval e de construção manual, conforme ilustrado na figura.

Queremos modelar tipos semelhantes de curvas usando um conjunto de equações matemáticas, com um polinômio para cada par de nós e , onde . Portanto, haverá polinômios e nós: o primeiro polinômio começa em e o último polinômio termina em . ${\ displaystyle y = q_ {i} (x)}$${\ displaystyle (x_ {i-1}, y_ {i-1})}$${\ displaystyle (x_ {i}, y_ {i})}$${\ displaystyle i = 1,2, \ dots, n}$${\ displaystyle n}$${\ displaystyle n + 1}$${\ displaystyle (x_ {0}, y_ {0})}$${\ displaystyle (x_ {n}, y_ {n})}$

A curvatura de qualquer curva é definida como ${\ displaystyle y = f (x)}$

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

Para fazer com que o spline tome uma forma que minimize a dobra (sob a restrição de passar por todos os nós), definiremos ambos e como contínuo em todos os lugares, inclusive nos nós. Assim, a primeira e a segunda derivadas de cada polinômio sucessivo devem ter valores idênticos nos nós, o que significa que ${\ displaystyle y '}$${\ displaystyle y ''}$

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

Isso só pode ser alcançado se polinômios de grau 3 ou superior - polinômios cúbicos ou superior - forem usados. A abordagem clássica é usar polinômios de exatamente grau 3 - splines cúbicos .

Algoritmo para encontrar a spline cúbica de interpolação

Queremos encontrar cada polinômio dados os pontos de passagem . Para fazer isso, consideraremos apenas uma única peça da curva , que será interpolada de a . Esta peça terá declives e em seus pontos finais. Ou, mais precisamente, ${\ displaystyle q_ {i} (x)}$${\ displaystyle (x_ {0}, y_ {0})}$${\ displaystyle (x_ {n}, y_ {n})}$${\ displaystyle q (x)}$${\ displaystyle (x_ {1}, y_ {1})}$${\ displaystyle (x_ {2}, y_ {2})}$${\ displaystyle k_ {1}}$${\ displaystyle k_ {2}}$

${\ displaystyle q (x_ {1}) = y_ {1},}$

${\ displaystyle q (x_ {2}) = y_ {2},}$

${\ displaystyle q '(x_ {1}) = k_ {1},}$

${\ displaystyle q '(x_ {2}) = k_ {2}.}$

A equação completa pode ser escrita na forma simétrica ${\ displaystyle q (x)}$

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

( 1 )

Onde

${\ 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 )

Mas o que são e ? Para derivar esses valores críticos, devemos considerar que ${\ displaystyle k_ {1}}$${\ displaystyle k_ {2}}$

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

Segue-se então que

${\ 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 + (ab) 3t} {{(x_ {2} -x_ {1})} ^ {2}}}.}$

( 6 )

Definindo t = 0 e t = 1 respectivamente nas equações ( 5 ) e ( 6 ), obtém-se de ( 2 ) que, de fato, as primeiras derivadas q ′ ( x ₁ ) = k ₁ e q ′ ( x ₂ ) = k ₂ , e também derivados secundários

${\ 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 )

Se agora ( x _i , y _i ), i = 0, 1, ..., n são n + 1 pontos, e

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

( 9 )

onde i = 1, 2, ..., n e são n polinômios de terceiro grau interpolando y no intervalo x _{i −1} ≤ x ≤ x _i para i = 1, ..., n tal que q ′ _i ( x _i ) = q ′ _{i +1} ( x _i ) para i = 1, ..., n  - 1, então os n polinômios juntos definem uma função diferenciável no intervalo x ₀ ≤ x ≤ x _n , e ${\ displaystyle t = {\ tfrac {x-x_ {i-1}} {x_ {i} -x_ {i-1}}}}$

${\ 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 )

para i = 1, ..., n , onde

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

( 12 )

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

( 13 )

${\ displaystyle k_ {n} = q_ {n} '(x_ {n}).}$

( 14 )

Se a sequência k ₀ , k ₁ , ..., k _n é tal que, além disso, q ′ ′ _i ( x _i ) = q ′ ′ _{i +1} ( x _i ) vale para i = 1, ... , n  - 1, então a função resultante terá até mesmo uma segunda derivada contínua.

De ( 7 ), ( 8 ), ( 10 ) e ( 11 ) segue que este é o caso se e somente se

${\ 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}}} \ right) 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}}} \ right)}$

( 15 )

para i = 1, ..., n  - 1. As relações ( 15 ) são n - 1 equações lineares para os n + 1 valores k ₀ , k ₁ , ..., k _n .

Para as réguas elásticas sendo o modelo para a interpolação de spline, tem-se que à esquerda do "nó" mais à esquerda e à direita do "nó" mais à direita a régua pode se mover livremente e, portanto, tomará a forma de uma linha reta com q ′ ′ = 0 . Como q ′ ′ deve ser uma função contínua de x , "splines naturais", além das n - 1 equações lineares ( 15 ) devem ter

${\ 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,}$

ou seja, isso

${\ 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 )

Eventualmente, ( 15 ) junto com ( 16 ) e ( 17 ) constituem n + 1 equações lineares que definem exclusivamente os n + 1 parâmetros k ₀ , k ₁ , ..., k _n .

Existem outras condições finais, "spline fixada", que especifica a inclinação nas extremidades da spline, e a popular "spline não um nó", que requer que a terceira derivada também seja contínua em x ₁ e x _{N -1} pontos. Para a spline "não um nó", as equações adicionais serão:

${\ 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}}} \ right),}$

${\ 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}}} \ right) k_ {n-1} - {\ frac {1} {\ Delta x_ {n} ^ {2}}} k_ {n} = 2 \ left ( {\ frac {\ Delta y_ {n-1}} {\ Delta x_ {n-1} ^ {3}}} - {\ frac {\ Delta y_ {n}} {\ Delta x_ {n} ^ {3 }}}\certo),}$

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

Exemplo

Interpolação com splines cúbicas "naturais" entre três pontos

No caso de três pontos, os valores para são encontrados resolvendo o sistema de equações lineares tridiagonais${\ displaystyle k_ {0}, k_ {1}, k_ {2}}$

${\ 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}}}$

com

${\ 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 \ left ({\ frac {1} {x_ {1} -x_ {0}}} + {\ frac {1} {x_ {2} -x_ {1}}} \ certo),}$

${\ 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 \ left ({\ frac {y_ {1} -y_ {0}} {{(x_ {1} -x_ {0})} ^ {2}}} + {\ frac {y_ {2} -y_ {1}} {{(x_ {2} -x_ {1})} ^ {2}}} \ right),}$

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

Pelos três pontos

${\ displaystyle (-1,0.5), \ (0,0), \ (3,3),}$

um consegue isso

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

e de ( 10 ) e ( 11 ) que

${\ 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 figura, a função spline que consiste nos dois polinômios cúbicos e dada por ( 9 ) é exibida. ${\ displaystyle q_ {1} (x)}$${\ displaystyle q_ {2} (x)}$

Veja também

• Spline cúbico Hermite
• Spline Catmull-Rom centrípeta
• Interpolação de spline discreta
• Interpolação cúbica monótona
• NURBS
• Interpolação multivariada
• Interpolação polinomial
• Spline de suavização
• Ondinha de spline
• Spline de placa fina
• Spline poliarmônica

Código de computador

TinySpline: biblioteca C de código aberto para splines que implementa interpolação de splines cúbicas

SciPy Spline Interpolation: um pacote Python que implementa interpolação

Interpolação cúbica: biblioteca C # de código aberto para interpolação de spline cúbica

Referências

• Schoenberg, Isaac J. (1946). "Contribuições para o Problema de Aproximação de Dados Equidistantes por Funções Analíticas: Parte A. - Sobre o Problema de Suavização ou Graduação. Uma Primeira Classe de Fórmulas de Aproximação Analítica" . Quarterly of Applied Mathematics . 4 (2): 45–99. doi : 10.1090 / qam / 15914 .
• Schoenberg, Isaac J. (1946). "Contribuições para o Problema de Aproximação de Dados Equidistantes por Funções Analíticas: Parte B. - Sobre o Problema de Interpolação Osculatória. Uma Segunda Classe de Fórmulas de Aproximação Analítica" . Quarterly of Applied Mathematics . 4 (2): 112–141. doi : 10.1090 / qam / 16705 .

links externos

• Ferramenta de cálculo e visualização on-line da interpolação Cubic Spline (com código-fonte JavaScript)
• "Spline interpolation" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Splines cúbicas dinâmicas com JSXGraph
• Aulas teóricas e práticas de interpolação spline
• Artigo que explica passo a passo como a interpolação de spline cúbica é feita, mas apenas para nós equidistantes.
• Receitas numéricas em C, vá para o Capítulo 3, Seção 3-3
• Uma nota sobre splines cúbicos
• Informações sobre interpolação de spline (incluindo código em Fortran 77)