Дискретно-непрерывная математика (стр. 97 )

(3.13)

Аналогично определяются и т. д. Из (3.11) — (3.13) следует, что при

(3.14)

Поэтому естественно полагать, что и для любого r при

(3.15)

Оценка (3.15) может быть доказана индукцией по r . Действительно, пусть (3.15) верно при всех r≤s. Докажем, что тогда оно верно и при

r = s + 1. Из нашего предположения и (3.10) имеем

(3.16)

Ищем решение уравнения (3.16) в форме где k(s) и a(s) — неизвестные функции от s. Уравнение, с учетом того, что при приближенно а

принимает вид

(3.17)

Из (3.17) однозначно определяются искомые коэффициенты

Итак, решение уравнения (3.16) что и требовалось доказать.

Сравнив асимптотику (3.15) с (3.3), заключаем, что вычисление ЛО-столбца r - го ранга с помощью последовательного оптимального разло­жения по элементам в r раз менее сложно, чем его вычисление по готовым формулам типа (2.26), (2.27). Аналогичное положение имеет место при вычислении общего ЛО.

Оценим сложность вычисления ЛО с помощью оптимальной последова­тельной дихотомии на основе блочных разложений (2.72), (2.73) (см. §2.12).

Сложность вычисления общего бесконечного ЛО получим из общего выражения (2.79) сложности вычисления с помощью последо­вательных блочных разложений, положив в нем k = 2, что соответствует случаю дихотомии:

(3.18)

Из (3.18) видно, что вычисление бесконечного ЛО с помощью последова­тельной дихотомии требует степенного (квадратичного по r и линейного по q) числа элементарных операций. Однако при q = 2 зависимость от r линейна

(3.19)

Оценим теперь сложность вычисления общего конечного ЛО Для простоты примем, что строки в содержат одинаковое число элемен­тов т, т. е.

(3.20)

Здесь n - общее число элементов в Учтем приведенные в § 2.12 особен­ности процедуры вычисления конечного ЛО В силу равенства длин строк в вычисленном ЛО (3.20) каждый ЛО 2-го порядка составленный на любом k-м этапе процедуры, также имеет равные длины двух своих строк: . . Тогда из (2.83) вытекает следующая развернутая формула для вычисления получившихся на k-м этапе ЛО

На 1-м этапе, сгруппировав строки вычисляемого ЛО по две, получим q/2 ЛО 2-го порядка с 2т элементами (в каждой строке по т элемен­тов) . Вычислив каждый из ЛО для всех значений ранга

s = 1,2,... ,2т (по формуле (3.21)), получим q/2 новых строк длины 2т. Составим из них ЛО На 2-м этапе, сгруппировав строки в по две, получим ЛО 2-го порядка с 22т элементами (в каждой строке по 2т эле­ментов) . Вычислив каждый из для всех значений ранга s = 1,2, ..., 22 т, получимновых строк длины 22т, из которых составим новый ЛО и т. д. Таким образом, на k-м этапе вычислению подлежат ЛО 2-го порядка с элементами (по 2k-1 т элементов в каждой строке). При этом в согласии с ранее сделанными замечаниями (§ 2.12) каждый ЛО вычисляется: на 1-м, 2-м,..., предпоследнем, -м этапе - для всех значений ранга на последнем -м этапе — для единственного значения ранга s= r. Следовательно, суммарная сложность процедуры вычисления ЛО (3.20)

(3.22)

Здесь - сложность вычисления ЛО на k-м этапе. Как видно из фор­мулы (3.21) (с учетом значения п(k)),

(3.23)

Будем считать, что ранг r вычисляемого ЛО удовлетворяет условию

(3.24)

Условие (3.24) не ограничивает общности отыскиваемой оценки сложнос­ти. Действительно, в силу леммы 2.15 вычисление ЛО при сво­дится к вычислению нового ЛО с тем же числом элементов п, но с ран­гом

Из (3.24) следует, что последнее слагаемое в (3.22) определяется всегда первой строкой выражения (3.23): Еслито по

условию суммирования в (3.22) для всех k. Это значит, что остальные слагаемые в (3.22) определяются первой строкой выраже­ния (3.23) Подставляя эти результаты в (3.22), после сум­мирования найдем

(3.25)

Если то выражение (3.23) зависит от соотношения k и s, и для суммирования в (3.22) удобно положить

(3.26)

При этом множество С этапов процедуры естественным образом разбива­ется на три подмножества С1, С2, С3. В С1 входят этапы с номерами k, для которых количество п (k) элементов в вычисляемых ЛО 2-го порядка не превышает r, т. е. откуда где— целая часть х.

На каждом таком этапе необходимо вычислять ЛО для всех возможных значений ранга реализуя при этом сложность, указываемую первой или второй строкой (3.23) - в зависимости от значения s. В С2 входит один этап с номером k, для которого количество п (k) эле­ментов в вычисляемых ЛО впервые превзошло r, т. е. откуда или где — символ округления до ближайшего большего целого числа. На этом этапе ЛО вычисляется лишь для значений ранга причем сложность вычисления при