Составители:
Рубрика:
19) q:=r;
20) r:=t;
21) Q:=R;
22) R:=T;
23) end;
24) exit (q,Q);
{ выход: в q имеется НОД(q, r)}
{ в Q содержится пара [a, b] }
{ такая, что НОД= aq + br }
25) end.
Задание 1. Для более глубокого усвоения алгоритма предлага-
ется его применить для случая q = 12, r = 10.
Первое значение, вырабатываемое этим алгоритмом – НОД ис-
ходных чисел q = 12 и r = 10, а второе значение – пара чисел [a, b]
такая, что
НОД(q, r) = aq + br. (∗)
Соотношение (*) называют тождеством Безу.
Задание 2. Применить расширенный алгоритм Евклида к мно-
гочленам
q = 2x
2
+ 4x + 2 и r = x
2
− 1 :
Последовательно получим:
h2x
2
+ 4x + 2 = (x
2
− 1) · 2 + 4x + 4i
При проверке тождества Безу имеем
НОД(q, r) = aq + br (4.1)
4x + 4
?
=
1 · (2x
2
+ 4x + 2) + (−2)(x
2
− 1)
Замечание. Если q и r – многочлены с целыми коэффициента-
ми, то НОД(q, r) – многочлен сцелыми коэффициентами, однако,
промежуточные вычисления могут иметь нецелые коэффициенты
(см. R и T на предпоследнем этапе вычислений).
5. Интерполирование методом Эрмита
88
Страницы
- « первая
- ‹ предыдущая
- …
- 85
- 86
- 87
- 88
- 89
- …
- следующая ›
- последняя »
