Дискретно-непрерывная математика (стр. 91 )

Если теперьи

то мы показываем тем же методом, что и раньше, что имеется нуль Требование выполнено тогда и

только тогда, когда

Это эквивалентно неравенству

(29)

вместе с

(30)

Неравенства (29) и (30) гарантируют выполнение условий теоремы Канторовича о существовании нуля в интервале Х(0).

Если то f не имеет нулей в Х(0). Условие выполнено тогда и только тогда, когда

т. е. при тогда и только тогда, когда

Это yверждение может быть аналогичным образом исполь­зовано для доказательства теорем об исключении в банаховых пространствах.

Микромодуль 27

Методы одновременной локализации вещественных корней многочленов

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

Дан вещественный многочлен

(1)

и мы предполагаем в дальнейшем, что

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

Предположим сначала, что все эти локализующие интервалы попарно не пересекаются, т. е.

(2)

Многочлен р(х) можно записать в виде

или

откуда следует

Если мы выберемто получим, что

и из (9 п.7.1) следует, что

Таким образом, интервальное выражение, стоящее в правой части этого равенства, задает новый локализующий интервал X(1,і), для которого верно

Это соотношение порождает следующую итерационную схему:

(3)

где

Для интервального выражения в знаменателе вводится сокращение

Итерационная схема (3) задает полношаговый метод лока­лизации корней многочлена Если в мы всегда используем последнее вычисленное значение локализую­щих интервалов, то получаем

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

выражений Функция sign для интервалов

определяется соотношением

(4)

Интервалы также содержащие корни определяются тогда следующим образом:

Заметим, что всегда имеет место соотношение

Используя только что введенные новые локализующие интер­валы, вычисляем теперь новое значение знаменателя с по­мощью выражения

Применяя его, приходим к следующему модифицирован­ному короткошаговому методу:

(5)

Оба метода (3), (5) можно считать интервальными вариан­тами известных методов одновременного нахождения корней ве­щественных многочленов. Преимущество интер­вальных вариантов этих методов состоит в том, что они не только дают локализующие интервалы для корней, но и всегда сходятся при сделанных выше допущениях. Это устанавливается в следующей теореме.

Теорема 1. Пусть дан многочлен (1), имеющий п простых корней

причем известны локализующие интервалы

для которых верно (2). Тогда последовательность при­ближений вычисленная по формулам (3) (соответственно (5)), либо удовлетворяет условиям

и

либо стабилизируется за конечное число шагов на точке [ξ(i) , ξ(i)].

Теорема 1 получается тем же методом, что и соответствую­щее утверждение в теореме 1 микромодуль 26, так как каждое из интерваль­ных выраженийобладает либо свойством (2 микромодуль 26), либо соответствующим свойством в интервале для m2 < 0.

Выбирая в обоих методах

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

Теорема 1 частично сохраняется и в случае, когда многочлен имеет кратные корни. Если выпишем эти кратные корни вместе

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

Можно обобщить метод (3) таким образом, что в теореме 1 удастся заменить предположение (2), касающееся локализую­щих интерваловна более слабое условие. Для этого следует полностью использовать возможность варьирова­ния значенияа не применять систематическую про­цедуру выбора, где это значение полагают равным, например, среднему арифметическому границ интервала.

Теперь рассмотрим подробнее поведение последователь­ности

Для метода (3) получаем оценку

с помощью (9 п.7.2), (10 п.7.2) и (14 п.7.2). Так как

отсюда следует, что