Автор работы: Пользователь скрыл имя, 03 Апреля 2013 в 18:37, курсовая работа
Самые ранние из известных аналогов алгебраических уравнений содержатся в папирусе Ринда и, очевидно, компилированы из более ранних работ египтянином Амесом приблизительно в 1650 или 1700 г. до нашей эры. Мы находим, например, следующую задачу: «Количество и его седьмая часть, сложенные вместе, дают 19. Чему равно количество?». Очевидно, задача состоит в том, чтобы решить уравнение х + (l/7)x = 19, как мы сказали бы сегодня. Из-за недостатка удобных алгебраических обозначений египтяне пользовались громоздким методом, известным впоследствии как метод «ложного положения».
9. [Возврат к циклу] Если ti-flag = 1, то перейти к шагу 7; иначе выполнять {ti-flag := 0; перейти к шагу 3}.
10. [Отделить отрицательные корни] Если р(х) ≠ р(—х), то выполнять { положить pn-flag := 1; ti-flag := 0; pw(x) := р(—х), так что отрицательные корни становятся положительными; Т := ø; вычислить число v вариаций знаков в последовательности коэффициентов полинома pw(x) и перейти к шагу 2}, иначе выход. (Если мы выходим здесь, то отрицательные корни симметричны положительным и мы уже знаем их изолирующие интервалы. Конечно, в этом случае интервалы, полученные нами для отрицательных корней, находятся в положительной полуплоскости и должны быть отображены на соответствующие интервалы в отрицательной полуплоскости — тривиальное действие.)
6. Пример
Отделим вещественные корни уравнения р(х) = х3 — 7х + 7 = 0, где p(0) ≠ 0. Применяя алгоритм ACF1978, получаем следующие результаты:
Шаг 1. Здесь мы полагаем pw(x) := х3 — 7х + 7, pn-flag := 0, ti-flag := 0, Т := ø и вычисляем значение v, равное 2. (Мы сначала отделяем положительные корни.)
Шаг 2а. Поскольку v > 1, мы полагаем pм(х) := х3 — 7х + 7, М(x) := х, vм := 2 и переходим к шагу 4.
Шаг 4. Чтобы использовать правило Коши, мы сначала полагаем х := 1/х в рм(x) =0 и получаем 7х3 — 7х2 + 1 = 0; затем мы применяем BPR к последнему уравнению и получаем 1/b = 1. Поэтому b = 1.
Шаг 5. На этом шаге мы модифицируем рм(x) := pм(1 + х) = x3 + Зх2 - 4х + 1 и М(х):= М(1 + х) = х + 1; очевидно, рм(0) ≠ 0.
Шаг 6. Полагаем v' := 2, модифицируем pм1(x) := pм(1 + х) = x3 + 6х2 +5х+ 1 и М1(х) := М(1 + x) = х + 2 и переходим к шагу 8.
Шаг 8. На этом шаге мы полагаем ti-flag := 1 и вычисляем vм1, равное 0.
Шаг 9. Поскольку ti-flag = 1, мы переходим к шагу 7.
Шаг 7. v' ≠ vм1, и мы вычисляем новые значения pм1(x) = x3 – х2 -2х + 1 и М1(х) = (х + 2)/(х + 1). [Заметим, что pм1(x) := рi(1 + x) и М1(х) := Mi(1 + x), где рi(х) = х3 - 4х2 + Зх + 1 и Мi(x) = (х + 1)/х мы получили, полагая х = 1/х в рм(x) и М(х) соответственно.]
Шаг 8. На этом шаге мы устанавливаем ti-flag := 2 и вычисляем значение vм1, которое оказывается равным 2. В этом случае мы полагаем
Т := {[х3 – х2 - 2х + 1, (х + 2)/(х + 1), 2]}.
Шаг 9. Поскольку ti-flag = 2, мы устанавливаем ti-flag := 0 и переходим к шагу 3.
Шаг 3. Т ≠ 0, и мы удаляем из него первую тройку рм(x) = x3 — х2 — 2х + 1, М(х) = (х + 2)/(х+1), vм = 2 и переходим к шагу 4.
Шаг 4. Снова мы сначала полагаем х := 1/х в pм(x) = 0 и получаем х3 + 2х2 - х + 1 = 0; затем мы применяем BPR к последнему уравнению и получаем 1/b = 4. Поэтому b = 1/4 < 1, и мы переходим к шагу 6.
Шаг 6. Полагаем v’ := 2, модифицируем pм1(x) := pм(1 + х) = x3 + 2x2 – x - 1 и M1(x) := М(1 + x) = (x + 3)/(x + 2) и переходим к шагу 8.
Шаг 8. Здесь мы устанавливаем ti-flag := 1 и вычисляем значение vм1, которое оказывается равным 1. В этом случае мы выводим первый изолирующий интервал (1, 3/2), полученный из М1(x) = (x + 3)/(х + 2).
Шаг 9. Поскольку ti-flag = 1, мы переходим к шагу 7.
Шаг 7. v' ≠ vм1, и мы вычисляем новые значения pм1(x) = x3 + х2 - 2х - 1 и М1(х) = (2х + 3)/(х + 2).
Шаг 8. Здесь мы устанавливаем ti-flag := 2 и вычисляем значение vм1, которое оказывается равным 1. В этом случае мы выводим второй изолирующий интервал (3/2,2), полученный из М1(х) = (2х + 3)/(х + 2).
Шаг 9. Поскольку fi-flag = 2, мы устанавливаем ti-flag := 0 и переходим к шагу 3.
Шаг 3. Т = ø и pn-flag = 0; поэтому мы переходим к шагу 10.
Шаг 10. Мы теперь отделяем отрицательные корни. Поскольку р(x) ≠ р(—х), мы полагаем pn-flag := 1, ti-flag := 0, рw(х) := р(—х) = х3 — 7х — 7, Т := ø, вычисляем значение v, которое оказывается равным 1, и переходим к шагу 2.
Шаг 2. Здесь v = 1, откуда следует, что изолирующим интервалом для отрицательного корня является (-∞,0), и, поскольку pn-flag = 1, мы выходим.
Полностью процесс проиллюстрирован на рис. 2.
Рис. 2.
Двоичное дерево, полученное для отделения положительных корней уравнения х3 — 7х + 7 = 0.
Литература:
Информация о работе Отделение действительных корней многочлена: метод цепных дробей