el problema de interpolación racional y el algoritmo de ... · el problema de interpolación...
TRANSCRIPT
![Page 1: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/1.jpg)
El Problema de Interpolación Racional y elAlgoritmo de Euclides
Carlos D’Andrea
Buenos Aires 25/04/19
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 2: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/2.jpg)
Una que sepamos todos...
Joseph-Louis Lagrange (1736–1813)
Dados (x1, y1), . . . , (xN , yN) ∈ K2
calcula P ∈ K[x ] de grado mínimotal queP(xi) = yi , i = 1, . . . ,N
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 3: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/3.jpg)
Una que sepamos todos...
Joseph-Louis Lagrange (1736–1813)
Dados (x1, y1), . . . , (xN , yN) ∈ K2
calcula P ∈ K[x ] de grado mínimotal queP(xi) = yi , i = 1, . . . ,N
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 4: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/4.jpg)
Una que sepamos todos...
Joseph-Louis Lagrange (1736–1813)
Dados (x1, y1), . . . , (xN , yN) ∈ K2
calcula P ∈ K[x ]
de grado mínimotal queP(xi) = yi , i = 1, . . . ,N
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 5: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/5.jpg)
Una que sepamos todos...
Joseph-Louis Lagrange (1736–1813)
Dados (x1, y1), . . . , (xN , yN) ∈ K2
calcula P ∈ K[x ] de grado mínimo
tal queP(xi) = yi , i = 1, . . . ,N
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 6: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/6.jpg)
Una que sepamos todos...
Joseph-Louis Lagrange (1736–1813)
Dados (x1, y1), . . . , (xN , yN) ∈ K2
calcula P ∈ K[x ] de grado mínimotal queP(xi) = yi , i = 1, . . . ,N
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 7: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/7.jpg)
La solución “fácil”
1 x1 x2
1 . . . xN−11
1 x2 x22 . . . xN−1
2... ... ... . . ....
1 xN x2N . . . xN−1
N
a0
...aN−1
=
y1...yN
P =N−1∑j=0
ajxj =
N∑j=1
yj
∏i 6=j
x − xixj − xi
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 8: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/8.jpg)
La solución “fácil”
1 x1 x2
1 . . . xN−11
1 x2 x22 . . . xN−1
2... ... ... . . ....
1 xN x2N . . . xN−1
N
a0
...aN−1
=
y1...yN
P =N−1∑j=0
ajxj =
N∑j=1
yj
∏i 6=j
x − xixj − xi
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 9: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/9.jpg)
La solución “fácil”
1 x1 x2
1 . . . xN−11
1 x2 x22 . . . xN−1
2... ... ... . . ....
1 xN x2N . . . xN−1
N
a0
...aN−1
=
y1...yN
P =N−1∑j=0
ajxj
=N∑j=1
yj
∏i 6=j
x − xixj − xi
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 10: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/10.jpg)
La solución “fácil”
1 x1 x2
1 . . . xN−11
1 x2 x22 . . . xN−1
2... ... ... . . ....
1 xN x2N . . . xN−1
N
a0
...aN−1
=
y1...yN
P =N−1∑j=0
ajxj =
N∑j=1
yj
∏i 6=j
x − xixj − xi
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 11: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/11.jpg)
Interpolación “con multiplicidades”
Charles Hermite (1822–1901)
Dados x1, . . . , xL,y10, . . . , y1N1−1, . . . , yL0, . . . , yLNL−1
calcular P ∈ K[x ] de grado mínimotal que P (j)(xi) = yij
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 12: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/12.jpg)
Interpolación “con multiplicidades”
Charles Hermite (1822–1901)
Dados x1, . . . , xL,y10, . . . , y1N1−1, . . . , yL0, . . . , yLNL−1
calcular P ∈ K[x ] de grado mínimotal que P (j)(xi) = yij
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 13: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/13.jpg)
Interpolación “con multiplicidades”
Charles Hermite (1822–1901)
Dados x1, . . . , xL,y10, . . . , y1N1−1, . . . , yL0, . . . , yLNL−1
calcular P ∈ K[x ] de grado mínimotal que P (j)(xi) = yij
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 14: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/14.jpg)
¿Cómo se resuelve esto?
1 x1 x2
1 . . . xN−11
0 1 2x1 . . . (N − 1)xN−21
......
... . . ....
0 0 0 . . . ∗xN−NL−1L
a0
...aN−1
=
y10...
yLNL−1
P =N−1∑j=0
ajxj =
L∑j=0
Pj(x)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 15: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/15.jpg)
¿Cómo se resuelve esto?
1 x1 x2
1 . . . xN−11
0 1 2x1 . . . (N − 1)xN−21
......
... . . ....
0 0 0 . . . ∗xN−NL−1L
a0
...aN−1
=
y10...
yLNL−1
P =N−1∑j=0
ajxj =
L∑j=0
Pj(x)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 16: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/16.jpg)
¿Cómo se resuelve esto?
1 x1 x2
1 . . . xN−11
0 1 2x1 . . . (N − 1)xN−21
......
... . . ....
0 0 0 . . . ∗xN−NL−1L
a0
...aN−1
=
y10...
yLNL−1
P =N−1∑j=0
ajxj
=L∑
j=0
Pj(x)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 17: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/17.jpg)
¿Cómo se resuelve esto?
1 x1 x2
1 . . . xN−11
0 1 2x1 . . . (N − 1)xN−21
......
... . . ....
0 0 0 . . . ∗xN−NL−1L
a0
...aN−1
=
y10...
yLNL−1
P =N−1∑j=0
ajxj =
L∑j=0
Pj(x)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 18: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/18.jpg)
Diferencias Divididas
P [x1, x2] =y2−y1x2−x1
P [x1, x2, x3] =P[x2,x3]−P[x1,x2]
x3−x1. . .
P = y1 + (x − x1)P [x1, x2]+(x − x1)(x − x2)P [x1, x2, x3]+ . . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 19: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/19.jpg)
Diferencias Divididas
P [x1, x2] =y2−y1x2−x1
P [x1, x2, x3] =P[x2,x3]−P[x1,x2]
x3−x1. . .
P = y1 + (x − x1)P [x1, x2]+(x − x1)(x − x2)P [x1, x2, x3]+ . . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 20: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/20.jpg)
Diferencias Divididas
P [x1, x2] =y2−y1x2−x1
P [x1, x2, x3] =P[x2,x3]−P[x1,x2]
x3−x1
. . .
P = y1 + (x − x1)P [x1, x2]+(x − x1)(x − x2)P [x1, x2, x3]+ . . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 21: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/21.jpg)
Diferencias Divididas
P [x1, x2] =y2−y1x2−x1
P [x1, x2, x3] =P[x2,x3]−P[x1,x2]
x3−x1. . .
P = y1 + (x − x1)P [x1, x2]+(x − x1)(x − x2)P [x1, x2, x3]+ . . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 22: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/22.jpg)
Diferencias Divididas
P [x1, x2] =y2−y1x2−x1
P [x1, x2, x3] =P[x2,x3]−P[x1,x2]
x3−x1. . .
P = y1 + (x − x1)P [x1, x2]+(x − x1)(x − x2)P [x1, x2, x3]+ . . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 23: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/23.jpg)
Teorema Chino del Resto
Si P1, . . . ,PL ∈ K[x ] son coprimos dos a dos,entonces para Q1, . . . ,QL ∈ K[x ] cualesquiera, hay
solución única del sistemaX ≡ Q1 modP1
X ≡ Q2 modP2...X ≡ QL modPL
de grado menor que deg(P1 . . .PL)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 24: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/24.jpg)
Teorema Chino del Resto
Si P1, . . . ,PL ∈ K[x ] son coprimos dos a dos,entonces para Q1, . . . ,QL ∈ K[x ] cualesquiera, hay
solución única del sistemaX ≡ Q1 modP1
X ≡ Q2 modP2...X ≡ QL modPL
de grado menor que deg(P1 . . .PL)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 25: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/25.jpg)
La solución es constructiva
Euclides (-325 -265)
R1P1 + R2P2 = 1
X = Q2R1P1 + Q1R2P2
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 26: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/26.jpg)
La solución es constructiva
Euclides (-325 -265)
R1P1 + R2P2 = 1
X = Q2R1P1 + Q1R2P2
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 27: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/27.jpg)
La solución es constructiva
Euclides (-325 -265)
R1P1 + R2P2 = 1
X = Q2R1P1 + Q1R2P2
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 28: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/28.jpg)
Aplicación
Sin multiplicidades
1 =∑N
j=1
(∏i 6=j
x−xixj−xi
)≡∏
i 6=jx−xixj−xi mod (x − xj)
P ≡ yj ≡ yj(∏
i 6=jx−xixj−xi
)mod x − xj
Con multiplicidades1 =
∑Lj=1 Qj , 1 ≡ Qj mod (x − xj)
Nj
P ≡(yj ,0+yj ,1(x−xj)+yj ,2(x−xj)2+. . .)Qj mod (x−xj)Nj
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 29: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/29.jpg)
Aplicación
Sin multiplicidades
1 =∑N
j=1
(∏i 6=j
x−xixj−xi
)
≡∏
i 6=jx−xixj−xi mod (x − xj)
P ≡ yj ≡ yj(∏
i 6=jx−xixj−xi
)mod x − xj
Con multiplicidades1 =
∑Lj=1 Qj , 1 ≡ Qj mod (x − xj)
Nj
P ≡(yj ,0+yj ,1(x−xj)+yj ,2(x−xj)2+. . .)Qj mod (x−xj)Nj
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 30: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/30.jpg)
Aplicación
Sin multiplicidades
1 =∑N
j=1
(∏i 6=j
x−xixj−xi
)≡∏
i 6=jx−xixj−xi mod (x − xj)
P ≡ yj ≡ yj(∏
i 6=jx−xixj−xi
)mod x − xj
Con multiplicidades1 =
∑Lj=1 Qj , 1 ≡ Qj mod (x − xj)
Nj
P ≡(yj ,0+yj ,1(x−xj)+yj ,2(x−xj)2+. . .)Qj mod (x−xj)Nj
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 31: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/31.jpg)
Aplicación
Sin multiplicidades
1 =∑N
j=1
(∏i 6=j
x−xixj−xi
)≡∏
i 6=jx−xixj−xi mod (x − xj)
P ≡ yj
≡ yj(∏
i 6=jx−xixj−xi
)mod x − xj
Con multiplicidades1 =
∑Lj=1 Qj , 1 ≡ Qj mod (x − xj)
Nj
P ≡(yj ,0+yj ,1(x−xj)+yj ,2(x−xj)2+. . .)Qj mod (x−xj)Nj
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 32: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/32.jpg)
Aplicación
Sin multiplicidades
1 =∑N
j=1
(∏i 6=j
x−xixj−xi
)≡∏
i 6=jx−xixj−xi mod (x − xj)
P ≡ yj ≡ yj(∏
i 6=jx−xixj−xi
)mod x − xj
Con multiplicidades1 =
∑Lj=1 Qj , 1 ≡ Qj mod (x − xj)
Nj
P ≡(yj ,0+yj ,1(x−xj)+yj ,2(x−xj)2+. . .)Qj mod (x−xj)Nj
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 33: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/33.jpg)
Aplicación
Sin multiplicidades
1 =∑N
j=1
(∏i 6=j
x−xixj−xi
)≡∏
i 6=jx−xixj−xi mod (x − xj)
P ≡ yj ≡ yj(∏
i 6=jx−xixj−xi
)mod x − xj
Con multiplicidades1 =
∑Lj=1 Qj , 1 ≡ Qj mod (x − xj)
Nj
P ≡(yj ,0+yj ,1(x−xj)+yj ,2(x−xj)2+. . .)Qj mod (x−xj)Nj
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 34: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/34.jpg)
Aplicación
Sin multiplicidades
1 =∑N
j=1
(∏i 6=j
x−xixj−xi
)≡∏
i 6=jx−xixj−xi mod (x − xj)
P ≡ yj ≡ yj(∏
i 6=jx−xixj−xi
)mod x − xj
Con multiplicidades1 =
∑Lj=1 Qj , 1 ≡ Qj mod (x − xj)
Nj
P ≡(yj ,0+yj ,1(x−xj)+yj ,2(x−xj)2+. . .)Qj mod (x−xj)Nj
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 35: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/35.jpg)
“Tiempo” de cálculo
Álgebra Lineal O(N3)
Teorema Chino del Resto (Hermite)Diferencias Divididas
O(N log2(N))
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 36: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/36.jpg)
“Tiempo” de cálculo
Álgebra Lineal O(N3)
Teorema Chino del Resto (Hermite)
Diferencias Divididas
O(N log2(N))
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 37: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/37.jpg)
“Tiempo” de cálculo
Álgebra Lineal O(N3)
Teorema Chino del Resto (Hermite)Diferencias Divididas
O(N log2(N))
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 38: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/38.jpg)
“Tiempo” de cálculo
Álgebra Lineal O(N3)
Teorema Chino del Resto (Hermite)Diferencias Divididas
O(N log2(N))
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 39: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/39.jpg)
Interpolación Racional
Agustin-Louis Cauchy (1789–1857)
Dados x1, . . . , xL,y10, . . . , y1N1−1, . . . , yL0, . . . , yLNL−1
calcular R = AB ∈ K(x) tal que
R (j)(xi) = yij de grado mínimo
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 40: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/40.jpg)
Interpolación Racional
Agustin-Louis Cauchy (1789–1857)
Dados x1, . . . , xL,y10, . . . , y1N1−1, . . . , yL0, . . . , yLNL−1
calcular R = AB ∈ K(x) tal que
R (j)(xi) = yij de grado mínimo
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 41: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/41.jpg)
Interpolación Racional
Agustin-Louis Cauchy (1789–1857)
Dados x1, . . . , xL,y10, . . . , y1N1−1, . . . , yL0, . . . , yLNL−1
calcular R = AB ∈ K(x) tal que
R (j)(xi) = yij
de grado mínimo
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 42: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/42.jpg)
Interpolación Racional
Agustin-Louis Cauchy (1789–1857)
Dados x1, . . . , xL,y10, . . . , y1N1−1, . . . , yL0, . . . , yLNL−1
calcular R = AB ∈ K(x) tal que
R (j)(xi) = yij de grado mínimoCarlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 43: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/43.jpg)
¿“grado” de una función racional?
degmax
(A
B
)= max{deg(A), deg(B)}
degsum
(A
B
)= deg(A) + deg(B)
. . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 44: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/44.jpg)
¿“grado” de una función racional?
degmax
(A
B
)= max{deg(A), deg(B)}
degsum
(A
B
)= deg(A) + deg(B)
. . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 45: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/45.jpg)
¿“grado” de una función racional?
degmax
(A
B
)= max{deg(A), deg(B)}
degsum
(A
B
)= deg(A) + deg(B)
. . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 46: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/46.jpg)
¿“grado” de una función racional?
degmax
(A
B
)= max{deg(A), deg(B)}
degsum
(A
B
)= deg(A) + deg(B)
. . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 47: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/47.jpg)
Ejemplo 1
x1 = 0 y1,0 = −2x2 = 2 y2,0 = 6x3 = −1 y3,0 = −3x3 = −1 y3,1 = 3
degmax = 2−2− 3λx2
−x2
3 + 1− λxλ 6= −1
6,−23
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 48: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/48.jpg)
Ejemplo 1
x1 = 0 y1,0 = −2x2 = 2 y2,0 = 6x3 = −1 y3,0 = −3x3 = −1 y3,1 = 3
degmax = 2
−2− 3λx2
−x2
3 + 1− λxλ 6= −1
6,−23
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 49: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/49.jpg)
Ejemplo 1
x1 = 0 y1,0 = −2x2 = 2 y2,0 = 6x3 = −1 y3,0 = −3x3 = −1 y3,1 = 3
degmax = 2−2− 3λx2
−x2
3 + 1− λxλ 6= −1
6,−23
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 50: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/50.jpg)
Ejemplo 2
x1 = 1 y1 = 1x2 = −1 y2 = 1x3 = 2 y3 = −14x4 = −2 y4 = −14x5 = 3 y5 = 1x6 = −3 y6 = 1
degsum = 4 x4 − 10x2 + 104
x4 − 2x2 + 3
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 51: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/51.jpg)
Ejemplo 2
x1 = 1 y1 = 1x2 = −1 y2 = 1x3 = 2 y3 = −14x4 = −2 y4 = −14x5 = 3 y5 = 1x6 = −3 y6 = 1
degsum = 4
x4 − 10x2 + 104
x4 − 2x2 + 3
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 52: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/52.jpg)
Ejemplo 2
x1 = 1 y1 = 1x2 = −1 y2 = 1x3 = 2 y3 = −14x4 = −2 y4 = −14x5 = 3 y5 = 1x6 = −3 y6 = 1
degsum = 4 x4 − 10x2 + 10
4x4 − 2x2 + 3
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 53: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/53.jpg)
Ejemplo 2
x1 = 1 y1 = 1x2 = −1 y2 = 1x3 = 2 y3 = −14x4 = −2 y4 = −14x5 = 3 y5 = 1x6 = −3 y6 = 1
degsum = 4 x4 − 10x2 + 104
x4 − 2x2 + 3Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 54: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/54.jpg)
Preguntas
¿Cómo se calculan degmax ydegsum?¿Cuántas soluciones “óptimas” hay?¿Se pueden “parametrizar” todaslas soluciones del problema deinterpolación?
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 55: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/55.jpg)
Preguntas
¿Cómo se calculan degmax ydegsum?
¿Cuántas soluciones “óptimas” hay?¿Se pueden “parametrizar” todaslas soluciones del problema deinterpolación?
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 56: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/56.jpg)
Preguntas
¿Cómo se calculan degmax ydegsum?¿Cuántas soluciones “óptimas” hay?
¿Se pueden “parametrizar” todaslas soluciones del problema deinterpolación?
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 57: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/57.jpg)
Preguntas
¿Cómo se calculan degmax ydegsum?¿Cuántas soluciones “óptimas” hay?¿Se pueden “parametrizar” todaslas soluciones del problema deinterpolación?
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 58: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/58.jpg)
Sub-Problema
Fijado 0 ≤ n ≤ N − 1 calcularA ∈ K[x ]≤n, B ∈ K[x ]≤N−n−1 talesque R = A
B resuelve el problema deinterpolación
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 59: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/59.jpg)
Sub-Problema
Fijado 0 ≤ n ≤ N − 1
calcularA ∈ K[x ]≤n, B ∈ K[x ]≤N−n−1 talesque R = A
B resuelve el problema deinterpolación
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 60: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/60.jpg)
Sub-Problema
Fijado 0 ≤ n ≤ N − 1 calcularA ∈ K[x ]≤n, B ∈ K[x ]≤N−n−1
talesque R = A
B resuelve el problema deinterpolación
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 61: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/61.jpg)
Sub-Problema
Fijado 0 ≤ n ≤ N − 1 calcularA ∈ K[x ]≤n, B ∈ K[x ]≤N−n−1 talesque R = A
B resuelve el problema deinterpolación
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 62: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/62.jpg)
“Problema” con el Sub-Problema
No siempre tiene solución!
N = 3, n = 1, x1 = 1, x2 = 2y1,0 = 1, y1,1 = 0, y2,0 = 0
������a0+a1x
b0+b1x
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 63: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/63.jpg)
“Problema” con el Sub-Problema
No siempre tiene solución!
N = 3, n = 1, x1 = 1, x2 = 2y1,0 = 1, y1,1 = 0, y2,0 = 0
������a0+a1x
b0+b1x
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 64: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/64.jpg)
“Problema” con el Sub-Problema
No siempre tiene solución!
N = 3, n = 1, x1 = 1, x2 = 2y1,0 = 1, y1,1 = 0, y2,0 = 0
������a0+a1x
b0+b1x
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 65: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/65.jpg)
“Problema” con el Sub-Problema
No siempre tiene solución!
N = 3, n = 1, x1 = 1, x2 = 2y1,0 = 1, y1,1 = 0, y2,0 = 0
������a0+a1x
b0+b1x
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 66: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/66.jpg)
El problema es el denominador
Se necesita B(xi) 6= 0∀i = 0, . . . , LPara datos “genéricos”, hay una única
soluciónThe set of unattainable points for the Rational
Hermite Interpolation ProblemCortadellas-D-Montoro
Linear Algebra Appl (2018)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 67: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/67.jpg)
El problema es el denominador
Se necesita B(xi) 6= 0∀i = 0, . . . , L
Para datos “genéricos”, hay una únicasolución
The set of unattainable points for the RationalHermite Interpolation Problem
Cortadellas-D-MontoroLinear Algebra Appl (2018)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 68: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/68.jpg)
El problema es el denominador
Se necesita B(xi) 6= 0∀i = 0, . . . , LPara datos “genéricos”, hay una única
solución
The set of unattainable points for the RationalHermite Interpolation Problem
Cortadellas-D-MontoroLinear Algebra Appl (2018)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 69: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/69.jpg)
El problema es el denominador
Se necesita B(xi) 6= 0∀i = 0, . . . , LPara datos “genéricos”, hay una única
soluciónThe set of unattainable points for the Rational
Hermite Interpolation ProblemCortadellas-D-Montoro
Linear Algebra Appl (2018)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 70: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/70.jpg)
El problema débil
Dados xi , yij calcularA ∈ K[x ]≤n, B ∈ K[x ]≤N−n−1 tales
que A(xi) = yiB(xi)
A(j)(xi) =
j∑s=0
(j)syisB(j−s)(xi)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 71: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/71.jpg)
El problema débil
Dados xi , yij
calcularA ∈ K[x ]≤n, B ∈ K[x ]≤N−n−1 tales
que A(xi) = yiB(xi)
A(j)(xi) =
j∑s=0
(j)syisB(j−s)(xi)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 72: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/72.jpg)
El problema débil
Dados xi , yij calcularA ∈ K[x ]≤n, B ∈ K[x ]≤N−n−1
talesque A(xi) = yiB(xi)
A(j)(xi) =
j∑s=0
(j)syisB(j−s)(xi)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 73: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/73.jpg)
El problema débil
Dados xi , yij calcularA ∈ K[x ]≤n, B ∈ K[x ]≤N−n−1 tales
que A(xi) = yiB(xi)
A(j)(xi) =
j∑s=0
(j)syisB(j−s)(xi)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 74: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/74.jpg)
El problema débil
Dados xi , yij calcularA ∈ K[x ]≤n, B ∈ K[x ]≤N−n−1 tales
que A(xi) = yiB(xi)
A(j)(xi) =
j∑s=0
(j)syisB(j−s)(xi)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 75: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/75.jpg)
Problema de Álgebra Lineal!!
El problema débil siempre se puederesolverLa solución es “única”El denominador de “la solución” nose anula en ningún xi ’s ⇐⇒ elsub-problema tiene solución
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 76: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/76.jpg)
Problema de Álgebra Lineal!!
El problema débil siempre se puederesolver
La solución es “única”El denominador de “la solución” nose anula en ningún xi ’s ⇐⇒ elsub-problema tiene solución
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 77: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/77.jpg)
Problema de Álgebra Lineal!!
El problema débil siempre se puederesolverLa solución es “única”
El denominador de “la solución” nose anula en ningún xi ’s ⇐⇒ elsub-problema tiene solución
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 78: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/78.jpg)
Problema de Álgebra Lineal!!
El problema débil siempre se puederesolverLa solución es “única”El denominador de “la solución” nose anula en ningún xi ’s ⇐⇒ elsub-problema tiene solución
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 79: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/79.jpg)
Métodos de resolución
Álgebra LinealFuncionesSimétricas/SubresultantesAlgoritmo de EuclidesCoordenadas Baricéntricas“Método de Jacobi” (Residuos). . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 80: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/80.jpg)
Métodos de resolución
Álgebra Lineal
FuncionesSimétricas/SubresultantesAlgoritmo de EuclidesCoordenadas Baricéntricas“Método de Jacobi” (Residuos). . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 81: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/81.jpg)
Métodos de resolución
Álgebra LinealFuncionesSimétricas/Subresultantes
Algoritmo de EuclidesCoordenadas Baricéntricas“Método de Jacobi” (Residuos). . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 82: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/82.jpg)
Métodos de resolución
Álgebra LinealFuncionesSimétricas/SubresultantesAlgoritmo de Euclides
Coordenadas Baricéntricas“Método de Jacobi” (Residuos). . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 83: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/83.jpg)
Métodos de resolución
Álgebra LinealFuncionesSimétricas/SubresultantesAlgoritmo de EuclidesCoordenadas Baricéntricas
“Método de Jacobi” (Residuos). . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 84: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/84.jpg)
Métodos de resolución
Álgebra LinealFuncionesSimétricas/SubresultantesAlgoritmo de EuclidesCoordenadas Baricéntricas“Método de Jacobi” (Residuos)
. . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 85: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/85.jpg)
Métodos de resolución
Álgebra LinealFuncionesSimétricas/SubresultantesAlgoritmo de EuclidesCoordenadas Baricéntricas“Método de Jacobi” (Residuos). . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 86: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/86.jpg)
Algoritmo de Euclides
f :=∏L
i=1(x − xi)Ni
g ∈ K[x ]≤N−1, g(j)(xi) = yij
γ(`)f + β(`)g = α(`), ` = 1, . . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 87: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/87.jpg)
Algoritmo de Euclides
f :=∏L
i=1(x − xi)Ni
g ∈ K[x ]≤N−1, g(j)(xi) = yij
γ(`)f + β(`)g = α(`), ` = 1, . . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 88: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/88.jpg)
Algoritmo de Euclides
f :=∏L
i=1(x − xi)Ni
g ∈ K[x ]≤N−1, g(j)(xi) = yij
γ(`)f + β(`)g = α(`), ` = 1, . . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 89: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/89.jpg)
Algoritmo de Euclides
f :=∏L
i=1(x − xi)Ni
g ∈ K[x ]≤N−1, g(j)(xi) = yij
γ(`)f + β(`)g = α(`), ` = 1, . . .
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 90: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/90.jpg)
Algoritmo de Euclides
f :=∏L
i=0(x − xi)Ni
g ∈ K[x ]≤N−1, g(j)(xi) = yij
γ(`)`−1f + β
(`)` g = α
(`)N−1−`, ` = 1, . . .
` = N − n − 1, A = α(`), B = β(`)
es “la” solución débil
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 91: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/91.jpg)
Algoritmo de Euclides
f :=∏L
i=0(x − xi)Ni
g ∈ K[x ]≤N−1, g(j)(xi) = yij
γ(`)`−1f + β
(`)` g = α
(`)N−1−`, ` = 1, . . .
` = N − n − 1, A = α(`), B = β(`)
es “la” solución débil
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 92: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/92.jpg)
Pero...
podría ocurrir α(`) = β(`) = 0 !
Aun así el ` más próximo a N − n− 1da la solución débil...
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 93: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/93.jpg)
Pero...
podría ocurrir α(`) = β(`) = 0 !
Aun así el ` más próximo a N − n− 1da la solución débil...
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 94: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/94.jpg)
Pero...
podría ocurrir α(`) = β(`) = 0 !
Aun así el ` más próximo a N − n− 1da la solución débil...
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 95: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/95.jpg)
Coordenadas Baricéntricas
(Schneider - Werner 86)
Cualquier elección de a1, . . . , aN en
R =
∑Ni=1
aiyi(x−xi )∑N
i=1ai
(x−xi )
da una solución del problema débilProblema fuerte ⇐⇒ ai 6= 0 ∀i
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 96: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/96.jpg)
Coordenadas Baricéntricas
(Schneider - Werner 86)
Cualquier elección de a1, . . . , aN en
R =
∑Ni=1
aiyi(x−xi )∑N
i=1ai
(x−xi )
da una solución del problema débil
Problema fuerte ⇐⇒ ai 6= 0 ∀i
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 97: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/97.jpg)
Coordenadas Baricéntricas
(Schneider - Werner 86)
Cualquier elección de a1, . . . , aN en
R =
∑Ni=1
aiyi(x−xi )∑N
i=1ai
(x−xi )
da una solución del problema débilProblema fuerte ⇐⇒ ai 6= 0 ∀i
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 98: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/98.jpg)
Método de Jacobi (Residuos)
(Egecioglu-Koc 89)
Bézout: C f + B g = A
Pasamos a xkC + xk Bf g = xkAf Si
k + deg(A) ≤ N − 2, Res∞(xkAf ) = 0
da ecuaciones “separadas” para A y B!
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 99: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/99.jpg)
Método de Jacobi (Residuos)
(Egecioglu-Koc 89)
Bézout: C f + B g = A
Pasamos a xkC + xk Bf g = xkAf Si
k + deg(A) ≤ N − 2, Res∞(xkAf ) = 0
da ecuaciones “separadas” para A y B!
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 100: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/100.jpg)
Método de Jacobi (Residuos)
(Egecioglu-Koc 89)
Bézout: C f + B g = A
Pasamos a xkC + xk Bf g = xkAf
Sik + deg(A) ≤ N − 2, Res∞(x
kAf ) = 0
da ecuaciones “separadas” para A y B!
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 101: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/101.jpg)
Método de Jacobi (Residuos)
(Egecioglu-Koc 89)
Bézout: C f + B g = A
Pasamos a xkC + xk Bf g = xkAf Si
k + deg(A) ≤ N − 2, Res∞(xkAf ) = 0
da ecuaciones “separadas” para A y B!
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 102: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/102.jpg)
Método de Jacobi (Residuos)
(Egecioglu-Koc 89)
Bézout: C f + B g = A
Pasamos a xkC + xk Bf g = xkAf Si
k + deg(A) ≤ N − 2, Res∞(xkAf ) = 0
da ecuaciones “separadas” para A y B!
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 103: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/103.jpg)
Complejidad: Euclides
Cálculo de f , g : O(N log2 N)
Una “línea” del Algoritmo deEuclides:
O(M(N) log(N)) = O(N log2 N)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 104: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/104.jpg)
Complejidad: Euclides
Cálculo de f , g : O(N log2 N)
Una “línea” del Algoritmo deEuclides:
O(M(N) log(N)) = O(N log2 N)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 105: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/105.jpg)
Complejidad: Euclides
Cálculo de f , g : O(N log2 N)
Una “línea” del Algoritmo deEuclides:
O(M(N) log(N))
= O(N log2 N)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 106: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/106.jpg)
Complejidad: Euclides
Cálculo de f , g : O(N log2 N)
Una “línea” del Algoritmo deEuclides:
O(M(N) log(N)) = O(N log2 N)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 107: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/107.jpg)
Complejidad: otros métodos
Álgebra Lineal: O(N3)
Coordenadas Baricéntricas:más estables numéricamente, peroaún así O(N3)
Jacobi: (Cortadellas-D-Montoro)O(n log2(n) + N log(N))
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 108: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/108.jpg)
Complejidad: otros métodos
Álgebra Lineal: O(N3)
Coordenadas Baricéntricas:más estables numéricamente, peroaún así O(N3)
Jacobi: (Cortadellas-D-Montoro)O(n log2(n) + N log(N))
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 109: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/109.jpg)
Complejidad: otros métodos
Álgebra Lineal: O(N3)
Coordenadas Baricéntricas:
más estables numéricamente, peroaún así O(N3)
Jacobi: (Cortadellas-D-Montoro)O(n log2(n) + N log(N))
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 110: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/110.jpg)
Complejidad: otros métodos
Álgebra Lineal: O(N3)
Coordenadas Baricéntricas:más estables numéricamente, peroaún así O(N3)
Jacobi: (Cortadellas-D-Montoro)O(n log2(n) + N log(N))
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 111: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/111.jpg)
Complejidad: otros métodos
Álgebra Lineal: O(N3)
Coordenadas Baricéntricas:más estables numéricamente, peroaún así O(N3)
Jacobi: (Cortadellas-D-Montoro)O(n log2(n) + N log(N))
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 112: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/112.jpg)
¿Se puede mejorar esto?
Problema de Interpolación débill
una “línea” del algoritmo de Euclides
O(M(N) logN) = O(N log2 N)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 113: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/113.jpg)
¿Se puede mejorar esto?
Problema de Interpolación débill
una “línea” del algoritmo de Euclides
O(M(N) logN) = O(N log2 N)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 114: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/114.jpg)
¿Se puede mejorar esto?
Problema de Interpolación débill
una “línea” del algoritmo de Euclides
O(M(N) logN)
= O(N log2 N)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 115: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/115.jpg)
¿Se puede mejorar esto?
Problema de Interpolación débill
una “línea” del algoritmo de Euclides
O(M(N) logN) = O(N log2 N)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 116: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/116.jpg)
Y ya que estamos...
El algoritmo para multiplicar enterosde la escuela tiene complejidad O(N2)
Algoritmo de Karatsuba(1960):O(N1,585)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 117: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/117.jpg)
Y ya que estamos...
El algoritmo para multiplicar enterosde la escuela tiene complejidad O(N2)
Algoritmo de Karatsuba(1960):O(N1,585)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 118: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/118.jpg)
Mejorando...
Toom-Cook (1966):O(N log(2k−1)/ log k), k ≥ 3
Schönhage-Strassen (1971):O(N logN log logN)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 119: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/119.jpg)
Mejorando...
Toom-Cook (1966):O(N log(2k−1)/ log k), k ≥ 3Schönhage-Strassen (1971):O(N logN log logN)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 120: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/120.jpg)
Mejorando....
Fürer’s algorithm (2007):O(N logN 2O(log∗N)))
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 121: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/121.jpg)
Mejorando?
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 122: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/122.jpg)
“We use [the fast Fourier transform] ina much more violent way, use it
several times instead of a single time,and replace even more multiplications
with additions and subtractions”
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 123: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/123.jpg)
¿Y el problema minimal?
Dados x1, . . . , xL,y10, . . . , y1N1−1, . . . , yL0, . . . , yLNL−1
calcular R = AB ∈ K(x) tal que
R (j)(xi) = yij de grado mínimo
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 124: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/124.jpg)
¿Y el problema minimal?
Dados x1, . . . , xL,y10, . . . , y1N1−1, . . . , yL0, . . . , yLNL−1
calcular R = AB ∈ K(x) tal que
R (j)(xi) = yij
de grado mínimo
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 125: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/125.jpg)
¿Y el problema minimal?
Dados x1, . . . , xL,y10, . . . , y1N1−1, . . . , yL0, . . . , yLNL−1
calcular R = AB ∈ K(x) tal que
R (j)(xi) = yij de grado mínimo
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 126: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/126.jpg)
Problema débil (Lagrange)
(Ravi 97)
Todo par (A,B) resuelve el problemadébil ⇐⇒
x − x1 0 . . . 0 1 −y10 x − x2 . . . 0 1 −y2...
......
......
0 0 . . . x − xN 1 −yN
∗...∗AB
= 0
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 127: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/127.jpg)
Problema débil (Lagrange)
(Ravi 97)
Todo par (A,B) resuelve el problemadébil
⇐⇒x − x1 0 . . . 0 1 −y1
0 x − x2 . . . 0 1 −y2...
......
......
0 0 . . . x − xN 1 −yN
∗...∗AB
= 0
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 128: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/128.jpg)
Problema débil (Lagrange)
(Ravi 97)
Todo par (A,B) resuelve el problemadébil ⇐⇒
x − x1 0 . . . 0 1 −y10 x − x2 . . . 0 1 −y2...
......
......
0 0 . . . x − xN 1 −yN
∗...∗AB
= 0
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 129: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/129.jpg)
Hilbert’s Syzygy’s Theorem
El núcleo de esa matriz es libre derango 2Hay dos generadores de gradosµ ≤ N − µµ es el degmax mínimo
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 130: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/130.jpg)
Hilbert’s Syzygy’s Theorem
El núcleo de esa matriz es libre derango 2
Hay dos generadores de gradosµ ≤ N − µµ es el degmax mínimo
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 131: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/131.jpg)
Hilbert’s Syzygy’s Theorem
El núcleo de esa matriz es libre derango 2Hay dos generadores de gradosµ ≤ N − µ
µ es el degmax mínimo
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 132: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/132.jpg)
Hilbert’s Syzygy’s Theorem
El núcleo de esa matriz es libre derango 2Hay dos generadores de gradosµ ≤ N − µµ es el degmax mínimo
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 133: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/133.jpg)
¡No hacen falta las resoluciones!
(Cortadellas-D-Montoro)arXiv:1808.02575
µ es el grado de uno de los restosen el AEE más próximos a N
2La “µ-base” son dos filasconsecutivas del AEE
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 134: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/134.jpg)
¡No hacen falta las resoluciones!
(Cortadellas-D-Montoro)arXiv:1808.02575
µ es el grado de uno de los restosen el AEE más próximos a N
2La “µ-base” son dos filasconsecutivas del AEE
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 135: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/135.jpg)
Cálculo de min-degsum
(Cortadellas-D-Montoro)arXiv:1808.02575
min-degsum=
mink{N − deg qk(x), sk(xj) 6= 0∀j}ri(x) = qi+1(x)ri+1(x)+ri+2(x) = f (x)si(x)+g(x)ti(x)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 136: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/136.jpg)
Cálculo de min-degsum
(Cortadellas-D-Montoro)arXiv:1808.02575
min-degsum=
mink{N − deg qk(x), sk(xj) 6= 0∀j}
ri(x) = qi+1(x)ri+1(x)+ri+2(x) = f (x)si(x)+g(x)ti(x)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 137: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/137.jpg)
Cálculo de min-degsum
(Cortadellas-D-Montoro)arXiv:1808.02575
min-degsum=
mink{N − deg qk(x), sk(xj) 6= 0∀j}ri(x) = qi+1(x)ri+1(x)+ri+2(x) = f (x)si(x)+g(x)ti(x)
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 138: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/138.jpg)
Más aún...
(Cortadellas-D-Montoro) arXiv:1808.02575
Todas las soluciones débiles sepueden parametrizar via el AEEEncontrar y describir las solucionesminimales se puede hacerconstructivamente
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 139: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/139.jpg)
Más aún...
(Cortadellas-D-Montoro) arXiv:1808.02575
Todas las soluciones débiles sepueden parametrizar via el AEE
Encontrar y describir las solucionesminimales se puede hacerconstructivamente
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 140: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/140.jpg)
Más aún...
(Cortadellas-D-Montoro) arXiv:1808.02575
Todas las soluciones débiles sepueden parametrizar via el AEEEncontrar y describir las solucionesminimales se puede hacerconstructivamente
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides
![Page 141: El Problema de Interpolación Racional y el Algoritmo de ... · El Problema de Interpolación Racional y el Algoritmo de Euclides. Lasoluciónesconstructiva Euclides (-325 -265) R](https://reader035.vdocumento.com/reader035/viewer/2022062318/5fdb84f7fc6f8f055e15a431/html5/thumbnails/141.jpg)
Gracias
Carlos D’Andrea
El Problema de Interpolación Racional y el Algoritmo de Euclides