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

Га О-О b Ь а

(12.3)

Пусть R - поле вещественных чисел. В примере 12.6 было показано, что три строки матрицы в (12.3) линейно независимы по модулю R«, и, следовательно, любое вычисление этих трех выражений над вещественным полем требует трех умножений вещественных чисел. □

*) Для читателей, незнакомых с этим фактом, укажем, что доказательство основной теоремы (нашей леммы 12.1) позволяет доказать и этот более легкий результат.

*) О - это вектор подходящей размерности, состоящий из одних нулей.

на каждом из шагов с умножением. Тогда М\ можно представить в виде линейной функции от ei, . . ., е, и формальных переменных, т. е.

Mx==Ne + l (12.1)

где е - вектор [ви .... ej, а компоненты вектора f представляют собой линейные функции только от Oi, . . . , а„ и Xi, . . . , Хр. Все элементы (гХ5)-матрицы принадлежат полю F.

Теперь допустим, что r>s. Это значит, что строки матрицы линейно зависимы (элементарный факт из линейной алгебры)). Таким образом, существует такой вектор уФО ) из f, что уЛ=0. Умножив (12.1) на у, получим

yMx = yNe + y4 = y4. (12.2)

Из (12.2) видно, что произведение (уШ)х равно yf, т. е. является линейной функцией от формальных переменных. Так как компоненты вектора х- различные формальные переменные, то вектор-строка уШ должна состоять только из элементов поля F, а иначе в у"Л1х нашлось бы слагаемое, состоящее из произведения формальных переменных, и, значит, такое слагаемое было бы и в yf, а это противоречит тому, что f - линейная функция от формальных переменных. Поскольку утО и уЛ1 € Р", то строки матрицы М зависимы по модулю F" вопреки условию. Поэтому sr, и теорема доказана. □

Пример 12.7. В разд. 12.2 мы рассмотрели вычисление трех выражений ас, bd и ad+bc простым рекурсивным алгоритмом умножения целых чисел. Все три умножения можно записать в виде умножения матрицы на вектор, а именно



12.5. НИЖНЯЯ ГРАНИЦА ДЛЯ ЧИСЛА УМНОЖЕНИЙ, СВЯЗАННАЯ С РАНГОМ ПО СТОЛБЦАМ

Теорема, аналогичная теореме 12.1, связанная с рангом по столбцам, верна, но доказывается с большим трудом. Нам понадобится предварительный результат о множествах линейно независимых векторов.

Лемма 12.1. Пусть {vi, . . . , V;} - множество, состоящее из kl т-мерных векторов с компонентами из РЫъ . . . , а„]. Если в {Vjl<j</j} есть подмножество из q векторов, линейно независимых по модулю то для любых элементов Ьг, . . . , Ь,из F множество {V(vJ=v,-f6jVi, 2<t<*} содержит подмножество, состоящее из q-1 векторов, линейно независимых по модулю F".

Доказательство. Перенумеровав при необходимости векторы Vj, Vs, . . . , V;, можно считать, что линейно независимы либо векторы из {vi, Va, . . . , v,}, либо векторы из {va, Vs, . . .

Случай 1. Пусть множество {vi, v......v,} состоит из линейно

независимых векторов. Мы утверждаем, что векторы из Va, . .. . . . , v} также линейно независимы. Чтобы доказать это, допустим, что >] CjV/ € F" для некоторого множества элементов 0% £ F.

Тогда V CjVi € Р"", где Ci=Cibi. Но так как векторы из {vi, Va, ...

. . . , Vg} линейно независимы, то ci=0 для lt. Поэтому множество {va, Vg,. . . , v} также состоит из линейно независимых векторов.

Случай 2. Пусть множество {у», v....., v+,} состоит из линейно независимых векторов. Если векторы из (va, ... , v} линейно независимы, то лемма верна; поэтому допустим, что это не так. Тогда найдутся такие элементы Са, . . ., с, из F, не все равные

ti €Р""- Пусть Ci=Cj&. Тогда вектор w= CjVf также принадлежит f".

Заметим, что сфО, ибо в противном случае вектор CjV,- оказался бы в f вопреки предположению, что векторы из {va, . . . • • м Vfl+i) линейно независимы. Поэтому можно написать

-±сЛ

1 = 2 )

Поскольку не все из Са, . . . , равны О, можно, не умаляя общности, считать, что сФ. Повторим наше рассуждение примени-

) Всюду в этом доказательстве мы опускаем слова «по модулю f



тельно к {vj, vJ, . . . , vj+i}. Если векторы из этого множества

линейно независимы, то все в порядке, так что считаем, что jv? €

F", где ds, . . . , d+i - элементы из f, не все равные 0. Пусть

di== dibi. Тогда вектор x=diVi+djV принадлежит F". Если

di=0, то получаем противоречие с линейной независимостью векторов из {v....., v,+,}. Если diO, можно написать

v, = dr(x-2d,v,

Приравняем два выражения для vi:

dr (х-2 d,v,] = cr» W- 2 C..V,).

Умножим на Cidi и перегруппируем члены: а

diC,v, + 2 (d,c,-сД.) V,-c,d,+,v,+i = d,w-CiX.

Поскольку w и X принадлежат F", то diW-CiX также принадлежит F". Так как с, и di отличны от нуля, то векторы из {v», Vj, . . . . . v,+i} линейно зависимы; получили противоречие. □

Пусть М будет (гХр)-матрицей с элементами из F[ai, . . . , о„1, как и ранее. Покажем теперь, что если q столбцов матрицы М линейно независимы по модулю F*", то любое вычисление вектора Afx, где х=[л:1, .... xV, занимает по крайней мере q умножений.

Определение. Умножение называют активным, если в значение одного из его операндов входит одна из формальных переменных Xi, а значение другого не принадлежит полю F. Например, умножение Ь*с активно, если и(&)=3+а» и v{c)=Xi+2*X3, но неактивно, если v(b)=3 и v{c)=Xi+2»X3 или v{b)=3+a2 и u(c)=ai+2«a,.

Теорема 12.2. Пусть у будет г-мерным вектором с элементами из Flfli, ... , а„]. Если ранг по спюлбцам матрицы М равен q, то любое вычисление вектора Л1х+у содержит не менее q активных умножений, где qX.

Доказательство. Доказательство проводится индукцией по q.

Базис: 9=1. Существуют столбец матрицы М, не принадлежащий F, и, значит, элемент е матрицы М, принадлежащий F\ai, .... а„1, но не F. Поэтому некоторая компонента вектора Л1х содержит произведение ех} для некоторого /. Тогда то же верно и для Л1х-1-у. Вычисление без активных умножений может вычислять





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.0039