Главная Промышленная автоматика. ТОЛЬКО выражения вида Р (а, . . . , an)+L {xi.....х, где Р - полином и L - линейная функция, оба с коэффициентами из F. Таким образом, вычисление вектора Afx+y должно включать хотя бы одно активное умножение. Шаг индукции. Допустим, что q>\ и теорема верна для q-\. Пусть С - вычисление вектора Л1х+у. По предположению индукции С содержит не менее 1>1 активных умножений. Пусть / ч- g*h - первое такое умножение. Тогда без потери общности можно считать, что f fe) = (a.. а„)+2сл, (12.4) где Р - полином с коэффициентами из f и все С также принадлежат F. Более того, не умаляя общности, можно считать, что СгфО. Наша стратегия состоит в том, чтобы построить из С и множества выражений Л1х+у новое множество выражений Л1х+у с вычислением С, содержащим на одно активное умножение меньше, чем С. Кроме того, q-\ столбцов матрицы М будут линейно независимы по модулю F. Тогда по предположению индукции С будет содержать не менее q-\ активных умножений, а значит, С - не менее q активных умножений. Конкретно, мы заменим хъС некоторым выражением е, которое сделает g из (12.4) равным 0. Выражение е будет вычислимо без активных умножений. Вычисление С начинается с вычисления выражения е, при этом значение е присваивается формальной переменной xi (она уже больше не будет входной переменной). Остальная часть вычисления С состоит из С, где / заменено на / ч-О. Затем мы покажем, что множество выражений, вычисляемых с помощью С, можно выразить в виде Afx-fy, где q-1 столбцов матрицы М линейно независимы по модулю f Итак, приступим к изложению деталей доказательства. Из (12.4) и допущения сФ заключаем, что g=0, если Xi=-cг Р(а„ ..., а„) + 2 CiXi . (12.5) Правая часть равенства (12.5) и есть выражение е, упоминаемое выше. Вычисление С, получаемое из С описанным выше способом, вычисляет Мх+у, куда вместо Xi подставлено е. Поэтому Мх+у можно записать как + У. а это переписать в виде Г р л - CT1,ClXl 1 = 2 -сгРК. .... а„) + У. (12.6) XpV. Таким образом, первое сла- Рассмотрим первое слагаемое в (12.6). Пусть гп - это г-й столбец матрицы М. Для 2ip положим m,=mi-(Ci/ci)mi. Пусть М- матрица, состоящая из р-1 столбцов, у которой t-й столбец есть ml+i, и пусть \ = [х2, . . ~ гаемое в (12.6) равно М\. Второе слагаемое - вектор с компонентами из F[ai.....а„], ибо элементы матрицы М принадлежат F[au . . . , а„]. Поэтому второе и третье слагаемые в (12.6) можно объединить в новый вектор у с компонентами из F[ai, . . . , flnl- Таким образом, С вычисляет Л1х+у. Из леммы 12.1 непосредственно вытекает, что не менее q-1 столбцов матрицы М линейно независимы по модулю fСледовательно, С содержит не менее q-1 активных умножений, и потому С содержит не менее q активных умножений. □ Приведем два примера применения теоремы 12.2. Пример 12.8. Мы утверждаем, что умножение (rt X р)-матрицы Л на р-мерный вектор v требует rtp умножений элементов. Формально, пусть uij HVj - формальные переменные, l<t<rt, 1</<р. Тогда произведение Av матрицы на вектор имеет вид, показанный на рис. 12.1. Непосредственно применяя теоремы 12.1 и 12.2 к Av, заключаем лишь, что требуется MAX(rt, р) умножений. Однако произведение матрицы на вектор можно также выразить в виде Мх, где в t-й строке матрицы М в столбцах с {{i-1)р+1)-го до (tp)-ro стоят Vi, . . . ,. .,Vp, а в остальных столбцах - нули. Вектор х - это вектор-стол-
Рис. 12.1. Общий вид произведения матрицы на вектор. п строк V, 2 . • • ifp о о • • • о • • • о о • о о • • • о гг • • • 0), • • • о О • .0 0 • • -О О О • • • О • • • у, 2 пр столбцов Рис. 12.2. Эквивалентная форма произведения матрицы на вектор. бец, равный конкатенации строк матрицы А, записанной сверху вниз. М и X изображены на рис. 12.2. Легко показать, что столбцы матрицы М линейно независимы по модулю F". Поэтому в силу теоремы 12.2 любое вычисление для А\ требует не менее пр умножений. □ Пример 12.9. Рассмотрим задачу вычисления полинома п-й степени fljx. Эту задачу можно представить как вычисление произведения матрицы М на вектор х: [1, X, X*, ..., х"\ Элементы матрицы М принадлежат Р[х] и х=«[ао, aj, . . . , а„1. Легко показать, что все столбцы матрицы М, кроме первого, линейно независимы по модулю F. Следовательно, в М содержатся п линейно независимых столбцов, и вычисление произвольного полинома п-й степени требует не менее п умножений. 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.002 |