Бабенко - Основы численного анализа (947491), страница 12
Текст из файла (страница 12)
Число арифметических операций, .выполняемых в процессе работы алгоритма, характеризует его сложность и время исполнения. Поэтому минимальное число арифметических операций, потребное для его работы, мы будем называть временной слооюностью алгоритма. Теорема 6. Существует алгоритм деле««ил с остатком многочлгнов степени т — 1 на многочлен стпепени п — 1, имеющий временную ти«ооюностт«ъ 0(т.!оог т).
Доказательство теоремы приведено выше. Крайние случаи, когда п, < С!ойз т либо т — п, < С1ойз т, не тРебУют изощРенного апгоРитма деления. Возможно, что в этих случаях обычный «школьный» способ деления будет оптимальным. Зль«вчанию Прн вычислении «т2 мы уже встречались с ныотоновски- ттмн итерациями. Итерационный процесс, описываемый формулами (30), это процесс ньютоновских итераций для решения уравнения т'(х) у(х] — 1 = 0 в кольцЕ степенных рядов от х 9. Быстрый алгоритм вычисления значений многочлена и — 1 р(х) = 2 аьхь степени п, — 1 в п «т«чках хо, ..., х„«построим следуюа=а щим образом. Пусть г = (!оса и', т — -- 2». Введем дополнительные точки тп, ..., хпт -, и определим т двучленов рта(х) = х — х; (т = О, 1,, т— — 1).
1!встроив« рекуррептную последовательность многочленов р, (х) = .= р, о «(х)1«,.~з« вЂ” «(х) (т, — "- 2гм и =- О, 1,..., 2т' т -- 1, у .—. 1. 2„..., г —. — 1). Ясно, что р, (х) многочлены степени 2«, а их число при фиксированном у равно 2' т. Процесс прервем на шаге у' —. г -- 1. Построение этих многочлонов прямой ход алгоритма. Обратный ход состоит в последовательнох«вычислении остатков от доления многочлена на многочлен. Ут:ловимся тюозначать остаток от деления многочлеца г(х) па многочлен в(х) через г(х)(шот! в(х)), Находим последовательность многочленов ит, «(х) = р(г) («пот! р,, «(х)) бо Глава 1. Постановка задач числе!!!гого и!зализа (! = О., 2" !); и! ! = и,.
(щой р! !) (1 = г, ! — , '2з, г = 2зр, р = = О, 1, ..., 2' з"' г, у' =- г — 1, г — 2, ..., 1). Легко проверить, что степень многочлена иг меньше, чем 2з, а по индУкции легко доказать, что и, =- р(х) (шос1 р, (х)). Таким образом, гзю(т) = Р(х) (гтзой Р,е(х)) — — Р(г!), г =- О, 1! ", г« -- ! Определим число операций. Чтобы вычислить многочлен ро, требуется ОЦ2з) операций, а на вычишгение всех многочленов р, понадобится 0(~2!2" ') = 0()2") операпий. Таким образом, прямой ход потребует 2, 002") = 0(2" ге) операций.
Нетрудно подсчитать, что и обратный ход з=! потребует 0(2ггз) операций. Таким образом, доказана Теорема 7. Оуи)ествуюгп алгоригпмы вычислепил п,значений пои линами сгиепсни и — 1 с временной сложггостью 0(п. 1о ~ и). Следствие. Если положить х —.— ыз (~ = О, 1, ..., и — 1), иг =. ехр(2кг)п), те вычисление значений р(ьзг) ((с = О. 1, .... и — 1) риеносильпо вычислению преобразования Фурье от последееагисльношпи ("з)г=! . Таким образок!, из теоремы 7 вытекает Теорема 8.
Каково бы ьпл было натуральное число и, сугйестеует илгоргппм вычисления прсебразоииюия Фурье (19) с временной сложностью 0(п 1ояз и). Является лн оценка теоремы 8 завышенной? Такой вопрос возникает прежде всего дчя простых и,. Нельзя ли для простых и понизить степень 1оув и со второй до первой? Какова нижняя оценка временной сложности оптимальных алгоритмов для вычиагения преобразования Фурье? Несложно убедиться, что существуют алгоритмы вычисления преобразования Фурье с временной сложностью 0(п!ойя и)., какова бы ни была арифметическая природа числа и. Идея построения таких алгоритмов основана на связи дискретного преобразования Фурье с так называемыми циркулянтными матрицами. 3 а д а ч н. 10.
а) Пусхь п = р! ' ...р~~', где рг, ..., Ззг —. простые чисза, Докажите, что существует алгоритм вычисления преобразования Фурье (19) с временной слоя<пастью О(п ч, гй!оя р;). б) Придумайте алгоритм вычис! =! пения преобразования Фурье, имеюпгий временную сложность О),п 1ей п) независимо ет арифметической природы числа п,. Один нз возможных подходов к получению нижних оценок временной сложности состоит в рассмотрении вычислений в расширении поля Š— в кеммутативпом кольце г (хг, ..., х ), где хг,..., т —. формальные переменные; обычно в качестве поля Е берутся поля В илн С.
Тогда под оы велением (алгоритмом) понимается последовательность шагов вида а бис, где й один Ь4. Примерь~ леоригимоо, аи лио алгоритмов кз знаков,, —, х! о переменная, не участвовавшая на предыдущих шагах; Ь, с — либо входы, т. е. формальные переменные. либо элементы Г, либо имена пе1юменных, появившихся слева от стрелки. Таким образом, мы считаем, что вычисление производится шаг за шагом; на каждом шаге новой переменной оказывается элемент из Г(хм..., зо), где ям..., яо входы. Значение о(а) переменной или входа а определяется саедуюп1им образом: <юли о — вход или элемент из Е, то о(а) = о; если а " переменная и о е- ЬВс, то о(о) — — г(Ь) Во(с).
Данное емчислсние (алгоритм) вычисляет множество Е выражений из Е(лп ..., яо) относительно поля Г. если для любого е б Е найдется в этом вычислении такая переменная Г", что о(г) = е. Такой подход позволяет получить целый ряд нижних оценок. Например, если р простое, то минимальная временная сложность алгоритма БПФ равна 2р — г(р — 1) — 3, где г(т) — число делителей цело~ о >и (см. (126)).
11. Покажите, что для вычисления выражений ос — Ьг! и Ьс о. ог! требуется не менее трох умноокений. 12. Докажите, что для деления двух комплексных чисел требуется не менее пяти умножений и делений. 13. Создайте комплекс программ для полиномиальной арифметики, основанной на алгоритмах быстрого умножения, деления и вычисления многочлена при заданных значениях аргумента.
Программа вычисления значений многочлена в точках тм ..., я будет эффективна при болыпом значении п. По тогда нельзя произвольно задавать эти точки, поскольку при вычис;юанях будет значитшгьное накопление погрешностей округления. Возможно, что лучше всего в качестве этих точек взять нули многочлена Чебышева Т„(х) = соэмагссозя (несколько ниже мы познакомимся с теорией этих многочленов). Тогда я, = соз(22 — 1)я/(2п) (У = 1, 2, ..., и). Приняв эти значения л„целесообразно разработать алгоритм бьк:трого вычисления значений, произведя предварительную обработку и вы- 1 числив целые части, х,1ро). Тогда прямой ход делать не нужно, а из обратного хода останется вычисление произведения и,, ~ на:т /р~ (я)).
Такой алгоритм может быть более экономным, 14. Напишите программу для вычисления значений многочлена р(т) в нулях многочлена Чебышева То(т) (п —. 2'), реализовав предварительное вычис- -1 ление целых частей !т /рб(л)). 10. О сложности алгоритмов числовой арифметики. Экономные алгоритмы полиномиалыюй арифметики позволяют по-новому взглянуть на алгоритмы вычисления произведения целых чисел н деления целых чисел с остатком.
Двоичную запись натурального числа можно трактовать как зна ~ение многочлена, коэффициенты которого равны либо 1, либо О дзя значения аргумента х =- 2. Поэтому алгоритм быстрого умножения позволит найти произведение таких много шенов, но останет ся проблема переносов в старшие разряды. Мы не будем останавливаться на этих проблемах, а лишь отметим, что алгоритм Шенхаге и Штрассена для вычисления произведения двух и-разрядных чисел, основанный на идеях быстрого преобразования Фурье, имеет временную сложность О(п !ояз и !одз )ояз п), исчисляемую в битовых операциях. Такова же временная сложность и алгоритма деления, построенного на тех же идеях, что и деленно многочленов (см. !7, 55)).
Глава 1. Павгааиавка задач чивлеиивгв анализа 11. Алгоритмы умножения и обращения матриц. Алгоритмы умножения и обращения матриц, а также решения систем линейных уравнений имеют колоссальное значение в численном анализе, поскольку огромное число задач численного анализа в конечном итоге сводится к тем или пяым вопросам линейной алгебры. Мы рассмотрим вопрос об оптимальности алгоритма умножения матриц, обращения матриц и алгоритма Гаусса решения систем линейных уравнений. Считаюсь, что алгоритм Гаусса оптимальный, Это мнение было подкреплено работой ]54], согласно которой алгоритм исключения Гаусса для решения систем линейных уравнений оптимален в классе алгоритмов, использующих только операции со строками и столбцами.
Покажем неоптимальность алгоритма Гаусса в более широком классе алгоритмов ]145]. Рассмотрим сначала алгоритм Штрассена умножения матриц аы а!2 В Ьы Ь42 основанный на тождестве А.В= где С = (аы -г а22)(Ь44 + Ь22) + аЫ,— Ьы —, Ь24) — (аы л- а42)Ь22+ + (а12 — а22)(Ь21 — ' Ь22), Г =.. (аы ~ а22)(Ьы + Ь22), а44(Ь42 — Ь22) — (а24 + н22)Ьы~ + ] а11 + а21)Ж11 + Ь42) 13 =. а44(Ь42 — Ь22) + (аы + аш)Ь 2, Е = (н 4 + а22)Ьы + а22( — Ьы — , 'Ь24).
Таким образом, чтобы получить произведение двух матриц, достаточно выполнить семь умножений и 18 сложений. Если записать произведение матриц в обычном виде, то нам потребуется восемь умножений. В предыдущем тождестве неважен характер элементов матриц А и В и не использована коммутативность умножения. Таким образом, эти матрицы можно рассматривать как олочные, и тем самым налицо рекурсивная процедура умножения матриц. Считая, что порядок матриц Л и В равен 2", последовательно построим алгоритмы умножения матриц порядка 2, ..., 2г.
Если Т(2") число операций дая умножения двух матриц порядка 2"., то в силу. предыдущего тождесгва Т(2") = 7Т(2' ') —. 18 2 ' Решением этого разносгного уравнения, удовлетворяющим начальному условию Т(2) —.— 7+ 18, будет Т(2") —... 7 —, 6(7" + 4"), и, таким образом, Т(н) = и' из 2 + 6(п'акз 2 + и'"вал), причем первое слагаемое определяет число умножений, а второе сложений. Поскольку 1о827 = 2,81..., 14, Пртливрл~ лворитптиов; аив ив влгоритамов при больших п имеем преимущество перед обычным способом улсножения матриц. Если порядок матриц А и В отличен от 2", то их порядок моясно увеличить до ближайшей степени числа 2, окаймляя исходные матрицы нужным числом нулевых строк и столбцов. Оценка числа операций останется прежней: Т(п1 = О(п'"ко т), Для обращения матрицы А поступим аналогично.
Пусть 1 )тслт слг 1 сгл сггт Элементы матрицы А л можно подсчитать по обычным правилам, решая систему матричных уравнений относительно неизвестных матриц сы. При этом предполагаем, что либо аы, либо агг неособая матрица. Допустим, что агг неособая матрица. Тогла сы =- (ап — апгагг агл) -1 — 1 -1 -1 — 1 — 1 сг~ = — аг ашсм, слг = — сыаггагг, сгг = а, г — а.,г аглсш, и, таким образом, нужно дважды обращать матрицы половинного порядка, шесть раз вычислять произведение матриц и дважды их складывать. Итак, если порядок матрицы равен 2', то мы получаем рекурсивную процедуру обращения матриц, построив алгоритмы обращения матриц порядка 2, ..., 2". Естественно мы нреишолагаем, что все те матрицы, которые по ходу приходится обращать, булут неособенными.
Если обозначить через Т(п) число операций для обращения матрицы порядка и, а через В(п) число операций в оптимальном алгоритме умножения, то Т(2") = 2Т(2""' ) -~- 65(2т ' ) в 2 2" . Если Я(2т) < С2"", то, полагая Т(2т)2 " = 1(г), получим г(г) < 2~ М(г — 1) + 6С2 ~ 2. 21~ и так как сл > 2, то г(г) < Сл. Следовательно, (32) Т(п) < С12от = Слпо Таким образом, при таком способе вычисления обратной матрицы число операций, нужных для обращения, диктуется алгоритмолс умножения.
В частности. можно принять о — —. 1ойг 7. Если порядок лсатрипы и не является степенью числа 2, то можно рассмотреть матрицу ~'=(и, где т — — 2 'окл "'; 1 ... „, —.- единичная матрица размером (тп — и) х (т — п): Оы Ог нулевые прямоугольныо матрицы соответствующих размеров. Обратив матрицу А ", птзлучим и А '. Такилл образом, оценка (32) остается в сила и в общем случае. Отметим, что множество матриц порядка и, для которых пригоден предлагаеллый метод обращения (т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
