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

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

Лемма 12.1. Пусть множество, состоящее из -мерных векторов с компонентами из Если в есть подмножество из векторов, линейно независимых по модулю то для любых элементов из множество содержит подмножество, состоящее из векторов, линейно независимых по модулю

Доказательство. Перенумеровав при необходимости векторы можно считать, что линейно независимы либо векторы из либо векторы из

Случай 1. Пусть множество состоит из линейно независимых векторов. Мы утверждаем, что векторы из также линейно независимы. Чтобы доказать это, допустим, что для некоторого множества элементов с

Тогда где Но так как векторы из линейно независимы, то для Поэтому множество также состоит из линейно независимых векторов.

Случай 2. Пусть множество состоит из линейно независимых векторов. Если векторы из линейно независимы, то лемма верна; поэтому допустим, что это не так. Тогда найдутся такие элементы из не все равные О что Пусть Тогда вектор также принадлежит

Заметим, что ибо в противном случае вектор оказался бы в вопреки предположению, что векторы из линейно независимы. Поэтому можно написать

Поскольку не все из равны 0, можно, не умаляя общности, считать, что Повторим наше рассуждение

применительно к Если векторы из этого множества линейно независимы, то все в порядке, так что считаем, что где элементы из не все равные 0. Пусть Тогда вектор принадлежит Если то получаем противоречие с линейной независимостью векторов из Если можно написать

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

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

Поскольку принадлежат то также принадлежит Так как отличны от нуля, то векторы из линейно зависимы; получили противоречие.

Пусть будет -матрицей с элементами из как и ранее. Покажем теперь, что если столбцов матрицы линейно независимы по модулю то любое вычисление вектора где занимает по крайней мере умножений.

Определение. Умножение называют активным, если в значение одного из его операндов входит одна из формальных переменных а значение другого не принадлежит полю Например, умножение активно, если

Теорема 12.2. Пусть у будет -мерным вектором с элементами из Если ранг по столбцам матрицы равен то любое вычисление вектора содержит не менее активных умножений, где

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

Базис: Существуют столбец матрицы не принадлежащий значит, элемент матрицы принадлежащий но не Поэтому некоторая компонента вектора содержит произведение для некоторого Тогда то же верно и для Вычисление без активных умножений может вычислять

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

Шаг индукции. Допустим, что и теорема верна для Пусть С — вычисление вектора По предположению индукции С содержит не менее активных умножений. Пусть первое такое умножение. Тогда без потери общности можно считать, что

где полином с коэффициентами из и все также принадлежат Более того, не умаляя общности, можно считать, что

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

Конкретно, мы заменим в С некоторым выражением которое сделает из (12.4) равным 0. Выражение будет вычислимо без активных умножений. Вычисление С начинается с вычисления выражения при этом значение присваивается формальной переменной (она уже больше не будет входной переменной). Остальная часть вычисления С состоит из С, где заменено на Затем мы покажем, что множество выражений, вычисляемых с помощью С, можно выразить в виде где столбцов матрицы линейно независимы по модулю

Итак, приступим к изложению деталей доказательства.

Из (12.4) и допущения заключаем, что если

Правая часть равенства (12.5) и есть выражение упоминаемое выше. Вычисление С, получаемое из С описанным выше способом, вычисляет куда вместо подставлено Поэтому можно записать как

а это переписать в виде

Рассмотрим первое слагаемое в (12.6). Пусть это столбец матрицы Для положим Пусть матрица, состоящая из столбцов, у которой столбец есть и пусть Таким образом, первое слагаемое в (12.6) равно

Второе слагаемое — вектор с компонентами из ибо элементы матрицы принадлежат Поэтому второе и третье слагаемые в (12.6) можно объединить в новый вектор у с компонентами из Таким образом, С вычисляет Из леммы 12.1 непосредственно вытекает, что не менее столбцов матрицы линейно независимы по модулю Следовательно, С содержит не менее активных умножений, и потому С содержит не менее активных умножений.

Приведем два примера применения теоремы 12.2.

Пример 12.8. Мы утверждаем, что умножение -матрицы А на -мерный вектор требует пр умножений элементов. Формально, пусть формальные переменные, Тогда произведение матрицы на вектор имеет вид, показанный на рис. 12.1.

Непосредственно применяя теоремы 12.1 и 12.2 к заключаем лишь, что требуется умножений. Однако произведение матрицы на вектор можно также выразить в виде где в строке матрицы в столбцах с до стоят а в остальных столбцах — нули. Вектор это вектор-столбец

Рис. 12.1. Общий вид произведения матрицы на вектор.

Рис. 12.2. Эквивалентная форма произведения матрицы на вектор.

равный конкатенации строк матрицы А, записанной сверху вниз. их изображены на рис. 12.2.

Легко показать, что столбцы матрицы линейно независимы по модулю Поэтому в силу теоремы 12.2 любое вычисление для требует не менее пр умножений.

Пример 12.9. Рассмотрим задачу вычисления полинома степени Эту задачу можно представить как вычисление произведения матрицы на вектор

Элементы матрицы принадлежат Легко показать, что все столбцы матрицы кроме первого, линейно независимы по модулю Следовательно, в содержатся линейно независимых столбцов, и вычисление произвольного полинома степени требует не менее умножений.

Правило Горнера, вычисляющее полином по схеме

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