ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2021
Просмотров: 3470
Скачиваний: 14
§
12
.
Приближенное вычисление корней многочленов
77
Следовательно, построенная таким способом система многочленов
f
0
(=
f
)
, f
0
, . . . , f
k
=
c
удовлетворяет условию 2) определения 1.
Рассматривая условие 1), допустим, что соседние многочлены
f
m
и
f
m
+1
имеют общий корень
α
. Тогда из равенства (3) следует, что
α
– корень много-
члена
f
m
−
1
. Из равенства
f
m
−
2
=
f
m
−
1
q
m
−
1
−
f
m
получаем, что
f
m
−
2
(
α
) = 0
.
Продолжая эти рассуждения, получим, что
α
– общий корень для
f
и
f
0
,
что противоречит простоте корня
α
.
Наконец, выполнение условия 3) следует из равенства (3):
если
f
m
(
α
) = 0
, то
f
m
−
1
(
α
) =
−
f
m
+1
(
α
)
.
Лемма доказана.
Определение 2.
Пусть
f
0
, f
1
, . . . , f
k
– некоторая система Штурма для
многочлена
f
. Если
c
∈
R
и
f
(
c
)
6
= 0
,
то рассмотрим упорядоченный набор
чисел
f
0
(
c
) =
f
(
c
)
, f
1
(
c
)
, . . . , f
k
(
c
)
вещественных чисел, и вычеркнем из него все числа, равные нулю. Число
перемен знаков в оставшемся наборе чисел назовем
числом перемен знаков
в системе Штурма для многочлена
f
в точке
x
=
c
и это число обозначим
символом
S
(
c
)
(таким образом, определено отображение
S
:
R
→
N
S
{
0
}
)
.
Т е о р е м а (теорема Штурма).
Пусть вещественные числа
a, b
(
a < b
)
не являются корнями многочлена
f
с вещественными коэффициента-
ми и не имеющего кратных корней. Тогда
S
(
a
)
≥
S
(
b
)
и разность
S
(
a
)
−
S
(
b
)
равна числу вещественных корней многочлена
f
, заключенных между
a
и
b
.
Доказательство.
Покажем, что заданная в определении 2 функция
S
:
R
→
N
S
{
0
}
)
,
является невозрастающей. Пока аргумент
x,
возрастая, не
совпадает с некоторым корнем одного из многочленов Штурма, знаки мно-
гочленов системы Штурма не будут меняться, и поэтому функция
S
будет
постоянной на таких интервалах.
Имея в виду условие 2 из определения 1, остается рассмотреть два слу-
чая: 1) переход
x
через корень одного из промежуточных многочленов Штур-
ма
f
1
, f
2
, . . . , f
k
−
1
и 2) переход
x
через корень самого многочлена
f
.
Допустим, что
x
0
– корень одного из промежуточных многочленов
f
m
,
1
≤
m
≤
k
−
1
.
Тогда, согласно условию 3), числа
f
m
−
1
(
x
0
)
и
f
m
+1
(
x
0
)
имеют противоположные знаки. Ввиду непрерывности многочленов можно
указать интервал
(
x
0
−
δ, x
0
+
δ
)
такой, что числа
f
k
−
1
(
x
)
, f
k
+1
(
x
)
, x
∈
(
x
0
−
δ, x
0
+
δ
)
отличны от нуля и имеют противоположные знаки. Отсюда следует,
что число перемен знаков в наборе чисел
f
k
−
1
(
x
)
, f
k
(
x
)
, f
k
−
1
(
x
)
78
Глава 2. Алгебраические объекты; Алгебра многочленов
не меняется для всех
x
∈
(
x
0
−
δ, x
0
+
δ
)
.
Это приводит к тому, что в системе
Штурма перемены знака могут лишь перемещаться (но не возникают вновь и
не исчезают). Поэтому число
S
(
x
)
при переходе через число
x
0
не меняется.
Пусть теперь
x
0
– корень многочлена
f
. По условию 1 (из определения
2) число
x
0
не будет корнем для
f
1
. Следовательно,
f
1
6
= 0
на некотором
отрезке
(
x
0
−
δ, x
0
+
δ
)
,
и поэтому
f
1
имеет на нем постоянный знак, для
определенности пусть положительный. Тогда по свойству 4) сам многочлен
f
при переходе через точку
x
0
меняет знак с минуса на плюс, т.е.
f
(
x
0
−
δ
)
<
0
, f
(
x
0
+
δ
)
>
0
.
Тогда для двух наборов чисел
f
(
x
0
−
δ
)
, f
1
(
x
0
+
δ
)
и
f
(
x
0
−
δ
)
, f
1
(
x
0
+
δ
)
соответствующие системы знаков имеют вид
−
,
+; +
,
+
,
т.е. в системе Штурма теряется одна перемена знаков.
Таким образом, функция
S
изменяет свое значение лишь при переходе
через корень многочлена, причем она уменьшает свое значение на единицу.
Итак,
S
(
a
)
−
S
(
b
)
равно числу корней многочлена
f
на отрезке
[
a, b
]
.
Теорема доказана.
Непосредственно из леммы 1 и доказанной теоремы получаем
Следствие.
Число вещественных корней многочлена
f
(
z
) =
a
0
z
n
+
a
1
z
n
−
1
+
· · ·
+
a
n
с вещественными коэффициентами и имеющего простые
корни равно
S
(
−
b
)
−
S
(
b
)
,
где
b
= 1 + max
1
∈
k
≤
n
|
a
k
|
|
a
0
|
.
Замечание.
Из теоремы Штурма и еe следствия вытекает, что можно
указать отрезок
[
−
b, b
]
и такое его разбиение вида
−
b
≤
b
1
<
· · ·
< b
m
< b,
что на каждом из отрезков
[
−
b, b
1
]
,
[
b
1
, b
2
]
, . . . ,
[
b
m
, b
]
находится ровно один
корень многочлена
f
. В этом случае говорят, что
корни многочлена
f
отде-
лены.
Это замечание позволяет ограничиться далее только рассмотрением мно-
гочлена
f
с единственным простым корнем
x
0
на интервале
(
a, b
)
. Укажем
способ приближенного вычисления корня
x
0
,
называемый
методом линейной
интерполяции
.
Геометрически метод линейной интерполяции заключается в том, что
функция
f
на отрезке
[
a, b
]
заменяется линейной функцией, соединяющей
точки
(
a, f
(
a
))
и
(
b, f
(
b
))
(см. рис. 13). В качестве приближенного значения
корня берется абсцисса точки пересечения линейной функции с осью абсцисс
§
12
.
Приближенное вычисление корней многочленов
79
Рис.13
т.е. число
x
1
=
bf
(
a
)
−
af
(
b
)
f
(
a
)
−
f
(
b
)
.
Если
f
(
x
1
)
6
= 0
,
то этот же прием применяется к интервалу
[
a, x
1
]
, если
f
(
x
1
)
<
0
, и интервалу
[
x
1
, b
]
, если
f
(
x
1
)
>
0
.
В результате получим после-
довательность
(
x
1
, x
2
, . . .
)
,
сходящуюся к
x
0
.
Упражнения к §12
1. Составьте ряд Штурма и отделите вещественные корни многочленов
а)
f
1
(
x
) =
x
3
−
3
x
−
1
,
б)
f
2
(
x
) =
x
4
−
2
x
3
+
x
2
−
2
x
+ 1
,
в)
f
3
(
x
) =
x
4
−
x
3
−
2
x
+ 1
.
2. Определите число вещественных корней многочлена
f
(
x
) =
x
3
+
px
+
q
,
где
p, q
∈
R
.
3. Укажите два последовательных приближения метода линейной интер-
поляции к вещественным корням следующих многочленов
a
)
f
(
x
) =
x
3
−
10
x
−
5;
b
)
f
(
x
) =
x
3
+ 2
x
−
30;
c
)
f
(
x
) =
x
3
−
3
x
2
−
13
x
−
7;
d
)
f
(
x
) =
x
3
−
3
x
2
−
x
+ 2
.
4. Определите число вещественных корней многочлена
f
(
x
) =
x
5
−
5
ax
3
+ 5
a
2
x
+ 2
b, a, b
∈
R
.
80
Глава 2. Алгебраические объекты; Алгебра многочленов
5. Пусть дан многочлен
f
(
x
) =
x
5
+ 3
x
2
+ 7
.
Какое утверждение ложно?
1)
f
не имеет положительных корней;
2)
f
имеет вещественный корень;
3)
f
не имеет рациональных корней;
4) сумма всех корней
f
отлична от нуля?
81
ГЛАВА Ш. ЛИНЕЙНАЯ АЛГЕБРА
§
13. Метод Гаусса решения систем линейных уравнений
Пусть
K
– некоторое поле. В этом параграфе излагается метод Гаусса
построения решений системы линейных уравнений вида
a
11
x
1
+
a
12
x
2
+
· · ·
+
a
1
n
x
n
=
b
1
,
a
21
x
1
+
a
22
x
2
+
· · ·
+
a
2
n
x
n
=
b
2
,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(1)
a
m
1
x
1
+
a
m
2
x
2
+
· · ·
+
a
mn
x
n
=
b
m
,
где
x
1
, x
2
, . . . , x
n
∈
K
– неизвестные, подлежащие определению (число их
n
не обязательно совпадает с числом
m
уравнений) и числа
a
11
, a
12
, . . . ,
a
mn
, b
1
, . . . , b
m
принадлежат полю
K
. Числа
a
11
, a
12
, . . . , a
mn
,
называемые
ко-
эффициентами
системы (1), часто записывают в виде прямоугольной табли-
цы
a
11
a
12
. . .
a
1
n
a
21
a
22
. . .
a
2
n
...
...
...
...
a
m
1
a
m
2
. . . a
mn
.
(2)
Таблицу вида (2) называют
матрицей размера
m
×
n
с элементами поля
K
(безотносительно к системе уравнений (1)), состоящей из
m
строк и
n
столб-
цов. При фиксированном
i
(1
≤
i
≤
m
)
упорядоченный набор
(
a
i
1
, . . . , a
in
)
∈
K
n
называется
i
-
ой строкой матрицы
. При фиксирован-
ном
j
(1
≤
j
≤
n
)
набор
(
a
1
j
, . . . , a
mj
)
∈
K
m
называется
j
-
ым столбцом
матрицы
. Числа
a
ij
,
1
≤
i
≤
m,
1
≤
j
≤
n
называют
элементами матри-
цы
, где число
i
указывает на номер строки, а число
j
- на номер столбца, на
пересечении которых стоит число
a
ij
. Если
m
=
n
(т.е.число строк равно чис-
лу столбцов), то матрица (2) называется квадратной (иногда "порядка
n
").
Числа
a
11
, a
22
, . . . , a
nn
называются
главной диагональю
квадратной матрицы.
Определение 1.
Упорядоченный набор
(
α
1
, α
2
, . . . , α
n
)
∈
K
n
называ-
ется решением системы линейных уравнений (1), если каждое из уравнений
обращается в тождество после замены в нем неизвестных
x
k
соответствую-
щими числами
α
k
.
Определение 2.
Система уравнений (1) называется
совместной
, если
она имеет хотя бы одно решение, и
несовместной
, если она не имеет решений.