>>  <<  Ркв  Ввд  JfC  LJ  Фрз  Слв  Изм  Рзг  !:  Помощь  Словарь

26. Многочлены: Корни из Коэффициентов I (метод Ньютона)

Поскольку многочлены (m;r)&PIR и (c=:CFR (m;r))&p. идентичны, параметры m;r и c являются различными представлениями одной и той-же функции. Каждое представление имеет свои полезные свойства. Например, сложение многочленов проще выполнить, если они представлены коэффициентами, и сложнее, если корнями; нахождение нулей по заданным коэффициентам многочлена сложно, но тривиально, если многочлен ими-же и представлен. Таким образом, полезно иметь функции, выполняющие преобразование между упомянутыми представлениями. CFR работает в одном направлении, обратная задача решается методом последовательных приближений.

Для дифференцируемой функции f , разность (f r)-(f a) в близких точках r и a приближенно равна разности r-a , помноженной на наклон касательной к графику функции f в точке a,f a , тоесть производной f в a . Обратное тоже верно, разность r-a можно приблизить величиной ((f r)-(f a))%f D a, а приближением к r будет a+((f r)-(f a))%f D a .

Если f — многочлен c&p. , а r — один из его корней, тогда f r равняется нулю. Тоесть, если a — приближение к r , формула для r упрощается до a-(f a)%f D a . Это выражение может дать лучшее приближение к r и лежит в основе метода Ньютона, определенного ниже в виде наречия:
   newton=: 1 : '] - x % x D'

   f=: (c=: 12 _10 2)&p.

   f a=: 2.4 
_0.48

   f newton a
1.2

   f 2
0

   f newton ^:0 1 2 3 4 _ a
2.4 1.2 1.75385 1.9594 1.99848 2

   ]a=: (^ - 4:) newton ^: 0 1 2 3 _ a=: 1
1 1.47152 1.38982 1.3863 1.38629

   ^ {: a
4
В частном случае применения метода Ньютона к многочленам, можно определить наречие, работающее непосредственно с коэффициентами и использующее производную многочлена pD вместо универсальной производной D :

   pD=: 1 }. ] * i.@#
   NEWTON=: 1 : '] - x&p. % (pD x)&p.'

   c NEWTON ^:0 1 2 3 4 _ a=: 2.4
2.4 1.2 1.75385 1.9594 1.99848 2
>>  <<  Ркв  Ввд  JfC  LJ  Фрз  Слв  Изм  Рзг  !:  Помощь  Словарь