#import "../../utils/core.typ": *

== Интерполяция

#th[
    Пусть $K$ --- поле$, space  n in NN: space  x_1, x_2, ..., x_n in K,$ различные между собой. $y_1, y_2, ..., y_n in K$. Тогда $exists! f in K[x]: deg f <= n - 1$ и $f(x_i) = y_i, space i = 1, ..., n$.
]

#proof[

    "Единственность":

    Предположим, что существует два многочлена $f, g in K[x], space deg f <= n - 1, space deg g <= n - 1: space  f(x_i) = g(x_i) = y_i, space i = 1, ..., n$

    Пусть $h = f - g, space deg h <= n - 1, space h(x_i) = 0, space i = 1, ..., n$

    Предположим, $h eq.not 0 ==>$ у $h <= n - 1$ корней, но такого не может быть.

    "Существование":

    *Формула Лагранжа*

    Решим интерполяционную задачу в специальном случае, когда $y_1 = 1, space  y_2 = ... = y_n = 0$.

    Найдем соответствующий многочлен $f_1$.

    $x_1, ..., x_n$ --- корни многочлена $f_1 ==> (x - x_2) divides f_1, ..., (x - x_n) divides f_1 ==>$ 

    $underbrace((x - x_2) (x - x_3) ... (x - x_n), "степени " n - 1) divides f_1 ==> f_1 = c(x - x_2) ... (x - x_n), space c in K$

    $f_1 (x_1) = 1 <==> c (x_1 - x_2) ... (x_1 - x_n) = 1 ==> c = (1)/((x_1 - x_2) ... (x_1 - x_n))$

    Получился многочлен $f_1 = ((x - x_2) ... (x - x_n))/((x_1 - x_2) ... (x_1 - x_n))$

    Аналогичная задача с $y_i = 1, forall_(j eq.not i) space y_j = 0$ имеет решение:

    $f_i = ((x - x_1) ... hat((x - x_i)) ... (x - x_n))/((x_i - x_1) ... hat((x_i - x_i)) ... (x_i - x_n)) = ((x - x_1) ... hat((x - x_i)) ... (x - x_n))/(F'(x_i))$

    Рассмотрим $f = y_1 f_1 + y_2 f_2 + ... + y_n f_n,quad y_1, ..., y_n$ теперь произвольные.

    $deg <= max(deg f_1, ..., deg f_n) = n - 1$

    Получилась такая формула $f(x_i) = y_1 underbrace(f_1 (x_i), 0) + y_2 underbrace(f_2 (x_i), 0) + ... + y_i underbrace(f_i (x_i), 1) + ... + y_n underbrace(f_n (x_i), 0) = y_i$
]

#notice[
    Про связь с производной

    $F = (x - x_1) ... (x - x_n)$

    $F' = limits(sum)_(i = 1)^n (x - x_1) ... hat((x - x_i)) ... (x - x_n)$

    $F'(x_j) = limits(sum)_(i = 1)^n (x_j - x_1) ... hat((x_j - x_i)) ... (x_j - x_n) = (x_j - x_1) ... hat((x_j - x_j)) ... (x_j - x_n)$
]

*<NAME>*

Рассмотрим интерполяционную задачу и предположим, что мы уже нашли $f_((n - 1)) in K[x]$, такой что $f_((n - 1))$ решение интерполяционной задачи $(x_1, ..., x_(n - 1); y_1, ..., y_(n - 1))$, то есть

$deg f_((n - 1)) <= n - 2$ и $f_((n - 1))(x_i) = y_i, space i = 1, ..., n - 1$

Пусть $f$ решение интерполяционной задачи

$f = f_((n - 1)) + g, space  g = ?$

$f(x_i) = y_i = f_((n - 1)) (x_i), space  i = 1, ..., n - 1$

$g = f - f_((n - 1)), space  g(x_1) = ... = g(x_(n - 1)) = 0$

$deg g <= n - 1 ==> g = c (x - x_1) ... (x - x_(n - 1))$

$g(x_n) = f(x_n) - f_((n - 1)) (x_n) = y_n - f_((n - 1)) (x_n) ==>$ отсюда находится $c$