Равенство одного полинома другому

1.         Равенство одного полинома другому.

Два многочлена f(x) и g(x) будут считаться равными (или тождественно равными), f(x) = g(x), в том случае, если равны их коэффициенты при одинаковых степенях неизвестного. [1, С. 131]

2.         Сложение и умножение полиномов.

Пусть  и , где , , n, s – степени многочленов f(x) и g(x). Если n ≥ s (иначе переобозначим степени полиномов), то их суммой называется многочлен , коэффициенты которого получаются сложением коэффициентов f(x) и g(x), стоящих при одинаковых степенях переменного, т.е. , i = 0, 1, …, n. Степень суммы равна n, если n ≥ s, но при n = s она может оказаться меньше n, а именно в том случае если . [1, С. 132]

Произведением многочленов f(x) и g(x) называется многочлен , коэффициенты которого определяются следующим образом , так как , , то , поэтому степень произведения многочленов равна n + s. [1, С. 132]

3.         Замкнутость относительно сложения и умножения. Исходя из первых двух свойств многочлена, очевидно, что складывая или перемножая два каких-либо многочлена от одного и того же переменного с коэффициентами из К, мы получим однозначно многочлен с коэффициентами из того же кольца К.

  1.1.4 Используемые в исследовании теоремы и их доказательства

Т1. [1, С. 134]

Для любых двух многочленов f(x) и g(x) можно на найти такие многочлены q(x) и r(x), что

f(x) = g(x) ∙ q(x) + r(x), (1.1)

причем степень r(x) меньше степени g(x) или же r(x) = 0. Многочлены q(x) и r(x), удовлетворяющие этому условию определяются однозначно.

Доказательство. [1, С. 134-135]

Докажем сперва вторую половину теоремы. Пусть существуют еще многочлены q1(x) и r1(x), также удовлетворяющие равенству

f(x) = g(x) ∙ q1(x) + r1(x), (1.2)

причем степень r1(x) меньше степени g(x) или равна нулю. Приравнивая друг другу правые части равенств (1.1) и (1.2), получим:

g(x) ∙ [q(x) – q1(x)] = r1(x) – r(x).

Степень правой части этого равенства меньше степени g(x), степень же левой части была бы при больше или равна степени g(x). Поэтому должно быть q(x) – q1(x) = 0, т.е. q(x) = q1(x), а тогда и r(x) = r1(x), что и требовалось доказать.

Переходим к доказательству первой половины теоремы. Пусть многочлены f(x) и g(x) имеют соответственно степени n и s. Если n < s, то можно положить q(x) = 0, r(x) = f(x). Если же n ≥ s, то воспользуемся методом деления многочленов с действительными коэффициентами, расположенных по убывающим степеням неизвестного. Пусть

Полагая

(1.3)

мы получаем многочлен, степень которого меньше n. Обозначим эту степень через n1, а старший коэффициент многочлена f₁(x) – через а_n1. Положим, далее, если все еще n1 ≥ s,

(1.4)

Обозначим эту степень через n2, а старший коэффициент многочлена f₂(x) – через а_n2. Положим, далее, если все еще n2 ≥ s,

(1.5) и т.д.

Так как степень многочленов f₁(x), f₂(x), … убывают, n > n1 > n2 > …, то мы дойдем после конечного числа шагов до такого многочлена f_k(x),

(1.k)

степень которого nk меньше s, после чего наш процесс останавливается. Складывая теперь равенства (1.3), (1.4), (1.5), …, (1.k) мы получим:

т.е. многочлены

Действительно удовлетворяют равенству (1.2), причем степень r(x) действительно меньше степени g(x).

Т2. [1, С. 135]

Многочлен g(x) тогда и только тогда будет делителем многочлена f(x), если существует многочлен q(x), удовлетворяющий равенству

f(x) = g(x)  q(x) (2.1)

 

Доказательство. [1, С. 135-136]

Если g(x) является делителем для f(x), то в качестве q(x) следует взять частное от деления f(x) на g(x).

Обратно, пусть многочлен q(x), удовлетворяющий равенству (2.1), существует. Из Т1 о единственности многочленов q(x) и r(x), удовлетворяющих равенству f(x) = g(x) ∙ q(x) + r(x) и условию, что степень r(x) меньше степени g(x), в нашем случае следует, что частное от деления f(x) на g(x) равно q(x), а остаток равен нулю.

Т3. [3, С. 106]

Если а – корень многочлена f(x), то f(x) делится на х – а.

Доказательство. [3, С. 106 -107]

Деление f(x) на х – а дает равенство f(x) = (x –a) ∙ q(x) +r(x). Подставим в это равенство х = а: 0 = r(x), откуда f(x) = (x –a) ∙ q(x).

Т4. Основная теорема алгебры. [1, С. 147]

Всякий многочлен с любыми числовыми коэффициентами, степень которого не меньше единицы имеет хотя бы один корень, в общем случае комплексный.

Доказательство.

См. [1, C.147 – 156]

Следствие 4.1 [1, С. 156]

Многочлен f(x) степени n над полем комплексных чисел имеет каноническое разложение с точностью до множителя нулевой степени вида f(x)=c ∙ (x – a₁) ∙ (x – a₂) ∙ … ∙ (x – a_n). Причем это разложение единственное.

Доказательство.

См. [1, С. 156-157]

Следствие 4.2

Всякий многочлен f(x) степени n, n ≥ 1, с любыми числовыми коэффициентами имеет n корней, если каждый корень считать столько раз, какова его кратность.

Доказательство.

См. [1, С. 157]

Из всех приведенных теорем и следствий наибольшее значение для данной курсовой работы имеют следствия 4.1 и 4.2, так как в них говориться, что любой многочлен в общем случае может разлагаться на многочлены первой степени с точностью до множителя нулевой степени, т.е. с точностью до числового коэффициента, и их количество с учетом кратности равно степени разлагаемого многочлена и что многочлены, входящие в каноническое разложение, содержат в себе все корни разлагаемого полинома, соответственно с учетом их кратности.

Это не маловажно, так как теперь можно говорить о том, что, имея степень генерируемого полинома и его корни, мы можем с точностью до числового коэффициента определить и получить необходимый полином указанной степени.

  1.2 Генерация полиномов

Генерация достаточно молодая и полностью не исследованная область

информатики и программирования. Дать точного и полного определения, что такое генерация пока еще не возможно. Под генерацией в общем случае понимается процесс динамического изменения некоторых программных параметров. Теоретически генерация может быть случайной, однако на практике случайную генерацию организовать практически не возможно. Так, например, генерация случайных чисел (в действительности псевдо случайных) зависит от многих параметров (время, дата и т.д.). Тема этой курсовой работы генерация полиномов. В программе, реализующей алгоритм генерации полинома, происходит заведомо неслучайная генерация коэффициентов полинома, так как она зависит от двух параметров: степени полинома и его корней

Глава 2. Практическая часть по генерации полиномов

  2.1 Алгоритм генерации полиномов

Исследовав теоретическую часть по проблеме генерации полиномов, приступил к практическому применению полученных знаний. Прежде, чем приступать к написанию кода программы, генерирующей полиномы по введенной пользователем степени и корням, составил алгоритм для решения данной задачи.

Алгоритм.

1.         Ввести степень генерируемого полинома.

2.         Если степень не была введена или был введен символ, не являющийся цифрой, или было введено число меньше двух, то выдать сообщение об ошибке и перейти к пункту 1, иначе, при корректном вводе, перейти к пункту 3.

3.         Организовать цикл (количество итераций равно степени генерируемого полинома) для ввода корней генерируемого полинома.

4.         Ввести корни генерируемого полинома.

5.         Если корень не был введен или был введен символ, не являющийся цифрой, то выдать сообщение об ошибке и перейти к пункту 4, иначе, при корректном вводе, перейти к пункту 6.

6.         После окончания работы цикла произвести перемножение введенных корней генерируемого полинома в соответствии с правилами перемножения полиномов (см. пункт 1.1.3.2)

7.         Вывести получившийся полином в порядке убывания степеней переменной на экран.

2.2 Написание программы, реализующей алгоритм генерации полиномов

  2.2.1 Преодоление проблем, возникших при написании программы

При написании кода программы, реализующей алгоритм генерации полиномов, столкнулись с рядом трудностей.

Во-первых, необходимо было реализовать проверку вводимых данных, чтобы вводимые значениями были только цифры и числа. Для преодоления первой проблемы был разработан следующий алгоритм, реализация которого будет приведена ниже.

1.         Инициализировать цикл с постусловием.

2.         Ввести значение в виде строки.

3.         Инициализировать цикл (количество итераций равно длине введенной пользователем строки).

4.         Перемещаться во введенной строке посимвольно.

5.         Если символ цифра перейти к пункту 6, иначе перейти к пункту 8.

6.         Переводим символ в цифру.

7.         Прибавляем цифру к числу, которое будет являться переводом введенной строки, если она число, предварительно умноженное его на десять.

8.         Выдаем сообщение об ошибке и переходим к пункту 2.

9.         Запоминаем получившееся число при корректном вводе.

Второй проблемой явилось переполнение типа данных – long при перемножении (в данной программе, написанной на языке С). Однако она была решена при написании функций проверки при перемножении и общей проверки коэффициентов генерируемого полинома, которые будут приведены ниже.

Третья проблема – переполнение буфера. При написании программы пришлось увеличить буфер для ввода значений, но при считывании рассматривать только первые девять символов, чтобы заведомо не превысить максимальное значение используемого типа, и, если было введено более девяти символов, то выдать сообщение об ошибке и попросить пользователя заново ввести значение.

Четвертая проблема – хранение введенных данных. Для ее преодоления было использовано четыре массива; в первом (массив m)будут храниться все корни генерируемого полинома (его размер – 2∙n, где n – степень генерируемого полинома), второй и третий – вспомогательные (участвуют в перемножении), в третьем (массив b) будет храниться корень генерируемого многочлена, взятый из первого массива, (его размер – 2); во втором (массив a) вначале храниться корень генерируемого многочлена из первого массива, а после первого перемножения в него будет перезаписываться результат перемножения для следующего выполнения этой операции (размер – n+1); последний массив (массив c) – результирующий, содержит все коэффициенты генерируемого многочлена после перемножения (размер n+1).

  2.2.2 Описание и пояснение некоторых частей программы

В данном пункте будут приведены некоторые части программы, реализующей алгоритм генерации полиномов, с пояснениями.