Главная Промышленная автоматика.

8.7. ИНТЕРПОЛЯЦИЯ ПОЛИНОМОВ

полинома степени -1 в k точках. Полином р(л:)=Х1 Pi{x) можно

получить за время Од (Л log* k), если сначала вычислить рори РгРз, затем poPiPiPa, PipiPiP-i, ... и т. д. Производную полинома р{х) можно найти за Оа() шагов. Вычисление значений производной занимает Од (Л log* k) времени в силу следствия 2 теоремы 8.10. Теорема вытекает теперь из следствия теоремы 8.13 при d=l. □

Пример 8.7. Проинтерполируем полином по следующим парам (точка, значение): (1, 2); (2, 7); (3, 4); (4, 8). Здесь аг=г+1 для 0i<4, «0=2, «1=7, «2=4 и «3=8, Тогда pt {х)=х-i-1, а полином

p{x)r[pi{x) равен л:*-10 л;з+35л:*-50л:+24. Далее, dp{x)ldx=

=4л:-30л:*+70л:-50, и в точках 1, 2, 3, 4 этот полином принимает соответственно значения -6, 2, -2, 6. Таким образом, do, di, d2 и da равны соответственно-V,, Va. -V2 и Ve- С помощью быстрого китайского алгоритма 8.5, переделанного для полиномов, получаем

«о, = d,«„p, +d,«jPo = ( -1) (2) (;t-2) + (1) (7) (д:-1) =

6 6 •

Sai = daUaP8 + 3«8P2 = = -1- + 4

(4) ( 4)+ (8) (-3)

и затем

= {т-т) (-7-12) + (-1 + 4) (д:-и{х) = х-19х + Щх-26.

-За:+ 2), □

Как отмечалось в гл. 7, такие арифметические операции над полиномами, как сложение и умножение, можно выполнять, вычисляя полиномы в п точках, производя над найденными значениями арифметические операции и затем интерполируя полином по полученным в результате значениям. Если на выходе должен быть полином степени не более п-1, то этот способ приведет к правильному ответу.

Метод БПФ именно это и делает в случае, когда в качестве п точек берутся числа и", о)*, . . ., и""*. Здесь алгоритмы вычисления значений и интерполяции оказались особенно простыми благодаря ствойствам степеней числа о) и специального упорядочения их. Однако стоит заметить, что вместо степеней числа о) можно было бы взять любой набор точек. Тогда у нас было бы такое "преобразова-



ние", что на всю задачу (преобразование, вычисления и обратное преобразование) потребовалось бы Од (« log п), а не Од (« log п) времени.

8.8. НАИБОЛЬШИЕ ОБЩИЕ ДЕЛИТЕЛИ И АЛГОРИТМ ЕВКЛИДА

Определение. Пусть Uo и Ci- положительные целые числа. Положительное целое число g называется наибольшим общим делителем чисел Со и а, (его часто обозначают через НОД(ао, Ci)), если

1) g делит Со и Ci,

2) всякий общий делитель чисел Со и а, делит g.

Легко показать, что для положительных целых чисел Со и Ui такое число g единственно. Например, НОД(57, 33)=3.

Алгоритм Евклида для вычисления НОД(ао, fli) состоит в вычислении последовательности остатков Uq, Ci, . . ., а, где Qj, 2 <i<ft,- ненулевой остаток от деления Ut- на Cj-i и а нацело делит Cft-i (т. е. afc+i=0). В этой ситуации НОД(ао, ai)=a.

Пример 8.8. В примере, приведенном выше, ао=57, ai=33, 02=24, аз=9, 04=6 и 05=3. Поэтому /г=5 и НОД (57, 33)=3. □

Теорема 8.15. Алгоритм Евклида правильно находит значение НОД(Оо, oi).

Доказательство. Этот алгоритм вычисляет aj+,=ai-,- -qiUi для l<t<ft, где qi= LOi-i/OjJ. Так как aj+i<ai при tl, то алгоритм, очевидно, заканчивает работу. Кроме того, любой общий делитель чисел Oj-i и Oj делит Oj+i и любой общий делитель чисел Oj и Oj+i делит Oj i. Следовательно, НОД(Оо, Oi)= = НОД (01,02)= . . . =Н0Д(а 1,а. Очевидно, НОД (о-1,0=0, так что теорема доказана. □

Алгоритм Евклида можно расширить так, чтобы он находил не только наибольший общий делитель чисел Оц и Oi, но также и целые числа хну, для которых ОоХ+01г/=НОД (Оо, Oi). Сформулируем этот алгоритм.

Алгоритм 8.6. Расширенный алгоритм Евклида

Вход. Положительные целые числа оо и Oi. Выход. НОД(Оо, Oi) и такие целые числа хну, что aoX-\-aiy= =НОД(Оо, Oi).

Метод. Применяем программу, приведенную на рис. 8.6. □



begin

1. Хо*-1; г/о -0; л:,.-0; z/j-1; i

2. while Of не делит a, i do

begin

3. Я*-Lai.JaiJ;

4. a,+i.-a, i-9»a,;

5. Xii*-x, , - q*Xi;

6. У1+г*-У1-1 - Я*У1:

7. ii + l end;

8. write Of, write л:,-; write t/, end

Рис. 8.6. Расширенный алгоритм Евклида.

Пример 8.9. Если ао=57 и ai=33, то для чисел а,, х,, и получаем значения

Заметим, что 57Х(-4)+ЗЗх7=3. □

Ясно, что алгоритм 8.6 правильно вычисляет НОД(а„, Oi), поскольку очевидно, что числа образуют требуемую последовательность остатков. В следующей лемме описывается важное свойство чисел Xi и yi, вычисляемых алгоритмом 8.6.

Лемма 8.4. В алгоритме 8.6

СоХ,- + ау,- - а,- при ( О.

(8.23)

Доказательство. Равенство (8.23) справедливо для i=0 и 1 = 1 в силу строки 1 алгоритма 8.6. Допустим, что (8.23) справедливо для t-1 и t. Тогда л:(+1=л:, 1-<7л:( в силу строки 5 и t/i+i= =yi-yr-qyi в силу строки 6. Следовательно,

(8.24)





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 [108] 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0023