От автора
Полиномы были первой серьезной темой, с которой начались мои занятия вычислительной математикой. В 50-х годах в аспирантуре я занимался дифференциальной геометрией. Мой научный руководитель Абрам Миронович Лопшиц, человек очень широких интересов, начал в это время заниматься сам и привлек меня сначала к линейной алгебре, а затем и к полиномам. По договоренности с издательством он поручил мне писать справочник [], взяв на себя обязанности научного редактора. О требовательности А.М.Лопшица к своим публикациям ходили легенды, поэтому наша работа над книгой оказалась для меня школой, оставившей след на всю жизнь.
Вычислительная математика в эти годы в связи с появлением ЭВМ находилась в состоянии бурного роста и переоценки идей. Этими соображениями мы руководствовались при отборе и анализе методов, хотя сами еще не имели опыта программирования, а приводимые в справочнике примеры я рассчитывал на арифмометре. Нужно сказать, что значительная часть отобранного материала выдержала проверку несколькими поколениями ЭВМ, и я с удивлением узнаю, что некоторые читатели пользуются нашим справочником до сих пор.
Живой интерес к справочнику проявлял заведующий кафедрой Леонид Михайлович Рыбаков, он во многом способствовал нашей работе. На одной из конференций Леонид Михайлович попросил меня сделать обзорный доклад по многочленам. В докладе я обратил внимание на то, что ни один метод в то время не гарантировал нахождения корней. При обсуждении доклада Леонид Михайлович вышел к доске и со свойственной ему четкостью изложения сформулировал идею алгоритма, гарантирующего нахождение всех действительных корней полинома. Вскоре он по просьбе
А.М.Лопшица оформил заметку [], а мне на курсах по программированию удалось реализовать этот метод (это была моя первая программа) [].
Сформировавшийся интерес к вычислительной математике вскоре привел меня на работу в Федеральном ядерном центре, а затем и других организациях, нуждающихся в серьезных вычислениях. Мне довелось заниматься разработкой методов и созданием программных комплексов для задач ядерной физики, механики, физики взрыва и соударения, турбулентной конвекции, рассеяния лазерного излучения, вопросами распараллеливания вычислений, проблемами точности при решении плохо обусловленных задач и многим другим. И вот через 40 лет судьба снова свела меня с многочленами. Руководство NSTL в лице Л. В. Нестеренко предложило мне написать обучающий курс по вычислениям с полиномами.
Что изменилось за эти 40 лет в самих методах и в наших представлениях о них? Появились, конечно, новые методы. Наиболее важным, по-видимому, является создание алгоритмически отработанной реализации метода спуска []. Этот метод теоретически обеспечивает гарантированное нахождение комплексных корней многочлена. Популярным одно время был очень экономичный метод Мюллера (метод парабол). Он не гарантирует нахождение всех корней, но чаще всего находит их правильно. По мере роста быстродействия ЭВМ фактор экономичности становится менее существенным, что делает предпочтительным метод спуска. Впрочем, использующееся в обеих методах понижение степени полинома после нахождения очередного корня приводит к потере точности, что может привести к потере части корней. Таким образом, вопрос об автоматизированном (путем обращения к процедуре) нахождении всех корней нельзя считать полностью решенным. Вероятно, можно построить такую процедуру с использованием арифметики переменной точности, но это потребует тщательного анализа погрешностей в процессе вычислений.
С другой стороны, рост производительности ПК и развитие графических методов дают возможность в интерактивном режиме найти все корни и оценить их погрешности. Автором в процессе работы над учебником был разработан метод MOG, который в сочетании с методом аргумента и графическими средствами решает поставленную задачу.
Такие классические методы, как метод Лобачевского или метод Бернулли, не находят сейчас широкого применения, но заложенные в них идеи по-прежнему интересны и способствуют появлению новых алгоритмов, например, [].
Наиболее значительные изменения в представлениях о полиномах связаны с понятием обусловленности. Мощность вычислительных машин сделала возможным выполнение операций с полиномами высокой степени. Однако возникающая при этом потеря точности часто обесценивает получаемые результаты. Развитие вычислительной математики в значительной части связано с разработкой методов, менее чувствительных к обусловленности задачи, а также к созданию средств оценки обусловленности. Применительно к алгебраическим задачам проблема обусловленности очень обстоятельно проанализирована в прекрасной книге Уилкинсона []. Частично этому посвящена и моя работа [].
Развитие интерфейса пользователя с машиной, особенно с персональным компьютером, повышает роль графических методов. Эти методы позволяют, например, не только найти нужные корни, но и оценить точность отдельных корней, обусловленность задачи в целом.
Появились, конечно, и другие многочисленные разработки, связанные с многочленами. Я не ставил перед собой цель дать систематическое изложение современного состояния данного раздела вычислительной математики, это потребовало бы и от меня и от читателя несоизмеримо больших затрат сил и времени. В то же время мне хотелось выделить, сообразуясь со своим опытом, те методы, которые обеспечивают основные потребности пользователя, и те идеи, которые нужны для их понимания или могут служить ступенькой для дальнейшего творчества.
PS. Обучающий курс состоит из учебника и программы. Предполагалось, что при чтении учебника примеры решаются с помощью программы. Однако, со времени написания программы прошло более 10 лет, интерфейс сильно устарел. Поэтому в данной публикации решение примеров, особенно их графические данные, добавлены в текст учебника. Таким образом, им можно пользоваться без программы. 09.08.2010
µ §
Цель и основное содержание курса
Области применения полиномов
Полином во многих отношениях является более простой функцией, чем экспонента, логарифм, тригонометрические, специальные функции и т.п. Значение полинома при фиксированном значении аргумента вычисляется с помощью операций сложения и умножения. Просто выражаются производные и интегралы. Это привело к тому, что в приложениях многие функции приближенно заменяются (аппроксимируются) полиномами.
Областью, в которой часто возникают полиномы, являются задачи математической физики. Многие физические объекты связаны с линейными операторами и представляющими их матрицами. Изучение свойств этих операторов требует решения так называемого характеристического уравнения, левая часть которого имеет форму полинома. К аналогичным уравнениям приводят и некоторые другие задачи, например, исследование устойчивости разностных схем. Полиномиальные уравнения возникают также при решении линейных обыкновенных дифференциальных уравнений и их систем.
Не будем перечислять все области применения полиномов. Сказанного уже достаточно, чтобы понять, что знание основных свойств полиномов и умение работать с ними должно входить в базу образования вычислителя-прикладника и может оказаться полезным для других специалистов, использующих компьютер.
Содержание курса
Данный курс лекций посвящен описанию свойств полиномов и методов работы с ними. Рассматриваются также характерные трудности, возникающие при использовании полиномов на практике. Лекции сопровождаются примерами, которые можно просчитать и проанализировать непосредственно в процессе изучения теоретического материала. Практическая работа ведется с помощью лаборатории полиномов PolyLab, которая прилагается к курсу и обеспечивает выполнение основных операций с полиномами. Пользователь, достаточно хорошо знакомый с теорией и практикой применения полиномов, может ограничиться изучением темы 2, содержащей описание лаборатории, и использовать PolyLab в своей повседневной работе.
Методические основы курса
Систематическое изложение свойств полиномов можно найти, например, в [],[],[]. Особенность данного курса заключается в том, что методы решения уравнений здесь излагаются более подробно, чем это необходимо для их формального использования на практике. Это дает возможность читателю усовершенствовать методы применительно к своей задаче. Такая потребность возникает достаточно часто, так как практика вычислений с полиномами, несмотря на их кажущуюся простоту, зачастую приводит к результатам, противоречащим теории. Это связано, главным образом, с погрешностями вычислений. Этому аспекту уделяется в курсе особое внимание.
Наибольшие трудности при работе с полиномами возникают при определении их корней. Мы видим свою задачу не в том, чтобы дать абсолютно надежные способы вычисления корней, что невозможно, а в том, чтобы прояснить характерные ситуации и объяснить, с чем и как можно бороться, а где необходимо смириться и, может быть, отказаться от полиномов как средства решения Вашей более общей задачи.
Возможности лаборатории PolyLab
Лаборатория полиномов PolyLab обеспечивает возможность создания и хранения полиномов, преобразования их из одной формы в другую, выполнение операций сложения, умножения, деления полиномов, замены аргумента в них и др. Кроме того, лаборатория содержит средства визуализации полиномов и вычисления их корней.
Как мы уже отмечали, задача вычисления корней является наиболее важной и наиболее трудной. Используя средства лаборатории PolyLab Вы сможете разобраться в любой ситуации и либо найти корни, либо понять, почему это невозможно. Для этого необходимо хорошее владение методами и немного терпения. Для некоторых методов введен управляющий параметр, которым Вы сможете влиять на ход решения в случае возникновения нештатных ситуаций.
В основном лаборатория разработана для учебных целей, но ее можно использовать и в прикладной деятельности.
Тема 1. Начальные сведения о полиномах
Лекция 1. Основные определения
Полином
Определение. Полиномом, или многочленом, называется функция вида
µ § (1.1.1)
где n ЁC степень полинома, х ЁC аргумент, a0, ЎK, an ЁC коэффициенты, a0 № 0.
Полиномы удобно рассматривать или над полем вещественных чисел, когда аргумент и коэффициенты вещественны, или над полем комплексных чисел, когда и аргумент, и коэффициенты являются комплексными. На практике, однако, наиболее распространены задачи, в которых коэффициенты полинома являются вещественными, а аргумент считается комплексным числом. При дальнейшем изложении именно этот случай имеется в виду, если не оговорено иное.
Полином Рn(x) может быть представлен в виде, отличном от (1.1.1), но его всегда можно преобразовать к данному виду. В лекции 2 подробно описаны различные формы представления полиномов и способы преобразования этих форм друг в друга.
Корень полинома
Определение. Число x1 называется корнем полинома Pn(x), если оно удовлетворяет равенству Рn (x1) = 0.
Вычисление корней является наиболее распространенной и в то же время наиболее сложной операцией с полиномами. По самому своему определению полином представляет собой сумму членов вида aк.xn ЁC k. При больших по модулю значениях x и для полиномов высокой степени некоторые из таких членов могут быть большими. В то же время нахождение корня связано с определением такого значения x, при котором полином, т.е. сумма его членов, обращается в ноль. При таком "взаимном уничтожении" больших членов неизбежна, как показывается в теме 5, потеря точности. Именно этим, в основном, и объясняются трудности, возникающие при вычислении корней некоторых полиномов.
Лекция 2. Формы представления полиномов
Каноническая форма
Форма представления полинома в виде (1.1.1), данная при его определении, а именно:
µ §
называется канонической. Коэффициент a0 обычно предполагается отличным от нуля, при этом n ЁC наивысшая степень аргумента x называется степенью полинома. Полином первой степени называют линейным, второй ЁC квадратичным, третьей ЁC кубическим. Фактически задание полинома в канонической форме сводится к заданию вектора коэффициентов µ §Соответственно, мы будем в дальнейшем говорить, что полином задан коэффициентами.
Форма разложения
Хорошо известным является способ разложения функции в степенной ряд. Если разложение ведется в окрестности точки a и ограничивается конечным числом членов, то возникает функция
µ § (1.2.1)
Эта функция с помощью несложных преобразований, как будет показано ниже, приводится к полиному в его канонической форме. Однако часто ее удобно использовать в исходном виде.
Мы будем говорить в таком случае о представлении полинома в форме разложения.
Форма Лагранжа
Полиномы также используются для аппроксимации функций, заданных в нескольких фиксированных точках. Так, например, в случае линейной аппроксимации строится отрезок ЁC линейная функция, проходящая через две заданные точки (x1, y1), (x2, y2). Аналогично, для системы точек
µ § (1.2.2)
можно построить полином Pn(x), проходящий через эти точки: Pn(xi) = yi. Такую форму задания полинома мы будем называть формой Лагранжа или опорной. Коэффициенты соответствующего полинома удовлетворяют системе уравнений:
µ § (1.2.3)
Система является линейной относительно коэффициентов a0, a1,ЎK, an, число уравнений равно числу неизвестных. Определитель системы известен как определитель Ван-дер-Монда:
µ §
Он отличии от нуля, если x1, x2,ЎK, xn+1 различны, так что система (1.2.3) имеет единственное решение.
Полином Лагранжа
Другая форма представления полинома, проходящего через опорные точки ЁC полином Лагранжа []. Элементарным полиномом Лагранжа для системы (1.2.2) называется полином
µ §
Произведение здесь берется для всех i = 1, 2,ЎK, n + 1, кроме i = r. Очевидно, что Lrn(xr) = 1 и Lrn(xj) = 0 для всех j № r. Полином Лагранжа, проходящий через опорные точки (1.2.2), можно представить в виде
µ § (1.2.4)
Это выражение можно преобразовать и найти коэффициенты полинома, однако в ряде случаев его целесообразно использовать непосредственно.
Факторизованная форма
Факторизованной мы будем называть форму представления
µ §
где Rm и Sn ЁC m ЁC некоторые многочлены степени которых меньше n (0 < m < n).
Полностью факторизованная форма
Форму представления полинома в виде произведения линейных множителей
µ § (1.2.5)
где x1 ,ЎK, xn ЁC все его корни, мы будем называть полностью факторизованной. Это представление мы будем также называть представлением корнями.
Вопрос о числе корней полинома и возможности его представления в полностью факторизованной форме (1.2.5) рассматривается в теме 3. В программе PolyLab в форме представления полинома корнями коэффициент a0 всегда равен единице.
Полностью факторизованная форма с учетом кратностей корней
