= Многочлены
== Производная многочлена
$ f(x) = product_(i = 1)^(n)(x - x_i) $
$ f'(x) = sum_(i = 1)^(n) frac(f(x), x - x_i) = f(x) sum_(i = 1)^(n) frac(1, x - x_i) $
$ f'(x) = f(x) sum_(i = 1)^(n) frac(1, x - x_i) => frac(f'(x), f(x)) = sum_(i = 1)^(n)frac(1, x - x_i) $ 

Если многочлен f(x) имеет корень кратности n, то это значит, что
+ $f(alpha) = 0$
+ $f^((i))(alpha) = 0 "для" forall i in [1,n - 1]$

=== Пример (связь производной с функцией и ее корнями)
$ f(x) = x^2 - 3x + 2 = (x - 2)(x - 1) $
$ f'(x) = f(x) dot frac(1, x - 1) + frac(1, x - 2) = f(x) dot frac(2x - 3, x ^ 2 - 3x + 2) = f(x) dot frac(2x - 3, f(x)) = 2x - 3 $
$ f'(x) = 2x - 3 $

=== Пример (задачи на нахождение суммы)


== Простейшие дроби
Дробь $frac(f, g) in K[t]$ - простейшая, если $g = p^k$, где $p in K[t]$ – неприводимый многочлен и $"deg"(f) < "deg"(g)$.

== Связь разложения на простейшие дроби с интерполяцией
=== Алгоритм, когда все корни первой степени
$ g(x) = (x - a_1) dots (x - a_n) $
$ frac(f(x), g(x)) = sum_(i = 1)^(n) frac(f(a_i), g'(a_i) dot (x - a_i)) $

#pagebreak()

== Алгоритм интерполяции Лагранжа

$ f(x) = product_(i = 1)^(n)(x - x_i) $
$ L(X) = sum_(i = 0)^(n)y_i dot l_(i)(x)  = sum_(i = 0)^(n) y_i dot frac(f(x), f'(x_i) dot (x - x_i)) $
$ l_i(x) = product_(j = 0, j != i)frac(x - x_j, x_i - x_j) $

=== Пример
#columns(2)[

#align(right)[
  $ l_0(x) = frac((x - x_1)(x - x_2)(x - x_3), (x_0 - x_1)(x_0 - x_2)(x_0 - x_3)) = \ = frac((x - 2)(x - 3)(x - 5), -30) $
  $ l_1(x) = frac((x - x_0)(x - x_2)(x - x_3), (x_1 - x_0)(x_1 - x_2)(x_1 - x_3)) = \ = frac((x - 0)(x - 3)(x - 5), 6) $
]

#colbreak()

#table(
  columns: 3,
  [*i*], [*x*], [*y*],
  [0], [0], [0],
  [1], [2], [1],
  [2], [3], [3],
  [3], [5], [2])
]

$ L(x) = y_0 dot l_0(x) + y_1 dot l_1(x) + y_2 dot l_2(x) + y_3 dot l_3(x) = 0 dot l_0(x) + 1 dot l_1(x) + 3 dot l_2(x) + 2 dot l_3(x) $

== Алгоритм интерполяции по Ньютону
$ N = a_0 + a_1 dot (x - x_0) + a_2 dot (x - x_0)(x - x_1) + dots $

Чтобы найти многочлен по точкам, нужно постепенно подставлять значения x, тогда если подставляем $x_i$, то начиная с i будут нули.

=== Пример
#columns(2)[

#align(right)[
  $ 2 = a_0 + a_1(1 - 1) + a_2(1 - 1)(2 - 1) + dots $
  $ 3 = a_0 + a_1(2 - 1) + a_2 (2 - 1)(2 - 2) + dots $
]

#colbreak()

#table(
  columns: 3,
  [*i*], [*x*], [*y*],
  [0], [1], [3],
  [1], [2], [-10],
  [2], [3], [5])
]

=== Упрощение алгоритма интерполяции Ньюетона при $Delta x = "const"$
Пусть $h = Delta x$, тогда построим табличку, где $Delta^k y_i = Delta^(k - 1)y_(i + 1) - Delta^(k - 1)y_i$, где i - строчка в таблице.

#table(
  columns: 5, align: (center, center, center , center, center), 
  [*i*], [*x*], [*y = $Delta^0$y*], [*$Delta^1$y*], [*$Delta^2$y*],
  [0], [1], [3], [-13], [28],
  [1], [2], [-10], [15], [],
  [2], [3], [5], [], []
)

Тогда коэффициент $a_k = frac(Delta^k y_0, k! dot h^k)$
