1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 99
Текст из файла (страница 99)
Определение. Умножение называют активным, если в значение одного нз его операндов входит одна из формальных переменных х„а значение другого не принадлежит полю Р. Например, умножение Ьвс активно, если о(Ь)=3+а, и и(с)=х,+2ьх„но неактивно, если о(Ь)=3 н о(с)=х,+2вхз или о(Ь)=3+а, и о(с)=а,+2ьаз. Теорема 12.2. Пусть у будет г-мерным вектором с элементами из Р[а„..., а„1. Если ранг но столбцам матрицы М равен и, то любое вычисление вектора М х+у содержит не менее д активных умножений, где дЫ. Д о к а з а т е л ь с т в о.
Доказательство проводится индукцией по о. Базис: у=1. Существуют столбец матрицы М, не принадлежащий Р', и, значит, элемент е матрицы М, принадлежащий Р[а„..., а„1, но не Р. Поэтому некоторая компонента вектора Мх содержит произведение ехз для некоторого 1. Тогда то же верно и для Мх+у. Вычисление без активных умножений может вычислять 1В,З. ГРАНИЦА, СВЯЗАННАЯ С РАНГОМ ПО СТОЛБЦАМ только выражения вида Р(а„..., а»)+т.(хв,..., хр), где Р— полипом и Ь вЂ” линейная функция, оба с коэффициейтами из Р. Таким образом, вычисление вектора Мх+у должно включать хотя бы одно активное умножение.
Шаг индукции. Допустим, что д)! и теорема верна для д — 1. Пусть С вЂ” вычисление вектора Мх+у. По предположению индукции С содержит не менее д — 1~)! активных умножений. Пусть 1 «- й»й — первое такое умножение. Тогда без потери общности можно считать, что Р и(л) =Р(а„..., а„)+ ~с,хо (12.4) в=! где Р— полипом с коэффициентами из Р и все св также принадлежат Р.
Более того, не умаляя общности, можно считать, что с,чьО. Наша стратегия состоит в том, чтобы построить из С и множества выражений Мх+у новое множество выражений М'х'+у' с вычислением С', содержащим на одно активное умножение меньше, чем С. Кроме того, д — 1 столбцов матрицы М' будут линейно независимы по модулю Р'. Тогда по предположению индукции С' будет содержать не менее д — 1 активных умножений, а значит, С вЂ” не менее д активных умножений.
Конкретно, мы заменим х, в С некоторым выражением е, которое сделает я из (12.4) равным О. Выражение е будет вычислимо без активных умножений. Вычисление С' начинается с вычисления выражения е, при этом значение е присваивается формальной переменной х, (она уже больше не будет входной переменной). Остальная часть вычисления С' состоит из С, где 1 «-й»Ь заменено на 1 «-О. Затем мы покажем, что множество выражений, вычисляемых с помощью С', можно выразить в виде М'х'+у', где д — 1 столбцов матрицы М' линейно независимы по модулю Р'.
Итак, приступим к изложению деталей доказательства. Из (12.4) и допущения св=~О заключаем, что й=О, если р — (Р »„ ..., ~! -~- х !* ~ . (!в.в! Правая часть равенства (12.5) и есть выражение е, упоминаемое выше. Вычисление С', получаемое нз С описанным выше способом, вычисляет Мх+у, куда вместо х, подставлено е.
Поэтому М'х1+у' можно записать как е хв хв +у» Гл, 32. иижииБ оцвики числА АРиФмитичвских опеРАция а зто переписать в виде Г в '1 — с, ',~~ с,х, ! 2 х, х, — с,' Р(а а„)1 + у. (12.6) Рассмотрим первое слагаемое в (12.6). Пусть т~ — это т-й столбец матрицы М. Для 2<1<р положим т,=пт,— (с;lс,)птп Пусть М' — матрица, состоящая из р — ! столбцов, у которой т-й столбец есть пь',и и пусть х'=(х„..., хрр'.
Таким образом, первое слагаемое в (!2.6) равно М'х'. Второе слагаемое — вектор с компонентами из Г(аи..., а„1, ибо элементы матрицы М принадлежат Г[а„..., а„1. Поэтому второе и третье слагаемые в (12.6) можно объединить в новый вектор у' с компонентами из Лаи..., а„1. Таким образом, С' вычисляет М'х'+у'. Из леммы 12.1 непосредственно вытекает, что не менее а — 1 столбцов матрицы М' линейно независимы по модулю Г", Следовательно, С' содержит не менее а — 1 активных умножений, и потому С содержит не менее а активных умножений.
С) Приведем два примера применения теоремы 12.2. Пример 12.8. Мы утверждаем, что умножение (и Х р)-матрицы А на р-мерный вектор и требует пр умножений элементов. Формально, пусть а» и от — формальные переменные, 1<2<а, 1<1<р. Тогда произведение Ач матрицы на вектор имеет вид, показанный на рис. 12.1. Непосредственно применяя теоремы 12.1 и 12.2 к Аи, заключаем лишь, что требуется МАХ(п, р) умножений. Однако произведение матрицы на вектор можно также выразить в виде Мх, где в 1-й стро. ке матрицы М в столбцах с ((1 — 1)р+1)-го до (тр)-го стоят о„...
..., Ср, а в остальных столбцах в нули. Вектор х †э вектор-стол- а а „ ... а,р а„а„... а, а„,а„, ... а„р ор1 Рис. 12,1, Общий вид вроизвеаеиия мвтрицы ив вектор. 22.5, ГРАНИЦА СВЯЗАННАЯ С РАНГОМ ПО СТОЛБЦАМ ан и22 а,р а, 2222 и! и ° ° ир О О ° О ° ° О О О О О О и, и, ир . О О О и сиуюл ае О О О О О О . и, и, ° ир лр си2оийрю а„, а„т Рве.
!2.2. Эквнвалентная форма произведения матрицы на вектор. бец, равный конкатенации строк матрицы А, записанной сверху вниз. М и х изображены на рис. 12.2. Легко показать, что столбцы матрицы М линейно независимы по модулю ги. Поэтому в силу теоремы 12.2 любое вычисление для Ат требует не менее пр умножений. Р Пример 12.9.
Рассмотрим задачу вычисления полинома п-й сте- и пени Д а2х'. Эту задачу можно представить как вычисление произведения матрицы М на вектор х: а, п, [1,х,хе, ..., хи1 Элементы матрицы М принадлежат г1х1 и х [а„ао..., а 1г. Легко показать, что все столбцы матрицы М, кроме первого, линейно независимы по модулю г. Следовательно, в М содержатся л линейно независимых столбцов, и вычисление произвольного поли- нома а-й степени требует не менее п умножений.
гл. пс нижнив оценки числа кеиемвтичвскнх опзэкцнп Правило Горнера, вычисляющее полипом по схеме (... ((а„х+а„,) х+а„,) х+... +а,) х+а„ требует в точности и умножений и, значит, оптимально в том смысле, что использует наименьшее возможное число умножений. Аналогично можно показать, что для вычисления фа;х' нужны и сложений и вычитаний. Таким образом, правило Горнера использует наименьшее число арифметических операций, необходимых для вычисления значения полинома в одной точке.
С) 12.6. ГРАНИЦА ДЛЯ ЧИСЛА УМНОЖЕНИЙ, СВЯЗАННАЯ С РАССМОТРЕНИЕМ СТРОМ И СТОЛБЦОВ Объединим теоремы 12.1 и 12.2, чтобы доказать более сильный результат, чем тот, который получается, если рассматривать независимость строк и столбцов отдельно. Пусть М будет (гор)-матрицей с элементами из р[аь..., а„[, как и раньше, и х=[х„...,х [г. Теорема 12.3. Пусть М содержит такую подматрицу 5 с д строками и с столбцами, что для любых векторов ц и ч из гч и г' соответственно элемент пг5ч принадлежит полю г" тогда и только тогда, когда ц=О или ч=О.
Тогда любое вычисление произведения Мх требует не менее у+с — 1 умножений. Д о к а з а т е л ь с т в о. Не умаляя общности, с самого начала считаем, что в матрице М только д строк, а 5 состоит нз ее первых с столбцов. Допустим, что Мх можно вычислить за э умножений. Пусть е — вектор, компонентами которого служат э выражений, вычисляемых этими умножениями. Предположим, кроме того, что 1-я компонента вектора е вычислена раньше!-й для 1(1.
Тогда, как в теореме 12,1, можно написать Мх= Же+1, (12.7) где !У вЂ” это (дХэ)-матрица с элементами из г и 1 — вектор, компоненты которого представляют собой линейные комбинации из а„ ..., а„ и х„ ..., х . Как и в теореме 12.1, можно заключить, что э н!. Если бы это было не так, то нашелся бы такой вектор у~О из гл, что угУ=Ог, откуда следовало бы, что компоненты вектора угМ принадлежат г. Тогда компоненты вектора у"5 принадлежали бы г вопреки условию (возьмите пг ч и чг=[1,..., 11). Поскольку э)д, можно разбить Ф на две матрицы Л(, и Ж„ где Ж, состоит из первых з — о+1 столбцов матрицы !ч', а Л(, — из ее последних д — 1 столбцов.
Далее, пусть е, и е, — векторы, составленные из первых э — а+! и последних а — 1 элементов вектора е со- пак и хницл для числА ъмнс> ответственно. Тогда можно записать (12.7) в виде Мх = Ф,е, + Ж,е, + 1. (12.8) Так как й(, имеет размер дх(п — 1), то найдется такой вектор у~О из Рт, что у~У =От Умножим (12.8) на ут утМх=утЯ е -(-ут1 (12.9) Положим М'=угМ. Заметим, что М' — это (1 Х р)-матрица, равная линейной комбинации строк матрицы М. Поскольку произведения, входящие в е„можно вычислять, не обращаясь к произведениям из е., (мы предположили, что первые вычисляются раньше вторых), то очевидно, что выражение М х можно вычислить с помощью (12.9) за з — д+1 умножений.
Если теперь мы сможем показать, что с столбцов матрицыМ' линейно независимы по модулю Р, то в силу теоремы 12.2 сможем утверждать, что з — у+1)с. Тогда з)0+с — 1, что и требовалось доказать. Итак, покажем, что первые с столбцов матрицы М'=утМ линейно независимы по модулю Р. Пусть ут=(уп..., ут). Первые с элементов матрицы М' имеют вид ~ у,Мм для 1(1(с, где Мм— Г=! это (1, 1)-й элемент матрицы М. допустим, что нашелся такой века тор х~О с компонентами г„..., з, из Р, что Х гф у,М» принад/ лежит Р, т. е. первые с столбцов матрицы М' зависимы по модулю Р. Тогда элемент утЗх оказался бы в Р вопреки условию теоремы относительно 5. Поэтому М' содержит с линейно независимых по модулю Р столбцов, и теорема доказана. П Применим теорему 12.3 к умножению двух комплексных чисел а+(Ь и с+Ы, чтобы показать, что оно требует трех умножений вещественных чисел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
