Способы нахождения корней линейных и квадратичных многочленов

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Методы нахождения границ многочлена

1.1 Метод хорд и касательных (комбинированный)

1.2 Метод итераций

1.3 Метод половинного деления (метод бисекции)

1.4 Метод разложения на множители

2. Схема Горнера

3. Универсальный метод нахождения границ многочлена. Метод Ньютона

4. Теорема Штурма

5. Решение задач на вычисление границ многочлена

Заключение

Список литературы



Введение

Способ нахождения корней линейных и квадратичных многочленов, то есть способ решения линейных и квадратных уравнений, был известен ещё в древнем мире. Поиски формулы для точного решения общего уравнения третьей степени продолжались долгое время (следует упомянуть метод, предложенный Омаром Хайямом), пока не увенчались успехом в первой половине XVI века в трудах Сципиона дель Ферро, Никколо Тарталья и Джероламо Кардано. Формулы для корней квадратных и кубических уравнений позволили сравнительно легко получить формулы для корней уравнения четвертой степени. [3, c. 67]

То, что корни общего уравнения пятой степени и выше не выражаются при помощи рациональных функций и радикалов от коэффициентов было доказано норвежским математиком Нильсом Абелем в 1826 г. Это совсем не означает, что корни такого уравнения не могут быть найдены. Во-первых, в частных случаях, при некоторых комбинациях коэффициентов корни уравнения при некоторой изобретательности могут быть определены. Во-вторых, существуют формулы для корней уравнений 5-й степени и выше, использующие, однако, специальные функции - эллиптические или гипергеометрические (см., к примеру, корень Бринга).

В случае, если все коэффициенты многочлена рациональны, то нахождение его корней приводится к нахождению корней многочлена с целыми коэффициентами. Для рациональных корней таких многочленов существуют алгоритмы нахождения перебором кандидатов с использованием схемы Горнера, причем при нахождении целых корней перебор может быть существенно уменьшен приемом чистки корней. Также в этом случае можно использовать полиномиальный LLL-алгоритм. Для приблизительного нахождения (с любой требуемой точностью) вещественных корней многочлена с вещественными коэффициентами используются итерационные методы, например, метод секущих, метод бисекции, метод Ньютона. Количество вещественных корней многочлена на интервале может быть оценено при помощи теоремы Штурма. [8, c. 56]



1. Методы нахождения границ многочлена

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

В этой связи задача нахождения корней многочлена вида (1):

F(x)=a0+a1x+a2x2+…+anxn. (1)

представляет особый интерес, т.к. формулы нахождения корней даже кубического уравнения достаточно сложны, а если необходимо отыс. кать корни многочлена, степень которого равна, например, 5 - то без помощи численных методов не обойтись, тем боле, что вероятность наличия у такого многочлена натуральных (или целых, или точных корней с с "короткой" дробной частью) довольно мала, а формул для нахождения корней уравнения степени, превышающей 4, не существует. [1, c. 23]

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

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

1.1 Метод хорд и касательных (комбинированный)

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

Надо отметить, что существуют также отдельно метод хорд (дает значение корня с недостатком) и метод касательных (с избытком). Однако преимущество комбинированного метода заключается в "двустороннем сжатии" рассматриваемого отрезка. [2,c.54]

Рассмотрим следующий случай. Дана функция F(x) и построен ее график. Определена допустимая погрешность Q на основании графика определен отрезок [a, b], на котром график функции пересекает ось абсцисс, следовательно, на этом отрезке (рис. 1).

Рис. 1

Существует корень рассматриваемого многочлена. (обозначим его через A). Дальнейший алгоритм сводится к следующим действиям:

строим касательную к графику функции в точке F(b);

вычисляем координату х пересечения касательной с осью абсцисс по формуле (3) и обозначаем ее через b';

строим к графику функции хорду, проходящую через точки F(a) и F(b).

Вычисляем точку пересечения хорды с осью абсцисс по формуле (2) и обозначаем ее через a'.

a'=a- Da, где , (2)

b'=b- Db. (3)

Таким образом мы получаем новый отрезок [a', b'], который (по определениям хорды и касательной) по-прежнему содержи решение уравнения A.

Теперь принимаем отрезок [a', b']за новый отрезок [a, b] и повторяем шаги 1-4 до тех пор, пока разность F(b)-F(a) не станет меньше первоначально заложенной погрешности Q. Отметим также, что после этого рекомендуется в качестве искомого решения взять среднее арифметическое F(a) и F(b).

Замечание к методу хорд и касательных. В рассмотренном случае производная F'(x)>0, т.е. график "выпуклый" и b>a. При работе с каждым отдельным случаем необходимо находить производные функции первого и второго порядков и, сообразуясь с ее знаком, определять a и b.

	Способ хорд	Способ касательных
F'(x)F''(x) > 0	С недостатком	С избытком
F'(x)F''(x) < 0	С ибытком	С недостатком

Таким образом, если хорда (касательная) дает значение корня с избытком, то этот корень берется в качестве новой правой границы, а если с недостатком - то левой. В обоих случаях точный корень лежит между точками пересечения хорды и касательной с осью абсцисс. [5, c.90]

Замечание 2 к методу хорд и касательных. Так как для решения поставленной задачи требуется отыскание производной функции F(x), метод хорд и касательных достаточно трудно реализуем на программном уровне, т.к. правила вычисления производных в общем виде довольно громоздки для "понимания" ЭВМ; при непосредственном указании производной для каждой степени многочлена память компьютера серьезно загружается, что очень замедляет работу, а задание функции и, соответственно, ее производной непосредственно в программном коде - недопустимо. Однако, используя данный метод, сходимость интервала к корню происходит наиболее быстро, особенно если совместить метод хорд и касательных с методом бисекции, т.к. середина нового отрезка зачастую дает вполне удовлетворительное решение. [9,c.12]

1.2 Метод итераций

Пятый шаг алгоритма хорд и касательных определял возврат к первому шагу и последующую цикличность хода, т.е. метод хорд и касательных являлся итерационным. Другой метод, также основанный на повторах так и был назван - "метод итераций". [2, c.7]

Суть его заключается в следующем:

дана функция F(x);

определена допустимая погрешность Q;

определен некоторый интервал [a, b], точно содержащий решение уравнения.

Определено некоторое число z, принадлежащее [a, b](назовем z "нулевым приближением").

Для получения следующего приближения подставим в формулу (1) вместо X Z, получим:

x1=F(z) (4)

и, продолжая аналогично,

x2=F(x1)

x3=F(x2) (5)

…

xn=F(xn-1).

Таким образом, получаем некоторую последовательность, и, если ее предел:

limxn=A, n®v (6)

то А является искомым корнем.

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

необходимость выбора нулевого приближения (ведь то, что интуитивно для человека, для ЭВМ может стать довольно сложной задачей);

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

Эти контраргументы стали основанием для отклонения метода итераций при выборе алгоритмизируемого метода. [4, c.71]

1.3 Метод половинного деления (метод бисекции)

Метод половинного деления (известный еще и как "метод деления отрезка пополам") также является рекурсивным, т.е. предусматривает повторение с учетом полученных результатов. [3, c.43]

Суть метода половинного деления заключается в следующем:

дана функция F(x);

определена допустимая погрешность Q;

определен некоторый интервал [a, b], точно содержащий решение уравнения.

Рис. 2

Вычисляем значение координаты Е, беря середину отрезка [a, b], т.е.:

Е= (a + b) / 2. (7)

Вычисляем значения F(a), F(b), F(E), и осуществляем следующую проверку: Если F(E)>Q, то корень с указанной точностью найден. Если F(E)<Q, т.е. необходимая точность еще не достигнута, то формируем два интервала: [a, E]и [E, b]проверяем знаки F(a), F(b), F(E). На концах одного из этих интервалов знаки функции будут одинаковы, а на другого различны (иначе Е - искомый корень). И именно то интервал, на концах которого знаки различны, мы берем за основу при следующей итерации, т.е. приравниваем к Е либо a, либо b.

Переходим к пункту 1.

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

1.4 Метод разложения на множители

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

Пусть дан многочлен:

F(x) = 2x3-11x2+20x-12. (11)

Его можно записать в виде:

F(x) = (x+2)2(2x-3). (12)

У многочлена n-степени, как известно, n корней, а из (12) следует, что корнями F(x) являются - 2 и 1,5, причем корень - 2 является кратным, т.е. фактически это два одинаковых корня. При отыскании же корней любым из вышеописанных методов "второй" корень - 2 будет потерян, т.к. график функции будет иметь лишь две точки пересечения с осью абсцисс. [5, c. 41]

Чтобы избежать этого применяется метод разложения на множители. Суть его заключается в следующем: каждый многочлен вида (1) можно представить в виде:

(x+h1)(x+h2)…(x+hn)*H = 0 (13), или

F(x) = (x+h)(bn-1xn-1+…b1)+b0, (14)

где h1…hn - корни уравнения, а Н - произведение множителей х, вынесенных за скобки (Н никак не влияет на уравнение, т.к. от него избавляются, деля на Н обе части (13). При этом не исключено, что некоторые h могут быть взаимно равны, что и свидетельствует о наличии кратного корня.

Для вычисления значений новых коэффициентов в (14) используются формулы:

bn=an

bn-1=bnh+an-1 (15)

bn-2=bn-1h+an-2.

Таким образом, алгоритм этого метода выглядит следующим образом:

определить границы корней уравнения;

при помощи любого из вышеописанных методов найти один корень уравнения;

применяя формулы (14) и (15) сформировать новый многочлен степени, на 1 меньшей предыдущего;

вернуться к пункту 2;

повторять до тех пор, пока степень многочлена не обнулится. [3, c.11]



2. Схема Горнера

Разделить с остатком многочлен f (x) на ненулевой многочлен g (x) - это значит представить f (x) в виде:

f (x) =g (x) s (x) +r (x),

где s (x) и r (x) -многочлены и либо r (x) =0, либо ст. r (x) < ст. g (x). S (x) назовем неполным частным, а r (x) - остатком при делении f (x) на g (x).

Неполное частное при делении можно найти с помощью простого правила, называемого схемой Горнера, которое, кстати, позволяет найти и остаток. [4, c. 29]

Пусть:

f (x) =a_nxⁿ+a_n-1x^n-1+ … +a₁x+a_0, a_n?0

- многочлен n-й степени. При делении его на x - c мы получим неполное частное s (x) и остаток r, т.е.:

f (x) = (x - c) s (x) + r.

Так как ст. f (x) = n, а ст. (x - c) = 1, то:

ст. s (x) = n - 1, т.е. s (x) = b_n-1x^n-1 + b_n-2x^n-2 + … + b₁x+ b₀, b_n-1? 0.

Таким образом, имеем равенство:

a_nxⁿ+a_n-1x^n-1+ … +a₁x+a₀ = (x - c) (b_n-1x^n-1+b_n-2x^n-2+ …+b₁x+b₀) +r.

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

a= b_n-1,a_-1 = b_{n-2 -} cb_n-1,a_-2 = b_{n-3 -} cb_n-2,

a₂ = b₁ - cb_2,a₁ = b₀ - cb_1,a₀ = r - cb₀.

Напомним, что требуется найти неполное частное, т.е. его коэффициенты, и остаток.

Выразим их из полученных равенств:

b_n-1 = a_n,

b _n-2 = cb_n-1 + a_n-1,b _n-3 = cb_n-2 + a _n-2,

b₁ = cb₂ + a_2,b₀ = cb₁ +a_1,r = cb₀ + a_0.

Мы нашли формулы, по которым можно вычислять коэффициенты неполного частного s (x) и остаток r. При этом вычисления оформляются в виде следующей таблицы; она называется схемой Горнера.

Таблица 1. Коэффициенты f (x)

	an	an-1	an-2	…	a0
c	bn-1	bn-2 = cbn-1+ an-1	bn-3 = cbn-2+an-2	…	r = cb0 + a0

Коэффициенты s (x) остаток.

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

Остальные клетки этой строки заполняют, вычисляя один за другим коэффициенты неполного частного s (x) и остаток r. Во второй клетке записывают коэффициент b_n-1, который, как мы установили, равен a_n.

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

Разделим, например, многочлен:

f (x) =3x⁴-5x²+3x-1

на х-2 с остатком, используя схему Горнера.

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

Так, коэффициенты f (x) - это числа 3, 0, - 5, 3, - 1. И еще следует помнить, что степень не полного частного на единицу меньше степени многочлена f (x).

Итак, выполняем деление по схеме Горнера:

Таблица 2

	3	0	-5	3	-1
2	3	6	7	17	33

Получим неполное частное:

s (x) =3x³+6x²+7x+17

и остаток r=33. заметим, что одновременно мы вычислили значение многочлена f (2) =33.

Разделим теперь тот же многочлен f (x) на х+2 с остатком. В этом случае с=-2. получим:

Таблица 3

	3	0	-5	3	-1
-2	3	-6	7	-11	21

В результате имеем:

f (x) = (x+2) (3x³-6x²+7x-11) +21.

Ранее мы установили, что, если с - корень многочлена f (x) делится на х-с. Сейчас обобщим это утверждение.

Пусть с ₁, с ₂, …, с_m - различные корни многочлена f (x). Тогда f (x) делится на х-с ₁, т.е.

f (x) = (x-c₁) s₁ (x).

Положим в этом равенстве х=с ₂. Получим:

f (c₂) = (c₂-c₁) s₁ (c₂)

f (c₂) =0, то (с ₂-с ₁) s₁ (c₂) =0.

S₁ (c₂) =0. Таким образом, с ₂ - корень многочлена s₁ (x).

Отсюда следует, что s₁ (x) делится на х-с ₂, т.е.:

s₁ (x) = (x-c₂) s₂ (x).

Подставим полученное выражение для s₁ (x) в равенство f (x) = (x-c₁) s₁ (x). Имеем:

f (x) = (x-c₁) (x-c₂) s₂ (x).

S₂ (x) = (x-c₃) s₃ (x),

f (x) = (x-c₁) (x-c₂) (x-c₃) s₃ (x) и т.д.

Продолжив эти рассужденья для оставшихся корней с ₄, с ₅, …, с_m, мы, наконец, получим:

f (x) = (x-c₁) (x-c₂) … (х-с_m) s_m (x).

Т.е. доказано формулируемое ниже утверждение.

Если с ₁, с ₂, …, с_m - различные корни многочлена f (x), то f (x) можно представить в виде:

f (x) = (x-c₁) (x-c₂)... (x-c_m) s_m (x).

Отсюда вытекает важное следствие.

Если с ₁, с ₂,…, с_m - различные корни многочлена f (x), то f (x) делится на многочлен (х-с ₁) (х-с ₂) … (х-с_m).

Как мы уже отмечали, одной из важных задач в теории многочленов является задача отыскания корней многочлена. В связи с этим существенным представляется вопрос о их числе. В самом деле, если дан какой-то многочлен и уже найдено, скажем, 10 его корней, то нужно знать, следует ли продолжать поиски. А вдруг этот многочлен больше не имеет корней? В таких случаях нам будет полезна приводимая ниже теорема. [8, c. 56]

Число различных корней ненулевого многочлена f (x) не больше, чем его степень. Действительно, если f (x) корней не имеет, то ясно, что теорема верна.Пусть теперь f (x) имеет m корней с ₁, с ₂, …, с_m, причем все они различны. Тогда, по только что доказанному f (x) делится на (х-с ₁) (х-с ₂) … (х-с_m). В таком случае: метод многочлен ньютон горнер

ст. f (x)= ст. ((х-с ₁) (х-с ₂) … (х-с_m)) =ст. (х-с ₁) + ст. (х-с ₂) +…+ст. (х-с_m) =m,

т.е. ст. f (x)m, а m - это число корней рассматриваемого многочлена.

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

Из только что доказанной теоремы следует такое утверждение.

Если многочлен f (x) не является многочленом степени, большей, чем n, и имеет более, чем n корней, то f (x) - нулевой многочлен.

В самом деле, из условий этого утверждения следует, что-либо f (x) - нулевой многочлен, либо ст. f (x)n. Если предположить, что многочлен f (x) не нулевой, то ст. f (x)n, и тогда f (x) имеет не более, чем n корней. Приходим к противоречию. Значит, f (x) - ненулевой многочлен.

Пусть f (x) и g (x) - ненулевые многочлены степени, не большей, чем n. Если эти многочлены принимают одинаковые значения при n+1 значении переменной х, то f (x) =g (x).

Для доказательства рассмотрим многочлен h (x) =f (x) - g (x). Ясно, что - либо h (x) =0, либо ст. h (x)n, т.е. h (x) не является многочленом степени, большей, чем n. Пусть теперь число с такое, что f (c) =g (c). Тогда h (c) = f (c) - g (c) =0, т.е. с - корень многочлена h (x). Следовательно, многочлен h (x) имеет n+1 корень, а когда, как только что доказано, h (x) =0, т.е. f (x) =g (x).

Если же f (x) и g (x) принимают одинаковые значения при всех значениях переменной х, то эти многочлены тем более равны.

Эта теорема весьма эффективно используется при доказательстве некоторых числовых тождеств. [8, c. 34]

Докажем, например, что для любых попарно различных чисел а, b, с и любого числа х.

(((x-b) (x-c)) / ((a-b) (a-c))) + (((x-a) (x-c)) ((b-a) (b-c))) + (((x-a) (x-b)) ((c-a) (c-b))) =1

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

Будем рассматривать х как переменную. Тогда, как нетрудно заметить, в левой части тождества находится многочлен, который мы обозначим f (x). Переменная х входит в этот многочлен самое большое в степени 2, т.е. ст. f (x)?2. в правой части того же тождества - так же многочлен: g (x) =1.

Найдем теперь значение многочленов f (x) и g (x) при х=a, b, c. Ясно, что g (a) =g (b) =g (c) =1. Далее,

f (a) = (((a-b) (a-c)) / ((a-b) (a-c))) + (((a-a) (a-c)) ((b-a) (b-c))) + (((a-a) (a-b)) ((c-a) (c-b))) =1.

Аналогично f (b) =f (c) =1. Следовательно, f (a) =g (a), f (b) =g (b), f (c) =g (c). Видим, что многочлены f (x) и g (x), не являющиеся многочленами степени выше, чем 2, принимают одинаковые значения при трех различных значениях переменной. Значит, f (x) =g (x).



3. Универсальный метод нахождения границ многочлена. Метод Ньютона

Одним из наиболее распространенных методов поиска корней уравнений является метод Ньютона и его модификации. Пусть требуется решить уравнение. Будем считать, что x является решением уравнения. Разложим функцию f(x) в ряд в точке x0 близкой к точке x и ограничимся только первыми двумя членами разложения.

.

Поскольку x - корень уравнения, то . Следовательно,

.

Таким образом, если нам известно приближенное значение корня уравнения, то полученное уравнение позволяет его уточнить. Понятно, что процесс уточнения можно повторять многократно, до тех пор, пока значение функции не будут отличаться от нуля на величину меньшую, чем заданная точность поиска. Очередное k-е приближение находится по формуле:

.

Ограничившись в разложении только первыми двумя членами, мы фактически заменили функцию f(x) на прямую линию, касательную в точке x0, поэтому метод Ньютона еще называют методом касательных. Далеко не всегда бывает удобно находить аналитическое выражение для производной функции. Однако, в этом и нет особой необходимости: поскольку на каждом шаге мы получаем приближенное значение корня, можно для его вычисления использовать приближенное значение производной. [6, c. 10]

.

В качестве малой величины можно взять, например, заданную точность вычислений , тогда расчетная формула примет вид:

(1.1)

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

(1.2)

В таком виде метод называется методом секущих (secant method). При этом, однако, возникает проблема с вычислением первого приближения. Обычно полагают, что , то есть первый шаг вычислений проводится с использованием формулы (1.1), а все последующие - с использованием формулы (1.2). Именно эта вычислительная схема реализована в пакете Mathcad. Используя метод секущих, мы не можем гарантировать, что корень находится между двумя последними приближениями. Можно, однако, для вычисления очередного приближения использовать границы интервала, на котором функция меняет знак. Такой метод называется методом хорд (false position method).



4. Теорема Штурма

Теорема Штурма. Если действительные числа а и Ь, a<ib, не являются корнями многочлена / (х), не имеющего кратных корней, то W(a)=W(b) и разность W(a)-W(b) равна числу действительных корней многочлена f(x), заключенных между а и b.

Количество вещественных корней многочлена на интервале может быть оценено при помощи теоремы Штурма.

Ряд Штурма (система Штурма) для вещественного многочлена - последовательность многочленов, позволяющая эффективно определять количество корней многочлена на промежутке и приближённо вычислять их с помощью теоремы Штурма. Ряд и теорема названы именем французского математика Жака Штурма. [2.c,34]

Рассмотрим многочлен f(x) с вещественными коэффициентами. Конечная упорядоченная последовательность отличных от нуля многочленов с вещественными коэффициентами называется рядом Штурма для многочлена f(x), если выполнены следующие условия: не имеет корней;

если и , то ;

если ,

то произведение меняет знак с минуса на плюс, когда x, возрастая, проходит через точку c, т.е. когда существует такое д > 0, что:

для и для .

Значением ряда Штурма в точке c называется количество смен знака в последовательности f0(c), f1(c), ..., fs(c) после исключения нулей.

Теорема Штурма Пусть f(x) - ненулевой многочлен с вещественными коэффициентами, f0(x), f1(x),..., fs(x) - некоторый ряд Штурма для него, [a,b]- промежуток вещественной прямой, причём . Тогда число корней многочлена f(x) на промежутке [a, b] равно W(a) ? W(b), где W(c) - значение ряда Штурма в точке c.

Ряд Штурма существует для любого ненулевого вещественного многочлена. Пусть многочлен f(x), отличающийся от константы, не имеет кратных корней. Тогда ряд Штурма для него можно построить, например, следующим образом:

;

;

Если fk(x) (k > 0) имеет корни, то

,

где - остаток от деления многочлена f(x) на многочлен g(x) в кольце многочленов , иначе s = k.

Для произвольного многочлена, отличающегося от константы, можно положить:

,

и далее следовать приведенному выше способу. Здесь (f(x), f'(x)) - наибольший общий делитель многочленов f(x) и f'(x). Если многочлен f(x) есть ненулевая константа, то его ряд Штурма состоит из единственного многочлена f0(x) = f(x).

Ряд Штурма используется для определения количества вещественных корней многочлена на промежутке. Отсюда вытекает возможность его использования для приближённого вычисления вещественных корней методом двоичного поиска.

Построим указанным выше способом ряд Штурма для многочлена:

f(x) = (x ? 1)(x ? 3) = x2 ? 4x + 3

Многочлен fi(x)	Знак многочлена в точке
		0	1	2	3	4
f0(x) = x2 ? 4x + 3
f1(x) = 2x ? 4
f2(x) = 1
Значение ряда в точке

Таким образом, по теореме Штурма число корней многочлена f(x) равно: 2 ? 0 = 2 на промежутке ;

2 ? 0 = 2 на промежутке (0,4);

2 ? 1 = 0 на промежутке (0,2).

Применим метод Штурма к многочлену:

Л (*) = *" + 2**-5*3 + 8*2-7* -3.

Мы не будем при этом предварительно проверять, что h (х) не имеет кратных корней, так как метод построения системы Штурма одновременно служит для проверки взаимной простоты многочлена и его производной. [7,c.32]

Найдем систему Штурма для h(x), применяя указанный метод. При этом в процессе деления мы будем, в отличие от алгоритма Евклида, умножать и сокращать лишь на произвольные положительные числа, так как знаки остатков играют в методе Штурма основную роль. Мы получим такую систему:

h (х)=хъ + 2х*-5*3+8*2-7х-3,

1ц (х) = б*4 + 8*3-15*2 + 16* - 7, /i2(*) = 66*3-150*2 + 172* + 61, h3 (*) = - 464*2 +1135* + 723, Л 4 (*) = - 32 599 457* - 8 486 093,

Л 6(*) = -1.

Определим знаки многочленов этой системы при * = -оо и *=оо, для чего, как было указано, следует смотреть лишь на знаки старших коэффициентов и на степени этих многочленов. Мы получим такую таблицу:

	h(x)	М*)	М*)	hs(x)	М*)		Число перемен знаков
- оо	-	+	-	-	+	-	4
со	+	+	+	-	-	-	1

Таким образом, при переходе * от-оо к со система Штурма теряет три перемены знаков, а поэтому многочлен h (*) имеет ровно три действительных корня. Применим метод Штурма к другому многочлену, более простому. Пусть дан многочлен: f (*) = *3+3*2-1.

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

Система Штурма для многочлена I (*) будет:

f (*) = *® + 3*2-1

(*) = 3*2 + 6*, /а (*) = 2* + 1,

Ы*) = 1.

Найдем число перемен знаков в этой системе при х =-оо и х=оо:

		h (X)	f2 (X)	/з М	Число перемен знаков
- 00	-	+	-	+	3
00	+	+	+	+	0

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

		h w	/2 (*)	/3 W	Число перемен знаков
х - -3	-	+	-	+	3
х = - 2	+	0	-	+	2
х= -1		-	-	+	2
* = 0	-	0	+	+	1
х=1	+	+	+	+	0

Таким образом, система Штурма многочлена Ј (х) теряет по одной перемене знаков при переходе х от-3 к-2, от-1 к 0 и от 0 к 1. Корни а 1 а 2 и а 3 этого многочлена удовлетворяют, следовательно, неравенствам:

- 3<а 1<-2, - 1<а 2<0, 0<а 3<1.



5. Решение задач на вычисление границ многочлена

Схема Горнера. Решение уравнений высших степеней.

Пример 1. Разделить многочлен 2x^4-7x^3-3х ² + 5x - 1 на х + 1.

Решение. Используем схему Горнера.

	2	-7	-3	5	-1
-1	2	-9	6	-1	0

При делении 2x^4-7x^3-3х ² + 5x - 1 на х + 1 получим 2x^3-9х ² + 6x - 1

Ответ: 2x^3-9х ² + 6x - 1

Пример 2. Вычислить Р(3), где:

Р(х) = 4x^5-7x⁴ + 5х ^3-2х + 1

Решение. Используя теорему Безу и схему Горнера, получим:

	4	-7	5	0	-2	1
3	4	5	20	60	178	535

Ответ: Р(3) = 535

Решить уравнение методом Ньютона.

sin x² + cos x^2-10x. = 0.

Вычисления производить с точностью е = 0, 001.

Решение:

Вычислим первую производную функции.

F'(x)=2x cos x^2-2x sin x^2-10.

Теперь вычислим вторую производную от функции.

F''(x)=2cos x^2-4 x²sin x^2-2sin x^2-4 x²cos x² = cos x² (2-4 x²) - sin x² (2+4x²).

Теперь возьмём первый приближённый корень и проверим условие (16): f(x⁽⁰⁾) * f''(x⁽⁰⁾) > 0.

Пусть x⁽⁰⁾ = 0, 565, тогда f(0. 565)*f''(0. 565) = -4. 387 * (-0. 342) = 1. 5 > 0.

Условие выполняется, значит берём x⁽⁰⁾ = 0, 565.

Теперь составим таблицу значений, для решения данного уравнения.

k	x(k)	f(x(k))	f'(x(k))	| x(k+1) - x(k) |
0	0. 565	-4. 387	-9. 982	0. 473
1	0. 092	0. 088	-9. 818	0. 009
2	0. 101	0. 000	-9. 800	0. 000
3	0. 101

Отсюда следует, что корень уравнения х = 0, 101.

Пример 2. Решить уравнение методом Ньютона.

cos x - e^-x2/2 + x - 1 = 0

Вычисления производить с точностью е = 0, 001.

Решение: Вычислим первую производную функции.

F'(x) = 1 - sin x + x*e^-x2/2.

Теперь вычислим вторую производную от функции.

F''(x) = e^-x2/2 *(1-x²) - cos x.

Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16): f(x⁽⁰⁾) * f''(x⁽⁰⁾) > 0.

Пусть x⁽⁰⁾ = 2, тогда f(2)*f''(2) = 0. 449 * 0. 010 = 0.05 > 0,

Условие выполняется, значит берём x⁽⁰⁾ = 2.

Теперь составим таблицу значений, для решения данного уравнения.

k	x(k)	f(x(k))	f'(x(k))	| x(k+1) - x(k) |
0	2	0. 449	0. 361	1. 241
1	-0. 265	0. 881	0. 881	0. 301
2	-0. 021	0. 732	0. 732	0. 029
3	0. 000	0. 716	0. 716	0. 000
4	1. 089

Отсюда следует, что корень уравнения х = 1. 089.

Пример 3. Решить уравнение методом Ньютона.

x^{2 -} e^-x = 0.

Вычисления производить с точностью е = 0, 001.

Решение: Вычислим первую производную функции.

F'(x) = 2*x + e^-x.

Теперь вычислим вторую производную от функции.

F''(x) = 2 - e^-x.

Теперь возьмём первый приближённый корень и проверим условие (16): f(x⁽⁰⁾) * f''(x⁽⁰⁾) > 0.

Пусть x⁽⁰⁾ = 1, тогда f(2)*f''(2) = 0. 632 * 1, 632 = 1, 031 > 0,

Условие выполняется, значит берём x⁽⁰⁾ = 1.

Теперь составим таблицу значений, для решения данного уравнения.

k	x(k)	f(x(k))	f'(x(k))	| x(k+1) - x(k) |
0	1, 000	0, 632	2, 368	0, 267
1	0, 733	0, 057	1, 946	0, 029
2	0, 704	0, 001	1, 903	0, 001
3	0, 703

Отсюда следует, что корень уравнения х = 0, 703.

Пример 4. Решить уравнение методом Ньютона.

cos x -e^-x/2+x-1=0.

Решение:

Вычислим первую производную функции.

F'(x) = -sin x + e^-x/2/2+1.

Теперь вычислим вторую производную от функции.

F''(x) = -cos x - e^-x/2 /4.

Теперь возьмём первый приближённый корень и проверим условие (16): f(x⁽⁰⁾) * f''(x⁽⁰⁾) > 0.

Пусть x⁽⁰⁾ = 1, тогда f(2)*f''(2) = -0. 066 * (-0. 692) = 0. 046 > 0,

Условие выполняется, значит берём x⁽⁰⁾ = 1.

Теперь составим таблицу значений, для решения данного уравнения.

k	x(k)	f(x(k))	f'(x(k))	| x(k+1) - x(k) |
0	1, 000	-0. 066	0. 462	0. 143
1	1. 161	-0. 007	0. 372	0. 018
2	1. 162	0. 0001.	0. 363	0. 001
3	1. 162

Отсюда следует, что корень уравнения х = 1. 162.

Пример 5. Решить уравнение методом Ньютона.

-2+e^x- e^-x =0.

Решение:

Вычислим первую производную функции.

F'(x) = e^x+e^-x.

Теперь вычислим вторую производную от функции.

F''(x) = e^x-e^-x.

Теперь возьмём первый приближённый корень и проверим условие (16): f(x⁽⁰⁾) * f''(x⁽⁰⁾) > 0.

Пусть x⁽⁰⁾ = 1, тогда f(2)*f''(2) = 0. 350 * 2, 350 = 0. 823 > 0,

Условие выполняется, значит берём x⁽⁰⁾ = 1.

Теперь составим таблицу значений, для решения данного уравнения.

k	x(k)	f(x(k))	f'(x(k))	| x(k+1) - x(k) |
0	1, 000	0, 350	3, 086	0, 114
1	0, 886	0, 013	2, 838	0, 005
2	0, 881	0, 001	2, 828	0, 000
3	0, 881

Отсюда следует, что корень уравнения х = 0, 881.

Заключение

В данной работе я изучила теорию о многочленах. В ней специально был подобран интересный материал. В эту курсовую работу было внесено много примеров и задач, которые помогают лучше понять данный материал. В данной работе я описала способы нахождения корней линейных и квадратичных многочленов, то есть способ решения линейных и квадратных уравнений, в частности, метод Горнера, универсальный метод Ньютона. Также была рассмотрена теорема Штурма.

Математическое моделирование, универсальность математических методов обуславливают огромную роль математики в самых различных областях человеческой деятельности.

Основой любой профессиональной деятельности являются умения:

- строить и использовать математические модели для описания, прогнозирования и исследования различных явлений;

- осуществить системный, качественный и количественный анализ;

- владеть компьютерными методами сбора, хранения и обработки информации;

- владеть методами решения оптимизационных задач.

Широкое применение находят математические методы в естествознании и сугубо гуманитарных науках: психологии, педагогике.

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



Список литературы

1. Б.П. Демидович, И.А Марон. Основы вычислительной математики. - Москва, изд. "Наука", 2010.

2. В.М. Вержбицкий. Численные методы (линейная алгебра и нелинейные уравнения). - Москва, "Высшая школа", 2009.

3. Н.С. Бахвалов, А.В. Лапин, Е.В. Чижонков. Численные методы в задачах и упражнениях. - Москва, "Высшая школа", 2009.

4. Мэтьюз Джон, Г. Финк, Куртис, Д. Численные методы MATLAB, 3-е издание. - Москва, "Вильяс", 2008.

5. В.В. Деменчук "Многочлены и микрокалькулятор". Минск, "Высшая школа", 2009 г.

6. А.И. Кострикин "Введение в алгебру". Москва, "Физматлит", 2010 г.

7. А.Г. Курош "Курс высшей алгебры". Санкт-Петербург, "Лань", 2009 г.

8. А.А. Прокофьев, И.Б. Кожухов "Универсальный справочник по математике школьникам и абитуриентам ". Москва, "Лист Нью", 2009 г.

9. Ф. Хартман. Обыкновенные дифференциальные уравнения: Учебн. пособие / Пер. с англ. И.Х. Сабитова, Ю.В. Егорова; под ред. В.М. Алексеева. -М.: изд."Мир", 2008г. - 720 с.

Размещено на Allbest.ru

...