Открытие в вычислительной математике

Открытие относится к третьему разделу классификации компьютерных наук — алгоритмы и их сложность и одновременно к четырнадцатому разделу — компьютерное моделирование и численные методы.

В вычислительной математике известен алгоритм Штурма, который позволяет найти число корней многочлена за конечное число арифметических действий, не вычисляя самих корней. Число требуемых действий зависит от коэффициентов многочлена, однако для данной степени многочлена не может быть слишком велико. Например, для многочлена второй степени x2+px+q число корней находится так. Сначала нужно вычислить так называемый дискриминат, т. е. выражение D = р2 — 4q. На это уйдёт два умножения и одно вычитание. Далее нужно сравнить D с нулём: если D < 0, то корней нет; если D = 0, то корень один; если D > 0, то корней два. В этом случае для вычисления числа корней понадобилось от четырёх до шести операций, включая сравнение.

Согласно легенде, когда великого немецкого  математика  Карла  Гаусса спросили, долгих экспериментов с числами». Гауссу приходилось проводить эти эксперименты вручную. Сегодня в распоряжении математиков-экспериментаторов есть компьютеры и специальные программы, которые умеют выполнять многие математические алгоритмы. В том числе и алгоритм Штурма, который необходим для выполнения многих других алгоритмов. Несмотря на стремительно растущую мощность современных компьютеров, с алгоритмом Штурма они справляются плохо. Число действий, требуемых для подсчёта числа корней, быстро растёт с увеличением степени многочлена.

Физико-математический журнал для школьников «Квант» попросил меня написать популярную статью про алгоритм Штурма и разобраться, многочлены какой степени «по зубам» современным персональным ЭВМ. Я сидел дома и пытался придумать первую фразу статьи. Естественно было начать её с описания того, что такое «многочлен». После нескольких попыток у меня родилась следующая фраза: «Многочленом называется выражение в котором много членов».