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