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

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

(• •({аг + а„-г)х+а„.2)х + . • • +а,)х + ао,

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

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

Объединим теоремы 12.1 и 12.2, чтобы доказать более сильный результат, чем тот, который получается, если рассматривать независимость строк и столбцов отдельно. Пусть М будет (гХр)-матрицей с элементами из Fla,, . . . , а„1, как и раньше, и x=Ui, . . . ,л;,].

Теорема 12.3. Пусть М содержит такую подматрицу S с q строками и с столбцами, что для любых векторов и и v из F" и F" соответственно элемент uSv принадлежит полю F тогда и только тогда, когда и=0 или v=0. Тогда любое вычисление произведения Мх требует не менее q+c-l умножений.

Доказательство. Не умаляя общности, с самого начала считаем, что в матрице М только q строк, а S состоит из ее первых с столбцов. Допустим, что Мх можно вычислить за s умножений. Пусть е - вектор, компонентами которого служат s выражений, вычисляемых этими умножениями. Предположим, кроме того, что i-я компонента вектора е вычислена раньше /-й для i<j. Тогда, как в теореме 12.1, можно написать

Лх = Ле + 1, (12.7)

где N - это ((7х5)-матрица с элементами из f и f - вектор, компоненты которого представляют собой линейные комбинации из fli, .... а„ их,,..., Хр.

Как и в теореме 12.1, можно заключить, что sq. Если бы это было не так, то нашелся бы такой вектор уфО из f«, что yiV=0, откуда следовало бы, что компоненты вектора уМ принадлежат F. Тогда компоненты вектора yS принадлежали бы F вопреки условию (возьмите u=v и v=[l, . . . , 11).

Поскольку sq, можно разбить N на две матрицы Ni и N, где Ni состоит из первых s-+1 столбцов матрицы N, а Мг - из ее последних q-1 столбцов. Далее, пусть ei и е - векторы, составленные из первых S-<7+1 и последних q-1 элементов вектора е со-



IB.6. ГРАНИЦА ДЛЯ чист»

ответственно. Тогда можно записать (12.7) в виде

(12.8)

Так как Л2 имеет размер qx(q-1), то найдется такой вектор уО из р1, что yiV2=0. Умножим (12.8) на у:

уМхуМе + уЧ. (12.9)

Положим Л1=уШ. Заметим, что М - это (1 Хр)-матрица, равная линейной комбинации строк матрицы М. Поскольку произведения, входящие в ei, можно вычислять, не обращаясь к произведениям из е-г (мы предположили, что первые вычисляются раньше вторых), то очевидно, что выражение Мх можно вычислить с помощью (12.9) за s-q+\ умножений. Если теперь мы сможем показать, что с столбцов матрицыiVfлинейно независимы по модулю F, то в силу теоремы 12.2 сможем утверждать, что s-q+lc. Тогда sq-\-c-1, что и требовалось доказать.

Итак, покажем, что первые с столбцов матрицы Л1=уЛ1 линейно независимы по модулю F. Пусть y=[«/i, ... , у]. Первые с

элементов матрицы М имеют вид yiMtj для 1/с, где Ми - это (t, /)-й элемент матрицы М. Допустим, что нашелся такой вектор ХфО с компонентами Zi, . . ., 2 из F, что г/гЛ!;; принадлежит F, т. е. первые с столбцов матрицы М зависимы по модулю F. Тогда элемент ySz оказался бы в F вопреки условию теоремы относительно S. Поэтому М содержит с линейно независимых по модулю F столбцов, и теорема доказана. □

Применим теорему 12.3 к умножению двух комплексных чисел a+ib и c+id, чтобы показать, что оно требует трех умножений вещественных чисел. Заметим, что каждая из теорем 12.1 и 12.2 в отдельности не достаточно сильна для этого.

Пример 12.10. Рассмотрим задачу умножения двух комплексных чисел a+ib и c+id, а именно вычисления

Afx =

Пусть S - сама матрица М, а F - поле вещественных чисел и

а -Ь

b а

- векторы из Fi. Допустим, что

[У1 У»]

- Ь а



- элемент поля F. Это произведение равно yiZiO+yib+y- -yiZib. Если оно принадлежит полю F, то коэффициенты при а и 6 должны равняться нулю. Поэтому

Угг+Уг.О (12.10)

Уаг-УггаО. (12.11)

Допустим, что «/iTO. Тогда из (12.11) получаем Za-yJyi. Подставив это в (12.10) и умножив на у, находим, что (iy\+yX)Zi=Q. Поскольку У1Ф<), то у\-{-у1фО и, значит, Zi=0 Тогда в силу (12.11) «2=0. Но равенства Zi=Za=0 противоречат условию

Теперь допустим, что (/,=0. Если г/а=0, то противоречие возникает сразу. Если «/2=50, то, поменяв ролями </i и (/а в рассуждении, приведенном выше, получаем, что 2i=Za=0; снова противоречие.

Таким образом, теорема 12.3 применима к М\ при q=c=2, так что три вещественных умножения необходимы. Программа в примере 12.3 показывает, что три умножения и достаточны. □

Теоремы 12.1-12.3 можно обобщить на случай, когда в вычислении допускаются деления. В этом случае надо допускать такие шаги в вычислении, которые при некоторых значениях входов приводят к делению на 0. Следовательно, теория, рассматривающая мультипликативные операции (т. е. умножение и деление), предполагает, что поле F бесконечно. Если бы оно было конечным, то мы могли бы столкнуться с вычислениями, не работающими ни для каких входов из-за того, что любой возможный вход приводит к делению на 0.

С учетом этих изменений каждую из теорем 12.1-12.3 можно перенести на случай обеих мультипликативных операций вместо одного умножения. В теореме 12.2 определение активной мультипликативной операции f -*~g*h или / должно быть следующим: или значение одной из переменных g и Л включает в себя одну из формальных переменных xt, а другой операнд не принадлежит F, или g принадлежит F, h включает в себя одну из формальных переменных Xi и операцией является деление.

12.7. ПРЕДВАРИТЕЛЬНАЯ ОБРАБОТКА

В примере 12.9 мы показали, что вычисление значения полинома п-й степени в одной точке требует п умножений. Однако мы исходили из предположения, что полином представлен своими коэффи-

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